机器学习笔记-Nonlinear Transformation

0 - 写在前面

本系列共四篇，为林轩田机器学习基础篇学习笔记。主要内容可以总结概括为：线性模型通过非线性的变换可以得到非线性的模型，增强了模型对数据的拟合能力，但这样导致了在机器学习领域中一个很常见的问题，过拟合。为了解决这个问题引入了正则化因子(规则化因子)。而为了解决正则化因子的选择，模型的选择以及超参数的选择等问题引入了validation$validation$的相关方法。

• 机器学习笔记-Nonlinear Transformation$NonlinearTransformation$
• 机器学习笔记-Hazard of Overfitting$HazardofOverfitting$
• 机器学习笔记-Regularization$Regularization$
• 机器学习笔记-Validation$Validation$

1 - Quadratic Hypothesis

之前介绍的模型是线性的，将所有的特征做一个加权和。现在我们要将这些model$model$延伸成更复杂的方法， 使用非线性的方式来做数据的分类。

线性分类器：模型是参数的线性函数，并且存在线性分类面，那么就是线性分类器。
logistic regression$logisticregression$属于线性模型还是非线性模型？
属于线性模型，因为logistic regression$logisticregression$的决策边界是线性的。证明如下：

–知乎
或者可以简单的理解为逻辑斯蒂回归是将普通的线性模型的结果映射到一个(0， 1)的区间，然后划分一个界限(0.5)。
–知乎

线性模型的复杂度是受到控制的，这是线性模型的好处之一， 因为这样可以确保Ein$E_{in}$(训练集误差)和Eout$E_{out}$(测试集误差)不会相差太远。但是缺点就是对于如下左图中的样本点，任一个线性分类器都无法完美的划分×$\times$和◯$◯$。怎么突破线性模型的这个限制呢？也就是说，我们不再限制在使用“线”的方式，而是拓展一下使用其他的方式来解决这个二分类问题？

直观上来看， 如下的数据虽然不是线性可分的，但是是“圆圈”可分的。也就是说当使用函数：hsep(x)=sign(−x21−x22+0.6)$h_{sep}(x)=sign(-x_1^2-x_2^2+0.6)$时可以正确的划分 ×$\times$ 和 ◯$◯$ 。这个函数是一个以原点为中心r2=0.6$r^2=0.6$的圆。

本节的目的是探讨如何系统化的设计算法使得原来的线性模型可以用于非线性可分的数据的分类。因为我们之前已经学到了一些针对分类的方法，例如PLA$PLA$算法，pocket$pocket$算法，linear regression$linearregression$算法，logistic regression$logisticregression$算法，如何可以不更改这些算法本身而能应用于非线性可分的数据是我们关心的问题。

面对上图这样的数据，我们怎么可以得到一个“圆”形，而不再是一条线状的分类器呢？

对上面我们得到的分类函数hsep(x)$h_{sep}(x)$进行一些变量的重新定义和命名：

经过这样简单的重新命名我们发现线性的模型的形式又出现了，这样的“重命名”的过程其实是我们将所有的X$X$空间中的点通过多项式转换Φ$\mathrm{\Phi }$映射到了一个新的空间中， 我们称之为Z$Z$空间。其中Φ$\mathrm{\Phi }$

而式子（1）告诉我们在Z$Z$空间中可以通过线性的模型sign(wTx)$sign(w^{T}x)$正确的划分×$\times$和◯$◯$。线性模型我们在之前学过，这样我们面对的问题就变成了Z$Z$空间中可用线性模型解决的问题，只不过变量多了一点而已。
在得到了和w~$\tilde{w}$相关的一个线性分类器之后，再对应到X$X$空间，就得到了一个可以正确的划分×$\times$和◯$◯$的圆形的分类边界。这样我们就可以使用一个“圆”而不再是一条“线”对数据分类， 并且这个“圆”是使用线性模型做到的。

上述的那个重命名的过程，即数据从X$X$空间到Z$Z$空间的过程称为特征转换(feature transform$featuretransform$)。所以当经过这样的转换之后我们就可以在Z$Z$空间中使用我们熟悉的线性模型PLA$PLA$，pocket$pocket$，linear regression$linearregression$，logistic regression$logisticregression$来对数据进行分类。

