支持向量机(下)

1. 背景

我们在前面介绍了线性可分支持向量机线性不可分支持向量机,线性支持向量机可以很好地解决线性分类问题。但是在实际情况中,大多数的分类问题都是非线性的,这时就需要使用非线性支持向量机了,非线性支持向量机的主要特点是利用核技术(kernel trick)方法,在介绍核函数方法之前,我们先介绍属性变换方法

2. 属性变换

属性变换,也就是特征映射,它将数据从原先的坐标空间变换到一个新的坐标空间,从而可以在变换后的坐标空间中使用一个线性的决策边界来划分样本。进行变换后,就可以应用上一节介绍的方法在变换后的空间中找到一个线性的决策边界。

我们考虑如图所示的二维数据集(变换前),它包含方块(类标号1)和圆圈(类标号-1),数据集的决策边界可以表示如下:

$$
\sqrt{(x_1-0.5)^2 + (x_2-0.5)^2} = 0.2
$$

进一步化简为下面的二次方程:

$$
x_1^2 - x_1 + x_2^2 - x_2 = -0.46
$$

sample

我们知道一条圆锥曲线(圆是圆锥曲线的一种特殊情况)的方程可以写作这样的形式:

$$
Ax^2 + Bxy + Cy^2 + Dx + Ey + F = 0
$$

如果我们构造一个五维的空间,令$z_1 = x^2$,$z_2=xy$,$z_3=y^2$,$z_4=x$,$z_5=y$,即
$$
(x, y) \longrightarrow (z_1, z_2, z_3, z_4, z_5, 1)
$$

那么二维空间的圆锥曲线就被映射到五维空间的超平面:

$$
Az_1 + Bz_2 + Cz_3 + Dz_4 + Ez_5 + F = 0
$$

现在,假定选择下面的变换$\phi$:

$$
\phi : (x_1, x_2) \longrightarrow (x_1^2, x_2^2, \sqrt{2}x_1, \sqrt{2}x_2, \sqrt{2}x_1x_2, 1)
$$

在变换后的空间中,我们找到参数$w=(w_0,w_1,\cdots,w_5)$,使得:
$$
w_5 x_1^2 + w_4 x_2^2 + w_3 \sqrt{2}x_1 + w_2 \sqrt{2}x_2 + w_1 \sqrt{2} x_1 x_2 + w_0 = 0
$$

例如,对于前面给定的数据,以$x_1^2 - x_1$和$x_2^2 - x_2$为坐标绘图,如图所示(变换后),假设样本在变换后的空间是线性可分的,这样,我们就可以采用线性支持向量机来解决非线性不可分问题了。

然而,直接采用非线性变换的方法却存在以下几个突出的问题:

  • 空间维度变高了,在高维特征空间求解约束优化问题是计算代价很高的任务,而且可能出现维数灾难;
  • 我们不是很明确应当使用什么类型的映射函数,才可以确保在变换后的空间构建线性决策边界。一种选择是把数据变换到无限维空间,但是这样的高维空间很难处理.

那应该怎么办呢?假定存在一个合适的函数$\phi(x)$来变换给定的数据集。变换后,我们需要构建一个线性的决策边界,把样本划分到它们各自所属的类中。在变换后的空间中,线性决策边界具有以下形式:

$$
w \cdot \phi(x) + b = 0
$$

线性支持向量机模型类似,非线性支持向量机的学习任务可以形式化地表达为以下的优化问题

\begin{equation}
\left\{
\begin{array}{ll}
\min \limits_{w,b} & \frac{1}{2}||w||^2 \\
s.t. & y_i(w \cdot \phi(x_i) + b) -1 \geq 0 , i = 1,2,\cdots, N \\
\end{array}
\right.
\end{equation}

注意,非线性支持向量机的学习任务和线性支持向量机很相似。主要的区别在于,学习任务是在变换后的属性$\phi(x)$,而不是在原属性x上执行的。类似前面线性可分支持向量机求解约束优化问题的方法,我们可以得到非线性支持向量机的对偶拉格朗日函数

$$
W(\alpha) = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (\phi(x_i) \cdot \phi(x_j) ) - \sum_{i=1}^N \alpha_i
$$

我们可以发现,上述对偶拉格朗日函数跟线性支持向量机的对偶拉格朗日函数很相似,线性支持向量机的对偶拉格朗日函数为:

$$
W(\alpha) = \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j ) - \sum_{i=1}^N \alpha_i
$$

