[林轩田]12-非线性变换
[TOC]
二次方程的hypothesis
对于非线性的数据分类，如果我们使用线性模型，就会使得Ein很大，分得不好。
对称中心在原点的二次方程
现在我们考虑如何用二次方程（圆的方式）来进行separate: 我们可以使用半径平方为0.6的圆可以将它分开 。
这里我们进行非线性的变换，实现坐标系的变换。从x空间变到z空间。在x系里面圆圈可分的情况在z系里面变得线性可分了。在x系里面可以用圆分开则在z系里面一定可以线性可分。
但是在z空间里面可以用直线分开的情形，在x空间里面就可能是圆、椭圆、双曲线等情况，所以说在z空间里面的直线在x空间里面对应的是特殊二次曲线(圆心在坐标原点)，三个参数。
一般情形的二次式
把所有的二次项、所有的一次项和常数项都要包含进来，这样在Z空间里面的直线对应x空间的二次hypothesis
这个权值W需要6个参数
所以我们如果能够在z空间里面找到好的线性分割，就能在x空间里找到好的二次曲线分割。
非线性变换
空间变换
- 首先把原始在x空间的数据变换到z空间的数据。
- 在z空间中得到好的线性感知机。
- 在z空间对得到的模型g进行反变换得到x空间应该有的二次曲线模型。
而实际上第三步并不是取逆变换，而是考察一个点在x空间的分类的时候，把这个点先转换到z空间，然后看它是哪个分类，我们就知道它在x空间里面应该是哪个分类了。
非线性变换的代价
之前从原始特征用领域知识变换到具体特征就是这样。
z空间的维度
从d维度特征的二次x空间转化为一次z空间是多少个维度。
z空间的计算和存储代价
d维Q次特征空间转化到1次空间时的特征维度是 $$ C_{Q+d}^{d} $$
证明：d维Q次特征空间转化到1次空间时的特征维度是$$ C_{Q+d}^{d} $$
可以把问题转化为求d个变量组成的Q次多线程里面，各种子项总共有多少个。转化为相同的问题就是：
把k个相同的物体分给d个人，不一定每个人都分到，也不一定分完，问有多少种分法？
那么这个问题是比较复杂的，我们高中的时候学的问题是下面这个类型的：
问题1. 把k个相同物体分给d个人，每人最少1个，要求分完，那么有几种分法？
设第i个人分得$$ x_i $$个物体，则$$ 0 < x_i < k $$ 用我们熟悉的插板法，在k-1个间隙里面插入d-1个板（分成d份），分法有
$$ C_{(k-1)}^{(d-1)} $$
问题2. 把k个相同的物体分给d个人，不一定每个人都分到，但物体必须分完，问有多少种分法？
设第i个人分得$$ x_i $$个物体，则$$ 0\leqslant x_i \leqslant k $$，我们可以把它转化一下
$$ x_1+x_2+...+x_d = k \rightleftharpoons (x_1+1)+(x_2+1)+(x_3+1)+...+(x_d+1) = k+d $$
$$ 0\leqslant x_i \leqslant k \rightleftharpoons 1 \leqslant x_i+1 \leqslant k+1 $$
可以认为把k+d个物体分给d个人，使用插板法 结果为
$$ C_{k+d-1}^{d-1} $$
到这里我们就可以把我们的问题转化为这里面相同的问题了，不分完可以理解为还有一个潜在的第k+1个人，把最后剩下的物体分给它。所以这个问题就转化为 把k个物体分给d+1个人，不一定每个人都分到，但物体必须分完。也转化为把k+d+1个物体分给d+1个人，每人必须分到，物体必须分完，所以结果为 $$ C_{k+d}^{d} $$
应该选择怎样的模型。
模型越复杂 $$ E_{in} $$越小,如果你选择的模型的维度比较高，会使得$$ E_{in} $$ 会使得 $$E_{out} / E_{in}$$ 差别会很远
