漫谈在线学习:在线梯度下降
作者:李沐
在线凸优化
回顾下上次聊的专家问题,在时刻专家的损失是,于是这个时刻Weighted Majority(WM)损失的期望是,是关于这个专家的损失的一个线性组合(因为权重关于的和为1,所以实际上是在一个simplex上)。将专家在时刻的损失看成是这个时候进来的数据点,于是我们便在这里使用了一个线性的损失函数。
虽然WM的理论在上个世纪完成了[Littlestone 94, Freund 99],将其理论拓展到一般的凸的函数还是在03年由Zinkevich完成的。当时Zinkevich还是CMU的学生,现在在Yahoo! Research。话说Yahoo! Research的learning相当强大,Alex Smola(kernel大佬),John Langford(有个非常著名的blog),这些年在large scale learning上工作很出色。
回到正题。我们提到在online learning中learner遭受的累计损失被记成,如果挑选的策略集是凸的,而且损失函数关于是凸的,那么我们称这个问题为Online Convex Optimization(OCP)。通常我们将表示成一个向量,例如WM中的维护的专家信任度,所以这时。
在线梯度下降
Zinkevich提出的算法很简单,在时刻做两步操作,首先利用当前得到数据对进行一次梯度下降得到,如果新的不在中,那么将其投影进来:
这里是关于的导数(如果导数不唯一,就用次导数),是学习率,是投影子,其将不在中的向量投影成一个与最近的但在中的向量(如果已经在中了,那就不做任何事),用公式表达就是。此算法通常被称之为 Online Gradient Descent。
先来啰嗦几句其与离线梯度下降的区别。下图是一个区别示意图。在离线的情况下,我们知道所有数据,所以能计算得到整个目标函数的梯度,从而能朝最优解迈出坚实的一步。而在online设定下,我们只根据当前的数据来计算一个梯度,其很可能与真实目标函数的梯度有一定的偏差。我们只是减少,而对别的项是否也是减少就难说了。当然,我们一直在朝目标前进,只是可能要走点弯路。
那online的优势在哪里呢?其关键是每走一步只需要看一下当前的一个数据,所以代价很小。而offline的算法每走一个要看下所有数据来算一个真实梯度,所以代价很大。假定有100个数据,offline走10步就到最优,而online要100步才能到。但这样offline需要看1000个数据,而online只要看100个数据,所以还是online代价小。
于是,我们很容易想到,offline的时候能不能每一步只随机抽几个数据点来算一个梯度呢?这样每一步代价就会很少,而且可能总代价会和online一样的少。当然可以!这被称之为Stochastic Gradient Descent,非常高效,下回再谈把。
在这里,的作用是什么呢?记得在learning中的目标函数通常是损失+罚()的形式。例如ridge regression就是平方误差+罚,lasso是平方误差+罚,SVM是hinge loss+罚。最小化这个目标函数可以等价于在的限制下最小化。和是一一对应的关系。实际上就是定义了一个凸子空间,例如使用罚,既,时就是一个半径为的球。所以,Online Gradient Descent可以online的解这一类目标函数,只是对于不同的罚要选择不同的投影子。
Regret Bound分析
记投影前的,以及offline最优解。因为是凸的且在其中,所以对投影只会减少其与的距离,既。简记,注意到
由于是凸的,所以有
取固定的,对进行累加就有。记的直径为,且对所有有成立(既Lipschitz常数为),再取,那么
这个bound可以通过设置变动的学习率加强,具体下次再谈咯。
本文转自 https://mli7.wordpress.com/2011/04/08/online_learning_2/。