线性回归算法

作者按：简书的文艺气息还是比较浓的。我们来捣捣乱，搞一篇全部数学公式的文章，用实际行动推动简书加入 MathJax 支持。不过这种文章这年头估计没人会看了吧......如果万一有人感兴趣，可以移步这里得到完整的阅读体验。

本文总结了线性回归算法里用到的一些微积分知识，接着根据最小均方差推导出梯度下降算法以及优化后的随机梯度下降算法。

微积分基本运算法则

• 法则一：对 $y(x)=cx^n$ ，其针对 x 的偏导数为 $\frac{\partial}{\partial x}f(x)=cnx^{n-1}$
• 法则二：常数的微分为 0
• 法则三：偏导数可以穿透累加器，即 $$\frac{\partial}{\partial x_0}\sum_{i=0}^nF(x_i) = \sum_{i=0}^n\frac{\partial}{\partial x_0}F(x_i)$$
• 法则四：微分链接法则，比如 $f(x)$ 是以 x 为自变量的函数，令 $J(x)=g(f(x))$ ，则 $J(x)$ 的微分方程为 $$\frac{\partial}{\partial x}J(x) = g'(f(x))\times f'(x)$$
• 法则五：计算偏导数时，把求导变量当作变量，其他的变量当作常数，比如对方程 $f(x, y) = ax^n + by^m$，则 $$\frac{\partial}{\partial x}f(x, y) = na x^{n-1}$$ 因为是对 x 求导，所以可以把 y 当成常数，即 $by^m$ 整个算子就是一个常数，根据第二个法则，常数的导数为 0。同理，$$\frac{\partial}{\partial y}f(x, y) = mby^{m-1}$$

维基百科上有教程可以参考，比如 Chain Rule 和 Partial Derivatives。

梯度下降算法

假设我们训练数据集 (training data set) 有 m 个数据 $(x_0, y_0), (x_1, y_1), ... (x_m, y_m)$ ，我们用线性方程 $h(x) = \theta_0 + \theta_1 x$ 来拟合这组数据，怎么样来选取参数 $\theta_0$ 和 $\theta_1$ 来最优拟合这组数据呢？

我们可以把这 m 个点画在二维坐标系里，然后计算这 m 个点到我们的线性方程所描述的直线的最短距离，当这些点到我们的拟合直线的距离总和最小时，那么我们就找到了最优的拟合方案了。所以，问题转化为求下面函数的最小值：

$$
J(\theta) = J(\theta_0, \theta_1) = \frac12\sum_{i=0}^m(h(x{(i)}) - y^{(i)})2
$$

上面的公式叫成本函数 (Cost Function)，其中 $h(x_i)$ 是我们的拟合函数针对 $x_i$ 这个点预测出来的值。乘以 $\frac12$ 是为了计算方便，后文我们会看到。

上面我们只考虑了一个变量 $x$ ，即决定这组数据 $y$ 值的只有一个变量。考虑更一般的情况，有 n 个变量 $x_1, x_2, x_3, ... x_n$ 决定 $y$ 的值，那么我们的预测函数模型可以改写如下：

