你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

机器学习基础---分类方法---支持向量机(SVM)

2021/11/12 21:48:08

支持向量机SVM(分类器)

方法描述

核心思想:

  • 本篇中主要以二分类问题为例讨论SVM分类器

  • 对于d维样本集,每个样本视作d维空间中的一个点

  • 就二分类问题而言:

    • 若样本线性可分,则一定可以找到一个超平面 ( W , b ) (W,b) (W,b)将d维样本空间分为两个部分,每类样本分别在超平面一边
    • 若样本线性不可分,通过核方法映射到可以线性分开样本的高维,再使用线性分类器
  • 对于线性可分数据来说,分割平面不唯一,为了得到唯一确定且最优的分割平面,引入间隔概念(衡量平面两端样本到平面的距离)

  • 间隔增大意味着对于样本的容错能力增强,因此SVM方法的核心目标即为最大化间隔

    如下图,黑色间隔平面与样本间间隔较大,蓝色平面与样本间隔较小,对于红色新样本点,黑色平面分类结果更合理:

在这里插入图片描述

形式描述(二分类)

  • 有输入样本集 X = [ x 1 , x 2 , . . . , x n ] X=[x_1,x_2,...,x_n] X=[x1,x2,...,xn],对应标签 L = [ y 1 , y 2 , . . . , y n ] , y i ∈ { + 1 , − 1 } L=[y_1,y_2,...,y_n],y_i\in{\{+1,-1\}} L=[y1,y2,...,yn],yi{+1,1}

  • 在d维空间中有分割平面 ( w , b ) (w,b) (w,b),其与输入样本的间隔为 τ \tau τ

  • 优化目标为:
    a r g   m a x W , b   τ \underset{W,b}{arg\ max}\ \tau W,barg max τ

  • 确定分割超平面 ( w , b ) (w,b) (w,b)后,定义分类器为:
    y i ˉ = s i g n ( w x i + b ) \bar{y_i}=sign(wx_i+b) yiˉ=sign(wxi+b)

