飞道的博客

机器学习基石12：非线性变换（Nonlinear Transformation）

2020-04-19 06:57 418人阅读  评论(0)

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

文章目录

12. Nonlinear Transformation

12.1 Quadratic Hypotheses

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

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


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

h S E P ( x ) = s i g n ( − x 1 2 − x 2 2 + 0.6 ) (12-01) h_{SEP}(x) = sign(−x^2_1−x^2_2+0.6) \tag{12-01}

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


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

原公式中， h ( x ) h(x) 的权重为 w 0 = 0.6 w_0 = 0.6 ， w 1 = − 1 w_1 = -1 ， w 2 = − 1 w_2 = -1 ，但是 h ( x ) h(x) 的特征不是线性模型的 ( 1 , x 1 , x 2 ) (1,x_1,x_2) ，而是 ( x , x 1 2 , x 2 2 ) (x,x^2_1,x^2_2) 。通过令 z 0 = 1 , z 1 = x 1 2 , z 2 = x 2 2 z_0 = 1, z_1 = x^2_1, z_2 = x^2_2 ， h ( x ) h(x) 可以变成上式。

这种 x n → z n x_n \rightarrow z_n 的变换可以看作将 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为：

上式中， h ~ \widetilde{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 ) } \{(x_n,y_n)\} ， Z Z 空间的数据集为 { ( z n = Φ 2 ( x n ) , y n ) } \{(z_n= \Phi_2(x_n),y_n)\} ；
  • 通过特征变换函数 Φ \Phi 将 X X 空间中线性不可分的数据集 { ( x n , y n ) } \{(x_n,y_n)\} 变换为 Z Z 空间中线性可分的数据集 { ( z n = Φ 2 ( x n ) , y n ) } \{(z_n= \Phi_2(x_n),y_n)\} ；
  • 使用线性分类算法和 Z Z 空间的数据集 { ( z n , y n ) } \{(z_n,y_n)\} 获得表现良好的感知器模型 （最优权重向量） w ~ \widetilde{w} ；
  • 最后得到最优的假设函数 g ( x ) = ( w ~ T   Φ ( x ) ) g(x) = (\widetilde{w}^T \ \Phi(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 空间的特征维度为：

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

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

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

d ˘ = C Q + d Q + C Q + d d = O ( Q d ) \breve{d} = C^Q_{Q+d} + C^d_{Q+d} = O(Q^d)

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


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

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

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

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

Φ 2 ( x ) = ( Φ 1 ( x ) , x 1 2 , x 1 x 2 , . . . , x d 2 ) Φ2(x) = (Φ_1(x), x^2_1,x1x2, . . . ,x^2_d)

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

Φ Q ( x ) = ( Φ Q − 1 ( x ) , x 1 Q , x 1 Q − 1 x 2 , . . . , x d Q ) Φ_Q(x) = (Φ_{Q−1}(x), x^Q_1,x^{Q−1}_1x2, . . . ,x^Q_d)

这种结构称为 Structured Hypothesis Sets：

对于这种 Structured Hypothesis Sets ，VC-Dimention 和 E i n E_{in} 满足如下关系：

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

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

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

习题4：

summary

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

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

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

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


转载：https://blog.csdn.net/weixin_39653948/article/details/105584730
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场