SVM算法理论详解

Posted by mudux on February 20, 2020

1. 介绍

 支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢压制了神经网络领域好多年。
 SVM是一个二分类算法。它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机。支持向量机还包括核技巧,这使它实质上的非线性分类器。支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题,也等价于正则化的合页损失函数的最小化问题。支持向量机的学习算法是求解凸二次规划的最优化算法。
 当训练数据线性可分时,通过硬间隔最大化,学习一个线性的分类器,即线性可分支持向量机;当训练数据近似线性可分时,通过软间隔最大化,也学习一个线性的分类器,即线性支持向量机;当训练数据线性不可分时,通过使用核技巧(kernel trick)及软间隔最大化,学习非线性支持向量机。
 当输入空间为欧式空间或离散集合、特征空间为希尔伯特空间时,核函数(kernel function)表示将输入从输入空间映射到特征空间得到的特征向量之间的內积。通过使用核函数可以学习非线性支持向量机,等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。核方法(kernel method)是比支持向量机更为一般的机器学习方法。
 Cortes与Vapnik提出线性支持向量机,Boser、Guyon与Vapnik又引入核技巧,提出非线性支持向量机。
 这里总结下SVM二分类算法,知识点总结于台大林轩田老师的机器学习技法前四章。

2. 线性支持向量机(Linear Support Vector Machine)

2.1 Large-Margin Separating Hyperplane

 在感知机PLA中,通过点在分类超平面的哪一侧把它归到哪一类。那么在下面的数据集中3个分类超平面都可以把数据集完美的分开,如何确定那个最好。
2.1.1
 当然希望模型具有较好的鲁棒性,测试集和训练集稍有变化时也应当正确分类,所以数据样本点应当离分类超平面越远越好。
2.1.2
 在上述3个分类超平面中,右边的分类超平面应该是我们想要的。用数学公式来表示就是要求满足:

定理-最大间隔分离超平面的存在唯一性:若训练数据集线性可分,则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

2.2 Support Vector Machine

 这里把偏置$b$拿出来,点$x$到$(w,b)$确定的超平面的距离为:

 现在需要求:

 对分类超平面$w^Tx+b=0$乘以一个因子如3,$3w^Tx+3b=0$不会改变超平面的位置,可以对超平面乘以因子使:

 现在就是要求:

 等同于:

 课程中举了一个例子: 2.1.3

append1

 从图可以看出:

  • 边界上的样本:’locates’ fattest hyperplane; 其它样本:not needed。
  • 就把边界样本称为支持向量(候选)(support vector)。

support vector machine (SVM) learn fattest hyperplances (with help of support vectors)

2.3 线性支持向量机模型求解

 需要求解:

 对这个有条件问题用SGD不容易求解,但是问题是关于$(b,w)$的二次目标函数,关于$(b,w)$的线性限制条件,也就是一个二次规划问题(Quadratic Programming)

 对上述QP问题的求解可以用现成的包 2.1.4

 最终线性硬间隔SVM算法就是 2.1.5

2.4 Reasons behind Large-Margin Hyperplane

 最大硬间隔分类超平面就相当于’weight-decay regularization’ with $E_{in}=0$。 同时dichotomies也更好,相当于更小的VC dimension,就能提高泛化能力。

2.1.6

 最大硬间隔线性分类超平面有更小的函数空间,能提高泛化能力。但分类边界还是线性边界,如果能用非线性分类器来分类,训练误差应该更小。

3. 对偶支持向量机(Dual Support Vector Machine)

3.1 Motivation of Dual SVM

 对上述2.4节需要非线性分类器对特征进行变换就行,这是有下列非线性支持向量机问题:

3.1

 假设经特征变化后有$\tilde {d}$个特征,这时的问题就是$\tilde {d} + 1$个变量,$N$个限制条件下的QP问题。如果在$\tilde {d}$很大时求解还是困难。接下来讲解如何通过对偶变换简化求解。

