SVM(support vector machine)支持向量机.
## 1 间隔与支持向量
+ 样本集 $D=\{(x_1, y_1), \cdots, (x_m, y_m)\}$, 其中 $x_i\in \mathbb{R}^d, y_i\in\{-1, 1\}, i=1,\cdots,m$.
+ 划分超平面为
$$
w^T x + b = 0,
$$
其中$w=(w_1, \cdots, w_d)^T$.
+ 点 $x$ 到平面的距离: 设 $x_0$ 是平面上一点, 即它满足
$$
w^T x_0 + b = 0,
$$
则 $x$ 到平面的距离即为向量 $x-x_0$ 在平面法向 $\frac{w}{\lVert w\rVert}$ 上投影长度:
$$
\frac{\lvert w^T(x-x_0)\rvert}{\lVert w\rVert} = \frac{\lvert w^T x + b\rvert}{\lVert w\rVert}.
$$
由此我们还可以知道, 原点到平面距离为
$$
\frac{\lvert w^T 0 + b\rvert}{\lVert w\rVert} = \frac{\lvert b\rvert}{\lVert w\rVert}.
$$
+ **支持向量:** 设超平面 $(w, b)$ 能将样本分类正确, 即对 $(x_i, y_i)\in D$ 有
$$
\left\{
\begin{aligned}
w^Tx_i + b &> 0 \quad y_i = +1\\
w^Tx_i + b &< 0 \quad y_i = -1
\end{aligned}
\right.
$$
通过变换$w$以及$b$可以使得下式成立:
$$
\left\{
\begin{aligned}
w^Tx_i + b &\geq 1 \quad y_i = +1\\
w^Tx_i + b &\leq -1 \quad y_i = -1
\end{aligned}
\right.
$$
若$D$中样本使得上式等号成立, 则称其为**支持向量**. 两个异类支持向量到超平面的距离之和为
$$
\gamma = \frac{2}{\lVert w\rVert},
$$
称其为**间隔**.
+ **目标:** 寻找 $(w, b)$ 使 $\gamma$ 最大, 即
$$
\begin{aligned}
&\max_{w, b} \frac{2}{\lVert w\rVert} \\
&s.t.\left\{
\begin{aligned}
w^Tx_i + b &\geq 1 \quad y_i = +1\\
w^Tx_i + b &\leq -1 \quad y_i = -1
\end{aligned}
\right.
\Leftrightarrow y_i(w^T x_i+b)\geq 1,
\end{aligned}
$$
转变为极小化问题:
$$
\begin{aligned}
&\min_{w, b} \frac12 \lVert w\rVert^2 \\
&s.t.\quad y_i(w^T x_i+b)\geq 1, \quad i=1,\cdots,m.
\end{aligned} \tag{1.1}
$$
这是个凸二次规划问题, 可以用相应的优化方法求解.
## 2 对偶问题
Lagrange 乘子法得到的 Lagrange 函数为
$$
L(w, b, \alpha) = \frac12 \lVert w\rVert^2 + \sum_{i= 1}^{m} \alpha_i\left(1-y_i(w^T x_i+b) \right),
$$
其中 $\alpha = (\alpha_1, \cdots, \alpha_m)^T$. 将 $L$ 对 $w$ 和 $b$ 的偏导置零, 有
$$
\begin{aligned}
\frac{\partial L(w, b, \alpha)}{\partial w} &= w - \sum_{i=1}^{m}\alpha_i y_i x_i = 0 \Rightarrow w = \sum_{i = 1}^{m}\alpha_i y_i x_i, \\
\frac{\partial L(w, b, \alpha)}{\partial b} &= \sum_{i = 1}^{m}\alpha_i y_i = 0.
\end{aligned}
$$
将上面第一式代入$L(w, b, \alpha)$, 再考虑上面第二式的约束, 得到对偶问题
$$
\begin{aligned}
&\quad \max_{\alpha}\frac12 \sum_{i = 1}^{m}\alpha_i y_i x_i^T\sum_{i = 1}^{m}\alpha_i y_i x_i + \sum_{i = 1}^{m}\alpha_i\left( 1-y_i(\sum_{i = 1}^{m}\alpha_i y_i x_i^T x_i + b) \right) \\
& = \max_{\alpha} \sum_{i = 1}^{m} \alpha_i - \frac12 \sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_i \\
&\qquad s.t. \\
&\qquad\qquad
\begin{aligned}
\sum_{i = 1}^{m} \alpha_i y_i &= 0 \\
\alpha_i &\geq 0 \qquad i=1,\cdots,m.
\end{aligned}
\end{aligned}
$$
求出这个问题的解 $\alpha$, 则可求出法向 $w=\sum_{i = 1}^{m}\alpha_i y_i x_i$, 于是得到分类函数:
$$
f(x) = \sum_{i = 1}^{m}\alpha_i y_i x_i^T x + b. \tag{2.1}
$$
另外, 因为 $(1.1)$ 式有不等式约束, 所以上述过程还需满足 KKT(Karush-Kuhn-Tucker) 条件:
$$
\left\{
\begin{aligned}
\alpha_i &\geq 0 \\
y_i(f(x_i) - 1) &\geq 0 \\
\alpha_i(y_i f(x_i) - 1) &= 0
\end{aligned}
\right.
$$
**分析:**
1. 若 $\alpha_i = 0$, 则对 $(2.1)$ 式不起作用;
2. 若 $\alpha_i > 0$, 则必有 $y_i f(x_i) = 1$, 即 $x_i$是支持向量,
$$
\begin{aligned}
&\Rightarrow y(w^T x_i+b) = 1\\
&\Rightarrow b = \frac{1}{y_i} - w^T x_i.
\end{aligned}
$$
因此, 我们有
$$
\begin{aligned}
f(x) &= \sum_{i = 1}^{m} \alpha_i y_i x_i^T x + b \\
&= \sum_{x_i \text{为支持向量}} \alpha_i y_i x_i^T x + b.
\end{aligned}
$$
理论上, 我们只需任取一个正支持向量 $x_{i_0}$, 即可计算出 $b=1-w^T x_{i_0}$. 但现实中, 我们常用更鲁棒的方法计算
$$
b = \frac{1}{\lvert S\rvert} \sum_{s\in S}\left(\frac{1}{y_s} - \sum_{i\in S}\alpha_i y_i x_i^T x_s \right)
$$
其中 $S=\{i: \alpha_i > 0 \}$. 即有**最终公式**
$$
f(x) = \sum_{i\in S} \alpha_i y_i x_i^T x + \frac{1}{\lvert S\rvert} \sum_{s\in S}\left(\frac{1}{y_s} - \sum_{i\in S}\alpha_i y_i x_i^T x_s \right).
$$
## 3 求解对偶问题
$$
\begin{aligned}
&\max_{\alpha} \sum_{i = 1}^{m} \alpha_i - \frac12 \sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_i \\
&\ s.t. \\
&\qquad
\begin{aligned}
\sum_{i = 1}^{m} \alpha_i y_i &= 0 \\
\alpha_i &\geq 0 \qquad i=1,\cdots,m.
\end{aligned}
\end{aligned} \tag{3.1}
$$
+ SMO(sequential minimal optimization)算法: 利用约束 $\sum_{i = 1}^{m}\alpha_i y_i = 0$, 不断执行以下步骤:
1. 选取一对需更新的变量 $\alpha_i$, $\alpha_j$;
2. 固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数, 求解 $(3.1)$更新 $\alpha_i$ 和 $\alpha_j$.
+ 怎么开始第一步? 选取的 $\alpha_i$ 和 $\alpha_j$ 对应的两样本之间间隔最大. **分析:**固定其他参数后, 仅优化两个参数的过程能做到非常高效. 仅考虑 $\alpha_i$ 和 $\alpha_j$, 约束条件可写为
$$
\alpha_i y_i + \alpha_j y_j = c = -\sum_{k\neq i,j}\alpha_k \alpha_k \qquad \alpha_i, \alpha_j \geq 0,
$$
用其消去 $(3.1)$ 中变量 $\alpha_j$, 则得到一个关于 $\alpha_i$ 的单变量二次规划问题, 仅有的约束是 $\alpha_i \geq 0$, 这样的二次规划问题具有闭式解(解析解), 于是不必调用数值优化算法, 即可高校计算出更新后的 $\alpha_i$ 和 $\alpha_j$.
## 4 参考文献
+ 周志华,《机器学习》, 清华大学出版社
