线性回归

本节的主要参考资料是机器学习基石[1]和机器学习[2]网络课程。

线性回归模型

线性回归的假设集（hypothesis）为 \begin{equation} h(\mathbf x) = \mathbf w^T\mathbf x， \label{eq:linear-regression-model} \end{equation} $\mathbf x$是含有常数项$x_0 = 1$的$d+1$维向量$\mathbf x =\left[1,x_1,\ldots,x_d\right]^T$，$\mathbf w=\left[w_0,w_1,\ldots,w_d\right]^T$，$d$是特征维数。

目标代价函数采用平方误差和估计 \begin{equation} E_{in}(\mathbf w)={1\over N}\sum_{n=1}^N\left(\mathbf w^T\mathbf x_n-y_n\right)^2， \label{eq:cost-function-linear-regression} \end{equation} $N$是样本数。通过机器学习算法求得线性回归的参数 \begin{equation} \mathbf w_{LIN} = \arg\min_{\mathbf w}E_{in}(\mathbf w)， \end{equation} 通常方法有正规方程（normal equation）的解析方法和梯度下降法（gradient descent）。

解析方法

解析方法得到的最优解也称为线性回归的最小二乘解。

代价函数改写为矩阵形式 \[ E_{in}(\mathbf w) ={1\over N}\lVert\mathbf X\mathbf w-\mathbf y\rVert^2 ={1\over N}\left(\mathbf w^T\mathbf X^T\mathbf X\mathbf w-2\mathbf w^T\mathbf X^T\mathbf y+\mathbf y^T\mathbf y\right)， \] $\mathbf X$是样本数据矩阵，每行代表一个样本点，每列代表一个特征，第一列的向量$\mathbf 1_N$对应常数偏移。$E_{in}(\mathbf w)$是连续可微的凸函数，当$\nabla E_{in}(\mathbf w)=0$时取得最小值， \[ \nabla E_{in}(\mathbf w)={2\over N}\left(\mathbf X^T\mathbf X\mathbf w-\mathbf X^T\mathbf y\right)， \] 取得最小值时 \begin{equation} \mathbf w_{LIN} = \left(\mathbf X^T\mathbf X\right)^{-1}\mathbf X^T\mathbf y = \mathbf X^\dagger \mathbf y， \end{equation} $\mathbf X^\dagger$称为伪逆（pseudo-inverse）。通常情况$N\gg d+1$，因此$\left(\mathbf X^T\mathbf X\right)^{-1}$通常都可逆；如果不可逆，解不唯一。

导致$\mathbf X^T\mathbf X$不可逆的原因可能是冗余特征（redundant features）或者特征数目过多（$d$太大而$N$太少），解决的办法：

• 对于冗余的线性相关特征，例如$x_1 = 2x_2$，删除线性相关特征；
• 对于特征数目过多，例如$N<d$，删除特征或正则化（regularization）¹。

Matlab的pinv函数可以处理$\mathbf X^T\mathbf X$不可逆的情况²。

解析方法求解$\mathbf w_{LIN}$是机器学习算法吗？

✅通过VC维的角度分析，能得到小的$E_{out}\left(\mathbf w_{\small{LIN}}\right)$，就是学习……

• 能够得到最佳的$E_{in}$；
• $d+1$个变量，有限的$d_{VC}$，因此有好的$E_{out}$；
• 事实上，求解伪逆的过程也是迭代逐步最优的过程（高斯消元法）。

VC维考察的是个别的$E_{in}$³，从$E_{in}$平均误差角度分析 \begin{equation} \bar E_{in} =\varepsilon_{\mathcal D\sim P^N}\left\{E_{in}\left(\mathbf w_{LIN}\mbox{ w.r.t }\mathcal D\right)\right\} =\mbox{noise level}\cdot\left(1-{d+1\over N}\right)， \label{eq:noise-level-e-in} \end{equation} $\mbox{noise level}$表示数据中的噪声，${d+1\over N}$表示比噪声小的比率，数据越多二者差别越小。

$E_{in}\left(\mathbf w_{LIN}\right)$计算方法为 \[ E_{in}\left(\mathbf w_{LIN}\right) ={1\over N}\left\lVert\mathbf y-\hat{\mathbf y}\right\rVert^2 ={1\over N}\left\lVert\mathbf y-\mathbf X\mathbf X^\dagger\mathbf y\right\rVert^2 ={1\over N}\left\lVert\left(\mathbf I-\mathbf X\mathbf X^\dagger\right)\mathbf y\right\rVert^2， \] $\mathbf X\mathbf X^\dagger$让$\mathbf y$加帽$\wedge$变成了$\hat{\mathbf y}$，也叫帽矩阵⁴（hat matrix），记为$\mathbf H$。

图 1: ［左］：图解证明；［右］：学习曲线 [PNG]

由$\hat{\mathbf y}=\mathbf X\mathbf w_{LIN}$可知，$\hat{\mathbf y}$是$\mathbf X$列向量的线性组合，也就是如上图左所示，$\hat{\mathbf y}$位于$\mathbf X$张成的线性空间中。当$\mathbf y-\hat{\mathbf y}$垂直于该生成空间时，$\left\lVert\mathbf y-\hat{\mathbf y}\right\rVert^2$的值最小。$\mathbf H$将$\mathbf y$投影为$\hat{\mathbf y}$，$\mathbf I-\mathbf H$将$\mathbf y$投影为$\mathbf y-\hat{\mathbf y}$。$\mathbf I-\mathbf H$的迹为$trace(\mathbf I-\mathbf H)=N-(d+1)$，表示自由度从$N$降到$N-(d+1)$。