线性支持向量机的分类决策函数为:
$$
f(x) = sign \left(\sum_{i=1}^N a_i^{*} y_i (x_i \cdot x) + b^{*}\right)
$$

通过类似的推导,我们可以得到非线性支持向量机的分类决策函数

$$
f(x) = sign \left(\sum_{i=1}^N a_i^{*} y_i (\phi(x_i) \cdot \phi(x)) + b^{*}\right)
$$

由上面的式子,我们注意到在线性支持向量机的对偶问题中,无论是目标函数还是决策函数(分离超平面)都只涉及输入实例与实例之间的内积(原空间的内积),而在非线性支持向量机的对偶问题中,原空间的内积$x_i \cdot x_j$被变换后的空间的内积$\phi(x_i) \cdot \phi(x_j)$取代了

而我们在上面说过,一方面变换后的空间往往是高维的,在高维空间进行运算是相当麻烦的,而且可能导致维数灾难,另一方面我们也不明确要选择什么类型的映射函数。因此,如果通过找一个映射$\phi$,然后计算原空间坐标点映射后的新坐标点,即$x_k \longrightarrow \phi(x_k)$,再计算内积$\phi(x_i) \cdot \phi(x_j)$,这种方法是行不通的。

那应该怎么办呢?下面我们就介绍一种突破性的解决方法—-核技术(kernel trick),它不需要显示地定义映射函数$\phi$,也能够计算变换后的空间的内积$\phi(x_i) \cdot \phi(x_j)$。

3. 核技术

核技术是一种使用原属性集(或特征集)计算变换后的空间的内积的方法。我们考虑前面的映射:
$$
\phi : (x_1, x_2) \longrightarrow (x_1^2, x_2^2, \sqrt{2}x_1, \sqrt{2}x_2, \sqrt{2}x_1x_2, 1)
$$

两个输入向量$u$和$v$在变换后的空间的内积可以写成如下形式:
$$
\begin{split}
\phi(u) \cdot \phi(v) &= (u_1^2,u_2^2,\sqrt{2}u_1,\sqrt{2}u_2, \sqrt{2}u_1u_2,1) \cdot (v_1^2,v_2^2,\sqrt{2}v_1,\sqrt{2}v_2, \sqrt{2}v_1v_2,1) \\
&= u_1^2 v_1^2 + u_2^2 v_2^2 + 2u_1v_1 + 2u_2v_2 + 2u_1u_2v_1v_2 + 1 \\
&= (u \cdot v + 1)^2
\end{split}
$$

该分析表明,变换后的空间的内积可以用原空间的内积来表示,避开了直接在高维空间中进行计算,而结果却是等价的:
$$
K(u,v) = \phi(u) \cdot \phi(v) = (u \cdot v + 1)^2
$$

这个在原空间中计算的函数$K$称为核函数(kernel function)。核技术有助于处理如何实现非线性支持向量机的一些问题:

  • 首先,由于在非线性支持向量机中使用的核函数必须满足一个称为Mercer定理的数学原理,因此我们不需要知道映射函数$\phi$的确切形式(显函数)。Mercer原理确保核函数总可以用某高维空间中两个输入向量的内积表示。SVM核的变换后的空间也称为再生核希尔伯特空间 (Reproducing Kernel Hilbert Space, RKHS);
  • 其次,相对于使用变换后的函数$\phi(x)$,使用核函数计算内积的开销更小;
  • 最后,计算在原空间中进行,避免了维数灾难问题.

3.1 Mercer定理

