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

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

  1. 首先是最简单的一类支持向量机:线性可分支持向量机。给定线性可分的训练数据及,通过间隔最大化方法得到分离超平面
    $$
    \tilde w \cdot x + \tilde b = 0
    $$
    以及相应的分类决策函数
    $$
    f(x) = sign(\tilde x \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{align}
      & \max_{w, b} \gamma \newline
      & s.t.\quad y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}) \geqslant \gamma,\quad i=1,2,\cdots,N
      \end{align}
      $$
      直接求解这个问题比较困难,可以转换为关于函数间隔的表达式
      $$
      \begin{align}
      & \max_{w,b} \frac{\hat \gamma}{||w||} \newline
      & s.t. \quad y_i(w \cdot x_i + b) \geqslant \hat \gamma, \quad i=1,2,\dots,N
      \end{align}
      $$
      因为我们要求解的只是这个超平面,所以可以解出任意一个$\lambda w$与$\lambda b$。所以,直接另$ \hat \gamma = 1 $即可。于是就得到了下面的线性可分支持向量机学习的最优化问题
      $$
      \begin{align}
      & \min_{w, b} \frac{1}{2}||w||^2 \newline
      & s.t.\quad y_i(w \cdot x_i + b) - 1 \geqslant 0, \quad i=1,2,\dots,N
      \end{align}
      $$
      最终,问题变成了一个凸二次规划问题。
    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)]_+ = \xi_i
    $$
  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) = \textrm{sign}(\sum_{i=1}^{N_s}a_i y_i K(x_i, x) + b)
    $$

标签: none

添加新评论