线性回归/14. 最优化问题的其他算法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "机器学习的本质是求解最优化问题，除了之前提到的线性问题的两种解法之外，还有很多相关的优化算法，这些算法不仅适用于线性模型，也适用于非线性模型。\n",
    "\n",
    "### 正规方程的优化算法\n",
    "\n",
    "在正规方程的计算过程中，我们既要对矩阵求逆，又要求矩阵乘法，如果直接计算，算法复杂度往往很高。这里的矩阵计算有很多优化方法，譬如对 X′X 进行 Cholesky 分解，或者对 X 进行 QR 分解等等。\n",
    "\n",
    "### 梯度下降的优化算法\n",
    "\n",
    "前面介绍了梯度下降的三种形式：BGD、SGD 和 MBGD。但在实际运用中还会面临很多挑战，具体的可以参考 Sebastian Ruder 的这篇论文 [An overview of gradient descent optimization algorithms](https://arxiv.org/pdf/1609.04747.pdf)，这里是相应的 [中文翻译](https://blog.csdn.net/google19890102/article/details/69942970)，论文中提到了 6 种优化算法：\n",
    "\n",
    "* Momentum（动量法）\n",
    "* NAG（Nesterov加速梯度下降法，Nesterov accelerated gradient）\n",
    "* Adagrad\n",
    "* Adadelta\n",
    "* RMSprop\n",
    "* Adam（自适应矩估计，Adaptive Moment Estimation）\n",
    "\n",
    "### 无约束项优化算法\n",
    "\n",
    "\n",
    "\n",
    "#### 牛顿法\n",
    "\n",
    "梯度下降主要是从目标函数的一阶导数推导而来的，形象点说，就是每次朝着当前梯度最大的方向收敛；而牛顿法是二阶收敛，每次考虑收敛方向的时候，还会考虑下一次的收敛的方向是否是最大（也就是梯度的梯度）。可以参考下图，红线为牛顿法，绿线为梯度下降：\n",
    "\n",
    "![](../images/newton.jpeg)\n",
    "\n",
    "本质上来看，牛顿法是二阶收敛，而梯度下降则为一阶收敛，所以牛顿法更快。简单来说，梯度下降是从所处位置选择一个坡度最大的方向走一步，而牛顿法则在选择方向时，不仅考虑坡度，还会考虑下一步的坡度是否会变得更大。\n",
    "\n",
    "几何上来说，牛顿法是用一个二次曲面去拟合当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。\n",
    "\n",
    "牛顿法的优点是二阶收敛，收敛速度快；它的缺点是每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。\n",
    "\n",
    "#### 高斯-牛顿迭代算法\n",
    "\n",
    "由于牛顿法需要求解二阶导，也就是 Hessian matrix，运算量大，不利于实现，所以通常在牛顿法的基础上用去掉二阶项，用一阶项来近似二阶导，从而保证了计算效率。\n",
    "\n",
    "高斯-牛顿迭代算法（Gauss-Newton iteration method）是另一种经常用来求解非线性最小二乘的迭代法，其原理是利用了 **泰勒展开公式**，其最大优点是收敛速度快。\n",
    "\n",
    "Taylor 级数求得原目标函数的二阶近似：\n",
    "\n",
    "$$\n",
    "f(x) \\approx \\phi(x) \n",
    "= f(x^{(k)}) + \\nabla f(x^{(k)})(x - x^{(k)}) + \\frac{1}{2}(x - x^{(k)})^T \\nabla^2 f(x^{k})(x - x^{(k)})\n",
    "$$\n",
    "\n",
    "把 $x$ 看作自变量，所有带有 $x^{(k)}$ 的项看作常量，令一阶导数等于 0，即可求近似函数的最小值：\n",
    "\n",
    "$$\n",
    "P_k = -(\\nabla^2 f(x_k))^{-1} \\nabla f(x_k) = - {Hesse}^{-1} {Jacobi}\n",
    "$$\n",
    "\n",
    "上边的 Hesse 矩阵，是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率。\n",
    "\n",
    "对于二元的情况，根据上述泰勒展开公式及求导，取0，可以得到如下迭代公式：\n",
    "\n",
    "$$\n",
    "x_{k+1} = x_k - \\frac{f'(x_k)}{f''(x_k)}\n",
    "$$\n",
    "\n",
    "可以看出，因为我们需要求矩阵逆，当 Hesse 矩阵不可逆时无法计算。而且矩阵的逆计算复杂度为n的立方，当规模很大时，计算量超大，通常改良做法是采用 **拟牛顿法**，如 BFGS、L-BFGS 等。此外，如果初始值离局部极小值太远，Taylor 展开并不能对原函数进行良好的近似。\n",
    "\n",
    "#### 拟牛顿法\n",
    "\n",
    "**拟牛顿法**（Quasi-Newton Methods）的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。\n",
    "\n",
    "#### LM 方法\n",
    "\n",
    "Levenberg-Marquardt 方法，是由于高斯-牛顿方法在计算时需要保证矩阵的正定性，于是引入了一个约束，从而保证计算方法更具普适性。\n",
    "\n",
    "### 共轭梯度\n",
    "\n",
    "共轭梯度法（Conjugate gradient, CG）\n",
    "\n",
    "https://cosx.org/2016/11/conjugate-gradient-for-regression/\n",
    "\n",
    "### 近端梯度\n",
    "\n",
    "近端梯度法（Proximal Gradient Method ，PG）\n",
    "\n",
    "https://blog.csdn.net/qq547276542/article/details/78251779\n",
    "\n",
    "http://roachsinai.github.io/2016/08/03/1Proximal_Method/\n",
    "\n",
    "### 参考\n",
    "\n",
    "* [梯度下降优化算法综述](https://blog.csdn.net/google19890102/article/details/69942970)\n",
    "* [一文通透优化算法：从随机梯度、随机梯度下降法到牛顿法、共轭梯度](https://blog.csdn.net/v_JULY_v/article/details/81350035)\n",
    "* [关于梯度下降法、牛顿法、高斯-牛顿、LM方法的总结](https://blog.csdn.net/wuaini_1314/article/details/79562400)\n",
    "* [高斯牛顿(Gauss Newton)、列文伯格-马夸尔特(Levenberg-Marquardt)最优化算法与VSLAM](https://blog.csdn.net/zhubaohua_bupt/article/details/74973347)\n",
    "* [常见的几种最优化方法（梯度下降法、牛顿法、拟牛顿法、共轭梯度法等）](https://www.cnblogs.com/shixiangwan/p/7532830.html)\n",
    "* [Gauss-Newton algorithm for nonlinear models](http://fourier.eng.hmc.edu/e176/lectures/NM/node36.html)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}