机器学习——linear regression

终于完成了机器学习基石相对理论的部分，可以开始一些具体的算法的学习了。首先学习的第一个算法就是线性回归（linear regression）。 线性回归想做到的事情是，给出一堆点，使用一条直线（平面或者其他）来拟合这个dataset。而在之前的noise and error中提到了，它用来衡量错误的办法是$(y - y')^2$。

和之前的机器学习算法也一致，因为VC bound在线性回归的例子中也一样适用，所以我们想做的是保证$E_ {in}$越小越好。

对于线性回归的H集合是 $y' = W^TX$，当然$X$，$W$都是列向量，向量的维度是d+1（d为特征量的个数）.为了minimize $E_ {in}$，首先我们应该写出来$E_ {in}$的表达式： $$E_ {in} = \frac 1 n \sum _ {i = 1} (h(X_n) - y)^2 = \frac 1 n \sum _ {i = 1} (W^TX_n - y_n)^2$$

这个表达式看着还比较复杂，有个求和符号在里面。首先，这后面有N个平方和，我们可以很轻松的想到向量的范数求法。因此，我们可以将原式写成对向量求范数的形式：

$$E_ {in} = \frac 1 n || XW - Y||^2$$ 上式中 $$X = \begin{bmatrix} ...X_1^T... \\ ...X_2^T... \\ ..........\\ ...X_n ^T ... \end{bmatrix}$$ X是一个n*（d+1）的矩阵，n是样本个数，d是特征量个数。

因此$E_ {in}$可以说是一个关于W的函数，而且可以证明的是，这个函数是连续的（continuous），可导的（differentiable）,并且是凸函数（convex）。因此我们一定可以求得最低点，也就是$E_ {in}$的最小值。与实数的函数一样（实际上求的是W的各个方向的偏导数），在取最小值的那个点的时候，$E_ {in}$关于$W$的导数是0，表明取得是极值，也就是梯度是0。

将上式展开可以得到：

$$E_ {in} = \frac 1 n (W^TX^TXW -2Y^TXW +Y^TY)，$$ 将除了W之外的矩阵或者数字看成常量，则可以得到： $$E_ {in} = \frac 1 n (W^TAW-2BW+c)$$ 为了求关于$W$的导数，我们首先想象一下如果是$W$一维的话的样子。 $$E_ {in} = aW^2-2bW+c ; \frac {dE_ {in} } {dW} = 2aW-2b$$

对应到矩阵上来说: $$\frac {dE_ {in} } {dW} = \frac 1 n 2AW-2B$$

可以看到的是梯度是一个向量。

为了使得$E_ {in}$取得最小值，那么$X^TXW = X^TY$,如果$(X^TX)$的反矩阵存在，那么很简单: $$W = (X^TX)^{-1}X^TY$$

我们称$(X^TX)^{-1}X^T$为pseudo-inverse $X^{+}$。而且大多数时候我们遇到的都是可逆的，因为$n>>d+1$，这意味着首先对于X矩阵来说，它的秩很可能就是等于d+1的.这样它们相乘的秩很大可能也是d+1，也就是可逆。

但是如果遇到另外的情况，如不可逆，我们可以使用其他的方式来定义$X^{+}$，具体的数学原理需要更详细的线性代数知识，但是我们知道很多程序包里都实现了这些东西，用它一样可以得到比较好的结果。

综上，$W = X^{+}Y$,$Y' = XW = XX^{+}Y$.

最后，这个算法之所以可以学习，我们可以使用VC bound来证明。但是还有另一种方法，也可以证明它泛化能力不错，可以取得良好的学习效果，当然，与VC bound一样，严格的证明需要更严密的数学推导，下面只是简要介绍。

首先，我们推导$\overline {E_ {in} }$是很接近噪声的（噪声意味着我们无法通过学习进行改善的部分），而同样的步骤可以用在对$\overline {E_ {out} }$的分析上，这样就说明了，平均来说我们的算法是可以取得很好的学习效果的。

首先，我们应该定义一下$\overline {E_ {in} }$： $$\overline {E_ {in} } = \epsilon _ {D~P^N}\left\{\ E_ {in}(W_ {LIN} w.r.t. D) \right\} = noise level \cdot (1-\frac {d+1}{N})$$

具体的含义就是多个样本的$E_ {in}$平均值，大概看起来会接近noise level，而当样本量越大，与noise level越接近。

首先，我们应该将线性回归得到的结果带入$E_ {in}$的表达式中： $$E_ {in} = \frac 1 N ||Y - \hat Y||^2 = \frac 1 N ||Y - XX^{+}Y ||^2 = \frac 1 N ||(I - X X^{+})Y||^2$$

我们称$XX^{+}$为hat matrix。

这里我们思考$\hat Y = XW$在做什么。Y是一个N维向量，而X可以看做是m个N维向量构成的矩阵，而实际上W的作用，是给每个矩阵中的N维向量分配一个参数，让他们做线性组合，最终得到一个新的N维向量。为了使得$\hat Y$尽量接近于$Y$，从另一个方面来说，就是让$Y - \hat Y \bot X's span$，也就是让他们的差尽量垂直于X所展开的空间，当垂直时，$\hat Y$等于Y在X上的投影，这时候二者相差是最小的.

实际上，Y一般不可能被X完美表示，因为一般来讲$N>>d$.所以我们能做的就是上面说的。

所以，Hat的作用就是将Y投影到X上。而$(I-Hat)$就是将Y转换为$(Y-\hat Y)$的矩阵。 而且我们可以计算出来$trace (I - Hat) = n - (d+1)$，意味着$(I- Hat)$有$N - d- 1$个自由度。

如果$Y$来自与一些理想的$f(X)$与噪声的组合，那么如果只是理想的函数，则上述得到的差距实际上是由噪声造成的，因此： $$E_ {in} = \frac 1 N ||Y - \hat Y||^2 = \frac 1 N ||(I - Hat)noise||^2 = \frac 1 N (N - d - 1)||noise||^2$$ 而$\overline {E_ {in} } = ( 1 - \frac{d+1}{N})noise level$ 利用类似的办法，可以推断出来，$\overline {E_ {out} } = ( 1 + \frac{d+1}{N})noise level$.

也就是平均来说，我们通过拟合样本，可以得到更小的错误率，但是泛化之后的错误率往往更大一点。

因此平均来说，我们可以将$E_ {in}$与$E_ {out}$画在一张图上：

如果对应到实际的机器学习，对于一些很少的样本量的机器学习过程，很容易拟合成功，得到很好的$E_ {in}$，甚至是0，但是这时候泛化能力却很差。机器学习，不是一味地增加特征量减少$E_ {in}$，而纠正过拟合的一种办法，就是增加样本量。

最后，我想说的是，上面的”证明”非常不严格，甚至有些地方让人费解。对于机器学习，理论部分严格的证明更多是数学和统计的事情，而学习计算机的人更多的是掌握各种算法，学习利用它来解决问题。即使这样，尽可能多地了解理论部分，对于实际的应用有很大的帮助。这个世界很复杂，永远保持一个好奇心吧。