机器学习基石-Linear Regression

Linear Regression

Lecture8中我们主要介绍说我们的VC理论在有杂讯的情况下也是成立的，然后今天我们主要来学习一个基本的演算法：linear regression。

Linear Regression Problem

首先我们回顾我们之前研究过的信用卡合法模型，我们将是否核发的问题转化为核发的额度的问题，即我们的问题变成了一个回归问题而非分类问题。

在线性回归问题上，我们的思路是给与各个维度特征一个权重然后计算一个分数(h(x) = wT x)，这就是线性回归的hypothesis。

然后我们可以将问题做一个可视化的展示，我们分别展示输入空间为一维和二维的情形（见上图）,我们容易发现我们衡量模型的好坏就是看实际点与我们模型线（或平面）间的residual。

然后我们选取合适的错误衡量方式，通过前辈们的研究，对于线性回归一般采用square error来衡量，相应我们可以得到Ein和Eout的计算公式（其中需要强调的是，我们之后的问题设定转至有杂讯的情形，即x取样字某个分布，y也是取样自某个分布，我们可以理解成（x,y)取样自某个联合分布，我们需要看在这样的设定条件下learning的效果），那么接下来的问题就转化为怎么将Ein做到最小的问题。

Linear Regression Algorithm

我们将Ein做数学上的变形处理，可以得到Ein的矩阵形式。(见上图）

我们可以将Ein看成w的函数，容易发现他是一个连续、可微的函数，并且是一个凸函数，那么Ein的最低点在梯度等于0的点上取到，所以我们的问题进一步转化为求梯度等于0的那个w值。

我们容易得出梯度公式，我们令其等于零，当XTX的反矩阵存在时，容易得到左边的公式解（其中我们定义pseudo-inverseX†），其他情况我们可以得到更一般的X†进而得到问题的解。

然后我们总结下这个算法过程：我们提取资料整理得到需要的矩阵，然后计算X†，最后计算返回w。

Generalization Issue

接下来我们看看线性回归中Eout的大小，最终通过他来看看learning的效果，我们的思路是从Ein出发。

我们对Ein的公式做一个整理，可以得到上图的结果，其中我们定义一个hat matrix H。我们从几何角度来解读，yˆ存在于由X展开的一个空间上，我们想要y−yˆ越小越好，则他应当垂直于x空间，于是H做的事情就是将y投影到平面上得到yˆ。相应我们可以得到：trace(I − H) = N − (d + 1)，这个公式不作详细证明，几何上可以理解成N维投影到d+1维，最多还整多少自由度。

我们想象，在有杂讯的场景下的learning，y可以看成是我们的目标函数f(x)加上某个noise产生得到的，然后我们使用（I-H)对noise做一个投影同样可以得到y−yˆ，于是我们经过相关整理可以得到上图的公式，进一步可以的到Eout的公式，公式比较复杂不作进一步推导。

我们可以画出Ein和Eout的平均误差与资料量间的关系大致如上图，中间的σ2对应的是错误的水平。

Linear Regression for Binary Classification

我们现在来总结一下线性分类和线性回归的异同，我们发现线性回归的解貌似简单很多，然后我们发现线性分类的输出结果包含于R中，那么我们是否可以直接跑线性回归然后返回相应的sign(wTLINx)，避免跑PLA或者pocket等算法呢？

问题的关键在于看两种算法的错误水平是否有明显差异。

我们可以画出两种方法的错误衡量方式，我们容易发现平方的误差是要大于0/1误差的，进一步我们可以结合VC理论来解释，为了追求求解问题的效率，我们换了一个更高的错误衡量方式（更宽松的bound），所以我们是可以使用线性回归来做binary classification的，只是他的精确度可能没有那么高，不过实际上一般也还不错。

实际学习流程中，我们还经常做的一件事是将linear regression的结果作为PLA或pocket的初始输入，能大大提高算法的效率。

本节课我们主要学习的线性回归，首先我们提出问题，然后我们具体分析问题并提出解决方案主要利用pseudo-inverse，然后我们分析Ein和Eout间的关系，最后我们将linear regression和linear classification联系起来。