参考文献:
机器学习数学:拉格朗日对偶问题
拉格朗日对偶问题
为什么支持向量机要用拉格朗日对偶算法来解最大化间隔问题?
零基础学SVM—Support Vector Machine(一)
1. SVM概念
支持向量机(英语:support vector machine,常简称为SVM,又名支持向量网络)是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例,每个训练实例被标记为属于两个类别中的一个或另一个,SVM训练算法创建一个将新的实例分配给两个类别之一的模型,使其成为非概率二元线性分类器。SVM模型是将实例表示为空间中的点,这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后,将新的实例映射到同一空间,并基于它们落在间隔的哪一侧来预测所属类别。
通俗的理解为我们在空间上设定一个超平面 ,分割所有的数据点,将其进行分类。关键点在于我们如何选择这个平面使他可以正常的将样本点分开。
2. 分割面(决策面)
对于一个二维平面中我们可以通过一条之间将每个点分隔开。
那么这个直线的方程正常情况下可以表示为:
y
=
w
x
+
b
y=wx+b
y=wx+b
如果我们将y同样看做为x则可以将上式转化为:
f
(
x
1
,
x
2
)
=
w
T
∗
x
+
b
f(x_1,x_2)=w^T*x+b
f(x1,x2)=wT∗x+b
其中x为一系列特征的组合,w为每个特征的特征值。
将这个二维空间的直线拓展到
N
N
N维即可得得到通用的一个分割面公式。
到现在我们得到了一个通用的分割面的方程。这个面就是我们所称的决策面。每一个决策面对应了一个分类器。
3. 分割间隔
我们现在已经知道分割面了,那从日常的经验可以得出分割面在中间时得到的分割效果最好。在此可以看出需要通过计算最大的分割距离使得分类的效果最好,即分割面所在的位置最佳。
点到直线的距离公式得到为:
从以上公式可以看出距离d最大等价条件为w的模最大。
3.1 硬间隔
对于我们所知的一条分割面,如果要求其所有的分类都是正确的,则我们称之为硬间隔。其中落在最大分割间隔上的点我们称之为支持向量(支持向量的字面理解为通过这些向量支持起一个曲面,使这个曲面可以正常的分类。这些向量其实是曲面的梯度方向)从支持向量的含义中我们可以看出,起决定性作用的是分布在平面上的点。
根据这样的思想我们可以得到所需要的限制条件
(2.2.3)式表示的是所有的点都被正确分类。加上我们所需要的的w模最大的条件(间隔距离最大)既可以得到我们所需要的最优间隔平面。
(2.2.4)中第二个不等式我们称之为约束条件,其含义为约束解所存在的范围,否则可能有无数的解存在。其意义可以看下图
对于这个约束条件其实有两个方面,一个为等式约束,一个为不等式约束。
3.1.1 等式约束
等式约束中表示其约束条件为等式其组合的方程组如下所示:
min
W
,
b
J
(
W
)
=
min
W
,
b
∥
W
∥
2
/
2
s
.
t
.
y
i
(
W
T
X
+
b
)
=
1
,
i
=
1
,
2
,
.
.
.
n
.
\begin{array}{cc}&\min_{W,b}J(W)=\min_{W,b}\left\|W\right\|^2/2\\s.t.&y_i(W^TX+b)=1,i=1,2,...n.\end{array}
s.t.minW,bJ(W)=minW,b∥W∥2/2yi(WTX+b)=1,i=1,2,...n.
那如何求解这个方程组?我们可以根据拉格朗日乘子法将约束条件整合到方程中,可以得到损失函数:
其中
α
i
=
1
,
2
,
3...
n
\alpha_i=1,2,3...n
αi=1,2,3...n,对于等式条件下的损失函数和约束条件为等式,是有唯一解的。
3.1.2 不等式约束
对于不等式约束其方程组为:
min
W
,
b
J
(
W
)
=
min
W
,
b
∥
W
∥
2
/
2
s
.
t
.
y
i
(
W
T
X
+
b
)
≥
1
,
i
=
1
,
2
,
.
.
.
n
.
\begin{array}{cc}&\min_{W,b}J(W)=\min_{W,b}\left\|W\right\|^2/2\\s.t.&y_i(W^TX+b)\geq1,i=1,2,...n.\end{array}
s.t.minW,bJ(W)=minW,b∥W∥2/2yi(WTX+b)≥1,i=1,2,...n.
同样是根据拉格朗日乘子法同样得到一个损失函数:
当不等式条件无法满足时:
否则,若满足不等式的约束条件,有
优化问题可以简化为:
根据拉格朗日对偶性,所述问题(2.4.4)即原始问题的对偶问题是:
3.1.2.1 拉格朗日对偶性
参考文献:
机器学习数学:拉格朗日对偶问题
拉格朗日对偶问题
对偶问题是利用拉格朗日对偶性将原始问题转换为对偶问题,通过解对偶问题得到原始问题的解。优点是:
- 对偶问题往往更易于求解自然引入核函数
- 推广到非线性分类问题的求解
原始问题
在限制条件下求最优值的普遍公式为:
对应我们的硬间隔公式:
极小极大问题
引入拉格朗日函数,由于约束条件有k+l个,所以我们有:
(求对x有限制条件的
f
(
x
)
f(x)
f(x)的最优化问题转为:对
α
,
β
,
x
\alpha,\beta,x
α,β,x 没有限制条件的,求
L
(
α
,
β
,
x
)
L(\alpha,\beta,x)
L(α,β,x)极值问题)
我们现在定义一个函数
θ
p
(
x
)
\theta_p(x)
θp(x)
- 假设有一个x,使得不满足原始问题的约束条件,即有c(x)>0或者h(x)!=0,那么上式求max的解为无穷大,因为可以取
θ
p
(
x
)
=
∞
\theta_p(x)=\infty
θp(x)=∞
- 相反,假设x满足原始问题的约束条件即
c
i
(
x
)
≤
0
c_i(x)\leq0
ci(x)≤0且
h
(
x
)
=
0
h(x)=0
h(x)=0,则可以求出上式中
α
\alpha
α最大值一定是0 ,同时
h
(
x
)
=
0
h(x)=0
h(x)=0,所以上式的最大值的条件不存在了,即最大值就是一个定值f(x).
- 所以在x满足原始问题约束的条件下,
θ
p
(
x
)
=
f
(
x
)
\theta_p(x)=f(x)
θp(x)=f(x)
因此如果需要求出f(x)的极值,也是就是将st给定条件省去后则可以得到公式:
对偶问题
我们得到的上式也就是被称为广义拉格朗日函数的极小极大问题,它与原问题是完全等价的。在对偶性中,这个问题被称为原始问题(Primal problem)。我们将上式中的最大值问题和最小值问题转换后就可以得到对偶问题。
m
a
x
α
,
β
,
α
i
≥
0
m
i
n
x
L
(
x
,
α
,
β
)
\underset{\alpha,\beta,\alpha_i\geq0}{max}\text{ }\underset x{min}L(x,\alpha,\beta)
α,β,αi≥0max xminL(x,α,β)
对偶函数可以理解为给原始函数找了一个下界,在原始函数计算困难的时候,可以通过解对偶函数来得到一个近似的值。并且在函数满足一定条件的时候,对偶函数的解与原始函数的解是等价的。
若原始问题和对偶问题都有最优值,则对偶问题最优值d∗
≤
\leq
≤ 原始问题最优值p∗:
当不满足我们给出的条件时我们将其称之为弱对偶性,弱对偶性对于优化问题都是存在的。而如果需要对偶问题和原始问题的最优值相等需要满足以下的几个条件:
-
f
(
x
)
,
c
i
(
x
)
f(x),c_i(x)
f(x),ci(x)为凸函数,满足凸优化的条件
- 不等式的约束为严格执行的,即
c
i
(
x
)
<
0
c_i(x)<0
ci(x)<0
这个条件在SVM中即变成了对任意一个点,都存在超平面能对其正确划分,也就是数据集是线性可分的。严格条件是强对偶性的充分条件,但并不是必要条件。有些不满足严格条件的可能也有强对偶性。
3.1.2.2 KKT条件
引用文献:
拉格朗日对偶性(Lagrange duality)
3.1.2.3 求不等式约束条件下的最优值
在了解了对偶问题以及其求解问题后我们再回来看我们损失函数的求解。
已知我们的最优问题为:
其对偶问题为:
为了求得对偶问题的解,需要先求得
L
(
W
,
b
,
α
)
L(W,b,\alpha)
L(W,b,α)对W和b的极小再求对
α
\alpha
α的极大。
在求最优化的
α
\alpha
α时,是需要满足约束条件的。我们可以通过二次规划,序列最小优化(Sequential Minimal Optimiation, SMO)算法进行求解。
3.2 软间隔
与硬间隔相对的,在分类时如果不严格要求所有的被分类点都被分类正确,则为软间隔。
3.2.1 软间隔最大化
我们的不等式约束和硬间隔一样,为:
为了使不满足上述条件的样本点尽可能少,我们需要在优化的目标函数里面新增一个对这些点的惩罚项。最常用的是hinge损失:
最优解可以优化为
其中C为惩罚项,C越大对分类错误的惩罚越大,当C为无穷大时则变为硬间隔。如果引入松弛变量
ζ
\zeta
ζ则优化的方程可以写作:
3.2.1 软间隔推导
3.3 非线性SVM
对于我们之前所提到的分割线都是线性的分割,对于有些数据我们进行线性的分割是无效的,这时需要使用非线性的方式进行分割。此时就需要用到核技巧(kernel trick)将线性支持向量机推广到非线性支持向量机。需要注意的是,不仅仅是SVM,很多线性模型都可以用核技巧推广到非线性模型,例如核线性判别分析(KLDA)。
3.3.1 核函数
核函数其基本思路为:将数据从原有的映射转换到一个新的空间(更高维度甚至无穷维度的空间)然后在新空间中使用线性方法从训练数据中学习模型。(也就是进行分类)
核函数的定义为:
通常通过映射计算出核函数的方式并不简单,同时我们还需要选择所需要的用到的映射,所以一般的情况下我们只需要选择合适的核函数即可。常用的核函数:
总结
支持向量机的优点是:
- 由于SVM是一个凸优化问题,所以求得的解一定是全局最优而不是局部最优。
- 不仅适用于线性线性问题还适用于非线性问题(用核技巧)。
- 拥有高维样本空间的数据也能用SVM,这是因为数据集的复杂度只取决于支持向量而不是数据集的维度,这在某种意义上避免了“维数灾难”。
- 理论基础比较完善(例如神经网络就更像一个黑盒子)。
支持向量机的缺点是:
- 二次规划问题求解将涉及m阶矩阵的计算(m为样本的个数), 因此SVM不适用于超大数据集。(SMO算法可以缓解这个问题)
- 只适用于二分类问题。(SVM的推广SVR也适用于回归问题;可以通过多个SVM的组合来解决多分类问题)