本文介绍了非线性变换的整体流程：通过非线性变换，将非线性模型映射到另一个空间，转换为线性模型，再来进行线性分类。
之后介绍了非线性变换存在的问题：时间复杂度和空间复杂度的增加。
最后证明了非线性变换的一般做法：尽可能使用简单的模型，而不是模型越复杂越好。

---

---

12. Nonlinear Transformation

12.1 Quadratic Hypotheses

在之前的章节中，学习的机器学习模型都为线性模型，即假设空间都为线性的（2D平面中为一条直线，3D空间为一个平面），使用的得分为线性得分（linear scores） $s=w^Tx$s=wTx。其中，$x$x 为特征值向量，$w$w 为权重。

线性模型的优点是理论上可以使用VC限制进行约束（假设是非线性的各种曲线或者超平面，则每种假设都可以完全二分，即有 $2^N$2N 种二分类。），这保证了 $E_{in} \approx E_{out}$Ein​≈Eout​（VC-Dimension比较小）。但是对于线性不可分（non-linear separable）的问题（如下图）， $E_{in}$Ein​ 很大，从而导致 $E_{out}$Eout​ 也很大，导致分类结果不理想。

为了解决线性模型的缺点，我们可以使用非线性模型来进行分类。基于这种非线性思想，之前讨论的PLA、Regression问题也可以通过非线性的形式进行求解。例如可以使用一个半径为 $\sqrt{0.6}$0.6​ 圆心在原点的圆划分，它的hypotheses可以写成：

$h_{SEP}(x) = sign(−x^2_1−x^2_2+0.6) \tag{12-01}$hSEP​(x)=sign(−x12​−x22​+0.6)(12-01)

该公式的含义为将样本点到原点距离的平方与数值0.6作比较，圆形将样本集分离，圆形内部是正类，标记为+1，外部是负类，标记为-1，此种方式称作圆形可分（circular separable）。如下图所示：

将公式（12-01）做如下转换，变为熟悉的线性模型：

原公式中，$h(x)$h(x) 的权重为 $w_0 = 0.6$w0​=0.6， $w_1 = -1$w1​=−1，$w_2 = -1$w2​=−1，但是 $h(x)$h(x) 的特征不是线性模型的 $(1,x_1,x_2)$(1,x1​,x2​)，而是 $(x,x^2_1,x^2_2)$(x,x12​,x22​)。通过令 $z_0 = 1, z_1 = x^2_1, z_2 = x^2_2$z0​=1,z1​=x12​,z2​=x22​，$h(x)$h(x) 可以变成上式。

这种 $x_n \rightarrow z_n$xn​→zn​ 的变换可以看作将 $X$X 空间中的点映射到 $Z$Z 空间中去，即从 $X$X 空间的圆形可分映射到 $Z$Z 空间的线性可分。$Z$Z 域中的直线对应于 $X$X 域中的圆形。其背后的思想是通过非线性的特征变换 $\Phi$Φ（feature transform） 将圆形可分（非线性可分）变为线性可分。

那么问题来了，已知在 $X$X 域中圆形可分，在 $Z$Z 域中线性可分；反过来，如果在 $Z$Z 域中线性可分，是否在 $X$X 域中一定圆形可分呢？

答案是否定的。由于权重向量 $w$w 取值不同，$X$X 域中的hypothesis可能是圆形、椭圆、双曲线等等多种情况。

通过这种形式转换的 $Z$Z 空间的直线对应着原 $X$X 空间中特殊的二次曲线（quadratic curves）。说“特殊”是因为表示的圆只能是圆心过原点的圆，不能随意表示各种情况的圆。如果想要表示 $X$X 空间中所有的二次曲面，应设计一个更大的 $Z$Z 空间，其特征转换如公式为：

通过以上特征转换，$Z$Z 空间中的每个超平面就对应 $X$X 空间中各种不同情况的二次曲线（圆、椭圆、双曲线）。则 $X$X 空间中的假设空间H为：

上式中，$\widetilde{h}$h 表示 $Z$Z 空间中的假设函数。

---

习题01：

---

12.2 Nonlinear Transform

从 $X$X 空间转换到 $Z$Z 空间，则在Z空间中获得的好的线性假设函数，相当于在X空间中获得了好的二次假设函数，即在 $Z$Z 空间中存在线性可分的直线对应于在 $X$X 中（非线性）可分的二次曲线。目标就是在 $Z$Z 空间中找到一个最佳的分类线（假设函数）。

利用映射变换的思想，通过映射关系，把 $X$X 空间中的最高阶二次的多项式转换为 $Z$Z 空间中的一次向量 z，即从二次假设转换成了感知器问题。用 z 值代替 x 多项式，其中向量 z 的个数与 $X$X 空间中 x 的多项式的个数相同（包含常数项）。这样就可以在 $Z$Z 域中利用线性分类器进行训练。训练好之后，再将 z 替换为 x 的多项式即可（反变换）。具体过程如下：

• $X$X 空间中的数据为 $\{(x_n,y_n)\}${(xn​,yn​)}，$Z$Z 空间的数据集为 $\{(z_n= \Phi_2(x_n),y_n)\}${(zn​=Φ2​(xn​),yn​)}；
• 通过特征变换函数 $\Phi$Φ 将 $X$X 空间中线性不可分的数据集 $\{(x_n,y_n)\}${(xn​,yn​)} 变换为 $Z$Z 空间中线性可分的数据集 $\{(z_n= \Phi_2(x_n),y_n)\}${(zn​=Φ2​(xn​),yn​)} ；
• 使用线性分类算法和 $Z$Z 空间的数据集 $\{(z_n,y_n)\}${(zn​,yn​)} 获得表现良好的感知器模型 （最优权重向量） $\widetilde{w}$w；
• 最后得到最优的假设函数 $g(x) = (\widetilde{w}^T \ \Phi(x))$g(x)=(wT Φ(x))。

上图中，最下边两幅图表达了该思路的核心思想。判断某个样本属于哪个类别，只需要将 $X$X 空间中的数据变换到 $Z$Z 空间；然后使用 $Z$Z 空间中的假设函数（线性分类器）对样本进行分类；最后反变换到 $X$X 空间，得到真实类别。

这类模型由两部分构成：

• 非线性变换函数 $\Phi$Φ ：通过特征变换，将非线性可分问题转换为线性可分问题；
• 线性模型：包括之前学习的二分类、线性回归和Logistic回归等；

使用以上求解非线性分类的思路可以解决二次PLA，二次回归，三次回归，…，多项式回归等多种问题。

特征变换（feature transform） 的思想非常常见，比如我们熟知的手写数字识别任务中，从原始的像素值特征转换为具体的特征，比如密度、对称性等：

习题2：

---

12.3 Price of Nonlinear Transform

如果 $X$X 的特征维度为 $d$d 维，也就是包含 $d$d 个特征，那么二次多项式个数，即 $Z$Z 空间的特征维度为：

$\breve{d} = 1 + C^1_d + C^2_d + d = \frac {d(d+3)}{2} + 1$d˘=1+Cd1​+Cd2​+d=2d(d+3)​+1

如果 $X$X 特征维度是2维的，即 $(x_1, x_2)$(x1​,x2​)，那么它的的二次多项式为 $(1, x_1, x_2, x^2_1, x_1x_2, x^2_2)$(1,x1​,x2​,x12​,x1​x2​,x22​)，有六项。

如果阶数为 $Q$Q ， $X$X 空间的特征维度为 d 维，则它的 $Z$Z 空间特征维度为：

$\breve{d} = C^Q_{Q+d} + C^d_{Q+d} = O(Q^d)$d˘=CQ+dQ​+CQ+dd​=O(Qd)

由上式可以看出，计算 $Z$Z 空间特征维度个数的时间复杂度是 $Q$Q 的 $d$d 次方，随着 $Q$Q 和 $d$d 的增大，计算量变大；空间复杂度也大。

