---

---

9.Linear Regression

9.1 Linear Regression Problem

回顾银行发放信用卡的问题，之前的课程中通过是否给用户发放信用卡引出了二元分类问题；本节课程通过发放给用户多大额度的信用卡引出回归（regression）问题，主要是线性回归（linear regression）问题。

回归与分类是机器学习两类不同的算法。回归与二元分类的区别是输出空间不同，二元分类的输出空间为 $ y \in {+1,1} $，而回归问题的输出空间是实数域，即 $y \in R$y∈R 。线性分类与线性回归对比如下图所示。

以银行发放信用卡为例，输入集合依然是用户的特征空间，如年龄，年收入等，可以使用与二元分类一致的表示方式 $X = [x_0,x_1,...,x_d]$X=[x0​,x1​,...,xd​]，特征空间的维度为 $d+1$d+1 （特征集为 $d$d 维的 $X$X，加常数项 $x_o$xo​），因为输出集合的转变导致回归问题的假设函数与二元分类中的有所不同，但思想一致，仍需考虑对每个输入样本的各个分量进行加权求和，因此最终目标函数 $f$f（含有噪音，使用 $y$y 表示）的表示如9-1式所示。特征空间与权重 $w$w 的线性组合即为假设函数 Hypothesis，记为 $h(x)$h(x)，如式9-2所示。

从式9-2可以看出，与二元分类假设函数只差了一个取正负号的 $sign$sign 函数。通过下图可以更直观的理解线性回归。

上图中，左图为输入空间为1维的线性回归表示，其中圆圈○表示输入样本点，蓝色直线表示假设函数 $h(x)=W^TX$h(x)=WTX，连接圆圈与蓝色直线之间的红色线段表示样本点到假设函数的距离，称为残留误差（residuals），亦可简称为残差。右图是二维输入空间的情况，也有类似表示。而设计算法的核心思想是使样本集中的点更接近它，即使得总体残留物差最小。

最常用的错误测量方式是基于最小二乘法，其目标是计算误差的最小平方和对应的权重 $w$w，即上节课介绍的squared error，公式为下图中式9-3所示，$E_{in}(h)$Ein​(h) 如公式9-4所示。

在线性回归问题中，假设函数 $h$h 与权值向量 $w$w 是一一对应的，因此公式9-4通常表示为权值向量 $w$w 的形式，如上图中公式9-5所示。同理 $E_{out}(W)$Eout​(W) 表示如公式9-6所示。注意：这里使用的是含有噪音的形式，因此 $(X,y)$(X,y) 服从联合概率分布P。

VC-demention 的限制可以约束各种情况的学习模型，当然回归类型的模型也被也受此约束，想要学习到知识，只需要寻找 $E_{in}(W)$Ein​(W) 足够小便可以满足 $E_{out}(W)$Eout​(W) 够小的需求。

注意：最小二乘法可以解决线性问题和非线性问题。线性最小二乘法的解是
闭式解（closed form solution），也叫解析解（analytical solution），即可以根据具体的公式求解。线性最小二乘法的解为 $X=(A^TA)^{-1}A^Ty$X=(ATA)−1ATy ，而非线性最小二乘法没有闭式解（解析解），通常用迭代法求解。

---

习题1：

---

9.2 Linear Regression Algorithm

样本数据误差 $E_{in}(w)$Ein​(w) 是权重 $w$w 的函数，因为训练样本 $X$X 和样本标签 $y$y 均已知。所以问题也就转化为如何寻找 $w$w 使得 $E_{in}(w)$Ein​(w) 最小。

为了表示方便，将 $E_{in}(w)$Ein​(w) 的9-5式求和的形式转化成向量与矩阵的形式，如下图中 式9-7所示。

我们最初的目标是寻找最小的 $E_{in}(w)$Ein​(w) ，现在可表示为式9-8：

要求解此问题，需要先弄清楚左式的意义，其一维（d=1时）示意图如下图所示。

可以看出该函数为连续（continuous）、可微（differentiable）的凸（convex）函数，此处的凸函数其实就是我们学的凹函数，老师讲的跟我们学的有差别。寻找的最小的 $E_{in}(w)$Ein​(w) 类似于寻找谷底，即梯度（gradient）为 0 的点。梯度计算公式如式9-9所示。

现在需要寻找 $W_{LIN}$WLIN​ 使 得 $ \nabla_w E_{in}(W_{LIN}) = 0$，其中 $w_{LIN}$wLIN​ 表示线性（linear）。

那么应该如何寻找？首先，进一步将公式9-7转化为9-10：

注意上式中 A、b、c所代表的的含义，关于对向量求梯度可以这么理解：

线性代数的美妙之处就在于此，如此的相似。梯度公式可以用式9-11表示：

