台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

从这节课开始就进入机器学习基石这门课的下半部分，之前的课程中介绍了linear classification的问题，这节课将继续介绍一个新的问题：Linear Regression(线性回归)。
一、Linear Regression Problem
台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

首先，仍然以信用卡发放为例，这一次问题改为如何给发放信用卡的用户设定信用额度？
这种输出空间不再是0或1，而是整个实数R的问题，我们称之为Linear Regression。
由上图，Linear Regression的目的在于找到一条直线（一维）或者一个平面（二维）使得所有样本中的点越接近这个直线/平面越好，即剩余误差residuals达到最小；
那怎么来评估这个误差呢？
一般情况下，我们使用squared error来进行error measure；

二、Linear Regression Algorithm
接下来，我们需要来求解一下什么时候Ein(w)达到最小：
台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

经过化简，我们把Ein用X、w、y进行表示，由于X和y是已知，那么我们的任务就是找出一个w使得Ein达到最小；

台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

对于此类的Linear Regression问题，Ein(w)一般是凸函数，就意味着只要对Ein(w)求导，使其等于0，就可以找到最优解；
那么将Ew对每个wi,i=0,1,⋯,d求偏导，偏导为零的wi，即为最优化的权重值分布。

台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

对Ein(w)进行求矩阵偏导如上；

台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

令偏导为零，最终可以计算出权重向量w的值了；
我们把上图中 $(X^TX)^{-1}X^T$ 称为伪逆矩阵pseudo-inverse，记为 $X^十$ ，维度是(d+1)xN。
我们注意到，伪逆矩阵中有逆矩阵的计算，逆矩阵 $(X^TX)^{-1}$ 是否一定存在？一般情况下，只要满足样本数量N远大于样本特征维度d+1，就能保证矩阵的逆是存在的，称之为非奇异矩阵。
但是如果是奇异矩阵，不可逆怎么办呢？其实，大部分的计算逆矩阵的软件程序，都可以处理这个问题，也会计算出一个逆矩阵。所以一般伪逆矩阵是可解的。

三、Generalization Issue
现在，可能有这样一个疑问，就是这种求解权重向量的方法是机器学习吗？这不就只是方程式的求解而已么？
台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

一种认为这不是机器学习，因为这种closed-form解的形式跟一般的机器学习算法不一样，而且在计算最小化误差的过程中没有用到迭代；
另一种认为这属于机器学习，因为从结果上看，Ein和Eout都实现了最小化，而且实际上在计算逆矩阵的过程中，也用到了迭代；
其实，只从结果来看，这种方法的确实现了机器学习的目的。下面通过介绍一种更简单的方法，证明linear regression问题是可以通过线下最小二乘法方法计算得到好的Ein和Eout的。
首先，我们根据平均误差的思想，把Ein写成如上图的形式（ $I$ 为单位矩阵），同时我们把 $XX^十$ 称为帽子矩阵H；
下面从几何图形的角度来介绍帽子矩阵H的物理意义：
图中，y是N维空间的一个向量，粉色区域表示输入矩阵X乘以不同权值向量w所构成的空间，根据所有w的取值，预测输出都被限定在粉色的空间中。向量 $\hat{y}$ 就是粉色空间中的一个向量，代表预测的一种。y是实际样本数据输出值;
机器学习的目的是在粉色空间中找到一个 $\hat{y}$ ，使它最接近真实的y，那么我们只要将y在粉色空间上作垂直投影即可，投影得到的 $\hat{y}$ 即为在粉色空间内最接近y的向量。这样即使平均误差 $\overline E$ 最小;
从图中可以看出， $\hat{y}$ 是y的投影，已知 $\hat y=Hy$ ，那么H表示的就是将y投影到 $\hat{y}$ 的一种操作。图中绿色的箭头 $y−\hat y$ 是向量y与 $\hat y$ 相减， $y−\hat y$ 垂直于粉色区域;
已知 $(I−H)y=y-\hat y$ ,那么I-H表示的就是将y投影到 $y-\hat y$ 即垂直于粉色区域的一种操作。这样的话，我们就赋予了H和I-H不同但又有联系的物理意义;
这里trace(I-H)称为I-H的迹，值为N-(d+1)。这条性质很重要，一个矩阵的 trace等于该矩阵的所有*特征值(Eigenvalues)*之和。下面给出简单证明：
介绍下该I-H这种转换的物理意义：原来有一个有N个自由度的向量y，投影到一个有d+1维的空间x（代表一列的自由度，即单一输入样本的参数，如图中粉色区域），而余数剩余的自由度最大只有N-(d+1)种。
如果存在noise的情况下，则如上图
图中，粉色空间的红色箭头是目标函数f(x)，虚线箭头是noise，可见，真实样本输出y由f(x)和noise相加得到。由上面推导，已知向量y经过I-H转换为 $y-\hat y$ ，而noise与y是线性变换关系，那么根据线性函数知识，我们推导出noise经过I-H也能转换为 $y-\hat y$ ;
由此我们推导出 $\bar E_{in}$ 和 $\bar E_{out}$ 如上，这个证明有点复杂，但是我们可以这样理解： $\bar E_{in}$ 和 $\bar E_{out}$ 形式上只差了 $\frac{(d+1)}N$ 项，从哲学上来说， $\bar E_{in}$ 是我们看得到的样本的平均误差，如果有noise，我们把预测往noise那边偏一点，让 $\bar E_{in}$ 好看一点点，所以减去 $\frac{(d+1)}N$ 项。那么同时，新的样本 $\bar E_{out}$ 是我们看不到的，如果noise在反方向，那么 $\bar E_{out}$ 就应该加上 $\frac{(d+1)}N$ 项。
我们把 $\bar E_{in}$ 和 $\bar E_{out}$ 画出来，得到学习曲线：
当N足够大时， $\bar E_{in}$ 和 $\bar E_{out}$ 逐渐接近，满足 $\bar E_{in}$ ≈ $\bar E_{out}$ ，且数值保持在noise level。这就类似VC理论，证明了当N足够大的时候，这种线性最小二乘法是可以进行机器学习的，算法有效！

四、Linear Regression for Binary Classification
之前介绍的Linear Classification问题使用的Error Measure方法用的是0/1 error，那么Linear Regression的squared error是否能够应用到Linear Classification问题？
台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

下图展示了两种错误的关系，一般情况下，squared error曲线在0/1
error曲线之上。即 $err_{0/1}≤err_{sqr}$ .

台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression
根据之前的VC理论，Eout的上界满足：

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

五、总结
本节课，我们主要介绍了Linear Regression。首先，我们从问题出发，想要找到一条直线拟合实际数据值；然后，我们利用最小二乘法，用解析形式推导了权重w的closed-form解；接着，用图形的形式得到 $\bar E_{in}-E_{out}≈\frac {2(d+1)}{N}$ ，证明了linear regression是可以进行机器学习的，；最后，我们证明linear regressin这种方法可以用在binary classification上，虽然上界变宽松了，但是仍然能得到不错的学习方法。

本文来自红色石头Will 的**** 博客并略做修改，全文地址请点击：https://blog.****.net/red_stone1/article/details/71599034?utm_source=copy

台湾大学林轩田《机器学习基石》学习笔记第9讲——Linear Regression

相关推荐