[ML Notes] SVM：线性模型

Author: nex3z 2020-08-29

1. 基本型

  对于给定样本集 $D = \{(\boldsymbol x_1, y_1), (\boldsymbol x_2, y_2), \dots, (\boldsymbol x_m, y_m)\}$，$y_i \in \{-1, +1\}$，SVM 试图在两类样本的正中间找到一个超平面，来将两类样本分开。所谓正中间指的是，样本集中距离超平面最近的样本，即支持向量，与超平面间的距离相等。

  将这个超平面写为

$$\boldsymbol w^\mathrm{T} \boldsymbol x + b = 0 \tag{1}$$

其中 $\boldsymbol w = (w_1, w_2, \dots, w_d)$ 为法向量，$b$ 为偏移，二者一起确定了超平面。任意样本 $\boldsymbol x$ 到该超平面的距离为

$$r = \frac{|\boldsymbol w^\mathrm{T} \boldsymbol x + b|}{||\boldsymbol w||} \tag{2}$$

超平面对应的模型为

$$f(\boldsymbol x) = \boldsymbol w^\mathrm{T} \boldsymbol x + b \tag{3}$$

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

$$\begin{cases} \boldsymbol w^\mathrm{T} \boldsymbol x_i + b \geq +1, & y_i = +1 \\ \boldsymbol w^\mathrm{T} \boldsymbol x_i + b \leq -1, & y_i = -1 \end{cases}$$

上式还可以写为

$$y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \geq 1 \tag{4}$$

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

$$\gamma = \frac{2}{||\boldsymbol w||} \tag{5}$$

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

$$\begin{aligned} \max_{\boldsymbol w, b} \; & \frac{2}{||\boldsymbol w||} \\ \mathrm{s.t.} \; & y_i (\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \geq 1, \;\; i = 1, 2, \dots, m \end{aligned} \tag{6}$$

或者写为

$$\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_2, \dots, \alpha_m)$ 为拉格朗日乘子，且有 $\alpha _i \geq 0$，得到对偶问题

$$\begin{aligned} \max_{\boldsymbol{\alpha}} &\min_{\boldsymbol{w}, b} L(\boldsymbol w, b, \boldsymbol \alpha) \\ \mathrm{s.t.} & \; \alpha _i \geq 0, \;\; i = 1, 2, \dots, m \end{aligned}$$

  式 $(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}$$

注意上式中已经消去了 $L(\boldsymbol w, b, \boldsymbol \alpha)$ 中的 $\boldsymbol{w}$ 和 $b$，只剩下一个参数 $\boldsymbol{\alpha}$，于是前述对偶问题可以写为

$$\begin{aligned} \max_{\boldsymbol{\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\}$ 为所有支持向量的下标集合。