在机器学习 中,支持向量机
(台湾称支援向量機 ,英语:support vector machine ,常简称为SVM ,又名支持向量网络 [1] )是在分类 与回归分析 中分析数据的监督式学习 模型与相关的学习算法 。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法建立一个将新的实例分配给两个类别之一的模型,使其成为非概率二元 线性分类器 。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。
除了进行线性分类之外,SVM还可以使用所谓的核技巧 有效地进行非线性分类,将其输入隐式映射到高维特征空间中。
当数据未被标记时,不能进行监督式学习,需要用非监督式学习 ,它会尝试找出数据到簇的自然聚类,并将新数据映射到这些已形成的簇。将支持向量机改进的聚类算法被称为支持向量聚类 [2] ,当数据未被标记或者仅一些数据被标记时,支持向量聚类经常在工业应用中用作分类步骤的预处理。
H1 不能把类别分开。H2 可以,但只有很小的间隔。H3 以最大间隔将它们分开。
将数据进行分类 是机器学习 中的一项常见任务。
假设某些给定的数据点各自属于两个类之一,而目标是确定新数据点将在哪个类中。对于支持向量机来说,数据点被视为
p
{\displaystyle p}
维向量,而我们想知道是否可以用
(
p
−
1
)
{\displaystyle (p-1)}
维超平面 来分开这些点。这就是所谓的线性分类器 。可能有许多超平面可以把数据分类。最佳超平面的一个合理选择是以最大间隔把两个类分开的超平面。因此,我们要选择能够让到每边最近的数据点的距离最大化的超平面。如果存在这样的超平面,则称为最大间隔超平面,而其定义的线性分类器被称为最大间隔分类器 ,或者叫做最佳稳定性感知器 。[来源请求]
用于文本和超文本的分类,在归纳和直推方法中都可以显著减少所需要的有类标的样本数。
用于图像分类。实验结果显示:在经过三到四轮相关反馈之后,比起传统的查询优化方案,支持向量机能够获取明显更高的搜索准确度。这同样也适用于图像分割系统,比如使用Vapnik所建议的使用特权方法的修改版本SVM的那些图像分割系统。[4] [5]
用于手写字体识别。
用于医学中分类蛋白质,超过90%的化合物能够被正确分类。基于支持向量机权重的置换测试已被建议作为一种机制,用于解释的支持向量机模型。[6] [7] 支持向量机权重也被用来解释过去的SVM模型。[8] 为识别模型用于进行预测的特征而对支持向量机模型做出事后解释是在生物科学中具有特殊意义的相对较新的研究领域。
原始SVM算法是由苏联 数学家弗拉基米尔·瓦普尼克 和亚历克塞·泽范兰杰斯 于1963年发明的。1992年,伯恩哈德·E·博瑟(Bernhard E. Boser)、伊莎贝尔·M·盖昂(Isabelle M. Guyon)和瓦普尼克提出了一种通过将核技巧应用于最大间隔超平面来创建非线性分类器的方法。[9] 当前标准的前身(软间隔)由科琳娜·科特斯 和瓦普尼克于1993年提出,并于1995年发表。[1]
我们考虑以下形式的
n
{\displaystyle n}
点测试集:
(
x
→
1
,
y
1
)
,
…
,
(
x
→
n
,
y
n
)
{\displaystyle ({\vec {x}}_{1},y_{1}),\,\ldots ,\,({\vec {x}}_{n},y_{n})}
其中
y
i
{\displaystyle y_{i}}
是 1 或者 −1,表明点
x
→
i
{\displaystyle {\vec {x}}_{i}}
所属的类。
x
→
i
{\displaystyle {\vec {x}}_{i}}
中每个都是一个
p
{\displaystyle p}
维实 向量。我们要求将
y
i
=
1
{\displaystyle y_{i}=1}
的点集
x
→
i
{\displaystyle {\vec {x}}_{i}}
与
y
i
=
−
1
{\displaystyle y_{i}=-1}
的点集分开的 “最大间隔超平面”,使得超平面与最近的点
x
→
i
{\displaystyle {\vec {x}}_{i}}
之间的距离最大化。
任何超平面都可以写作满足下面方程的点集
x
→
{\displaystyle {\vec {x}}}
w
→
⋅
x
→
−
b
=
0
,
{\displaystyle {\vec {w}}\cdot {\vec {x}}-b=0,\,}
设样本属于两个类,用该样本训练SVM得到的最大间隔超平面。在边缘上的样本点称为支持向量。
其中
w
→
{\displaystyle {\vec {w}}}
(不必是归一化的)是该法向量 。参数
b
‖
w
→
‖
{\displaystyle {\tfrac {b}{\|{\vec {w}}\|}}}
决定从原点沿法向量
w
→
{\displaystyle {\vec {w}}}
到超平面的偏移量。
如果这些训练数据是线性可分的,可以选择分离两类数据的两个平行超平面,使得它们之间的距离尽可能大。在这两个超平面范围内的区域称为“间隔”,最大间隔超平面是位于它们正中间的超平面。这些超平面可以由方程:
w
→
⋅
x
→
−
b
=
1
{\displaystyle {\vec {w}}\cdot {\vec {x}}-b=1\,}
或是
w
→
⋅
x
→
−
b
=
−
1.
{\displaystyle {\vec {w}}\cdot {\vec {x}}-b=-1.\,}
来表示。通过几何不难得到这两个超平面之间的距离是
2
‖
w
→
‖
{\displaystyle {\tfrac {2}{\|{\vec {w}}\|}}}
,因此要使两平面间的距离最大,我们需要最小化
‖
w
→
‖
{\displaystyle \|{\vec {w}}\|}
。同时为了使得样本数据点都在超平面的间隔区以外,我们需要保证对于所有的
i
{\displaystyle i}
满足其中的一个条件:
w
→
⋅
x
→
i
−
b
≥
1
,
{\displaystyle {\vec {w}}\cdot {\vec {x}}_{i}-b\geq 1,}
若
y
i
=
1
{\displaystyle y_{i}=1}
或是
w
→
⋅
x
→
i
−
b
≤
−
1
,
{\displaystyle {\vec {w}}\cdot {\vec {x}}_{i}-b\leq -1,}
若
y
i
=
−
1.
{\displaystyle y_{i}=-1.}
这些约束表明每个数据点都必须位于间隔的正确一侧。
这两个式子可以写作:
y
i
(
w
→
⋅
x
→
i
−
b
)
≥
1
,
for all
1
≤
i
≤
n
.
(
1
)
{\displaystyle y_{i}({\vec {w}}\cdot {\vec {x}}_{i}-b)\geq 1,\quad {\text{ for all }}1\leq i\leq n.\qquad \qquad (1)}
可以用这个式子一起来得到优化问题:
“在
y
i
(
w
→
⋅
x
i
→
−
b
)
≥
1
{\displaystyle y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\geq 1}
条件下,最小化
‖
w
→
‖
{\displaystyle \|{\vec {w}}\|}
,对于
i
=
1
,
…
,
n
{\displaystyle i=1,\,\ldots ,\,n}
"
这个问题的解
w
→
{\displaystyle {\vec {w}}}
与
b
{\displaystyle b}
决定了我们的分类器
x
→
↦
sgn
(
w
→
⋅
x
→
−
b
)
{\displaystyle {\vec {x}}\mapsto \operatorname {sgn}({\vec {w}}\cdot {\vec {x}}-b)}
。
此几何描述的一个显而易见却重要的结果是,最大间隔超平面完全是由最靠近它的那些
x
→
i
{\displaystyle {\vec {x}}_{i}}
确定的。这些
x
→
i
{\displaystyle {\vec {x}}_{i}}
叫做支持向量 。
为了将SVM扩展到数据线性不可分的情况,我们引入铰链损失 函数,
max
(
0
,
1
−
y
i
(
w
→
⋅
x
i
→
−
b
)
)
.
{\displaystyle \max \left(0,1-y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\right).}
当约束条件 (1) 满足时(也就是如果
x
→
i
{\displaystyle {\vec {x}}_{i}}
位于边距的正确一侧)此函数为零。对于间隔的错误一侧的数据,该函数的值与距间隔的距离成正比。
然后我们希望最小化
[
1
n
∑
i
=
1
n
max
(
0
,
1
−
y
i
(
w
→
⋅
x
i
→
−
b
)
)
]
+
λ
‖
w
→
‖
2
,
{\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}({\vec {w}}\cdot {\vec {x_{i}}}-b)\right)\right]+\lambda \lVert {\vec {w}}\rVert ^{2},}
其中参数
λ
{\displaystyle \lambda }
用来权衡增加间隔大小与确保
x
→
i
{\displaystyle {\vec {x}}_{i}}
位于间隔的正确一侧之间的关系。因此,对于足够小的
λ
{\displaystyle \lambda }
值,如果输入数据是可以线性分类的,则软间隔SVM与硬间隔SVM将表现相同,但即使不可线性分类,仍能学习出可行的分类规则。
核机器,图中核函数Φ,将低维非线性可分离函数(左)计算成高维线性可分离函数(右)
弗拉基米尔·瓦普尼克 在1963年提出的原始最大间隔超平面算法构造了一个线性分类器 。而1992年,伯恩哈德·E·博瑟(Bernhard E. Boser)、伊莎贝尔·M·盖昂(Isabelle M. Guyon)和瓦普尼克提出了一种通过将核技巧 (最初由Aizerman et al.[10] 提出)应用于最大边界超平面来创建非线性分类器的方法。[11] 所得到的算法形式上类似,除了把点积 换成了非线性核 函数。这就允许算法在变换后的特征空间 中拟合最大间隔超平面。该变换可以是非线性的,而变换空间是高维的;虽然分类器是变换后的特征空间中的超平面,但它在原始输入空间中可以是非线性的。
值得注意的是,更高维的特征空间增加了支持向量机的泛化误差 ,但给定足够多的样本,算法仍能表现良好。[12]
常见的核函数包括:
齐次多项式 :
k
(
x
i
→
,
x
j
→
)
=
(
x
i
→
⋅
x
j
→
)
d
{\displaystyle k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}})^{d}}
非齐次多项式 :
k
(
x
i
→
,
x
j
→
)
=
(
x
i
→
⋅
x
j
→
+
1
)
d
{\displaystyle k({\vec {x_{i}}},{\vec {x_{j}}})=({\vec {x_{i}}}\cdot {\vec {x_{j}}}+1)^{d}}
高斯径向基函数 :
k
(
x
i
→
,
x
j
→
)
=
exp
(
−
γ
‖
x
i
→
−
x
j
→
‖
2
)
{\displaystyle k({\vec {x_{i}}},{\vec {x_{j}}})=\exp(-\gamma \|{\vec {x_{i}}}-{\vec {x_{j}}}\|^{2})}
,其中
γ
>
0
{\displaystyle \gamma >0}
。有时参数化表示
γ
=
1
/
2
σ
2
{\displaystyle \gamma =1/{2\sigma ^{2}}}
双曲正切 :
k
(
x
i
→
,
x
j
→
)
=
tanh
(
κ
x
i
→
⋅
x
j
→
+
c
)
{\displaystyle k({\vec {x_{i}}},{\vec {x_{j}}})=\tanh(\kappa {\vec {x_{i}}}\cdot {\vec {x_{j}}}+c)}
,其中一些(而非所有)
κ
>
0
{\displaystyle \kappa >0}
且
c
<
0
{\displaystyle c<0}
由等式
k
(
x
i
→
,
x
j
→
)
=
φ
(
x
i
→
)
⋅
φ
(
x
j
→
)
{\displaystyle k({\vec {x_{i}}},{\vec {x_{j}}})=\varphi ({\vec {x_{i}}})\cdot \varphi ({\vec {x_{j}}})}
,核函数与变换
φ
(
x
i
→
)
{\displaystyle \varphi ({\vec {x_{i}}})}
有关。变换空间中也有 w 值,
w
→
=
∑
i
α
i
y
i
φ
(
x
→
i
)
{\displaystyle \textstyle {\vec {w}}=\sum _{i}\alpha _{i}y_{i}\varphi ({\vec {x}}_{i})}
。与 w 的点积也要用核技巧来计算,即
w
→
⋅
φ
(
x
→
)
=
∑
i
α
i
y
i
k
(
x
→
i
,
x
→
)
{\displaystyle \textstyle {\vec {w}}\cdot \varphi ({\vec {x}})=\sum _{i}\alpha _{i}y_{i}k({\vec {x}}_{i},{\vec {x}})}
。
计算(软间隔)SVM分类器等同于使下面表达式最小化
[
1
n
∑
i
=
1
n
max
(
0
,
1
−
y
i
(
w
⋅
x
i
+
b
)
)
]
+
λ
‖
w
‖
2
.
(
2
)
{\displaystyle \left[{\frac {1}{n}}\sum _{i=1}^{n}\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)\right]+\lambda \lVert w\rVert ^{2}.\qquad (2)}
如上所述,由于我们关注的是软间隔分类器,
λ
{\displaystyle \lambda }
选择足够小的值就能得到线性可分类输入数据的硬间隔分类器。下面会详细介绍将(2)简化为二次规划 问题的经典方法。之后会讨论一些最近才出现的方法,如次梯度下降法和坐标下降法。
最小化(2)可以用下面的方式改写为目标函数可微的约束优化问题。
对所有
i
∈
{
1
,
…
,
n
}
{\displaystyle i\in \{1,\,\ldots ,\,n\}}
我们引入变量
ζ
i
=
max
(
0
,
1
−
y
i
(
w
⋅
x
i
+
b
)
)
{\displaystyle \zeta _{i}=\max \left(0,1-y_{i}(w\cdot x_{i}+b)\right)}
。注意到
ζ
i
{\displaystyle \zeta _{i}}
是满足
y
i
(
w
⋅
x
i
+
b
)
≥
1
−
ζ
i
{\displaystyle y_{i}(w\cdot x_{i}+b)\geq 1-\zeta _{i}}
的最小非负数。
因此,我们可以将优化问题叙述如下
minimize
1
n
∑
i
=
1
n
ζ
i
+
λ
‖
w
‖
2
{\displaystyle {\text{minimize }}{\frac {1}{n}}\sum _{i=1}^{n}\zeta _{i}+\lambda \|w\|^{2}}
subject to
y
i
(
x
i
⋅
w
+
b
)
≥
1
−
ζ
i
and
ζ
i
≥
0
,
for all
i
.
{\displaystyle {\text{subject to }}y_{i}(x_{i}\cdot w+b)\geq 1-\zeta _{i}\,{\text{ and }}\,\zeta _{i}\geq 0,\,{\text{for all }}i.}
这就叫做原型 问题。