令式9-11求梯度结果为0，即可使得 $E_{in}(w)$Ein​(w) 最小。在输入空间 $X$X 与输出向量 $y$y 都为已知的情况下，求解最佳的假设函数 $W_{LIN}$WLIN​ 可分为两种情况，第一种是 $X^TX$XTX 可逆的情况，令式9-11等于0，即可求解，结果如式9-12所示。

其中 $X^†$X† 表示矩阵 $X$X 的伪逆（pseudo-inverse）。矩阵 $X$X 在 $N=d+1$N=d+1 时才是方阵，伪逆矩阵与方阵的逆矩阵具有很多相似的性质，因此而得名。注意：$X^TX$XTX 在大部分的情况下是可逆的，原因是在机器学习中， $X$X 通常满足 $ N \gg d+1$ ，即样本数量 $N$N 远大于样本的特征数量 $d+1$d+1，因此在 $X^TX$XTX 中存在足够的*度使其可以满足可逆的条件。

第二种情况是 $X^TX$XTX 不可逆的情况。在这种情况下，实际上可以得到许多满足条件的解，只需要通过其他的方式求解出 $X^†$X† ，选择其中一个满足条件 $W_{LIN} = X^†y$WLIN​=X†y 条件的解即可。

线性回归算法的求解过程如下：

• 首先通过已知的数据集 $X$X，构建输入矩阵 $X$X （样本）与输出向量 $y$y（样本标签）；
• 然后通过构造的输入矩阵和输出向量，求解伪逆；
• 最后通过伪逆求得假设函数 $W_{LIN}$WLIN​；

习题2：

---

9.3 Generalization Issue

本小节提出问题：上一小节中求解最佳假设函数 $W_{LIN}$WLIN​ 的算法，是否为机器学习？或者说这种方法是否有很好的泛化能力？

回答不是的理由：求解只一步就完成了，不像前面章节中提到的学习方法需要很多步的过程，即解析解（analytical solution）或称为封闭解、闭式解（closed-form solution）。因此不同于PLA等通过迭代法求解 $E_{in}(w)$Ein​(w) 最小解的算法。

回答是的理由：更看重结果，这种直接求解方式是数学推导中的精确解，因此求出的 $W_{LIN}$WLIN​ 一定是的 $E_{in}(w)$Ein​(w) 最小解，符合求解条件，而且求解伪逆算法（高斯消元法）并非如公式展示中显示的那样，一步就可以得出最终结果，而是需要几次循环迭代。而判断是否发生机器学习过程最主要标准是学习到的 $E_{out}(w)$Eout​(w) 是否够好。

通过改进VC-bound，也可以证明在线性回归问题中VC起到了很好的约束作用，即找到了好的 $E_{in}(w)$Ein​(w) 就可以保证 $E_{out}(w)$Eout​(w) 还不错。下面通过一种更简单的方法，证明线性回归问题是可以通过线下最小二乘法方法计算得到好的 $E_{in}(w)$Ein​(w) 和 $E_{out}(w)$Eout​(w) 。

公式 $\overline{E_{in}}$Ein​​ 中，$\varepsilon$ε 表示期望，不断的从整体样本空间中抽取样本集，计算其平均值； $w.\gamma.t$w.γ.t 表示关于；$noise \ level$noise level 表示数据中的噪音，$N$N 为每次抽样的样本数量，$d+1$d+1 为权值向量 $w$w 的维度。

根据平均误差的思想，改写上节提到的公式。新的公式 $E_{in}(W_{LIN})$Ein​(WLIN​) 中， I 为 $N \times N$N×N 的单位矩阵，$XX^†$XX† 被称为帽子矩阵，可以使用 $N \times N$N×N 的 H矩阵（hat matrix）表示。

通过几何图形更具体的了解 H矩阵 的物理意义。

图中，$y$y 是N维空间的一个向量，粉色区域表示输入矩阵 $X$X 乘以不同权值向量 $w$w 所构成的空间，根据所有 $w$w 的取值，预测输出都被限定在粉色的空间中。向量 $\hat{y}$y^​ 就是粉色空间中的一个向量，代表预测的一种。$y$y 是实际样本数据输出值。

机器学习的目的是在粉色空间中找到一个 $\hat{y}$y^​，使它最接近真实的 $y$y ，那么我们只要将 $y$y 在粉色空间上作垂直投影即可，投影得到的 $\hat{y}$y^​ 即为在粉色空间内最接近 $y$y 的向量。这样即使平均误差 $\overline{E_{in}}$Ein​​ 最小。

从图中可以看出， $\hat{y}$y^​ 是 $y$y 的投影，已知 $\hat{y} = Hy$y^​=Hy ，那么 H 表示的就是将 $y$y 投影到 $\hat{y}$y^​ 的一种操作。图中绿色的箭头表示的向量 $y-\hat{y}$y−y^​ 垂直于粉色区域。已知 $(I - H)y = y - \hat{y}$(I−H)y=y−y^​ ，那么 $(I - H)$(I−H) 就表示将 $y$y 投影到 $y-\hat{y}$y−y^​ ，即垂直于粉色区域。

