机器学习笔记-梯度下降法和牛顿法

2020-09-18

机器学习中很多时候都是在求解无约束条件的最优化问题,比如:感知机、逻辑斯谛回归、条件随机场的求解。在求解无约束最优化问题最常用的两类方法是 梯度下降法牛顿法,可参考《统计学习方法》的附录A 和 附录B。 这篇笔记记录下自己对两类方法的理解。

梯度下降法

在机器学习任务中,要求目标函数 $f(x)$ 的使其最小的 $x$ 的值。梯度下降是一种迭代算法,常用来求解这类问题。基本步骤为:选取初值;梯度方向不断迭代;更新 $x$ 的值找到最逼近的解。

选取 $x^{k}$ ,计算 $f(x^{k})$$k$ 初始值为0;

$f(x^{k+1})$$x^{k}$ 处一阶泰勒展开得: $f(x^{k+1}) = f(x^{k} + \Delta t) \approx f(x^{k}) + f'(x^{k}) \Delta t$ ,按梯度方向不断迭代逼近可取 $\Delta t = - \lambda \cdot f'(x^k)$ ,其中 $\lambda$ 为步长;

重复以上两步,直到迭代找出相应的 $x^{k+1}$ 为止,即 $||f(x^{(k+1)} - f(x^k) || < \epsilon$ ,停止迭代,令 $x=x^{k+1}$

个人理解:$\Delta t = - \lambda \cdot f'(x^k)$ 这里的 $\lambda$ 为步长,可由一维搜索确定(比如GBDT);也可直接赋一个小的数即可(比如神经网络模型)。

牛顿法

牛顿法是二阶泰勒展开,而梯度下降法是一阶泰勒展开。其基本步骤如下:

选取 $x^k$ ,计算 $f(x^k)$$k$ 初始值为0;

$f(x^{k+1})$$x^k$ 处二阶泰勒展开得: $f(x^{k+1}) = f(x^k + \Delta t) \approx f(x^k) + f'(x^k) \cdot \Delta t + \frac{1}{2} \cdot f''(x^k) \cdot (\Delta t)^2$ ,通常将一阶导和二阶导分别记为 $g$$h$$f(x^{k+1}) \approx f(x^k) + g \cdot \Delta t + \frac{1}{2} \cdot h \cdot (\Delta t)^2$ ,因为要使 $f(x^{k+1})$ 取得极小值,则令 $\frac{ \partial ( g \Delta t + \frac{1}{2} h \Delta t^2 ) } {\Delta t} = 0$ ,得到 $\Delta t = - \frac{g}{h}$ ,则 $x^{k+1} = x^{k} - \frac{g}{h}$ ,按二阶梯度方向不断迭代逼近;

重复以上两步,直到迭代找出相应的 $x^{k+1}$ 为止;

注:当参数 $x^k$ 推广到向量形式,迭代公式 $x^{k+1} = x^k - H^{-1} \cdot g$ ,这里 $H$ 是海赛矩阵。

个人理解:这里统计学习方法里没有引入 $\lambda$ 步长,这里是可以加上 $\lambda$ 步长,在很多机器学习框架里已经加入了步长(比如XGBoost中的eta参数);

区别

梯度下降是一阶收敛,牛顿法是二阶收敛,牛顿法相比梯度下降收敛更快。

如果更通俗点,比如你想找一条最短路径到一个盆地的最底部,梯度下降每次从你当前所处位置选一个坡度最大的方向走一步;而牛顿法在选择方向时,不仅会考虑坡度是否大,还会考虑当你走了一步后,坡度是否会变得更大。所以说牛顿法比梯度下降法看得更远一点,能更快地到达盆地的最底部。

从几何上说,牛顿法是用二次曲面去拟合你当前所处位置的局部曲面,而梯度下降是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比局部曲面更好,所以牛顿法选择下降路径会更符合最优的路径。

avatar

参考文献

  1. 梯度下降法与牛顿法比较

  2. 《统计学习方法》附录A 与 附录B