【机器学习】支持向量机详解,附带案例

2019年12月04日 阅读数:466
这篇文章主要向大家介绍【机器学习】支持向量机详解,附带案例,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

前言

\quad\quad 支持向量机基本思想就是 间隔最大化,看上去很简单,可是要想理解它并非很容易。本篇将由基本概念出发,对公式进行推导,而后经过一些案例加以展现来介绍支持向量机。本篇篇幅比较长,需耐心仔细看完,适当动手跟着推导及代码实现。html

因为博主也在学习中,因此本篇中不免会有些理解错误的地方,还望你们赐教,共同窗习。git

本篇的代码可见:Githubgithub

1、SVM 涉及的概念

\quad\quad 支持向量机(support vector machines,SVM)是一种二类分类模型。它的 基本模型定义在特征空间上的间隔最大的线性分类器,支持向量机的学习策略就是间隔最大化,可形式化为求解凸二次规划的问题web

一、分类任务

\quad\quad 分类任务就是肯定对象属于哪一个预约义的目标类。分类任务的输入数据是记录的集合,每条记录也称为实例或样例,用元祖 ( x , y ) (x,y) 表示,其中 x x 是属性的集合, y y 是类标记(也称目标属性)。在回归模型中,目标属性值是连续的;而在分类模型中,目标属性时离散的。算法

考虑二分类任务,其目标属性为 y { 0 , 1 } y \in \{0,1\} ,而线性回归模型参数的预测值 z = w T x + b z = w^Tx+b 是实值,因而咱们须要将实值 z z 转换为目标属性值 0 或 1 。固然最理想的就是单位阶跃函数,可是单位阶跃函数不连续,因而使用 sigmoid函数 做为替代函数。缓存

在这里插入图片描述

sigmoid函数 表达式以下:
g ( z ) = 1 1 + e z g(z) = \frac{1}{1 + e^{-z}} app

Logistic回归 目的是从特征中学习出一个 0/1 分类模型,而这个分类模型是将特征的线性组合做为自变量,因为自变量的取值范围是 ( , + ) (-\infty, + \infty) 。所以,使用 sigmoid函数 将自变量映射到 ( 0 , 1 ) (0,1) 上,映射后的值被认为是属于 y = 1 y = 1 的几率。dom

假设函数为:
h θ ( x ) = g ( θ T x ) = 1 1 + e θ T x h_\theta(x) = g(\theta^Tx) = \frac{1}{1 + e^{-\theta^Tx}} ide

根据 sigmoid函数 的特性,假设:
p ( y = 1 x ; θ ) = h θ ( x ) p(y=1|x;\theta) = h_{\theta}(x)
p ( y = 0 x ; θ ) = 1 h θ ( x ) p(y=0|x;\theta) =1 - h_{\theta}(x) svg

上式表示,已知样本 x x 和参数 θ \theta 的状况下,样本 x x 属于正样本 ( y = 1 y = 1 )和负样本( y = 0 y = 0 )的条件几率。若 h θ ( x ) > 0.5 h_\theta(x) > 0.5 则属于正样本,反之属于负样本。

进一步的, h θ ( x ) h_\theta(x) 只和 θ T x \theta^Tx 有关, θ T x > 0 \theta^Tx>0 ,那么 h θ ( x ) > 0.5 h_\theta(x) > 0.5 ,而 g ( z ) g(z) 只是用来映射的,真实的类别决定权在于 θ T x \theta^Tx 。当 θ T x 0 \theta^Tx \gg 0 时, h θ ( x ) h_\theta(x) 趋于1,反之趋于0。若是咱们只从 θ T x \theta^Tx 出发,那么模型应该尽量的让训练数据中 y = 1 y =1 的特征 θ T x 0 \theta^Tx \gg 0 ,而 y = 0 y = 0 的特征 θ T x 0 \theta^Tx \ll 0

Logistic回归 就是要学习获得参数 θ \theta ,使得正例的特征远远大于0,负例的特征远远小于0,并且要在所有训练数据上达到这个目标。

接下来,尝试把 Logistic回归 作个变形:

  • 首先将目标属性 y { 0 , 1 } y \in \{0,1\} 替换为 y { 1 , 1 } y \in \{-1,1\}
  • θ T x = θ 0 + θ 1 x 1 + θ 2 x 2 + . . . + θ n x n \theta^Tx = \theta_0 + \theta_1 x_1+ \theta_2 x_2+...+ \theta_n x_n θ 0 \theta_0 替换为 b b
  • 最后将 θ 1 x 1 + θ 2 x 2 + . . . + θ n x n \theta_1 x_1+ \theta_2 x_2+...+ \theta_n x_n 替换为 w T x = θ 1 x 1 + θ 2 x 2 + . . . + θ n x n w^Tx = \theta_1 x_1+ \theta_2 x_2+...+ \theta_n x_n
  • 获得 θ T x = w T x + b \theta^Tx =w^Tx +b

就是说,除了 y y 由 0 变为 -1,线性分类函数跟 Logistic回归 的形式化表示 h θ ( x ) = g ( θ T x ) = g ( w T x + b ) h_\theta(x) = g(\theta^Tx) = g(w^Tx +b) 没区别。

