支持向量机(SVM)原理分析

2019年12月08日 阅读数:100
这篇文章主要向大家介绍支持向量机(SVM)原理分析,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

版权说明:码字不易,转载请注明出处:http://blog.csdn.net/flying_sfeng/article/details/79055411
支持向量机(SVM)是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机学习的基本思想是求解可以正确划分训练数据集而且几何间隔最大的分离超平面。
对于下图线性可分的状况,SVM就是为了找到一个最优的超平面,将正负样本尽量地分开来,也就是说,咱们要找到分开样本的最大间隔。
Fig1
先了解一下函数间隔和几何间隔。
函数间隔
web

γ ^ ( i ) = y ( i ) ( w T x ( i ) + b )

其中, y ( i ) 为标签 ( y { 1 , 1 } )
y ( i ) = 1 时,为了使间隔最大, w T x + b 必须是一个尽量大的正数,这样才能确保分类正确的确信度最高。一样地,当 y ( i ) = 1 时,为了使间隔最大, w T x + b 必须是一个尽量大的负数。
而咱们的目的是最大化全部训练样本的最小间隔,即给定一个训练集 S = { ( x ( i ) , y ( i ) ) ; i = 1 , . . . , m } ,咱们定义在S下 ( w , b ) 的函数间隔为全部训练样本的函数边界的最小值,则:
γ ^ = min i = 1 , . . . , m γ ^ ( i )

几何间隔
如图,
这里写图片描述
假设 γ ( i ) 为咱们要求的几何间隔,咱们知道, w | | w | | w 方向上的单位向量,给定A: x ( i ) ,能够获得B: x ( i ) γ ( i ) w | | w | | ,又由于B位于决策边界,因此B也知足 w T x + b = 0 ,代入得:
w T ( x ( i ) γ ( i ) w | | w | | ) + b = 0.

移项获得:
γ ( i ) = w T x ( i ) + b | | w | | = ( w | | w | | ) T x ( i ) + b | | w | |

这只是一个方向上的,为了知足正负样本 y = ± 1 的状况,更通常的,咱们能够令
γ ( i ) = y ( i ) ( ( w | | w | | ) T x ( i ) + b | | w | | )

所以,几何间隔与函数间隔的关系为:
γ ( i ) = γ ^ ( i ) | | w | |

| | w | | = 1 时,几何间隔就等于函数间隔。
一样地,几何间隔为全部样本距离分界面的间隔的最小值,则
γ = min i = 1 , . . . , m γ ( i )

间隔最大化:
间隔最大化的直观解释是:对训练数据集找到几何间隔最大的超平面,这意味着以充分大的确信度对训练数据进行分类。也就是说,不只将正负实例点分开,并且对最难分的实例点(离超平面最近的点)也有足够的确信度将它们分开。
下面考虑如何求得一个几何间隔最大的分离超平面,即最大间隔分离超平面。具体地,这个问题能够表示为下面的约束最优化问题:
max w , b γ s.t. γ ( i ) = y ( i ) ( ( w | | w | | ) T x ( i ) + b | | w | | ) γ ,     i = 1 , 2 , . . . , N

即咱们但愿最大化超平面(w,b)关于训练数据集的几何间隔 γ , γ 表示的是训练数据集中的最小几何间隔,因此约束条件表示的是超平面(w,b)关于每一个训练样本点的几何间隔至少是 γ .
考虑到几何间隔与函数间隔的关系,可将这个问题改写为:
max w , b γ ^ | | w | | s.t. y ( i ) ( ( w | | w | | ) T x ( i ) + b | | w | | ) γ ^ | | w | | ,     i = 1 , 2 , . . . , N

将不等式两边的 | | w | | 约去,即:
max w , b γ ^ | | w | | s.t. y ( i ) ( w T x ( i ) + b ) γ ^ ,     i = 1 , 2 , . . . , N