(z0,z1,z2)=z=Φ(x)=(1,x21,x22)$(z_0,z_1,z_2)=z=\mathrm{\Phi }(x)=(1,x_1^2,x_2^2)$
h(x)=h~(z)=sign(w~TΦ(x))=sign(w0~+w1~x21+w0~x22)$h(x)=\tilde{h}(z)=sign({\tilde{w}}^T\mathrm{\Phi }(x))=sign(\widetilde{w_0}+\widetilde{w_1}{x}_1^2+\widetilde{w_0}{x}_2^2)$

如果在X$X$空间中可以使用“圆圈”划分数据， 在经过了转换之后，在Z$Z$空间中就线性划分。这是（1）式告诉我我们的。反过来呢？如果新的资料可以使用一条线划分开， 那么原来的资料一定可以使用圆划分开吗？通过下表可以看出，在Z$Z$空间中的不同的线，对应回Z$Z$空间可能是各式各样不同的曲线， 所以把这些线对应回来之后我们就知道在X$X$空间可以用哪些曲线来做不同的分类器， 有可能是正圆，椭圆，双曲线等等：

可以看到使用上面的特征转换得到了X$X$空间中的二次曲线分类器是有限制的，圆心是原点(0,0)$(0,0)$。进一步如果想要得到X$X$空间中所有的二次曲线分类器，那就需要重新定义上面更复杂一点的特征转换：Φ2(x)=(1,x1,x2,x1x2,x21,x22)${\mathrm{\Phi }}_2(x)=(1,x_1,x_2,x_1{x}_2,x_1^2,x_2^2)$，得到新的Z$Z$空间（6维），Z$Z$空间中的每一条直线，对应原来空间中的一个二次的曲线；原来X$X$空间中的任意二次曲线，也对应到Z$Z$空间中的一条直线。

所以我们现在有了对数据进行分类的新的思路或者是新的假设集：先把原始的数据（例如是二维的）通过某个特征转换（例如Φ2(x)${\mathrm{\Phi }}_2(x)$， 其中2$2$表示二次转换）映射到Z$Z$空间， 在Z$Z$空间中使用某个线性的模型得到线性的分类器h~$\tilde{h}$， 这样就可以得到在X$X$空间中任意形状的二次分类器。

举个例子：

例如在X$X$空间中需要一个如下的“斜椭圆”才能正确的划分数据：
2(x1+x2−3)2+(x1−x2−4)2=1$2(x_1+x_2-3{)}^2+(x_1-x_2-4{)}^2=1$。
现在看看是不是可以使用6$6$维的Z$Z$空间(1,x1,x2,x1x2,x21,x22)$(1,x_1,x_2,x_1{x}_2,x_1^2,x_2^2)$中的一条直线做到。经过配参数可以得到相对应的Z$Z$空间中的直线的参数为w=[33,−20,−4,3,2,3]$w=[33,-20,-4,3,2,3]$。所以Z$Z$空间中的每一条线，可以帮助我们实现某一个在X$X$空间中对应的分类方式。

这一小节的思想其实不难，不知道为什么我想说清楚却觉得很难。总结下：为了得到更复杂的分类器，不单单只是线性的，我们要做的就是进行特征转换，想要得到更复杂的分类器就进行更复杂的特征转换。在转换后的高维空间中使用线性模型对转换后的特征进行分类， 就可以得到对应于原始的空间中任意形状的分类器。

2 - Nonlinear Transform

现在我们已经得到，在上节中建立的6维的特征转化下，Z$Z$空间（6$6$维）中的所有的直线可以对应到X$X$空间（2$2$维）中的所有的二次曲线。（这里的X是二维空间， Z是六维的空间）。所以如果在Z$Z$空间中可以找到一个好的分隔线，那么就对应到在X$X$空间中的一个好的二次曲线。所谓好的分割线就是指能够正确划分×$\times$和◯$◯$的线。
所以我们现在的任务是在Z$Z$空间中找到一条好的“线”。目前我们会的是如何在X$X$空间中使用已知的数据{(xn,yn)}$\{(x_n,y_n)\}$得到一个好的分割线，所以我们只要将X$X$空间中的数据通过某个特征转换， 例如，Φ2(x1,x2)=(1,x1,x2,x1x2,x21,x22)${\mathrm{\Phi }}_2(x_1,x_2)=(1,x_1,x_2,x_1{x}_2,x_1^2,x_2^2)$映射到Z$Z$空间， 这样就可以使用任何的线性的二元分类方法在Z$Z$空间使用数据{(zn=Φ2(xn),yn)}$\{(z_n={\mathrm{\Phi }}_2(x_n),y_n)\}$来找一个好的分割线。

