机器学习——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}\)，而纠正过拟合的一种办法，就是增加样本量。

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