SVM 基础:间隔、对偶

内容纲要

综述

SVM(support vector machine, 支持向量机),是一个二元分类模型,采用方法是高维空间下用超平面分割不同数据点,并使两类的之间的间隔最大化,SVM 的三大核心在于间隔对偶核技巧

  1. hard-margin SVM
  2. soft-margin SVM
  3. kernel Method

参考资料:

Doto, 统计学习方法|支持向量机(SVM)原理剖析及实现

《统计学习方法》李航

支持向量机通俗导论(理解SVM的三层境界)

硬间隔分类器 hard margin

最大化泛化能力,减少过拟合

\mathcal{D} = {\{(x_i, y_i)\}}_{i=1}^{N}, x_i \in \mathbb{R}^p, y_i \in \{ +1, -1\}y_i = 1 为正例, y_i=-1 为负例。超平面为


w^Tx+b = 0

一个分类正确的超平面要满足


y_i(w^Tx_i+b) > 0

让超平面在正确分类所有数据点的前提下,改变 w,b 的值,就获得了新的超平面,使得该超平面与所有数据点的距离之中的最小值,在其他所有能正确分类的超平面中是最大的。那么目标就是


\begin{aligned}
&\mathop{\max}_{w, b} margin(w, b)\\
&\text{s.t. } y_i(w^Tx_i + b) > 0\text{. }\forall{i = 1, 2, \dots,N}
\end{aligned}

距离函数为


\begin{aligned}
margin(w, b) = & \mathop{\min}_{i}distance(w, b, x_i)
\\ = & \mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b \mid
\end{aligned}

代入式子,常数 \frac{1}{\|w\|} 可以提出来,绝对值符号可以去掉,目标是


\begin{aligned}
\mathop{\max}_{w, b} margin(w, b)
 = & \mathop{\max}_{w, b} [\mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b\mid ]\\
 = & \mathop{\max}_{w, b}[\frac{1}{\|w\|}\mathop{\min}_{i}y_i(w^Tx_i + b) ]   \\
& \text{s.t. } y_i(w^Tx_i + b) > 0\text{. }
\end{aligned}

函数间隔和几何间隔 funtional margin & geometric margin

\mid w^Tx_i+b\mid 可以确定数据点与超平面的距离,从 w^Tx_i+by_i 的符号是否一致可以确定分类是否正确,于是自然就有了函数间隔的定义,来确定分类结果正确的置信度


\hat{\gamma_i} = y_i(w^Tx_i + b)

其最小值为


\hat{\gamma} = \mathop{\min}_{i}{\hat{\gamma_i}}

但这个定义有问题,例如 2x_1+4x_2+2 = 0x_1+2x_2+1 = 0 是同一个平面,但函数间隔算出来是不同的。 w,b 成比例变化 \lambda 倍,超平面不会发生改变,最小函数间隔变成了 \lambda\hat{\gamma} ,所以要让同一个超平面的方程形式也是一致的。

函数间隔同除以超平面的法向量的 L_2 范数,就有了几何间隔的定义


\gamma_i = y_i(\frac{w^Tx_i}{\|w\|} + \frac{b}{\|w\|}) \\

最小值为


\gamma = \mathop{\min}_{i}{\gamma_i}

回顾高中数学说的点到平面距离公式(向量描述)


d = \frac{\mid w^Tx+b\mid}{\|w\|}

是不是有点像?其实几何间隔就是点到超平面的距离。回到 SVM 上,要最大化最小的几何间隔,其与最小函数间隔的数量关系


\gamma = \frac{\hat{\gamma}}{\|w\|} = \frac{y_i(w^Tx_i + b)}{\|w\|}

结合上式,目标就变成了


\begin{aligned}
&\mathop{\max}_{w,b}\gamma 
&\text{s.t. }\frac{y_i(w^Tx_i + b)}{\|w\|} \ge \gamma \\
\Rightarrow&\mathop{\max}_{w,b}\frac{\hat{\gamma}}{\|w\|} 
&\text{s.t. }y_i(w^Tx_i + b) \ge \hat{\gamma}
\end{aligned}

改变函数间隔,就是改变分子, w,b 会相应地改变。若更新使得 w_{i+1}=\lambda w_i, b_{i+1} = \lambda b_i, \lambda \neq 0 ,那超平面不会改变(可以验证),函数间隔变为 \lambda 倍,几何间隔不变。反之, w,b 不按同样的比例改变,超平面和几何间隔才会变。

换句话说,如果我们调整 w,b 使得函数间隔变为 \lambda 倍,并不会改变几何间隔。

函数间隔不为 0 ,放缩 w,b 使最小函数间隔 \hat{\gamma }= 1 ,令 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}}


