《统计学习方法》读书笔记7：支持向量机

支持向量机是工业界很常用的分类算法（另一个是 LR），目前比神经网络更为常用，面试中也经常考到。SVM 的数学逻辑很完备，不像神经网络那样难以解释，分类也只依赖样本点（支持向量），所以非常鲁棒。但是，它的数学证明可能会稍稍复杂，需要好好做一下笔记了。

1. 首先是最简单的一类支持向量机：线性可分支持向量机。给定线性可分的训练数据集，通过间隔最大化方法得到分离超平面：

   $$\tilde{w} \cdot x + \tilde{b} = 0$$

   以及相应的分类决策函数：

   $$f(x) = \mathrm{sign}(\tilde{w} \cdot x + \tilde{b})$$

   称为线性可分支持向量机。它的解是唯一的。

2. 函数间隔与几何间隔。函数间隔的定义是：

   $$\hat{\gamma}_i = y_i (w \cdot x_i + b)$$

   函数间隔定义了分类预测的正确性。

   几何间隔是将函数间隔做规范化：

   $$\gamma_i = \frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|}$$

   为什么要引入两种间隔呢？因为我们要找到的是一个超平面 $\tilde{w} \cdot x + \tilde{b} = 0$，可是这一个超平面有无数种表示方法：只要对 $w$ 和 $b$ 乘上一个因子 $\lambda$，表示的还是同一个超平面。可是对于不同的 $w$ 和 $b$，它的函数间隔却不一样。那么直接使用几何间隔不就行了？为什么还要提函数间隔？因为可以将用几何间隔表述的问题转化为求函数间隔的问题，更加便于求解。

3. 间隔最大化。间隔最大化的直观意义就是：不仅要用一个超平面分开样本点，还要让离超平面最近的点距超平面尽可能的远。这样的分割方式具有比较好的泛化能力。

   1. 最大间隔分离超平面。这个问题可以表述为：

      $$\begin{aligned} \max_{w, b} \quad & \gamma \\ \text{s.t.} \quad & y_i \left( \frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|} \right) \geq \gamma, \quad i = 1, 2, \ldots, N \end{aligned}$$

      直接求解这个问题比较困难，可以转换为关于函数间隔的表达式：

      $$\begin{aligned} \max_{w, b} \quad & \frac{\hat{\gamma}}{\|w\|} \\ \text{s.t.} \quad & y_i (w \cdot x_i + b) \geq \hat{\gamma}, \quad i = 1, 2, \ldots, N \end{aligned}$$

      因为我们要求解的只是这个超平面，所以可以解出任意一个 $\lambda w$ 与 $\lambda b$。所以，直接令 $\hat{\gamma} = 1$ 即可。于是就得到了下面的线性可分支持向量机学习的最优化问题：

      $$\begin{aligned} \min_{w, b} \quad & \frac{1}{2} \|w\|^2 \\ \text{s.t.} \quad & y_i (w \cdot x_i + b) - 1 \geq 0, \quad i = 1, 2, \ldots, N \end{aligned}$$

      最终，问题变成了一个凸二次规划问题。

   2. 决定分离超平面时只有支持向量起作用，其他实例点并不起作用。

   3. 为了方便求解和后面引入核技巧，通常使用拉格朗日乘子法求解其对偶问题：

      $$\min_{\alpha} \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$$

4. SVM 的最优化问题可以等价成合页损失函数（hinge loss function）：

   $$\min_{w, b} \sum_{i=1}^{N} [1 - y_i (w \cdot x_i + b)]_+$$

5. 通过核技巧可以让 SVM 解决非线性分类问题。为了解决非线性分类问题，通常的做法是找一个非线性变换。但是，直接找出变换往往并不容易。核技巧的想法是，只用核函数来完成。核函数指的是：

   $$K(x, z) = \phi(x) \cdot \phi(z)$$

   其中 $\phi(x)$ 为变换，$K(x, z)$ 为核函数。可以结合 SVM 优化问题的对偶形式考虑为什么不需要知道 $\phi(x)$ 只知道核函数就可以：因为对偶问题中只涉及到了内积，而核函数可以直接算出变换后的内积。

6. 对偶问题中，使用了核技巧的目标函数变为：

   $$W(\alpha) = \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^{N} \alpha_i$$

   同样，分类决策函数变为：

   $$f(x) = \mathrm{sign} \left( \sum_{i=1}^{N_s} \alpha_i y_i K(x_i, x) + b \right)$$