林轩田机器学习基石课程个人笔记-第十二讲

在前面学习的算法基本上都是用于线性分类或是线性回归，所用的数据集基本上也是线性可分的。但是在实际中这种理想的情况是大概率不存在的，也就是说我们的问题是线性不可分问题，这时应该怎么处理呢？这就是下面学习的内容

举例来说，如下所示：如果数据集是线性可分的，意味着我们可以找到一条线较好的将不同的部分进行区分，数学上来说就是可以求出一个矩阵W来得到S；如果数据集是线性不可分的，那么很难找到一条直线进行很好的划分吗，这dvc是很难控制的，选择的划分直线的Ein也会特别的大。那么如何解决这种非线性可分的问题呢?

比如有如下的数据集可视化如图所示，很明显数据集属于线性不可分，无法找到一条很合适的直线将其进行一个划分。但是如果用一个圆心在原点，半径为根号下0.6为半径的圆来划分，结果会很好，它的h如图所示。这就给了一个启发：可以经过一些变换来得到想要的结果。基于这种非线性思想，我们之前讨论的PLA、Regression问题都可以有非线性的形式进行求解

我们将上面的表达式做一下代换和整理，经过处理又回到了熟悉的形式。现在形式相似，但是元素不同了，这就意味了数据的形式也发生了变化

这种的转换可以看成是一种元素空间的转换，即把x空间的点映射到z空间中去，而在z域中，数据是线性可分的，即从x空间的圆形可分映射到z空间的线性可分，z域中的直线对应于x域中的圆形。将这种变换称之为特征转换（Feature Transform）。通过这种特征转换，可以将本来非线性可分的问题，经过转换为另一个域，将其变成线性可分的，其中不同域之间的这个映射的规则起到很重要的作用。

那么如果在X域中圆形可分，对应的Z域中线性可分，反过来说是否成立呢？答案是不一定！因为在映射过程中当W的值取的不同时，映射到X域中就不一定是圆了，可能是椭圆、双曲线等其他的情况

但总体上我们可以这样说：如果在Z域中是线性可分的，那么在X域中有一个特殊的曲线与之对应，可以较好的划分数据集

如果z域含有更多的项时，那么z域中每一条线对应x域中的某二次曲线的分类方式，也许是圆，也许是椭圆，也许是双曲线等等。那么z域中的hypothesis可以写成如下的形式

经过上面的学习，我们知道了存在如下的规则对应

那么在此基础上，很多问题的需要在Z域中找到一个很好的分类线

利用映射变换的思想，通过映射关系，把x域中的最高阶二次的多项式转换为z域中的一次向量，也就是从quardratic hypothesis转换成了perceptrons问题。用z值代替x多项式，其中向量z的个数与x域中x多项式的个数一致（包含常数项）。这样就可以在z域中利用线性分类模型进行分类训练。训练好的线性模型之后，再将z替换为x的多项式。简单的分为如下几步：
• 通过某种映射规则进行数据集的转换
• 在转换后的数据集上，选择你想要用的算法来得到一个很好的perceptron
• 多项式的变换
具体过程如下：

其中就涉及到两个很重要的部分：映射规则的选择和学习算法的选择（这里不仅限于二分类算法）

这样来看好像很多问题就很好解决了，但现实真的是这么简单吗？上面提到的很多都是在一维或是二维情况下的问题，如果维数很高时，比如下面的情况

这时映射规则中的项就很多，很难直观上找到一个规则。当x特征维度是2维的，那么它的二次多项式中的元素就有6个；当x特征维度是d维的，也就是包含d个特征，那么二次多项式个数，即z域特征维度是d(d+3)/2 + 1。如果阶数更高，假设阶数为Q，那么对于x特征维度是d维的，它的z域特征维度为O(Q^d)

由分析可得，如果我们的Q和d很大时，计算量会变得很大，空间复杂度也大，同时存储耗费也会很大。

从VC Dimension的角度来看，当Q和d都很大时，*度就会很大，而*大时模型的泛化能力就会下降。

所以在实际中要做一个权衡，比如一个模型效果很好但各种复杂度都高，而另一个模型虽然效果差一点，但是复杂度很低时，改如何选择？例如下面的例子，左面是选了一条直线，对应的计算量是很小的，但是有一些点分错了；而右边的都分对了，但是分隔线都是各种曲线。那么哪一个分类效果好呢？单从平面上这些训练数据来看，右面的分类效果更好，但是很容易带来过拟合的问题，虽然它的Ein比较小，从泛化能力上来说，还是左边的分类器更好一些

那么如何选择合适的Q，来保证不会出现过拟合问题，使模型的泛化能力强呢？一般情况下，为了尽量减少特征*度，我们会根据训练样本的分布情况，人为地减少、省略一些项。但是，这种人为地删减特征会带来一些“自我分析”代价，虽然对训练样本分类效果好，但是对训练样本外的样本，不一定效果好。所以，一般情况下，还是要保存所有的多项式特征，避免对训练样本的人为选择。

下面再看一下映射的规则，我们可以将其看成是一种递归的定义方式，即后面的表达式包含前面的部分

用集合来看就如下图所示，称之为Structured Hypothesis Sets：

有如上结构时，它们的dvc和Ein就满足如下的形式：当结构越复杂时，dvc自然就会越来越大，但是也更有机会找到更小的Ein

但是是不是我们的模型阶数越高，得到的效果约好呢？，从下面的图中可以看出，随着变换多项式的阶数dvc增大，虽然Ein逐渐减小，但是model complexity会逐渐增大，导致Eout也很大，所以不是阶数越高越好

那么，如果选择的阶数很大，确实能使Ein接近于0，但是模型的泛化能力通常很差，各种复杂度也很大，我们把这种情况叫做tempting sin。故一般最合适的做法是先从低阶开始，如先选择一阶hypothesis，看看是否很小，如果足够小的话就没必要使用更复杂的模型了；如果这时的Ein还是很大的话，可以再逐渐增加阶数，直到满足要求为止。即尽量选择低阶的hypothes来解决问题，就不要给自己增加难度

最后总结一下，这一讲学习到了如何来处理非线性可分的相关问题，以及过程中要注意的一些问题。