可以先阅读上一篇博文【ML系列】简单的二元分类——Logistic回归

上一篇博文简单介绍了什么是二元分类问题，与简单的线性二元分类问题的实现方法，本篇着重来解决一个所谓的“非线性”二元分类的问题，从而引出Cover定理。这里之所以称之为所谓的“非线性”问题，是因为这类的二元分类问题看似是个非线性问题实际上依旧是使用线性回归的方法解决的。

问题描述

与上一篇博文类似，依旧是红蓝两类坐标分类，只不过这次很难简单地用一条直线将其分离开来。用于训练的数据集如下图所示：

解决方法

在二维平面上无论一条直线摆在什么位置都无法合适地分离上图中的红蓝两类坐标，很自然考虑地考虑到可以使用一个圆或是多段曲线将其分界线描述出来，这样一来就可以使用非线性回归拟合这样一个多段曲线，但是这个方法有一个前提，就是需要确定分界线的线形（如圆，椭圆或其它圆锥曲线）或是确定分段数然后使用多项式拟合，这需要结果导向型的经验，总体来说是十分麻烦的。更加需要注意的是，当应用到高维数据集时，数据分布特点不能以坐标的形式展现出来，这种方法就很难适用了。

这个数据集的分界线看似是一个圆，是一条非线性的曲线，但这条曲线始终在一个二维平面内，如果是在三维空间中，分界线自然就变成了分界面，且是一个二维平面，注意，二维平面的表达式是线性的！现在问题就变成了如何在三维空间中将红蓝坐标分离开来，如果可以成功的将二维平面内的问题转化为三维空间的问题，那么继续使用上一篇博文中的解决方法也是可行的了。原先的数据集可以用向量形式表示出来，即为：

$$ X = \begin{matrix} [x_1 & x_2] \end{matrix}$$

现在构造一个新维度，即为$x_1^2 + x_2^2$，使得数据集转变为三维：

$$ X = \begin{matrix} [x_1 & x_2 & x_1^2 + x_2^2] \end{matrix}$$

对于提升维度后的数据集已经变得线性可分了，接下来就是重复logistic回归的步骤，使用梯度下降法求解最优参数$\theta$，并得到该分界面的方程：

$$ \theta_1 + \theta_2 x_1 + \theta_3 x_2 + \theta_4z = 0 $$

我们已知$z = x_1^2 + x_2^2$，进而可以得出在二维平面内的分界线方程为：

$$ \theta_1 + \theta_2 x_1 + \theta_3 x_2 + \theta_4(x_1^2 + x_2^2) = 0 $$

利用Matlab中contour函数画出曲面$z = \theta_1 + \theta_2 x_1 + \theta_3 x_2 + \theta_4(x_1^2 + x_2^2)$ 与平面$z = 0$的交线，即为二维平面内的分界线：

Cover定理

在提升维度后，原本非线性的数据点变得线性可分，这在数学上是有严格证明的，即Cover定理。Cover定理可以定性的描述为：当空间的维数D越大时，在该空间的N个数据点间的线性可分的概率就越大。这里需要注意一点，Cover定理描述的是线性可分的概率，并非提供了提升维度就一定可以线性可分的依据。Cover定理作为模式识别中的基本定理之一是有严格证明的，这里就不再赘述了。

依据Cover定理，在面对低维且线性不可分的数据时，我们有了一个可以努力尝试的方向，即将数据从低维空间映射到高维空间从而提升其线性可分的概率。这类可以将低维数据转变到高维的映射可以用$\phi(X)$来表示，例如多项式映射中的某一种平方映射可以写为：

如果向量$X = \begin{matrix} [1 & x_1 & x_2 ] \end{matrix}$，则：

$$ \begin{align} \phi(X) & = \begin{matrix}\phi([1 & x_1 & x_2])\end{matrix}\\ & = \begin{matrix} [1 & x_1 & x_2 & x_1 x_2 & x_1^2 & x_2^2 & x_1^2 x_2 & x_1 x_2^2 & x_1^2 x_2^2] \end{matrix} \end{align} $$

这种映射非常常见，又可称为“特征构建”，映射后的向量可称之为“特征向量”。特征构建前的数据维度为3xN（假设共有N组数据），特征构建后升为了9xN。因为特征向量内的线性特性更加显著，所以在RL approximation中也是常用到的。

还有一种特殊的映射，叫做内积映射，也可以将低维数据转变为高维数据。假设有样本$ S = (s_1, s_2, ...., s_N) $，内积映射后的矩阵维度为NxN，通常来说内积映射可以表示为：

$$ \Phi(S) =\left[ \begin{matrix} \phi(s_1, s_1) & \phi(s_1, s_2) &...& \phi(s_1, s_N)\\ \phi(s_2, s_1) & \phi(s_2, s_2) &...& \phi(s_2, s_N)\\ ... & ... & .... & ....\\ ... & ... & .... & ....\\ \phi(s_N, s_1) & \phi(s_N, s_2) &...& \phi(s_N, s_N) \end{matrix} \right]$$

内积映射又有多种，常用的比如多项式内积映射与高斯内积映射，让我们分别看一下他们的表达式：

n次多项式内积映射：

$$ \phi(s_i, s_j) = < s_i,\  s_j >^n $$

高斯内积映射：

$$ \phi(s_i, s_j) = \exp(-\frac{<s_i - s_j,\  s_i - s_j>}{2\Sigma}) $$

其中$\Sigma$为方差对角矩阵，如果将高斯内积映射写成向量形式：

$$ \phi(s_i, s_j) = \exp(-\frac{1}{2} (s_i - s_j)^T\Sigma^{-1}(s_i - s_j)) $$

了解了内积映射后，接下来就可以引入Kernel Method了