- 引言
- 回顾：最大间隔分类器
- 问题的转化过程
- 凸二次规划问题求解及其弊端
- 拉格朗日乘数法求解——原问题与无约束问题
- 小插曲：关于原问题与无约束问题等价的解释
- 无约束问题与对偶问题关联关系
- 模型求解
上一节介绍了支持向量机模型分类的朴素思想——最大间隔分类器，本节将利用拉格朗日乘数法进行分析。
回顾：最大间隔分类器最大间隔分类器选择最优模型 的朴素思想是：从能够将样本点分类正确的直线中找出这样一条直线：该直线与 N N N个样本点对应的 N N N个距离中找出长度最小的距离，而基于该直线找出的最小距离比其他直线的都要大，那么该直线即为所求。
使用数学语言进行表达：
max
W
,
b
min
x
(
i
)
∈
X
1
∣
∣
W
∣
∣
∣
W
T
x
(
i
)
+
b
∣
=
max
W
,
b
1
∣
∣
W
∣
∣
min
x
(
i
)
∈
X
y
(
i
)
(
W
T
x
(
i
)
+
b
)
\mathop{\max}\limits_{\mathcal W,b} \mathop{\min}\limits_{x^{(i)} \in \mathcal X} \frac{1}{||\mathcal W||}|\mathcal W^{T}x^{(i)} + b| = \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||} \mathop{\min}\limits_{x^{(i)} \in \mathcal X} y^{(i)}\left(\mathcal W^{T}x^{(i)} + b \right)
W,bmaxx(i)∈Xmin∣∣W∣∣1∣WTx(i)+b∣=W,bmax∣∣W∣∣1x(i)∈Xminy(i)(WTx(i)+b) 其中
X
\mathcal X
X表示样本集合
{
x
(
1
)
,
x
(
2
)
,
⋯
,
x
(
N
)
}
\{x^{(1)},x^{(2)},\cdots,x^{(N)}\}
{x(1),x(2),⋯,x(N)}，约束条件即直线能够将所有样本点分类正确：
y
(
i
)
(
W
T
x
(
i
)
+
b
)
>
0
∀
(
x
(
i
)
,
y
(
i
)
)
∈
D
a
t
a
y^{(i)}(\mathcal W^{T}x^{(i)} + b) > 0 \quad \forall (x^{(i)},y^{(i)}) \in Data
y(i)(WTx(i)+b)>0∀(x(i),y(i))∈Data 至此，最大间隔分类器朴素思想表示如下：
{
max
W
,
b
1
∣
∣
W
∣
∣
min
x
(
i
)
∈
X
y
(
i
)
(
W
T
x
(
i
)
+
b
)
s
.
t
.
y
(
i
)
(
W
T
x
(
i
)
+
b
)
>
0
\begin{cases} \mathop{\max}\limits_{\mathcal W,b} \frac{1}{||\mathcal W||} \mathop{\min}\limits_{x^{(i)} \in \mathcal X} y^{(i)}\left(\mathcal W^{T}x^{(i)} + b \right) \\ s.t. \quad y^{(i)}(\mathcal W^{T}x^{(i)} + b) > 0 \end{cases}
⎩
⎨
⎧W,bmax∣∣W∣∣1x(i)∈Xminy(i)(WTx(i)+b)s.t.y(i)(WTx(i)+b)>0 经过对函数间隔(Function Margin)的约束，化简结果为： 函数间隔的相关介绍同见上一节
{
min
W
,
b
1
2
W
T
W
s
.
t
.
y
(
i
)
(
W
T
x
(
i
)
+
b
)
≥
1
∀
(
x
(
i
)
,
y
(
i
)
)
∈
D
a
t
a
\begin{cases} \mathop{\min}\limits_{\mathcal W,b} \frac{1}{2} \mathcal W^{T}\mathcal W \\ s.t. \quad y^{(i)}(\mathcal W^{T}x^{(i)} + b) \geq 1 \quad \forall (x^{(i)},y^{(i)}) \in Data \end{cases}
⎩
⎨
⎧W,bmin21WTWs.t.y(i)(WTx(i)+b)≥1∀(x(i),y(i))∈Data
可以将上式理解成包含 N N N个约束条件的凸优化问题( 1 2 W T W \frac{1}{2}\mathcal W^{T}\mathcal W 21WTW是一个凸函数，每一个 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))均对应一个约束条件)。 将约束条件移项，将其写成如下形式： { min W , b 1 2 W T W s . t . 1 − y ( i ) ( W T x ( i ) + b ) ≤ 0 ∀ ( x ( i ) , y ( i ) ) ∈ D a t a \begin{cases}\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2} \mathcal W^{T}\mathcal W \\ s.t. \quad 1 - y^{(i)}(\mathcal W^{T}x^{(i)} + b) \leq 0 \quad \forall (x^{(i)},y^{(i)}) \in Data \end{cases} ⎩ ⎨ ⎧W,bmin21WTWs.t.1−y(i)(WTx(i)+b)≤0∀(x(i),y(i))∈Data
观察，目标函数
1
2
W
T
W
\frac{1}{2}\mathcal W^{T}\mathcal W
21WTW是一个二次型函数。即：
f
(
W
)
=
1
2
W
T
W
=
1
2
(
w
1
,
w
2
,
⋯
,
w
p
)
(
w
1
w
2
⋮
w
p
)
=
1
2
(
w
1
2
+
w
2
2
+
⋯
+
w
p
2
)
f(\mathcal W) =\frac{1}{2}\mathcal W^{T}\mathcal W =\frac{1}{2}(w_1,w_2,\cdots,w_p)\begin{pmatrix}w_1 \\ w_2 \\ \vdots \\ w_p\end{pmatrix} = \frac{1}{2}(w_1^2 + w_2^2 + \cdots +w_p^2)
f(W)=21WTW=21(w1,w2,⋯,wp)
w1w2⋮wp
=21(w12+w22+⋯+wp2) 并且
N
N
N个约束均为不等式约束，且每个不等式约束均为仿射函数(affine function)，即 最高次数为1的多项式函数：
w
i
(
i
=
1
,
2
,
⋯
p
)
,
b
w_i(i=1,2,\cdots p),b
wi(i=1,2,⋯p),b均是一次项。
g
(
W
,
b
)
=
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
=
1
−
y
(
i
)
[
(
w
1
,
w
2
,
⋯
,
w
p
)
(
x
1
(
i
)
x
2
(
i
)
⋮
x
p
(
i
)
)
+
b
]
=
1
−
y
(
i
)
(
w
1
⋅
x
1
(
i
)
+
w
2
⋅
x
2
(
i
)
+
⋯
+
w
p
⋅
x
p
(
i
)
+
b
)
\begin{aligned}g(\mathcal W,b) & = 1 - y^{(i)}(\mathcal W^{T}x^{(i)} + b) \\ & = 1 - y^{(i)}\left[(w_1,w_2,\cdots,w_p)\begin{pmatrix}x_1^{(i)} \\ x_2^{(i)} \\ \vdots \\ x_p^{(i)}\end{pmatrix} + b \right] \\ & = 1 - y^{(i)}(w_1\cdot x_1^{(i)} + w_2 \cdot x_2^{(i)} + \cdots +w_p \cdot x_p^{(i)} + b) \end{aligned}
g(W,b)=1−y(i)(WTx(i)+b)=1−y(i)
(w1,w2,⋯,wp)
x1(i)x2(i)⋮xp(i)
+b
=1−y(i)(w1⋅x1(i)+w2⋅x2(i)+⋯+wp⋅xp(i)+b)
至此，该问题从凸优化问题转化为一个 凸二次规划问题(Convex Quadratic Programming)。凸二次规划问题存在解，但是对凸二次规划问题求解存在较高约束： 理想状态下：
- 样本空间(样本点 x ( i ) x^{(i)} x(i)的维度)或者特征空间( W \mathcal W W的维度) p p p不高；
- 样本空间中的样本数量 N N N不多；
这种情况下对凸二次规划问题求解是方便的。但实际情况下，样本数量和特征空间维度都很高，甚至存在将样本点 x ( i ) x^{(i)} x(i)的维度通过特征转换将其映射到高维空间甚至是无限维空间。这种情况下，凸二次规划很难求解。本节将介绍通过求解对偶问题对原问题进行求解。
拉格朗日乘数法求解——原问题与无约束问题继续观察化简结果：
{
min
W
,
b
1
2
W
T
W
s
.
t
.
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
≤
0
∀
(
x
(
i
)
,
y
(
i
)
)
∈
D
a
t
a
\begin{cases}\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2} \mathcal W^{T}\mathcal W \\ s.t. \quad 1 - y^{(i)}(\mathcal W^{T}x^{(i)} + b) \leq 0 \quad \forall (x^{(i)},y^{(i)}) \in Data \end{cases}
⎩
⎨
⎧W,bmin21WTWs.t.1−y(i)(WTx(i)+b)≤0∀(x(i),y(i))∈Data 将该化简结果称为原问题(Primal Problem),使用拉格朗日乘数法引出它的无约束原问题。 首先，列出原问题的拉格朗日函数
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)： 由于‘原问题’中包含
N
N
N个约束条件，因此
λ
\lambda
λ中一共包含
N
N
N个分量：
λ
=
{
λ
(
1
)
,
λ
(
2
)
,
⋯
,
λ
(
N
)
}
L
(
W
,
b
,
λ
)
=
1
2
W
T
W
+
∑
i
=
1
N
λ
(
i
)
[
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
]
\lambda = \{\lambda^{(1)},\lambda^{(2)},\cdots,\lambda^{(N)}\} \\ \mathcal L(\mathcal W,b,\lambda) = \frac{1}{2} \mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right]
λ={λ(1),λ(2),⋯,λ(N)}L(W,b,λ)=21WTW+i=1∑Nλ(i)[1−y(i)(WTx(i)+b)] 根据拉格朗日函数自身性质，
λ
(
i
)
(
i
=
1
,
2
,
⋯
,
N
)
≥
0
\lambda^{(i)}(i=1,2,\cdots,N)\geq 0
λ(i)(i=1,2,⋯,N)≥0
至此，原问题通过拉格朗日函数转化为如下形式： { min W , b max λ L ( W , b , λ ) s . t . λ ( i ) ≥ 0 ( i = 1 , 2 , ⋯ , N ) \begin{cases}\mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) \\ s.t. \quad \lambda^{(i)} \geq 0 \quad (i=1,2,\cdots,N)\end{cases} ⎩ ⎨ ⎧W,bminλmaxL(W,b,λ)s.t.λ(i)≥0(i=1,2,⋯,N)
观察上述式子，和原问题相比，原问题的约束条件被拉格朗日乘数
λ
\lambda
λ并入到了目标函数中，新式子的约束条件中多出关于
λ
\lambda
λ的约束条件。称该式子为 无约束原问题。 这里的无约束指‘带约束原问题’的约束条件消失了。对于求解模型参数
W
,
b
\mathcal W,b
W,b,原问题与无约束问题是等价的。
在求解最优模型参数过程中，为什么 原问题和无约束原问题是等价的？ 观察拉格朗日函数 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)： L ( W , b , λ ) = 1 2 W T W + ∑ i = 1 N λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] \mathcal L(\mathcal W,b,\lambda) = \frac{1}{2} \mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right] L(W,b,λ)=21WTW+i=1∑Nλ(i)[1−y(i)(WTx(i)+b)]
1 − y ( i ) ( W T x ( i ) + b ) 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) 1−y(i)(WTx(i)+b)具有什么意义？结合回顾中的介绍，它的实际意义如下：
- 1 − y ( i ) ( W T x ( i ) + b ) ≤ 0 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \leq 0 1−y(i)(WTx(i)+b)≤0，意味着直线 W T x + b = 0 \mathcal W^{T}x + b = 0 WTx+b=0对具体样本 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))分类正确；
- 反之， 1 − y ( i ) ( W T x ( i ) + b ) > 0 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) > 0 1−y(i)(WTx(i)+b)>0，意味着直线 W T x ( i ) + b = 0 \mathcal W^{T}x^{(i)} + b = 0 WTx(i)+b=0对具体样本 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))分类错误；
由于 在介绍最大间隔分类器朴素思想 时，就已经说明了前提条件：基于样本点分类正确的基础上。
假如并没有提到这个条件，即当前直线存在样本点被分类错误。数学语言表达即： ∃ ( x ( i ) , y ( i ) ) ∈ D a t a → 1 − y ( i ) ( W T x ( i ) + b ) > 0 \exists (x^{(i)},y^{(i)}) \in Data \to 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) > 0 ∃(x(i),y(i))∈Data→1−y(i)(WTx(i)+b)>0 将上述两种情况分别带入拉格朗日函数 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)中进行分析：
-
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
>
0
1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) > 0
1−y(i)(WTx(i)+b)>0时，已知
λ
(
i
)
≥
0
\lambda^{(i)} \geq 0
λ(i)≥0恒成立，则
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda)
λmaxL(W,b,λ)结果表示如下：
由于λ ( i ) \lambda^{(i)} λ(i)与1 − y ( i ) ( W T x ( i ) + b ) 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) 1−y(i)(WTx(i)+b)同号，因此∑ i = 1 N λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right] ∑i=1Nλ(i)[1−y(i)(WTx(i)+b)]部分没有上界，即当λ ( i ) \lambda^{(i)} λ(i)均取值∞ \infty ∞时,max λ L ( W , b , λ ) \mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda) λmaxL(W,b,λ)取得最大值∞ \infty ∞; max λ L ( W , b , λ ) = 1 2 W T W + ∑ i = 1 N λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] = 1 2 W T W + ∑ i = 1 N ∞ = ∞ \begin{aligned}\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda) & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right] \\ & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \infty \\ & = \infty \end{aligned} λmaxL(W,b,λ)=21WTW+i=1∑Nλ(i)[1−y(i)(WTx(i)+b)]=21WTW+i=1∑N∞=∞ -
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
≤
0
1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \leq 0
1−y(i)(WTx(i)+b)≤0时，同理，对应的
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda)
λmaxL(W,b,λ)结果表示如下：
由于λ ( i ) \lambda^{(i)} λ(i)与1 − y ( i ) ( W T x ( i ) + b ) 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) 1−y(i)(WTx(i)+b)异号，因此∑ i = 1 N λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right] ∑i=1Nλ(i)[1−y(i)(WTx(i)+b)]结果是’非正数‘，即存在上界0，当λ ( i ) = 0 ( i = 1 , 2 , ⋯ , N ) \lambda^{(i)} = 0 (i=1,2,\cdots,N) λ(i)=0(i=1,2,⋯,N)时，max λ L ( W , b , λ ) \mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda) λmaxL(W,b,λ)取得最大值1 2 W T W \frac{1}{2}\mathcal W^{T}\mathcal W 21WTW； max λ L ( W , b , λ ) = 1 2 W T W + ∑ i = 1 N λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] = 1 2 W T W + ∑ i = 1 N 0 = 1 2 W T W \begin{aligned}\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda) & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} \left[1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \right] \\ & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N 0 \\ & = \frac{1}{2}\mathcal W^{T}\mathcal W \end{aligned} λmaxL(W,b,λ)=21WTW+i=1∑Nλ(i)[1−y(i)(WTx(i)+b)]=21WTW+i=1∑N0=21WTW - 综上，目标函数
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)
W,bminλmaxL(W,b,λ)可以表示为如下形式：
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)
λmaxL(W,b,λ)
结果由两部分组成：{ ∞ , 1 2 W T W } \{\infty,\frac{1}{2}\mathcal W^{T}\mathcal W\} {∞,21WTW},对∞ \infty ∞取最小值没有意义；只能对1 2 W T W \frac{1}{2}\mathcal W^{T}\mathcal W 21WTW取最小值。 min W , b max λ L ( W , b , λ ) = min W , b { ∞ , 1 2 W T W } = min W , b 1 2 W T W \mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) = \mathop{\min}\limits_{\mathcal W,b}\{\infty,\frac{1}{2}\mathcal W^{T}\mathcal W\}=\mathop{\min}\limits_{\mathcal W,b} \frac{1}{2}\mathcal W^{T}\mathcal W W,bminλmaxL(W,b,λ)=W,bmin{∞,21WTW}=W,bmin21WTW
最终结果发现和原问题的目标函数完全相同。回顾整个推导过程，这意味着 λ ( i ) ≥ 0 ( i = 1 , 2 , ⋯ , N ) \lambda^{(i)} \geq 0(i=1,2,\cdots,N) λ(i)≥0(i=1,2,⋯,N)条件满足的同时，还隐含地满足了另一个条件： 1 − y ( i ) ( W T x ( i ) + b ) ≤ 0 1 - y^{(i)} \left(\mathcal W^{T}x^{(i)} + b\right) \leq 0 1−y(i)(WTx(i)+b)≤0
无约束问题与对偶问题关联关系基于无约束问题，它的 对偶问题表示如下： { max λ min W , b L ( W , b , λ ) s . t . λ ( i ) ≥ 0 ( i = 1 , 2 , ⋯ , N ) \begin{cases}\mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \\ s.t. \quad \lambda^{(i)} \geq 0 \quad (i=1,2,\cdots,N)\end{cases} ⎩ ⎨ ⎧λmaxW,bminL(W,b,λ)s.t.λ(i)≥0(i=1,2,⋯,N) 从数学角度观察，无约束问题也是原问题，即“没有约束的原问题”，它和对偶问题之间存在对偶关系。从公式中表示即 min , max \min,\max min,max调换了位置，约束条件没有变化。
首先探究：无约束问题的目标函数与其对偶问题的目标函数之间的关系。即： min W , b max λ L ( W , b , λ ) ⇔ ? max λ min W , b L ( W , b , λ ) \mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)\overset{\text{?}}{\Leftrightarrow}\mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) W,bminλmaxL(W,b,λ)⇔?λmaxW,bminL(W,b,λ) 如果没有其他限制条件，该问题是被数学证明了的，其结果为：对偶问题 ≤ \leq ≤ 原问题。即： min W , b max λ L ( W , b , λ ) ≥ max λ min W , b L ( W , b , λ ) \mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)\geq \mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) W,bminλmaxL(W,b,λ)≥λmaxW,bminL(W,b,λ)
具体证明如下： 首先观察公式两端的前半部分：
- 公式左端： max λ L ( W , b , λ ) ≥ L ( W , b , λ ) \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) \geq \mathcal L(\mathcal W,b,\lambda) λmaxL(W,b,λ)≥L(W,b,λ)恒成立。 解释：从字面意义上解释 max λ L ( W , b , λ ) \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) λmaxL(W,b,λ)，即：通过选择最优参数 λ \lambda λ，选择该参数的结果是：使 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)最大。那么它 必然大于等于任意一个 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)结果；
- 同理，公式右端： min W , b L ( W , b , λ ) ≤ L ( W , b , λ ) \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \leq \mathcal L(\mathcal W,b,\lambda) W,bminL(W,b,λ)≤L(W,b,λ)恒成立。即： min W , b L ( W , b , λ ) \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) W,bminL(W,b,λ)是关于 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)的最小值，那么它必然小于等于任意一个 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)结果；
综上，我们可以得到如下关系：
min
W
,
b
L
(
W
,
b
,
λ
)
≤
L
(
W
,
b
,
λ
)
≤
max
λ
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \leq \mathcal L(\mathcal W,b,\lambda) \leq \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)
W,bminL(W,b,λ)≤L(W,b,λ)≤λmaxL(W,b,λ) 即：
min
W
,
b
L
(
W
,
b
,
λ
)
≤
max
λ
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \leq \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)
W,bminL(W,b,λ)≤λmaxL(W,b,λ) 此时令
min
W
,
b
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda)
W,bminL(W,b,λ)是关于
λ
\lambda
λ的函数： 原因：
W
,
b
\mathcal W,b
W,b已经被确定，对应结果是’使
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)最小’。因此，该式中仅包含
λ
\lambda
λ一个变量;
min
W
,
b
L
(
W
,
b
,
λ
)
=
A
(
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) = \mathcal A(\lambda)
W,bminL(W,b,λ)=A(λ) 同理，令
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)
λmaxL(W,b,λ)是关于
W
,
b
\mathcal W,b
W,b的函数： 原因：与上面类似~
max
λ
L
(
W
,
b
,
λ
)
=
B
(
W
,
b
)
\mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) = \mathcal B(\mathcal W,b)
λmaxL(W,b,λ)=B(W,b) 则有：
A
(
λ
)
≤
B
(
W
,
b
)
\mathcal A(\lambda)\leq \mathcal B(\mathcal W,b)
A(λ)≤B(W,b) 那么：基于上述公式，
A
(
λ
)
\mathcal A(\lambda)
A(λ)必然小于等于
B
(
W
,
b
)
\mathcal B(\mathcal W,b)
B(W,b)的最小值。即：
A
(
λ
)
≤
min
W
,
b
B
(
W
,
b
)
\mathcal A(\lambda) \leq \mathop{\min}\limits_{\mathcal W,b} \mathcal B(\mathcal W,b)
A(λ)≤W,bminB(W,b) 同理，基于上述公式，
A
(
λ
)
\mathcal A(\lambda)
A(λ)中的最大值
max
λ
A
(
λ
)
\mathop{\max}\limits_{\lambda} \mathcal A(\lambda)
λmaxA(λ)也必然小于
B
(
W
,
b
)
\mathcal B(\mathcal W,b)
B(W,b)中的任意一个结果，包括最小值
min
W
,
b
B
(
W
,
b
)
\mathop{\min}\limits_{\mathcal W,b}\mathcal B(\mathcal W,b)
W,bminB(W,b)。即：
max
λ
A
(
λ
)
≤
min
W
,
b
B
(
W
,
b
)
\mathop{\max}\limits_{\lambda} \mathcal A(\lambda) \leq \mathop{\min}\limits_{\mathcal W,b}\mathcal B(\mathcal W,b)
λmaxA(λ)≤W,bminB(W,b) 将
A
(
λ
)
,
B
(
W
,
b
)
\mathcal A(\lambda),\mathcal B(\mathcal W,b)
A(λ),B(W,b)进行替换，即可得到如下公式：
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
≥
max
λ
min
W
,
b
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda)\geq \mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda)
W,bminλmaxL(W,b,λ)≥λmaxW,bminL(W,b,λ) 证明完毕。 我们称该关系为弱对偶关系。与弱对偶关系相反的是强对偶关系。强对偶关系表示如下：
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
=
max
λ
min
W
,
b
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathop{\max}\limits_{\lambda}\mathcal L(\mathcal W,b,\lambda) = \mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda)
W,bminλmaxL(W,b,λ)=λmaxW,bminL(W,b,λ) 从弱对偶关系到强对偶关系需要满足一些条件。由于原问题是凸二次规划问题，该类问题可以通过数学证明其原问题与对偶问题之间是强对偶关系。这里篇幅有限，不在此证明了。
至此，无约束问题和它的对偶问题是强对偶关系，因次它们之间是等价关系。
模型求解重新观察对偶问题：
{
max
λ
min
W
,
b
L
(
W
,
b
,
λ
)
s
.
t
.
λ
(
i
)
≥
0
(
i
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\max}\limits_{\lambda} \mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \\ s.t. \quad \lambda^{(i)} \geq 0 \quad (i=1,2,\cdots,N)\end{cases}
⎩
⎨
⎧λmaxW,bminL(W,b,λ)s.t.λ(i)≥0(i=1,2,⋯,N) 继续观察目标函数的前半部分：
min
W
,
b
L
(
W
,
b
,
λ
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda)
W,bminL(W,b,λ) 可以将其理解为：求解最优参数
W
,
b
\mathcal W,b
W,b使
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)最小。由于上式中对
λ
\lambda
λ没有任何约束，因此将
λ
\lambda
λ视作常数，直接分别对
W
,
b
\mathcal W,b
W,b求导： 个人理解：之所以要求解其‘对偶问题‘，原因在于’无约束问题‘的前半部分是关于
λ
\lambda
λ的函数，而
λ
\lambda
λ存在约束条件，不容易直接求解。
- 首先对参数
b
b
b进行求导(
W
\mathcal W
W同样被视作常数)：
展开的大括号中只有最后一项包含b b b,其余均视作常数;∂ L ( W , b , λ ) ∂ b = ∂ ∂ b [ 1 2 W T W + ∑ i = 1 N λ ( i ) − ∑ i = 1 N λ ( i ) y ( i ) W T x ( i ) − ∑ i = 1 N λ ( i ) y ( i ) b ] = ∂ ∂ b [ − ∑ i = 1 N λ ( i ) y ( i ) b ] = − ∑ i = 1 N λ ( i ) y ( i ) \begin{aligned} \frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial b} & = \frac{\partial}{\partial b}\left[\frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)} - \sum_{i=1}^N \lambda^{(i)}y^{(i)}b \right] \\ & = \frac{\partial}{\partial b}\left[-\sum_{i=1}^N \lambda^{(i)} y^{(i)} b \right] \\ & = -\sum_{i=1}^N\lambda^{(i)}y^{(i)} \end{aligned} ∂b∂L(W,b,λ)=∂b∂[21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i)−i=1∑Nλ(i)y(i)b]=∂b∂[−i=1∑Nλ(i)y(i)b]=−i=1∑Nλ(i)y(i) 令 ∂ L ( W , b , λ ) ∂ b ≜ 0 \frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial b} \triangleq 0 ∂b∂L(W,b,λ)≜0，此时得到一个新的条件： ∑ i = 1 N λ ( i ) y ( i ) = 0 \sum_{i=1}^N \lambda^{(i)}y^{(i)} = 0 i=1∑Nλ(i)y(i)=0
将该条件重新带回
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)，对拉格朗日函数进行化简： 展开的最后一项中
b
b
b不含
i
i
i,因此视作常数，提到连加号前面；又因为新条件，最后一项消除；但由于第三项中包含
x
(
i
)
x^{(i)}
x(i),因此不能被消除；
L
(
W
,
b
,
λ
)
=
1
2
W
T
W
+
∑
i
=
1
N
λ
(
i
)
−
∑
i
=
1
N
λ
(
i
)
y
(
i
)
W
T
x
(
i
)
−
∑
i
=
1
N
λ
(
i
)
y
(
i
)
b
=
1
2
W
T
W
+
∑
i
=
1
N
λ
(
i
)
−
∑
i
=
1
N
λ
(
i
)
y
(
i
)
W
T
x
(
i
)
−
b
∑
i
=
1
N
λ
(
i
)
y
(
i
)
=
1
2
W
T
W
+
∑
i
=
1
N
λ
(
i
)
−
∑
i
=
1
N
λ
(
i
)
y
(
i
)
W
T
x
(
i
)
\begin{aligned}\mathcal L(\mathcal W,b,\lambda) & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)} - \sum_{i=1}^N \lambda^{(i)}y^{(i)}b \\ & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)} - b\sum_{i=1}^N \lambda^{(i)}y^{(i)} \\ & = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)} \end{aligned}
L(W,b,λ)=21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i)−i=1∑Nλ(i)y(i)b=21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i)−bi=1∑Nλ(i)y(i)=21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i) 对化简结果继续对
W
\mathcal W
W进行求导： 大括号中只有第一项和第三项含
W
\mathcal W
W,这里仍然使用矩阵论中的矩阵求导法则~
1
2
W
T
W
∂
W
=
1
2
⋅
2
⋅
W
=
W
∑
i
=
1
N
λ
(
i
)
y
(
i
)
W
T
x
(
i
)
∂
W
=
∑
i
=
1
N
λ
(
i
)
y
(
i
)
x
(
i
)
\begin{aligned} \frac{\frac{1}{2} \mathcal W^{T}\mathcal W}{\partial \mathcal W} & = \frac{1}{2} \cdot 2 \cdot \mathcal W = \mathcal W \\ \frac{\sum_{i=1}^N \lambda^{(i)} y^{(i)} \mathcal W^{T}x^{(i)}}{\partial \mathcal W} &=\sum_{i=1}^N\lambda^{(i)}y^{(i)}x^{(i)} \end{aligned}
∂W21WTW∂W∑i=1Nλ(i)y(i)WTx(i)=21⋅2⋅W=W=i=1∑Nλ(i)y(i)x(i)
求导结果如下： L ( W , b , λ ) ∂ W = ∂ ∂ W [ 1 2 W T W + ∑ i = 1 N λ ( i ) − ∑ i = 1 N λ ( i ) y ( i ) W T x ( i ) ] = 1 2 ⋅ 2 ⋅ W − ∑ i = 1 N λ ( i ) y ( i ) x ( i ) \begin{aligned} \frac{\mathcal L(\mathcal W,b,\lambda)}{\partial \mathcal W} & = \frac{\partial}{\partial \mathcal W}\left[\frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)}\right] \\ & = \frac{1}{2} \cdot 2 \cdot \mathcal W - \sum_{i=1}^N\lambda^{(i)}y^{(i)}x^{(i)} \end{aligned} ∂WL(W,b,λ)=∂W∂[21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i)]=21⋅2⋅W−i=1∑Nλ(i)y(i)x(i)
继续令 L ( W , b , λ ) ∂ W ≜ 0 \frac{\mathcal L(\mathcal W,b,\lambda)}{\partial \mathcal W} \triangleq 0 ∂WL(W,b,λ)≜0，则有： W = ∑ i = 1 N λ ( i ) y ( i ) x ( i ) \mathcal W = \sum_{i=1}^N \lambda^{(i)}y^{(i)}x^{(i)} W=i=1∑Nλ(i)y(i)x(i) 最后，将 W \mathcal W W的表达式带回第一次化简后的 L ( W , b , λ ) \mathcal L(\mathcal W,b,\lambda) L(W,b,λ)中，此时该函数是只关于参数 λ \lambda λ的一个函数： W = ∑ i = 1 N λ ( i ) y ( i ) x ( i ) → L ( W , b , λ ) = 1 2 W T W + ∑ i = 1 N λ ( i ) − ∑ i = 1 N λ ( i ) y ( i ) W T x ( i ) L ( W , b , λ ) = 1 2 ( ∑ i = 1 N λ ( i ) y ( i ) x ( i ) ) T ( ∑ j = 1 N λ ( j ) y ( j ) x ( j ) ) + ∑ i = 1 N λ ( i ) − ∑ i = 1 N [ λ ( i ) y ( i ) ( ∑ i = 1 N λ ( i ) y ( i ) x ( i ) ) T x ( i ) ] \mathcal W = \sum_{i=1}^N \lambda^{(i)}y^{(i)}x^{(i)} \to \mathcal L(\mathcal W,b,\lambda) = \frac{1}{2}\mathcal W^{T}\mathcal W + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N\lambda^{(i)} y^{(i)}\mathcal W^{T}x^{(i)} \\ \begin{aligned} \mathcal L(\mathcal W,b,\lambda) & = \frac{1}{2}\left(\sum_{i=1}^N \lambda^{(i)}y^{(i)}x^{(i)}\right)^{T}\left(\sum_{j=1}^N \lambda^{(j)}y^{(j)}x^{(j)}\right) + \sum_{i=1}^N \lambda^{(i)} - \sum_{i=1}^N \left[\lambda^{(i)} y^{(i)}\left(\sum_{i=1}^N \lambda^{(i)}y^{(i)}x^{(i)}\right)^{T}x^{(i)} \right]\\ \end{aligned} W=i=1∑Nλ(i)y(i)x(i)→L(W,b,λ)=21WTW+i=1∑Nλ(i)−i=1∑Nλ(i)y(i)WTx(i)L(W,b,λ)=21(i=1∑Nλ(i)y(i)x(i))T(j=1∑Nλ(j)y(j)x(j))+i=1∑Nλ(i)−i=1∑N λ(i)y(i)(i=1∑Nλ(i)y(i)x(i))Tx(i) 观察第一项，由于 λ ( i ) \lambda^{(i)} λ(i)是每个样本点 ( x ( i ) , y ( i ) ) (x^{(i)},y^{(i)}) (x(i),y(i))对应的 拉格朗日乘数，是一个标量、常数； y ( i ) ∈ { − 1 , 1 } y^{(i)} \in \{-1,1\} y(i)∈{−1,1}，也是一个标量、常数；因此则有： ( λ ( i ) ) T = λ ( i ) ; ( y ( i ) ) T = y ( i ) \left(\lambda^{(i)}\right)^{T} = \lambda^{(i)};\left(y^{(i)}\right)^{T} = y^{(i)} (λ(i))T=λ(i);(y(i))T=y(i)
至此，将第一项展开，并将上式带入：
1
2
[
∑
i
=
1
N
∑
j
=
1
N
λ
(
i
)
λ
(
j
)
y
(
i
)
y
(
j
)
(
x
(
i
)
)
T
x
(
j
)
]
\frac{1}{2} \left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right]
21[i=1∑Nj=1∑Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)] 同理，将第三项展开，并将上式带入：
[
∑
i
=
1
N
∑
j
=
1
N
λ
(
i
)
λ
(
j
)
y
(
i
)
y
(
j
)
(
x
(
i
)
)
T
x
(
j
)
]
\left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right]
[i=1∑Nj=1∑Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)] 发现，第一项与第三项之间只有系数上的差异。重新将三项合并，得到最终的
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)结果： 此时结果只包含
λ
(
i
)
(
i
=
1
,
2
,
⋯
,
N
)
\lambda^{(i)}(i=1,2,\cdots,N)
λ(i)(i=1,2,⋯,N)一种类型的变量。
L
(
W
,
b
,
λ
)
=
−
1
2
[
∑
i
=
1
N
∑
j
=
1
N
λ
(
i
)
λ
(
j
)
y
(
i
)
y
(
j
)
(
x
(
i
)
)
T
x
(
j
)
]
+
∑
i
=
1
N
λ
(
i
)
\mathcal L(\mathcal W,b,\lambda) = -\frac{1}{2} \left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right] + \sum_{i=1}^N\lambda^{(i)}
L(W,b,λ)=−21[i=1∑Nj=1∑Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)]+i=1∑Nλ(i) 由于对
b
b
b求解偏导化为了新的条件；对
W
\mathcal W
W求偏导得到了
W
\mathcal W
W关于
λ
\lambda
λ的最优解。因此，则有：
min
W
,
b
L
(
W
,
b
,
λ
)
=
−
1
2
[
∑
i
=
1
N
∑
j
=
1
N
λ
(
i
)
λ
(
j
)
y
(
i
)
y
(
j
)
(
x
(
i
)
)
T
x
(
j
)
]
+
∑
i
=
1
N
λ
(
i
)
\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) = -\frac{1}{2} \left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right] + \sum_{i=1}^N\lambda^{(i)}
W,bminL(W,b,λ)=−21[i=1∑Nj=1∑Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)]+i=1∑Nλ(i)
最终，通过求解对偶问题，将对偶问题转化为 目标函数、约束条件中只含
λ
(
i
)
(
i
=
1
,
2
,
⋯
,
N
)
\lambda^{(i)}(i=1,2,\cdots,N)
λ(i)(i=1,2,⋯,N)的优化问题： 该公式对应于机器学习(周志华著)123页最下方。 于此同时，不要忘记加上因
∂
L
(
W
,
b
,
λ
)
∂
b
≜
0
\frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial b} \triangleq 0
∂b∂L(W,b,λ)≜0产生的新的约束条件。
{
max
λ
−
1
2
[
∑
i
=
1
N
∑
j
=
1
N
λ
(
i
)
λ
(
j
)
y
(
i
)
y
(
j
)
(
x
(
i
)
)
T
x
(
j
)
]
+
∑
i
=
1
N
λ
(
i
)
{
s
.
t
.
λ
(
i
)
≥
0
∑
i
=
1
N
λ
(
i
)
y
(
i
)
=
0
\begin{cases}\mathop{\max}\limits_{\lambda} -\frac{1}{2} \left[\sum_{i=1}^N\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left(x^{(i)}\right)^{T}x^{(j)}\right] + \sum_{i=1}^N\lambda^{(i)} \\ \begin{cases} s.t. \quad \lambda^{(i)} \geq 0 \\ \sum_{i=1}^N \lambda^{(i)}y^{(i)} = 0 \end{cases} \end{cases}
⎩
⎨
⎧λmax−21[∑i=1N∑j=1Nλ(i)λ(j)y(i)y(j)(x(i))Tx(j)]+∑i=1Nλ(i){s.t.λ(i)≥0∑i=1Nλ(i)y(i)=0
下一节将引入 K K T KKT KKT条件，将最优直线的表达式求解出来。
相关参考： 仿射函数-百度百科 凸二次规划(convex quadratic programming)问题 机器学习-支持向量机2-硬间隔SVM-模型求解(对偶问题之引出) 机器学习-支持向量机5-约束优化问题-弱对偶性证明