\begin{aligned}
&y_j(\frac{w^T_ix_j}{\hat{\gamma}} + \frac{b_i}{\hat{\gamma}}) =\frac{\hat{\gamma}}{\hat{\gamma}}=  1 \\
\Rightarrow&y_j({w^T_{i+1}x_j} + b_{i+1}) = 1
\end{aligned}

没有改变平面本身和几何间隔,实际上,我们可以让最小函数间隔取任意值且 \hat{\gamma} \neq 0 ,都有 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}} ,我们最终求解出的SVM参数 w,b 仍然和目标的超平面参数是一致的,不会对不等式的约束和目标函数造成影响。取最简单的 \hat{\gamma} = 1 ,原问题就变成了


\begin{aligned}
&\mathop{\max}_{w,b}\frac{1}{\|w\|}\\
&\text{s.t. }\mathop{\min}_iy_i(w^Tx_i + b) = 1 \Leftrightarrow y_i(w^Tx_i + b) \ge 1
\end{aligned}

对偶问题 dual problem

最大值问题可以转换为最小值问题,刚才的目标函数可以化为


\begin{aligned}
&\mathop{\min}_{w,b} \frac{1}{2}\| w \| \\
&\text{s.t. }y_i(w^Tx_i + b) \ge1,\forall i=1,2,\dots,N
\end{aligned}

有这种形式,是因为凸优化问题一般都为求最小值,目标函数的常数不会造成什么影响, \frac{1}{2} 主要是为了后续计算。

为了消除约束条件,引入拉格朗日算子


\mathcal{L}(w, b, \alpha) = \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))

算子 \alpha = [\alpha_1, \alpha_2, \cdots, \alpha_N]^T,\alpha_i \ge 0,i=1,\cdots,N. ,令 \Delta_i = 1 - y_i(w^Tx_i + b) , \forall i= 1, \cdots, N.

其实就有


\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) =  \left \{
\begin{aligned}
&\frac{1}{2}\|w\| + \infty = +\infty , &\text{if }\Delta_i > 0 \\
&\frac{1}{2}\|w\| ,&\text{if }\Delta_i \le 0
\end{aligned}
\right.

\mathop{\max}\mathcal{L} 的最小值就等于刚才的目标函数,把约束归并到目标中,相当于丢弃了 \Delta_i >0 的解空间,目标变为


infty\mathop{\min}_{w,b}\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) = \mathop{\min}_{w,b}(+ \infty, \frac{1}{2}\|w\|) = \mathop{\min}\frac{1}{2}\|w\|

w,b 约束的原问题转化为无约束的


\begin{aligned}
&\mathop{\min}_{w,b} \mathop{\max}_\alpha \mathcal{L}(w, b, \alpha) \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

它的对偶问题是


\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha)  \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

如何理解这个问题?


\mathop{\min}\mathop{\max}f \ge \mathop{\max}\mathop{\min} f

举个栗子,宁为鸡头,不为凤尾。(or 瘦死的骆驼比马大) \mathop{\max}f 就是凤, \mathop{\min}f 就是鸡, \mathop{\max}\mathop{\min}f 就是鸡头, \mathop{\min}\mathop{\max}f 就是凤尾。

凸优化二次问题就满足强对偶关系,即等号也成立。

回到 SVM ,刚才的目标是


\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha)  \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}

先求 \mathop{\min}_\alpha \mathcal{L} ,可以求偏导得到最优解


\begin{aligned}
\frac{\partial \mathcal{L}}{\partial b} 
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))) \\
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b)
\\
&= \frac{\partial}{\partial b}(-\sum_{i = 1}^{N} \alpha_i y_i  b) \\
&= -\sum_{i = 1}^{N} \alpha_i y_i
\end{aligned}

\frac{\partial \mathcal{L}}{\partial b} = 0 ,得 \sum_{i = 1}^{N} \alpha_i y_i = 0 ,将其代入 \mathcal{L} ,求关于 w 的偏导


\begin{aligned}
\frac{\partial \mathcal{L}}{\partial w} 
&= \frac{\partial}{\partial b}[ \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))] \\
&= \frac{\partial}{\partial b}[\frac{1}{2}w^Tw +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - 0] \\
&= w - \sum_{i = 1}^{N} \alpha_i y_i  x_i
\end{aligned}

\frac{\partial \mathcal{L}}{\partial w} = 0 ,得最优解参数 w* = \sum_{i = 1}^{N} \alpha_i y_i x_i 。结合之前公式,推出 \sum_{i = 1}^{N} \alpha_i y_i b = 0b 不是向量),将其代入 \mathcal{L}