将假设函数 h w , b ( x ) = g ( w T x + b ) h_{w,b}(x) = g(w^Tx+b) 中的 g ( z ) g(z) 作一个简化,将其映射到 y = 1 y = -1 y = 1 y = 1 上,映射以下:
g ( z ) = { 1 , z 0 1 , z < 0 g(z) = \begin{cases} 1,& z \geqslant 0 \\ -1, & z < 0 \end{cases}

二、线性分类器

线性可分数据集:存在某个超平面S可以将数据集的正实例和负实例彻底划分到超平面的两侧,则称为线性可分数据集;不然,线性不可分。

在这里插入图片描述

如上图,这些数据就是线性可分的,因此能够用一条直线将这两类数据分开,二维中是一条直线,在多维中就是一个超平面。

这个超平面能够用分类函数 f ( x ) = w T x + b f(x) = w^Tx + b 表示,在进行分类时,将 x x 代入 f ( x ) f(x) 中,若是 f ( x ) = 0 f(x) = 0 表示数据点在超平面上; f ( x ) > 0 f(x) > 0 对应 y = 1 y =1 的数据点; f ( x ) < 0 f(x) < 0 对应 y = 1 y=-1 的数据点。

三、SVM 在作什么?

在这里插入图片描述

\quad\quad 假定给定数据如上图,圆的为正类,方的为负类,要想经过一个划分超平面(这里是二维,因此是条直线)将不一样类别的样本分开。从图中咱们就能够看出,能将训练样本分开的划分超平面可能有不少,可是咱们应该去选择哪个呢?

\quad\quad 直观上,咱们应该选择中间红色的那个,由于它对于训练样本局部扰动的“容忍”性最好,好比,训练集外的样本可能比图中的样本更接近两类的划分超平面,这将使许多划分超平面出现错误,而红色的超平面受到的影响是最小的,也就是说,这个划分超平面的分类结果是最鲁棒的,对未知示例的泛化能力最强。

\quad\quad 找出这个划分超平面就成了关键,以前咱们介绍的 感知机(点击连接) 也是寻找这个超平面,将训练集划分开,可是感知机利用误分类最小的策略,求得划分超平面,并且解有无穷多个;在全部的划分超平面中,有一个平面是最好的,它能够尽量地让全部的样本点都离该划分超平面最远,这就是 SVM 要作的。

四、函数间隔

在这里插入图片描述

如图,有三个实例 A B C A、B、C 均在划分超平面的正类一侧,预测它们的类,点 A A 距离超平面较远,若预测为正类,就比较确信预测是正确的;点 C C 距离超平面较近,若预测为正类就不那么确信了;点 B B 介于 A C A、C 之间,预测其为正类的确信度也在 A C A、C 之间。

通常来讲,一个点距离超平面的远近能够相对地表示分类预测的确信程度。

咱们注意到:当一个点 x x 被正确预测时,那么 w x + b wx+b 的符合与类标记 y y 的符号相同。

因此可用 y ( w x + b ) y(w\cdot x+b) 来表示分类的正确性及确信度。

对于给定的训练数据集 T T 和超平面 ( w , b ) (w,b)
(1)定义超平面 ( w , b ) (w,b) 关于样本点 ( x i , y i ) (x_i,y_i) 函数间隔 为:

δ i = y i ( w x i + b ) \delta_i = y_i(w \cdot x_i+b)

(2)定义超平面 ( w , b ) (w,b) 关于训练数据集 T T 的函数间隔为超平面 $(w,b) $关于 T T 中全部样本点 ( x i , y i ) (x_i,y_i) 的函数间隔之最小值,即:

δ = min i = 1 , 2 , . . . , N δ i \delta = \min_{i = 1,2,...,N}\delta_i

函数间隔能够表示分类预测的正确性和确信度

五、几何间隔(点到超平面距离)

样本空间中任意点 x x 到超平面 ( w , b ) (w,b) 的距离可写为:

r = w T x + b w r = \frac{|w^Tx+b|}{||w||}

补充:

x 0 x_0 到超平面 S : w x + b = 0 S:wx+b=0 的距离 d d :

  • x 0 x_0 S S 上面的投影为 x 1 x_1 ,则 w x 1 + b = 0 wx_1+b=0

  • 由向量 x 0 x 1 \vec{x_0x_1} S S 平面的法向量平行:
    w x 0 x 1 = ( w 1 ) 2 + ( w 2 ) 2 + . . . + ( w N ) 2 d = w d |w \cdot \vec{x_0x_1}| = \sqrt{(w^1)^2 + (w^2)^2+...+(w^N)^2}d = ||w||d

  • w L 2 ||w||为L_2范数

  • 又:
    w x 0 x 1 = w 1 ( x 0 1 x 1 1 ) + w 2 ( x 0 2 x 1 2 ) + . . . + w N ( x 0 N x 1 N ) w \cdot \vec{x_0x_1} = w^1(x_0^1-x_1^1)+w^2(x_0^2-x_1^2)+...+w^N(x_0^N-x_1^N)
    = w 1 x 0 1 + w 2 x 0 2 + . . . + w N x 0 N ( w 1 x 1 1 + w 2 x 1 2 + . . . + w N x 1 N ) =w^1x_0^1+w^2x_0^2+...+w^Nx_0^N-(w^1x_1^1+w^2x_1^2+...+w^Nx_1^N)

  • 又有: w x + b = 0 w \cdot x + b = 0
    = w 1 x 0 1 + w 2 x 0 2 + . . . + w N x 0 N ( b ) =w^1x_0^1+w^2x_0^2+...+w^Nx_0^N-(-b)

  • 故:
    w d = w x 0 + b ||w||d = |w \cdot x_0 + b|
    d = w x 0 + b w d =\frac{|w \cdot x_0 + b|}{||w||}

对于给定的训练数据集 T T 和超平面 ( w , b ) (w,b)
(1)定义超平面 ( w , b ) (w,b) 关于样本点 ( x i , y i ) (x_i,y_i) 的几何间隔为:

γ i = y i ( w w x i + b w ) \gamma_i = y_i(\frac{w}{||w||} \cdot x_i+\frac{b}{||w||})

(2)定义超平面 ( w , b ) (w,b) 关于训练数据集 T T 的几何间隔为超平面 ( w , b ) (w,b) 关于 T T 中全部样本点 ( x i , y i ) (x_i,y_i) 的几何间隔之最小值,即:

γ = min i = 1 , 2 , . . . , N γ i \gamma = \min_{i = 1,2,...,N}\gamma_i

几何间隔与函数间隔的关系:
γ = δ w \gamma = \frac{\delta}{||w||}

以上内容可参考:点到直线的距离

六、支持向量

\quad\quad 训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量,即图中在黑色线上的实例点。

在这里插入图片描述

七、拉格朗日对偶性

\quad\quad 在约束最优化问题中,经常利用拉格朗日对偶性将原始问题转化为对偶问题。经过求解对偶问题而获得原始问题的解。

\quad\quad 支持向量机和最大熵模型都用用到,下面咱们来简单介绍下拉格朗日对偶性的主要概念和结果。

1.原始问题:

假设 f ( x ) c i ( x ) h j ( x ) f(x),c_i(x),h_j(x) 是定义在 R n R^n 上的连续可微函数,考虑约束最优化问题:
min x R n f ( x ) \min_{x \in R^n} f(x)
s . t . c i ( x ) 0 i = 1 , 2 , . . . , k s.t. c_i(x) \leqslant 0,i = 1,2,...,k
h j ( x ) = 0 j = 1 , 2 , . . . , l h_j(x) = 0,j = 1,2,...,l

称此约束最优化问题为原始最优化问题或原始问题。

首先,引进广义拉格朗日函数:

L ( x , α , β ) = f ( x ) + i = 1 k α i c i ( x ) + j = 1 k β j h j ( x ) L(x,\alpha,\beta) = f(x) +\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{k}\beta_jh_j(x)

这里, x = ( x ( 1 ) x ( 2 ) x ( n ) ) T R n α i β j x=(x^{(1)},x^{(2)},。。。,x^{(n)})^T \in R^n, \alpha_i, \beta_j 是拉格朗日乘子, α i 0 \alpha_i \geqslant 0

那么原始问题就是:
θ p ( x ) = max α , β : α i 0 L ( x , α , β ) \theta_p(x)=\max_{\alpha,\beta:\alpha_i \geqslant0} L(x,\alpha,\beta)

假设给定某个 x x ,若是 x x 违反了约束条件,即存在某个 i i 使得 c i ( w ) > 0 c_i(w)>0 或者存在某个 j j 使得 h j ( w ) 0 h_j(w) \neq 0 ,那么就有:
θ p ( x ) = max α , β : α i 0 L ( x , α , β ) = + \theta_p(x)=\max_{\alpha,\beta:\alpha_i \geqslant0} L(x,\alpha,\beta) = +\infty

由于若某个 i i 使得 c i ( w ) > 0 c_i(w)>0 ,则可令 α i + , \alpha_i \rightarrow +\infty, 若某个 j j 使得 h j ( w ) 0 h_j(w) \neq 0 ,则可令 β j \beta_j 使 β j h j ( x ) + \beta_jh_j(x) \rightarrow +\infty ,而其他各 α i , β j \alpha_i,\beta_j 均为0

相反地,若是知足约束条件,则 i = 1 k α i c i ( x ) 0 j = 1 k β j h j ( x ) = 0 \sum_{i=1}^{k}\alpha_ic_i(x) \leqslant 0,\sum_{j=1}^{k}\beta_jh_j(x)=0 ,因为 f ( x ) f(x) 加上一个小于等于的数,最大值就是加上0,因此 θ p ( x ) = f ( x ) \theta_p(x) = f(x)

综上:
θ p ( x ) = { f ( x ) , x + , \theta_p(x) = \begin{cases} f(x), & x知足原始问题约束 \\ +\infty, & 其余\end{cases}

因此,若是考虑极小化问题
min x θ p ( x ) = min x max α , β : α i 0 L ( x , α , β ) \min_x \theta_p(x) = \min_x \max_{\alpha,\beta : \alpha_i \geqslant 0}L(x,\alpha,\beta)

它与原始问题最优化问题等价的,即他们有相同的解。这也称为广义拉格朗日 函数的极小极大问题。

2.对偶问题:
定义:
θ D ( α , β ) = min x L ( x , α , β ) \theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta)

再考虑极大化上式,即

max α , β : α i 0 θ D ( α , β ) = max α , β : α i 0 min x L ( x , α , β ) \max_{\alpha,\beta : \alpha_i \geqslant 0}\theta_D(\alpha,\beta)=\max_{\alpha,\beta : \alpha_i \geqslant 0}\min_xL(x,\alpha,\beta)

此称为广义拉格朗日函数的极大极小问题。

能够将广义拉格朗日函数的极大极小问题表示为约束最优化问题:
max α , β θ D ( α , β ) = max α , β min x L ( x , α , β ) \max_{\alpha,\beta }\theta_D(\alpha,\beta)=\max_{\alpha,\beta }\min_xL(x,\alpha,\beta)
s . t . α i 0 i = 1 , 2 , . . . , k s.t. \alpha_i \geqslant 0 ,i =1,2,...,k
称为原始问题的对偶问题。

补充:

若原始问题和对偶问题都有最优解,则:
d = max α , β ; α i 0 min x L ( x , α , β ) min x max α , β ; α i 0 L ( x , α , β ) = p d^* = \max_{\alpha,\beta;\alpha_i \geqslant 0} \min_x L(x,\alpha, \beta) \leqslant \min_x \max_{\alpha,\beta;\alpha_i \geqslant 0} L(x, \alpha, \beta) = p^*

对任意的 α , β \alpha, \beta x x ,有:
θ D ( α , β ) = min x L ( x , α , β ) L ( x , α , β ) max α , β : α i 0 L ( x , α , β ) = θ p ( x ) \theta_D(\alpha,\beta)=\min_xL(x,\alpha,\beta) \leqslant L(x,\alpha,\beta) \leqslant \max_{\alpha,\beta:\alpha_i \geqslant0} L(x,\alpha,\beta) = \theta_p(x)
即:
θ D ( α , β ) θ p ( x ) \theta_D(\alpha,\beta) \leqslant \theta_p(x)
因为原始问题和对偶问题都有最优解,因此:
max α , β : α i 0 θ D ( α , β ) min x θ p ( x ) \max_{\alpha,\beta:\alpha_i \geqslant0}\theta_D(\alpha,\beta) \leqslant \min_x\theta_p(x)
即:
d p d^* \leqslant p^*

\quad\quad 在知足某些条件下,原始问题和对偶问题的最优解相等,即 d = p d^* = p^* ,这是能够经过解对偶问题替代求原始问题,每每原始问题求解最优解比较困难,可是求它的对偶问题比较容易。

\quad\quad 假设函数 f ( x ) f(x) c i ( x ) c_i(x) 是凸函数, h j ( x ) h_j(x) 是仿射函数,而且不等式约束 c i ( x ) c_i(x) 是严格可行的,则 x x^* α , β \alpha^*,\beta^* 分别是原始问题和对偶问题的解的充分必要条件是 x , α , β x^*,\alpha^*,\beta^* 知足 KTT 条件:

x L ( x , α , β ) = 0 \nabla_xL(x^*,\alpha^*,\beta^*) = 0
α i c i ( x ) = 0 , i = 1 , 2 , . . . , k \alpha_i^*c_i(x^*) = 0, \quad\quad i=1,2,...,k
c i ( x ) 0 , i = 1 , 2 , . . . , k c_i(x^*) \leqslant 0, \quad\quad i=1,2,...,k
α i 0 , i = 1 , 2 , . . . , k \alpha_i^* \geqslant 0, \quad\quad i=1,2,...,k
h j ( x ) = 0 , j = 1 , 2 , . . . , l h_j(x^*) = 0, \quad\quad j=1,2,...,l

\quad\quad 以上介绍了理解支持向量机须要的基本概念,接下来咱们将分别介绍线性可分支持向量机、线性支持向量机和线性不可分支持向量机。

3.拉格朗日乘子法帮助理解

待优化目标:
y = 0.6 ( θ 1 + θ 2 ) 2 θ 1 θ 2 y=0.6 * (\theta_1 +\theta_2)^2 - \theta_1 * \theta_2
约束条件:
x 2 x + 1 = 0 x [ 4 , 4 ] x^2 - x + 1=0 \quad\quad x \in [-4,4]

在这里插入图片描述

上图中曲面为待优化目标,红点造成的曲线即是约束条件,表示要在约束条件下找到目标函数的最优解(最小值)

代码可见:01_拉格朗日乘子法.py

2、线性可分支持向量机

\quad\quad 咱们知道,支持向量机的学习目标是在特征空间找到一个分离超平面,能将实例分到不一样的类。

\quad\quad 当训练数据集线性可分时,存在无穷个分离超平面将两类数据正确分开。感知机利用误分类最小化的策略,求得分离超平面,不过这时的解有无穷多个。线性可分支持向量机利用间隔最大化求最优分离超平面,而且解是惟一的。

\quad\quad 那么咱们如何使得间隔最大化并求得分离超平面呢?

一、间隔最大化(硬间隔)

\quad\quad 间隔最大化的直观解释是:对训练数据集找到 几何间隔最大 的超平面意味着以充分大的确信度对训练数据进行分类。也就是说,不只将正负实例点分开,而求对最难分的实例点(离超平面最近的点)也有足够大的确信度将它们分开,这样的超平面对于未知的新实例有很好的分类预测能力。

\quad\quad 下面咱们考虑如何求得一个几何间隔最大的分离超平面,即最大间隔分离超平面。咱们能够将这个问题表示为下面的约束最优化问题:
max w , b γ s . t . y i ( w w x i + b w ) γ , i = 1 , 2 , . . . , N \max_{w,b} \quad \gamma \\ s.t. \quad y_i(\frac{w}{||w||} \cdot x_i + \frac{b}{||w||}) \geqslant \gamma, \quad i = 1,2,...,N

即咱们但愿最大化超平面 ( w , b ) (w,b) 关于训练数据集的几何间隔 γ \gamma
约束条件表示:超平面关于每一个样本点的几何间隔至少是 γ \gamma

进一步地,咱们考虑几何间隔和函数间隔的关系。
γ = δ w \gamma =\frac{\delta}{||w||}
此处: δ \delta 为函数间隔 y i ( w x i + b ) y_i(w\cdot x_i +b)

这是可将上面的约束问题改成:

max w , b δ w s . t . y i ( w x i + b ) δ , i = 1 , 2 , . . . , N \max_{w,b} \quad \frac{\delta}{||w||} \\ s.t. \quad y_i(w\cdot x_i +b) \geqslant \delta, \quad i = 1,2,...,N

这是咱们须要注意到,函数间隔 δ \delta 的取值并不影响最优化问题的解。

这里,假设咱们将 w , b w,b 按比例改成 λ w λ b \lambda w,\lambda b ,这是函数间隔变为 y i ( λ w x i + λ b ) = λ δ y_i(\lambda w \cdot x_i + \lambda b) = \lambda \delta
此时,函数间隔的改变并无改变上面的约束,对目标函数的优化也没用影响,也就是说,它产生一个等价的最优化问题;
这样,咱们就能够把函数间隔 δ \delta 特殊化,取 δ = 1 \delta = 1
将上面 δ = 1 \delta = 1 ,带入原来最优化问题中,注意到最大化 1 w \frac{1}{||w||} 和最小化 1 2 w 2 \frac{1}{2}||w||^2 是等价的。

咱们将获得线性支持向量机学习的最优化问题:
min w , b 1 2 w 2 s . t . y i ( w x i + b ) 1 0 , i = 1 , 2 , . . . , N \min_{w,b} \quad \frac{1}{2}||w||^2 \\ s.t. \quad y_i(w\cdot x_i +b) - 1 \geqslant 0, \quad i = 1,2,...,N

上面这个约束最优化问题是一个凸二次规划的问题。

若是求出了约束最优化问题的解 ( w , b ) (w^*,b^*) ,那么就能够获得最大间隔分离超平面 w x + b = 0 w^* \cdot x+b^*=0 及分类决策函数 f ( x ) = s i g n ( w x + b ) f(x) = sign(w^* \cdot x+b^*) ,即线性可分支持向量机。

二、线性可分支持向量机学习算法——最大间隔法以下:

输入:线性可分训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} ,其中, x i X = R n y i Y = { 1 , + 1 } i = 1 , 2 , . . . , N x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y}=\{-1,+1\},i=1,2,...,N
输出:最大间隔分离超平面和分类决策函数。
(1)构造并求解约束最优化问题:
min w , b 1 2 w 2 s . t . y i ( w x i + b ) 1 0 , i = 1 , 2 , . . . , N \min_{w,b} \quad \frac{1}{2}||w||^2 \\ s.t. \quad y_i(w\cdot x_i +b) - 1 \geqslant 0, \quad i = 1,2,...,N
求得最优解 w , b w^*,b^*
(2)由此获得分离超平面:
w x + b = 0 w^* \cdot x+b^*=0
分类决策函数:
f ( x ) = s i g n ( w x + b ) f(x) = sign(w^* \cdot x+b^*)

