支持向量机（SVM）

  • 由Vapnik在上世纪60年代首次提出，并于1995年发表的论文Support-Vector Networks中正式提出。
  • 其优势在于具有完善的数学理论基础，且预测效果出类拔萃。在上世纪90年代到2010年左右（深度神经网络出现）处于机器学习的主流地位。
  • 其主要用于二分类问题：
    • 样本数据的标签取值为{0,1}\{0,1\}或{−1,1}\{-1,1\}（通常称标签为11的为正样本，−1-1的为负样本）；
    • 若两类样本可以用一个线性超平面（也称为决策边界）分开，则称数据线性可分，否则称为线性不可分。
      • pp维超平面（hyperplane）的形式：β0+β1x1+⋯+βpxp=0\beta_0+\beta_1x_1+\cdots+\beta_px_p=0

硬边界支持向量机（Hard Margin SVM）

也称为最大边界分类器（Maximum Margin Classifier）。

  • 首先，超平面需要满足以下性质： β0+β1xi1+⋯+βpxip>0⟺yi=1β0+β1xi1+⋯+βpxip<0⟺yi=−1\begin{aligned} \beta_0+\beta_1x_{i1}+\cdots+\beta_px_{ip}>0&\Longleftrightarrow y_i=1\\ \beta_0+\beta_1x_{i1}+\cdots+\beta_px_{ip}< 0&\Longleftrightarrow y_i=-1 \end{aligned} 其中正负是人为定义的，β0,⋯ ,βp\beta_0,\cdots,\beta_p由此决定。
    • 对于新样本x∗x^*，分类器通过计算β0+β1x1∗+⋯+βpxp∗\beta_0+\beta_1x^*_1+\cdots+\beta_px^*_p的符号进行分类（正or负样本）。
  • 评估分离超平面的分类效果：
    1. 稳健性：分类边界离训练样本越远越好；
    2. 泛化能力：训练样本离超平面越远，测试样本也会离超平面越远。

间隔与支持向量

  • 如何量化距离？计算每个训练样本到分离超平面的（垂直）距离，取最小。支持向量机的目标就是寻找间隔最大的超平面！
  • 支持向量（support vector）：在间隔边界上的样本点，即距离分离超平面最近的样本点。（“支撑”着最大间隔超平面）
    • 移动任何其他观测值都不会影响分隔超平面（在间隔外）

优化问题

  • 令β=(β1,⋯ ,βp)⊤\beta=(\beta_1,\cdots,\beta_p)^\top，则：

    • 正超平面：β⊤x+β0=c\beta^\top x+\beta_0=c；
    • 决策超平面：β⊤x+β0=0\beta^\top x+\beta_0=0；
    • 负超平面：β⊤x+β0=−c\beta^\top x+\beta_0=-c；

    这里cc是非零常数，故可以方程两边同除以cc（即取c=1c=1）。

  • 样本点x0x_0到超平面的距离：d=∣β⊤x0+β0∣∥β∥d=\dfrac{|\beta^\top x_0+\beta_0|}{\|\beta\|}

    • 支持向量到超平面的距离：d=1∥β∥d=\dfrac{1}{\|\beta\|}（非支持向量∣β⊤x0+β0∣>1|\beta^\top x_0+\beta_0|>1）。

  • 优化目标：最大化支持向量到超平面距离，即max⁡1∥β∥=min⁡∥β∥\max\dfrac{1}{\|\beta\|}=\min\|\beta\|。为后续求偏导方便，我们转换为min⁡12∥β∥2\min\dfrac{1}{2}\|\beta\|^2。

  • 约束条件：yi(β⊤xi+β0)≥1,i=1,2,⋯ ,Ny_i(\beta^\top x_i+\beta_0)\geq 1,i=1,2,\cdots,N（标签yiy_i与分类结果同号）

  • 这种优化问题属于凸优化，下面简单介绍凸优化的概念（详细解释可见CS127系列笔记）：

    • 凸优化：目标函数是凸的，约束条件是凸集；
    • 凸函数：任何两点之间的连线都在函数图形上方；
    • 凸集：凸集中的任意两点连成一条直线，这条直线上的所有点也都在这个集合里面；
    • 凸优化的最优解是唯一的，非凸优化可能有多个局部最优解。
    • 二次规划：目标函数为二次方程，约束条件为（线性）超平面。本优化问题就属于二次规划。
补充

这个优化问题还有另一种形式（来自ISL）：

  • 优化目标：max⁡β0,⋯ ,βp,MM\displaystyle\max_{\beta_0,\cdots,\beta_p,M} M
  • 约束条件： ∑j=1pβj2=1,yi(β0+∑j=1pβjxij)≥M,∀i=1,2,⋯ ,n\begin{aligned} \sum_{j=1}^p\beta_j^2=1,\quad y_i\left(\beta_0+\sum_{j=1}^p\beta_jx_{ij}\right)\geq M,\forall i=1,2,\cdots,n \end{aligned}

    本质是固定法向量范数为11，最大化平面间隔。下面的软边界SVM同样有类似的等价形式，在此作略。

