Linear Regression
最小二乘法
最小二乘法（又称最小平方法）是一种数学优化技术。它通过最小化误差的平方和寻找数据的最佳函数匹配。利用最小二乘法可以简便地求得未知的数据，并使得这些求得的数据与实际数据之间误差的平方和为最小。最小二乘法还可用于曲线拟合。其他一些优化问题也可通过最小化能量或最大化熵用最小二乘法来表达。
通过这段描述可以看出来，最小二乘法也是一种优化方法，求得目标函数的最优值。并且也可以用于曲线拟合，来解决回归问题。难怪《统计学习方法》中提到，回归学习最常用的损失函数是平方损失函数，在此情况下，回归问题可以著名的最小二乘法来解决。最小二乘法是机器学习领域有名和有效的算法之一。
一元线性模型
我们先以最简单的一元线性模型来解释最小二乘法。什么是一元线性模型呢？ 监督学习中，如果预测的变量是离散的，我们称其为分类（如决策树，支持向量机等），如果预测的变量是连续的，我们称其为回归。回归分析中，如果只包括一个自变量和一个因变量，且二者的关系可用一条直线近似表示，这种回归分析称为一元线性回归分析。如果回归分析中包括两个或两个以上的自变量，且因变量和自变量之间是线性关系，则称为多元线性回归分析。对于二维空间线性是一条直线；对于三维空间线性是一个平面，对于多维空间线性是一个超平面…
对于一元线性回归模型, 假设从总体中获取了n组观察值( X 1 , Y 1 ) , ( X 2 , Y 2 ) , ⋯   , ( X n , Y n ) (X_1,Y_1),(X_2,Y_2),\cdots,(X_n,Y_n)(X1,Y1),(X2,Y2),⋯,(Xn,Yn)。对于平面中的这n nn个点，可以使用无数条曲线来拟合。要求样本回归函数尽可能好地拟合这组值。综合起来看，这条直线处于样本数据的中心位置最合理。 选择最佳拟合曲线的标准可以确定为：使总的拟合误差（即总残差）达到最小。有以下三个标准可以选择：
- 用“残差和最小”确定直线位置是一个途径。但很快发现计算“残差和”存在相互抵消的问题。
- 用“残差绝对值和最小”确定直线位置也是一个途径。但绝对值的计算比较麻烦。
- 最小二乘法的原则是以“残差平方和最小”确定直线位置。用最小二乘法除了计算比较方便外，得到的估计量还具有优良特性。这种方法对异常值非常敏感。
最常用的是普通最小二乘法（ Ordinary Least Square，OLS）：所选择的回归模型应该使所有观察值的残差平方和达到最小。（Q QQ为残差平方和）- 即采用平方损失函数。
样本回归模型:
Y i = β 0 ^ + β 1 ^ X i + e i Y_i=\hat{\beta_0}+\hat{\beta_1}X_i+e_iYi=β0^+β1^Xi+ei
⇒ e i = Y i − β 0 ^ − β 1 ^ X i \Rightarrow e_i=Y_i-\hat{\beta_0}-\hat{\beta_1}X_i⇒ei=Yi−β0^−β1^Xi
其中e i e_iei为样本(X i X_iXi,Y i Y_iYi)的误差
平方损失函数：
Q = ∑ i = 1 n e i 2 = ∑ i = 1 n ( Y i − Y i ^ ) 2 = ∑ i = 1 n ( Y i − β 0 ^ − β 1 ^ X i ) 2 Q=\sum_{i=1}^{n}e_i^2=\sum_{i=1}^{n}(Y_i-\hat{Y_i})^2=\sum_{i=1}^n(Y_i-\hat{\beta_0}-\hat{\beta_1}X_i)^2Q=i=1∑nei2=i=1∑n(Yi−Yi^)2=i=1∑n(Yi−β0^−β1^Xi)2
通过对Q QQ求极值来确定参数β 0 ^ , β 1 ^ \hat{\beta_0},\hat{\beta_1}β0^,β1^,对Q QQ求偏导：
{ ∂ Q ∂ β 0 ^ = 2 ∑ i = 1 n ( Y i − β 0 ^ − β 1 ^ X i ) ( − 1 ) = 0 ∂ Q ∂ β 1 ^ = 2 ∑ i = 1 n ( Y i − β 0 ^ − β 1 ^ X i ) ( − X i ) = 0 \left\{\begin{matrix} \frac{\partial Q}{\partial \hat{\beta_0}}=2\sum_{i=1}^{n}(Y_i-\hat{\beta_0}-\hat{\beta_1}X_i)(-1)=0\\ \frac{\partial Q}{\partial \hat{\beta_1}}=2\sum_{i=1}^{n}(Y_i-\hat{\beta_0}-\hat{\beta_1}X_i)(-X_i)=0 \end{matrix}\right.{∂β0^∂Q=2∑i=1n(Yi−β0^−β1^Xi)(−1)=0∂β1^∂Q=2∑i=1n(Yi−β0^−β1^Xi)(−Xi)=0
解得：
β 0 ^ = n ∑ X i Y i − ∑ X i ∑ Y i n ∑ X i 2 − ( ∑ X i ) 2 \hat{\beta_0}=\frac{n\sum X_iY_i- \sum X_i\sum Y_i}{n\sum X_i^2-(\sum X_i)^2}β0^=n∑Xi2−(∑Xi)2n∑XiYi−∑Xi∑Yi
β 1 ^ = ∑ X i 2 ∑ Y i − ∑ X i ∑ X i Y i n ∑ X i 2 − ( ∑ X i ) 2 \hat{\beta_1}=\frac{\sum {X_i}^2\sum Y_i-\sum X_i\sum X_iY_i}{n\sum {X_i}^2-(\sum X_i)^2}β1^=n∑Xi2−(∑Xi)2∑Xi2∑Yi−∑Xi∑XiYi
以上是一元线性回归模型的最小二乘法的推导
多元线性回归模型
与一元线性回归模型的自变量只有一个特征不同，多元线性回归模型的自变量由多个特征。那么我们就引入特征的向量来表示，这里涉及到矩阵的乘法，向量，矩阵求导等一些线性代数的知识。
多元线性回归模型自变量与因变量之间为线性关系可表示为：
h θ ( x i ) = θ 0 + θ 1 x i 1 + θ 2 x i 2 + ⋯ + θ n x i n h_\theta(x_i)=\theta_0+\theta_1x_{i1}+\theta_2x_{i2}+\cdots+\theta_nx_{in}hθ(xi)=θ0+θ1xi1+θ2xi2+⋯+θnxin
令
θ = ( θ 0 θ 1 ⋮ θ n ) , x i = ( 1 x i 1 x i 2 ⋮ x i n ) \theta=\left(\begin{matrix} \theta_0\\ \theta_1\\ \vdots\\\theta_n \end{matrix}\right), x_i=\left(\begin{matrix} 1\\x_{i1}\\x_{i2}\\ \vdots\\x_{in} \end{matrix}\right)θ=⎝⎜⎜⎜⎛θ0θ1⋮θn⎠⎟⎟⎟⎞,xi=⎝⎜⎜⎜⎜⎜⎛1xi1xi2⋮xin⎠⎟⎟⎟⎟⎟⎞
则上边的式子可以写成如下形式：
h θ ( x i ) = θ T x i h_\theta(x_i)=\theta^Tx_ihθ(xi)=θTxi
其中，θ \thetaθ表示模型的参数，x i x_ixi表示数据集中第i ii条数据。令
X = ( x 1 T x 2 T ⋮ x m T ) = ( 1 x 11 x 12 ⋯ x 1 n 1 x 21 x 22 ⋯ x 2 n ⋮ ⋮ ⋮ ⋮ 1 x m 1 x m 2 ⋯ x m n ) X=\left( \begin{matrix} x_{1}^T\\x_{2}^T\\ \vdots \\x_{m}^T \end{matrix} \right)=\left(\begin{matrix} 1 & x_{11} &x_{12} & \cdots &x_{1n} \\ 1 & x_{21} &x_{22} & \cdots &x_{2n} \\ \vdots & \vdots &\vdots & & \vdots \\ 1 & x_{m1} &x_{m2} & \cdots &x_{mn} \end{matrix}\right)X=⎝⎜⎜⎜⎛x1Tx2T⋮xmT⎠⎟⎟⎟⎞=⎝⎜⎜⎜⎛11⋮1x11x21⋮xm1x12x22⋮xm2⋯⋯⋯x1nx2n⋮xmn⎠⎟⎟⎟⎞
y = ( y 1 y 2 ⋮ y m ) y=\left(\begin{matrix} y_1\\ y_2 \\ \vdots \\ y_m \end{matrix}\right)y=⎝⎜⎜⎜⎛y1y2⋮ym⎠⎟⎟⎟⎞
则线性模型的表达式可写为：
h θ ( X ) = X θ h_\theta(X)=X\thetahθ(X)=Xθ
损失函数可以写为：
KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲L&=\sum_{i=1}^m…
二.多特征下求解参数 θ \thetaθ:
KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲L&=(X\theta-y)^…
我们的目标是让损失函数最小，即求（2）的最小值，我们对θ \thetaθ求偏导数，令其等于0 00，就可以求出L取得极小值时参数θ \thetaθ的值。
KaTeX parse error: No such environment: align* at position 7: \begin{̲a̲l̲i̲g̲n̲*̲}̲\frac{\partial …
推导过程中用到的部分公式:
| f ( θ ) f(\theta)f(θ) | ∂ f ∂ θ \frac{\partial f}{\partial \theta}∂θ∂f |
|---|---|
| θ T x \theta^TxθTx | x xx |
| x T θ x^T\thetaxTθ | x xx |
| θ T θ \theta^T\thetaθTθ | 2 θ 2\theta2θ |
| θ T C θ \theta^TC\thetaθTCθ | 2 C θ 2C\theta2Cθ |
梯度下降法
在进行线性回归模型参数估计时，最小二乘法与梯度下降法两种方法本质相同。都是在给定已知数据（自变量和因变量）的前提下对因变量算出一个一般性的估值函数。然后对给定新数据的因变量进行估算。两种方法的目标相同，都是在已知数据的框架内，使得估算值与实际值的总平方差尽量更小。，估算值与实际值的总平方差的公式为：
Δ = ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 \Delta=\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2Δ=i=1∑m(hθ(x(i))−y(i))2
其中h θ h_\thetahθ为估值函数，x ( i ) x^{(i)}x(i)为第i ii组数据的自变量，y ( i ) y^{(i)}y(i) 为第i ii组数据的因变量，θ \thetaθ为系数向量。
不同的是最小二乘法是直接对Δ \DeltaΔ求导找出全局最小，是非迭代法。而梯度下降法是一种迭代法，先给定一个θ \thetaθ ，然后向Δ \DeltaΔ下降最快的方向调整θ \thetaθ ，在若干次迭代之后找到局部最小。梯度下降法的缺点是到最小点的时候收敛速度变慢，并且对初始点的选择极为敏感，实际操作中一般是随机选择初始点。采用最小均方法LMS(Least Mean Square)更新θ \thetaθ。下面是具体推导过程：
我们将线性模型的表达式写为：
h θ ( x ) = θ 0 + θ 1 x 1 + θ 2 x 2 + ⋯ + θ n x n h_\theta(x)=\theta_0+\theta_1x_{1}+\theta_2x_{2}+\cdots+\theta_nx_{n}hθ(x)=θ0+θ1x1+θ2x2+⋯+θnxn
为了方便推导，将损失函数写为如下形式：
J ( θ ) = 1 2 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) 2 J(\theta)=\frac{1}{2m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})^2J(θ)=2m1i=1∑m(hθ(x(i))−y(i))2
x ( i ) x^{(i)}x(i)表示数据集中第i ii个数据的自变量，y ( i ) y^{(i)}y(i)表示数据集中第i ii个数据的因变量，
h θ ( x ( i ) ) h_\theta(x^{(i)})hθ(x(i))表示已知的假设函数,m mm为训练集的数量。
对J ( θ ) J(\theta)J(θ)求偏导：
∂ J ∂ θ j = 1 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) , j = ( 1 , 2 , ⋯   , n ) \frac{\partial J}{\partial \theta_j}=\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_j,j=(1,2,\cdots,n)∂θj∂J=m1i=1∑m(hθ(x(i))−y(i))xj(i),j=(1,2,⋯,n)
更新参数θ \thetaθ:
θ j : = θ j − α ∂ J ∂ θ j = θ j − α 1 m ∑ i = 1 m ( h θ ( x ( i ) ) − y ( i ) ) x j ( i ) \theta_j:=\theta_j-\alpha\frac{\partial J}{\partial \theta_j}=\theta_j-\alpha\frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)})-y^{(i)})x^{(i)}_jθj:=θj−α∂θj∂J=θj−αm1i=1∑m(hθ(x(i))−y(i))xj(i)
由于θ \thetaθ每次更新都用到了数据集中全部的数据，因此这种方式叫做批量梯度下降法。
特征缩放
在使用梯度下降算法进行模型参数估计时，训练的样本中会容易出现数据相差很大的情况，这就会造成训练过程中需要经历很长的迭代才能找到最优参数，为了加快梯度下降的执行速度。需要将各个特征的值标准化，使得取值范围大致都在[ − 1 , 1 ] [-1,1][−1,1]区间内。
常用的方法有以下两种：
第一种是0均值标准化 (z-score标准化)
x : = x − u σ x:=\frac{x-u}{\sigma}x:=σx−u
其中u uu是均值，σ \sigmaσ是标准差。经过处理后的数据符合标准正态分布，即均值为0，标准差为1。第二种是min-max标准化 (Min-Max Normalization)
x : = x − m i n m a x − m i n x:=\frac{x-min}{max-min}x:=max−minx−min
经过处理后数据全部落在[ 0 , 1 ] 区 间 内 [0,1]区间内[0,1]区间内。这种方法有一个缺陷就是当有新数据加入时，可能导致m a mamax和m i n minmin的变化，需要重新定义。
这两种归一化方法的适用场景为：
在不涉及距离度量、协方差计算、数据不符合正太分布的时候，可以使用第一种方法或其他归一化方法。比如图像处理中，将RGB图像转换为灰度图像后将其值限定在[0 255]的范围
在分类、聚类算法中，需要使用距离来度量相似性的时候、或者使用PCA技术进行降维的时候，第二种方法(Z-score standardization)表现更好。
参考链接
机器学习经典算法之-----最小二乘法
机器学习笔记（二）——多变量最小二乘法
详解梯度下降法求解线性模型参数
数据归一化和两种常用的归一化方法