[置顶] 加州理工学院公开课：机器学习与数据挖掘_线性模型（第三课）

这一课时主要是讲述了线性模型的一些处理。

包括：

1、输入数据的表示（Input Representation）

2、线性分类（Linear Classification）

3、线性回归（Linear Regression）

4、非线性模型转换（Nonlinear Transformation）

作者认为，如果要测试某个模型的可用性，最好就是利用真实数据。

为了讲解线性模型如何应用，作者利用线性模型来解决邮局数据辨别问题：

由于不同的人有不同的书写习惯，对于同一个数字其书写形式可能各异，但是其基本骨架不会变化太大。如下面一幅图是来自邮局中的，来自真实世界的数据：

在上图的那些数据中有些数字是很容易辨认的，但是有些数据却难以辨认，比如倒数第二行最后一个数字究竟是‘8’还是‘0’ ？

为了识别这些数字，我们需要机器学习。在这里作者利用了感知器模型（线性模型）来解决这个问题。

需要做的第一点就是如何输入数据（Input Representation）？

假设每个数字像素都是 16*16的，

那么我们可以对每一张图片输入16*16 = 256 个点，对应的我们有 256+1 个参数：x0 -- x256。我们期望通过机器学习来确定所有的这些参数的值，可是参数这么多，机器学习可能需要很多的时间来完成，而且效果不一定好。观察到有一些像素点是不需要的，因此我们应该从这些像素点中抽取出一些特征出来，用来表示每一张图片，这样就可以把维度降下来，从而降低学习强度。观察到不同的数字其强度（黑色的点数）和对称性是不一样的，因此我们尝试用强度和对称性来描述每一张图片，即抽取出特征，从而把维度从 257 降到 3 维（不要忘记w0）。当然我们在提取出有用的信息的同时可能也丢掉了同样多的有用信息。进过特征抽取后，每一张图片的表示如下：

现在我们可以利用这些特征来进行机器学习了。（Linear Classification）（为了简化问题，只处理了数字‘1’和‘5’）。根据线性模型的公式：h(X) = WX(W T 均是向量)。下面是学习的效果图。

每幅图的左边是利用了线性模型进行学习的过程及结果，左图中红色线表示实际的结果，绿色线表示学习的结果。由于数据不是线性可分的，所以算法不会自动停止。因此在这里定义迭代1000次后强制停止。并把最后一次迭代结果作为最终输出。但是学习的效果并不是很理想，分割线太过偏上了。这是因为最后一次迭代的结果不一定是最好的，有可能刚好迭代到一次坏的数据那里就停止了。所以就有了后面的口袋算法（Pocket Algorithm）如下每幅图中右边的图就表明是利用口袋算法得到的结果，可以看到，最后结果表现的很好，但是依然有一些点无法正确分类，但是没所谓，不要求百分百正确，主要错误在允许的范围内就可以。

   

说了这么多，那么究竟什么是口袋算法呢？

口袋算法就是增加一个跟踪器，该跟踪器跟踪最好的结果，并把它记录下来。这样在最后的时候，跟踪器就保留了所有迭代中表现的做好的那次迭代。可是为什么叫做口袋算法而不是什么其它的？作者解析说：想象一下，每次都把最好的结果放到口袋里，当发现更好的结果的时候，就把更好的放到你的口袋中并丢弃口袋中原有的结果。最后当算法结束时，你只需要把你口袋里面的结果拿出来就是了。所以叫做口袋算法。(呵呵，好生动)

接下来作者讲到线性回归（Linear Regression ）问题

Regression = Real-Valued Output

当每次提到一些变量是否跟别的变量是否有关时，想到的就是回归。

利用线性回归我们求出一条线（或面，这个要根据参数数量即维数来决定），使得误差最小

   

二维：线 三维：面

线性回归方程如下：

但是应该如何衡量误差？毕竟回归就是为了找出一个函数，使得该函数与真实函数之间的误差最小化。作者在这里用了标准的回归误差计算函数：平方差。

为了求出该误差函数的最小值及相应的 W，我们需要进行求导：标准矩阵微积分：

只要当 XW = y 时即可求出，求解过程如下：等式左边同时乘上 X 的逆，然后同时乘上 XtX 的反，那个 X头上有个加号的叫做伪倒数。

现在，我们已经求出 W 了。但是如何利用线性回归来进行分类？因为二元结果也属于实数，所以可以利用线性回归进行分类，当结果为真的时候我们把它作为 +1 类，为负时则认为是 -1 类。

问题是线性回归真的可以用来进行分类？先看一张效果图：

其中蓝色部分属于 +1 类，红色属于 -1 类。越往上的区域，正直越大，越往下的区域正直越小。但是回归方程试图使所有的负数变为 -1， 所有的正数变为 +1，可是它不能，对于那些 -2，-3 的值来说它只能把它当做错误处理。所以线性回归只能最小化误差，但是不是真正的分类！什么？不是真正的分类？are you kidding me ？

不急，虽然不是真正的分类，但是我们已经成功了一半了，如果我们把 W 初始化为线性回归算出来的 W 然后继续利用口袋算法等进行迭代那样就能加速整个过程了，毕竟如果一开始就是靠口袋算法，可能要迭代很久才能达到我们需要的值，因此我们为什么不来一次跳跃呢？这就是线性回归于分类的结合了。

（虽然是这么说，只是我不是很懂那个为什么不能把负数变成 -1，为什么会把 -2 等当做错误来处理？？？...）

最后，作者讲到如何把非线性问题转换为线性问题。

在本节中作者并没有提出一个理论性的方法关于如何指导转换，这些将会在下一课时提到。在这一课时中，作者提出了一个例子并且利用了转换方法，成功地把非线性可分问题转换成线性可分问题，如下：

左边的是原始的数据集，很明显是非线性可分的，但是如果我们对输入进行处理，把 x1，x2 的值同时平方，则相当于把左边的空间映射到右边的空间中，这样就成功的把非线性可分问题转换成线性可分问题了，需要注意的一点是，当输入新的x的时候我们要利用同样的方法先进行转换。

结论：

线性可分模型是机器学习中一个很重要的模型之一，有很多模型都是建立在线性可分模型上面的。

当我们的输入是多维的时候，为了降低学习的难度及时间，我们需要对输入的表示进行处理，抽取出特征，降低维度，从而降低机器学习的成本。

为了加快机器学习的过程及质量，可以利用线性回归方法先求出一个 W 作为线性模型的初始值，然后再此初始值上进行迭代。

由于现实中很多问题的数据都不是严格线性可分的。如果存在一条可以接受的边界（只有少数的点分类错误），对于这类问题，我们没有办法使算法收敛，但是我们依然可以应用线性模型来解决，只是我们需要限定迭代的次数，同时利用口袋算法找出在迭代过程中最好的结果作为最终的结果。

另外对于那些明显线性不可分的问题，我们可以通过对输入数据进行处理从而转换成线性可分的问题，然后利用线性模型进行求解。