近似线性可分支持向量机的原理推导

近似线性可分的意思是训练集中大部分实例点是线性可分的，只是一些特殊实例点的存在使得这种数据集不适用于直接使用线性可分支持向量机进行处理，但也没有到完全线性不可分的程度。所以近似线性可分支持向量机问题的关键就在于这些少数的特殊点。

相较于线性可分情况下直接的硬间隔最大化策略，近似线性可分问题需要采取一种称为“软间隔最大化”的策略来处理。少数特殊点不满足函数间隔大于1的约束条件，近似线性可分支持向量机的解决方案是对每个这样的特殊实例点引入一个松弛变量 $\xi_i \geqslant 0$ ，使得函数间隔加上松弛变量后大于等于1，约束条件就变为：
$y_i(w \cdot x_i + b) + \xi_i \geqslant 1 \tag{9-37}$

对应的目标函数也变为：
$\frac{1}{2} ||w||^2 + C \sum_{i=1}^{N} \xi_i \tag{9-38}$

其中 $C$ 为惩罚系数，表示对误分类点的惩罚力度。

跟线性可分支持向量机一样，近似线性可分支持向量机可形式化为一个凸二次规划问题：
$\begin{aligned} & \min_{w,b,\xi} \quad \frac{1}{2} \| w \|^2 + C \sum_{i=1}^{N} \xi_i \\ & \text { s.t. } \quad y_i (w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \cdots, N \\ & \quad \xi_i \geq 0, \quad i = 1, 2, \cdots, N \tag{9-39} \end{aligned}$

类似于 9.2.1 节的线性可分离支持向量机的凸二次规划问题，我们同样将其转化为对偶问题进行求解。式(9-39)的对偶问题为：
$\begin{aligned} & \min_{\alpha} \quad \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\ & \text { s.t. } \quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ & \quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, \cdots, N \tag{9-40} \end{aligned}$

式(9-39)的拉格朗日函数为：
$\xi, \alpha, \mu) = \frac{1}{2} \| w \|^2 + C \sum_{i=1}^{N} \xi_i - \sum_{i=1}^{N} \alpha_i (y_i (w \cdot x_i + b) - 1 + \xi_i) - \sum_{i=1}^{N} \mu_i \xi_i \tag{9-41}$

原始问题为极小极大化问题，则对偶问题为极大极小化问题。同样先对 $\xi, \alpha, \mu)$ 求 $\xi$ 的极小，再对其求 $\alpha$ 的极大。首先求 $\xi, \alpha, \mu)$ 关于 $\xi$ 的偏导，如下：
$\frac{\partial L}{\partial w} = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \tag{9-42}$

$\frac{\partial L}{\partial b} = - \sum_{i=1}^{N} \alpha_i y_i = 0 \tag{9-43}$

$\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \tag{9-44}$

可解得：
$\sum_{i=1}^{N} \alpha_i y_i x_i \tag{9-45}$

$\sum_{i=1}^{N} \alpha_i y_i = 0 \tag{9-46}$

$\alpha_i - \mu_i = 0 \tag{9-47}$

将式(9-45)~式(9-47)代入式(9-41)，有：

$\min_{w,b,\xi} \quad L(w, b, \xi, \alpha, \mu) = - \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N} \alpha_i \tag{9-48}$

然后对 $\min_{w,b,\xi}$ $L(w,b,\xi,\alpha,\mu)$ 求 $\alpha$ 的极大，可得对偶问题为：

$\begin{aligned} & \max_\alpha L(w,b,\xi,\alpha,\mu) = -\frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^N \alpha_i \\ & s.t. \quad \sum_{i=1}^N \alpha_i y_i = 0 \\ & \quad C - \alpha_i - \mu_i = 0 \\ & \quad \alpha_i \geq 0 \\ & \quad \mu_i \geq 0, \quad i = 1, 2, \dots, N \tag{9-49} \end{aligned}$

将式(9-49)的第2~4个约束条件式进行变换，消除变量 $\mu_i$ 后可简化约束条件为：
$\leq \alpha_i \leq C \tag{9-50}$

联合式(9-48)和式(9-49)，并将极大化问题转化为极小化问题，即式(9-40)的对偶问题。跟线性可分支持向量机求解方法一样，近似线性可分问题也是通过求解对偶问题而得到原始问题的解，进而确定线性分隔超平面和分类决策函数。

假设 $\alpha^* = (\alpha_1^*, \alpha_2^*, \dots, \alpha_N^*)^T$ 是对偶最优化问题式(9-40)的解，根据拉格朗日对偶理论相关推论，式(9-40)满足KKT(Karush-Kuhn-Tucker)条件，有：
$\frac{\partial L}{\partial w} = w^* - \sum_{i=1}^N \alpha_i^* y_i x_i = 0 \tag{9-51}$