$$
h(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + ... + \theta_n x_n
$$

我们让 $x_0$ 为常数 1，用累加器运算符重写上面的预测函数

$$
h(x) = \sum_{j=0}^n \theta_j x_j
$$

$\theta_0, \theta_1, ... \theta_n$ 我们统称为 $\theta$，是我们的预测函数的 n 个参数 (parameters)。即一组 $\theta$ 值就决定了一个预测函数，我们记作 $h_\theta(x)$，为了简便起见，在不引起误解的情况下我们也把它简写为 $h(x)$。理论上，预测函数有无穷多个，我们求解的目标就是找出一个最优的 $\theta$ 值。

!!! Hint "考考你"
当有 n 个变量 $x_1, x_2, ... x_n$ 决定 y 的值的时候，训练数据集应该长什么样呢？

为了计算 $J(\theta)$ 的最小值，我们选取一组初始的 $\theta$ ，然后逐步调整 $\theta$ 的值，以便让 $J(\theta)$ 逐渐变小，最后我们希望能让 $J(\theta)$ 收敛在一个极值附近，这样我们就找到了最优或局部最优的解。$\theta$ 的迭代公式为：

$$
\theta_j = \theta_j - \alpha \frac\partial{\partial{\theta_j}}J(\theta)
$$

其中，$\alpha$ 是叫学习率 (learning rate)，表示我们一次要让 $\theta_j$ 往前迈多大步子。如果步子太小，意味着要计算很多次才能到达目的地，如果步子太大，可以会直接跨过目的地，从而无法收敛。$\frac\partial{\partial{\theta_j}}J(\theta)$ 就是成本函数的偏导数 (partial derivatives)。

!!! Hint "偏导数的物理意义"
在这个公式里，可以简单地把偏导数理解为斜率。我们要让 $\theta_j$ 不停地迭代，则根据当前 $\theta_j$ 的值，我们算出 $J(\theta)$ 在 $\theta_j$ 上的斜率，然后再乘以我们的学习率 $\alpha$ 就让我们的 $\theta_j$ 往前迈了一小步。

现在问题转化为求 $J(\theta)$ 的偏导数，这个推导过程会用到文章开头部分介绍的几个微积分运算基本法则。

根据成本函数的定义

$$
\frac\partial{\partial{\theta_j}}J(\theta) = \frac\partial{\partial{\theta_j}} \frac12\sum_{i=0}^m(h(x{(i)}) - y^{(i)})2
$$

根据上文的法则三

$$
\frac\partial{\partial{\theta_j}}J(\theta) = \frac12\sum_{i=0}^m \frac\partial{\partial{\theta_j}} (h(x^{(i)}) - y^{(i)})2
$$

根据上文的法则四，这里也可以看到之前除以 2 的目的是为了抵消计算偏导数时乘以 2。

$$
\frac\partial{\partial{\theta_j}}J(\theta) = 2 \frac12 \sum_{i=0}^m \left((h(x^{(i)}) - y^{(i)}) \frac\partial{\partial{\theta_j}} \left(h(x^{(i)}) - y^{(i)}\right)\right)
$$

$$
\frac\partial{\partial{\theta_j}}J(\theta) = \sum_{i=0}^m \left(\left(h(x^{(i)}) - y^{(i)}\right) \frac\partial{\partial{\theta_j}} \left(\sum_{j=0}^n \theta_j x_j^{(i)} - y^{(i)}\right)\right)
$$

根据法则五

$$
\frac\partial{\partial{\theta_j}}J(\theta) = \sum_{i=0}^m \left(\left(h(x^{(i)}) - y^{(i)}\right) x_j^{(i)}\right)
$$

最后得出我们的参数迭代函数

$$
\theta_j = \theta_j - \alpha \sum_{i=0}^m \left(\left(h(x^{(i)}) - y^{(i)}\right) x_j^{(i)}\right)
$$

这个就是 LSM (Least Mean Squares) 迭代算法，也叫 Widrow-Hoff 学习算法。

解析一下这个公式几个关键部分的含义

• $h(x^{(i)})$: 这个是按照我们的给定的参数的预测值，只要 $\theta$ 确定了，我们就可以根据预测函数算出这个值
• $y^{(i)}$: 这个是训练数据集 (training data set) 的目标值
• $x_j^{(i)}$: 这个是训练数据集里第 j 个变量的值
• $\sum_{i=0}^m$: 这个是对所有训练数据集求和。从这个也可以看到每迭代一次就要遍历一次全部训练数据集。所以这个算法也称为**批量梯度下降算法 (Batch Gradient Descent) **。对训练数据集比较大的场景下，计算成本是很高的。后面我们会介绍另外一个提高运算效率的算法。

这个公式有些符合直觉的地方，比如 $\left(h(x^{(i)}) - y^{(i)}\right)$ 表示的是预测值与真实值的误差，当误差比较大时，经过一轮的迭代，$\theta_j$ 的步幅就迈得比较大。即当我们的参数 $\theta$ 离我们的目标值很远的时候，迭代一次的值变化比较大，可以快速地收敛，而当 $\theta$ 离目标值比较近的时候，迭代一次的值变化比较小，即慢慢地收敛到目标值。

这个公式怎么样用编程语言来实现呢？在编写机器学习算法的时候，一般步骤如下：

• **确定学习率 $\alpha$ **
  $\alpha$ 太大可能会使成本函数无法收敛，太小计算太多，机器学习算法效率就比较低。
• 确定参数起始点
  比如让所有的参数都为 1 作为起点，即 $\theta_0 := 1, \theta_1 := 1, ... \theta_n := 1$。这样就得到了我们的预测函数：$h_\theta(x) = \sum_{i=0}^m x^{(i)}$。根据预测值和我们的成本函数，就可以算出我们在参数起始位置的成本。需要注意的是，参数起始点可以根据实际情况灵活选择，以便让机器学习算法的性能更高，比如选择比较靠近极点的位置。
• 计算参数的下一组值
  根据 LSM 算法，分别同时算出新的 $\theta_j$ 的值。然后用新的 $\theta$ 值得到新的预测函数 $h_\theta(x)$，再根据新的预测函数，代入成本函数就可以算出新的成本。
• 确认成本函数是否收敛
  拿新的成本和旧的成本进行比较，看成本是不是变得越来越小。如果两次成本之间的差异小于误差范围，即说明我们已经非常靠近最小成本附近了。就可以近似地认为我们找到了最小成本了。如果两次成本之间的差异在误差范围之外，重复步骤 3 继续计算下一组参数 $\theta$。直到找到我们的最优解。

随机梯度下降算法

批量梯度下降算法对参数进行一次迭代运算，就需要遍历所有的训练数据集。当训练数据集比较大时，这个算法的效率会很低。考虑另外一个算法：

$$
\theta_j = \theta_j - \alpha \left(\left(h(x^{(i)}) - y^{(i)}\right) x_j^{(i)}\right)
$$

这就是 随机梯度下降算法 (stochastic gradient descent)。这个算法的关键点是不去遍历所有的训练数据集，而是改成每次随机地从训练数据集里取一个数据进行参数迭代计算。

!!! Hint "怎么理解随机"
为什么这么神奇呢？为什么随机从训练数据集里选取一个数据来迭代，不但不影响最终计算结果，还大大地提高了效率。看数学时最怕的就是 我们考虑 bla bla bla，作者说出 “我们考虑 bla bla bla” 时背后的过程是怎么样的？坦白讲，怎么样从数学上证明随机梯度下降算法和批量梯度下降算法是等价的，我也不知道。不过我有个直观的可以帮助理解的解释。回到成本函数的定义：$J(\theta) = \frac12 \sum_{i=0}^m \left(h(x^{(i)}) - y^{(i)}\right)2$。我们说过，这里累加后除以 2 是为了计算方便，那么我们除以 m 是什么意思呢？答案是平均值，即所有训练数据集上的点到我们预测函数的距离的平均值。因为 m 是正整数，$J(\theta)$ 除以 m 不影响它的最小值的属性。再回到随机选取训练数据集里的一个数据这个做法来看，如果计算次数足够多，并且是真正随机，那么随机选取出来的这组数据从概率的角度来看，和平均值是相当的。打个比方，有一个储钱罐里有 1 角的硬币 10 枚，5 角的硬币 2 枚，1 元的硬币 1 枚，总计 3 元，13 枚硬币。你随机从里面取 1000 次，每次取出来的硬币把币值记录下来，然后放回储钱罐里。这样最后去算这 1000 次取出来的钱的平均值 (1000 次取出来的币值总和除以 1000) 和储钱罐里每枚硬币的平均值 (3/13 元) 应该是近似相等的。我数学太水，概率论还没复习，哪位概率论高人给证明一下啊。

这样，我们基本上把梯度下降算法，最小均方差，随机梯度下降算法的来龙去脉理了一遍。