本次Lecture主要是讲述如何将非线性问题变成线性问题来求解。

Quadratic Hypotheses

我们之前看到的都是线性的得分函数，这样在二维上是一条直线，三维上是一个平面。

在不具有线性性质的情况下，尽管比较小，能保证，但是在一些数据上会很大，这样的结果就不太理想了。

 就像在上图的左图中，我们可以用一个圆来划分，圆形内部是正类，外面是负类。假设它的hypotheses可以写成：，于是我们就能把这个式子再写成的形式——

这样我们就将x空间的点映射到z空间中去，在是可用圆来划分的，就可以线性划分，完成了的转换，被称为非线性特征转换（nonlinear feature transform）。

反过来，如果是线性可分的，是不是一定可以用圆来划分呢？答案是不一定的，因为不同的参数可能会形成不同的二次曲线，当然也有可能会让恒为正/负。

 那么我们如果要讨论更加一般的情况，特征转换为，这样就能够表示所有的二次曲线划分，当然也包括直线、常数点这些特殊情况。那么Z域中的hypothesis可以写成：

Nonlinear Transform

现在我们知道了如何将二次曲线划分hypothesis转化成线性划分hypothesis，那么如何设计一个好的二次hypothesis来达到良好的分类效果呢？

其实还是通过映射的方法，将X域中的二次多项式转换为Z域中的一次向量，这样就能用z值代替x的多项式，其中向量z的个数与x域中x多项式的个数一致（包含常数项）。这样在Z域中可利用线性分类模型进行分类训练。训练好的线性模型中，将z替换为x的多项式就可以。

具体步骤如上图，其实就是一个变换后训练，训练后逆变换（代入）的过程。

于是通过下面两个关键点，就能像打开潘多拉魔盒一样，将非线性的问题用线性问题来解决。

• feature transform 特征转换
• linear model 线性模型A

而其实，我们之前也碰到过类似的方法，在笔记识别中，就是将raw原始数据转换成concrete具体特征，然后在进行训练，最后能将识别的raw图片成功分类，这是同样的transform思想。

Price of Nonlinear Transform

我们之前研究的是2阶d维的特征，它在Z域的特征维度有：

如果阶数上升为Q，那么Q阶transform多项式在Z域的特征维度就是：

由此可以看出，随着Q和d的增大，计算量会变得很大，空间复杂度也大。也就是说，这种特征变换的一个代价是计算的时间、空间复杂度都比较大。

从VC Dimension的角度来看，Z域的特征维度增大就会让的维度增大，也就是自由度增加，VC Dimension就会增大。可以证明的是，并且有，令Z域中的特征维度是，则在域中，任何的输入都不能被shattered；同样，在X域中，任何的输入也不能被shattered。也就是Q较大的时候，VC Dimension会比较大，模型的泛化能力会比较差。

 这个例子就告诉我们Q比较大时候的矛盾，的小，但是过拟合与相差较大，泛化能力倒不如。所以就需要一个合适的Q来确保模型的正确且泛化能力较好。采用什么方法呢？当然可以画图来人工视觉观测决定，但是我们往往不能在样本之外获得良好的效果。所以一般情况下还是要保存所有的多项式特征，避免人为选择。

Structured Hypothesis Sets

我们能看到随着阶数Q的增加，特征维度是不断增加的，变换多项式是包含了之前的多项式的——

于是，我们就能在不同阶次构成的hypothesis发现如下关系，这就是Structured Hypothesis Sets——

VC Dimension满足下列关系：

满足下列关系：

所以随着阶数Q的增大，就呈现了下图的样子（非常熟悉吧～）——

 这其实也就是说明了我们在上一节最后的问题，Q不能选得太大，那样会让也非常大。

所以一个安全的方法就是从开始尝试，呈现出两种结果——

• 就已经很好了，那当然就可以收工了
• 否则的话，就继续增大Q，让曲线向右移动，这样总能找到一个合适的Q（大不了多浪费一点计算）

通过不断增加Q寻找最优的方法，我们能够安全地得到理想的结果。而不是一味地追求复杂模型，简单模型反而能得到好的结果。