3.2 Lagrange Dual SVM

3.2.1 Lagrange Dual Problem

 这个问题的拉格朗日函数为: 3.2

 接下来介绍如何求解这个min-max问题。

 易知在 $any\ fixed\ \alpha^{‘} with\ all\ \alpha_n^{‘}\ge 0$条件下:

 因为 $max\ge any$

 for best $\alpha^{‘}\ge 0$ on RHS,

 因为 $best\ is\ one\ of\ any$

 拉格朗日对偶问题为:’outer’ maximization of $\alpha$ on lower bound of original problem

3.2.2 Strong Duality of Quadratic Programming

3.3

  • ’$\ge$’: weak duality;
  • ’=’: strong duality,true for QP if
    • convex primal
    • feasible primal(true is separable)
    • linear constraints —— called constraint qualification

所以在SVM中,两边等价

3.2.3 Solving Lagrange Dual

 现在只需求解对偶问题:

  • inner problem ‘unconstrained’, at optimal $\frac {\partial L(b,w,\alpha)}{\partial b} = 0 = -\sum\limits_{n=1}^N\alpha_n y_n$
  • no loss of optimality if solving with constraint $\sum\limits_{n=1}^N\alpha_n y_n=0$

 把$b$移除后问题变为:

  • inner problem ‘unconstrained’, at optimal: $\frac {\partial L(b,w,\alpha)}{\partial w_i} = 0 = w_i-\sum\limits_{n=1}^N\alpha_ny_nz_{n,i}$
  • no loss of optimality if solving with constraint $w=\sum\limits_{n=1}^N\alpha_n y_n z_n$

 把问题化简:

3.2.4 KKT Optimality Conditions

 在上式条件下,if primal-dual optimal$(b,w,\alpha)$,

  • primal feasible: $y_n(w^Tx_n+b)\ge 1$
  • dual feasible: $\alpha_n\ge 0$
  • dual-inner optimal: $\sum\limits y_n\alpha_n=0;w=\sum\limits\alpha_ny_nz_n$
  • primal-inner optimal(at optimal all ‘Lagrange terms’ disappear):

—— called Karush-Kuhn-Tucker(KKT) conditions, nessary for optimality[& sufficient hear]

 在求出最优$\alpha$后,将会用到KKT条件求解$(b,w)$。

3.3 Solving Dual SVM

3.3.1 Dual Formulation of Support Vector Machine

 等价于:

现在就把原始$\tilde {d} + 1$个变量,$N$个限制条件下的QP问题转换为了$N$个变量,$N+1$个限制条件的QP问题。

3.3.2 Dual SVM with QP Solver

 用QP求解器求解公式为:

3.4

 如果$N$很大时,$Q$矩阵很大,可能需要特殊求解器求解。

3.3.3 Optimal $(b,w)$

KKT条件
 if primal-dual optimal$(b,w,\alpha)$,

  • primal feasible: $y_n(w^Tx_n+b)\ge 1$
  • dual feasible: $\alpha_n\ge 0$
  • dual-inner optimal: $\sum\limits y_n\alpha_n=0;w=\sum\limits\alpha_ny_nz_n$
  • primal-inner optimal(at optimal all ‘Lagrange terms’ disappear):

 当用求解器求出最优$\alpha$后:

  • optimal $\alpha\Rightarrow$ optimal $w$? easy above!
  • optimal $\alpha\Rightarrow$ optimal $b$? a range from primal feasible & equality from complementary slackness if one $\alpha_n \ge 0 \Rightarrow b = y_n - w^T z_n$

complementary slackness: $\alpha \gt 0\Rightarrow$ on fat boundary(SV!)

3.4 Messages behind Dual SVM

3.4.1 Support Vectors Revisited