函数间隔 γ ^ 的取值并不影响最优化问题的解。为何呢?事实上,假设将w和b按比例改变成 λ w λ b ,这时函数间隔成为 λ γ ^ 。把 λ w λ b λ γ ^ 分别代入上面的优化问题能够获得:
max w , b λ γ ^ | | λ w | | = λ γ ^ λ | | w | | s.t. y ( i ) ( ( λ w ) T x ( i ) + λ b ) λ γ ^ ,     i = 1 , 2 , . . . , N

两个式子的 λ 均可以约去,所以,函数间隔的这一改变对上述目标函数的优化没有影响,对不等式约束也没有影响。也就是说,它产生了一个等价的最优化问题。因此,咱们就能够取 γ ^ = 1 , 将 γ ^ = 1 代入上面的最优化问题中,考虑到最大化 1 | | w | | 和最小化 1 2 | | w | | 2 是等价的,因而就获得了下面的线性可分支持向量机学习的最优化问题:
min w , b 1 2 | | w | | 2 s.t. y ( i ) ( w T x ( i ) + b ) 1 0 ,     i = 1 , 2 , . . . , N

若是求出了上述约束最优化问题的解 w , b , 那么就能够获得最大间隔超平面 w x + b = 0 及分类决策函数 f ( x ) = s i g n ( w x + b ) , 即线性可分支持向量机模型。
接下来考虑 对偶问题
咱们暂时先无论以上的优化式子,考虑通常化的条件:
min w f ( w )  s.t.  h i ( w ) = 0 ,   i = 1 , . . . , l .

这是含有等式约束的最小化问题,能够用拉格朗日乘子方法求解。
以上含等式约束的问题能够转换为如下拉格朗日函数:
L ( w , β ) = f ( w ) + i = 1 l β i h i ( w )

其中 β i 为拉格朗日乘子,令 L 的导数等于零:
L w i = 0 ;   L β i = 0

能够求出 w β .
接下来咱们看一下含有不等式约束的最优化问题。原问题:
min w f ( w ) s.t. g i ( w ) 0 ,   i = 1 , . . . , k h i ( w ) = 0 ,   i = 1 , . . . , l .

为了解决这个不等式约束问题,咱们定义如下的拉格朗日函数:
L ( w , α , β ) = f ( w ) + i = 1 k α i g i ( w ) + i = 1 k β i h i ( w ) .

其中 α i , β i 为拉格朗日乘子。
考虑如下等式:
θ p ( w ) = max α , β : α i 0 L ( w , α , β )

当违背约束时(即存在 i , 使得 g i ( w ) > 0 h i ( w ) 0 ),
θ p ( w ) = max α , β : α i 0 f ( w ) + i = 1 k α i g i ( w ) + i = 1 k β i h i ( w ) =