2.1 - 非线性转换的基本步骤

1. 将X$X$空间中的资料通过某一个转换Φ$\mathrm{\Phi }$映射到Z空间$Z空间$（高维空间），（左上图⟶$⟶$右上图）
2. 在Z$Z$空间中利用数据{(zn,yn)}$\{(z_n,y_n)\}$使用任何线性分类的算法A$A$得到一个好的分类器w~$\tilde{w}$。（右上图⟶$⟶$右下图）
3. 得到分类器g(x)=sign(w~T Φ(x))$g(x)=sign({\tilde{w}}^T\mathrm{\Phi }(x))$。当一个X$X$空间中的新的数据点要确定类别的时候，同样先对该数据点使用变换Φ$\mathrm{\Phi }$映射至Z$Z$空间，在Z$Z$空间中得到分类的结果。（左下图⟶$⟶$右下图）

2.2 - 非线性模型

非线性的转换 + 线性的模型 = 非线性的模型。

非线性的模型需要考虑的两个问题：

1. 使用什么样的特征转换，或者说转换到什么样的Z$Z$空间中；
2. 使用什么样的线性模型，或者说是使用什么算法。

所以当PLA$PLA$算法， pocket$pocket$算法，linear regression$linearregression$或者是logistic regression$logisticregression$算法配合一个二次的特征转换，就可以得到二次的PLA$PLA$算法， 二次的pocket$pocket$算法，二次的linear regression$linearregression$或者是二次的logistic regression$logisticregression$算法；当配合三次的特征转换就有了三次的PLA$PLA$算法，…$\dots$ 。也就是说只是换一个空间做linear learning$linearlearning$。

2.3 - 一个非线性模型的实例

在机器学习里面有一个很著名也是很基础的应用就是手写数字的识别。在这里我们考虑一种比较原始的方法来区分数字1$1$，即做一个二分类的问题：给定一个数字，判定是1$1$或者不是1$1$。
机器学习的feature$feature$分为两种， 一种是concrete$concrete$的，即有很丰富的物理意义；一种是raw$raw$，即原始收集来的数据。对于raw$raw$类型的资料，可以使用专业的知识变为concrete$concrete$。例如对于以上的问题，我们收集到的资料是像素级别的， 即每一个手写数字使用一个32×$\times$32的像素矩阵表示（是raw$raw$类型的）。我们可以通过对问题的认识（domain knowledge$domainknowledge$）从中提取特征。例如对于上述问题我们可以考虑对称性和密度：因为数字1$1$是比较对称的，数字1$1$的像素密度是比较低的。所以我们就将原来的32×$\times$32维的特征转换为了2维的特征：（对称性，密度）$（对称性，密度）$， 这就对应于一个特征转化Φ$\mathrm{\Phi }$。 从左上图⟶$⟶$右上图描述了这个过程, 每一张图片变为了二维空间中的一个点。此时的特征就是concrete$concrete$类型的。原来的32×$\times$32维的特征现在通过转换Φ$\mathrm{\Phi }$变为2维的， 所以可以使用线性的算法进行分类。（右上图⟶$⟶$ 右下图）。那么对于测试集中的数据（左下图），同样我们先提取它们的两个特征，密度和对称性$密度和对称性$，在这两个维度的空间中进行分类。

2.4 - A question

现在假设X空间中特征的维度不再是2$2$， 而是d$d$，现在在X空间中做二次转换Φ2${\mathrm{\Phi }}_2$，那么转换后的Z空间的维度是多少？

• 二次项的个数：Cd2+d$C_2^d+d$
• 一次项的个数：d$d$
• 常数项的个数：1$1$

Z$Z$空间的维度是：d22+3d2+1$\frac{d^2}{2}+\frac{3d}{2}+1$。

3 - Price of Nonlinear Transform

3.1 - Computation or Storage Price

接着上面提到的问题，原始的X$X$空间中特征的维度是d$d$，如果现在要做Q$Q$-次的多项式转换ΦQ(x)${\mathrm{\Phi }}_Q(x)$， 那么转换之后的空间的维度可以表示如下：