3.5

  • only SV needed to compute $w$: $w=\sum\limits_{n=1}^N\alpha_n y_n z_n = \sum\limits_{SV}\alpha_n y_n z_n$
  • only SV needed to compute $b$: $b=y_n - w^Tz_n\ with\ any\ SV(z_n, y_n)$

SVM: learn fattest hyperplane by identifying support vectors with dual optimal solution

3.4.2 Representation of Fattest Hyperplane

w=linear combination of $y_n z_n$
  • also true for GD/SGD-based LogReg/LinReg when $w_0=0$
  • call w ‘represented’ by data

SVM: represent w by SVs only

3.4.3 Two Forms of hard-Margin SVM

3.6

3.4.4 Are We Done Yet?

 在对偶问题求解中,$q_{n,m}=y_n y_m z_n^T z_m$:inner product in $R^{\widetilde {d}}$ —— O($\widetilde d$)via naive computation

所以只有解决这个內积问题才能避免大规模运算

4. Kernel Support Vector Machine

4.1 Kernel Trick

4.1.1 Fast Inner Product for $\Phi_2$

 假设在进行非线性特征变换时用了二次多项式变换:

 那么变化后特征向量內积为:

 对$\Phi_2$变换,非线性变换+內积能够在$O(d)$时间而不是$O(d^2)$

  • quadratic coefficient $q_{n,m}=y_n y_m z_n^T z_m = y_n y_m K(x_n, x_m)$
  • optimal bias $b$? from SV($x_s$,$y_s$)
  • optimal hypothesis $g_{SVM}$:for test input $x$,

kernel trick: plug in efficient kernel function to avoid dependence on $\widetilde d$

4.1.2 Kernel SVM with QP

3.7

  • 1:time complexity $O(N^2)\dot (kernel evaluation)$
  • 2: QP with $N$ variables and $N+1$ constraints
  • 3 & 4: time complexity

kernel SVM: use computational shortcut to avoid $\widetilde d$ & predict with SV only

4.2 几种常用核函数

4.2.1 Linear Kernel

4.2.2 Polynomial Kernel

4.2.3 Gaussian Kernel

 在这个变换后维度为无穷维$\Phi(x)=exp(-x^2) \cdot \left(1,\sqrt{\frac{2}{1!}x},\sqrt{\frac{2^2}{2!}x^2},\cdots \right)$

 这就是高斯核:

 在高斯核下:

  • linear combination of Gaussians centered at SVs $x_n$
  • also called Radia Basis Function(RBF) kernel

4.3 Support Vector Mechanism

3.8

5. Soft-Margin Support Vector Machine

5.1 Motivation and Primal Problem

 recall: SVM也能过拟合,如下图: 4.1

if always insisting on separable($\Leftarrow$ shatter), have power to overfit to noise

 放弃一些噪声样本:

 但上述指示函数不能求解QP,而且不能区分大误差和小误差。
 所以,

  • record ‘margin violation’ by $\xi_n$ —— linear constraints
  • penalize with margin violation instead of error count —— quadratic objective

 所以,得到soft-margin SVM:

  • 参数$C$: 在large margin和margin violation之间trade-off
    • large $C$: want less margin violation
    • small $C$: want large margin
  • QP of $\widetilde d + 1 + N$ variables, $2N$ constraints

可以证明$w$的解是唯一的,但$b$的解不唯一,$b$的解存在于一个区间(统计学习方法第七章)。

5.2 Dual Problem

5.2.1 Lagrange Dual

primal:

 带有拉格朗日乘子$\alpha_n$和$\beta_n$

5.2.2 Simplify $\xi_n$ and $\beta_n$

  • $\frac{\partial L}{\partial \xi_n} = 0 = C -\alpha_n - \beta_n$
  • no loss of optimality if solving with implicit constraint $\beta_n = C - \alpha_n$ and explicit constraints $0 \le \alpha_n \le C$: $\beta_n$ removed

 化简公式,$\xi$被移除

  • inner problem same as hard-margin SVM
  • $\frac {\partial L}{\partial b} = 0$: no loss of optimality if solving with constraint $\sum\limits_{n=1}^N\alpha_ny_n=0$
  • $\frac{\partial L}{\partial w_i}=0$: no loss of optimality if solving with constraint $w=\sum\limits_{n=1}^N \alpha_n y_n z_n$

