林轩田《机器学习基石》（十二）—— Nonlinear Transformation

上一节讲的三个模型：线性分类、线性回归，logistics回归问题都是线性的方式：用w计算一个分数。今天要讲的是nolinear 非线性的方式去做分类。

一、二次hypothesis

对于线性的假设，二元分类问题中，首先从视觉上是用把资料用一条线切割。数学上来讲就是用我们输入的特征x计算一个分数：

另一方面，我们会遇到某些资料无法用线切割，不管用哪一条线切割都会很大。今天我们研究的是，如何突破线性的限制：不用“线”的方式，用其他方式也可以做到分类。

1.资料D不是线性可分的。

2.用一个圆圈可以将资料分开。圆形内部是正类，外面是负类。

这个虽然不是线性可分，但是确实圆圈可分，划分它的h可以写成： 

我们可以进一步研究circle-PLA、circle-Regression等问题，如何设计这些算法。

首先作如下变换：

会发现我们这样相当于把原来点x的空间转化到了z空间：.，这个过程称之为特征转换（Feature Transform）图中也显示了变换后的点的位置。从而只要我们找到，就可以把z空间用一条直线分开。

→→→→→

现在我们知道了，如果在x空间里面的资料x能用一个圆圈分开，那么经过某个变换后到z空间，新资料z可以用一条线分开。

那么反之是否成立呢？（不成立，下面解释）

比如我们先知道z空间资料是线性可分的，z是由x特征变换而来的：

在z空间的hypothesis为：

现在我们讨论的取值对上述问题的影响（红字部分）。

•  (0.6, -1, -1) ：x空间的资料用一个圆可以分开，圆圈内部是‘o’正类点
•  (-0.6, +1, +1) ：x空间的资料用一个圆可以分开，圆圈内部是‘×’负类点
•  (0.6, -1, -2) ：x空间的资料用一个椭圆可以分开，椭圆内部是‘o’正类点
•  (0.6, -1, +2) ：x空间的资料用一个双曲线可以分开
• (0.6, +1, +2) ：x空间的资料总被分类为‘o’正类点

虽然反过来我们并不能说x空间一定会被圆圈划分， 但是我们可以说他一定可以被某个特定的二次曲线划分。

上面的x空间中的二次曲线都是圆心过原点的，我们希望包含所有的一般情况（比如圆心不过原点），于是添加了二次项、一次项和常数项1：

举例：

x空间：

的系数分别为33，-20，-4, 3, 2, 3。

因此后，

这样，在z空间的一条线就对应于x空间中的某个二次曲线：

z空间中的hypothesis可以写成：

二、如何学到一个好的二次hypothesis

那么如何设计一个好的二次hypothesis来达到良好的分类效果。

由上面一节我们可以把目标变为：在z空间中设计一个最佳的分类线。

已知：资料，以及使用资料在x空间找到好的曲线

所以我们要做的事情就是：使用z空间的资料来找到一个最佳分类线，获得z空间资料的方法是对x空间中的资料做特征变换。

步骤：

1.先把x空间的资料转化到z空间

2.用一个算法A在z空间中找到一条好的线（也就是找到w）

3.做一个类似反变换的事情，z空间中的点已经被很好分类了，那么返回去x空间中的点也会有对应的分类。但是现在我们不是从z空间再做反变换到x空间，我们是依旧做x到z的变换，某个资料x的类别是它在z空间中的对应点的标签。

过程流程图：

上述过程其中有两件事，需要我们选择：

• 特征变换：转换到什么样的z空间
• 算法A的选择：PLA？logistics回归？线性回归？

其实整个思想就是把原来的资料变换一个空间做线性分类。

现在我们学会了上面的问题，也就是学会了二次PLA，二次logistics回归，二次线性回归等。

之前在讲处理原始资料（图像）时候讲过一个特征变换的例子：

比如数字识别问题，原始的像素值特征转换为一些实际的具体特征，比如密度、对称性等等，这就从原来的灰度图变成了二维的向量。

写出一个新的数字依旧可以做出这两个具体特征，然后可以得到一个类别，这就是新数字的类别。

当然做这种特征变换会产生一些代价，下节将具体介绍。