从d$d$个特征中找出所有低于Q$Q$次的组合，允许重复。所以Z$Z$空间的维度是O(Qd)$O(Q^d)$。例如原始的X$X$空间中的维度为2，特征转换为Φ50${\mathrm{\Phi }}_{50}$， 即经过一个50$50$次多项式的特征转换，那么经过计算可以得到新的Z$Z$空间的大小是1325维的。这其中就带来了一个重要的问题，你的数据量够不够支撑这个1000多维的空间， 在2维的空间中，可能20个样本就够了， 但是在一个1000维的空间中，20个样本是肯定不够的。

这需要付出很大的代价price$price$：

1. 进行特征转换的计算量是非常庞大的。每一个样本都要从d$d$维转换为O(Qd)$O(Q^d)$维。
2. 在使用线性的模型求解w$w$的时候， w$w$不再是d$d$个，而是O(Qd)$O(Q^d)$量级个。例如，linear regression$linearregression$中的解析解需要求解(1+d~)×(1+d~)$(1+\tilde{d})\times (1+\tilde{d})$维的矩阵的伪逆矩阵。
3. 储蓄上需要1+d~$1+\tilde{d}$的空间而不再是d$d$。

3.2 - Overfitting

如上图分别是使用原始的数据（经过Φ1${\mathrm{\Phi }}_1$转换）和经过特征转换（使用Φ4${\mathrm{\Phi }}_4$转换成四次多项式）的数据来进行分类的结果。虽然右图的Ein(g)=0$E_{in}(g)=0$，即在训练集上的误差为0， 但是我们认为左边的划分是更好的。

机器学习关心的两个核心问题：

1. 能不能确保Eout(g)$E_{out}(g)$和Ein(g)$E_{in}(g)$足够的接近（要求模型足够简单）

2. 能不能做到使得Ein(g)$E_{in}(g)$足够小（要求模型足够复杂）

当使用不同的假设函数–是2次的，还是4次的，对这两个核心问题的侧重是不一样的。当进行特征转换的时候，如果Q$Q$很大，即使用非常复杂的特征转换，此时问题2能够很好的解决，但是问题1不能得到保证；如果Q$Q$很小，即使用很简单的特征转换或者直接使用原始的数据来进行learning$learning$，此时问题1能够很好的解决，但是问题2不能得到保证。这是machine learning$machinelearning$中最重要的一个tradeoff$tradeoff$。

所以问题来了， 如何选择合适的特征转换Φ$\mathrm{\Phi }$？

4 - Structured Hypothesis Sets

4.1 - Polynomial Transform

对多项式特征变换给一个“递归”的定义：
以下分别给出的是0$0$维的变换，1$1$维的变换…

即：

所以可以得到如下的关系， 其中H$H$表示的是Hypothesis set$Hypothesisset$（可以简单的理解为可用的模型）， 后一个变换的假设集包含前一个变换的假设集（新添加的项的系数设置为0即可）。

可以得到如下的Hypothesis set structure$Hypothesissetstructure$

进一步的分析可以得到：

当hypothesis$hypothesis$变多的时候，选择变多了， 在这些增加的选择中，可能会找到一个hypothesis$hypothesis$有更小的Ein$E_{in}$，所以Ein$E_{in}$就会下降，但是如果没有找到更好的，但是起码会和原来的是一样的。所以Ein$E_{in}$应该是会一直下降的。
根据最后的两个不等式得到机器学习中一个很重要的图：

从上面的图可以看到：Ein$E_{in}$随着Hypothesis Set$HypothesisSet$的复杂度的提高而下降；但是模型的复杂度会随之上升。我们最关心的Eout$E_{out}$先下降后上升。所以使用一个高维度的变换很容易使得Ein$E_{in}$很小，但是Eout$E_{out}$却会很高， 因为模型的复杂度太大了。最佳的做法是先试用简单的模型， 如果这个时候Ein$E_{in}$已经很小了， 那么就可以将这个模型作为最终的模型；否则的话， 逐步试用较为复杂的特征转换。

5 - Summary

本篇讲述了非线性变换的流程，使得原来针对的线性的算法可以应用到非线性可分的情形。需要做的事情仅仅是通过一个特征转换Φ$\mathrm{\Phi }$将低维空间（原来的X$X$空间）中的特征转化到高维空间Z$Z$中，在Z$Z$空间中使用线性的分类算法即可。虽然这看起来非常的powerful$powerful$， 但是实际上是要付出模型复杂度的代价的。所以我们最安全的做法就是：先使用简单的模型。