\begin{aligned}
\mathop{\min}_\alpha \mathcal{L}(w, b, \alpha) 
&= \frac{1}{2}\|w\| +  \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b 
\\
&=  \frac{1}{2}(\sum_{i = 1}^{N} \alpha_i y_i  x_i)^T (\sum_{j = 1}^{N} \alpha_j y_j  x_j) 
+ \sum_{i = 1}^{N} \alpha_i
- \sum_{i = 1}^{N} (\alpha_i y_i  x_i )^T(\sum_{j = 1}^{N} \alpha_j y_j  x_j)
\\
&= \frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j 
- \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j  + \sum_{i = 1}^{N} \alpha_i
\\
&= -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j + 
\sum_{i = 1}^{N} \alpha_i
\end{aligned}

进一步得到目标


\begin{aligned}
&\mathop{\max}_{w,b}[ -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N}  \alpha_i \alpha_j y_iy_j  x_i^Tx_j + \sum_{i = 1}^{N} \alpha_i] \\
&\text{s.t. } \alpha_i \ge 0, \text{且} \sum_{j = 1}^{N} \alpha_iy_i = 0, \forall i=1,2,\dots,N
\end{aligned}

KKT条件

原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件:


\begin{aligned}
&\frac{\partial \mathcal{L}}{\partial w}=0,\frac{\partial \mathcal{L}}{\partial b}=0
\\&\alpha_k(1-y_k(w^Tx_k+b))=0\text{ (slackness complementary, 松弛互补条件)}\\
&\alpha_i\ge0\\
&1-y_i(w^Tx_i+b)\le 0
\end{aligned}

得出最优解参数为


w^* =\sum\limits_{i=1}^N\alpha_iy_ix_i \\

w^* 是训练集的线性组合, \alpha_i 其实只在支持向量上时才有值,其他地方是0。

对于参数 b 和( x_k 是支持向量)


\begin{aligned}

\exists k, 1-y_k(w^Tx_k+b) =0,
\text{s.t. }b^* 
=y_k-w^Tx_k 
=y_k-\sum\limits_{i=1}^N\lambda_iy_ix_i^Tx_k
\end{aligned}

发现其实 b^* 也是是训练集的线性组合。决策函数就出来了


f(x) = sign(w^* + b^*)

软间隔分类器 soft margin

soft: 允许一点点错误。保持泛化的能力,降低噪声对模型的影响。

Hard-margin 的 SVM 只对可分数据可解,如果不可分的情况,我们的基本想法是在损失函数中加入错误分类的可能性。错误分类的个数可以写成( \mathbb{I} 为指示函数)


loss =\sum\limits_{i=1}^N\mathbb{I}\{y_i(w^Tx_i+b)\lt1\}

这个样本点分类错误则输出0,正确则输出1,容忍一点错误。但这个函数不连续,可以将其改写为:


loss =\sum\limits_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}

求和符号中的式子又叫铰链函数 ( Hinge Function ) 。前面说的函数间隔 \hat{\gamma}_i = y_i(w^Tx_i+b) ,这个函数本质就是


H = \left \{
\begin{aligned}
&\hat{\gamma}_i , &\text{if } \hat{\gamma}_i < 1
\\
&0 , &\text{if } \hat{\gamma}_i \ge 1
\end{aligned}
\right.

我个人的理解是


某样本点 \hat{\gamma}_i 的意义  = \left\{
\begin{aligned}
  &\text{分类正确的置信度很高,}&\hat{\gamma}_i > 1 \\ 
 &\text{是支持向量,} &\hat{\gamma}_i = 1 \\
 &\text{噪声,} &0 < \hat{\gamma}_i < 1  \\
 &\text{分类错误的置信度,} &\hat{\gamma}_i < 0
\end{aligned}
\right.

将这个错误加入 Hard-margin SVM 中,于是:


\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}
\\
&\text{s.t. }y_i(w^Tx_i+b) \ge 1 ,i=1,2,\cdots,N
\end{aligned}

这个式子中,超参数 C 可以看作允许的错误水平,同时上式为了进一步消除 \max 符号,对数据集中的每一个观测,我们可以认为其大部分满足约束,但是其中部分违反约束,因此令 \xi_i=1-y_i(w^Tx_i+b) ,这部分约束变成 y_i(w^Tx+b)\ge1-\xi_i\xi_i 实际上是可以容忍错误的那部分间隔,进一步的化简:


\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum\limits_{i=1}^N\xi_i 
\\
&\text{s.t. }y_i(w^Tx_i+b)\ge 1- \xi_i, \xi_i \ge 0,i=1,2,\cdots,N
\end{aligned}

发表评论

邮箱地址不会被公开。 必填项已用*标注