[ML Notes] SVM：线性模型

Author: nex3z 2021-03-14

1. 基本型

  对于给定样本集 D={(x1,y1),(x2,y2),…,(xm,ym)}，yi∈{−1,+1}，SVM 试图在两类样本的正中间找到一个超平面，来将两类样本分开。所谓正中间指的是，样本集中距离超平面最近的样本，即支持向量，与超平面间的距离相等。

  将这个超平面写为

wTx+b=0

其中 w=(w1,w2,…,wd) 为法向量，b 为偏移，二者一起确定了超平面。任意样本 x 到该超平面的距离为

r=|wTx+b|||w||

超平面对应的模型为

f(x)=wTx+b

  假设超平面能将训练样本正确分类，令

{wTxi+b≥+1,yi=+1wTxi+b≤−1,yi=−1

上式还可以写为

yi(wTxi+b)≥1

支持向量使上式中的等号成立，两个异类支持向量到超平面的距离之和称为“间隔”（margin），为

γ=2||w||

  SVM 的目标是找到具有最大间隔的划分超平面，即

\begin{aligned} \min_{\boldsymbol w, b} \; & \frac{1}{2} \boldsymbol w^\mathrm{T} \boldsymbol w \\ \mathrm{s.t.} \; & 1 – y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \leq 0, \;\; i = 1, 2, \dots, m \end{aligned} \tag{7}

称为 SVM 的基本型。

2. 对偶问题

  式 (7) 是一个凸二次优化问题，可以通过拉格朗日乘子法得到其对偶问题解决，该问题的拉格朗日函数为

L(\boldsymbol w, b, \boldsymbol \alpha) = \frac{1}{2} \boldsymbol w^\mathrm{T} \boldsymbol w + \sum_{i=1}^m \alpha_i \big(1 – y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \big) \tag{8}

其中 \boldsymbol \alpha = (\alpha_1, \alpha_1, \dots, \alpha_m) 为拉格朗日乘子，且有 \alpha _i \geq 0。

  式 (8) 分别对 \boldsymbol w 和 b 求偏导，得到

\nabla_{\boldsymbol w} L(\boldsymbol w, b, \boldsymbol \alpha) = \boldsymbol w – \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i

\frac{\partial L(\boldsymbol w, b, \boldsymbol \alpha)}{\partial b} = – \sum_{i=1}^m \alpha_i y_i

分别令以上两个偏导为零，得到

\boldsymbol w = \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i \tag{9}

\sum_{i=1}^m \alpha_i y_i = 0 \tag{10}

  由此式 (8) 可以进一步写为

\begin{aligned} L(\boldsymbol w, b, \boldsymbol \alpha) &= \frac{1}{2} \boldsymbol w^\mathrm{T} \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i + \sum_{i=1}^m \alpha_i – \sum_{i=1}^m \alpha_i y_i \boldsymbol w^\mathrm{T} \boldsymbol x_i + \sum_{i=1}^m \alpha_i y_i b \\ &= \sum_{i=1}^m \alpha_i – \frac{1}{2} \sum_{i=1}^m \alpha_i y_i \boldsymbol w^\mathrm{T} \boldsymbol x_i \\ &= \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 \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \end{aligned} \tag{11}

于是对偶问题可以写为

\begin{aligned} \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 \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \\ \mathrm{s.t.} \; & \sum_{i=1}^m \alpha_i y_i = 0, \\ & \alpha_i \geq 0, \; i = 1, 2, \dots, m. \end{aligned} \tag{12}

  由上面的对偶问题解出的 \alpha_i，是式 (8) 中对应样本 (\boldsymbol x_i, y_i) 的拉格朗日乘子。注意原优化问题（式 (7)）中有不等式，求解过程需要满足 KKT 条件，即

\begin{cases} \alpha_i \geq 0 \\ 1 – y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \leq 0 \\ \alpha_i \big( 1 – y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \big) = 0 \end{cases} \tag{13}

由上面的条件可知，对任意样本 (\boldsymbol x_i, y_i)，总有 \alpha_i = 0 或者 y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) = 1：

• 如果 \alpha_i = 0，则该样本不会在式 (9) 所示的权重中出现，不会对模型有影响；
• 如果 \alpha_i > 0，则必有 y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) = 1，即式 (4) 的等号成立，该样本点位于最大间隔边界上，是一个支持向量。

这表明在训练支持向量机时，大部分样本都不会保留，最终模型只与支持向量有关。

  求解得到 \boldsymbol \alpha 后，由式 (9) 就可以得到 \boldsymbol w。

  如前所述，支持向量使得式 (4) 中的等号成立，因此可以通过任意支持向量和 \boldsymbol w 来求解 b。实际中常采用所有支持向量求解的平均值，得到更加稳定和准确的结果

\begin{aligned} b &= \frac{1}{|S|} \sum_{\boldsymbol s \in S} (y_s – \boldsymbol w^\mathrm{T} \boldsymbol x_s) \\ &= \frac{1}{|S|} \sum_{\boldsymbol s \in S} \bigg( y_s – \sum_{i \in S} \alpha_i y_i \boldsymbol x_i^\mathrm{T} \boldsymbol x_s \bigg) \end{aligned} \tag{14}

其中 S = \{i|\alpha_i > 0, \; i = 1, 2, \dots, m\} 为所有支持向量的下标集合。