支持向量机(中)

1. 背景

我们在前面介绍了线性可分支持向量机,但它不能用于线性不可分的数据,因为原优化问题中的不等式约束并不能都成立,我们可以将原来的硬间隔最大化改为软间隔最大化,将其扩展到线性不可分的问题。那么什么是软间隔最大化呢?

2. 线性不可分支持向量机

假设给定一个特征空间上的训练数据集
$$
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$。$x_i$为第$i$个特征向量,也称为实例,$y_i$为$x_i$的类标记,当$y_i=+1$时,称$x_i$为正例;当$y_i=-1$时,称$x_i$为负例,$(x_i,y_i)$称为样本点。

假设训练数据集不是线性可分的,线性不可分意味着某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1的约束条件(参见前文)。为了解决这个问题,可以对每个样本点$(x_i,y_i)$引进一个松弛变量$\xi_i \ge 0$,使函数间隔加上松弛变量大于等于1,也就是

$$
y_i (w \cdot x_i + b) \ge 1 - \xi_i
$$

同时,目标函数由原来的$\frac{1}{2}||w||^2$变成

$$
\frac{1}{2}||w||^2 + C \sum_{i=1}^N \xi_i
$$

这里,$C>0$称为惩罚参数,一般由应用问题决定,$C$值大时对误分类的惩罚增大,$C$值小时对误分类的惩罚减小。最小化上面的目标函数意味着两层含义:

  • 使$\frac{1}{2}||w||^2$尽量小即间隔尽量大;
  • 使误分类点的个数尽量小;

类似线性可分支持向量机的硬间隔最大化方法,线性不可分向量机可以用软间隔最大化进行训练,也就是如下的凸二次规划问题(原始问题):

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

该问题是一个凸二次规划问题,因而关于$(w,b,\xi)$的解是存在的。可以证明$w$的解是唯一的,但$b$的解不唯一,$b$的解存在于一个区间。

下面给出线性支持向量机的定义:

对于给定的线性不可分的训练数据集,通过求解上述的凸二次规划问题(1),得到分离超平面
$$
w^{*} \cdot x + b^{*} = 0
$$
和分类决策函数
$$
f(x) = sign(w^{*} \cdot x + b^{*})
$$
称这样的模型为线性不可分支持向量机,简称为线性支持向量机。显然,线性支持向量机包含线性可分支持向量机。

3. 学习的对偶算法

由于原始问题含有不等式约束,不宜直接求解,与前文的求解方法类似,我们引入拉格朗日函数,将原始问题转为化对偶问题,通过求解对偶问题得到原始问题的最优解。这里直接给出原始问题(1)的对偶问题,推导方法跟前文类似。

\begin{equation}
\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(x_i \cdot 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.
\end{equation}

线性支持向量机的学习算法总结如下:

[线性支持向量机对偶学习算法]
输入:线性可分训练数据集$$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) 选择惩罚参数$C>0$,构造并求解凸二次规划问题:
$$
\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(x_i \cdot 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) 计算
$$
w^{*} = \sum_{i=1}^N \alpha_i^{*} y_i x_i
$$
并选择$\alpha^{*}$的一个正分量$\alpha_j$,使得$0 < \alpha_j^{*} < C$,计算
$$
b^{*} = y_j - \sum_{i=1}^N \alpha_i^{*} y_i (x_i \cdot x_j)
$$
(3) 求得分离超平面
$$
w^{*} \cdot x + b^{*} = 0
$$
分类决策函数:
$$
f(x) = sign(w^{*} \cdot x + b^{*})
$$

步骤(2)中,对任一适合条件$0 < \alpha_j^{*} < C$的$\alpha_j^{*} $,可以计算出$b^{*}$,但是由于原始问题(1)对$b$的解并不唯一,所以实际计算时可以取在所有符号条件的样本点上的平均值。

4. 参考资料