若训练数据集线性可分,则可将训练数据集中的样本点彻底正确分开的最大间隔分离超平面存在且惟一。

咱们知道 支持向量 就是距离分离超平面最近的实例点。注意到上面约束问题,支持向量即是使约束条件等号成立的点,即:
y i ( w x + b ) 1 = 0 y_i(w\cdot x+b) - 1 =0

在决定分离超平面时只有支持向量起做用,而其余实例点并不起做用,若是移动支持向量将改变所求的解;可是若是在间隔边界之外移动其余实例点,甚至去掉这些点,则解是不会改变的。

三、对偶算法

\quad\quad 为了求解线性可分支持向量机的最优化问题,将原来的约束最优化问题做为原始问题,应用拉格朗日对偶性,经过求解对偶问题获得原始问题的最优解。

这样作的有点:
对偶问题每每更容易求解
天然引入核函数,进而推广到非线性分类问题(这在后面会介绍)

如今咱们就开始构建原始问题的对偶问题:

(1)首先构建拉格朗日函数
L ( w , b , α ) = 1 2 w 2 i = 1 N α i [ y i ( w x + b ) 1 ] L(w,b,\alpha) = \frac{1}{2}||w||^2-\sum_{i=1}^N \alpha_i[y_i(w \cdot x + b) - 1]
其中, α i 0 α = ( α 1 , α 2 , . . . , α N ) T \alpha_i \geqslant 0,\alpha = (\alpha_1,\alpha_2,...,\alpha_N)^T 为拉格朗日乘子向量。

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题。

