【牛人博客之】最小二乘法

最小二乘法是用来做函数拟合或者求函数极值的方法。在机器学习，尤其是回归模型中，经常可以看到最小二乘法的身影。

最小二乘法的原理与要解决的问题^{刘建平博客}

最小二乘法形式如下式：

$$目标函数 = \sum(观测值-理论值)^2$$

观测值就是我们的样本，理论值就是我们的假设拟合函数（假设的模型输出）。目标函数也就是在机器学习中常说的损失函数，我们的目标是得到能够使目标函数最小化时候的拟合函数的模型。举一个最简单的线性回归的简单例子，比如我们有m个只有一个特征的样本：

$$T=\left \{(x_1, y_1),(x_2, y_2),...,(x_m, y_m)\right \}$$

样本采用下面的拟合函数：

$$h_{\theta} (x)= \theta_0+ \theta_1x$$

这样我们的样本有一个特征$x$，对应的拟合函数有两个参数$\theta_0$和$\theta_1$需要求出。
我们的目标函数为：

$$J(\theta_0, \theta_1)=\sum_{i=1}^{m} (y_i - h_{\theta}(x_i))^2 = \sum_{i=1}^{m}(y_i-\theta_0-\theta_1x_i)^2$$

以上就是要解决的问题了，用最小二乘法做什么呢？使$J(\theta_0, \theta_1)$最小，求出使$J(\theta_0, \theta_1)$最小时的$\theta_0$和$\theta_1$，这样拟合函数就得出了。
那么，最小二乘法怎么才能使$J(\theta_0, \theta_1)$最小呢？

$x_i$表示多个输入变量中的第$i$个，即有$n$维特征的第$i$个输入变量$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$
$y_i$ 表示多个观察样本中的第$i$个

最小二乘法的解法

代数解法

为了使$J(\theta_0, \theta_1)$最小，方法就是对$\theta_0$和$\theta_1$分别来求偏导数，令偏导数为0，得到一个关于$\theta_0$和$\theta_1$的二元方程组。求解这个二元方程组，就可以得到$\theta_0$和$\theta_1$的值。下面我们具体看看过程。
$J(\theta_0, \theta_1)$对$\theta_0$求导，得到如下方程：

$$\frac{\partial J(\theta_0, \theta_1)}{\partial \theta_0}=-2 \sum_{i=1}^{m}(y_i - \theta_0 - \theta_1 x_i)$$

令偏导数为0，得到如下方程：

$$\sum_{i=1}^{m}(y_i - \theta_0 - \theta_1 x_i)=0 \tag{1.1}$$

$J(\theta_0, \theta_1)$对$\theta_1$求导，得到如下方程：

$$\frac{\partial J(\theta_0, \theta_1)}{\partial \theta_1}=-2 \sum_{i=1}^{m}(y_i - \theta_0 - \theta_1 x_i)x_i$$

令该偏导数为0，则有：

$$\sum_{i=1}^{m}(y_i - \theta_0 - \theta_1 x_i)x_i=0 \tag{1.2}$$

公式(1.1)和(1.2)组成一个二元一次方程组，容易求出$\theta_1$的值：

$$\theta_1=\frac{m \sum (x_iy_i) - \sum x_i \sum y_i}{m \sum x_i^2 - (\sum x_i)^2} \tag{1.3}$$

将(1.3)代入(1.1)得到$\theta_0$的值：

$$\theta_0=\frac{\sum x_i^2 \sum y_i - \sum x_i \sum x_iy_i}{m \sum x_i^2 - (\sum x_i)^2} \tag{1.4}$$

这个方法很容易推广到多个样本特征的线性拟合。
拟合函数表示为$h_\theta(x^{(1)},x^{(2)},…x^{(n)})=\theta_0 + \theta_1 x^{(1)}+…+\theta_n x^{(n)}$，其中$\theta_i(i=0, 1,2,…n)$为模型参数，$x^{(i)}(i=0, 1,2,…n)$为每个样本在第$i$个特征属性上的取值。这个表示可以简化，我们增加一个特征$x_0=1$，这样拟合函数表示为：

$$h_\theta(x^{(1)},x^{(2)},...x^{(n)})=\sum_{i=0}^{n}\theta_i x_i$$

损失函数表示为：

$$J(\theta_0,\theta_1,...,\theta_n) = \sum_{j=1}^{m}(y_j - h_\theta(x_j^{(1)},x_j^{(2)},...x_j^{(n)}))^2 = \sum_{j=1}^{m} (y_j - \sum_{i=0}^{n} \theta_i x_j^i)^2$$

利用损失函数分别对$\theta_i(i=0, 1,2,…n)$求导，并令导数为0可得：

$$\sum_{j=0}^{m} (y_j - \sum_{i=0}^{n} \theta_ix_j^{(i)})x_j^{(i)} = 0$$

这样我们得到一个$n+1$元一次方程组，这个方程组有$n+1$个方程，求解这个方程，就可以得到所有的$n+1$个未知的$\theta$。
这个方法很容易推广到多个样本特征的非线性拟合。原理和上面的一样，都是用损失函数对各个参数求导取0，然后求解方程组得到参数值。

矩阵法解法

矩阵法比袋鼠要简介，且矩阵运算可以取代循环，所以现在很多书和机器学习库都是用的矩阵法来做最小二乘法。
这里用上面的多元线性回归例子来描述矩阵法解法。
假设函数$h_\theta(x^{(1)},x^{(2)},…x^{(n)})=\theta_0 + \theta_1 x^{(1)}+…+\theta_n x^{(n)}$的矩阵表达方式为：

$$h_\theta(X)= X\theta$$

其中，假设函数$h_\theta(X)$为$m\times 1$的向量， $\theta$为$n \times 1$的向量，里面有$n$个代数法的模型参数。$X$为$m \times n$维的矩阵。$m$代表样本个数，$n$代表样本的特征数。
损失函数定义为$J(\theta)=\frac{1}{2} (X \theta -Y)^T(X\theta-Y)$
其中$Y$是样本的输出向量，维度为$m \times 1$，$\frac{1}{2}$在这里是为了求导后系数为1，方便计算。
根据最小二乘法的原理，我们要对这个损失函数对$\theta$向量求导取0。结果如下式：

$$\frac{\partial}{\partial \theta}J(\theta)=X^T(X\theta-Y)=0$$

这里面用到了矩阵求导链式法则，和两个矩阵求导的公式：

$$\frac{\partial}{\partial X} (XX^T)=2X \tag{2.1}$$ $$\frac{\partial}{\partial \theta} (X\theta)=X^T \tag{2.2}$$

对上述求导等式整理后可得：

$$X^TX\theta = X^TY$$

两边同时左乘$(X^TX)^{-1}$可得：

$$\theta = (X^TX)^{-1}X^TY$$

这样只要给了数据,我们就可以用$\theta = (X^TX)^{-1}X^TY$算出$\theta$

最小二乘法的局限性和使用场景

从上面可以看出，最小二乘法适用简洁高效，比梯度下降这样的迭代法似乎方便很多。但是这里我们就聊聊最小二乘法的局限性。

1. 最小二乘法需要计算$X^TX$的逆矩阵，有可能它的逆矩阵不存在，这样就没有办法直接用最小二乘法了，此时梯度下降法仍然可以使用。当然，我们可以通过对样本数据进行整理，去掉冗余特征。让$X^TX$的行列式不为0，然后继续使用最小二乘法。
2. 当样本特征$n$非常的大的时候，计算$X^TX$的逆矩阵是一个非常耗时的工作（$nxn$的矩阵求逆），甚至不可行。此时以梯度下降为代表的迭代法仍然可以使用。那这个$n$到底多大就不适合最小二乘法呢？如果你没有很多的分布式大数据计算资源，建议超过10000个特征就用迭代法吧。或者通过主成分分析降低特征的维度后再用最小二乘法。
3. 如果拟合函数不是线性的，这时无法使用最小二乘法（为什么呢？），需要通过一些技巧转化为线性才能使用，此时梯度下降仍然可以用。
4. 讲一些特殊情况。当样本量$m$很少，小于特征数$n$的时候，这时拟合方程是欠定的，常用的优化方法都无法去拟合数据。当样本量$m$等于特征数$n$的时候，用方程组求解就可以了。当$m$大于$n$时，拟合方程是超定的，也就是我们常用与最小二乘法的场景了。

^{刘建平博客}. 最小二乘法小结 ↩