[林轩田]12-非线性变换

[TOC]

二次方程的hypothesis

对于非线性的数据分类，如果我们使用线性模型，就会使得Ein很大，分得不好。

Paste_Image.png

对称中心在原点的二次方程

现在我们考虑如何用二次方程（圆的方式）来进行separate: 我们可以使用半径平方为0.6的圆可以将它分开。

Paste_Image.png

这里我们进行非线性的变换，实现坐标系的变换。从x空间变到z空间。在x系里面圆圈可分的情况在z系里面变得线性可分了。在x系里面可以用圆分开则在z系里面一定可以线性可分。

但是在z空间里面可以用直线分开的情形，在x空间里面就可能是圆、椭圆、双曲线等情况，所以说在z空间里面的直线在x空间里面对应的是特殊二次曲线(圆心在坐标原点)，三个参数。

Paste_Image.png

一般情形的二次式

把所有的二次项、所有的一次项和常数项都要包含进来，这样在Z空间里面的直线对应x空间的二次hypothesis
这个权值W需要6个参数

Paste_Image.png

所以我们如果能够在z空间里面找到好的线性分割，就能在x空间里找到好的二次曲线分割。

Paste_Image.png

非线性变换

空间变换

首先把原始在x空间的数据变换到z空间的数据。
在z空间中得到好的线性感知机。
在z空间对得到的模型g进行反变换得到x空间应该有的二次曲线模型。

而实际上第三步并不是取逆变换，而是考察一个点在x空间的分类的时候，把这个点先转换到z空间，然后看它是哪个分类，我们就知道它在x空间里面应该是哪个分类了。

Paste_Image.png

非线性变换的代价

之前从原始特征用领域知识变换到具体特征就是这样。

z空间的维度

从d维度特征的二次x空间转化为一次z空间是多少个维度。

Paste_Image.png

z空间的计算和存储代价

d维Q次特征空间转化到1次空间时的特征维度是 $$ C_{Q+d}^{d} $$

Paste_Image.png

证明：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} $$

应该选择怎样的模型。