向量机学习

向量机和感知机很像,都是为了寻找一个超平面来对样本分类.但是从感知机的算法中可以知道,其寻找的只是一个能实现分类的超平面,而这样的超平面给可能有多个.向量机就不一样.其寻找的是最优的超平面,原理则是因为该超平面在建立的时候,其截距和法向量的寻找只和样本中部分数据相关,既只和支持向量有关.这一寻找,提高了分类预测的准确性.

线性可分支持向量机和硬间隔最大化

线性可分支持向量机

给定线性可分训练数据集,通过间隔最大化或等价求解相应的凸二次规划问题学习得到的分离超平面为

$$\omega x + b = 0$$

以及相应的分类决策函数

$$f(x) = sign(\omega * x + b)$$

称为线性可分支持向量机

函数间隔和几何间隔

间隔表示点到超平面的距离,距离越远,可以认为这次分类预测的确信程度越高.因此间隔则和确信程度绑定

函数间隔:

对于给定的训练数据集 T 和 超平面 $(\omega,b)$,定义超平面 $(\omega,b)$ 关于样本点 $(x_i,y_i)$ 的函数间隔为:

$$\hat \gamma_i = y_i(\omega * x_i + b)$$

定义超平面 $(\omega,b)$ 关于训练集 T 的函数间隔 为超平面 $(\omega,b)$ 关于 T 中所有样本点 $(x_i,y_i)$ 的函数间隔最小值:

$$\hat \gamma = \underset{i = 1,…,N}{min} \hat \gamma_i$$

但是对于函数间隔有一个缺点则是,如果成比例改变 $\omega$ 和 $b$,虽然超平面不会改变,但是函数间隔却变大了,因此,必须对法向量做一些限定,使得间隔是确定的.

几何间隔:

对于给定的训练数据集 T 和超平面 $(\omega,b)$,定义超平面关于样本点 $(x_i,y_i)$ 的几何间隔为:

$$\gamma_i = \frac{y_i}{||\omega||}(\omega * x_i + b)$$

定义超平面 $(\omega,b)$ 关于训练集 T 的几何间隔 为超平面 $(\omega,b)$ 关于 T 中所有样本点 $(x_i,y_i)$ 的几何间隔最小值:

$$\gamma = \underset{i = 1,…,N}{min} \gamma_i$$

间隔最大化

如果一个超平面的几何间隔很大,我们可以认为该超平面的可信度很高.因此,寻找超平面的问题变成了寻找一个几何间隔最大的分离超平面.这个问题可以表示为下面的约束最优化问题:

$$\begin{aligned}
\underset{\omega,b}{max} \quad & \gamma \\
s.t. \quad & \frac{y_i}{||\omega||}(\omega * x_i + b) \ge \gamma, \quad i = 1,…,N
\end{aligned}$$

将原式子中的几何间隔改为函数间隔,问题等价于:

$$\begin{aligned}
\underset{\omega,b}{max} \quad & \frac{\hat \gamma}{||\omega||} \\
s.t. \quad & y_i(\omega * x_i + b) \ge \hat \gamma, \quad i = 1,…,N
\end{aligned}$$

因为变成了函数间隔,其间隔是可以和 $\omega$,$b$ 成比例放大,因此将原参数扩大 $\hat \gamma$ 倍,则可消除 $\hat \gamma$ 参数,也可认为其值为 1.

另外,我们易得 $||\omega||$ 的最大值问题等价于 $\frac{1}{2}||\omega||^2$ 的最小值问题相同(系数只是为了求导时化简方便).

因此,整个问题可以化简为:

$$\begin{aligned}
\underset{\omega,b}{min} \quad & \frac{1}{2}||\omega||^2 \\
s.t. \quad & y_i(\omega * x_i + b) - 1 \ge 0 , \quad i = 1,…,N
\end{aligned}$$

若训练数据集 T 线性可分,则其解是存在且唯一的.

支持向量:

在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量.

因为其距离最近,寄二者距离为几何/函数间隔,因此下式成立

$$y_i(\omega x_i + b) - 1 == 0$$

因为 $y_i$ 的取值只有 +1/-1,因此,可以看成形成了两个新的平面,且两个平面之间的间距为 $\frac{2}{||\omega||}$

学习的对偶算法

通过构建拉格朗日函数,对每一个不等式因子引入朗格朗日乘子 $\alpha_i$,定义的拉格朗日函数如下:
$$L(\omega,b,\alpha) = \frac{1}{2}||\omega||^2 - \sum \alpha_iy_i(\omega * x_i +b) + \sum \alpha_i$$

