此文是本人学习林轩田老师的机器学习技法第四课——Soft-Margin Support Vector Machine——的课堂笔记。
前几节课的 SVM 不能容忍错误——包括不可分错误及可分分却在 margin 内的错误，这节课要解决这个问题，推导出 Soft Margin SVM。
参考
松弛变量
引入松弛变量 $\xi$，放宽条件，同时避免过度放宽，在最小化公式中也加入 $\xi$：
$$ \min{b,\mathbf{w},\xi} \frac{1}{2}\mathbf{w^Tw} + C \sum{n=1}^{N}\xi_n \\
s.t.\ y_n(\mathbf{w^Tz_n} + b) \ge 1 - \xi_n \\
s.t.\ \xi_n \ge 0
$$
此处 $C$ 是一个常量，作为平衡“large margin”与”margin violation”的参数。
$\xi$ 在限制条件中确实减小了下限，放宽了条件，但至于这背后为何能使 SVM 容忍错误，这可能要从头开始推导了。很明显，这已经可以用二次规划求解。
对偶问题
转换成对偶问题，用前面课程 Dual Support Vector Machine 中同样的方法。
拉格朗日乘数
$$ L(b,\mathbf{w},\alpha,\beta) = \frac{1}{2}\mathbf{w^Tw} + C \sum_{n=1}^{N}\xin + \sum{n=1}^N \alpha_n(1-\xi_n-y_n(\mathbf{w^T zn} + b)) + \sum{n=1}^N \beta_n (-\xin)
$$
求解：
$$ \max{\alpha_n \ge 0,\ \betan \ge 0} (min{b,\mathbf{w},\xi} L(b,\mathbf{w},\alpha,\beta))
$$
求导化简成关于 $\alpha$ 的函数
$$ \frac{\partial L}{\partial \xi_n} = C - \alpha_n - \beta_n\\
let\ \ \beta_n= C -\alpha_n
$$
因为条件中有 $\alpha_n \ge 0$，故 $C \ge \alphan \ge 0$。如此原式变换为：
$$ \max{$0 \le \alpha_n \le C,\ \beta_n=C-\alphan} (\min{b,\mathbf{w},\xi} \frac{1}{2} \mathbf{w^T w} + \sum_{n=1}^{N}\alpha_n(1 - y_n(\mathbf{w^T \mathbf{z_n}} + b)))
$$
这一步增加了限制条件，但消去了 $\beta, \xi, C$。接下来与 Dual Support Vector Machine 的过程相同，令 $\frac{\partial L}{\partial b} = 0, \frac{\partial L}{\partial wi} = 0$ 化简得：
$$
\min{\alphan} (\frac{1}{2}\sum{m=1}^{N} \sum_{n=1}^{N} y_m y_n \mathbf{z_m^T} \mathbf{z_n} \alpha_m \alphan - \sum{n=1}^{N}\alphan) \\
s.t.\ \ \sum{n=1}^N y_n \alpha_n = 0,\ \ all\ 0 \le \alpha_n \le C
$$
看上去与之前的差别只有对 $\alpha$ 加上上限 C。
求解 $b$
部分 KKT 条件：
$$ \alpha_n(1-\xi_n-y_n(\mathbf{w^T z_n} + b)) = 0 \\
(C - \alpha_n) \xi_n = 0 $$
因为除 $\xi,\ b$ 其他都是已知量，所以只要求解方程组就能得到解。而多数情况下，当 $0 \lt \alpha_n \lt C$ 时，被称为 free Support Vector，可推导出
$$ b = y_s - \mathbf{w^T z_s}
$$
之后的求解过程与前面课程没什么不同。
$\alpha_n$ 与向量角色
根据 KKT 条件，当 $\alpha_n = 0$ 时，松弛变量 $\xi_n=0$，没有错误，被称为非支持向量，non SV，处于 margin 外界；
当 $0 \lt \alpha \lt C$ 时，$\xi_n=0$，没有错误，而且可以求解 $b$，被称为 free SV，位于 margin 上；
当 $\alpha = C$ 时， $\xi_n \ne 0$，有错误，同样可以帮助求解，被称为 bounded SV，位于 margin 内部或越过了超平面。
LOOC 帮助模型选择
模型选择时，可以用 Cross Validation 做参考，其中特别的有 Leave-One-Out CV，即只留一个数据点做验证。
将 Leave-One-Out CV 与全数据集（不留验证数据）的训练做比较。如果验证数据是一个 non-SV，那么，2 者的错误是相同的，而如果验证数据是一个 SV，那么有可能分类错误。所以有
$$ E_{loocv} \le \frac{num(SV)}{N} $$
这里存在疑问的是，如果验证数据是一个很关键的 SV，可能极大地影响超平面的训练结果，这个 bound 是否成立。
这个上限可以用做安全检查，在训练模型之后便能得到 $E_{loocv}$ 的上限，可以排除一些结果太差的模型，节省时间，但它的作用有限，不能断定一个模型的好坏。