综述
SVM（support vector machine, 支持向量机），是一个二元分类模型，采用方法是高维空间下用超平面分割不同数据点，并使两类的之间的间隔最大化，SVM 的三大核心在于间隔、对偶、核技巧。
- hard-margin SVM
- soft-margin SVM
- kernel Method
参考资料：
Doto, 统计学习方法|支持向量机(SVM)原理剖析及实现
《统计学习方法》李航
硬间隔分类器 hard margin
最大化泛化能力，减少过拟合
\mathcal{D} = {\{(x_i, y_i)\}}_{i=1}^{N}, x_i \in \mathbb{R}^p, y_i \in \{ +1, -1\} ， y_i = 1 为正例， y_i=-1 为负例。超平面为
w^Tx+b = 0
一个分类正确的超平面要满足
y_i(w^Tx_i+b) > 0
让超平面在正确分类所有数据点的前提下，改变 w,b 的值，就获得了新的超平面，使得该超平面与所有数据点的距离之中的最小值，在其他所有能正确分类的超平面中是最大的。那么目标就是
\begin{aligned}
&\mathop{\max}_{w, b} margin(w, b)\\
&\text{s.t. } y_i(w^Tx_i + b) > 0\text{. }\forall{i = 1, 2, \dots,N}
\end{aligned}
距离函数为
\begin{aligned}
margin(w, b) = & \mathop{\min}_{i}distance(w, b, x_i)
\\ = & \mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b \mid
\end{aligned}
代入式子，常数 \frac{1}{\|w\|} 可以提出来，绝对值符号可以去掉，目标是
\begin{aligned}
\mathop{\max}_{w, b} margin(w, b)
= & \mathop{\max}_{w, b} [\mathop{\min}_{i}\frac{1}{\|w\|}\mid w^Tx_i + b\mid ]\\
= & \mathop{\max}_{w, b}[\frac{1}{\|w\|}\mathop{\min}_{i}y_i(w^Tx_i + b) ] \\
& \text{s.t. } y_i(w^Tx_i + b) > 0\text{. }
\end{aligned}
函数间隔和几何间隔 funtional margin & geometric margin
\mid w^Tx_i+b\mid 可以确定数据点与超平面的距离，从 w^Tx_i+b 和 y_i 的符号是否一致可以确定分类是否正确，于是自然就有了函数间隔的定义，来确定分类结果正确的置信度
\hat{\gamma_i} = y_i(w^Tx_i + b)
其最小值为
\hat{\gamma} = \mathop{\min}_{i}{\hat{\gamma_i}}
但这个定义有问题，例如 2x_1+4x_2+2 = 0 和 x_1+2x_2+1 = 0 是同一个平面，但函数间隔算出来是不同的。 w,b 成比例变化 \lambda 倍，超平面不会发生改变，最小函数间隔变成了 \lambda\hat{\gamma} ，所以要让同一个超平面的方程形式也是一致的。
函数间隔同除以超平面的法向量的 L_2 范数，就有了几何间隔的定义
\gamma_i = y_i(\frac{w^Tx_i}{\|w\|} + \frac{b}{\|w\|}) \\
最小值为
\gamma = \mathop{\min}_{i}{\gamma_i}
回顾高中数学说的点到平面距离公式（向量描述）
d = \frac{\mid w^Tx+b\mid}{\|w\|}
是不是有点像？其实几何间隔就是点到超平面的距离。回到 SVM 上，要最大化最小的几何间隔，其与最小函数间隔的数量关系
\gamma = \frac{\hat{\gamma}}{\|w\|} = \frac{y_i(w^Tx_i + b)}{\|w\|}
结合上式，目标就变成了
\begin{aligned}
&\mathop{\max}_{w,b}\gamma
&\text{s.t. }\frac{y_i(w^Tx_i + b)}{\|w\|} \ge \gamma \\
\Rightarrow&\mathop{\max}_{w,b}\frac{\hat{\gamma}}{\|w\|}
&\text{s.t. }y_i(w^Tx_i + b) \ge \hat{\gamma}
\end{aligned}
改变函数间隔，就是改变分子， w,b 会相应地改变。若更新使得 w_{i+1}=\lambda w_i, b_{i+1} = \lambda b_i, \lambda \neq 0 ，那超平面不会改变（可以验证），函数间隔变为 \lambda 倍，几何间隔不变。反之， w,b 不按同样的比例改变，超平面和几何间隔才会变。
换句话说，如果我们调整 w,b 使得函数间隔变为 \lambda 倍，并不会改变几何间隔。
函数间隔不为 0 ，放缩 w,b 使最小函数间隔 \hat{\gamma }= 1 ，令 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}}
\begin{aligned}
&y_j(\frac{w^T_ix_j}{\hat{\gamma}} + \frac{b_i}{\hat{\gamma}}) =\frac{\hat{\gamma}}{\hat{\gamma}}= 1 \\
\Rightarrow&y_j({w^T_{i+1}x_j} + b_{i+1}) = 1
\end{aligned}
没有改变平面本身和几何间隔，实际上，我们可以让最小函数间隔取任意值且 \hat{\gamma} \neq 0 ，都有 w^T_{i+1} = \frac{w^T_i}{\hat{\gamma}}, b_{i+1} = \frac{b_i}{\hat{\gamma}} ，我们最终求解出的SVM参数 w,b 仍然和目标的超平面参数是一致的，不会对不等式的约束和目标函数造成影响。取最简单的 \hat{\gamma} = 1 ，原问题就变成了
\begin{aligned}
&\mathop{\max}_{w,b}\frac{1}{\|w\|}\\
&\text{s.t. }\mathop{\min}_iy_i(w^Tx_i + b) = 1 \Leftrightarrow y_i(w^Tx_i + b) \ge 1
\end{aligned}
对偶问题 dual problem
最大值问题可以转换为最小值问题，刚才的目标函数可以化为
\begin{aligned}
&\mathop{\min}_{w,b} \frac{1}{2}\| w \| \\
&\text{s.t. }y_i(w^Tx_i + b) \ge1,\forall i=1,2,\dots,N
\end{aligned}
有这种形式，是因为凸优化问题一般都为求最小值，目标函数的常数不会造成什么影响， \frac{1}{2} 主要是为了后续计算。
为了消除约束条件，引入拉格朗日算子
\mathcal{L}(w, b, \alpha) = \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))
算子 \alpha = [\alpha_1, \alpha_2, \cdots, \alpha_N]^T,\alpha_i \ge 0,i=1,\cdots,N. ，令 \Delta_i = 1 - y_i(w^Tx_i + b) , \forall i= 1, \cdots, N.
其实就有
\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) = \left \{
\begin{aligned}
&\frac{1}{2}\|w\| + \infty = +\infty , &\text{if }\Delta_i > 0 \\
&\frac{1}{2}\|w\| ,&\text{if }\Delta_i \le 0
\end{aligned}
\right.
\mathop{\max}\mathcal{L} 的最小值就等于刚才的目标函数，把约束归并到目标中，相当于丢弃了 \Delta_i >0 的解空间，目标变为
infty\mathop{\min}_{w,b}\mathop{\max}_{\alpha}\mathcal{L}(w, b, \alpha) = \mathop{\min}_{w,b}(+ \infty, \frac{1}{2}\|w\|) = \mathop{\min}\frac{1}{2}\|w\|
带 w,b 约束的原问题转化为无约束的
\begin{aligned}
&\mathop{\min}_{w,b} \mathop{\max}_\alpha \mathcal{L}(w, b, \alpha) \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}
它的对偶问题是
\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha) \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}
如何理解这个问题？
\mathop{\min}\mathop{\max}f \ge \mathop{\max}\mathop{\min} f
举个栗子，宁为鸡头，不为凤尾。（or 瘦死的骆驼比马大） \mathop{\max}f 就是凤， \mathop{\min}f 就是鸡， \mathop{\max}\mathop{\min}f 就是鸡头， \mathop{\min}\mathop{\max}f 就是凤尾。
凸优化二次问题就满足强对偶关系，即等号也成立。
回到 SVM ，刚才的目标是
\begin{aligned}
&\mathop{\max}_{w,b} \mathop{\min}_\alpha \mathcal{L}(w, b, \alpha) \\
&\text{s.t. } \alpha_i \ge 0,\forall i=1,2,\dots,N
\end{aligned}
先求 \mathop{\min}_\alpha \mathcal{L} ，可以求偏导得到最优解
\begin{aligned}
\frac{\partial \mathcal{L}}{\partial b}
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))) \\
&= \frac{\partial}{\partial b}(\frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b)
\\
&= \frac{\partial}{\partial b}(-\sum_{i = 1}^{N} \alpha_i y_i b) \\
&= -\sum_{i = 1}^{N} \alpha_i y_i
\end{aligned}
令 \frac{\partial \mathcal{L}}{\partial b} = 0 ，得 \sum_{i = 1}^{N} \alpha_i y_i = 0 ，将其代入 \mathcal{L} ，求关于 w 的偏导
\begin{aligned}
\frac{\partial \mathcal{L}}{\partial w}
&= \frac{\partial}{\partial b}[ \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i(1 - y_i(w^Tx_i + b))] \\
&= \frac{\partial}{\partial b}[\frac{1}{2}w^Tw + \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - 0] \\
&= w - \sum_{i = 1}^{N} \alpha_i y_i x_i
\end{aligned}
令 \frac{\partial \mathcal{L}}{\partial w} = 0 ，得最优解参数 w* = \sum_{i = 1}^{N} \alpha_i y_i x_i 。结合之前公式，推出 \sum_{i = 1}^{N} \alpha_i y_i b = 0 （ b 不是向量），将其代入 \mathcal{L}
\begin{aligned}
\mathop{\min}_\alpha \mathcal{L}(w, b, \alpha)
&= \frac{1}{2}\|w\| + \sum_{i = 1}^{N} \alpha_i - \sum_{i = 1}^{N} \alpha_i y_i w^T x_i - \sum_{i = 1}^{N} \alpha_i y_i b
\\
&= \frac{1}{2}(\sum_{i = 1}^{N} \alpha_i y_i x_i)^T (\sum_{j = 1}^{N} \alpha_j y_j x_j)
+ \sum_{i = 1}^{N} \alpha_i
- \sum_{i = 1}^{N} (\alpha_i y_i x_i )^T(\sum_{j = 1}^{N} \alpha_j y_j x_j)
\\
&= \frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N} \alpha_i \alpha_j y_iy_j x_i^Tx_j
- \sum_{i = 1}^{N}\sum_{j = 1}^{N} \alpha_i \alpha_j y_iy_j x_i^Tx_j + \sum_{i = 1}^{N} \alpha_i
\\
&= -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N} \alpha_i \alpha_j y_iy_j x_i^Tx_j +
\sum_{i = 1}^{N} \alpha_i
\end{aligned}
进一步得到目标
\begin{aligned}
&\mathop{\max}_{w,b}[ -\frac{1}{2} \sum_{i = 1}^{N}\sum_{j = 1}^{N} \alpha_i \alpha_j y_iy_j x_i^Tx_j + \sum_{i = 1}^{N} \alpha_i] \\
&\text{s.t. } \alpha_i \ge 0, \text{且} \sum_{j = 1}^{N} \alpha_iy_i = 0, \forall i=1,2,\dots,N
\end{aligned}
KKT条件
原问题和对偶问题满足强对偶关系的充要条件为其满足 KKT 条件：
\begin{aligned}
&\frac{\partial \mathcal{L}}{\partial w}=0,\frac{\partial \mathcal{L}}{\partial b}=0
\\&\alpha_k(1-y_k(w^Tx_k+b))=0\text{ (slackness complementary, 松弛互补条件)}\\
&\alpha_i\ge0\\
&1-y_i(w^Tx_i+b)\le 0
\end{aligned}
得出最优解参数为
w^* =\sum\limits_{i=1}^N\alpha_iy_ix_i \\
w^* 是训练集的线性组合， \alpha_i 其实只在支持向量上时才有值，其他地方是0。
对于参数 b 和( x_k 是支持向量)
\begin{aligned}
\exists k, 1-y_k(w^Tx_k+b) =0,
\text{s.t. }b^*
=y_k-w^Tx_k
=y_k-\sum\limits_{i=1}^N\lambda_iy_ix_i^Tx_k
\end{aligned}
发现其实 b^* 也是是训练集的线性组合。决策函数就出来了
f(x) = sign(w^* + b^*)
软间隔分类器 soft margin
soft: 允许一点点错误。保持泛化的能力，降低噪声对模型的影响。
Hard-margin 的 SVM 只对可分数据可解，如果不可分的情况，我们的基本想法是在损失函数中加入错误分类的可能性。错误分类的个数可以写成( \mathbb{I} 为指示函数)
loss =\sum\limits_{i=1}^N\mathbb{I}\{y_i(w^Tx_i+b)\lt1\}
这个样本点分类错误则输出0，正确则输出1，容忍一点错误。但这个函数不连续，可以将其改写为：
loss =\sum\limits_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}
求和符号中的式子又叫铰链函数 ( Hinge Function ) 。前面说的函数间隔 \hat{\gamma}_i = y_i(w^Tx_i+b) ，这个函数本质就是
H = \left \{
\begin{aligned}
&\hat{\gamma}_i , &\text{if } \hat{\gamma}_i < 1
\\
&0 , &\text{if } \hat{\gamma}_i \ge 1
\end{aligned}
\right.
我个人的理解是
某样本点 \hat{\gamma}_i 的意义 = \left\{
\begin{aligned}
&\text{分类正确的置信度很高，}&\hat{\gamma}_i > 1 \\
&\text{是支持向量，} &\hat{\gamma}_i = 1 \\
&\text{噪声，} &0 < \hat{\gamma}_i < 1 \\
&\text{分类错误的置信度，} &\hat{\gamma}_i < 0
\end{aligned}
\right.
将这个错误加入 Hard-margin SVM 中，于是：
\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N\max\{0,1-y_i(w^Tx_i+b)\}
\\
&\text{s.t. }y_i(w^Tx_i+b) \ge 1 ,i=1,2,\cdots,N
\end{aligned}
这个式子中，超参数 C 可以看作允许的错误水平，同时上式为了进一步消除 \max 符号，对数据集中的每一个观测，我们可以认为其大部分满足约束，但是其中部分违反约束，因此令 \xi_i=1-y_i(w^Tx_i+b) ，这部分约束变成 y_i(w^Tx+b)\ge1-\xi_i ， \xi_i 实际上是可以容忍错误的那部分间隔，进一步的化简：
\begin{aligned}
&\arg\min_{w,b}\frac{1}{2}w^Tw+C\sum\limits_{i=1}^N\xi_i
\\
&\text{s.t. }y_i(w^Tx_i+b)\ge 1- \xi_i, \xi_i \ge 0,i=1,2,\cdots,N
\end{aligned}