原问题变为:
$$\underset{\alpha}{max} \underset{\omega,b}{min} L(\omega,b,\alpha)$$

求 $\underset{\omega,b}{min} L(\omega,b,\alpha)$

原函数对 $\omega,b$求导,可求得
$$\begin{aligned}
& \omega = \sum \alpha_i y_i x_i \\
& \sum \alpha_i y_i = 0
\end{aligned}$$

带入原式子,得

$$\underset{\omega,b}{min} L(\omega,b,\alpha) = -\frac{1}{2}*(A Y X)^2 + \sum \alpha_i$$

式子中$A$ 为 $(\alpha_1,…,\alpha_n)$,$YX$ 为 $(x_1y_1,…,x_ny_n)^T$,$(A Y X)^2$为矩阵相乘的模

求 $\underset{\alpha}{max} L(\omega,b,\alpha)$

问题转化为:
$$\begin{aligned}
\underset{\alpha}{min} \quad & -\frac{1}{2}*(A Y X)^2 + \sum \alpha_i \\
s.t. \quad & \sum \alpha_iy_i = 0 \\
& \alpha_i \ge 0,\quad i = 1,..,N
\end{aligned}$$

由此,整个算法为:

• 构造并求解约束最优化问题:
  $$\begin{aligned}
  \underset{\alpha}{min} \quad & -\frac{1}{2}*(A Y X)^2 + \sum \alpha_i \\
  s.t. \quad & \sum \alpha_iy_i = 0 \\
  & \alpha_i \ge 0,\quad i = 1,..,N
  \end{aligned}$$
  求得最优解$(\alpha_1,…,\alpha_n)$

• 计算
  $$\omega = \sum \alpha_i y_i x_i$$
  选择一个正分量$\alpha_j \gt 0$,计算
  $$b = y_j - \sum \alpha_i y _i x_i x_j$$

• 求得超平面
  $$\omega * x + b = 0$$

此时,支持向量的定义变为:

训练数据集中对于 $\alpha_i \gt 0$的样本点的实例$x_i$称为支持向量

总结

上述算法很完美,可以现实并不完美,存在噪声,且数据可能线性不可分,因此,需要更一般的算法.

线性支持向量机与软间隔最大化

如果线性不可分,上面式子的不等式约束是不能成立的,原因为其函数间隔不能满足大于等于1的要求.为了解决这个问题,我们对于间隔的越是变宽,引入松弛变量 $\zeta$

因此,约束条件变为:

$$y_i(\omega * x_i + b) \ge 1 - \zeta_i$$

每有一个松弛变量,则支付一个代价,则目标函数变为:

$$\frac{1}{2}||\omega||^2 + C \sum \zeta_i$$

其中 $C$ 称为惩罚系数,值越大,对于误分类的惩罚越大.

因此,原始问题为:
$$\begin{aligned}
\underset{\omega,b,\zeta}{min} & \frac{1}{2} ||\omega||^2 + C \sum \zeta_i \\
s.t. & y_i(\omega x_i + b) \ge 1 - \zeta_i \\
& \zeta_i \ge 0
\end{aligned}$$

这个问题的 $\omega$ 是有唯一解的,但是 $b$ 可能是一个区间

对偶算法

对于原始问题,通过引入拉格朗日函数得

$$L(\omega,b,\zeta,\alpha,\mu) = \frac{1}{2}||\omega||^2 + C \sum \zeta - \sum \alpha_i(y_i(\omega_x + b)-1+\zeta_i) - \sum \mu_i \zeta_i$$

求导可得
$$\begin{aligned}
\omega = \sum \alpha_i y_i x_i \\
\sum \alpha_i y_i = 0 \\
C - \alpha_i - \mu_i = 0
\end{aligned}$$

带入原始可得对偶问题为:

$$\begin{aligned}
\underset{\alpha}{max} & -\frac{1}{2} A Y X + \sum \alpha_i \\
s.t. & \sum \alpha_i y_i = 0 \\
& C - \alpha_i - \mu_i = 0 \\
& \alpha_i \ge 0 \\
& \mu_i \ge 0
\end{aligned}$$

消去 $\mu$ 也可写成:

$$\begin{aligned}
\underset{\alpha}{max} & -\frac{1}{2} A Y X + \sum \alpha_i \\
s.t. & \sum \alpha_i y_i = 0 \\
& C \ge \alpha_i \ge 0
\end{aligned}$$