max α min w , b L ( w , b , α ) \max_\alpha \min_{w,b} L(w,b,\alpha)

即,须要先求 L ( w , b , α ) L(w,b,\alpha) w , b w,b 的极小,再求对 α \alpha 的极大。

(2)求 min w , b L ( w , b , α ) \min_{w,b} L(w,b,\alpha)

将拉格朗日函数 L ( w , b , α ) L(w,b,\alpha) 分别对 w , b w,b 求偏导并令其等于0
w L ( w , b , α ) = w i = 1 N α i y i x i = 0 b L ( w , b , α ) = 0 \nabla_wL(w,b,\alpha)=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0 \\ \nabla_bL(w,b,\alpha)=0
得:
w = i = 1 N α i y i x i i = 1 N α i y i = 0 w=\sum_{i=1}^{N}\alpha_iy_ix_i \\ \sum_{i=1}^{N}\alpha_iy_i=0
代入拉格朗日函数中,即得:
L ( w , b , α ) = 1 2 i = 1 N j = 1 N α i α j y i y j ( x i x j ) i = 1 N α i y i ( ( j = 1 N α j y j x j ) 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 L(w,b,\alpha) = \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)\cdot x_i+b)+\sum_{i=1}^N\alpha_i \\ = -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^N\alpha_i
即:
min w , b L ( w , b , α ) = 1 2 i = 1 N j = 1 N α i α j y i y j ( x i x j ) + i = 1 N α i \min_{w,b} L(w,b,\alpha)= -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^N\alpha_i
(3)求 min w , b L ( w , b , α ) \min_{w,b} L(w,b,\alpha) α \alpha 的极大,便是对偶问题:
max α 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 , i = 1 , 2 , . . . , N \max_\alpha \quad -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)+\sum_{i=1}^N\alpha_i \\ s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0 \\ \alpha_i \geqslant 0, \quad i=1,2,...,N