三、特征变换会产生一些代价

首先我们介绍，如果我们把上面的二次扩展成多次的特征变换。

二次的特征变换写完整是

Q次的特征变换里面项全写出来则是（我们假设x特征维度是d维的，也就是包含d个特征）：

计算中具体有多少个分量（也就是z空间有多少个特征维度）：

(1是指‘第一项常数1’，是其他项)

我们先来分析一下，由于是Q次的，所以从这些里面选择小于等于Q个项。计算有多少种取法，

排列组合知识：从n个元素中取m个（可重复取）的组合为C(n+m-1,m)

现在是对于0次是只有一种取法，

对于1次项来说，是从d个元素里面选1一个：C(d+1-1,1)

对于二次项来说是从d个里面选两个：C(d+2-1,2)

....

对于q次项来说是从d个元素里取q个：C(d+q-1,q)

一直到最大次数Q，所以一共有

又因为排列组合知识：

所以一共有

（下面图里第一个不等式就解释清楚了）

排列组合知识：（下面第二个等式的原因），所以有

计算z空间特征维度个数的时间复杂度是Q的d次方，随着Q和d的增大，计算量会变得很大。

同时，空间复杂度也大，因为要把z空间中的权重也全部储存起来（权重的维度=z空间的维度）。

综上在计算和储存上都要花较大的力气，这种特征变换的一个代价是计算的时间、空间复杂度都比较大。

由于

很显然的一件事是：

自由度：

z空间中的特征维度是，则在z空间中，任何的输入都不能被shattered。（之前证过）

那么同样的任何的输入在x空间都不能被shattered，否则一定可以找到z空间中对应的系数，使得z空间中的某个的输入都被shattered。因此，对VC Dimension产生限制。

与Q是相关的，因此Q变大时候，VC Dimension也会变大。

那因此会带来一些什么坏事呢？

如下是对同一个资料的两种分类方式。哪一个比较好？

左边：视觉上来说符合我们对资料的认知

右边：虽然为0，但是好像学习的太过头了

这就又回到我们最初提的“两个问题”，1.和接近吗？2.够小吗？

我们权衡一下大的时候，1不好 2好；小的时候，1好 2不好。

于是又到了我们抉择的时候了，如何选择Q呢？用眼睛决定吗？（肯定不可能，要是高维空间中一般视觉上不容易决定）

那低维空间d=2，结果会好吗？实际上，用眼睛决定可能会有一些潜在问题：

1.  ，

2.如果我们不用全部，只用其中三个，，

3.如果我们考虑反正是一个圆，更好的话，只用其中两个，，

4.或者我站在“上帝角度”直接给出可以吗？这样仿佛只用付出的代价

但这是human learning不是machine learning，机器会受到你主观的影响。这样实际的代价其实会包含在你人脑中所做的代价。这样导致看起来VC维很小，实际上并不是。所以，不要让你的决策进入你的机器学习中。

四、hypothesis set的结构

我们讨论，从x空间到z空间的变换，0次的变换:

1次的变换=0次的变换+新的变换：

2次的变换=1次的变换+新的变换：

3次的变换=2次的变换+新的变换：

Q次的变换=Q-1次的变换+新的变换：

可以看到我们的每一个变换都包含了前一个变换，hypothesis角度则是

、

上面的被称为hypothesis set的结构，上面的结构告诉我们

1.vc维其实告诉我们的就是可以shatter多少个点，所以比shatter的点多。

2.我们对每个hypothesis找到了最好的（也就是最小的），那么这些的关系如上图：因为hypothesis越来越多，他的选择也增多了，你可能会在新增的这些hypothesis里找到更小的。

可以用下面的图表示：

越来越小，in-sample error曲线一直下降；

vc维越来越大，model complexity曲线就上升；

所以造成先下后上。

直接选择这些很高维的hypothesis set是很危险的。

安全的做法：从低维度开始做起，

如果已经很小，那我们开心地就选择。

如果不够小，继续往右边移动。

也就是说：不要一开始就试很复杂的转换，从简单的开始，通常我们会发现其实低维度的做的还不错（甚至有时候线性都很好）。

总结：