###线性回归之最小二乘法
1.最小二乘法的原理
最小二乘法的重要思想是通过确定未知参数$\theta$（通常是一个参数矩阵），来使得真实值和猜测值的弊端（也称残差）平方和最小，其盘算公式为$E=\sum_{i=0}ne_i2=\sum_{i=1}^n(y_i-\hat)$，此中$y_i$是真实值，$\hat$是对应的猜测值。如下图所示（泉源于维基百科，Krishnavedala的作品），就是最小二乘法的一个示例，此中赤色为数据点，蓝色为最小二乘法求得的最佳解，绿色即为弊端。
图1图中有四个数据点分别为：(1, 6), (2, 5), (3, 7), (4, 10)。在线性回归中，通常我们利用均方弊端来作为丧失函数，均方弊端可以看作是最小二乘法中的E除以m（m为样本个数），以是最小二乘法求出来的最优解就是将均方弊端作为丧失函数求出来的最优解。对于图中这些一维特性的样本，我们的拟合函数为$h_\theta(x)=\theta_0+\theta_1x$，以是丧失函数为 \(J(\theta_0,\theta_1)=\sum_{i=0}^m(y^{(i)}-h_\theta(x^{(i)}))^2=\sum_{i=0}^m(y^{(i)}-\theta_0-\theta_1x^{(i)})^2\)（这里丧失函数利用最小二乘法，并非均方弊端），此中上标(i)表示第i个样本。
2.最小二乘法求解
要使丧失函数最小，可以将丧失函数当作多元函数来处置处罚，采用多元函数求偏导的方法来盘算函数的极小值。比方对于一维特性的最小二乘法，$J(\theta_0,\theta_1)\(分别对\)\theta_0$，$\theta_1$求偏导，令偏导即是0得：
\(\frac{\partial J(\theta_0,\theta_1)}{\partial\theta_0}=-2\sum_{i=1}^{m}(y^{(i)}-\theta_0-\theta_1x^{(i)}) = 0\tag{2.1}\)
\(\frac{\partial J(\theta_0,\theta_1)}{\partial\theta_1}=-2\sum_{i=1}^{m}(y^{(i)}-\theta_0-\theta_1x^{(i)})x^{(i)} = 0\tag{2.2}\)
联立两式，求解可得：
\(\theta_0 =\frac{\sum_{i=1}^m(x^{(i)})^2\sum_{i=1}^my^{(i)}-\sum_{i=1}^mx^{(i)}\sum_{i=1}^mx^{(i)}y^{(i)}}{m\sum_{i=1}^m(x^{(i)})^2-\sum_{i=1}^mx^{(i)}(\sum_{i=1}^mx^{(i)})^2} \tag{2.3}\)
\(\theta_1 =\frac{m\sum_{i=1}^mx^{(i)}y^{(i)}-\sum_{i=1}^mx^{(i)}\sum_{i=1}^my^{(i)}}{m\sum_{i=1}^m(x^{(i)})^2-\sum_{i=1}^mx^{(i)}(\sum_{i=1}^mx^{(i)})^2} \tag{2.4}\)
对于图1中的例子，代入公式$(2.3)\(和\)(2.4)\(举行结算得，\)\theta_0 = 3.5, \theta_1=1.4,J(\theta) = 4.2$。
对于n维特性的样本，同样可以采用这种方式来求解。对于特性维度$(x_1,x_2, \cdots,x_n)$，我们增长一个第0维$x_0=1$，如许增广特性向量$x = (x_0,x_1,\cdots,x_n)\(，增广权向量为\)\theta = (\theta_0, \theta_1,\dots,\theta_n)$.
此时我们的拟合函数变为：
\(h_\theta(x) = \sum_{i=0}^n\theta_ix_i =\theta_0+ \theta_1x_1 + \cdots+\theta_nx_n\)
丧失函数变为：
\(J(\theta)=\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})^2=\sum_{j=1}^m(\sum_{i=0}^n\theta_ix_i^{(j)}-y^{(j)})^2\)
丧失函数$J(\theta)\(分别对\)\theta_i(i=0,1,\dots,n)$求偏导，得：
$$\frac{\partial J(\theta)}{\partial\theta_i} = 2\sum_{j=1}m(h_\theta(x{(j)})-y^{(j)})x^{(j)}=2\sum_{j=1}m(\sum_{i=0}n\theta_ix_i{(j)}-y{(j)})x^{(j)}\quad (i=0,1,\dots,n) $$
令偏导即是0，则有：
$$\sum{j=1}m(\sum{i=0}n\theta_ix_i{(j)}-y{(j)})x^{(j)}=0\quad (i=0,1,\dots,n) $$
如许终极得到的结果就是一个线性方程组，未知数的个数为n+1，方程的个数也为n+1，如许就可以通过高斯消元法解出$\theta_i(i=0,1,\dots,n)$，具体可拜见：详解最小二乘法原理和代码。
对于线性回归标题，我们可以依据拟合函数的情势举行特性空间变更，即广义线性回归。比方，\(h_\theta(x)=\theta_0+\theta_1x_1+\theta_2x_2^2\)，我们可以令$x_2:=x_2^2$，这里$:=$表示赋值，即将右边的值赋给左边。如许又酿成了我们所熟悉的拟合函数情势。
对于非线性回归标题，最小二乘法的思想同样适用，只不外函数情势有所厘革。比方，对于拟合函数$h_\theta(x)=\theta_0+\theta_1x+\theta_2l nx$，此时$J(\theta)=\sum_{j=1}m(h_\theta(x{(j)})-y^{(j)})^2$，求偏导的结果为：
\(\frac{\partial J(\theta)}{\partial\theta_i}=2\sum_{j=1}^{m}(h_\theta(x^{(j)})-y^{(j)})\frac{\partial h_\theta(x)}{\theta_i}\quad (i=0,1,2);此中\frac{\partial h_\theta(x)}{\theta_0} = 1, \frac{\partial h_\theta(x)}{\theta_2} = x, \frac{\partial h_\theta(x)}{\theta_2} = lnx\)
同样可以构造线性方程组，用高斯消元法求解。
3.矩阵求解最小二乘法
对于函数$_(x)=_0+_1_1+\dots+__$，我们将其用矩阵表示为：
\(X\theta = Y \qquad \tag{3.1}\)
此中，
\(X = \left\{\begin{matrix} (x^{(1)})^T \\ (x^{(2)})^T \\ \vdots \\(x^{(m)})^T \end{matrix} \right\} , Y = \left\{\begin{matrix} y^{(1)} \\ y^{(2)} \\ \vdots \\y^{(m)}) \end{matrix} \right\},x^{(j)}=\left\{\begin{matrix} x_0^{(j)}) \\ x_1^{(j)} \\ \vdots \\ x_n^{(j)} \end{matrix} \right\}, \theta = \left\{\begin{matrix} \theta_0 \\ \theta_1 \\ \vdots \\ \theta_n \end{matrix} \right\}\)
m表示样本个数，n为特性维度，\(x_0^{(i)}=1\quad(i = 0,1,\dots,m)\)，即$X$的第一列全为1，$x_i^{(j)}$表示第j个样本的第i个特性，$X$为增广样本矩阵((1+n)*m维)，$Y$为真实值构成的列向量。
丧失函数表示为：
\(J(\theta)=\sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)})^2=(X\thetaY)^T(X\thetaY) \tag{3.2}\)
根据最小二乘法，利用矩阵求导得：（具体推导拜见线性回归矩阵推导和线性回归干系向量求导）
\(\frac{\partial J(\theta)}{\partial\theta}=2X^T(X\theta-Y)\)
令求导结果即是0矩阵，可得：
\(X^TX\theta = X^TY\quad\Rightarrow \quad \theta = (X^TX)^{-1}X^TY \tag{3.3}\)
对于图1中的例子，利用公式$(3.3)\(盘算得：\)\theta = \left{\begin 3.5 \1.4\end \right}$
4.总结
最小二乘法可以直接求解参数矩阵，在盘算时可以直接套入公式。但是仍有一定的范围性，重要体现在：
1.$X^TX$的逆矩阵大概不存在，这个在Matlab中，可以通过求伪逆来举行盘算。
2.对于$(3.1)$式，可以将其当作一个线性方程组（假设各方程线性无关）。如果样本个数m小于特性维数n，那么此方程组有无穷多个解。如果m = n，有唯一解。如果m大于n，无解（即存在抵牾解）。最小二乘法一般是在m大于n的时间利用，此时求出来的解是最优近似解。
3.最小二乘法的时间复杂度为$O(n^3)$，当n特别大的时间（一般大于10000），求逆矩阵的过程非常复杂。此时采用最小二乘法，会非常耗时。
参考链接：
最小二乘法小结
半小时学习最小二乘法 |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
