线性回归/10. 什么是梯度下降.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们前面在求解线性回归时，都是通过下面的这个被叫做**正规方程**的式子来计算线性回归的：\n",
    "\n",
    "$$\n",
    "\\bf{a} = (\\rm{X}^T\\rm{X})^{-1}\\rm{X}^T\\bf{y}\n",
    "$$\n",
    "\n",
    "使用这种方法虽然简单，容易理解，但在现实生活中却有着很大的局限性。首先，并非所有的函数都可以通过求导来计算它的极值点，有些函数的导数根本不存在解析解；其次，在正规方程的计算过程中使用的矩阵 $\\rm{X}^T\\rm{X}$ 必须是可逆的，且不说有些矩阵是不可逆的，还有些矩阵的求逆非常困难，比如 **希尔伯特矩阵**；另外，当数据量或维度不断增加时，矩阵计算的开销也会越来越大，要知道，矩阵求逆的时间复杂度是矩阵维度的三次方，因此当数据量过大时，使用正规方程会非常耗时，数据量如果只有成百上千，可能影响并不大，一旦数据量达到万级以上，使用正规方程的性能问题就会凸显出来。\n",
    "\n",
    "我们以一元线性回归为例，在前面的最小二乘法求解过程中我们知道，求解一元线性回归可以转化为求解损失函数的最小值，损失函数是一个关于参数 a, b 的二元二次函数：\n",
    "\n",
    "$$\n",
    "loss = n\\bar{y^2} + a^2n\\bar{x^2} + nb^2 + 2abn\\bar{x} - 2an\\bar{xy} - 2bn\\bar{y}\n",
    "$$\n",
    "\n",
    "它是三维空间里的一个曲面，图像类似于下面左图这样：\n",
    "\n",
    "![](../images/loss-2.jpg)\n",
    "\n",
    "右图代表的是损失函数的**等高图**，每一条线表示损失函数的值相等，红色的叉号表示损失函数的最小值。要求这个最小值，除了前面介绍的正规方程法，这一节我们将学习一种新的方法，**梯度下降**（Gradient Descent），它比正规方程更具有广泛性，可以用于很多复杂算法的求解。\n",
    "\n",
    "梯度下降算法的基本思路是，在坡上任意取一点，然后沿着下坡方向走最后到达最低点，为了走的最快，我们每次都沿着最陡的方向下坡，这样不断的迭代，直到损失函数收敛到最小值。\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 什么是梯度？\n",
    "\n",
    "为了更好的理解梯度下降，我们来看看什么是**梯度**（gradient），而要知道什么是梯度，还得从函数的**导数**（derivative）说起。\n",
    "\n",
    "导数的公式如下所示：\n",
    "\n",
    "$$\n",
    "f'(x) = \\lim\\limits_{\\Delta x \\to 0}\\frac{\\Delta y}{\\Delta x}\n",
    "      = \\lim\\limits_{\\Delta x \\to 0}\\frac{f(x_0 + \\Delta x) - f(x_0)}{\\Delta x}\n",
    "$$\n",
    "\n",
    "它可以表示函数在某点的切线斜率，也就是函数在该点附近的变化率，如果导数大于零，那么函数在区间内单调递增，如果导数小于零，函数在区间内则是单调递减。\n",
    "\n",
    "![](../images/gradient-1.jpg)\n",
    "\n",
    "上面是一个一元函数的导数示例，当扩展到二元或更多元的情况时，就出现了 **偏导数**（partial derivative）和 **方向导数**（directional derivative），偏导数是多元函数沿坐标轴的变化率，而方向导数则是多元函数沿任意方向的变化率。\n",
    "\n",
    "从上面的导数定义可以看出，导数是一个数，包括偏导数和方向导数也是一个数，代表的是函数沿某个方向的变化率。梯度并不是一个数，而是一个向量，它代表的是在各个导数中，变化趋势最大的那个方向。梯度的数学定义为：\n",
    "\n",
    "> 设函数 $z = f(x, y)$ 在平面区域 $D$ 内具有一阶连续偏导数，则对于每一点 $(x_0, y_0)$ 属于 $D$，都可定义一个向量：\n",
    ">\n",
    "> $$ \\frac{\\partial{f(x_0, y_0)}}{\\partial x}i + \\frac{\\partial{f(x_0, y_0)}}{\\partial y}j $$\n",
    ">\n",
    "> 这个向量被称为函数 $z = f(x, y)$ 在点 $(x_0, y_0)$ 处的梯度，记作 $grad f(x_0, y_0)$，即：\n",
    ">\n",
    ">$$\n",
    "\\begin{align}\n",
    "grad f(x_0, y_0) &= \\frac{\\partial{f(x_0, y_0)}}{\\partial x}i + \\frac{\\partial{f(x_0, y_0)}}{\\partial y}j \\\\\n",
    "                 &= f_x(x_0, y_0)i + f_y(x_0, y_0)j\n",
    "\\end{align}\n",
    "$$\n",
    ">\n",
    "> 有时候，梯度也可以用 $\\nabla$ 来表示：\n",
    "> $$ grad f(x_0, y_0) = \\nabla f(x_0, y_0) $$\n",
    ">\n",
    ">其中，$\\frac{\\partial}{\\partial x}i + \\frac{\\partial}{\\partial y}j$ 被称为 **向量微分算子**或 **Nabla 算子**。\n",
    "\n",
    "可以看到梯度就是对各个坐标轴分别求偏导，得到的一个向量，下面是一个例子，假设 $J(\\theta)$ 是一个三元一次函数：\n",
    "\n",
    "$$\n",
    "J(\\theta) = 5\\theta_1 + 2\\theta_2 - 12\\theta_3\n",
    "$$\n",
    "\n",
    "该函数的梯度为：\n",
    "\n",
    "$$\n",
    "\\nabla J(\\theta) = \\langle \\frac{\\partial J}{\\partial \\theta_1}, \\frac{\\partial J}{\\partial \\theta_2}, \\frac{\\partial J}{\\partial \\theta_3} \\rangle \\\\\n",
    "= \\langle 5, 2, -12 \\rangle\n",
    "$$\n",
    "\n",
    "那么为什么说梯度是变化趋势最大的方向呢？可以参考[这里](https://zhuanlan.zhihu.com/p/24913912)。总之，沿着梯度方向，函数会以最快的速度到达极大值，而沿着负梯度方向，函数会以最快的速度到达极小值。如果这个函数是一个**凸函数**，那么极值点就是最值点。假设上面的 $f(x,y)$ 就是我们的损失函数，且它是一个凸函数，那么我们就可以通过沿着负梯度方向，不断迭代，最终收敛在最小值。\n",
    "\n",
    "![](../images/gradient-direction.jpg)\n",
    "\n",
    "不过，如果损失函数是一个**非凸函数**，则可能会存在多个极值点，使用梯度下降法收敛的结果可能只是一个局部最小值，而不是全局最小值，譬如下图中的两种情况，可以看出，选择的初始点不同，计算出的极值点也不尽相同。\n",
    "\n",
    "![](../images/gradient-direction-2.jpg)\n",
    "\n",
    "这是梯度下降法的一个最主要的缺点，对初始点的选择极为敏感，不可避免的会存在陷入局部极小值的情形，梯度下降另一个缺点是，当到达最小点附近的时候收敛速度会变的很慢，所以针对这两个缺点，后来又提出了很多改进算法，比如 **拟牛顿法**，**共轭梯度法** 等。"
   ]
  }
 ],
 "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
}