机器学习中很多时候都是在求解无约束条件的最优化问题，比如：感知机、逻辑斯谛回归、条件随机场的求解。在求解无约束最优化问题最常用的两类方法是 梯度下降法 和 牛顿法，可参考《统计学习方法》的附录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参数）;
区别
梯度下降是一阶收敛，牛顿法是二阶收敛，牛顿法相比梯度下降收敛更快。
如果更通俗点，比如你想找一条最短路径到一个盆地的最底部，梯度下降每次从你当前所处位置选一个坡度最大的方向走一步；而牛顿法在选择方向时，不仅会考虑坡度是否大，还会考虑当你走了一步后，坡度是否会变得更大。所以说牛顿法比梯度下降法看得更远一点，能更快地到达盆地的最底部。
从几何上说，牛顿法是用二次曲面去拟合你当前所处位置的局部曲面，而梯度下降是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比局部曲面更好，所以牛顿法选择下降路径会更符合最优的路径。
参考文献
《统计学习方法》附录A 与 附录B