【直观详解】支持向量机SVM | Go Further | Stay Hungry, Stay Foolish

【阅读时间】13min - 19min
【内容简介】详解解读什么是支持向量机，如何解支持向量以及涉及的拉普拉斯乘子法，还有核方法的解读

[](#%E4%BB%80%E4%B9%88%E6%98%AF%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA-SVM "什么是支持向量机-SVM")什么是支持向量机-SVM

支持向量机-SVM(Support Vector Machine)从本质来说是一种：用一条线（方程）分类两种事物

SVM的任务是找到这条分界线使得它到两边的margin都最大，注意，这里的横坐标是 x1x1 纵坐标为 x2x2，如下图所示

margin

margin

有了直观的感知，在定义这一节在做一些深入的思考，分解名词（Support Vector Machine）并尝试解释：

  • Machine - Classification Machine 说明它的本质是一个分类器
  • Support Vector - 如上图所示，在Maximum Margin上的这些点就是支持向量，具体说即最终分类器表达式中只含有这些支持向量的信息，而与其他数据点无关。在下面的公式中，只有支持向量的系数 αiαi 不等于0。说人话，上图中两个红色的点，一个蓝色的点，合起来就是支持向量 w⋅φ(x)=∑iλiyik(xi,x)w⋅φ(x)=∑iλiyik(xi,x)
公式中每一个符号的含义在后文有说明

[](#%E5%A6%82%E4%BD%95%E6%B1%82%E8%A7%A3%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA "如何求解支持向量机")如何求解支持向量机

对于我们需要求解的这个超平面（直线）来说，我们知道

  • 它离两边一样远（待分类的两个部分的样本点）
  • 最近的距离就是到支持向量中的点的距离

根据这两点，抽象SVM的直接表达（Directly Representation）

注：argmaxxf(x)argmaxx⁡f(x) 表示当 f(x)f(x) 取最大值时，x的取值

argmaxboundarymargin(boundary)所有正确归类的两类到boundary的距离≥margin(1)(1)argmaxboundary⁡margin(boundary)所有正确归类的两类到boundary的距离≥margin

其实这个公式是一点也不抽象，需要更进一步的用符号来表达。

我们知道在准确描述世界运行的规律这件事上，数学比文字要准确并且无歧义的多，文字（例子）直观啰嗦，数学（公式）准确简介

[](#%E7%A1%AC%E9%97%B4%E9%9A%94 "硬间隔")硬间隔

SVM支持向量机

SVM支持向量机

注：公式中加粗或者带有向量箭头的都表达一个向量
  • 假设这些数据线性可分，也可称为硬间隔（Hard Margin）
  • 首先定义超平面：wT→xi+b=0wTx→i+b=0，接下来为了方便，设 →x=(x1,x2)x→=(x1,x2) 即一条直线
  • 任意点 →xix→i 到该直线的距离为 1∥w∥(wT→xi+b)1‖w‖(wTx→i+b)
  • 对于空间内所有训练点的坐标记为 (→xi,yi)(x→i,yi)，其中 yiyi = 1 or -1， 表示点 →xix→i 所属的类
  • 如果这些训练数据是线性可分的，选出两条直线（上图中的虚线），使得他们的距离尽可能的大，这两条直线的中央就是待求的超平面（直线）

  • 为了表达直观，我们定义这两个超平面（直线）分别为 wT→xi+b=1wTx→i+b=1 和 wT→xi+b=−1wTx→i+b=−1，两个超平面（直线）之间的距离为 γ=2∥w∥γ=2‖w‖

    注：选择1的好处是，w 和b进行尺缩变换（kw和kb）不改变距离，方便计算

  • 为了使得所有样本数据都在间隔区（两条虚线）以外，我们需要保证对于所有的 ii 满足下列的条件

    • wT→xi+b⩾1wTx→i+b⩾1 若 yi=1yi=1
    • wT→xi+b⩽−1wTx→i+b⩽−1 若 yi=−1yi=−1
  • 上述两个条件可以写作 yi(wT→xi+b)⩾1,for all 11⩽i⩽nyi(wTx→i+b)⩾1,for all 11⩽i⩽n 这里的n指样本点的数量
  • 上面的表达（Directly Representation）可以被写成

    argmaxw,b{1∥w∥minn[yi(wT→xi+b)]}(2)(2)argmaxw,b⁡{1‖w‖minn⁡[yi(wTx→i+b)]}

  • 最终目的是找到具有“最大间隔”（Maximum Margin）的划分超平面（直线），找到参数 ww 和 bb 使得 γγ 最大
  • 则可以对(2)式进行形式变换，得到 canonical representation argmaxw,b2∥w∥⟹argminw,b12∥w∥2s.t.yi(wT→xi+b)⩾1,i=1,2,…,m(3)(3)argmaxw,b⁡2‖w‖⟹argminw,b⁡12‖w‖2s.t.yi(wTx→i+b)⩾1,i=1,2,…,m
注：s.t. ：subject to 表示约束条件，表达的意思等价于：为了使得所有样本数据都在间隔区（两条虚线）以外

为了解(3)式，需要用到拉格朗日乘子法（Method of lagrange multiplier），它是用来求解在约束条件目标函数的极值的，详细直观详解

注：以下解算过程希望完全看懂强烈建议理解阅读详细直观详解，很多地方推导过程只写必要过程及结论

根据约束的形式，我们引入m个拉格朗日乗法子，记为 λ=(λ1,…,λm)Tλ=(λ1,…,λm)T ，原因是，有m个约束，所以需要m个拉格朗日乗法子。可以得出拉格朗日方程如下：
L(w,b,λ)=12∥w∥2−m∑i=1λi{yi(wT→xi+b)−1}(4)(4)L(w,b,λ)=12‖w‖2−∑i=1mλi{yi(wTx→i+b)−1}

解这个拉格朗日方程，对 ww 和 bb 求偏导数，可以得到以下两个条件
w=m∑i=1λiyi→xi0=m∑i=1λiyiw=∑i=1mλiyix→i0=∑i=1mλiyi

将这两个条件带回公式(4)，可以得到对偶形式（dual representaiton），我们的目的也变为最大化 L(λ)L(λ)，表达式如下
argmaxλL(λ)=m∑i=1λi−12m∑i=1m∑j=1λiλj→xi→xjxTixjs.t.λi⩾0,∀i;m∑i=1λiyi=0(5)(5)argmaxλ⁡L(λ)=∑i=1mλi−12∑i=1m∑j=1mλiλjx→ix→jxiTxjs.t.λi⩾0,∀i;∑i=1mλiyi=0

以上表达式可以通过二次规划算法解出 λλ 后，带回，求出ww 和 bb，即可得到模型
f(x)=wTx+b=m∑i=1λiyixTix+b(6)(6)f(x)=wTx+b=∑i=1mλiyixiTx+b

补充一些关于二次规划算法的相关，(3)式的约束是一个不等式约束，所以我们可以使用KKT条件得到三个条件：
λi⩾0;yif(xi)−1⩾0;λi{yif(xi)−1}=0λi⩾0;yif(xi)−1⩾0;λi{yif(xi)−1}=0

使用这些条件，可以构建高效算法来解这个方程，比如SMO（Sequential Minimal Optimization）就是其中一个比较著名的。至于SMO是如何做的，考虑到现代很多SVM的Pakage都是直接拿来用，秉承着前人付出了努力造了轮子就不重复造的核心精神，直接调用就好

[](#%E8%BD%AF%E9%97%B4%E9%9A%94 "软间隔")软间隔

已经说明了如何求得方程，以上的推导形式都是建立在样本数据线性可分的基础上，如果样本数据你中有我我中有你（线性不可分），应该如何处理呢？这里就需要引入软间隔（Soft Margin），意味着，允许支持向量机在一定程度上出错

SoftMargin

由上一节我们得知，约束为： yi(wT→xi+b)⩾1,i=1,2,…,myi(wTx→i+b)⩾1,i=1,2,…,m ，目标是使目标函数可以在一定程度不满足这个约束条件，我们引入常数 CC 和 损失函数 ℓ0/1(z)ℓ0/1(z) 为0/1损失函数，当z小于0函数值为1，否则函数值为0
minw,b12∥w∥2+Cm∑i=1ℓ0/1(yi(wT→xi+b)−1)(7)(7)minw,b⁡12‖w‖2+C∑i=1mℓ0/1(yi(wTx→i+b)−1)

对于(7)式来说 C⩾0C⩾0 是个常数，当C无穷大时，迫使所有样本均满足约束；当C取有限值时，允许一些样本不满足约束

但 ℓ0/1(z)ℓ0/1(z) 损失函数非凸、非连续，数学性质不好，不易直接求解，我们用其他一些函数来代替它，叫做替代损失函数（surrogate loss）
hinge损失:ℓhinge(z)=max(0,1−z)指数损失:ℓexp(z)=e−z对数损失:ℓlog(z)=log(1+e−z)hinge损失:ℓhinge(z)=max(0,1−z)指数损失:ℓexp(z)=e−z对数损失:ℓlog(z)=log(1+e−z)
三种常见损失函数如下图

损失函数

为了书写方便，我们引入松弛变量（slack variables）: ξi⩾0ξi⩾0，可将(7)式重写为
minw,b,ξi12∥w∥2+Cm∑i=1ξis.t.yi(wT→xi+b)⩾1−ξi;ξi⩾0,i=1,2,…,m(8)(8)minw,b,ξi⁡12‖w‖2+C∑i=1mξis.t.yi(wTx→i+b)⩾1−ξi;ξi⩾0,i=1,2,…,m
(8)式就是常见的软间隔支持向量机，其中，每一个样本都有一个对应的松弛变量，用以表征该样本不满足约束的程度，求解的方法同理硬间隔支持向量机

[](#%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA%E6%89%A9%E5%B1%95 "支持向量机扩展")支持向量机扩展

[](#%E6%A0%B8%E6%96%B9%E6%B3%95 "核方法")核方法

以上我们求解的支持向量机都是在线性情况下的，那么非线性情况下如何处理？这里就引入：核方法

对于这样的问题，可以将样本从原始空间映射到一个更高为的特征空间，使得样本在这个特征空间内线性可分，直观可视化解释

为了完成这个目的，令 ϕ(x)ϕ(x) 表示将 xx 映射后的特征向量，于是，在特征空间划分超平面所对应的模型可表示为：
f(x)=wTϕ(x)+bf(x)=wTϕ(x)+b

同理上文中引入拉格朗日乘子，求解整个方程后可得
f(x)=wTϕ(x)+b=m∑i=1λiyiϕ(xi)Tϕ(x)+b=m∑i=1λiyik(x,xi)+bf(x)=wTϕ(x)+b=∑i=1mλiyiϕ(xi)Tϕ(x)+b=∑i=1mλiyik(x,xi)+b

这里的函数 k(⋅,⋅)k(⋅,⋅) 就是核函数（kernel function），常见的核函数见下表

名称

表达式

参数

线性核

xTixjxiTxj

无

多项式核

(xTixj)d(xiTxj)d

d⩾1d⩾1 多项式次数

高斯核

exp(−∥xi−xj∥22σ2)exp(−‖xi−xj‖22σ2)

σ>0σ>0 高斯核带宽

拉普拉斯核

exp(−∥xi−xj∥2σ)exp(−‖xi−xj‖2σ)

σ>0σ>0

Sigmoid核

tanh(βxTixj+θ)tanh(βxiTxj+θ)

β>0β>0 θ>0θ>0

也可以通过函数组合得到这些值

[](#%E5%A4%9A%E7%B1%BB%E9%97%AE%E9%A2%98 "多类问题")多类问题

多类问题可以使用两两做支持向量机，再由所有的支持向量机投票选出这个类别的归属，被称为one-versus-one approace。

Reference
知乎各类回答
Wiki百科
PRML
周志华-机器学习

Original url: Access
Created at: 2018-11-26 10:26:27
Category: default
Tags: none

未标明原创文章均为采集，版权归作者所有，转载无需和我联系，请注明原出处，南摩阿彌陀佛，知识，不只知道，要得到

请先后发表评论
  • 最新评论
  • 总共0条评论