【西瓜书】 006 支持向量机

训练数据集

\[D = {(x_1, y_1), (x_2, y_2), ..., (x_m, y_m)}, y_i\in{-1, +1}\]

划分超平面可以用线性方程来表示

\[w^T x + b = 0\]

其中$w = (w_1; w_2; …; w_d)$为法向量，决定了超平面的方向；$b$为位移项，决定了超平面与原点之间的距离。记作超平面$(w, b)$。

样本空间中任意点$x$到超平面$(w, b)$的距离可以写为

\[r = \frac{|w^T x + b|}{\|w\|}\]

超平面$(w,b)$能够将训练样本正确分类，即对于$(x_i, y_i) \in D$

1. $w^T x + b >= +1 , y_i = +1$
2. $w^T x + b <= -1 , y_i = -1$

两个异类支持向量(support vector)到超平面的距离之和为间隔(margin)

\[\gamma = \frac{2}{\|w\|}\]

最大间隔(maximum margin)的划分超平面

\[\max_{w, b} \frac{1}{2} \|w\|^2 s.t. y_i (w^T x_i + b) >= 1, i = 1, 2, ..., m\]

解出$\alpha$后求出$w$和$b$即可得到模型

\[f(x) = w^T x + b = \sum_{i = 1}^{m}{w_i^T x + b}\]

从对偶问题解出的$\alpha_i$是公式6.8的拉格朗日乘子,他恰对应着训练样本$(x_i, y_i)$

上述过程需满足KKT条件

对于任意训练样本$(x_i, y_i)$,总有$\alpha_i = 0$或$y_i f(x_i) = 1$. 若$\alpha_i = 0$则该样本将不会对$f(x)$有任何影响. 若$\alpha_i > 0$则必有$y_i f(x) = 1$所对应的样本点位于最大间隔边界上,是一个支持向量.

支持向量机在训练完成后,大部分训练样本都不需要保留,最终模型仅与支持向量有关.

SMO

公式6.11的求解是个二次规划问题. 因为问题的规模正比于训练样本数,使用通用二次规划算法求解会造成很大的开销. 通过利用问题的特性提出很多高效算法,例如SMO(Sequential Minimal Optimization)

基本思路:

先固定$\alpha_i$以外的所有参数,然后求$\alpha_i$上的极值. 由于存在约束$\sum_{i = 1}^{m}{\alpha_i y_i} = 0$,若固定$\alpha_i$以外的其他变量,则$\alpha_i$可由其他变量导出. 于是,SMO每次选择两个变量$\alpha_i$和$\alpha_j$,并固定其他参数,在参数初始化后,SMO不断执行如下两个步骤直至收敛:

• 选取一对需要更新的变量$\alpha_i$和$\alpha_j$
• 固定$\alpha_i$和$\alpha_j$以外的参数,求解公式6.11获取更新后的$\alpha_i$和$\alpha_j$

只需选取的$\alpha_i$和$\alpha_j$中有一个不满足KKT条件,目标函数就会在迭代后减少. KKT条件违背的程度越大,则变量更新后导致的目标函数值减幅越大. SMO先选取违背KKT条件程度最大的变量,第二个变量应选择一个是目标函数值减少最快的变量. 由于比较各变量所对应的目标函数值减幅的复杂度过高,因此SMO采用了一种启发式:使选取的两个变量所对应样本之间的间隔最大.

//

核函数

当训练样本线性不可分时,可将样本从原始空间映射到一个更高维的特征空间,是的样本正在这个特征空间内线性可分.

\[f(x) = w^T \phi(x) + b\]

从而有

\(min_{w, b} \frac{1}{2}\|w\|^2\) \(s.t. y_i(w^T \phi(x_i) + b) >= 1, i = 1, 2, ..., m.\)

对偶问题

\(\max_{\alpha} \sum_{i = 1}^{m}{\alpha_i} - \frac{1}{2} \sum_{i = 1}^{m}{\sum_{j = 1}^{m}{\alpha_i \alpha_j y_i y_j \phi(x_i)^T \phi(x_j)}}\) \(s.t. \sum_{i = 1}^{m}{\alpha_i y_i = 0}, \alpha_i >= 0, i = 1, 2, ..., m.\)

软间隔与正则化

支持向量回归

核方法