5.2.3 Standard Soft-Margin SVM Dual

QP with $N$ variables & $2N+1$ constraints

 和hard-margin相比唯一的差别是$\alpha_n$有了上界。

5.3 Message behind Soft-Margin SVM

5.3.1 Kernel Soft-Margin SVM

5.1

5.3.2 Solving for $b$

5.2

solve unique $b$ with free SV($x_s$,$y_s$):

5.3.3 Physical Meaning of $\alpha_n$

complementary slackness:

5.3

当$\alpha_n=C$时,

  • 若$0 \lt \xi_n \lt 1$,则分类正确,$x_n$在间隔边界与分类超平面之间;
  • 若$\xi_n = 1$,则$x_n$在分类超平面上;
  • 若$\xi_n \gt 1$,则$x_n$位于分类超平面误分一侧。

$\alpha_n$ can be used for data analysis

5.4 SVM另一种解释:合页损失函数

 线性支持向量机(软间隔)学习还有另外一种解释,就是最小化以下目标函数:

 目标函数的第1项是经验损失或经验风险,函数

 称为合页损失函数(hinge loss function)。下标’+’表示以下取正值的函数。

 这就是说,当样本点$(x_n,y_n)$被正确分类且函数间隔(确信度)$y_n(w^x_n+b)$大于1时,损失是0,否则损失是$1-y_n(w^Tx_n+b)$。目标函数的第2项是系数为$\lambda$的$w$的$L_2$范数,是正则化项。
 而容易证明线性支持向量机原始最优化问题:

 等价于最优化问题

证明:令

当$1-y_n(w^Tx_n+b)\gt 0$时,$x_n$错分,$\xi_n \ge 0$表示错误量,当$1-y_n(w^Tx_n+b)\le 0$时,$x_n$正确分类,$\xi_n = 0$。
 合页损失函数可写成:

 若取$\lambda=\frac{1}{2C}$,则

 二者等价。
 合页损失函数图形如下所示:

5.4

 可以看出合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的,直接优化由其构成的目标函数比较困难,可以认为线性支持向量机是优化由0-1损失函数的上界(合页损失函数)构成的目标函数。
 图中虚线显示的是感知机的损失函数$\left[y_n(w^Tx_n+b)\right]_{+}$,这时,当样本点$(x_n,y_n)$被正确分类时,损失是0,否则损失是$-y_n(w^Tx_n+b)$。相比之下,合页损失函数不仅要分类正确,而且确信度足够高时损失才是0。也就是说,合页损失函数对学习有更高的要求。

6. SVM总结

6.1 优点

  • 有严格的数学理论支持,可解释性强,不依靠统计方法,从而简化了通常的分类和回归问题;
  • 能找出对任务至关重要的关键样本(支持向量);
  • 采用核技巧之后,可以处理非线性分类/回归任务;
  • 最终决策函数只由少数的支持向量所确定。

6.2 缺点

  • 训练时间长。当采用SMO算法是,由于每次都需要挑选一对参数,因此时间复杂度为$O(N^2)$,其中$N$为训练样本的数量;
  • 当采用核技巧时,如果需要存储核矩阵,则空间复杂度为$O(N^2)$;
  • 模型预测时,预测时间与支持向量的个数成正比。当支持向量的数量较大时,预测计算复杂度较高。

因此SVM目前只适合小批量样本的任务,无法适应百万甚至上亿样本的任务。

7. Reference

1. 支持向量机SVM-阿泽
2. 机器学习技法-林轩田老师
3 统计学习方法第七章-李航