$trace (I - H)$trace(I−H) 称为 $(I - H)$(I−H) 的迹，值为 $N-(d+1)$N−(d+1)。一个矩阵的迹（trace）等于该矩阵的所有特征值（Eigenvalues）之和。简单证明如下：

$(I - H)$(I−H) 转换的物理意义：原来有N个*度的向量y，投影到 $d+1$d+1 维的空间$x$x（代表一列的*度，即单一输入样本的参数，如图中粉色区域），而余数剩余的*度最大只有 $N-­(d+1)$N−­(d+1) 种。

在存在noise的情况下，上图变为：

图中，粉色空间的红色箭头是目标函数 $f(x)$f(x)，虚线箭头是 $noise$noise，可见，真实样本输出 $y$y 由 $f(x)$f(x) 和 $noise$noise 相加得到。由上面推导，已知向量 $y$y 经过 $I­-H$I­−H 转换为 $y-\hat{y}$y−y^​，而 $noise$noise 与 $y$y 是线性变换关系，由此推导出$noise$noise 经过 $I­-H$I­−H 也能转换为 $y-\hat{y}$y−y^​。则对于样本平均误差，有下列推导成立：

即：

证明有点复杂，可以简单理解： $\overline{E_{in}}$Ein​​ 与 $\overline{E_{out}}$Eout​​ 形式上只差了 $\frac{d+1} N$Nd+1​ 项，从哲学上来说， $\overline{E_{in}}$Ein​​ 是看得到的样本的平均误差，如果有noise，把预测往noise那边偏一点，让 $\overline{E_{in}}$Ein​​ 好看一点点，所以减去 $\frac{d+1} N$Nd+1​ 项。同时，新的样本 $\overline{E_{out}}$Eout​​ 是看不到的；如果noise在反方向，那么 $\overline{E_{in}}$Ein​​ 就应该加上 $\frac{d+1} N$Nd+1​ 项。 由 $\overline{E_{in}}$Ein​​ 与 $\overline{E_{out}}$Eout​​ 得到学习曲线：

其中在N趋于无穷大时，$\overline{E_{in}}$Ein​​ 与 $\overline{E_{out}}$Eout​​ 两者都会趋近于 $noise \ level$noise level 的值，即 $\sigma^2$σ2。

泛化误差之间的差距：$\frac{2(d+1)} N$N2(d+1)​。

至此可以表明在线性回归中可以寻找到很好的 $E_{out}$Eout​，因此线性回归可以学习。

---

习题3：

---

9.4 Linear Regression for Binary Classification

之前介绍的Linear Classification问题使用的Error Measure方法用的是0/1 error，那么Linear Regression的squared error是否能够应用到Linear Classification问题？

首先对比二元线性分类与线性回归之间的差异，分别在三个部分进行对比，输出空间、假设函数和错误衡量函数，如图9-7所示。

从求解问题的难度考虑，二元分类的求解是一个NP-hard问题，只能使用近似求解的方式，而线性回归通过求解析解，求解方便，程序编写也简单。

因此考虑能否通过求解线性回归的方式求二元分类问题，因为二元分类的输出空间 $\{-1，+1\}${−1，+1} 属于线性回归的输出空间，即 $\{-1，+1\} \in R${−1，+1}∈R，其中数据集的标记大于零的表示+1，小于零的表示-1，通过线性回归求得的解析解 $W_{LIN}$WLIN​，直接得出最优假设 $g(X)=sign(W_{LIN}X)$g(X)=sign(WLIN​X) 。但是这种推理只符合直觉，而如何使用数学知识去说明这种方式的合理性呢？

观察两种错误衡量方式：

观察两公式的共同特点都含有 $W^TX$WTX 这一向量内积的形式，如果将 $W^TX$WTX 作为横轴，将 err 作为纵轴，可以画出下图。

从图中可知有下式成立：

根据之前的VC理论， 的上界满足

在实际运用中，一般都将通过线性回归求得的解析解 $W_{LIN}$WLIN​ 作为PLA或者pocket的初始值 $W_{0}$W0​，达到快速求解的目的 。

从图中可以看出，用 $err_{sqr}$errsqr​ 代替 $err_{0/1}$err0/1​，仍然有上界，只不过是上界变得宽松了。也就是说用线性回归方法仍然可以解决线性分类问题，效果不会太差。二元分类问题得到了一个更宽松的上界，但是也是一种更有效率的求解方式。

---

习题4：

---

参考：
https://www.cnblogs.com/ymingjingr/p/4306666.html
https://github.com/RedstoneWill/HsuanTienLin_MachineLearning