因此
$$\omega = \sum \alpha_i y_i x_i$$
选择一个符合 $C \ge \alpha_j \ge 0$ 的 $\alpha_j$,计算
$$b = y_j - \sum y_i \alpha_i(x_i*x_j)$$

支持向量

这个模型中,支持向量要么落在间隔边界上,要么落在间隔边界和分离超平面之间,要么处于误分类的一侧.对于 $\zeta_i = 0$ 的点,其刚好落在边界上,如果$0 \lt \zeta_i \lt 1$,则落在间隔边界和超平面之间,如果$\zeta_i == 1$,则落在误分类的一侧.

合页损失函数

对于线性支持向量机学习还有另外一种解释,为:

$$\sum[1-y_i(\omega * x_i + b)]_+ + \lambda ||\omega||^2$$

第一项是经验损失或经验风险函数,称为合页损失函数,下标 “+” 表示:
$$[z]_+ = \begin{cases}
z,z \gt 0 \\
0,else
\end{cases}$$

这个函数可以认为是示例和超平面的距离的评估函数,如果距离大于1,则对风险没有影响,否则则有影响.

非线性支持向量机与核函数

对于非线性问题,可以利用核技巧,将其转换到另一个空间,使其线性,然后使用线性支持向量机的算法即可.

核技巧

设 $\mathcal{X}$ 是输入空间,设 $\mathcal{H}$ 为特征空间(希尔伯特空间),如果存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射:

$$\phi(x): \mathcal{X} \rightarrow \mathcal{H}$$

使得对所有 $x,z \in \mathcal{X}$,函数 $K(x,z)$ 满足条件:

$$K(x,z) = \phi(x) * \phi(z)$$

则称 $K(x,z)$ 为核函数,式中 $\phi(x) * \phi(z)$ 为内积.

一个核函数能对应多种映射,对每一种情况建立映射是困难的.直接使用核函数则简单方便不少.

这样,原目标函数则为:

$$W(\alpha) = \frac{1}{2} \underset{i}{\sum} \underset{j}{\sum} \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum \alpha_i$$

同样,分类决策函数变为:

$$f(x) = sign(\sum \alpha_i y_i K(x_i,x) + b)$$

核函数是一个正定核函数.其虫咬条件是对任意 $x \in \mathcal{X},i = 1,..,m,K(x,z) 对应的 Gram 矩阵:$

$$K = [K(x_i,x_j)]_{m*m}$$

是一个半正定矩阵

常用核函数

多项式核函数 (polynomial kernel function)

$$K(x,z) = (x+z+1)^p$$

高斯核函数 (Gaussian kernel function)

$$K(x,z) = exp(-\frac{||x-z||^2}{z\sigma^2})$$

字符串核函数

该核函数定义在离散数据的几何上.在文本分类,信息检索,生物信息学方面有应用.

考虑一个有限字符串表 $\Sigma$.字符串 $s$ 是从其中取出的有限个字符的序列,包括空字符串.其长度由 $|s|$ 表示.他的元素记作 $s(1)s(2)…s(|u|)$.定义所有长度为 n 的字符串的集合记作 $\Sigma^n$,记所有字符串的集合记作 $\Sigma^* = \overset{\infty}{\underset{n = 0}{\bigcup}} \Sigma^n$

考虑字符串 $s$ 的子串 $u$.给定一个指标序列 $i = (i_1,…,i_{|u|})$,$s$ 的字串定义为 $u = s(i_1)s(i_2)…s(i_{|u|})$,其长度记作 $l(i) = i_{|u|} - i_1 + 1$.

假设 S 是长度大于或等于 n 的字符串的集合, s 是 S 的元素. 现在建立字符串集合 S 到特征空间 $\mathcal{H}_n = R^{\Sigma^n}$. 其每一个温度对应一个字符串 $u \in \Sigma^n$ 映射 $\phi(s)$ 将字符串 $s$ 对应于空间 $R^{\Sigma^n}$ 的一个向量,其在 $u$ 维的取值为:
$[\phi_n(s)]u = \displaystyle \sum{i:s(i) = u} \lambda ^{l(i)}$

序列最小最优化算法

前面已经介绍了向量机了,现在则讲解如何求解向量机问题中的 $\alpha$