观测到的数据$\mathbf y$是理想的数据空间$f\left(\mathbf X\right)$叠加一些噪声。$\mathbf y-\hat{\mathbf y}$也可以从噪声投影得到，如上图左所示， \[ E_{in}\left(\mathbf w_{LIN}\right) ={1\over N}\left\lVert\mathbf y-\hat{\mathbf y}\right\rVert^2 ={1\over N}\left\lVert(\mathbf I-\mathbf H)\cdot\mbox{noise}\right\rVert^2 ={1\over N}(N-(d+1))\lVert\mbox{noise}\rVert^2， \] 因此可得公式\eqref{eq:noise-level-e-in}的结论。$E_{out}$的证明过程叫复杂，仍然可以得到 \[ \bar E_{out} =\mbox{noise level}\cdot\left(1+{d+1\over N}\right)。 \]

$\mbox{noise level}$可以用$\sigma^2$表示，从上图右可见，$\bar E_{in}$和$\bar E_{out}$在$N\rightarrow\infty$时都会趋近于$\sigma^2$。期望的泛化误差（generalization error）可以用${2(d+1)\over N}$衡量，这里是平均情况，VC维衡量的是最坏的情况。

梯度下降法

梯度下降法就是沿梯度下降方向更新参数，也就是对每个特征的权值$w_i$，不断迭代执行更新 \begin{equation} w_i := w_i-\alpha{\partial E_{in}(\mathbf w)\over\partial w_i}\quad(i=0,1,\ldots,d) \end{equation} 直至收敛，其中$\alpha$表示学习速率，梯度计算公式为 \[ {\partial E_{in}(\mathbf w)\over\partial w_i} ={1\over N}\sum_{n=1}^N\left(\mathbf w^T\mathbf x_n - y_n\right)x_{n,i}。 \]

参数须同时更新，也就是当每个$w_i$都更新完成后，才能用新的$\mathbf w$计算$E_{in}(\mathbf w)$，具体可参考Andrew NG的讲义⁵。

图 2: ［左1］：未归一化梯度下降路径；［左2］：归一化梯度下降路径；
［右］：梯度下降路径 [PNG]

梯度下降法需要将所有特征归一（feature scaling）到统一的尺度（不用归一化$x_0$），比如$-1\le x_i\le 1$， \[ \hat{x}_i = \frac{x_i - x_{mean}}{x_{max}-x_{min}} \qquad\mbox{or}\qquad \hat{x}_i = \frac{x_i - x_{mean}}{x_{std}}， \] 这样有助于提高梯度下降法的速度，如上图左2所示。但是，归一化改变了特征的物理意义，有时并非好事儿。

学习率$\alpha$的注意事项：

1. 在迭代过程中不需调节$\alpha$大小，由于梯度会不断减小，在固定$\alpha$的情况下梯度下降步长也会自动减小，如上图右所示；
2. $\alpha$太小收敛慢，太大可能错过极值点而不收敛，甚至可能导致$E_{in}(\mathbf w)$不降反升。

线性回归的代价函数$E_{in}(\mathbf w)$不存在局部极值（local optima），极小值就是全局极值⁶。

两种方法对比

分类问题

线性分类器和线性回归的对比如下表：

能否利用线性回归的高效，借助$g(\mathbf x)=\mbox{sign}\left(\mathbf w_{LIN}^T\mathbf x\right)$，用线性回归解决分类问题？✅

图 3: 线性分类器和线性回归误差比较 [PNG]

上图展示了两种方法误差的对比，$err_{0/1}\leq err_{sqr}$，平方误差是0/1误差的上限。从VC维的理论可知 \[ \mbox{classification }E_{out}(\mathbf w) \leq \mbox{classification }E_{in}(\mathbf w)+\sqrt{\cdots} \leq \mbox{regression }E_{in}(\mathbf w)+\sqrt{\cdots}， \] in-sample回归误差也是out-sample分类误差的上限，做好in-sample回归误差也是做好in-sample分类误差的一种方法，in-sample回归误差很小时能保证out-sample分类误差也很小。由此可见，可用线性回归解决分类问题。

也可直接将回归问题视为分类问题，只是用$err_{sqr}$当作$\widehat{err}$作为$err_{0/1}$误差的近似。为分类问题选择稍宽松的误差上界，这样容易求解参数。

在很多时候，用线性回归解决分类问题效果尚可。如果要让效果更好，可将$\mathbf w_{LIN}$当做PLA或pocket算法的初始值$\mathbf w_0$，加速PLA或pocket算法。

多项式回归

构造多项式特征，利用线性回归模型解决非线性问题，称为多项式回归（polynomial regression）。例如利用$x_1 = x, x_2 = x^2, x_3 = x^3, \ldots $，构造新的特征向量$\mathbf x$，带入线性回归模型\eqref{eq:linear-regression-model}求解。从另一个角度看，当特征是多项式时，可直接利用线性模型求解。

当对特征进行高次多项式变换后，取值范围可能急剧变化，需要对多项式特征进行尺度归一化处理[3, P. 8]。

参考资料

1. [1]H.-T. Lin, “Lecture 9: Linear Regression.” Coursera, 2014. [Online]
2. [2]A. Ng, “Linear Regression with multiple variables.” Coursera, 2014. [Online]
3. [3]A. Ng, “Programming Exercise 5: Regularized Linear Regression and Bias v.s. Variance.” Coursera, 2014. [Online]

脚注