[ML Notes] SVM：线性模型
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\}$ 为所有支持向量的下标集合。