- 前言
- 一、SVM问题的基本形式
- 二、拉格朗日对偶算法
- 这就是一个典型的条件最值问题 (凸优化问题，约束最优化问题)
- 什么叫做对偶性?
- 用拉格朗日对偶算法求解SVM的问题
上一篇介绍了 一个点到直线距离的向量理解。
知道这个点到超平面的距离公式：
d
i
s
t
a
n
c
e
=
∣
d
∣
=
∣
w
T
x
+
b
∣
∥
w
∥
begin{array}{c} distance = left |d right | = frac{left |w^Tx+bright | }{left | w right | } end{array}
distance=∣d∣=∥w∥∣wTx+b∣
我们为什么要强调这个点的概念呢，很简单，因为这个点表示的就是数据点，也就是模型的特征。有多少个特征也就意味着这个 x 的长度大小 。
接下来将介绍SVM的原理以及详细的 拉格朗日对偶问题 推导过程。
以二分类为例子
对于一组已经知道的数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
(
x
N
,
y
N
)
}
begin{array}{c} D=left {(x_1,y_1),(x_2,y_2),...(x_N,y_N) right } end{array}
D={(x1,y1),(x2,y2),...(xN,yN)}其中
- x 表示为特征向量 x = ( x 0 , x 1 , . . . , x k ) T begin{array}{c} x = (x_0,x_1,...,x_k)^T end{array} x=(x0,x1,...,xk)T表示有k个特征.
- D 中有N 个数据样本。
- y表示的是改数据集的标签 label ，
y
i
=
+
1
begin{array}{c} y_i = +1 end{array}
yi=+1 与
y
i
=
−
1
begin{array}{c} y_i = -1 end{array}
yi=−1 分别标记为二分类的两个类。
为什么一个是+1，一个是-1?
前面我们推导过计算点到直线的距离的时候要再分子加个绝对值，这是因为一个超平面必然会划分出两个半空间，超平面是一个等于0 的方程。在超平面的上方的为正，则在下方的为负数。所以将一类标记为+1，一类标记为-1 时，可以化掉绝对值符号，用来表示距离：
d i s t a n c e = ∣ w T x + b ∣ ∥ w ∥ = y i ( w T x + b ) ∥ w ∥ begin{array}{c} distance = frac{left | boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b right | }{left | w right | } = frac{y_i(boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b)}{left | w right |} end{array} distance=∥w∥∣wTx+b∣=∥w∥yi(wTx+b)
由上图可知，要区分D中的两个类目标就是找出一个合理的超平面，图中的直线就是一个超平面。这个超平面必须具备两个功能。
1. 尽可能地让两个类别分在两个不同的半空间。
2. 两个类的点到超平面的距离越大越好。
超平面可以表示为：
w
T
x
+
b
=
0
begin{array}{c} boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b = 0 end{array}
wTx+b=0
显然两个半空间就是
w
T
x
+
b
>
0
begin{array}{c} boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b> 0 end{array}
wTx+b>0和
w
T
x
+
b
<
0
begin{array}{c} boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b <0 end{array}
wTx+b<0
在SVM问题中，这由于标签 y 标记为+1 ，-1 ，在数学上这两个半空间需要做小小改动。也就是：
{
w
T
x
+
b
⩾
+
1
,
y
i
=
+
1
w
T
x
+
b
⩽
−
1
,
y
i
=
−
1
begin{array}{c} left{begin{array}{ll} boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b geqslant+1, & y_{i}=+1 \ boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b leqslant-1, & y_{i}=-1 end{array}right. end{array}
{wTx+b⩾+1,wTx+b⩽−1,yi=+1yi=−1
为什么需要这样改动？/为什么是1？
这是因为要描述最优的超平面，最优在这里的含义就是尽可能地讲连个类别分开。在距离上定义上版空间要>1 ,下半空间<-1 是为了引出一个两个平行直线之间的 间隔 这一概念，然后“两个分类的数据点点到划分超平面的距离越远越好”问题就可以转换为 间隔越大越好。如图：
这样很容易得到这个间隔的大小为
γ
=
2
∥
w
∥
begin{array}{c} gamma = frac{2}{left | w right | } end{array}
γ=∥w∥2,也就是优化的目标。
“尽可能地让两个类别分在两个不同的半空间。”则是优化的约束条件，不能让样本点落在间隔之内。
也就是样本点到超平面的距离大于1,也就是：
y
i
(
w
T
x
+
b
)
≥
1
begin{array}{c} y_i(boldsymbol{w}^{mathrm{T}} boldsymbol{x}+b)ge 1 end{array}
yi(wTx+b)≥1
为什么是1？不用纠结这个数值，他就是表示一个“间隔”的意义，后面我们知道只需要最小化分母即可，与分母无关，这是一种问题的等价思想。
将它表示为凸优化问题：
max
2
∥
w
∥
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
…
,
N
begin{array}{c} maxfrac{2}{|w|} \ s.t. quad y_{i}left(boldsymbol{w}^{boldsymbol{T}} boldsymbol{x}_{boldsymbol{i}}+bright) geq 1, quad i=1,2, ldots, N end{array}
max∥w∥2s.t.yi(wTxi+b)≥1,i=1,2,…,N
最大化
γ
=
2
∥
w
∥
begin{array}{c} gamma = frac{2}{left | w right | } end{array}
γ=∥w∥2, 在凸优化问题上与最小化分母
∥
w
∥
begin{array}{c} left |w right | end{array}
∥w∥是等价的。因此就可以得出SVM 问题的基本形式：
min
1
2
∥
w
∥
2
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
…
,
N
begin{array}{c} min frac{1}{2}|w|^{2}\ s.t. quad y_{i}left(boldsymbol{w}^{boldsymbol{T}} boldsymbol{x}_{boldsymbol{i}}+bright) geq 1, quad i=1,2, ldots, N end{array}
min21∥w∥2s.t.yi(wTxi+b)≥1,i=1,2,…,N
- 插上一句：如果你学过高数，求解一个条件最值问题的时候，通常用拉格朗日乘子法来解。
1.构造拉格朗日函数，
2.分别求各个参数的一阶偏导数=0，
3.分情况讨论，求解最值。 - 在最优化理论里面步骤3就是作为的KKT条件。
- 回顾语文：对偶的修辞手法。“海阔凭鱼跃，天高任鸟飞。”这就是对偶。
- 那么拉格朗日的对偶性也是同样的含义：
简单来说： 一个极小极大问题，它的对偶问题就是极大极小问题。
以下latex 图片识别次数有限。手推了。
min
1
2
∥
w
∥
2
s
.
t
.
y
i
(
w
T
x
i
+
b
)
≥
1
,
i
=
1
,
2
,
…
,
N
begin{array}{c} min frac{1}{2}|w|^{2}\ s.t. quad y_{i}left(boldsymbol{w}^{boldsymbol{T}} boldsymbol{x}_{boldsymbol{i}}+bright) geq 1, quad i=1,2, ldots, N end{array}
min21∥w∥2s.t.yi(wTxi+b)≥1,i=1,2,…,N
构造拉格朗日函数：
L
(
x
,
λ
,
ν
)
=
f
0
(
x
)
+
∑
i
=
1
m
λ
i
c
i
(
x
)
+
∑
i
=
1
p
ν
i
h
i
(
x
)
begin{array}{c} L(x, lambda , nu )=f_0(x)+sum_{i=1}^{m} lambda _{i} c_{i}(x)+sum_{i=1}^{p} nu _{i} h_{i}(x) end{array}
L(x,λ,ν)=f0(x)+∑i=1mλici(x)+∑i=1pνihi(x)
原问题是拉格朗日函数的极小极大，则其对偶问题是拉格朗日函数的极大极小。
因此SVM问题的对偶算法求解思路是：
-
构造拉格朗日函数 L ( x , λ , ν ) begin{array}{c} L(x,lambda ,nu) end{array} L(x,λ,ν)
-
求一阶偏导数=0的x,代入拉格朗日函数，目的是找到最小的 L ( x , λ , ν ) begin{array}{c} L(x,lambda ,nu) end{array} L(x,λ,ν)使得求出对偶函数：
-
转化为通过优化拉格朗日乘子来优化出最大的对偶函数问题：
具体步骤：
- 非等式约束一律化为左边<= 右边的形式
min 1 2 ∥ w ∥ 2 s . t . − y i ( w T x i + b ) + 1 ≤ 0 , i = 1 , 2 , … , N begin{array}{c} min frac{1}{2}|w|^{2}\ s.t. quad -y_{i}left(boldsymbol{w}^{boldsymbol{T}} boldsymbol{x}_{boldsymbol{i}}+bright) +1le0, quad i=1,2, ldots, N end{array} min21∥w∥2s.t.−yi(wTxi+b)+1≤0,i=1,2,…,N - 构造拉格朗日函数：
化简一下等价于：
- 求w,b 的一阶偏导数，并且令一阶偏导数为0 得到：
即可得到：
- 将上面等式代入原拉格朗日函数即可得到对偶函数：
所以对 对偶函数 优化 λ lambda λ 的极大 既得到原问题的对偶问题：
对偶问题描述：
当原问题的解对偶问题的解和符合KKT条件时，为强对偶，这里不再证明。
接下来就是如果在对偶问题上求解SVM的解了，请看下篇SMO算法。