软边界支持向量机（Soft Margin SVM）

  • 上述使用的硬边界SVM存在以下问题：
    • 约束过于严格，往往导致过拟合（对异常值过于敏感）；
    • 对于线性不可分的分类问题，硬边界SVM不可解。
  • 于是我们做出适当妥协——允许部分样本违反约束甚至被错误分类。【用泛化能力换准确性】
  • 具体而言，我们再硬边界SVM的基础上加入松弛变量δi≥0\delta_i\geq 0，表示违反约束的程度：
    • δi=0\delta_i=0：被正确分类，且在间隔边界上或者间隔之外；
    • 0<δi<10< \delta_i< 1：被正确分类，但在边界内；
    • δi≥1\delta_i \geq 1：被错误分类。
  • 约束条件改为{yi(β⊤xi+β0)≥1−δi,δi≥0\begin{cases}y_i(\beta^\top x_i+\beta_0)\geq 1-\delta_i,\\ \delta_i\geq 0\end{cases}；
  • 目标函数改为min⁡β,β0,δi12∥β∥2+C∑i=1Nδi\displaystyle\min_{\beta,\beta_0,\delta_i}\frac{1}{2}\|\beta\|^2+C\sum_{i=1}^N\delta_i，其中c∑i=1Nδi\displaystyle c\sum_{i=1}^N\delta_i为正则项（或惩罚项），作用为控制分类的错误程度，阻止松弛变量无限扩大。
    • CC为超参数，控制了模型的复杂度：CC越大，模型越接近硬边界（c=∞c=\infty即为硬边界），反之则允许更多错误。
    • 因此，可以说CC控制了Bias-Variance Tradeoff（CC越大，越容易过拟合，Var越大，Bias越小）。

损失函数

  • 将支持向量机看作机器学习方法，那么它用什么损失函数？一个简单的想法是0-1损失： L(y,f(x))={0,y=sgn(β⊤x+β0)1,y≠sgn(β⊤x+β0)L(y,f(x))=\begin{cases} 0,y=\text{sgn}(\beta^\top x+\beta_0)\\ 1,y\neq\text{sgn}(\beta^\top x+\beta_0) \end{cases} 但这个损失函数只考虑分类是否正确，而没有考虑分类错误的严重程度。
  • 作为改进（考虑数据点离分类边界的距离），我们引入Hinge Loss：L(y,f(x))=max⁡(0,1−yf(x))L(y,f(x))=\max(0,1-yf(x))
    • 1−yf(x)<01-yf(x)< 0表示点在间隔之外（被正确分类），损失为00；
    • 1−yf(x)>01-yf(x)> 0表示点在间隔内或错误分类，损失呈线性关系。

    实际上，上面优化问题中的松弛变量δi\delta_i就是Hinge Loss的一种体现。

  • 于是，SVM模型也可以用以下形式表述： min⁡β,β0C∑i=1Nmax⁡(0,1−yi(β⊤xi+b))+12∥β∥2\min_{\beta,\beta_0}C\sum_{i=1}^N\max(0,1-y_i(\beta^\top x_i+b))+\frac{1}{2}\|\beta\|^2

非线性SVM与核方法

  • 实际上，SVM不止可以解决线性分类问题。对于非线性分类问题，SVM的策略是：丰富并扩大特征空间，从而构造非线性分离边界。【低维到高维映射】
  • 具体而言，若原来的变量维度为x1,x2,⋯ ,xpx_1,x_2,\cdots,x_p，则可以将其扩充为x1,x12,x13,x2,x2x3,⋯x_1,x_1^2,x_1^3,x_2,x_2x_3,\cdots，这样甚至可以扩充到无穷维。
    • 事实上，我们有以下定理：假设在一个MM维空间中，随机取NN个训练样本，随机对每一个训练样本赋予标签+1+1或者−1-1，当M→∞M\to\infty，这些训练样本线性可分的概率P(M)=1P(M)=1。

核技巧（Kernal Trick）

  • 设样本xx经过升维后变为ψ(x)\psi(x)，则约束条件（之一）需要改为yi(β⊤ψ(xi)+β0)≥1−δiy_i(\beta^\top\psi(x_i)+\beta_0)\geq 1-\delta_i。
  • 实际上，我们不需要知道ψ(xi)\psi(x_i)的具体形式，而只需要确定ψ(xi)⊤ψ(xj)\psi(x_i)^\top\psi(x_j)，我们将其记作核函数K(xi,xj)K(x_i,x_j)。
为什么只需要核函数？

证明这个结论需要使用一些最优化理论的知识（可见CS127系列笔记），这里只作简单说明：

  • 原问题可表示为 min⁡β,b,δ12∥β∥2+C∑i=1Nδis.t.1−δi−yi(β⊤ψ(xi)+β0)≤0,i=1,…,N−δi≤0,i=1,…,N\begin{aligned} \min_{\beta,b,\delta} \quad & \frac{1}{2}\|\beta\|^2 + C\sum_{i=1}^N \delta_i \\ \text{s.t.} \quad & 1 - \delta_i - y_i(\beta^\top\psi(x_i)+\beta_0) \leq 0, \quad i=1,\ldots,N \\ & -\delta_i \leq 0, \quad i=1,\ldots,N \end{aligned}
  • 对偶函数为： θ(λ,η)=min⁡β,β0,δ{12∥β∥2−C∑i=1Nδi+∑i=1Nηiδi+∑i=1Nλi(1+δi−yiβ⊤ψ(xi)−yiβ0)}=∑i=1Nλi−12∑i=1N∑j=1Nλiλjyiyjψ(xi)⊤ψ(xj)\begin{aligned} \theta(\lambda, \eta) &= \min_{\beta, \beta_0, \delta} \left\{ \frac{1}{2} \|\beta\|^2 - C \sum_{i=1}^N \delta_i + \sum_{i=1}^N \eta_i \delta_i + \sum_{i=1}^N \lambda_i (1 + \delta_i - y_i \beta^\top \psi(x_i) - y_i \beta_0) \right\}\\ &= \sum_{i=1}^N \lambda_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \lambda_i \lambda_j y_i y_j \psi(x_i)^\top \psi(x_j) \end{aligned}
  • 将其转化为对偶问题： max⁡λθ(λ)s.t. 0≤λi≤C,∑i=1Nλiyi=0\begin{aligned} \max_{\lambda} \quad &\theta(\lambda)\\ \text{s.t. } \quad &0 \leq \lambda_i \leq C, \quad \sum_{i=1}^N \lambda_i y_i = 0 \end{aligned} 可见对偶问题只需要知道核函数即可。

训练流程

  1. 输入{(xi,yi)}i=1N\{ (x_i, y_i) \}_{i=1}^N，并求解优化问题（利用SMO算法）

    • 目标函数： max⁡θ(λ)=∑i=1Nλi−12∑i=1N∑j=1Nλiλjyiyjψ(xi)⊤ψ(xj)\max\theta(\lambda) = \sum_{i=1}^N \lambda_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \lambda_i \lambda_j y_i y_j \psi(x_i)^\top \psi(x_j)
    • 约束条件： 0≤λi≤C,∑i=1Nλiyi=00 \leq \lambda_i \leq C, \quad \sum_{i=1}^N \lambda_i y_i = 0

  2. 计算β0\beta_0：找一个0<λi<C0 < \lambda_i < C，计算

    β0=1−yi∑j=1Nλjyjψ(xi)⊤ψ(xj)yi\beta_0 = \frac{\displaystyle 1 - y_i \sum_{j=1}^N \lambda_j y_j \psi(x_i)^\top \psi(x_j)}{y_i}

    或者通过所有满足条件（即恰好落在边界上）的样本点求bb，并取平均。

测试流程

  • 输入测试样本xx：
    • 若∑i=1Nλiyiψ(xi)⊤ψ(x)+b>0\displaystyle\sum_{i=1}^N \lambda_i y_i \psi(x_i)^\top \psi(x) + b > 0，则y=1y = 1；
    • 若∑i=1Nλiyiψ(xi)⊤ψ(x)+b<0\displaystyle\sum_{i=1}^N \lambda_i y_i \psi(x_i)^\top \psi(x) + b < 0，则y=−1y = -1。

核函数的选择

  • 线性（linear）核函数：K(xi,xj)=xi⊤xjK(x_i, x_j) = x_i^\top x_j
    • 适用Soft Margin SVM
  • 多项式（polynomial）核函数：K(xi,xj)=(1+xi⊤xj)dK(x_i, x_j) = (1 + x_i^\top x_j)^d
    • 适用有限维映射，与dd有关
  • 径向（radial）核函数：K(xi,xj)=exp⁡(−γ∥xi−xj∥2)K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)
    • 适用无穷维映射
  • Mercer定理：核函数K(xi,xj)K(x_i, x_j)能写成ψ(xi)Tψ(xj)\psi(x_i)^T \psi(x_j) 的充要条件：
    • 交换性：K(xi,xj)=K(xj,xi)K(x_i, x_j) = K(x_j, x_i)；
    • 半正定性：∑i=1N∑j=1NCiCjK(xi,xj)≥0, ∀ Ci,i=1,2,...,N\displaystyle\sum_{i=1}^N \sum_{j=1}^N C_i C_j K(x_i, x_j) \geq 0, \, \forall \, C_i, i = 1, 2, ..., N。

应用：兵王问题

这个例子源于浙江大学胡浩基老师的《机器学习》课程。

多分类问题

解决方案包括：

  1. 改造优化的目标函数和限制条件，使之能处理多类（Multi-class SVM）；
  2. 一类 VS 其他类，例如1类 VS 23类，2类 VS 13类，3类 VS 12类；
    • 缺点：样本类别数量不平衡
  3. 一类 VS 另一类，例如1类 VS 2类，1类 VS 3类，2类 VS 3类（采用投票的方式决定样本的最终类别）；
    • 缺点：可能出现平票；需要K2K^2个分类器
  4. 树结构，例如123类 VS 456类，然后12类 VS 3类，然后1类 VS 2类。【类似决策树】