相关概念

  • 间隔

    • 函数间隔

      • 定义函数间隔:
        τ i ˉ = y i ( w x i + b ) τ ˉ = m i n ( τ i ˉ ) \bar{\tau_i}=y_i(wx_i+b)\\ \bar{\tau}=min(\bar{\tau_i}) τiˉ=yi(wxi+b)τˉ=min(τiˉ)

      • 可以通过函数间隔的正负判断分类正误,由于 ( λ w , λ b ) (\lambda{w},\lambda{b}) (λw,λb)代表同一个平面,该值大小无确切物理意义

    • 几何间隔

      • 定义物理间隔:
        τ i = y i ( w x i ∣ w ∣ + b ∣ w ∣ ) τ = m i n ( τ i ) \tau_i=y_i(\frac{wx_i}{|w|}+\frac{b}{|w|})\\ \tau=min(\tau_i) τi=yi(wwxi+wb)τ=min(τi)

      • 几何间隔值即为空间中样本点 x i x_i xi到分割平面的距离

    • 软间隔&硬间隔

      • 硬间隔

        • 最大化间隔问题可以表示为:
          a r g   m a x w , b   τ s . t .   y i ( w x i ∣ w ∣ + b ∣ w ∣ ) ≥ τ \underset{w,b}{arg\ max}\ \tau\\ s.t.\ y_i(\frac{wx_i}{|w|}+\frac{b}{|w|})\geq\tau w,barg max τs.t. yi(wwxi+wb)τ
          该问题的约束,即要求训练集样本线性可分,目标超平面可以完美划分训练集中两类样本的

          这种情况,即为存在硬间隔

      • 软间隔

        • 若训练集中样本非严格线性可分,无法找到一个超平面完美地将两类样本分开,使用硬间隔的方法无法处理

        • 调整对于决策边界的定义,让决策边界能够忍受一小部分训练误差,在最大化间隔减少被分错的样本数之间寻求平衡

        • 在约束中引入松弛变量,即
          y i ( w x i ∣ w ∣ + b ∣ w ∣ ) ≥ τ − ξ i y_i(\frac{wx_i}{|w|}+\frac{b}{|w|})\geq\tau-\xi_i yi(wwxi+wb)τξi

      • 这种方案下,引入松弛变量的间隔问题称为软间隔

      • 两类样本间不存在直线能将其完美分开,即 y i ( w x i ∣ w ∣ + b ∣ w ∣ ) ≥ τ y_i(\frac{wx_i}{|w|}+\frac{b}{|w|})\geq\tau yi(wwxi+wb)τ约束无法满足,为解决这种情况,只能引入松弛变量 ξ i \xi_i ξi,使带松弛的约束成立

    • KKT条件

      • 定理:

        对有等式及不等式约束的问题:
        m i n f ( x ) s . t .   g j ( x ) ≤ 0    ( j = 1 , 2 , . . . , m ) h k ( x ) = 0    ( k = 1 , 2 , . . . , l ) \begin{aligned} &minf(x)\\ s.t.\ &g_j(x)\leq{0}\ \ (j=1,2,...,m)\\ &h_k(x)=0\ \ (k=1,2,...,l) \end{aligned} s.t. minf(x)gj(x)0  (j=1,2,...,m)hk(x)=0  (k=1,2,...,l)
        KKT条件给出判断 x ∗ x^* x是否为最优解的必要条件(当原问题为凸问题时也是必要条件)
        { ∂ f ∂ x i + ∑ j = 1 d u j ∂ g j ∂ x i + ∑ k = 1 l λ k ∂ h k ∂ x i = 0    ( i = 1 , 2 , . . . , n ) h k ( x ) = 0 g j ( x ) ≤ 0 u j g j ( x ) = 0 u j ≥ 0 , λ j ≠ 0 \begin{cases} \frac{\partial{f}}{\partial{x_i}}+\sum_{j=1}^du_j\frac{\partial{g_j}}{\partial{x_i}}+\sum_{k=1}^l\lambda_k\frac{\partial{h_k}}{\partial{x_i}}=0\ \ (i=1,2,...,n)\\ h_k(x)=0\\ g_j(x)\leq{0}\\ u_jg_j(x)=0\\ u_j\geq0,\lambda_j\neq0 \end{cases} xif+j=1dujxigj+k=1lλkxihk=0  (i=1,2,...,n)hk(x)=0gj(x)0ujgj(x)=0uj0,λj=0

      • 推导:见数学推导部分

      • 理解:

        • 相等约束在空间中构成一个曲面,不等约束构成曲面加曲面一侧空间

          svm_kkt_st
        • 对一个满足单约束的点 x ∗ x^* x,其可行方向(在这些方向上移动一点,点仍然近似满足约束)

          • 满足 h ( x ) = 0 h(x)=0 h(x)=0,可行方向为约束曲面在 x ∗ x^* x处的切面 T h T_h Th
          • 满足 g ( x ) ≤ 0 g(x)\leq{0} g(x)0,且 g ( x ∗ ) < 0 g(x^*)<0 g(x)<0,可行方向为全空间
          • 满足 g ( x ) ≤ 0 g(x)\leq{0} g(x)0,且 g ( x ∗ ) = 0 g(x^*)=0 g(x)=0,可行方向为切面 T g T_g Tg(保持为0)与 g ( x ) g(x) g(x)的负梯度方向(约束内部空间)
        • 多约束情况:
          在这里插入图片描述

          • 满足多个约束的点的可行方向是每个约束的可行方向的交集
        • 对最小化 f ( x ) f(x) f(x)问题,满足各约束的 f ( x ) f(x) f(x)的取值空间在函数平面与各约束的交集上,即可行空间由多个约束切面的法向量张成

        • 对满足所有约束的 x ∗ x^* x
          f ( x ∗ ) 的 可 行 方 向 由 ∂ g i ∂ x ∣ x ∗ ( i = 1 , 2 , . . . , m ) 张 成 f(x^*)的可行方向由\frac{\partial{g_i}}{\partial{x}}|_{x^*}(i=1,2,...,m)张成 f(x)xgix(i=1,2,...,m)

        • f ( x ) f(x) f(x) x ∗ x^* x处约束下的梯度为函数梯度与约束切面的法向量的线性组合:
          ∂ f ∂ x + ∑ j = 1 d u j ∂ g j ∂ x \frac{\partial{f}}{\partial{x}}+\sum_{j=1}^du_j\frac{\partial{g_j}}{\partial{x}} xf+j=1dujxgj

        • 由于规定不等约束小于0,而不等式约束梯度指向不等式函数增加方向(球外,大于0),为保证约束条件,规定:
          u j ≤ 0 u_j\leq0 uj0

    • 对偶问题

      • 原始问题
        m i n f ( x ) s . t .   g j ( x ) ≤ 0    ( j = 1 , 2 , . . . , m ) h k ( x ) = 0    ( k = 1 , 2 , . . . , l ) \begin{aligned} &minf(x)\\ s.t.\ &g_j(x)\leq{0}\ \ (j=1,2,...,m)\\ &h_k(x)=0\ \ (k=1,2,...,l) \end{aligned} s.t. minf(x)gj(x)0  (j=1,2,...,m)hk(x)=0  (k=1,2,...,l)

        • 拉格朗日函数

        L ( x , α , β ) = f ( x ) + ∑ i = 1 m α i g i ( x ) + ∑ i = 1 l β i h i ( x ) L(x,\alpha,\beta)=f(x)+\sum_{i=1}^m\alpha_ig_i(x)+\sum_{i=1}^l\beta_ih_i(x) L(x,α,β)=f(x)+i=1mαigi(x)+i=1lβihi(x)

        ​ 定义:
        θ p ( x ) = m a x α , β L ( x , α , β ) \theta_p(x)=\underset{\alpha,\beta}{max}L(x,\alpha,\beta) θp(x)=α,βmaxL(x,α,β)
        ​ 有:
        θ p ( x ) = { f ( x )     ( x 满 足 约 束 ) + ∞     e l s e \theta_p(x)=\begin{cases} f(x)\ \ \ (x满足约束)\\ +\infty\ \ \ else \end{cases} θp(x)={f(x)   (x)+   else
        ​ 因此,极小化问题
        m i n   θ p ( x ) = m i n x   m a x α , β L ( x , α , β ) min\ \theta_p(x)=\underset{x}{min}\ \underset{\alpha,\beta}{max}L(x,\alpha,\beta) min θp(x)=xmin α,βmaxL(x,α,β)
        ​ 称作广义拉格朗日函数的极小极大问题,与约束下极小化问题等价

        • 定义原始问题最优解 P ∗ = m i n x θ p ( x ) P^*=\underset{x}{min}\theta_p(x) P=xminθp(x)
      • 对偶问题:

        • 定义
          θ D ( α , β ) = m i n x   L ( x , α , β ) \theta_D(\alpha,\beta)=\underset{x}{min}\ L(x,\alpha, \beta) θD(α,β)=xmin L(x,α,β)
          极大化:
          m a x α , β θ D ( α , β ) = m a x α , β m i n x   L ( x , α , β ) \underset{\alpha,\beta}{max}\theta_D(\alpha,\beta)= \underset{\alpha,\beta}{max}\underset{x}{min}\ L(x,\alpha, \beta) α,βmaxθD(α,β)=α,βmaxxmin L(x,α,β)
          称作广义拉格朗日函数的极大极小问题,也称作原始问题的对偶问题

        • 对偶问题的最优解 d ∗ = m a x α , β θ D ( α , β ) d^*=\underset{\alpha,\beta}{max}\theta_D(\alpha,\beta) d=α,βmaxθD(α,β)

        • 原始问题与对偶问题关系

          • 若原始问题与对偶问题均有最优值,有:

          d ∗ = m a x α , β m i n x   L ( x , α , β ) ≤ m i n x   m a x α , β L ( x , α , β ) = p ∗ d^*=\underset{\alpha,\beta}{max}\underset{x}{min}\ L(x,\alpha, \beta)\leq{\underset{x}{min}\ \underset{\alpha,\beta}{max}L(x,\alpha,\beta)}=p^* d=α,βmaxxmin L(x,α,β)xmin α,βmaxL(x,α,β)=p

          • α ∗ , β ∗ , x ∗ \alpha^*,\beta^*,x^* α,β,x为原始问题和对偶问题可行解,且 d ∗ = p ∗ d^*=p^* d=p,则 α ∗ , β ∗ , x ∗ \alpha^*,\beta^*,x^* α,β,x是原始问题与对偶问题最优解
          • 假设 f ( x ) f(x) f(x) g i ( x ) g_i(x) gi(x)是凸函数, h i ( x ) h_i(x) hi(x)是仿射函数,有 g i ( x ) < 0 g_i(x)<0 gi(x)<0 ,则存在 α ∗ , β ∗ , x ∗ \alpha^*,\beta^*,x^* α,β,x,使 x ∗ x^* x是原始问题解, α ∗ , β ∗ \alpha^*,\beta^* α,β是对偶问题解

方法推导

  • 硬间隔

    • 根据硬间隔方法定义,优化目标为:

    a r g   m a x w , b   τ s . t .   y i ( w x i ∣ w ∣ + b ∣ w ∣ ) ≥ τ \underset{w,b}{arg\ max}\ \tau\\ s.t.\ y_i(\frac{wx_i}{|w|}+\frac{b}{|w|})\geq\tau w,barg max τs.t. yi(wwxi+wb)τ

    • 由函数间隔定义,目标可改为:
      a r g   m a x W , b   τ ˉ ∣ w ∣ s . t .   y i ( w x i + b ) ≥ τ ˉ \underset{W,b}{arg\ max}\ \frac{\bar{\tau}}{|w|}\\ s.t.\ y_i(wx_i+b)\geq\bar{\tau} W,barg max wτˉs.t. yi(wxi+b)τˉ

    • 由于函数间隔不由点和平面唯一确定,指定距离平面最近的样本点到平面函数距离为1,即 τ ˉ = 1 \bar\tau=1 τˉ=1 ,有:
      a r g   m a x W , b   1 ∣ w ∣ s . t .   y i ( w x i + b ) − 1 ≥ 0 \underset{W,b}{arg\ max}\ \frac{1}{|w|}\\ s.t.\ y_i(wx_i+b)-1\geq0 W,barg max w1s.t. yi(wxi+b)10

    • 该问题又可转化为:
      a r g   m i n w , b   1 2 ∣ w ∣ 2 s . t .   y i ( w x i + b ) − 1 ≥ 0 \underset{w,b}{arg\ min}\ \frac12|w|^2\\ s.t.\ y_i(wx_i+b)-1\geq0 w,barg min 21w2s.t. yi(wxi+b)10

    • 构建广义拉格朗日函数:
      L ( x , α , β ) = 1 2 ∣ w ∣ 2 − ∑ i = 1 n α i y i ( w x i + b ) + ∑ i = 1 n α i L(x,\alpha,\beta)=\frac12|w|^2-\sum_{i=1}^n\alpha_iy_i(wx_i+b)+\sum_{i=1}^n\alpha_i L(x,α,β)=21w2i=1nαiyi(wxi+b)+i=1nαi
      原问题等价于:
      m i n W , b   m a x α L ( w , b , α ) \underset{W,b}{min}\ \underset{\alpha}{max}L(w,b,\alpha) W,bmin αmaxL(w,b,α)
      原问题的对偶问题:
      m a x α   m i n W , b L ( w , b , α ) \underset{\alpha}{max}\ \underset{W,b}{min}L(w,b,\alpha) αmax W,bminL(w,b,α)

    • m i n W , b L ( W , b , α ) \underset{W,b}{min}L(W,b,\alpha) W,bminL(W,b,α)求解:

      • 求偏导,令为0
        L ( x , α , β ) = 1 2 ∣ w ∣ 2 − ∑ i = 1 n α i y i ( w x i + b ) + ∑ i = 1 n α i L(x,\alpha,\beta)=\frac12|w|^2-\sum_{i=1}^n\alpha_iy_i(wx_i+b)+\sum_{i=1}^n\alpha_i L(x,α,β)=21w2i=1nαiyi(wxi+b)+i=1nαi

        { ∇ w L ( w , b , α ) = w − ∑ i = 1 n α i y i x i = 0 ∇ b L ( w , b , α ) = − ∑ i = 1 n α i y i = 0 \begin{cases} \nabla_wL(w,b,\alpha)=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \nabla_bL(w,b,\alpha)=-\sum_{i=1}^n\alpha_iy_i=0 \end{cases} {wL(w,b,α)=wi=1nαiyixi=0bL(w,b,α)=i=1nαiyi=0

      • 得:
        { w = ∑ i = 1 n α i y i x i ∑ i = 1 n α i y i = 0 \begin{cases} w=\sum_{i=1}^n\alpha_iy_ix_i\\ \sum_{i=1}^n\alpha_iy_i=0 \end{cases} {w=i=1nαiyixii=1nαiyi=0
        带入L,有:
        L ( x , α , β ) = 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i x j ) − ∑ i = 1 n ∑ j = 1 n α i y i ( ( ∑ i = 1 n α i y i x i ) x i + b ) + ∑ i = 1 n α i = − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i x j ) + ∑ i = 1 n α i \begin{aligned} L(x,\alpha,\beta)&=\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum_{i=1}^n\sum_{j=1}^n\alpha_iy_i((\sum_{i=1}^n\alpha_iy_ix_i)x_i+b)+\sum_{i=1}^n\alpha_i\\ &=-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_ix_j)+\sum_{i=1}^n\alpha_i \end{aligned} L(x,α,β)=21i=1nj=1nαiαjyiyj(xixj)i=1nj=1nαiyi((i=1nαiyixi)xi+b)+i=1nαi=21i=1nj=1nαiαjyiyj(xixj)+i=1nαi

    • m a x W , b   θ D \underset{W,b}{max}\ \theta_D W,bmax θD
      m a x α   m i n w , b L ( W , b , α ) \underset{\alpha}{max}\ \underset{w,b}{min}L(W,b,\alpha) αmax w,bminL(W,b,α)

      m a x α ( − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i x j ) + ∑ i = 1 n α i ) s . t . ∑ i = 1 n α i y i = 0 α i ≥ 0 \begin{aligned} \underset{\alpha}{max}(-\frac12\sum_{i=1}^n\sum_{j=1}^n&\alpha_i\alpha_jy_iy_j(x_ix_j)+\sum_{i=1}^n\alpha_i)\\ s.t.&\sum_{i=1}^n\alpha_iy_i=0\\ &\alpha_i\geq0 \end{aligned} αmax(21i=1nj=1ns.t.αiαjyiyj(xixj)+i=1nαi)i=1nαiyi=0αi0

      转化为
      m i n α ( 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j ( x i x j ) − ∑ i = 1 n α i ) s . t . ∑ i = 1 n α i y i = 0 α i ≥ 0 \begin{aligned} \underset{\alpha}{min}(\frac12\sum_{i=1}^n\sum_{j=1}^n&\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum_{i=1}^n\alpha_i)\\ s.t.&\sum_{i=1}^n\alpha_iy_i=0\\ &\alpha_i\geq0 \end{aligned} αmin(21i=1nj=1ns.t.αiαjyiyj(xixj)i=1nαi)i=1nαiyi=0αi0
      上述问题也是原始问题的对偶问题

    • 结合对偶问题相关定理,目标函数与约束函数为凸函数,约束严格可行,故存在 α ∗ , w ∗ , b ∗ \alpha^*,w^*,b^* α,w,b使 α ∗ \alpha^* α是原问题的解, w ∗ , b ∗ w^*,b^* w,b是对偶问题的解

    • 因此,有线性可分数据集,已知对偶问题解 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α n ∗ ) \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_n^*) α=(α1,α2,...,αn),即可求得原始问题解 w ∗ , b ∗ w^*,b^* w,b

      由KKT条件:
      { ∇ w L ( w , b , α ) = w − ∑ i = 1 n α i y i x i = 0 ∇ b L ( w , b , α ) = − ∑ i = 1 n α i y i = 0 α i ∗ ( y i ( w ∗ x i + b ∗ ) − 1 ) = 0 y i ( w ∗ x i + b ∗ ) − 1 ≥ 0 α i ∗ ≥ 0 \begin{cases} \nabla_wL(w,b,\alpha)=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \nabla_bL(w,b,\alpha)=-\sum_{i=1}^n\alpha_iy_i=0\\ \alpha_i^*(y_i(w^*x_i+b^*)-1)=0\\ y_i(w^*x_i+b^*)-1\geq0\\ \alpha_i^*\geq0 \end{cases} wL(w,b,α)=wi=1nαiyixi=0bL(w,b,α)=i=1nαiyi=0αi(yi(wxi+b)1)=0yi(wxi+b)10αi0
      得:
      { w ∗ = ∑ i = 1 n α i ∗ y i x i b j ∗ = y j − ∑ i = 1 n α i ∗ y i x i x j        ( j 满 足 α j > 0 ) \begin{cases} w^*=\sum_{i=1}^n\alpha_i^*y_ix_i\\ b_j^*=y_j-\sum_{i=1}^n\alpha_i^*y_ix_ix_j \ \ \ \ \ \ (j满足\alpha_j>0) \end{cases} {w=i=1nαiyixibj=yji=1nαiyixixj      (jαj>0)

    • 对偶问题求解 α ∗ \alpha^* α通过SMO方法完成

  • 软间隔

    为了处理线性不可分情况,修改约束条件,对样本点 x i x_i xi引入松弛变量 ζ i \zeta_i ζi,有:
      y i ( w x i + b ) ≥ 1 − ζ i \ y_i(wx_i+b)\geq1-\zeta_i  yi(wxi+b)1ζi
    优化目标为:
    m i n w , b , ζ 1 2 ∣ w ∣ 2 + C ∑ i = 1 n ζ i s . t .     y i ( w x i + b ) ≥ 1 − ζ i     ( i = 1 , 2 , . . . n ) ζ i ≥ 0 \underset{w,b,\zeta}{min} \frac12|w|^2+C\sum_{i=1}^n\zeta_i\\ s.t.\ \ \ y_i(wx_i+b)\geq1-\zeta_i\ \ \ (i=1,2,...n)\\ \zeta_i\geq0 w,b,ζmin21w2+Ci=1nζis.t.   yi(wxi+b)1ζi   (i=1,2,...n)ζi0
    广义拉格朗日函数:
    L ( w , b , ζ , α , u ) = 1 2 ∣ w ∣ 2 + C ∑ i = 1 n ζ i − ∑ i = 1 n α i ( y i ( w x i + b ) − 1 + ζ i ) − ∑ i = 1 n u i ζ i L(w,b,\zeta,\alpha,u)=\frac12|w|^2+C\sum_{i=1}^n\zeta_i-\sum_{i=1}^n\alpha_i(y_i(wx_i+b)-1+\zeta_i)-\sum_{i=1}^nu_i\zeta_i L(w,b,ζ,α,u)=21w2+Ci=1nζii=1nαi(yi(wxi+b)1+ζi)i=1nuiζi
    目标问题是极小极大问题:
    m i n W , b , ζ   m a x α , u L ( w , b , ζ , α , u ) \underset{W,b,\zeta}{min}\ \underset{\alpha,u}{max}L(w,b,\zeta,\alpha,u) W,b,ζmin α,umaxL(w,b,ζ,α,u)
    对偶问题为极大极小问题:
    m a x α , u   m i n w , b , ζ   L ( w , b , ζ , α , u ) \underset{\alpha,u}{max}\ \underset{w,b,\zeta}{min}\ L(w,b,\zeta,\alpha,u) α,umax w,b,ζmin L(w,b,ζ,α,u)

    • 先求极小 m i n w , b , ζ   L ( w , b , ζ , α , u ) \underset{w,b,\zeta}{min}\ L(w,b,\zeta,\alpha,u) w,b,ζmin L(w,b,ζ,α,u)

      • 令偏导为0
        { ∇ w L ( w , b , ζ , α , u ) = w − ∑ i = 1 n α i y i x i = 0 ∇ b L ( w , b , ζ , α , u ) = − ∑ i = 1 n α i y i = 0 ∇ ζ i L ( w , b , ζ , α , u ) = C − α i − u i = 0 \begin{cases} \nabla_wL(w,b,\zeta,\alpha,u) = w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \nabla_bL(w,b,\zeta,\alpha,u) = -\sum_{i=1}^n\alpha_iy_i=0\\ \nabla_{\zeta_i}L(w,b,\zeta,\alpha,u)=C-\alpha_i-u_i=0 \end{cases} wL(w,b,ζ,α,u)=wi=1nαiyixi=0bL(w,b,ζ,α,u)=i=1nαiyi=0ζiL(w,b,ζ,α,u)=Cαiui=0

      • 得:
        { w = ∑ i = 1 n α i y i x i ∑ i = 1 n α i y i = 0 C − α i − u i = 0 \begin{cases} w=\sum_{i=1}^n\alpha_iy_ix_i \\ \sum_{i=1}^n\alpha_iy_i=0\\ C-\alpha_i-u_i=0 \end{cases} w=i=1nαiyixii=1nαiyi=0Cαiui=0

      • 带回L得:
        L ( w , b , ζ , α , u ) = − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i x j + ∑ i = 1 n α i L(w,b,\zeta,\alpha,u)=-\frac12\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^n\alpha_i L(w,b,ζ,α,u)=21i=1nj=1nαiαjyiyjxixj+i=1nαi
        有约束:
        ∑ i = 1 n α i y i = 0 0 ≤ α i ≤ C \sum_{i=1}^n\alpha_iy_i=0\\ 0\leq\alpha_i\leq{C} i=1nαiyi=00αiC

    • 再对极小求极大,问题为:
      m a x α   ( − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i x j + ∑ i = 1 n α i ) s . t .        ∑ i = 1 n α i y i = 0               0 ≤ α i ≤ C \underset{\alpha}{max}\ (-\frac12\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^n\alpha_i)\\ s.t.\ \ \ \ \ \ \sum_{i=1}^n\alpha_iy_i=0\\ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\leq\alpha_i\leq{C} αmax (21i=1nj=1nαiαjyiyjxixj+i=1nαi)s.t.      i=1nαiyi=0             0αiC
      该问题是原问题的对偶问题

    • 目标函数与约束函数为凸函数,约束严格可行,故存在 α ∗ , w ∗ , b ∗ \alpha^*,w^*,b^* α,w,b使 α ∗ \alpha^* α是原问题的解, w ∗ , b ∗ w^*,b^* w,b是对偶问题的解

      由KKT条件:
      { ∇ w L ( w , b , ζ , α , u ) = w − ∑ i = 1 n α i y i x i = 0 ∇ b L ( w , b , ζ , α , u ) = − ∑ i = 1 n α i y i = 0 ∇ ζ i L ( w , b , ζ , α , u ) = C − α i − u i = 0 α i ∗ ( y i ( w ∗ x i + b ∗ ) − 1 + ζ i ) = 0 u i ζ i = 0   y i ( w x i + b ) − 1 + ζ i ≥ 0 ζ i ≥ 0 ,   α i ≥ 0 ,   u i ≥ 0 \begin{cases} \nabla_wL(w,b,\zeta,\alpha,u) = w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \nabla_bL(w,b,\zeta,\alpha,u) = -\sum_{i=1}^n\alpha_iy_i=0\\ \nabla_{\zeta_i}L(w,b,\zeta,\alpha,u)=C-\alpha_i-u_i=0\\ \alpha_i^*(y_i(w^*x_i+b^*)-1+\zeta_i)=0\\ u_i\zeta_i=0\\ \ y_i(wx_i+b)-1+\zeta_i\geq0\\ \zeta_i\geq0, \ \alpha_i\geq0,\ u_i\geq0\\ \end{cases} wL(w,b,ζ,α,u)=wi=1nαiyixi=0bL(w,b,ζ,α,u)=i=1nαiyi=0ζiL(w,b,ζ,α,u)=Cαiui=0αi(yi(wxi+b)1+ζi)=0uiζi=0 yi(wxi+b)1+ζi0ζi0, αi0, ui0
      在对偶问题解 α ∗ \alpha^* α确定情况下,有:
      w ∗ = ∑ i = 1 n α i y i x i b j ∗ = y j − ∑ i = 1 n y i α i ∗ ( x i x j )    ( 0 < α j < C , u j ≠ 0 , ζ j = 0 ) \begin{aligned} &w^*=\sum_{i=1}^n\alpha_iy_ix_i\\ &b_j^*=y_j-\sum_{i=1}^ny_i\alpha_i^*(x_ix_j)\ \ (0<\alpha_j<C, u_j\neq0,\zeta_j=0) \end{aligned} w=i=1nαiyixibj=yji=1nyiαi(xixj)  (0<αj<C,uj=0,ζj=0)

    • 对偶问题求解 α ∗ \alpha^* α通过SMO方法完成

  • SMO方法

    • 求解目标:

      • α ∗ = ( α 1 ∗ , . . . , a n ∗ ) \alpha^*=(\alpha_1^*,...,a_n^*) α=(α1,...,an)

      m i n α   ( 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( x i x j ) − ∑ i = 1 n α i ) s . t .        ∑ i = 1 n α i y i = 0               0 ≤ α i ≤ C \underset{\alpha}{min}\ (\frac12\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_jK(x_ix_j)-\sum_{i=1}^n\alpha_i)\\ s.t.\ \ \ \ \ \ \sum_{i=1}^n\alpha_iy_i=0\\ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\leq\alpha_i\leq{C} αmin (21i=1nj=1nαiαjyiyjK(xixj)i=1nαi)s.t.      i=1nαiyi=0             0αiC

    • 基本思路:

      • α ∗ \alpha^* α中所有变量解都满足KKT条件,则 α ∗ \alpha^* α满足KKT条件
      • SMO算法将原问题不断分为子问题并对其求解
      • 每个子问题更新时指定两个变量,一个是违反KKT条件最严重的变量 α 1 \alpha_1 α1,另一个由 α 2 = − y 1 ∑ i ≠ 2 α i y i \alpha_2=-y_1\sum_{i\neq2}\alpha_iy_i α2=y1i=2αiyi确定
    • 变量更新:

      • 选取一对变量 α 1 , α 2 \alpha_1,\alpha_2 α1,α2

      • 优化目标:
        m i n α 1 , α 2    W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 n y i α i K i 1 + y 2 α 2 ∑ i = 3 n y i α i K i 2 s . t .    α 1 y 1 + α 2 y 2 = − ∑ i = 3 n y i α i = ζ 0 ≤ α i ≤ C \underset{\alpha_1,\alpha_2}{min}\ \ W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_{2}-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^ny_i\alpha_iK_{i2}\\ s.t.\ \ \alpha_1y_1+\alpha_2y_2=-\sum_{i=3}^ny_i\alpha_i=\zeta\\ 0\leq\alpha_i\leq{C} α1,α2min  W(α1,α2)=21K11α12+21K22α22+y1y2K12α1α2(α1+α2)+y1α1i=3nyiαiKi1+y2α2i=3nyiαiKi2s.t.  α1y1+α2y2=i=3nyiαi=ζ0αiC

      • α 1 , α 2 \alpha_1,\alpha_2 α1,α2之间的约束关系可表示为:

        在这里插入图片描述

        两个变量存在限制,因此两变量优化问题实际上是单变量优化问题,假设对 α 2 \alpha_2 α2进行优化,上一轮解为 α 1 o l d , α 2 o l d \alpha_1^{old},\alpha_2^{old} α1old,α2old,假设沿着约束方向未根据约束剪切的解是 α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc,本轮结果 α 1 n e w , α 2 n e w \alpha_1^{new},\alpha_2^{new} α1new,α2new

        假设L,H分别为 α 2 n e w \alpha_2^{new} α2new所在线段的边界,有 L < α 2 n e w < H L<\alpha_2^{new}<H L<α2new<H

        若是左图中的情况( y 1 , y 2 y_1,y_2 y1,y2不一致),
        L = m a x ( 0 , α 2 o l d − α 1 o l d ) ,   H = m i n ( C , C + α 2 o l d − α 1 o l d ) L=max(0,\alpha_2^{old}-\alpha_1^{old}),\ H=min(C,C+\alpha_2^{old}-\alpha_1^{old}) L=max(0,α2oldα1old), H=min(C,C+α2oldα1old)
        若是右图中的情况( y 1 , y 2 y_1,y_2 y1,y2一致),
        L = m a x ( 0 , α 2 o l d + α 1 o l d − C ) ,   H = m i n ( C , α 2 o l d + α 1 o l d ) L=max(0,\alpha_2^{old}+\alpha_1^{old}-C),\ H=min(C,\alpha_2^{old}+\alpha_1^{old}) L=max(0,α2old+α1oldC), H=min(C,α2old+α1old)
        有:
        α 2 n e w = { H                   α 2 n e w , u n c > H α 2 n e w , u n c         L < α 2 n e w , u n c < H L                   α 2 n e w , u n c < L \alpha_2^{new}=\begin{cases} H \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha_2^{new,unc}>H\\ \alpha_2^{new,unc}\ \ \ \ \ \ \ L<\alpha_2^{new,unc}<H\\ L \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \alpha_2^{new,unc}<L \end{cases} α2new=H                 α2new,unc>Hα2new,unc       L<α2new,unc<HL                 α2new,unc<L

      • α 2 n e w , u n c \alpha_2^{new,unc} α2new,unc求解

        • 定义:

        g ( x ) = ∑ j = 1 m α j ∗ y j K ( x j , x i ) + b E i ( x ) = g ( x i ) − y i v i = ∑ i = 3 n y j α j K ( x i , x j ) = g ( x i ) − ∑ i = 1 2 α j ∗ y j K ( x j , x i ) − b \begin{aligned} &g(x)=\sum_{j=1}^m\alpha_j^*y_jK(x_j,x_i)+b\\ &E_i(x)=g(x_i)-y_i\\ &v_i=\sum_{i=3}^ny_j\alpha_jK(x_i,x_j)=g(x_i)-\sum_{i=1}^2\alpha_j^*y_jK(x_j,x_i)-b \end{aligned} g(x)=j=1mαjyjK(xj,xi)+bEi(x)=g(xi)yivi=i=3nyjαjK(xi,xj)=g(xi)i=12αjyjK(xj,xi)b

        • 目标函数简化为:
          W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 v 1 + y 2 α 2 v 2 W(\alpha_1,\alpha_2)=\frac12K_{11}\alpha_1^2+\frac12K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1v_1+y_2\alpha_2v_2 W(α1,α2)=21K11α12+21K22α22+y1y2K12α1α2(α1+α2)+y1α1v1+y2α2v2

        • 由:
          α 1 y 1 + α 2 y 2 = ζ y i 2 = 1 \alpha_1y_1+\alpha_2y_2=\zeta\\ y_i^2=1 α1y1+α2y2=ζyi2=1
          有:
          α 1 = y 1 ( ζ − α 2 y 2 ) \alpha_1=y_1(\zeta-\alpha_2y_2) α1=y1(ζα2y2)

        • 再带入目标,消除 α 1 \alpha_1 α1
          W ( α 2 ) = 1 2 K 11 ( y 1 ( ζ − α 2 y 2 ) ) 2 + 1 2 K 22 α 2 2 + y 2 K 12 α 2 ( ζ − α 2 y 2 ) − y 1 ( ζ − α 2 y 2 ) − α 2 + ( ζ − α 2 y 2 ) v 1 + y 2 α 2 v 2 W(\alpha_2)=\frac12K_{11}(y_1(\zeta-\alpha_2y_2))^2+\frac12K_{22}\alpha_2^2+y_2K_{12}\alpha_2(\zeta-\alpha_2y_2)-y_1(\zeta-\alpha_2y_2)-\alpha_2+(\zeta-\alpha_2y_2)v_1+y_2\alpha_2v_2 W(α2)=21K11(y1(ζα2y2))2+21K22α22+y2K12α2(ζα2y2)y1(ζα2y2)α2+(ζα2y2)v1+y2α2v2
          α 2 \alpha_2 α2求导,令为0:
          ∂ W ∂ α 2 = K 11 α 2 + K 22 α 2 − 2 K 12 α 2 − K 11 ζ y 2 + K 12 ζ y 2 + y 1 y 2 − 1 − v 1 y 2 + v 2 y 2 = 0 \frac{\partial{W}}{\partial\alpha_2}=K_{11}\alpha_2+K_{22}\alpha_2-2K_{12}\alpha_2-K_{11}\zeta{y_2}+K_{12}\zeta{y_2+y_1y_2}-1-v_1y_2+v_2y_2=0 α2W=K11α2+K22α22K12α2K11ζy2+K12ζy2+y1y21v1y2+v2y2=0
          再带入 α 1 y 1 + α 2 y 2 = ζ \alpha_1y_1+\alpha_2y_2=\zeta α1y1+α2y2=ζ,求解得:
          α 2 n e w , u n c = α 2 o l d + y 2 ( E 1 − E 2 ) K 11 + K 22 − 2 K 12 \alpha_2^{new,unc}=\alpha_2^{old}+\frac{y2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}} α2new,unc=α2old+K11+K222K12y2(E1E2)

      • 阈值与差值更新:

        • 完成两个变量的优化之后,需要重新计算阈值b

        • 0 < α 1 n e w < C 0<\alpha_1^{new}<C 0<α1new<C有: y 1 − ∑ i = 1 n α i y i K i 1 − b 1 = 0 y_1-\sum_{i=1}^n\alpha_iy_iK_{i1}-b_1=0 y1i=1nαiyiKi1b1=0

        • 新的 b 1 n e w b_1^{new} b1new E 1 E_1 E1
          b 1 n e w = y 1 − ∑ i = 3 n α i y i K i 1 − α 1 n e w y 1 K 11 − α 2 n e w y 2 K 21 b_1^{new}=y_1-\sum_{i=3}^n\alpha_iy_iK_{i1}-\alpha_1^{new}y_1K_{11}-\alpha_2^{new}y_2K_{21} b1new=y1i=3nαiyiKi1α1newy1K11α2newy2K21

          E 1 = g ( x 1 ) − y 1 = α 1 o l d y 1 K 11 + α 2 o l d y 2 K 21 + ∑ i = 3 n α i y i K i 1 + b o l d − y 1 E_1=g(x_1)-y_1=\alpha_1^{old}y_1K_{11}+\alpha_2^{old}y_2K_{21}+\sum_{i=3}^n\alpha_iy_iK_{i1}+b^{old}-y_1 E1=g(x1)y1=α1oldy1K11+α2oldy2K21+i=3nαiyiKi1+boldy1

          b 1 n e w = − E 1 − y 1 K 11 ( α 1 n e w − α 2 o l d ) − y 2 K 21 ( α 2 n e w − α 2 o l d ) + b o l d b_1^{new}=-E_1-y_1K_{11}(\alpha_1^{new}-\alpha_2^{old})-y_2K_{21}(\alpha_2^{new}-\alpha_2^{old})+b^{old} b1new=E1y1K11(α1newα2old)y2K21(α2newα2old)+bold

        • 同样, 0 < α 2 n e w < C 0<\alpha_2^{new}<C 0<α2new<C时有 b 2 n e w b_2^{new} b2new
          b 2 n e w = − E 2 − y 1 K 12 ( α 1 n e w − α 1 o l d ) − y 2 K 22 ( α 2 n e w − α 2 o l d ) + b o l d b_2^{new}=-E_2-y_1K_{12}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b^{old} b2new=E2y1K12(α1newα1old)y2K22(α2newα2old)+bold

        • b n e w = b 1 n e w + b 2 n e w 2 b^{new}=\frac{b_1^{new}+b_2^{new}}{2} bnew=2b1new+b2new

        • 更新 E i E_i Ei
          E i = ∑ 支 持 向 量 y j α j K ( x i , x j ) + b n e w − y i E_i=\sum_{支持向量}y_j\alpha_jK(x_i,x_j)+b^{new}-y_i Ei=yjαjK(xi,xj)+bnewyi

    • 变量选择:

      • 第一个变量:

        检测样本 ( x i , y i ) (x_i,y_i) (xi,yi)是否满足KKT条件:
        { α i = 0   < = >   y i ( ∑ j = 1 n α j y j K ( x j x i ) + b ) ≥ 1         ( 间 隔 外 ) 0 < α i < C   < = >   y i ( ∑ j = 1 n α j y j K ( x j x i ) + b ) = 1         ( 间 隔 边 界 上 的 支 持 向 量 ) α i = C   < = >   y i ( ∑ j = 1 n α j y j K ( x j x i ) + b ) ≤ 1         ( 间 隔 内 ) \begin{cases} \begin{aligned} \alpha_i=0 \ &<=> \ y_i(\sum_{j=1}^n\alpha_jy_jK(x_jx_i)+b)\geq1\ \ \ \ \ \ \ (间隔外)\\ 0<\alpha_i<C\ &<=>\ y_i(\sum_{j=1}^n\alpha_jy_jK(x_jx_i)+b)=1\ \ \ \ \ \ \ (间隔边界上的支持向量)\\ \alpha_i=C\ &<=>\ y_i(\sum_{j=1}^n\alpha_jy_jK(x_jx_i)+b)\leq1\ \ \ \ \ \ \ (间隔内) \end{aligned} \end{cases} αi=0 0<αi<C αi=C <=> yi(j=1nαjyjK(xjxi)+b)1       ()<=> yi(j=1nαjyjK(xjxi)+b)=1       ()<=> yi(j=1nαjyjK(xjxi)+b)1       ()
        优先选间隔超平面上的点(支持向量),若这些点都满足KKT条件,再选其他违反KKT条件的点

      • 第二个变量:

        假设我们在外层循环已经找到了 α 1 \alpha_1 α1, 第二个变量 α 2 \alpha_2 α2的选择标准是让 ∣ E 1 − E 2 ∣ |E_1-E_2| E1E2尽可能大,即当 E 1 E_1 E1正时选最小的 E i E_i Ei,否则选最大 E i E_i Ei

    • SMO流程

      • 取初值 α 0 = 0 , k = 0 \alpha^0=0,k=0 α0=0,k=0
      • 选取 α 1 k , α 2 k \alpha_1^k,\alpha_2^k α1k,α2k
      • 计算 α 2 k + 1 , α 1 k + 1 \alpha_2^{k+1},\alpha_1^{k+1} α2k+1,α1k+1
      • 计算 b k + 1 b^{k+1} bk+1 E i E_i Ei
      • 若对所有 α i \alpha_i αi均满足KKT条件,结束,否则回到第二步
  • 多分类:

    • SVM方法是基于几何的方法,只能通过多个分割平面组合来解决多分类问题,有OVO,OVA两种方案

    • OVO(One Vs One)

      • 对于每两类之间,都求一个分割超平面(求K(K-1)/2个平面*)

        在这里插入图片描述

      • 在判断样本分类情况时,对所有的分割平面都进行一次判断,投票决定分类(进行K(K-1)/2次判断*)

    • OVA(One Vs All)

      • 对每一类样本,都视作本类与非本类的二分类问题,求一个分割平面(整个样本集求K个平面

      在这里插入图片描述

      • 判断样本分类时,对所有的分割平面都进行一次判断,投票决定分类(进行K次判断
    • 二者相比,OVO方法无法判断的区域比OVA方法小,更加准确,但计算量更大

方法流程

  • 输入数据集 X = [ x 1 , x 2 , . . . , x n ] X=[x_1,x_2,...,x_n] X=[x1,x2,...,xn],标签 L = [ y 1 , y 2 , . . . , y n ] L=[y_1,y_2,...,y_n] L=[y1,y2,...,yn]

  • 选择惩罚系数C,构造约束优化问题:
    m i n α   ( 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i x j + ∑ i = 1 n α i ) s . t .        ∑ i = 1 n α i y i = 0               0 ≤ α i ≤ C \underset{\alpha}{min}\ (\frac12\sum_{i=1}^n\sum_{j=1}^n \alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^n\alpha_i)\\ s.t.\ \ \ \ \ \ \sum_{i=1}^n\alpha_iy_i=0\\ \ \ \ \ \ \ \ \ \ \ \ \ \ 0\leq\alpha_i\leq{C} αmin (21i=1nj=1nαiαjyiyjxixj+i=1nαi)s.t.      i=1nαiyi=0             0αiC

  • SMO算法求出目标最小时 α ∗ \alpha^* α

  • 计算 w ∗ =