1. SVM基本型
分离超平面： ω T x + b = 0 \omega^Tx+b=0 ωTx+b=0
间隔边界： ω T x + b = ± 1 \omega^Tx+b=±1 ωTx+b=±1
支持向量： y i ( ω T x i + b ) = 1 y_i(\omega^Tx_i+b)=1 yi(ωTxi+b)=1
原始问题
m i n ω , b 1 2 ∣ ∣ ω ∣ ∣ 2 \underset{\omega,b}{min} \quad \frac{1}{2}||\omega||^2 ω,bmin21∣∣ω∣∣2 s . t . 1 − y i ( ω T x i + b ) ≤ 0 , i = 1 , 2 , . . . , n s.t. \quad 1-y_i(\omega^Tx_i+b)≤0, \quad i=1,2,...,n s.t.1−yi(ωTxi+b)≤0,i=1,2,...,n
变量： ω = ( ω 1 , ω 2 , . . . , ω d ) T , b \omega=(\omega_1,\omega_2,...,\omega_d)^T,b ω=(ω1,ω2,...,ωd)T,b
约束： n n n个不等式约束
模型推导：
样本点 x x x到超平面 ( ω , b ) (\omega,b) (ω,b)的距离 d = ∣ ω T x + b ∣ ∣ ∣ ω ∣ ∣ d=\frac{|\omega^Tx+b|}{||\omega||} d=∣∣ω∣∣∣ωTx+b∣，我们可以对 ( ω , b ) (\omega,b) (ω,b)进行适当缩放，最终使得在支持向量 x 0 x_0 x0上有 ∣ ω T x 0 + b ∣ = ± 1 |\omega^Tx_0+b|=±1 ∣ωTx0+b∣=±1，此时支持向量到超平面的距离为 1 ∣ ∣ ω ∣ ∣ \frac{1}{||\omega||} ∣∣ω∣∣1。
间隔定义为两个异类支持向量到超平面的距离之和，即 2 ∣ ∣ ω ∣ ∣ \frac{2}{||\omega||} ∣∣ω∣∣2，优化目标转化为最大化 2 ∣ ∣ ω ∣ ∣ \frac{2}{||\omega||} ∣∣ω∣∣2，也就是最小化 ∣ ∣ ω ∣ ∣ ||\omega|| ∣∣ω∣∣或 ∣ ∣ ω ∣ ∣ 2 ||\omega||^2 ∣∣ω∣∣2，此处带有 1 2 \frac{1}{2} 21的原因是便于后续求导。
约束条件的意义在于所有样本点都需要满足该硬性条件，我愿称之为“硬间隔”。
对偶问题
m i n λ 1 2 Σ i = 1 n Σ j = 1 n y i y j x i T x j λ i λ j − Σ i = 1 n λ i \underset{\lambda}{min} \quad \frac{1}{2}\Sigma_{i=1}^n\Sigma_{j=1}^ny_iy_jx_i^Tx_j\lambda_i\lambda_j-\Sigma_{i=1}^n\lambda_i λmin21Σi=1nΣj=1nyiyjxiTxjλiλj−Σi=1nλi s . t . Σ i = 1 n λ i y i = 0 , s.t. \quad \Sigma_{i=1}^n\lambda_iy_i=0, s.t.Σi=1nλiyi=0, λ i ≥ 0 , i = 1 , 2 , . . . , n \lambda_i≥0, \quad i=1,2,...,n λi≥0,i=1,2,...,n
模型推导：
采用拉格朗日乘子法，定义拉格朗日函数： L ( ω , b , α ) = 1 2 ∣ ∣ ω ∣ ∣ 2 + Σ i = 1 n λ i ( 1 − y i ( ω T x i + b ) ) , λ i ≥ 0 L(\omega,b,\alpha)=\frac{1}{2}||\omega||^2+\Sigma_{i=1}^n\lambda_i(1-y_i(\omega^Tx_i+b)), \quad \lambda_i≥0 L(ω,b,α)=21∣∣ω∣∣2+Σi=1nλi(1−yi(ωTxi+b)),λi≥0令 L ( ω , b , α ) L(\omega,b,\alpha) L(ω,b,α)对 ω \omega ω和 b b b的偏导为0可得： ω = Σ i = 1 n λ i y i x i \omega=\Sigma_{i=1}^n\lambda_iy_ix_i ω=Σi=1nλiyixi 0 = Σ i = 1 n λ i y i 0=\Sigma_{i=1}^n\lambda_iy_i 0=Σi=1nλiyi将 ω \omega ω代入拉格朗日函数中即得对偶模型。
KKT条件
原始问题为极大极小问题（推导见下），即：
m
i
n
ω
,
b
m
a
x
λ
≥
0
L
(
ω
,
b
,
α
)
\underset{\omega,b}{min}\underset{\lambda≥0}{max}L(\omega,b,\alpha)
ω,bminλ≥0maxL(ω,b,α)；
而对偶问题为极小极大问题（由定义），即：
m
a
x
λ
≥
0
m
i
n
ω
,
b
L
(
ω
,
b
,
α
)
\underset{\lambda≥0}{max} \underset{\omega,b}{min}L(\omega,b,\alpha)
λ≥0maxω,bminL(ω,b,α)。
原问题为凸优化问题，当 f ( x ) , g ( x ) f(x),g(x) f(x),g(x)为凸函数，且可行域中至少有一点使不等式约束严格成立时，强对偶性成立，对偶问题等价于原问题。即需要满足 K K T KKT KKT条件： { ω = Σ i = 1 n λ i y i x i , 0 = Σ i = 1 n λ i y i λ i ≥ 0 λ i [ 1 − y i ( ω T x i + b ) ] = 0 1 − y i ( ω T x i + b ) ≤ 0 \begin{cases} \omega=\Sigma_{i=1}^n\lambda_iy_ix_i, \quad 0=\Sigma_{i=1}^n\lambda_iy_i\\ \lambda_i≥0\\ \lambda_i[1-y_i(\omega^Tx_i+b)]=0\\ 1-y_i(\omega^Tx_i+b)≤0\\ \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧ω=Σi=1nλiyixi,0=Σi=1nλiyiλi≥0λi[1−yi(ωTxi+b)]=01−yi(ωTxi+b)≤0
KKT条件推导如下：
当约束不起作用时，极小值在可行域内某处取得，而不在边界处取得，故此时 g ( x ∗ ) < 0 g(x^*)<0 g(x∗)<0， g ( x ) g(x) g(x)不起作用，故 λ = 0 \lambda=0 λ=0，由极小值点梯度为零知 ∇ x f ( x ∗ ) = 0 \nabla_xf(x^*)=0 ∇xf(x∗)=0。
当约束起作用时，极小值在可行域边界处取得，故此时 g ( x ∗ ) = 0 g(x^*)=0 g(x∗)=0，易知 λ > 0 \lambda>0 λ>0，故由极小值点梯度为零知 − ∇ x f ( x ∗ ) = λ ∇ x f ( x ∗ ) -\nabla_xf(x^*)=\lambda\nabla_xf(x^*) −∇xf(x∗)=λ∇xf(x∗)。
于是我们得到KKT条件，即 x ∗ x^* x∗是局部最小的等价条件为，存在唯一的 λ ∗ \lambda^* λ∗，使得： { ∇ x L ( x ∗ , λ ∗ ) = 0 λ ∗ ≥ 0 λ ∗ g ( x ∗ ) = 0 g ( x ∗ ) ≤ 0 \begin{cases} \nabla_xL(x^*,\lambda^*)=0\\ \lambda^*≥0\\ \lambda^*g(x^*)=0\\ g(x*)≤0 \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧∇xL(x∗,λ∗)=0λ∗≥0λ∗g(x∗)=0g(x∗)≤0
支持向量的探讨
假设已知支持向量 ( x s , y s ) (x_s,y_s) (xs,ys)，易知 y s ( ω T x s + b ) − 1 = 0 y_s(\omega^Tx_s+b)-1=0 ys(ωTxs+b)−1=0，又已知 ω = Σ i = 1 n λ i y i x i \omega=\Sigma_{i=1}^n\lambda_iy_ix_i ω=Σi=1nλiyixi，故 b = y s − ω T x s = y s − Σ i = 1 n λ i y i x i T x s b=y_s-\omega^Tx_s=y_s-\Sigma_{i=1}^n\lambda_iy_ix_i^Tx_s b=ys−ωTxs=ys−Σi=1nλiyixiTxs。
由上述推导知：当 λ ∗ = 0 \lambda^*=0 λ∗=0时， g ( x ∗ ) < 0 g(x^*)<0 g(x∗)<0；当 λ ∗ > 0 \lambda^*>0 λ∗>0时， g ( x ∗ ) = 0 g(x^*)=0 g(x∗)=0。也就是说， λ ∗ = 0 \lambda^*=0 λ∗=0和 g ( x ∗ ) = 0 g(x^*)=0 g(x∗)=0二者必居其一。
由KKT条件知： λ i [ 1 − y i ( ω T x i + b ) ] = 0 \lambda_i[1-y_i(\omega^Tx_i+b)]=0 λi[1−yi(ωTxi+b)]=0，因此满足 λ i = 0 \lambda_i=0 λi=0的样本点不出现在拉格朗日函数中，不影响模型求解；满足 λ i > 0 \lambda_i>0 λi>0的样本点必定满足 y i ( ω T x i + b ) = 1 y_i(\omega^Tx_i+b)=1 yi(ωTxi+b)=1，即一定是支持向量。
因此，只有支持向量对于模型求解才是有意义的。
求解分类平面
已知
ω
=
Σ
i
=
1
n
λ
i
y
i
x
i
\omega=\Sigma_{i=1}^n\lambda_iy_ix_i
ω=Σi=1nλiyixi，
b
=
y
s
−
ω
T
x
s
=
y
s
−
Σ
i
=
1
n
λ
i
y
i
x
i
T
x
s
b=y_s-\omega^Tx_s=y_s-\Sigma_{i=1}^n\lambda_iy_ix_i^Tx_s
b=ys−ωTxs=ys−Σi=1nλiyixiTxs，欲求
f
(
x
)
=
ω
T
x
+
b
f(x)=\omega^Tx+b
f(x)=ωTx+b。
只需根据对偶模型求解各个拉格朗日乘子
λ
i
\lambda_i
λi，即代入
x
i
,
y
i
x_i,y_i
xi,yi计算目标函数并进行求解即可：
m
i
n
λ
1
2
Σ
i
=
1
n
Σ
j
=
1
n
y
i
y
j
x
i
T
x
j
λ
i
λ
j
−
Σ
i
=
1
n
λ
i
\underset{\lambda}{min} \quad \frac{1}{2}\Sigma_{i=1}^n\Sigma_{j=1}^ny_iy_jx_i^Tx_j\lambda_i\lambda_j-\Sigma_{i=1}^n\lambda_i
λmin21Σi=1nΣj=1nyiyjxiTxjλiλj−Σi=1nλi
s
.
t
.
Σ
i
=
1
n
λ
i
y
i
=
0
,
s.t. \quad \Sigma_{i=1}^n\lambda_iy_i=0,
s.t.Σi=1nλiyi=0,
λ
i
≥
0
,
i
=
1
,
2
,
.
.
.
,
n
\lambda_i≥0, \quad i=1,2,...,n
λi≥0,i=1,2,...,n
2. 软间隔SVM
支持向量：可以在间隔边界上、间隔边界间，甚至可以是错分类点。
软间隔SVM
m i n ω , b , ξ i 1 2 ∣ ∣ ω ∣ ∣ 2 + C Σ i = 1 n ξ i \underset{\omega,b,ξ_i}{min} \quad \frac{1}{2}||\omega||^2+C\Sigma_{i=1}^nξ_i ω,b,ξimin21∣∣ω∣∣2+CΣi=1nξi s . t . y i ( ω T x i + b ) ≥ 1 − ξ i s.t. \quad y_i(\omega^Tx_i+b)≥1-ξ_i s.t.yi(ωTxi+b)≥1−ξi ξ i ≥ 0 , i = 1 , 2 , . . . , n ξ_i≥0, \quad i=1,2,...,n ξi≥0,i=1,2,...,n其中， ξ i ξ_i ξi是松弛变量。
变量： ω , b , ξ i \omega,b,ξ_i ω,b,ξi
约束： 2 n 2n 2n个不等式约束
对偶问题
m i n λ 1 2 Σ i = 1 n Σ j = 1 n y i y j x i T x j λ i λ j − Σ i = 1 n λ i \underset{\lambda}{min} \quad \frac{1}{2}\Sigma_{i=1}^n\Sigma_{j=1}^ny_iy_jx_i^Tx_j\lambda_i\lambda_j-\Sigma_{i=1}^n\lambda_i λmin21Σi=1nΣj=1nyiyjxiTxjλiλj−Σi=1nλi s . t . Σ i = 1 n α i y i = 0 , s.t. \quad \Sigma_{i=1}^n\alpha_iy_i=0, s.t.Σi=1nαiyi=0, 0 ≤ λ i ≤ C , i = 1 , 2 , . . . , n 0≤\lambda_i≤C, \quad i=1,2,...,n 0≤λi≤C,i=1,2,...,n
变量： λ = ( λ 1 , λ 2 , . . . , λ n ) T \lambda=(\lambda_1,\lambda_2,...,\lambda_n)^T λ=(λ1,λ2,...,λn)T
约束：1个等式约束， n n n个不等式约束
因此可以看出，软间隔SVM与SVM基本型的目标函数一致，约束条件仅在拉格朗日乘子的取值范围处有区别。当 C → + ∞ C→+∞ C→+∞时，软间隔SVM退化为SVM基本型。
模型推导：
采用拉格朗日乘子法，定义拉格朗日函数： L ( ω , b , α , ξ , μ ) = 1 2 ∣ ∣ ω ∣ ∣ 2 + C Σ i = 1 n ξ i + Σ i = 1 n λ i ( 1 − ξ i − y i ( ω T x i + b ) ) − Σ i = 1 n μ i ξ i , λ i ≥ 0 L(\omega,b,\alpha,ξ,μ)=\frac{1}{2}||\omega||^2+C\Sigma_{i=1}^nξ_i+\Sigma_{i=1}^n\lambda_i(1-ξ_i-y_i(\omega^Tx_i+b))-\Sigma_{i=1}^nμ_iξ_i, \quad \lambda_i≥0 L(ω,b,α,ξ,μ)=21∣∣ω∣∣2+CΣi=1nξi+Σi=1nλi(1−ξi−yi(ωTxi+b))−Σi=1nμiξi,λi≥0令 L ( ω , b , α ) L(\omega,b,\alpha) L(ω,b,α)对 ω \omega ω和 b b b的偏导为0可得： ω = Σ i = 1 n λ i y i x i \omega=\Sigma_{i=1}^n\lambda_iy_ix_i ω=Σi=1nλiyixi 0 = Σ i = 1 n λ i y i 0=\Sigma_{i=1}^n\lambda_iy_i 0=Σi=1nλiyi C = λ i + μ i C=\lambda_i+μ_i C=λi+μi将 ω \omega ω代入拉格朗日函数中即得对偶模型。
KKT条件
同理，要使原始问题与对偶问题等价，需要满足KKT条件：
{
ω
=
Σ
i
=
1
n
λ
i
y
i
x
i
,
0
=
Σ
i
=
1
n
λ
i
y
i
,
C
=
λ
i
+
μ
i
λ
i
≥
0
,
μ
i
≥
0
λ
i
(
1
−
ξ
i
−
y
i
(
ω
T
x
i
+
b
)
)
=
0
,
μ
i
ξ
i
=
0
1
−
y
i
(
ω
T
x
i
+
b
)
≤
0
,
−
ξ
i
≤
0
\begin{cases} \omega=\Sigma_{i=1}^n\lambda_iy_ix_i, \quad 0=\Sigma_{i=1}^n\lambda_iy_i, \quad C=\lambda_i+μ_i\\ \lambda_i≥0, \quad μ_i≥0\\ \lambda_i(1-ξ_i-y_i(\omega^Tx_i+b))=0, \quad μ_iξ_i=0\\ 1-y_i(\omega^Tx_i+b)≤0, \quad -ξ_i≤0\\ \end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧ω=Σi=1nλiyixi,0=Σi=1nλiyi,C=λi+μiλi≥0,μi≥0λi(1−ξi−yi(ωTxi+b))=0,μiξi=01−yi(ωTxi+b)≤0,−ξi≤0
可以简化表示为（去掉参数
μ
μ
μ）：
{
ω
=
Σ
i
=
1
n
λ
i
y
i
x
i
,
0
=
Σ
i
=
1
n
λ
i
y
i
0
≤
λ
i
≤
C
λ
i
(
1
−
ξ
i
−
y
i
(
ω
T
x
i
+
b
)
)
=
0
,
(
C
−
λ
i
)
ξ
i
=
0
1
−
y
i
(
ω
T
x
i
+
b
)
≤
0
,
−
ξ
i
≤
0
\begin{cases} \omega=\Sigma_{i=1}^n\lambda_iy_ix_i, \quad 0=\Sigma_{i=1}^n\lambda_iy_i\\ 0≤\lambda_i≤C\\ \lambda_i(1-ξ_i-y_i(\omega^Tx_i+b))=0, \quad (C-\lambda_i)ξ_i=0\\ 1-y_i(\omega^Tx_i+b)≤0, \quad -ξ_i≤0\\ \end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧ω=Σi=1nλiyixi,0=Σi=1nλiyi0≤λi≤Cλi(1−ξi−yi(ωTxi+b))=0,(C−λi)ξi=01−yi(ωTxi+b)≤0,−ξi≤0
支持向量的探讨
同理，满足 λ i > 0 \lambda_i>0 λi>0的样本点都是支持向量，支持向量满足 y i ( ω T x i + b ) = 1 − ξ i y_i(\omega^Tx_i+b)=1-ξ_i yi(ωTxi+b)=1−ξi：
- λ i < C \lambda_i<C λi<C时，由 C = λ i + μ i C=\lambda_i+μ_i C=λi+μi知 μ i > 0 μ_i>0 μi>0，再由 μ i ξ i = 0 μ_iξ_i=0 μiξi=0知 ξ i = 0 ξ_i=0 ξi=0，因此 x i x_i xi落在间隔边界上；
- λ i = C \lambda_i=C λi=C时，若 0 < ξ i < 1 0<ξ_i<1 0<ξi<1，则 x i x_i xi落在间隔边界和超平面之间；
- λ i = C \lambda_i=C λi=C时，若 ξ i = 1 ξ_i=1 ξi=1，则 x i x_i xi落在超平面上；
- λ i = C \lambda_i=C λi=C时，若 ξ i > 1 ξ_i>1 ξi>1，则 x i x_i xi落在超平面另一侧。
优化目标
由软间隔SVM的约束条件：
y
i
(
ω
T
x
i
+
b
)
≥
1
−
ξ
i
,
ξ
i
≥
0
,
i
=
1
,
2
,
.
.
.
,
n
y_i(\omega^Tx_i+b)≥1-ξ_i, \quad ξ_i≥0, \quad i=1,2,...,n
yi(ωTxi+b)≥1−ξi,ξi≥0,i=1,2,...,n，容易得到：
ξ
i
≥
m
a
x
(
0
,
1
−
y
i
(
ω
T
x
i
+
b
)
)
ξ_i≥max(0,1-y_i(\omega^Tx_i+b))
ξi≥max(0,1−yi(ωTxi+b))。
因此软间隔SVM的优化目标为：
m
i
n
ω
,
b
1
2
∣
∣
ω
∣
∣
2
+
C
Σ
i
=
1
n
m
a
x
(
0
,
1
−
y
i
(
ω
T
x
i
+
b
)
)
\underset{\omega,b}{min} \quad \frac{1}{2}||\omega||^2+C\Sigma_{i=1}^nmax(0,1-y_i(\omega^Tx_i+b))
ω,bmin21∣∣ω∣∣2+CΣi=1nmax(0,1−yi(ωTxi+b))而hinge损失函数为：
l
o
s
s
h
i
n
g
e
(
z
)
=
m
a
x
(
0
,
1
−
z
)
loss_{hinge}(z)=max(0,1-z)
losshinge(z)=max(0,1−z)，因此软间隔SVM是最小化hinge损失函数的正则化模型。
其中，
1
2
∣
∣
ω
∣
∣
2
\frac{1}{2}||\omega||^2
21∣∣ω∣∣2是正则项（提供模型先验信息，防止过拟合），
Σ
i
=
1
n
m
a
x
(
0
,
1
−
y
i
(
ω
T
x
i
+
b
)
)
\Sigma_{i=1}^nmax(0,1-y_i(\omega^Tx_i+b))
Σi=1nmax(0,1−yi(ωTxi+b))是误差项（衡量预测值与真实值的误差），
C
C
C是正则参数（用于平衡其余两项的大小）。
监督学习任务模型： m i n f Ω ( f ) + C Σ i = 1 n l o s s ( f ( x i ) , y i ) \underset{f}{min} \quad \Omega(f)+C\Sigma_{i=1}^nloss(f(x_i),y_i) fminΩ(f)+CΣi=1nloss(f(xi),yi)其中， Ω ( f ) \Omega(f) Ω(f)称为“结构风险”（正则项）， Σ i = 1 n l o s s ( f ( x i ) , y i ) \Sigma_{i=1}^nloss(f(x_i),y_i) Σi=1nloss(f(xi),yi)称为“经验风险”（误差项）， C C C用于对二者进行折中（正则参数）。
L p L_p Lp范数是常用的正则化项： L 0 L_0 L0范数 ∣ ∣ ω ∣ ∣ 0 ||\omega||_0 ∣∣ω∣∣0代表 ω \omega ω中非零元的个数； L 1 L_1 L1范数 ∣ ∣ ω ∣ ∣ 1 ||\omega||_1 ∣∣ω∣∣1代表各元素绝对值之和 Σ i ∣ ω i ∣ \Sigma_i|\omega_i| Σi∣ωi∣； L 2 L_2 L2范数 ∣ ∣ ω ∣ ∣ 2 ||\omega||_2 ∣∣ω∣∣2代表各元素平方和开根号 Σ i ω i 2 \sqrt{\Sigma_i\omega_i^2} Σiωi2 。
模型求解
- 求出内积矩阵 K K K，其中 K i j = x i T x j K_{ij}=x_i^Tx_j Kij=xiTxj；
- 应用SMO算法求解对偶模型。
3. 核化SVM
基本思想：对于非线性可分的数据，尝试找到一个非线性映射