机器学习基石第十二周笔记

一.Quadratic Hypothesis
之前学习了线型的分类器，今天将介绍非线性的分类器。
下图左边的数据，我们用直线分类器能够很容易的将数据分开，但是右边的数据我们却不行，那么我们该怎么办呢？

之前对于线型不可分的数据我们容许有一定的误差，但是这里的误差明显太大了，所以不能应用。但是我们发现该数据是能够用一个圆进行分割的，所以这里我们将应用Circular Separable.


我们将输入特征进行转换，另z0=1,z1=x1^2,z2=x2^2并将x空间的数据映射到z空间进行显示，发现数据在z空间能够被线型分开，于是我们就能在z空间使用之前所学过的知识进行分类了。

我们能够学得的结果如下图所示，能够是圆，椭圆，双曲线和常数，这样我们就相当于用x空间的上述形状对数据进行分类了。

但是上述的模型学到的圆等形状他们的原点必须要在圆心，要想突破这个限制我们在从x转换到z空间的时候需要增加移动项的组合。

仔细分析会发现，当后三项为0时形状就会退化成直线，所以上述模型里面包含了直线和常数模型。
二.Nonlinear Transform
非线性分类的流程如下所示，首先进行特征转换将x空间转换成z空间，在z空间进行线型分类，然后将分类好的点反转换回x空间。
注：实际上是对x空间的一个点进行转换分类后直接将该点进行标记，而不是将转换的点进行反转换

三.Price of Nonlinear Transform
想象很美好，现实很骨感，为了实现上述的φ的转换，我们要付出极大的计算和内存空间，假如我们的原始数据的维数为d，我们要转换的多项式次数为Q，那么我们转换后的数据的维数将会是O(Q^d)这将会额外浪费极大的计算资源和效率。

同样的，由于d的增加，我们的VC维也会增加，这就会增加模型的复杂度。

所以我们应该如何选取Q也成为了一个难题，如下两幅图，当我们选择大的Q时Ein会下降，但是Eout与Ein的差会变大，选择小的Q，Ein会增加，但是Ein与Eout的差距会变小，这就会形成矛盾。

但是我们绝对不要靠我们的眼睛来决定Q的大小，因为第一，我们的眼睛不能够看到大于3维的数据，而我们所用的数据大多是三维以上，第二，我们的眼睛会带入主观偏见，这会妨碍算法求得真正的规律。

四.Structured Hypothesis Sets
从Q=1到Q=n假设空间的变化及关系如下图所示：

VC维和Ein的关系如下图所示：

那我们该怎么决定Q呢？我们应该从Q=1开始从简单往难的模型进行试验，如果简单的模型能找到一个小的Ein那么我们就选择它。