机器学习笔记之支持向量机(三)模型求解
机器学习笔记之支持向量机——模型求解
引言
上一节介绍了基于最大间隔分类器朴素思想产生的原问题转化为对偶问题的过程,本节将针对对偶问题进行求解。并介绍 强对偶关系需要满足的条件。
回顾:原问题转化为对偶问题的具体过程
在机器学习笔记之支持向量机(一)模型构建思路中介绍过,经过 函数间隔约束 的最大间隔分类器朴素思想表示如下:
{
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)} \left(\mathcal W^{T}x^{(i)} + b\right) \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
该问题是一个包含
N
N
N个约束的凸优化问题,使用拉格朗日乘数法将 原问题转化为无约束原问题:
令拉格朗日函数为
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)]
基于原问题的约束条件是不等式约束,则有:
λ
(
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)
假设直接对无约束原问题 进行求解,那么按照求解顺序需要先求解
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda)
λmaxL(W,b,λ)的结果,但是该式子中的变量
λ
\lambda
λ存在约束条件,因此,我们尝试先从无约束的
W
,
b
\mathcal W,b
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)
在无约束条件的情况下,无约束原问题的目标函数与对偶问题的目标函数必然存在如下关系:
max
λ
min
W
,
b
L
(
W
,
b
,
λ
)
≤
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda}\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) \leq \mathop{\min}\limits_{\mathcal W,b}\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda)
λmaxW,bminL(W,b,λ)≤W,bminλmaxL(W,b,λ)
并称之为弱对偶关系。与之对应的是强对偶关系:
max
λ
min
W
,
b
L
(
W
,
b
,
λ
)
=
min
W
,
b
max
λ
L
(
W
,
b
,
λ
)
\mathop{\max}\limits_{\lambda}\mathop{\min}\limits_{\mathcal W,b} \mathcal L(\mathcal W,b,\lambda) = \mathop{\min}\limits_{\mathcal W,b}\mathop{\max}\limits_{\lambda} \mathcal L(\mathcal W,b,\lambda)
λmaxW,bminL(W,b,λ)=W,bminλmaxL(W,b,λ)
可以看出,强对偶关系是弱对偶关系的一种 特殊情况,弱对偶关系上升至强对偶关系需要满足什么条件?本节将详细介绍这个条件——
K
K
T
KKT
KKT条件。
由于无约束原问题满足
K
K
T
KKT
KKT条件,因此,顺利成章地将无约束问题转化为对偶问题。此时的
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求解偏导,得到 仅关于变量
λ
\lambda
λ的拉格朗日函数:
这里将
max
\max
max和
−
1
2
-\frac{1}{2}
−21合并为
min
\min
min和
1
2
\frac{1}{2}
21;
{
min
λ
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{\min}\limits_{\lambda} \frac{1}{2} \sum_{i=1}^{N}\sum_{j=1}^N \lambda^{(i)}\lambda^{(j)}y^{(i)}y^{(j)}\left({x^{(i)}}\right)^{T}x^{(j)} - \sum_{i=1}^N \lambda^{(i)} \\ s.t.\quad \begin{cases} \quad \lambda^{(i)} \geq 0 \\ \quad\quad \sum_{i=1}^N \lambda^{(i)}y^{(i)} = 0 \end{cases} \end{cases}
⎩⎪⎪⎨⎪⎪⎧λmin21∑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
模型求解
继续观察,本质上是仅关于 λ \lambda λ的包含两个约束条件的最小化问题。
其中,变量
λ
(
i
)
,
λ
(
j
)
∈
{
λ
(
1
)
,
λ
(
2
)
,
⋯
,
λ
(
N
)
}
\lambda^{(i)},\lambda^{(j)} \in \{\lambda^{(1)},\lambda^{(2)},\cdots,\lambda^{(N)}\}
λ(i),λ(j)∈{λ(1),λ(2),⋯,λ(N)},
y
(
i
)
,
y
(
j
)
∈
{
−
1
,
1
}
y^{(i)},y^{(j)} \in \{-1,1\}
y(i),y(j)∈{−1,1},均为标量、常数;
(
x
(
i
)
)
T
x
(
j
)
\left({x^{(i)}}\right)^{T}x^{(j)}
(x(i))Tx(j)可以写为:
(
x
(
i
)
)
T
x
(
j
)
=
(
x
1
(
i
)
,
x
2
(
i
)
,
⋯
,
x
p
(
i
)
)
(
x
1
(
j
)
x
2
(
j
)
⋮
x
p
(
j
)
)
=
x
1
(
i
)
x
1
(
j
)
+
x
2
(
i
)
x
2
(
j
)
+
⋯
+
x
p
(
i
)
x
p
(
j
)
\left({x^{(i)}}\right)^{T}x^{(j)} = (x_1^{(i)},x_2^{(i)},\cdots,x_p^{(i)})\begin{pmatrix}x_1^{(j)} \\ x_2^{(j)} \\ \vdots \\ x_p^{(j)}\end{pmatrix} = x_1^{(i)}x_1^{(j)} + x_2^{(i)}x_2^{(j)} + \cdots + x_p^{(i)}x_p^{(j)}
(x(i))Tx(j)=(x1(i),x2(i),⋯,xp(i))⎝⎜⎜⎜⎜⎛x1(j)x2(j)⋮xp(j)⎠⎟⎟⎟⎟⎞=x1(i)x1(j)+x2(i)x2(j)+⋯+xp(i)xp(j)
其结果也是一个标量、常数;因此 目标函数只包含
λ
\lambda
λ的一次项和二次项;
约束条件中变量是一次的,即仿射函数;且为不等式约束,实际上此时的优化问题依然是一个凸二次规划问题。和原问题相似,同样可以使用类似
Q
P
QP
QP方法 进行求解。
本节将使用 K K T KKT KKT条件求解最优模型以及最优超平面。
K K T KKT KKT条件介绍
K
K
T
KKT
KKT条件的作用:它是原问题、对偶问题之间具有强对偶关系的充分必要条件。
下面将进行论证:
场景描述
已知一个关于变量
X
\mathcal X
X的原问题表示如下:
{
min
X
f
(
X
)
s
.
t
.
{
m
i
(
X
)
≤
0
(
i
=
1
,
2
,
⋯
,
M
)
n
j
(
X
)
=
0
(
j
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\min}\limits_{\mathcal X} f(\mathcal X) \\ s.t. \begin{cases} m_i(\mathcal X) \leq 0 \quad (i=1,2,\cdots,M) \\ n_j(\mathcal X) = 0 \quad (j=1,2,\cdots,N) \end{cases} \end{cases}
⎩⎪⎪⎨⎪⎪⎧Xminf(X)s.t.{mi(X)≤0(i=1,2,⋯,M)nj(X)=0(j=1,2,⋯,N)
观察发现,该原问题包含
M
+
N
M+N
M+N个约束条件:其中包含
M
M
M个不等式约束和
N
N
N个等式约束。
使用拉格朗日乘数法将原问题转化为无约束原问题。拉格朗日函数
L
(
X
,
λ
,
η
)
\mathcal L(\mathcal X ,\lambda,\eta)
L(X,λ,η)表示如下:
L
(
X
,
λ
,
η
)
=
f
(
X
)
+
∑
i
=
1
M
λ
i
m
i
(
X
)
+
∑
j
=
1
N
η
j
n
j
(
X
)
\mathcal L(\mathcal X ,\lambda,\eta) = f(\mathcal X) + \sum_{i=1}^M \lambda_im_i(\mathcal X) + \sum_{j=1}^N \eta_jn_j(\mathcal X)
L(X,λ,η)=f(X)+i=1∑Mλimi(X)+j=1∑Nηjnj(X)
对应的无约束原问题表示如下:
{
min
X
max
λ
,
η
L
(
X
,
λ
,
η
)
s
.
t
.
{
λ
i
≥
0
(
i
=
1
,
2
,
⋯
,
M
)
η
j
=
0
(
j
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\min}\limits_{\mathcal X} \mathop{\max}\limits_{\lambda,\eta} \mathcal L(\mathcal X,\lambda,\eta) \\ s.t. \begin{cases}\lambda_i \geq 0 \quad (i=1,2,\cdots,M) \\ \eta_j = 0 \quad (j=1,2,\cdots,N)\end{cases} \end{cases}
⎩⎪⎪⎨⎪⎪⎧Xminλ,ηmaxL(X,λ,η)s.t.{λi≥0(i=1,2,⋯,M)ηj=0(j=1,2,⋯,N)
继续将它的对偶问题表示如下:
{
max
λ
,
η
min
X
L
(
X
,
λ
,
η
)
s
.
t
.
{
λ
i
≥
0
(
i
=
1
,
2
,
⋯
,
M
)
η
j
=
0
(
j
=
1
,
2
,
⋯
,
N
)
\begin{cases}\mathop{\max}\limits_{\lambda,\eta} \mathop{\min}\limits_{\mathcal X} \mathcal L(\mathcal X,\lambda,\eta) \\ s.t. \begin{cases} \lambda_i \geq 0 \quad (i=1,2,\cdots,M) \\ \eta_j = 0 \quad (j=1,2,\cdots,N)\end{cases}\end{cases}
⎩⎪⎪⎨⎪⎪⎧λ,ηmaxXminL(X,λ,η)s.t.{λi≥0(i=1,2,⋯,M)ηj=0(j=1,2,⋯,N)
论证过程
我们可以将无约束原问题和原问题一样,看做关于
X
\mathcal X
X的函数。即
λ
,
η
\lambda,\eta
λ,η已确定,使得
L
(
X
,
λ
,
η
)
\mathcal L(\mathcal X,\lambda,\eta)
L(X,λ,η)结果最大的基础上,找到合适的
X
∗
\mathcal X^{*}
X∗,使
max
λ
,
η
L
(
X
,
λ
,
η
)
\mathop{\max}\limits_{\lambda,\eta}\mathcal L(\mathcal X,\lambda,\eta)
λ,ηmaxL(X,λ,η)最小:
f
(
X
)
=
max
λ
,
η
L
(
X
,
λ
,
η
)
f
(
X
∗
)
=
min
X
f
(
X
)
f(\mathcal X) = \mathop{\max}\limits_{\lambda,\eta}\mathcal L(\mathcal X,\lambda,\eta) \\ f(\mathcal X^{*}) = \mathop{\min}\limits_{\mathcal X} f(\mathcal X)
f(X)=λ,ηmaxL(X,λ,η)f(X∗)=Xminf(X)
其中,
X
∗
\mathcal X^{*}
X∗表示 原问题的最优解。同理,我们同样可以将对偶问题看作关于
λ
,
η
\lambda,\eta
λ,η的函数,即:
X
\mathcal X
X已确定,使得
L
(
X
,
λ
,
η
)
\mathcal L(\mathcal X,\lambda,\eta)
L(X,λ,η)结果最小的基础上,找到合适的
λ
∗
,
η
∗
\lambda^{*},\eta^{*}
λ∗,η∗,使
min
X
L
(
X
,
λ
,
η
)
\mathop{\min}\limits_{\mathcal X}\mathcal L(\mathcal X,\lambda,\eta)
XminL(X,λ,η)最大:
g
(
λ
,
η
)
=
min
X
L
(
X
,
λ
,
η
)
g
(
λ
∗
,
η
∗
)
=
max
λ
,
η
g
(
λ
,
η
)
g(\lambda,\eta) = \mathop{\min}\limits_{\mathcal X} \mathcal L(\mathcal X,\lambda,\eta) \\ g(\lambda^{*},\eta^{*}) = \mathop{\max}\limits_{\lambda,\eta}g(\lambda,\eta)
g(λ,η)=XminL(X,λ,η)g(λ∗,η∗)=λ,ηmaxg(λ,η)
假设对偶问题与原问题之间确定是强对偶关系,即求解 λ ∗ , η ∗ \lambda^{*},\eta^{*} λ∗,η∗与求解 X ∗ \mathcal X^{*} X∗等价。 K K T KKT KKT条件给出了 λ ∗ , η ∗ \lambda^{*},\eta^{*} λ∗,η∗与 X ∗ \mathcal X^{*} X∗的关系。
K K T KKT KKT条件(Karush-Kuhn-Tucker Conditions)可以包含三个部分:
-
可行域(约束条件)。在本场景中,分别表示原问题与对偶问题取最优解时的约束条件:
{ m i ( X ∗ ) ≤ 0 ( i = 1 , 2 , ⋯ , M ) n j ( X ∗ ) = 0 ( j = 1 , 2 , ⋯ , N ) λ ∗ ≤ 0 \begin{cases}m_i(\mathcal X^{*}) \leq 0 \quad (i=1,2,\cdots,M) \\ n_j(\mathcal X^{*}) = 0 \quad (j=1,2,\cdots,N) \\ \lambda ^{*} \leq 0 \end{cases} ⎩⎪⎨⎪⎧mi(X∗)≤0(i=1,2,⋯,M)nj(X∗)=0(j=1,2,⋯,N)λ∗≤0 -
互补松弛原则(Complementary Slackness)
通过基于强对偶关系成立的条件下,推导互补松弛原则的具体格式:-
由于强对偶关系成立情况下原问题最优解与对偶问题最优解 等价。即:
max λ , η g ( λ , η ) = max λ , η min X L ( X , λ , η ) = min X max λ , η L ( X , λ , η ) = min X f ( X ) \mathop{\max}\limits_{\lambda,\eta} g(\lambda,\eta) = \mathop{\max}\limits_{\lambda,\eta} \mathop{\min}\limits_{\mathcal X} \mathcal L(\mathcal X,\lambda,\eta) = \mathop{\min}\limits_{\mathcal X} \mathop{\max}\limits_{\lambda,\eta} \mathcal L(\mathcal X,\lambda,\eta) = \mathop{\min}\limits_{\mathcal X} f(\mathcal X) λ,ηmaxg(λ,η)=λ,ηmaxXminL(X,λ,η)=Xminλ,ηmaxL(X,λ,η)=Xminf(X) -
假设存在一组解 λ ∗ , η ∗ \lambda^{*},\eta^{*} λ∗,η∗,使得:
L ( X , λ ∗ , η ∗ ) = max λ , η L ( X , λ , η ) \mathcal L(\mathcal X,\lambda^{*},\eta^{*}) = \mathop{\max}\limits_{\lambda,\eta} \mathcal L(\mathcal X,\lambda,\eta) L(X,λ∗,η∗)=λ,ηmaxL(X,λ,η)
与此同时:
min X max λ , η L ( X , λ , η ) = min X L ( X , λ ∗ , η ∗ ) \mathop{\min}\limits_{\mathcal X} \mathop{\max}\limits_{\lambda,\eta} \mathcal L(\mathcal X,\lambda,\eta) = \mathop{\min}\limits_{\mathcal X} \mathcal L(\mathcal X,\lambda^{*},\eta^{*}) Xminλ,ηmaxL(X,λ,η)=XminL(X,λ∗,η∗) -
基于 min X L ( X , λ ∗ , η ∗ ) \mathop{\min}\limits_{\mathcal X} \mathcal L(\mathcal X,\lambda^{*},\eta^{*}) XminL(X,λ∗,η∗)的最小值性质,则有:
min X L ( X , λ ∗ , η ∗ ) ≤ L ( X , λ ∗ , η ∗ ) \mathop{\min}\limits_{\mathcal X}\mathcal L(\mathcal X,\lambda^{*},\eta^{*}) \leq \mathcal L(\mathcal X,\lambda^{*},\eta^{*}) XminL(X,λ∗,η∗)≤L(X,λ∗,η∗)
于此同时,必然存在:
X ∗ \mathcal X^{* } X∗暂时理解为
X \mathcal X X可以取到的任意一个值。
min X L ( X , λ ∗ , η ∗ ) ≤ L ( X ∗ , λ ∗ , η ∗ ) \mathop{\min}\limits_{\mathcal X}\mathcal L(\mathcal X,\lambda^{*},\eta^{*}) \leq \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) XminL(X,λ∗,η∗)≤L(X∗,λ∗,η∗) -
将 L ( X ∗ , λ ∗ , η ∗ ) \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) L(X∗,λ∗,η∗)展开,有:
L ( X ∗ , λ ∗ , η ∗ ) = f ( X ∗ ) + ∑ i = 1 M λ i ∗ m i ( X ) + ∑ j = 1 N η j ∗ n j ( X ) \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) = f(\mathcal X^{*}) + \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) + \sum_{j=1}^N\eta_j^{*}n_j(\mathcal X) L(X∗,λ∗,η∗)=f(X∗)+i=1∑Mλi∗mi(X)+j=1∑Nηj∗nj(X) -
基于可行域条件: n j ( X ∗ ) = 0 ( j = 1 , 2 , ⋯ , N ) n_j(\mathcal X^{*}) = 0 \quad (j=1,2,\cdots,N) nj(X∗)=0(j=1,2,⋯,N),则有:
L ( X ∗ , λ ∗ , η ∗ ) = f ( X ∗ ) + ∑ i = 1 M λ i ∗ m i ( X ) \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) = f(\mathcal X^{*}) + \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) L(X∗,λ∗,η∗)=f(X∗)+i=1∑Mλi∗mi(X) -
又因为可行域条件: { m i ( X ∗ ) ≤ 0 ( i = 1 , 2 , ⋯ , M ) λ ∗ ≤ 0 \begin{cases}m_i(\mathcal X^{*}) \leq 0 \quad (i=1,2,\cdots,M) \\ \lambda ^{*} \leq 0\end{cases} {mi(X∗)≤0(i=1,2,⋯,M)λ∗≤0,因此则有:
两项异号,其结果有上界0。
∑ i = 1 M λ i ∗ m i ( X ) ≤ 0 \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) \leq 0 i=1∑Mλi∗mi(X)≤0
从而有:
L ( X ∗ , λ ∗ , η ∗ ) = f ( X ∗ ) + ∑ i = 1 M λ i ∗ m i ( X ) ≤ f ( X ∗ ) \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) = f(\mathcal X^{*}) + \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) \leq f(\mathcal X^{*}) L(X∗,λ∗,η∗)=f(X∗)+i=1∑Mλi∗mi(X)≤f(X∗)
观察上述推导过程,发现:满足什么条件才能将最后的 ≤ \leq ≤换成 = = =,成为真正的强对偶关系?
其核心原因在于:
∑ i = 1 M λ i ∗ m i ( X ) ≤ 0 \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) \leq 0 i=1∑Mλi∗mi(X)≤0
如果将该式改为: ∑ i = 1 M λ i ∗ m i ( X ) = 0 \sum_{i=1}^{M} \lambda_i^{*}m_i(\mathcal X) = 0 ∑i=1Mλi∗mi(X)=0,此时就成为真正的强对偶关系。我们称该条件为互补松弛原则。 -
-
梯度为0:
观察上述推导过程,发现还有一个 ≤ \leq ≤没有解决:
min X L ( X , λ ∗ , η ∗ ) ≤ L ( X ∗ , λ ∗ , η ∗ ) \mathop{\min}\limits_{\mathcal X}\mathcal L(\mathcal X,\lambda^{*},\eta^{*}) \leq \mathcal L(\mathcal X^{*},\lambda^{*},\eta^{*}) XminL(X,λ∗,η∗)≤L(X∗,λ∗,η∗)
该小于号转换为等号需要满足什么条件?
X ∗ \mathcal X^{*} X∗是 L ( X , λ ∗ , η ∗ ) \mathcal L(\mathcal X,\lambda^{*},\eta^{*}) L(X,λ∗,η∗)的最优解。即:
∂ L ( X , λ ∗ , η ∗ ) ∂ X = 0 ∣ X = X ∗ \frac{\partial \mathcal L(\mathcal X,\lambda^{*},\eta^{*})}{\partial \mathcal X} = 0 |_{\mathcal X = \mathcal X^{*}} ∂X∂L(X,λ∗,η∗)=0∣X=X∗
整理,互补松弛原则共包含3个部分,5个条件:
- 可行域(约束条件);
m i ( X ∗ ) ≤ 0 ; n j ( X ∗ ) ≤ 0 ; λ ∗ ≥ 0 m_i(\mathcal X^*)\leq 0;n_j(\mathcal X^*) \leq 0;\lambda^* \geq 0 mi(X∗)≤0;nj(X∗)≤0;λ∗≥0 - 互补松弛原则;
λ i m i = 0 \lambda_im_i = 0 λimi=0 - 梯度为0;
∂ L ( X , λ ∗ , η ∗ ) ∂ X = 0 ∣ X = X ∗ \frac{\partial \mathcal L(\mathcal X,\lambda^{*},\eta^{*})}{\partial \mathcal X} = 0 |_{\mathcal X = \mathcal X^{*}} ∂X∂L(X,λ∗,η∗)=0∣X=X∗
利用 K K T KKT KKT条件求解最优参数;
结合最大间隔分类器产生的原问题与对偶问题,我们列出满足强对偶关系需要的 K K T KKT KKT条件:
- 可行域(约束条件):
1 − y ( i ) ( W T x ( i ) + b ) ≤ 0 ( i = 1 , 2 , ⋯ , N ) λ ( i ) ≥ 0 ( i = 1 , 2 , ⋯ , N ) ∑ i = 1 N λ ( i ) y ( i ) = 0 1 - y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) \leq 0 \quad (i=1,2,\cdots,N)\\ \lambda^{(i)} \geq 0 \quad (i=1,2,\cdots,N)\\ \sum_{i=1}^N \lambda^{(i)}y^{(i)} = 0 1−y(i)(WTx(i)+b)≤0(i=1,2,⋯,N)λ(i)≥0(i=1,2,⋯,N)i=1∑Nλ(i)y(i)=0 - 拉格朗日函数
L
(
W
,
b
,
λ
)
\mathcal L(\mathcal W,b,\lambda)
L(W,b,λ)对原问题、对偶问题对应变量梯度为0:
∂ L ( W , b , λ ) ∂ W ≜ 0 ∂ L ( W , b , λ ) ∂ b ≜ 0 ∂ L ( W , b , λ ) ∂ λ ≜ 0 \frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial \mathcal W} \triangleq 0 \\ \frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial b} \triangleq 0 \\ \frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial \lambda} \triangleq 0 ∂W∂L(W,b,λ)≜0∂b∂L(W,b,λ)≜0∂λ∂L(W,b,λ)≜0 - 互补松弛原则:
λ ( i ) [ 1 − y ( i ) ( W T x ( i ) + b ) ] = 0 \lambda^{(i)}\left[1 - y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right)\right] = 0 λ(i)[1−y(i)(WTx(i)+b)]=0
这里观察互补松弛原则在求解最优模型中起到的作用:
首先观察
[
1
−
y
(
i
)
(
W
T
x
(
i
)
+
b
)
]
\left[1 - y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right)\right]
[1−y(i)(WTx(i)+b)]具有什么实际意义?
在函数间隔约束部分,第一次产生这种格式。当时的设定是:
min
x
(
i
)
∈
X
y
(
i
)
(
W
T
x
(
i
)
+
b
)
=
1
\mathop{\min}\limits_{x^{(i)} \in \mathcal X} y^{(i)}\left(\mathcal W^{T}x^{(i)} + b\right) = 1
x(i)∈Xminy(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的样本点是
(
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
那么 互补松弛原则中对应的
λ
(
i
)
\lambda^{(i)}
λ(i)可以不为0。基于该思路,可以继续引出两条推测:
- λ ( i ) \lambda^{(i)} λ(i)一旦不为0,那么 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必然成立,它对应的样本点 ( x ( i ) , y ( i ) ) \left(x^{(i)},y^{(i)}\right) (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,它对应的 λ ( i ) = 0 \lambda^{(i)} = 0 λ(i)=0必然成立。
假设存在某样本点
(
x
(
k
)
,
y
(
k
)
)
(x^{(k)},y^{(k)})
(x(k),y(k))使得:
1
−
y
(
k
)
(
W
T
x
(
k
)
+
b
)
=
0
1 - y^{(k)}\left(\mathcal W^{T}x^{(k)} + b\right) = 0
1−y(k)(WTx(k)+b)=0
由于最优解
W
∗
\mathcal W^{*}
W∗通过
∂
L
(
W
,
b
,
λ
)
∂
W
≜
0
\frac{\partial \mathcal L(\mathcal W,b,\lambda)}{\partial \mathcal W} \triangleq 0
∂W∂L(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∗带入
1
−
y
(
k
)
(
W
T
x
(
k
)
+
b
)
=
0
1 - y^{(k)}\left(\mathcal W^{T}x^{(k)} + b\right) = 0
1−y(k)(WTx(k)+b)=0中,求出最优解
b
∗
b^{*}
b∗:
y
(
k
)
(
W
T
x
(
k
)
+
b
)
=
1
y^{(k)}\left(\mathcal W^{T}x^{(k)} + b\right) = 1
y(k)(WTx(k)+b)=1
由于
y
(
k
)
∈
{
−
1
,
1
}
y^{(k)} \in \{-1,1\}
y(k)∈{−1,1},左右两边同乘
y
(
k
)
y^{(k)}
y(k),等式左边
(
y
(
k
)
)
2
=
1
\left(y^{(k)}\right)^2 = 1
(y(k))2=1恒成立,省略;等式右侧剩余一个
y
(
k
)
y^{(k)}
y(k):
W
T
x
(
k
)
+
b
=
y
(
k
)
\mathcal W^{T}x^{(k)} + b = y^{(k)}
WTx(k)+b=y(k)
最终
b
∗
b^{*}
b∗结果表示如下:
b
∗
=
y
(
k
)
−
(
W
∗
)
T
x
(
k
)
=
y
(
k
)
−
∑
i
=
1
N
[
λ
(
i
)
y
(
i
)
(
x
(
i
)
)
T
]
x
(
k
)
\begin{aligned} b^* & = y^{(k)} - \left(\mathcal W^* \right)^{T} x^{(k)} \\ & = y^{(k)} - \sum_{i=1}^N \left[\lambda^{(i)}y^{(i)}\left(x^{(i)}\right)^{T}\right]x^{(k)} \end{aligned}
b∗=y(k)−(W∗)Tx(k)=y(k)−i=1∑N[λ(i)y(i)(x(i))T]x(k)
至此,我们得到了构成分类直线(超平面)的两个参数:
W
∗
,
b
∗
\mathcal W^{*},b^*
W∗,b∗;最终 分类直线(超平面) 的表达式为:
(
W
∗
)
T
X
+
b
∗
=
0
(\mathcal W^*)^{T}\mathcal X + b^* = 0
(W∗)TX+b∗=0
对应模型表示为:
f
(
W
,
b
)
=
s
i
g
n
[
(
W
∗
)
T
X
+
b
∗
]
f(\mathcal W,b) = sign\left[(\mathcal W^*)^{T}\mathcal X + b^*\right]
f(W,b)=sign[(W∗)TX+b∗]
至此,硬间隔 S V M SVM SVM最优参数求解过程结束。下一节将介绍软间隔 S V M SVM SVM。
相关参考:
机器学习-支持向量机3-硬间隔SVM模型求解(对偶问题之KKT条件)
机器学习-支持向量机8-约束优化问题-对偶关系之KKT条件
相关文章
- Coursera台大机器学习技法课程笔记07-Blending and Bagging
- Coursera台大机器学习技法课程笔记12-Neural Network
- Coursera台大机器学习技法课程笔记08-Adaptive Boosting
- 机器学习笔记----最小二乘法,局部加权,岭回归讲解
- 机器学习笔记 - 模式识别的应用场景之一简单车牌识别
- 机器学习笔记 - 基于Torch Hub和YOLOv5和SSD的目标检测
- 机器学习笔记 - 关于Contrastive Loss对比损失
- 机器学习笔记 - 机器学习系统设计流程概述
- 机器学习笔记 - 构建推荐系统(1)的步骤
- 机器学习笔记 - U-Net论文解读
- 机器学习笔记 - 如何对两个分类变量使用卡方检验?
- 机器学习笔记 - 人工智能如何用于电影制作
- 机器学习笔记 - 什么是图注意力网络?
- 机器学习笔记 - 确定性与随机机器学习
- 机器学习笔记 - 支持向量机(SVM)背后的数学二
- 机器学习笔记 - 支持向量机(SVM)背后的数学一
- 机器学习笔记 - 支持向量机(SVM)
- 机器学习笔记 - Kaggle表格游乐场 Feb 2022 学习二
- 机器学习笔记 - Kaggle表格游乐场 Feb 2022 学习一
- 机器学习笔记 - 探索性数据分析(EDA) 概念理解
- 机器学习笔记(八)---- 神经网络【华为云分享】
- 西瓜书学习笔记第1章(绪论)机器学习