将上式的目标函数由求极大转换为求极小,获得等价的对偶最优化问题:
min α 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 , i = 1 , 2 , . . . , N \min_\alpha \quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^N\alpha_i \\ s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0 \\ \alpha_i \geqslant 0, \quad i=1,2,...,N

对于线性可分训练数据集,假设对偶最优化问题对 α \alpha 的解为 α = ( α 1 , α 2 , . . . , α N ) T \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T ,能够由 α \alpha^* 求得原始最优化问题对 ( w , b ) (w,b) 的解 w , b w^*,b^*

  • 上式能够经过SMO算法求解,具体内容后面将介绍

存在如下定理:

假设 α = ( α 1 , α 2 , . . . , α N ) T \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T 是对偶最优化问题的解,则存在下标 j j ,使得 α j > 0 \alpha_j^* > 0 ,并可求得原始最优化问题的解 w , b w^*,b^*
w = i = 1 N α i y i x i b = y j i = 1 N α i y i ( x i x j ) w^* = \sum_{i=1}^N\alpha_i^*y_ix_i \\ b^* = y_j - \sum_{i=1}^N\alpha_i^*y_i(x_i \cdot x_j)

至此,分离超平面能够写成:
i = 1 N α i y i ( x x i ) + b = 0 \sum_{i=1}^N\alpha_i^*y_i( x \cdot x_i)+b^* = 0
分类决策函数能够写为:
f ( x ) = s i g n ( i = 1 N α i y i ( x x i ) + b ) f(x) = sign(\sum_{i=1}^N\alpha_i^*y_i( x \cdot x_i)+b^* )

