非线性变换
线性假设集（分类器）的类别之间的判别界是线性的，低VC维可使$E_{in}$和$E_{out}$接近，但无法分类线性不可分数据。线性分类器应用于线性不可分数据，会导致很大的$E_{in}$，$E_{out}$也会很大。如何突破线性分类器的局限，对线性不可分数据分类？
上图左的数据$\mathcal D$虽然线性不可分，但是可以用上图中所示的圆分开 \[ h_{SEP}(\mathbf x)=\mbox{sign}\left(0.6-x_1^2-x_2^2\right)， \] 令$\tilde{\mathbf w}^T=[0.6,-1,-1],\mathbf z=\left[1,x_1^2,x_2^2\right]^T$，上式可以记为 \[ h(\mathbf x)=\mbox{sign}\left(\tilde{\mathbf w}^T\mathbf z\right)， \] 这就相当于通过非线性特征变换$\Phi: \mathbf x\in\mathcal X\mapsto\mathbf z\in\mathcal Z$，将$\mathcal X$空间中线性不可分数据变到线性可分的$\mathcal Z$空间，如上图右所示。
通过变换$\Phi_2(\mathbf x)=\left(1,x_1,x_2,x_1^2,x_1x_2,x_2^2\right)$，可以使得$\mathcal Z$空间的感知器和$\mathcal X$空间的二次假设等价， \[ \mathcal H_{\Phi_2}=\left\{h(\mathbf x):h(\mathbf x)=\tilde h(\Phi_2(\mathbf x))\mbox{ for some linear }\tilde h\mbox{ on }\mathcal Z\right\} \] 可以实现$\mathcal X$空间的所有二次曲线判别界，当然也包括线性的特殊情况，使得$E_{in}$有机会更小。
上图展示了使用非线性变换的步骤。首先通过变换$\Phi$将数据从$\mathcal X$空间映射到$\mathcal Z$空间；然后在$\mathcal Z$空间利用线性分类算法$\mathcal A$得到线性判别界；最后返回 \begin{equation} g(\mathbf x)=\mbox{sign}\left(\tilde{\mathbf w}^T\Phi(\mathbf x)\right)， \end{equation} 逆变换$\Phi^{-1}$不一定存在。
非线性变换$\Phi$和$\mathcal Z$空间的线性模型算法$\mathcal A$，不仅可以用于分类，而且可用于回归。
复杂度与性能分析
若原始特征是$d$维，$Q$次多项式特征变换$\Phi_{Q}(\mathbf x)$后的特征空间维度$\tilde d+1$为$\binom{Q+d}{Q}$，空间复杂度为$O\left(Q^d\right)$。当$Q$很大时，新空间中的计算和存储代价都极大。新空间中$d_{VC}\left(\mathcal H_{\Phi_Q}\right)\leq \tilde d+1$，当$Q$很大时$d_{VC}$也会很大。当$d_{VC}$增加时，用于训练的数据量也要增加，需要考虑训练集的数据量是否足够。
上图展示了人工基于视觉的选择，不同特征变换下，$d_{VC}$从6降到了1。事实上，此时的模型复杂度需要考虑人工付出的$d_{VC}$代价，这是“human learning1 ＋ machine learning”。对于机器学习，人工偷看了数据付出的代价也必须加以考量。
对于特征变换，$Q$次变换可以在$Q-1$次的基础上进行 \[ \Phi_{Q}(\mathbf x)=\left(\Phi_{Q-1}(\mathbf x),x_1^Q,x_1^{Q-1}x_2,\ldots,x_d^Q\right)， \] 也就是存在嵌套关系 \[ \mathcal H_{\Phi_0}\subset\mathcal H_{\Phi_1}\subset\mathcal H_{\Phi_2}\subset\ldots\subset\mathcal H_{\Phi_Q}， \] 那么$d_{VC}$按上述次序递增（$\leq$），$E_{in}$按上述次序递减（$\geq$）。高次变换能得到$E_{in}$非常小的结果，然而$E_{in}$仅仅是中间产物，并不能说明$E_{out}$会很小。合理的方法是从$H_{\Phi_1}$开始尝试，线性模型是首选，如果效果不达标再考虑高次的特征变换。
参考资料
-
human的能力并非是绝对的强大，只是在人类的时空中如此。当数据维度很高时，机器学习远胜人类。 ↩