这里介绍 SMO 算法,其求解的是下列问题:
$$\begin{aligned}
\underset{\alpha}{max} & -\frac{1}{2} \sum_{i=1} \sum_{j=1} \alpha_i \alpha_j y_i y_j K(x_i,x_j) + \sum \alpha_i \\
s.t. & \sum \alpha_i y_i = 0 \\
& C \ge \alpha_i \ge 0
\end{aligned}$$

其思路就是如果所有解都满足最优化问题的 KKT 条件,则其为解,如果不是,则选择两个变量,固定其他变量,针对这两个变量构建一个二次规划问题.

两个变量二次规划的求解方法

假设选择两个变量是 $\alpha_1,\alpha_2$,其他变量固定,于是最优化写成:
$$\begin{aligned}
\underset{\alpha_1,\alpha_2}{min} \quad & \frac{1}{2}K_{11}\alpha_1 ^2 + \frac{1}{2} K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 - (\alpha_1 + \alpha_2) + y_1\alpha_1\sum_{i = 3} y_i \alpha_i K_{i1} + y_2\alpha_2\sum_{i = 3} y_i \alpha_i K_{i2} \\
s.t. \quad & \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}y_i\alpha_i = \epsilon \\
& C \ge \alpha_i \ge 0
\end{aligned}$$

对于二次规划问题:
$$\begin{aligned}
如果 y_1 = y_2,则 \quad \alpha_1 + \alpha_2 = k \\
如果 y_1 \ne y_2,则 \quad \alpha_1 - \alpha_2 = k
\end{aligned}$$

假设初始可行解为 $\alpha_1^{old},\alpha_2^{old}$,最优解为 $\alpha_1^{new},\alpha_2^{new}$,并且假设在沿着约束方向未经剪辑时 $\alpha_2$ 的最优解为 $\alpha_2^{new,unc}$

由于满足不等式约束,所以 $\alpha_2^{new}$ 必须满足条件
$$L \le \alpha_2^{new} \le H$$
其中 $L,H$ 是对角线的端点,为
$$\begin{aligned}
如果 y_1 = y_2,\quad L = max(0,\alpha_2^{old} + \alpha_1^{old} - C),H = min(C, \alpha_2^{old} + \alpha_1^{old}) \\
如果 y_1 \ne y_2,\quad L = max(0,\alpha_2^{old} - \alpha_1^{old} ),H = min(C, C + \alpha_2^{old} - \alpha_1^{old})
\end{aligned}$$

记
$$g(x) = \sum \alpha_i y_i K(x_i,x) + b$$

令
$$E_i = g(x_i) - y_i$$

则沿着约束方向未经剪辑时的解为:
$$\alpha_2^{new,unc} = \alpha_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}$$

其中
$$\eta = K_{11} + K_{22} - 2K_{12}$$

剪辑后 $\alpha_2^{new}$ 的解为:
$$\alpha_2^{new} = \begin{cases}
H, \quad \alpha_2^{new,unc} \gt H\\
\alpha_2^{new,unc}, \quad else\\
L, \quad \alpha_2^{new,unc} < L
\end{cases}$$

根据之前的二次规划的约束条件可以求得 $\alpha_1^{new}$

变量的选择

第 1 个变量选择

KKT 条件:
$$\begin{aligned}
\alpha_i = 0 \Leftrightarrow y_i g(x_i) \ge 1 \\
C \gt \alpha_i \gt 0 \Leftrightarrow y_i g(x_i) = 1 \\
\alpha_i = C \Leftrightarrow y_i g(x_i) \le 1 \\
\end{aligned}$$

因此,外层循环首先遍历所有满足在间隔边界上的支持向量点,检验是否满足 KKT 条件,如果都满足则遍历整个训练集.

第 2 个变量选择

第二个变量选择的希望时使 $\alpha_2$ 有足够大的变化,所以选择一个最大的 $|E_1 - E_2|$

如果选不到一个满足要求的 $\alpha_2$,那么则遍历整个训练集,如果还是找不到,则更换 $\alpha_1$

计算阙值 b 和差值 E_i

在优化之后,需要重新计算阙值,设 $\alpha_1,\alpha_2$ 中在边界点上的值为 $\alpha_j$,则

$$b^{new} = y_j - \sum_{i=3}\alpha_i y_i K_{ij} - \alpha_1 y_1 K_1j - \alpha_2 y_2 K_2j$$

如果两个都满足,则取平均值
$E_i$的更新如下:
$$E_i^{new} = \sum y_j \alpha_j K(x_i,x_j) + b^{new} - y_i$$