这就是说,分类决策函数只依赖于输入 x x 和训练数据集样本输入的内积。

四、线性可分支持向量机学习算法——对偶算法:

输入:线性可分训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\} ,其中, x i X = R n y i Y = { 1 , + 1 } i = 1 , 2 , . . . , N x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y}=\{-1,+1\},i=1,2,...,N
输出:最大间隔分离超平面和分类决策函数。
(1)构造并求解约束最优化问题:
min α 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 , i = 1 , 2 , . . . , N \min_\alpha \quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^N\alpha_i \\ s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0 \\ \alpha_i \geqslant 0, \quad i=1,2,...,N
求得最优解 α = ( α 1 , α 2 , . . . , α N ) T \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T
(2)计算:
w = i = 1 N α i y i x i w^* = \sum_{i=1}^N\alpha_i^*y_ix_i
并选择 α \alpha^* 的一个正份量 α j > 0 \alpha_j^* > 0 ,计算:
b = y j i = 1 N α i y i ( x i x j ) b^* = y_j - \sum_{i=1}^N\alpha_i^*y_i(x_i \cdot x_j)
(3)求得分离超平面:
i = 1 N α i y i ( x x i ) + b = 0 \sum_{i=1}^N\alpha_i^*y_i( x \cdot x_i)+b^* = 0
分类决策函数:
f ( x ) = s i g n ( i = 1 N α i y i ( x x i ) + b ) f(x) = sign(\sum_{i=1}^N\alpha_i^*y_i( x \cdot x_i)+b^* )

五、下面经过具体的数据,比较两个算法的计算:

数据以下图:正例点是 x 1 = ( 3 , 3 ) T , x 2 = ( 4 , 3 ) T x 3 = ( 1 , 1 ) T x_1 = (3,3)^T,x_2 = (4,3)^T,负例点是x_3 = (1,1)^T

在这里插入图片描述

问题:试求最大间隔分离超平面?

1.最大间隔法求解:

解:按照最大间隔法,根据训练数据集构造约束最优化问题:
min w , b 1 2 ( w 1 2 + w 2 2 ) s . t . 3 w 1 + 3 w 2 + b 0        4 w 1 + 3 w 2 + b 0        1 w 1 1 w 2 b 0 \min_{w,b} \quad \frac{1}{2}(w_1^2+w_2^2) \\ s.t. \quad 3w_1+3w_2 + b \geqslant 0 \\ \quad \ \ \ \ \ \ 4w_1+3w_2 + b \geqslant 0 \\ \quad \ \ \ \ \ \ -1w_1-1w_2 - b \geqslant 0
求得此最优化问题的解为: w 1 = w 2 = 1 2 , b = 2 w_1=w_2=\frac{1}{2},b=-2 。因而最大间隔分离超平面为:
1 2 x ( 1 ) + 1 2 x ( 2 ) 2 = 0 \frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2 = 0
其中, x 1 = ( 3 , 3 ) T x 3 = ( 1 , 1 ) T x_1 = (3,3)^T 与 x_3 = (1,1)^T 是支持向量。

2.对偶算法求解:

解:根据所给数据,对偶问题是:
min α 1 2 i = 1 N j = 1 N α i α j y i y j ( x i x j ) i = 1 N α i = 1 2 ( 18 α 1 2 + 25 α 2 2 + 2 α 3 2 + 42 α 1 α 2 12 α 1 α 3 14 α 2 α 3 ) α 1 α 2 α 3 s . t . α 1 + α 2 α 3 = 0 α i 0 , i = 1 , 2 , 3 \min_\alpha \quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i \cdot x_j)-\sum_{i=1}^N\alpha_i \\ = \frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3)-\alpha_1-\alpha_2-\alpha_3 \\ s.t. \alpha_1+\alpha_2-\alpha_3=0 \\ \alpha_i \geqslant 0, \quad i=1,2,3
解这一最优化问题,将 α 3 = α 1 + α 2 \alpha_3 = \alpha_1+\alpha_2 代入目标函数并记为:
s ( α 1 , α 2 ) = 4 α 1 2 + 13 2 α 2 2 + 10 α 1 α 2 2 α 1 2 α 2 s(\alpha_1,\alpha_2) = 4\alpha_1^2+\frac{13}{2}\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2
α 1 , α 2 \alpha_1,\alpha_2 求偏导数并令其为0,易知 s ( α 1 , α 2 ) s(\alpha_1,\alpha_2) 在点 ( 3 2 , 1 ) T (\frac{3}{2},-1)^T 取极值,但该点不知足约束条件 α 2 0 \alpha_2 \geqslant 0 ,因此极小值应在边界上达到。

α 1 = 0 \alpha_1 = 0 时,最小值 s ( 0 , 2 13 ) = 2 13 s(0, \frac{2}{13}) = -\frac{2}{13} ;当 α 2 = 0 \alpha_2 = 0 时,最小值 s ( 1 4 0 ) = 1 4 s(\frac{1}{4},0) = -\frac{1}{4} 。因而, s ( α 1 , α 2 ) s(\alpha_1,\alpha_2) α 1 = 1 4 , α 2 = 0 \alpha_1=\frac{1}{4},\alpha_2=0 达到最小,此时 α 3 = α 1 + α 2 = 1 4 \alpha_3 = \alpha_1+\alpha_2 = \frac{1}{4}

这样, α 1 = α 3 = 1 4 \alpha_1^*=\alpha_3^* = \frac{1}{4} 对应的实例点 x 1 , x 3 x_1,x_3 是支持向量,根据:
w = i = 1 N α i y i x i w^* = \sum_{i=1}^N\alpha_i^*y_ix_i
b = y j i = 1 N α i y i ( x i x j ) b^* = y_j - \sum_{i=1}^N\alpha_i^*y_i(x_i \cdot x_j)
计算得:
w = 1 4 ( 1 ) ( 3 , 3 ) + 1 4 ( 1 ) ( 1 , 1 ) = ( 1 2 , 1 2 ) w 1 = w 2 = 1 2 w^* = \frac{1}{4}(1)(3,3)+\frac{1}{4}(-1)(1,1) = (\frac{1}{2},\frac{1}{2})\\ w_1^*=w_2^* = \frac{1}{2}
取点 x 1 = ( 3 , 3 ) T b j = 1 , y j = 1 x_1=(3,3)^T求b^*,此时j=1,y_j=1
b = 1 [ 1 4 ( 1 ) ( x 1 x 1 ) + 1 4 ( 1 ) ( x 3 x 1 ) ] = 1 ( 1 4 18 1 4 6 ) = 2 b^* = 1 - [\frac{1}{4}(1)(x_1 \cdot x_1)+\frac{1}{4}(-1)(x_3 \cdot x_1)] \\ = 1-(\frac{1}{4}*18-\frac{1}{4}*6)= -2

因而分离超平面为:
1 2 x ( 1 ) + 1 2 x ( 2 ) 2 = 0 \frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2 = 0
分类决策函数为:
f ( x ) = s i g n ( 1 2 x ( 1 ) + 1 2 x ( 2 ) 2 ) f(x) = sign(\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2 )

由上面两种方法可见,两种方法获得的超平面是同样的,也验证了对偶方法的有效性。

至此,咱们获得目标函数:
max α i 0 L ( w , b , α ) = max α i 0 1 2 w 2 i = 1 N α i [ y i ( w x + b ) 1 ] \max_{\alpha_i \geqslant 0}L(w,b,\alpha) = \max_{\alpha_i \geqslant 0} \frac{1}{2}||w||^2-\sum_{i=1}^N \alpha_i[y_i(w \cdot x + b) - 1]

注意到,若是 x i x_i 是支持向量的话,上式中 y i ( w x + b ) 1 = 0 y_i(w \cdot x + b) - 1 = 0 (由于至此向量的函数间隔为1),而对于非支持向量来讲,函数间隔会大于1,所以 y i ( w x + b ) 1 > 0 y_i(w \cdot x + b) - 1 > 0 ,而 α i 0 \alpha_i \geqslant 0 ,为了知足最大化, α i \alpha_i 必须等于0。

到目前为止,线性可分支持向量机只能处理线性可分数据集,不过,在获得了对偶问题形式以后,经过核函数(Kernel)推广到非线性的状况就变成了一个很是容易的事情了。

3、核函数 Kernel

\quad\quad 在现实任务中,咱们获得的通常都不是线性可分的,这时线性可分支持向量机就不适用了。由于这时咱们以前所提到的不等式约束并不能都成立。那么对于非线性的数据 SVM 是如何处理的呢?

\quad\quad 对于非线性的状况,SVM 的处理方法是选择一个核函数 k ( , ) k(\cdot,\cdot) ,经过将数据映射到高维空间,来解决在原始空间中线性不可分的问题。

\quad\quad 具体来讲,在线性不可分的状况下,支持向量机首先在低维空间中完成计算,而后经过核函数将输入空间映射到高维特征空间,最终在高维特征空间中构造出最优的分离超平面,从而把平面上自己很差分的非线性数据分开。如图所示,一维数据在二维空间没法划分,从而映射到三维空间里划分:

在这里插入图片描述

所以,在没有核函数以前,当咱们但愿用前面线性分类问题的方法来解决这个问题,就须要选择一个非线性特征集,并将数据改写成新的表达方式,这等价于应用一个固定的非线性映射,将数据映射到特征空间,在特征空间中使用线性分类器。

f ( x ) = i = 1 N w i ϕ i ( x ) + b f(x) = \sum_{i=1}^N w_i \phi_i(x) + b

其中, ϕ \phi :表示从输入空间到某个特征空间的映射,这意味着线性分类方法求解非线性分类问题通常分为两步:

  • 使用一个变换将原空间的数据映射到新空间;
  • 在新空间里使用线性分类学习方法从训练数据中学习分类模型。

一、核函数:如何处理非线性数据

\quad\quad 假设咱们有以下图所示的两类数据,分别为两个圆圈的形状,很明显这样的数据是线性不可分的,那么咱们如何把这两类数据分开呢?

在这里插入图片描述

\quad\quad 事实上,上图数据集使用两个不一样半径的圆圈加上少许噪声生成获得的,因此,一个理想的分类应该是一个“圆圈”而不是一条直线(超平面),若是用 X 1 X_1 X 2 X_2 来表示这个二维平面的两个坐标,咱们知道一个二次曲线的方程能够写成以下形式:

a 1 X 1 + a 2 X 1 2 + a 3 X 2 + a 4 X 2 2 + a 5 X 1 X 2 + a 6 = 0 a_1X_1 + a_2X_1^2+a_3X_2+a_4X_2^2+a_5X_1X_2+a_6=0

注意上面的形式,若是咱们构造另外一个五维的空间,其中五个坐标的值分别为:
Z 1 = X 1 , Z 2 = X 1 2 , Z 3 = X 2 , Z 4 = X 2 2 , Z 5 = X 1 X 2 Z_1 = X_1,Z_2=X_1^2,Z_3=X_2,Z_4=X_2^2,Z_5=X_1X_2
那么,上面的方程就能够写成:

i = 1 5 a i Z i + a 6 = 0 \sum_{i=1}^5a_iZ_i + a_6 =0

\quad\quad 关于新的坐标 Z Z ,若是咱们作一个映射 ϕ R 2 R 5 \phi:R_2 \rightarrow R_5 ,将 X X 按照上面的规则映射为 Z Z ,那么在的新的空间中原来的数据将变成线性可分的,从而使用以前咱们推导的线性分类算法就能够进行处理了,这正是 Kernel 方法处理非线性问题的基本思想。

\quad\quad 再进一步描述 Kernel 的细节以前,不妨再来看看上述例子在映射事后的直观形态。固然,咱们没法把五维空间画出来,不过因为咱们生成数据的时候用了特殊的情形,因此这里的超平面实际的方程是这个样子的(圆心在 X 2 X_2 轴上的一个正圆):

i = 1 5 a i Z i + a 6 = 0 \sum_{i=1}^5a_iZ_i + a_6 =0

\quad\quad 所以我只须要把它映射到 Z 1 = X 1 2 , Z 2 = X 2 2 , Z 3 = X 2 Z_1 = X_1^2,Z_2 = X_2^2,Z_3 = X_2 ,这样一个三维空间中便可,下图便是映射以后的结果,将坐标通过适当的旋转,就能够很明显地看出,数据是能够经过的一个平面来分开的,以下图:

在这里插入图片描述

核函数至关于把原来的分类函数:
f ( x ) = i = 1 n α i y i x i , x + b f(x) = \sum_{i=1}^n\alpha_iy_i \langle x_i, x \rangle + b
映射成:
f ( x ) = i = 1 n α i y i ϕ ( x i ) , ϕ ( x ) + b f(x) = \sum_{i=1}^n\alpha_iy_i \langle \phi(x_i), \phi(x) \rangle + b

而其中的 α \alpha 能够经过求解以下对偶问题获得:

max α i = 1 n α i 1 2 i , j = 1 n α i α j y i y j ϕ ( x i ) , ϕ ( x ) \max_\alpha \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j\langle \phi(x_i), \phi(x) \rangle
s . t . α i 0 i = 1 , 2 , . . . , n s.t. \quad \alpha_i \geqslant0 \quad\quad i = 1,2,...,n
i = 1 n α i y i = 0 \sum_{i=1}^n \alpha_i y_i =0

获得以上对偶问题,彷佛咱们就能够解决非线性问题,咱们只须要找到一个映射 ϕ ( ) \phi(\cdot) ,而后将非线性数据映射到新空间中,再作线性 SVM 便可,然而事实上并无这么简单。

  • 在最初的例子里,咱们对一个二维空间最映射,选择的新空间是原始空间的全部一阶和二阶的组合,获得五维空间;
  • 若是原始空间是三维的,那么咱们就会获得:3个一次项+3个二次交叉项+3个平方项+1个三次交叉项+6个一次和二次交叉项=19维的空间,这个数目层指数级爆炸增加,从而一定给 ϕ ( ) \phi(\cdot) 的计算带来困难,并且若是遇到无穷维的状况,就根本没法计算了。

这时候,Kernel 核函数就派上用场了。

咱们还使用前面的二维原始空间,设两个向量 x 1 = ( η 1 , η 2 ) T x_1 = (\eta_1, \eta_2)^T x 2 = ( ξ 1 , ξ 2 ) T x_2 = (\xi_1, \xi_2)^T