对非线性支持向量机使用的核函数主要的要求是,必须存在一个相应的变换,使得计算一对向量的核函数等价于在变换后的空间中计算这对向量的内积。这个要求可以用Mercer定理形式化地描述。

[Mercer定理]
核函数$K$可以表示为:
$$
K(u,v) = \phi(u) \cdot \phi(v)
$$
当且仅当对于任意满足$\int g(x)^2 dx$为有限值的函数$g(x)$,有
$$
\int K(x,y) g(x) g(y) dx dy \ge 0
$$

满足Mercer定理的核函数称为正定(positive definite)核函数。

下面给出一些这种核函数的例子:

  • 多项式核函数 (polynomial kernel function)
    $$
    K(x,z) = (x \cdot z + 1)^p
    $$

  • 高斯核函数(Gaussian kernel function)
    $$
    K(x,z) = \exp \left(-\frac{||x-z||^2}{2 \sigma ^2}\right)
    $$

  • 线性核 (linear kernel)
    实际上就是原始空间的内积:
    $$
    K(x,z) = (x, z)
    $$

4. 非线性支持向量机学习算法

综上,我们给出非线性支持向量机学习算法:

[非线性支持向量机学习算法]
输入:线性可分训练数据集$$T = \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$$ 其中,$x_i \in R^n, y_i \in \{+1,-1\}, i = 1,2,\cdots, N $ 。
输出:分类决策函数。
(1) 选取适当的核函数$K(x,z)$和适当的参数$C$,构造并求解最优化问题:
$$
\left \{
\begin{split}
\min \limits_{\alpha} & \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^N \alpha_i \\
s.t. & \sum_{i=1}^N \alpha_i y_i = 0 \\
& 0 \le \alpha_i \le C, i = 1,2,\cdots,N
\end{split}
\right.
$$
SMO算法求得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},\cdots,\alpha_N^{*})^T$。
(2) 选择$\alpha^{*}$的一个正分量$\alpha_j$,使得$0 < \alpha_j^{*} < C$,计算
$$
b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*} y_i K(x_i,x_j)
$$
(3) 构造分类决策函数:
$$
f(x) = sign \left(\sum_{i=1}^N \alpha_i^{*} y_i K(x,x_i) + b^{*}\right)
$$

当$K(x,z)$是正定核函数时,上面的优化问题是凸二次规划问题,解是存在的。

5. 小结

5.1 为什么引进核函数

  • 对于非线性的分类问题,我们希望能找到一个非线性变换,将数据从原先的坐标空间(原空间)映射到一个新的坐标空间(新空间),使得样本点在新空间中是可分的。这样,就可以将原空间的非线性可分问题转化成新空间的线性可分问题,再利用线性支持向量机的方法进行解决;
  • 但是,直接采用非线性变换存在以下几个问题:
    (1)空间维度变高了,求解优化问题的计算代价也变得很高,而且可能出现维数灾难;
    (2)我们并不明确应当使用什么类型的映射函数,才可以确保在变换后的空间构建线性决策边界;
  • 在变换后的空间求解优化问题的其中一个难点是计算变换后的内积$\phi(x_i) \cdot \phi(x_j)$,核函数方法使得计算(内积)在原空间进行,也就是说新空间的内积可以用原空间的内积来表示,它不需要显示地定义映射函数,也能够计算变换后的空间的内积,这样使得计算开销变小,而且也有效避免了维数灾难问题.

5.2 支持向量机的特征

  • SVM学习问题可以表示为凸优化问题,因此可以利用已知的有效算法发现目标函数的全局最小值。而其他的分类方法(如基于规则的分类器和人工神经网络)都采用一种基于贪心学习的策略来搜索假设空间,这种方法一般只能获得局部最优解;
  • SVM通过最大化函数间隔来控制模型的能力。尽管如此,用户必须提供其他参数,如使用的核函数类型、为了引入松弛变量所需的代价函数$C$等;
  • 通过对数据中每个分类属性值引入一个哑变量,SVM可以应用于分类数据。例如,如果收入水平有三个值{高,中,低},可以对每一个属性值引入一个二元变量.

6. 参考资料