特征转换还带来另一个问题。在前面的章节中讲述过，模型参数的自由度大概是该模型的VC维度。z域中特征个数随着Q和d增加变得很大，同时权重w也会增大，即自由度增加，VC-Dimension 增大。令z域中的特征维度为 $\breve{d} + 1$d˘+1 ，在 $Z$Z 域中，任何 $\breve{d} + 2$d˘+2 的输入都不能被 shattered，同样，在 $X$X 域中，任何 $\breve{d} + 2$d˘+2 的输入也不能被 shattered；$\breve{d} + 1$d˘+1 是 VC-Dimension 的上界，如果 $\breve{d} + 1$d˘+1 很大，相应的 VC-Dimension 也会很大。根据之前章节课程的讨论，VC-Dimenslon 过大，模型的泛化能力会比较差。

下例解释了 VC-Dimension 过大，导致分类效果不佳的原因：

上图中，左边用直线进行线性分类，有部分点分类错误；右边用四次曲线进行非线性分类，所有点都分类正确，那么哪一个分类效果好呢？单从平面上这些训练数据来看，四次曲线的分类效果更好，但是四次曲线模型很容易带来过拟合的问题，虽然它的 $E_{in}$Ein​ 比较小；泛化能力上，左边的分类器更好。也就是说，VC-Dimension 过大会带来过拟合问题，$\breve{d} + 1$d˘+1 不能过大。

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

---

习题3：

---

12.4 Structured Hypothesis Sets

下面讨论 $X$X 空间到 $X$X 空间的多项式变换。

如果特征维度是一维的，变换多项式只有常数项：

$Φ_0(x) =(1)$Φ0​(x)=(1)

如果特征维度是两维的，变换多项式包含了一维的 $Φ_0(x)$Φ0​(x)：

$Φ_1(x) = (Φ_0(x), x_1,x_2, . . . ,x_d)$Φ1​(x)=(Φ0​(x),x1​,x2​,...,xd​)

如果特征维度是三维的，变换多项式包含了二维的 $Φ_1(x)$Φ1​(x)：

$Φ2(x) = (Φ_1(x), x^2_1,x1x2, . . . ,x^2_d)$Φ2(x)=(Φ1​(x),x12​,x1x2,...,xd2​)

以此类推，如果特征维度是Q维的，则它的变换多项式为：

$Φ_Q(x) = (Φ_{Q−1}(x), x^Q_1,x^{Q−1}_1x2, . . . ,x^Q_d)$ΦQ​(x)=(ΦQ−1​(x),x1Q​,x1Q−1​x2,...,xdQ​)

这种结构称为 Structured Hypothesis Sets：

对于这种 Structured Hypothesis Sets ，VC-Dimention 和 $E_{in}$Ein​ 满足如下关系：

VC-Dimention 与错误率之间的关系如下：

由上图易知，随着变换多项式的阶数增大，虽然 $E_{in}$Ein​ 逐渐减小，但模型复杂度会逐渐增大，造成 $E_{out}$Eout​ 很大，所以阶数不能太高。

如果选择的阶数很大，能使 $E_{in} \approx 0$Ein​≈0 ，但泛化能力很差，这种情况叫做tempting sin。所以，一般做法是先从低阶开始，如先选择一阶假设，看看$E_{in}$Ein​ 是否很小，如果 $E_{in}$Ein​ 足够小就选择一阶，如果很大就逐渐增加阶数，直到满足要求为止。也就是说，尽量选择低阶的假设，这样才能得到泛化能力较强的模型。

---

习题4：

---

summary

本节课介绍了非线性变换的整体流程（通过非线性变换，将非线性模型映射到另一个空间，转换为线性模型，再来进行线性分类。

之后介绍了非线性变换存在的问题：时间复杂度和空间复杂度的增加。

最后介绍了在付出代价的情况下，使用非线性变换的最安全做法：尽可能使用简单的模型，而不是模型越复杂越好。

---

参考：
https://www.cnblogs.com/ymingjingr/p/4306666.html
https://github.com/RedstoneWill/HsuanTienLin_MachineLearning