而当不等式约束跟等式约束都知足时, θ p ( w ) = f ( w ) ,即:
θ p ( w ) = { f ( w ) , 若是w知足全部约束 , 不然

这就是要最大化拉格朗日函数的缘由。当不等式约束跟等式约束都知足要求时, θ p ( w ) = f ( w ) ; 当违背约束时, θ p ( w ) 趋向于无穷大,式子无解,这样作至关于把约束放到了上述式子中了。同时,咱们最小化 f ( w ) ,就至关于最小化 θ p ( w ) .即:
p = min w θ p ( w ) = min w max α , β : α i 0   L ( w , α , β )

p 即为原问题的解。
接下来咱们最小化拉格朗日函数,
θ d ( α , β ) = min w L ( w , α , β )

由此咱们能够列出对偶优化问题:
d = max α , β : α i 0 θ d ( α , β ) = max α , β : α i 0 min w   L ( w , α , β )

d 即为对偶问题的解。
原问题跟对偶问题有什么关系呢?关系以下:
d = max α , β : α i 0 min w   L ( w , α , β ) min w max α , β : α i 0   L ( w , α , β ) = p

当拉格朗日乘子的解 w , α , β 知足如下的KKT条件时, d = p :
(27) L ( w , α , β ) w i = 0 ,     i = 1 , . . . , n (28) L ( w , α , β ) β i = 0 ,     i = 1 , . . . , l (29) α i g i ( w ) = 0 ,     i = 1 , . . . , k (30) g i ( w ) 0 ,     i = 1 , . . . , k (31) α 0 ,     i = 1 , . . . , k

下面,将证实原问题与对偶问题的关系的由来。
咱们再次写下拉格朗日函数:
L ( w , α , β ) = f ( w ) + i = 1 k α i g i ( w ) + i = 1 k β i h i ( w ) .

如下式子恒成立( s u p 表示上确界, i n f 表示下确界):
(32) inf w W L ( w , α , β ) L ( w , α , β ) ,     w , α , β (33) sup α , β : α i 0 L ( w , α , β ) L ( w , α , β ) ,     w , α , β

令:
(34) q ( α , β ) = inf w W L ( w , α , β ) (35) f ( w ) = sup α , β : α i 0 L ( w , α , β )

因此,有:
q ( α , β ) f ( w )

所以:
sup α , β : α i 0 q ( α , β ) inf w W f ( w )

即:
sup α , β : α i 0 inf w W L ( w , α , β ) inf w W sup α , β : α i 0 L ( w , α , β )

等式成立的条件是: L ( w , α , β ) 的第二项跟第三项为零,即:
(36) α i 0 ,     i (37) g i ( w ) 0 ,     i (38) α i g i ( w ) = 0 ,     i (39) h i ( w ) = 0 ,     i

也就是说,当变量知足KKT条件时,对偶问题的解等于原问题的解。

优化问题的求解:
再次写下咱们要求解的优化问题:
算法

min w , b 1 2 | | w | | 2 s.t. y ( i ) ( w T x ( i ) + b ) 1 0 ,     i = 1 , 2 , . . . , N

拉格朗日函数以下:
L ( w , α , β ) = 1 2 | | w | | 2 + i = 1 m α i [ 1 y ( i ) ( w T x ( i ) + b ) ] .

咱们经过求解对偶问题来获得原问题的解,固然前提是必须知足KKT条件。
对偶问题以下:
max α i 0 min w , b 1 2 | | w | | 2 + i = 1 m α i [ 1 y ( i ) ( w T x ( i ) + b ) ] .

对于这个问题,咱们先经过最小化 L ( w , α , β ) 来求出 w , b ( α ) ,具体作法是使L对w,b的导数为零。对w求导:
w L ( w , b , α ) = w i = 1 m α i y ( i ) x ( i ) = 0

即:
w = i = 1 m α i y ( i ) x ( i )

对b求导:
b L ( w , b , α ) = i = 1 m α i y ( i ) = 0

将上述两式代入到拉格朗日函数中,能够获得:
L ( w , b , α ) = i = 1 m α i 1 2 i = 1 m j = 1 m y ( i ) y ( j ) α i α j ( x ( i ) ) T x ( j )

所以,优化问题可写成下列形式:
max α i = 1 m α i 1 2 i = 1 m j = 1 m y ( i ) y ( j ) α i α j ( x ( i ) ) T x ( j ) s.t. α i 0 ,   i = 1 , . . . , m i = 1 m α i y ( i ) = 0

这就变成了对 α 的单变量优化问题。对 α 的求解可使用SMO算法,咱们后面会讲到。假设咱们已经求解出 α , 那么咱们能够经过 w = i = 1 m α i y ( i ) x ( i ) 求出w,可是b该怎么求解呢?
当i为支持向量时,咱们能够获得函数间隔: y ( i ) ( w T x ( i ) + b ) = γ ^ ,即:
max i : y ( i ) = 1 w T x ( i ) + b = γ ^ min i : y ( i ) = 1 w T x ( i ) + b = γ ^

以上两式相加能够获得b:
b = max i : y ( i ) = 1 w T x ( i ) + min i : y ( i ) = 1 w T x ( i ) 2 .

所以,对于一个待预测的样本,咱们能够获得:
w T x + b = i = 1 m α i y ( i ) ( x ( i ) ) T x + b = i = 1 m α i y ( i ) x ( i ) , x + b .

w T x + b > 0 时咱们把该样本预测为正样本, w T x + b 0 时预测为负样本。

核函数:
在前面的讨论中,咱们假设训练样本时线性可分的,即存在一个划分超平面能将训练样本正确分类。然而在现实任务中,原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对于这样的问题,可将样本从原始空间映射到一个更高维的特征空间,使得样本在这个特征空间内线性可分。幸运的是,若是原始空间是有限维,即属性数有限,那么必定存在一个高维特征空间使样本可分。(参考《机器学习》6.3节 周志华著)
核函数的定义:
设X是原始输入空间,H为特征空间(希尔伯特空间),若是存在一个从X到H 的映射:
机器学习

ϕ ( x ) : X H

使得对全部 x , z X , 函数 K ( x , z ) 知足条件:
K ( x , z ) = ϕ ( x ) , ϕ ( z )

则称 K ( x , z ) 为核函数, ϕ ( x ) 为映射函数,式中 ϕ ( x ) , ϕ ( z ) ϕ ( x ) ϕ ( z ) 的内积。
核技巧的想法是:在学习与预测中只定义核函数 K ( x , z ) ,而不显式地定义映射函数 ϕ 。一般,直接计算 K ( x , z ) 比较容易,而经过 ϕ ( x ) ϕ ( z ) 计算 K ( x , z ) 并不容易。这是由于, ϕ 是原始输入空间X到特征空间H地映射,特征空间H通常是高维的,甚至是无穷维的。
通俗点讲,对于在原始空间内线性不可分的状况,咱们能够将原始空间映射到高维空间,高维空间的内积计算使用核函数代替。
所以,咱们的目标函数的对偶问题能够写成下列形式:
max α i = 1 m α i 1 2 i = 1 m j = 1 m y ( i ) y ( j ) α i α j k ( x ( i ) , x ( j ) ) s.t. α i 0 ,   i = 1 , . . . , m i = 1 m α i y ( i ) = 0

求解后便可获得:
f ( x ) = w T ϕ ( x ) + b = i = 1 m α i y ( i ) ϕ ( x ( i ) ) T ϕ ( x ) + b = i = 1 m α i y ( i ) k ( x ( i ) , x ) + b

那么,什么样的函数能作核函数呢?咱们有下面的定理:
定理:令 X 为原始输入空间, k ( x ( i ) , x ( j ) ) 是定义在 X × X 上的对称函数,则 k 是核函数当且仅当对于任意数据 D = x ( 1 ) , x ( 2 ) , . . . , x ( m ) , 核矩阵 K 老是半正定的:
K = [ k ( x ( 1 ) , x ( 1 ) ) k ( x ( 1 ) , x ( j ) ) k ( x ( 1 ) , x ( m ) ) k ( x ( i ) , x ( 1 ) ) k ( x ( i ) , x ( j ) ) k ( x ( i ) , x ( m ) ) k ( x ( m ) , x ( 1 ) ) k ( x ( m ) , x ( j ) ) k ( x ( m ) , x ( m ) ) ]

定理代表,只要一个对称函数所对应的核矩阵半正定,它就能做为核函数使用。
定理证实:若是 k 是一个有效的核函数,那么 k ( x ( i ) , x ( j ) ) = ϕ ( x ( i ) ) T ϕ ( x ( j ) ) == ϕ ( x ( j ) ) T ϕ ( x ( i ) ) = k ( x ( j ) , x ( i ) ) , 所以核函数 k 必须是对称的。另外,对于任意向量 z ,咱们有:
z T K z = i j z i k ( x ( i ) , x ( j ) ) z j = i j z i ϕ ( x ( i ) ) T ϕ ( x ( j ) ) z j = i j z i k ϕ k ( x ( i ) ) ϕ k ( x ( j ) ) z j = k i j z i ϕ k ( x ( i ) ) ϕ k ( x ( j ) ) z j = k ( i z i ϕ k ( x ( i ) ) ) 2 0.

所以,核矩阵 K 必须是半正定的。证毕。
经常使用核函数: