随机梯度下降(Stochastic Gradient Descent, SGD)是 随机 和 优化 相结合的产物,是一种很神奇的优化方法,属于梯度下降的一种,适用于 大规模的问题 。 要想扯清楚它,还得先谈谈梯度下降。众所周知,每个优化问题会有一个目标函数f(w),梯度下降就是采用迭代的策略,从初始点w1开始,每次沿着目标函数在当前点的负梯度方向前进一定的步长,即 wt+1=wtηtf(wt) 只要步长ηt设置合理,这样可以得到一个单调递减的序列{f(w1),…,f(wt),…},直至最终不再下降,即可得到最优解w。对于一般优化问题,梯度下降可以找到局部最优解,对于凸优化问题,梯度下降可以得到全局最优解,下面我们只考虑凸优化问题。 考虑如下的目标函数 f(w)=∑i=1nf(w,xi) 其中xi是与w无关的常向量。当n为很大的正整数时,例如几十万甚至几百万时,计算梯度 f(w)=∑i=1nfi(w,xi) 代价很大,那么这个方法就行不通了。但是这样的问题在机器学习领域又很常见,比如感知机(Perceptron),支持向量机(Support Vector Machine, SVM),套索(Least Absolute Shrinkage and Selection Operator, LASSO)等算法都可以写成如下的形式 λΩ(w)+1n∑i=1nL(w,xi) 其中Ω(w)是关于w的凸正则化项,L(w,xi)是关于w的凸损失函数。因此我们需要克服梯度下降计算开销太大的问题,那么,随机梯度下降就呼之欲出了。 随机梯度下降的基本想法很简单,就是不直接计算梯度的精确值,而是用梯度的 无偏估计 g(w)来代替梯度,即 wt+1=wtηtg(wt) 其中E[g(wt) | wt]=f(wt)。 那么肯定有人要问,这么简单,靠不靠谱啊?可以证明的是在某些条件下,这样得到的序列{f(w1),…,f(wt),…}中的 最小值依期望收敛 到f(w)。具体来说,设 ηt≥0, ∑t=1∞η2t=||η||22<∞, ∑t=1∞ηt=∞ 其中η=[η1,η2,…]是无穷维向量,并假设存在常数G和R满足,对于任意t有E[||g(wt)||22]≤G2,E[||w1w||22]≤R2,并记fbest(t)=min{f(w1),…,f(wt)},那么当t→∞时,E[fbest(t)]→f(w)。 结合条件期望的性质和f的凸性知 E[||wt+1w||22 | wt]=E[||wtηtg(wt)w||22 | wt]=E[||wtw||22 | wt]2ηtE[g(wt)(wtw) | wt]+η2tE[g(wt)2 | wt]=||wtw||222ηtE[g(wt) | wt](wtw)+η2tE[g(wt)2 | wt]=||wtw||222ηtf(wt)(wtw)+η2tE[g(wt)2 | wt]≤||wtw||222ηt(f(wt)f(w))+η2tE[g(wt)2 | wt] 两边同时对wt取期望,由重期望公式知 E[||wt+1w||22]≤E[||wtw||22]2ηt(E[f(wt)]f(w))+η2tG2 重复利用该式可得 E[||wt+1w||22]≤E[||w1w||22]2∑j=1tηj(E[f(wj)]f(w))+G2∑j=1tη2j 注意E[||wt+1w||22]≥0,E[||w1w||22]≤R2以及∑tj=1η2j≤||η||22,于是 2∑j=1tηj(E[f(wj)]f(w))≤R2+G2||η||22 结合E[fbest(t)]≤E[f(wj)]可知 E[fbest(t)]f(w)≤R2+G2||η||222∑tj=1ηj 由于∑∞t=1ηt=∞,故当t→∞时有E[fbest(t)]→f(w)。 此外,由Markov不等式知对于>0有 P(fbest(t)f(w)≥)≤E[fbest(t)f(w)]≤R2+G2||η||222∑tj=1ηj 即当t→∞时有P(fbest(t)f(w)≥)→0。 下面举几个机器学习里的具体例子,设训练集S有n个样本,即S={(x1,y1),(x2,y2),…,(xn,yn)},由于有 Exi[L(w,xi)]=∑i=1n1nL(w,xi)=(1n∑i=1nL(w,xi)) 成立,于是一个很直观的想法就是每次更新只随机选取一个样本xi来计算梯度。
|