SVM主要用来处理二分类问题，其也可用以用来解决多分类问题与回归问题，只不过不常用。其目标是找到一个最优的分隔平面，来使得不同类别之间的距离最大化。核心思想是将问题转化成凸二次规划求解的问题。
一、拉格朗日对偶变换
想要搞清楚SVM问题是如何进行转化的，首先就要搞清楚什么是拉格朗日对偶变换，我们这里简要的叙述一下。其核心思想是将求解最优问题转化成为相对容易求解的问题。
原始问题
假设我们研究的优化问题如下：
M
i
n
i
m
i
z
e
f
0
(
x
)
Minimizef_0(x)
Minimizef0(x)
s
.
t
.
f
i
(
x
)
≤
0
i
=
{
1
,
.
.
.
,
K
}
s.t.\quad f_i(x)\le 0\quad \quad i= \{1,...,K\}
s.t.fi(x)≤0i={1,...,K}
g
j
(
x
)
=
0
j
=
{
1
,
.
.
.
,
L
}
g_j(x)= 0\quad \quad j= \{1,...,L\}
gj(x)=0j={1,...,L}
同时我们假设满足约束条件的最优解为
x
∗
x^*
x∗，
p
∗
=
f
0
(
x
∗
)
p^*=f_0(x^*)
p∗=f0(x∗)
极小极大问题
那么根据拉格朗日函数我们可以构造出：
L
(
x
,
α
,
β
)
=
f
0
(
x
)
+
∑
i
=
1
K
α
i
f
i
(
x
)
+
∑
j
=
1
L
β
j
g
j
(
x
)
α
≥
0
L(x,\alpha ,\beta)=f_0(x)+\sum_{i=1}^K\alpha_if_i(x)+\sum_{j=1}^L\beta_jg_j(x)\quad\quad\quad \alpha \ge0
L(x,α,β)=f0(x)+i=1∑Kαifi(x)+j=1∑Lβjgj(x)α≥0
拉格朗日函数是一个关于
x
,
α
x,\alpha
x,α和
β
\beta
β的函数，其中
x
x
x是原问题的自变量，
α
,
β
\alpha,\beta
α,β被称为拉格朗日乘子，是标量。
其中
f
0
(
x
)
f_0(x)
f0(x)是原优化问题的目标函数，
f
i
(
x
)
f_i(x)
fi(x)为原优化问题的不等式约束项，
g
i
(
x
)
g_i(x)
gi(x)为原问题的等式约束项。
我们构造函数
θ
p
(
x
)
\theta_p(x)
θp(x)如下：
θ
p
(
x
)
=
max
α
,
β
L
(
x
,
α
,
β
)
\theta_p(x)=\max\limits_{\alpha,\beta}L(x,\alpha,\beta)
θp(x)=α,βmaxL(x,α,β)
假设存在违反约束条件的样本
x
x
x，即存在某个
i
i
i使得
f
i
(
x
)
>
0
f_i(x)>0
fi(x)>0或者
g
i
(
x
)
≠
0
g_i(x)\neq0
gi(x)=0，如果
f
i
(
x
)
>
0
f_i(x)>0
fi(x)>0，那么我们可以使得
α
i
\alpha_i
αi的取值为
+
∞
+\infty
+∞,那么
θ
p
(
x
)
\theta_p(x)
θp(x)的取值也为
+
∞
+\infty
+∞；如果
g
i
(
x
)
≠
0
g_i(x)\neq0
gi(x)=0，同理我们使得
β
i
\beta_i
βi为
+
∞
+\infty
+∞，
θ
p
(
x
)
\theta_p(x)
θp(x)的取值同样为
+
∞
+\infty
+∞。即：
θ
p
(
x
)
=
max
α
,
β
[
f
0
(
x
)
+
∑
i
=
1
K
α
i
f
i
(
x
)
+
∑
j
=
1
L
β
j
g
j
(
x
)
]
=
+
∞
\theta_p(x)=\max\limits_{\alpha,\beta}[f_0(x)+\sum_{i=1}^K\alpha_if_i(x)+\sum_{j=1}^L\beta_jg_j(x)]=+\infty
θp(x)=α,βmax[f0(x)+i=1∑Kαifi(x)+j=1∑Lβjgj(x)]=+∞
但如果样本
x
x
x满足约束条件，即
f
i
(
x
)
≤
0
f_i(x)\le0
fi(x)≤0并且
g
i
(
x
)
=
0
g_i(x)=0
gi(x)=0，那么当
α
i
\alpha_i
αi的取值为0时，使得
θ
p
(
x
)
=
f
0
(
x
)
\theta_p(x)=f_0(x)
θp(x)=f0(x)，即：
θ
p
(
x
)
=
max
α
,
β
[
f
0
(
x
)
+
∑
i
=
1
K
α
i
f
i
(
x
)
+
∑
j
=
1
L
β
j
g
j
(
x
)
]
=
f
0
(
x
)
\theta_p(x)=\max\limits_{\alpha,\beta}[f_0(x)+\sum_{i=1}^K\alpha_if_i(x)+\sum_{j=1}^L\beta_jg_j(x)]=f_0(x)
θp(x)=α,βmax[f0(x)+i=1∑Kαifi(x)+j=1∑Lβjgj(x)]=f0(x)
因此我们可以得到：
θ
p
(
x
)
=
{
+
∞
x
不
满
足
原
始
约
束
条
件
f
0
(
x
)
否
则
\theta_p(x)=\left\{ \begin{array}{rcl} +\infty & & {x不满足原始约束条件}\\ f_0(x) & & {否则} \end{array} \right.
θp(x)={+∞f0(x)x不满足原始约束条件否则
因此：
p
∗
=
min
x
f
0
(
x
)
=
min
x
θ
p
(
x
)
=
min
x
max
α
,
β
L
(
x
,
α
,
β
)
p^*=\min\limits_{x}f_0(x)=\min\limits_x\theta_p(x)=\min\limits_x\max\limits_{\alpha,\beta}L(x,\alpha,\beta)
p∗=xminf0(x)=xminθp(x)=xminα,βmaxL(x,α,β)
被称为广义拉格朗日函数的极小极大问题。
极大极小问题
我们构造函数
θ
(
α
,
β
)
=
min
x
L
(
x
,
α
,
β
)
\theta(\alpha,\beta)=\min\limits_xL(x,\alpha,\beta)
θ(α,β)=xminL(x,α,β)，同时令：
d
∗
=
max
α
,
β
min
x
L
(
x
,
α
,
β
)
d^*=\max\limits_{\alpha,\beta}\min\limits_xL(x,\alpha,\beta)
d∗=α,βmaxxminL(x,α,β)
称为原始问题的对偶问题，其中
d
∗
≤
p
∗
d^*\le p^*
d∗≤p∗
被称为弱对偶，是一定成立的，感兴趣的可以自己找一下统计学原理看看推导过程，这里就不进行推导了。
当满足一定情况时，
d
∗
=
p
∗
d^*=p^*
d∗=p∗，我们称其为强对偶。
对于原始问题及其对偶问题，假设函数
f
0
(
x
)
f_0(x)
f0(x)和
f
i
(
x
)
f_i(x)
fi(x) 是凸函数，
g
i
(
x
)
g_i(x)
gi(x)是仿射函数，且不等式约束
f
i
(
x
)
f_i(x)
fi(x)是严格可行的，即存在
x
x
x ，对所有
f
i
(
x
)
f_i(x)
fi(x)有
f
i
(
x
)
≤
0
f_i(x)\le0
fi(x)≤0 ，则存在
x
∗
,
α
∗
,
β
∗
x^*,\alpha^*,\beta^*
x∗,α∗,β∗ ，使
x
∗
x^*
x∗是原始问题的解，
α
∗
,
β
∗
\alpha^*,\beta^*
α∗,β∗是对偶问题的解的充分必要条件是
x
∗
,
α
∗
,
β
∗
x^*,\alpha^*,\beta^*
x∗,α∗,β∗满足下面的Karush-Kuhn-Tucker(KKT)条件：
∂
L
(
x
∗
,
α
∗
,
β
∗
)
∂
x
i
=
0
,
i
=
1
,
.
.
.
d
\frac{\partial L(x^*,\alpha^*,\beta^*)}{\partial x_i}=0,\quad i=1,...d
∂xi∂L(x∗,α∗,β∗)=0,i=1,...d
∂
L
(
x
∗
,
α
∗
,
β
∗
)
∂
β
i
=
0
,
i
=
1
,
.
.
.
,
l
\frac{\partial L(x^*,\alpha^*,\beta^*)}{\partial \beta_{i}}=0,\quad i=1,...,l
∂βi∂L(x∗,α∗,β∗)=0,i=1,...,l
α
i
f
i
(
x
∗
)
=
0
,
i
=
1
,
.
.
.
,
k
\alpha_if_i(x^*)=0,\quad i=1,...,k
αifi(x∗)=0,i=1,...,k
f
i
(
x
∗
)
≤
0
,
i
=
1
,
.
.
.
,
k
f_i(x^*)\le0,\quad i=1,...,k
fi(x∗)≤0,i=1,...,k
α
i
≥
0
,
i
=
1
,
.
.
.
,
k
\alpha_i\ge0,\quad i=1,...,k
αi≥0,i=1,...,k
二、经典的SVM
经典的SVM主要用来处理线性可分的问题。如图所示，对于两类样本点，我们期望找到一条合适的分隔线，使其到两个类别支撑向量的距离最大，同时，到两个支撑向量的距离相同。
这里由于分隔线到两条支撑向量的距离相同，而且分隔线函数为
w
x
+
b
=
0
wx+b=0
wx+b=0，因此我们不妨设两条支撑向量的函数分别为
w
x
+
b
=
1
wx+b=1
wx+b=1和
w
x
+
b
=
−
1
wx+b=-1
wx+b=−1。因此我们可以得到:
(
w
T
x
1
+
b
)
−
(
w
T
x
2
+
b
)
=
2
(w^Tx_1+b)-(w^Tx_2+b)=2
(wTx1+b)−(wTx2+b)=2
w
T
(
x
1
−
x
2
)
=
2
w^T(x_1-x_2)=2
wT(x1−x2)=2
向量
a
a
a与向量
b
b
b的内积可以看做
a
a
a的模与
b
b
b在
a
a
a方向上投影的乘积，即
a
⋅
b
=
∣
∣
a
∣
∣
∣
2
∣
b
∣
∣
2
cos
θ
a\cdot b=||a|||_2|b||_2\cos\theta
a⋅b=∣∣a∣∣∣2∣b∣∣2cosθ
因此我们可以的得到：
∣
∣
w
∣
∣
2
∣
∣
x
1
−
x
2
∣
∣
2
cos
θ
=
2
||w||_2||x_1-x_2||_2\cos\theta=2
∣∣w∣∣2∣∣x1−x2∣∣2cosθ=2
∣
∣
x
1
−
x
2
∣
∣
cos
θ
=
2
∣
∣
w
∣
∣
2
=
d
1
+
d
2
||x_1-x_2||\cos\theta=\frac{2}{||w||_2}=d_1+d_2
∣∣x1−x2∣∣cosθ=∣∣w∣∣22=d1+d2
我们的目的是使得两个支撑向量之间的距离
d
d
d达到最大，即:
max
w
,
b
2
∣
∣
w
∣
∣
2
\max\limits_{w,b}\frac{2}{||w||_2}
w,bmax∣∣w∣∣22
按照机器学习求最小的习惯，将其转化成最小值问题，我们求
min
∣
∣
w
∣
∣
2
\min||w||^2
min∣∣w∣∣2的效果是一样的
同时对于这里的二分类问题，我们假设其标签为1或-1，因此对于在支撑向量上的点，满足
y
(
i
)
(
w
T
x
(
i
)
+
b
)
=
1
y^{(i)}(w^Tx^{(i)}+b)=1
y(i)(wTx(i)+b)=1，对于不在支撑向量上的点，其一定满足
y
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
y^{(i)}(w^Tx^{(i)}+b)\ge1
y(i)(wTx(i)+b)≥1，因此我们的到最后的目标函数：
min
w
,
b
1
2
∣
∣
w
∣
∣
2
\min\limits_{w,b}\frac{1}{2}||w||^2
w,bmin21∣∣w∣∣2
s
.
t
.
y
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
,
i
=
1
,
.
.
.
,
n
s.t.y^{(i)}(w^Tx^{(i)}+b)\ge1,\quad i=1,...,n
s.t.y(i)(wTx(i)+b)≥1,i=1,...,n
为了满足拉格朗日对偶变换，我们可以将约束条件写为：
g
i
(
w
)
=
−
y
(
i
)
(
w
T
x
(
i
)
+
b
)
+
1
≤
0
g_i(w)=-y^{(i)}(w^Tx^{(i)}+b)+1\le0
gi(w)=−y(i)(wTx(i)+b)+1≤0
将问题构造成拉格朗日函数为：
min
w
,
b
max
α
L
(
w
,
b
,
α
)
=
1
2
∣
∣
w
∣
∣
2
−
∑
i
=
1
n
α
i
[
y
(
i
)
(
w
T
x
(
i
)
+
b
)
−
1
]
\min\limits_{w,b}\max\limits_{\alpha}L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum\limits_{i=1}^n\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]
w,bminαmaxL(w,b,α)=21∣∣w∣∣2−i=1∑nαi[y(i)(wTx(i)+b)−1]
由于这里原函数为凸函数，同时其限制条件为线性函数也为凸函数，因此我们可以将其进行KKT条件的构造，转化成对偶问题：
∇
w
L
(
w
,
b
,
α
)
=
w
−
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
=
0
\nabla_wL(w,b,\alpha)=w-\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{(i)}=0
∇wL(w,b,α)=w−i=1∑nαiy(i)x(i)=0可得：
w
=
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
w=\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{(i)}
w=i=1∑nαiy(i)x(i)
∇
b
L
(
w
,
b
,
α
)
=
∑
i
=
1
n
α
i
y
(
i
)
=
0
\nabla_bL(w,b,\alpha)=\sum\limits_{i=1}^n\alpha_iy^{(i)}=0
∇bL(w,b,α)=i=1∑nαiy(i)=0
我们将
w
w
w打带入拉格朗日化的原问题可得：
L
(
w
,
b
,
α
)
=
1
2
w
T
w
−
w
T
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
−
b
∑
i
=
1
n
α
i
y
(
i
)
+
∑
i
=
1
n
α
i
=
∑
i
=
1
n
α
i
−
1
2
∑
i
,
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
x
(
i
)
(
x
(
j
)
)
T
\begin{aligned}L(w,b,\alpha)&=\frac{1}{2}w^Tw-w^T\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{(i)}-b\sum\limits_{i=1}^n\alpha_iy^{(i)}+\sum\limits_{i=1}^n\alpha_i\\ &=\sum\limits_{i=1}^n\alpha_i-\frac{1}{2}\sum\limits_{i,j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)}(x^{(j)})^T \end{aligned}
L(w,b,α)=21wTw−wTi=1∑nαiy(i)x(i)−bi=1∑nαiy(i)+i=1∑nαi=i=1∑nαi−21i,j=1∑nαiαjy(i)y(j)x(i)(x(j))T
此时问题就转变成了关于
α
\alpha
α的函数，构造dual得：
max
α
W
(
α
)
=
∑
i
=
1
n
α
i
−
1
2
∑
i
,
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
x
(
i
)
(
x
(
j
)
)
T
\max\limits_\alpha W(\alpha)=\sum\limits_{i=1}^n\alpha_i-\frac{1}{2}\sum\limits_{i,j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}x^{(i)}(x^{(j)})^T
αmaxW(α)=i=1∑nαi−21i,j=1∑nαiαjy(i)y(j)x(i)(x(j))T
s
.
t
.
α
i
≥
0
,
i
=
1
,
.
.
,
n
s.t.\quad \alpha_i\ge0,\quad i=1,..,n
s.t.αi≥0,i=1,..,n
∑
i
=
1
n
α
i
y
(
i
)
=
0
\sum\limits_{i=1}^n\alpha_iy^{(i)}=0
i=1∑nαiy(i)=0
同时其要满足KKT条件如下：
α
i
g
i
(
w
∗
)
=
0
,
i
=
1
,
.
.
.
,
k
\alpha_ig_i(w^*)=0,\quad i=1,...,k
αigi(w∗)=0,i=1,...,k
g
i
(
w
∗
)
≤
0
,
i
=
1
,
.
.
.
,
k
g_i(w^*)\le0,\quad i=1,...,k
gi(w∗)≤0,i=1,...,k
由于该问题为二次规划问题，所以一定存在最优解
α
∗
=
(
α
1
∗
,
.
.
.
,
α
n
∗
)
\alpha*=(\alpha_1^*,...,\alpha_n^*)
α∗=(α1∗,...,αn∗)，那么就可以计算原始问题的最优解
w
∗
=
∑
i
=
1
n
α
i
∗
y
(
i
)
x
(
i
)
w^*=\sum\limits_{i=1}^n\alpha_i^*y^{(i)}x^{(i)}
w∗=i=1∑nαi∗y(i)x(i)，同时如果
α
i
∗
≠
0
\alpha_i^*\ne0
αi∗=0的话，那么根据KKT条件，
−
y
(
i
)
(
w
T
x
(
i
)
+
b
)
+
1
=
0
-y^{(i)}(w^Tx^{(i)}+b)+1=0
−y(i)(wTx(i)+b)+1=0，其中
y
∈
{
1
,
−
1
}
y\in\{1,-1\}
y∈{1,−1},因此可得
b
∗
=
y
(
i
)
−
∑
i
=
1
n
α
i
∗
y
(
i
)
x
(
i
)
b^*=y^{(i)}-\sum\limits_{i=1}^n\alpha_i^*y^{(i)}x^{(i)}
b∗=y(i)−i=1∑nαi∗y(i)x(i)。
训练结束之后，每来一个新的数据
x
x
x我们便可以对其进行预测：
y
=
s
i
g
n
(
w
T
x
+
b
)
=
s
i
g
n
(
(
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
)
T
x
+
b
)
=
s
i
g
n
(
∑
i
=
1
n
α
i
y
(
i
)
<
x
(
i
)
,
x
>
+
b
)
\begin{aligned}y&=sign(w^Tx+b)\\ &=sign((\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{}(i))^Tx+b)\\ &= sign(\sum\limits_{i=1}^n\alpha_iy^{(i)}<x^{(i)},x>+b)\end{aligned}
y=sign(wTx+b)=sign((i=1∑nαiy(i)x(i))Tx+b)=sign(i=1∑nαiy(i)<x(i),x>+b)
其中
s
i
g
n
sign
sign为阶跃函数：
s
i
g
n
(
x
)
=
{
1
x
>
0
0
x
=
0
−
1
x
<
0
sign(x)=\left\{ \begin{array}{rcl} 1 & & {x>0}\\ 0 & & {x=0}\\ -1 & &{x<0} \end{array} \right.
sign(x)=⎩⎨⎧10−1x>0x=0x<0
这里看似每来一个数据，要计算其分类需要同所有样本数据进行一次计算，但实际上有KKT条件的约束：
α
i
g
i
(
w
∗
)
=
0
,
i
=
1
,
.
.
.
,
k
\alpha_ig_i(w^*)=0,\quad i=1,...,k
αigi(w∗)=0,i=1,...,k
根据支持向量机的定义我们可以知道，大部分数据点都位于支撑线以内，即
g
i
(
w
)
=
0
g_i(w)=0
gi(w)=0，因此其
α
i
=
0
\alpha_i=0
αi=0，因此我们只需要记住支撑向量上有限几个
α
i
\alpha_i
αi不等于0的点进行预测即可，大大缩短了预测所需的计算量。
三、带松弛变量的SVM
在实际应用中，完全线性可分的情况往往很少，那么我们应该怎么处理一些异常点呢？有一种思路就是放宽其区分的条件，我们称之为软间隔。
我们允许少数出现
y
(
i
)
(
w
T
x
(
i
)
+
b
)
<
1
y^{(i)}(w^Tx^{(i)}+b)<1
y(i)(wTx(i)+b)<1的情况出现，但是我们应该放宽达到什么地步，我们为每一个样本引入松弛变量
ξ
i
\xi_i
ξi来进行控制，其中
ξ
i
≥
0
\xi_i\ge0
ξi≥0，
C
C
C是一个大于零的常数，可以理解为对错误样本的惩罚程度，可以类比正则项中的正则系数。此时我们的目标函数就变成了：
min
w
1
2
∣
∣
w
∣
∣
2
+
C
∑
i
=
1
n
ξ
i
\min\limits_{w}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^n\xi_i
wmin21∣∣w∣∣2+Ci=1∑nξi
s
.
t
.
y
(
i
)
(
w
T
x
(
i
)
+
b
)
≥
1
−
ξ
i
,
i
=
,
.
.
.
,
n
s.t.\quad y^{(i)}(w^Tx^{(i)}+b)\ge1-\xi_i,\quad i=,...,n
s.t.y(i)(wTx(i)+b)≥1−ξi,i=,...,n
ξ
i
≥
0
,
i
=
1
,
.
.
.
,
n
\xi_i\ge0,\quad i=1,...,n
ξi≥0,i=1,...,n
同样我们将原问题进行拉格朗日化变为：
min
w
,
b
,
ξ
max
α
,
β
L
(
w
,
b
,
ξ
,
α
,
β
)
=
min
w
1
2
∣
∣
w
∣
∣
2
+
C
∑
i
=
1
n
ξ
i
−
∑
i
=
1
n
α
i
[
y
(
i
)
(
w
T
x
(
i
)
+
b
)
+
ξ
i
−
1
]
−
∑
i
=
1
n
β
i
ξ
i
\min\limits_{w,b,\xi}\max\limits_{\alpha,\beta} L(w,b,\xi,\alpha,\beta)=\min\limits_{w}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^n\xi_i-\sum\limits_{i=1}^n\alpha_i[y^{(i)}(w^Tx^{(i)}+b)+\xi_i-1]-\sum\limits_{i=1}^n\beta_i\xi_i
w,b,ξminα,βmaxL(w,b,ξ,α,β)=wmin21∣∣w∣∣2+Ci=1∑nξi−i=1∑nαi[y(i)(wTx(i)+b)+ξi−1]−i=1∑nβiξi
s
.
t
.
α
i
≥
0
,
β
i
≥
0
s.t.\quad\alpha_i\ge0,\quad\beta_i\ge0
s.t.αi≥0,βi≥0
其对偶问题为：
max
α
,
β
min
w
,
b
,
ξ
L
(
w
,
b
,
ξ
,
α
,
β
)
\max\limits_{\alpha,\beta}\min\limits_{w,b,\xi} L(w,b,\xi,\alpha,\beta)
α,βmaxw,b,ξminL(w,b,ξ,α,β)
满足以下KKT条件：
∇
w
L
(
w
,
b
,
ξ
,
α
,
β
)
=
w
−
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
=
0
\nabla_wL(w,b,\xi,\alpha,\beta)=w-\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{(i)}=0
∇wL(w,b,ξ,α,β)=w−i=1∑nαiy(i)x(i)=0可得：
w
=
∑
i
=
1
n
α
i
y
(
i
)
x
(
i
)
w=\sum\limits_{i=1}^n\alpha_iy^{(i)}x^{(i)}
w=i=1∑nαiy(i)x(i)
∇
b
L
(
w
,
b
,
ξ
,
α
,
β
)
=
∑
i
=
1
n
α
i
y
(
i
)
=
0
\nabla_bL(w,b,\xi,\alpha,\beta)=\sum\limits_{i=1}^n\alpha_iy^{(i)}=0
∇bL(w,b,ξ,α,β)=i=1∑nαiy(i)=0
∇
ξ
i
L
(
w
,
b
,
ξ
i
,
α
,
β
)
=
C
−
α
i
−
β
i
=
0
\nabla_{\xi_i} L(w,b,\xi_i,\alpha,\beta)=C-\alpha_i-\beta_i=0
∇ξiL(w,b,ξi,α,β)=C−αi−βi=0
将以上得到的三个条件带入拉格朗日化的函数可得：
max
α
L
(
w
,
b
,
ξ
,
α
,
β
)
=
∑
i
=
1
n
α
i
−
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
<
x
(
i
)
,
x
(
j
)
>
s
.
t
.
0
≤
α
i
≤
C
∑
i
=
1
n
α
i
y
(
i
)
=
0
\begin{aligned}\max\limits_\alpha L(w,b,\xi,\alpha,\beta)&=\sum\limits_{i=1}^n\alpha_i-\frac{1}{2}\sum\limits_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}<x^{(i)},x^{(j)}>\\ s.t.\quad&0\le\alpha_i\le C\\&\sum\limits_{i=1}^n\alpha_iy^{(i)}=0\end{aligned}
αmaxL(w,b,ξ,α,β)s.t.=i=1∑nαi−21i=1∑nj=1∑nαiαjy(i)y(j)<x(i),x(j)>0≤αi≤Ci=1∑nαiy(i)=0
同时其满足KKT条件如下：
1
−
ξ
i
−
y
(
i
)
(
w
T
x
(
i
)
+
b
)
≤
0
1-\xi_i-y^{(i)}(w^Tx^{(i)}+b)\le0
1−ξi−y(i)(wTx(i)+b)≤0
α
i
[
1
−
ξ
i
−
y
(
i
)
(
w
T
x
(
i
)
+
b
)
]
=
0
\alpha_i[1-\xi_i-y^{(i)}(w^Tx^{(i)}+b)]=0
αi[1−ξi−y(i)(wTx(i)+b)]=0
C
−
α
i
−
β
i
=
0
C-\alpha_i-\beta_i=0
C−αi−βi=0
ξ
i
≥
0
\xi_i\ge0
ξi≥0
β
i
ξ
i
=
0
\beta_i\xi_i=0
βiξi=0
此时我们可以针对
α
i
\alpha_i
αi不同的取值进行讨论：
- 如果 α i = 0 \alpha_i=0 αi=0，可得 β i = C ≠ 0 \beta_i=C\ne0 βi=C=0，因此 ξ i = 0 \xi_i=0 ξi=0， y ( i ) ( w T x ( i ) + b ) ≥ 1 y^{(i)}(w^Tx^{(i)}+b)\ge1 y(i)(wTx(i)+b)≥1，说明样本点 x x x落在分隔边界上或者分隔边界外并且被分类正确，不是支撑向量
- 如果 0 < α i < C 0<\alpha_i<C 0<αi<C，那么 β i ≠ 0 ， ξ i = 0 \beta_i\ne0，\xi_i=0 βi=0，ξi=0，此时 1 − ξ i − y ( i ) ( w T x ( i ) + b ) = 0 1-\xi_i-y^{(i)}(w^Tx^{(i)}+b)=0 1−ξi−y(i)(wTx(i)+b)=0，因此可得 y ( i ) ( w T x ( i ) + b ) = 1 y^{(i)}(w^Tx^{(i)}+b)=1 y(i)(wTx(i)+b)=1，所以此时的样本点落在最大分隔边界上，是支撑向量
- 如果 α i = C \alpha_i=C αi=C，此时 β i = 0 \beta_i=0 βi=0，此时 ξ i \xi_i ξi的取值就变得不一定，但一定是大于等于0的，同时 1 − ξ i − y ( i ) ( w T x ( i ) + b ) = 0 1-\xi_i-y^{(i)}(w^Tx^{(i)}+b)=0 1−ξi−y(i)(wTx(i)+b)=0，所以可得 y ( i ) ( w T x ( i ) + b ) ≤ 1 y^{(i)}(w^Tx^{(i)}+b)\le1 y(i)(wTx(i)+b)≤1。- 如果 0 ≤ ξ i < 1 0\le\xi_i<1 0≤ξi<1，此时 y ( i ) ( w T x ( i ) + b ) = 1 − ξ i > 0 y^{(i)}(w^Tx^{(i)}+b)=1-\xi_i>0 y(i)(wTx(i)+b)=1−ξi>0,说明此时的样本点位于最大分隔边界内部并且分类正确。- 如果 ξ i = 1 \xi_i=1 ξi=1，此时 y ( i ) ( w T x ( i ) + b ) = 1 − ξ i = 0 y^{(i)}(w^Tx^{(i)}+b)=1-\xi_i=0 y(i)(wTx(i)+b)=1−ξi=0，说明此时样本点位于分隔平面上，无法进行正确的分类。- 如果 ξ i > 1 \xi_i>1 ξi>1，此时 y ( i ) ( w T x ( i ) + b ) = 1 − ξ i < 0 y^{(i)}(w^Tx^{(i)}+b)=1-\xi_i<0 y(i)(wTx(i)+b)=1−ξi<0，说明此时样本点分类错误
四、带核函数的SVM
使用带核函数的SVM主要用来处理线性不可分的情况，已经不是单纯的处理部分异常值的问题。下面的左图很明显不可能靠一条线性的线来讲两个类别给区分开，只能是如右图所示将其映射至高维空间。
假设原来的样本点为
x
x
x，我们射映射后的样本点为
ϕ
(
x
)
\phi(x)
ϕ(x)，那么其分割的超平面可以表示为
w
ϕ
(
x
)
+
b
w\phi(x)+b
wϕ(x)+b，其对偶问题就变成了：
max
α
L
(
w
,
b
,
ξ
,
α
,
β
)
=
∑
i
=
1
n
α
i
−
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
<
ϕ
(
x
(
i
)
)
,
ϕ
(
x
(
j
)
)
>
s
.
t
.
0
≤
α
i
≤
C
∑
i
=
1
n
α
i
y
(
i
)
=
0
\begin{aligned}\max\limits_\alpha L(w,b,\xi,\alpha,\beta)&=\sum\limits_{i=1}^n\alpha_i-\frac{1}{2}\sum\limits_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}<\phi(x^{(i)}),\phi(x^{(j)})>\\ s.t.\quad&0\le\alpha_i\le C\\&\sum\limits_{i=1}^n\alpha_iy^{(i)}=0\end{aligned}
αmaxL(w,b,ξ,α,β)s.t.=i=1∑nαi−21i=1∑nj=1∑nαiαjy(i)y(j)<ϕ(x(i)),ϕ(x(j))>0≤αi≤Ci=1∑nαiy(i)=0
核函数的作用
我们假设
K
(
x
(
i
)
,
x
(
j
)
)
K(x^{(i)},x^{(j)})
K(x(i),x(j))为核函数，其可以代替
<
ϕ
(
x
(
i
)
)
,
ϕ
(
x
(
j
)
)
>
<\phi(x^{(i)}),\phi(x^{(j)})>
<ϕ(x(i)),ϕ(x(j))>来进行相同的运算。原始向量映射至高纬空间再进行点积运算是一件十分繁琐的事情，而使用核函数使得我们无需进行这一步骤，以另一种方式达到同样的效果，省去大量计算，下面将举例说明：
我们假设原始数据为
x
i
=
[
x
i
1
x
i
2
]
x
j
=
[
x
j
1
x
j
2
]
x_i=[x_{i1}x_{i2}]\quad\quad x_j=[x_{j1}x_{j2}]
xi=[xi1xi2]xj=[xj1xj2]
我们想要实现
<
x
i
,
x
j
>
2
<x_i,x_j>^2
<xi,xj>2的功能：
K
(
x
i
,
x
j
)
=
<
x
i
,
x
j
>
2
=
(
x
i
1
x
j
1
+
x
i
2
x
j
2
)
2
=
(
x
i
1
2
x
j
1
2
+
x
i
2
2
x
j
2
2
+
2
x
i
1
x
j
1
x
i
2
x
j
2
)
=
<
ϕ
(
x
1
)
,
ϕ
(
x
2
)
>
\begin{aligned}K(x_i,x_j)&=<x_i,x_j>^2\\ &=(x_{i1}x_{j1}+x_{i2}x_{j2})^2\\ &= (x_{i1}^2x_{j1}^2+x_{i2}^2x_{j2}^2+2x_{i1}x_{j1}x_{i2}x_{j2})\\&=<\phi(x_1),\phi(x_2)>\end{aligned}
K(xi,xj)=<xi,xj>2=(xi1xj1+xi2xj2)2=(xi12xj12+xi22xj22+2xi1xj1xi2xj2)=<ϕ(x1),ϕ(x2)>
ϕ
(
x
i
)
=
[
x
i
1
2
,
x
i
2
2
,
2
x
i
1
x
i
2
]
\phi(x_i)=[x_{i1}^2,x_{i2}^2,\sqrt{2}x_{i1}x_{i2}]
ϕ(xi)=[xi12,xi22,2xi1xi2]
ϕ
(
x
j
)
=
[
x
j
1
2
,
x
j
2
2
,
2
x
j
1
x
j
2
]
\phi(x_j)=[x_{j1}^2,x_{j2}^2,\sqrt{2}x_{j1}x_{j2}]
ϕ(xj)=[xj12,xj22,2xj1xj2]
可见使用核函数无需将数据映射至高维，大大简化了计算的过程。
核函数的要求
G
r
a
m
Gram
Gram矩阵：
G
i
j
=
K
(
x
i
,
x
j
)
G_{ij}=K(x_i,x_j)
Gij=K(xi,xj)
如果
G
r
a
m
Gram
Gram矩阵为对称矩阵并且为半正定矩阵，那么
K
(
x
i
,
x
j
)
K(x_i,x_j)
K(xi,xj)可以成为核函数。
常见的核函数
①多项式核函数 POLY
K
(
x
i
,
x
j
)
=
(
<
x
i
,
x
j
>
+
c
)
d
K(x_i,x_j)=(<x_i,x_j>+c)^d
K(xi,xj)=(<xi,xj>+c)d
c ≥ 0 c\ge0 c≥0控制低阶项的强度- 特殊情况，当 c = 0 , d = 1 c=0,d=1 c=0,d=1时就是线性核，跟无核一样
②高斯核函数 RBF
K
(
x
i
,
x
j
)
=
e
x
p
(
−
∣
∣
x
i
−
x
j
∣
∣
2
2
2
σ
2
)
K(x_i,x_j)=exp(-\frac{||x_i-x_j||^2_2}{2\sigma^2})
K(xi,xj)=exp(−2σ2∣∣xi−xj∣∣22)
- 当 x i = x j x_i=x_j xi=xj，值为1，当 x i 与 x j x_i与x_j xi与xj距离增加，值倾向于0，使用高斯核函数之前需要将特征正规划
- 相当于做一个高维空间的高斯分布映射， σ \sigma σ越大，则正态分布的曲线越舒缓。
- 使用高斯核之前需要将数据进行正规化
五、将SVM扩展到支持多个类别
①OVR
对于K个类别的情况，训练K个SVM,第j个SVM用于判断任意条数据是属于类别j还是属于类别非j.预测的时候，具有最大值的
w
i
T
x
+
b
i
w_i^Tx+b_i
wiTx+bi表示给定的数据
x
x
x属于类别
i
i
i.
②OVO
对于K个类别的情况，训练
K
∗
(
K
−
1
)
/
2
K*(K-1)/2
K∗(K−1)/2个SVM,每一个SVM只用于判读任意条数据是属于K中的特定两个类别。预测的时候，使用
K
∗
(
K
−
1
)
/
2
K*(K-1)/2
K∗(K−1)/2个SVM做
K
∗
(
K
−
1
)
/
2
K*(K-1)/2
K∗(K−1)/2次预测，使用计票的方式决定数据被分类为哪个类别的次数最多，就认为数据
x
x
x属此类别。
六、SVM的求解
经过对偶变换，我们将原始问题转化成了关于求解
α
∗
\alpha^*
α∗的问题：
min
α
L
(
w
,
b
,
ξ
,
α
,
β
)
=
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
K
(
x
(
i
)
,
x
(
j
)
)
−
∑
i
=
1
n
α
i
s
.
t
.
0
≤
α
i
≤
C
∑
i
=
1
n
α
i
y
(
i
)
=
0
\begin{aligned}\min\limits_\alpha L(w,b,\xi,\alpha,\beta)&=\frac{1}{2}\sum\limits_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})-\sum\limits_{i=1}^n\alpha_i\\ s.t.\quad&0\le\alpha_i\le C\\&\sum\limits_{i=1}^n\alpha_iy^{(i)}=0\end{aligned}
αminL(w,b,ξ,α,β)s.t.=21i=1∑nj=1∑nαiαjy(i)y(j)K(x(i),x(j))−i=1∑nαi0≤αi≤Ci=1∑nαiy(i)=0
这里最优解
α
∗
\alpha^*
α∗是
n
n
n维的，直接求解在
n
n
n过大的情况下并不能完成，因此我们可以采用坐标轮换法的思想：
其原理就是对于高维的
x
x
x寻找最优解的过程转化为一系列低纬的
x
i
x_i
xi分量求解过程，利用梯度下降的方法，在各自的维度上依次寻找最优解，最终可以达到相同的效果。
关于SVM求解我们使用较多的是SMO算法，其就是采用了坐标轮换法的思想，下面将进行介绍：
如果我们每次只选择更新一个参数
α
i
\alpha_i
αi，那么他势必会打破
∑
i
=
1
n
α
i
y
(
i
)
=
0
\sum\limits_{i=1}^n\alpha_iy^{(i)}=0
i=1∑nαiy(i)=0的约束条件，因此SMO算法每次针对两个参数进行更新
α
1
和
α
2
\alpha_1和\alpha_2
α1和α2，这两个参数满足：
α
1
y
(
1
)
+
α
2
y
(
2
)
=
−
∑
k
=
3
n
α
k
y
(
k
)
\alpha_1y^{(1)}+\alpha_2y^{(2)}=-\sum\limits_{k=3}^n\alpha_ky^{(k)}
α1y(1)+α2y(2)=−k=3∑nαky(k)
我们不妨设
−
∑
k
=
3
n
α
k
y
(
k
)
-\sum\limits_{k=3}^n\alpha_ky^{(k)}
−k=3∑nαky(k)为一个固定的常数
ζ
\zeta
ζ，那么我们可以得到
α
1
y
(
1
)
+
α
2
y
(
2
)
=
ζ
\alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta
α1y(1)+α2y(2)=ζ
因此我们可以得到
α
1
=
ζ
y
(
1
)
−
α
2
y
(
2
)
y
(
1
)
\alpha_1=\zeta y^{(1)}-\alpha_2y^{(2)}y^{(1)}
α1=ζy(1)−α2y(2)y(1)
求解过程
**1.先求得未限制范围的
α
2
n
e
w
,
u
n
c
\alpha_2^{new,unc}
α2new,unc**
下面介绍
α
2
n
e
w
,
u
n
c
\alpha_2^{new,unc}
α2new,unc的求解过程：
记：
g
(
x
)
=
∑
i
=
1
n
α
i
y
i
K
(
x
i
,
x
)
+
b
g(x)=\sum\limits_{i=1}^n\alpha_iy_iK(x_i,x)+b
g(x)=i=1∑nαiyiK(xi,x)+b
令：
E
i
=
g
(
x
i
)
−
y
i
=
(
∑
j
=
1
n
α
j
y
j
K
(
x
j
,
x
i
)
+
b
)
−
y
i
E_i=g(x_i)-y_i=(\sum\limits_{j=1}^n\alpha_jy_jK(x_j,x_i)+b)-y_i
Ei=g(xi)−yi=(j=1∑nαjyjK(xj,xi)+b)−yi
引入：
v
i
=
∑
j
=
3
n
α
j
y
j
K
(
x
i
,
x
j
)
=
g
(
x
i
)
−
∑
j
=
1
2
α
j
y
j
K
(
x
i
,
x
j
)
−
b
v_i=\sum\limits_{j=3}^n\alpha_jy_jK(x_i,x_j)=g(x_i)-\sum\limits_{j=1}^2\alpha_jy_jK(x_i,x_j)-b
vi=j=3∑nαjyjK(xi,xj)=g(xi)−j=1∑2αjyjK(xi,xj)−b
目标函数：
W
(
α
)
=
min
α
L
(
w
,
b
,
ξ
,
α
,
β
)
=
1
2
∑
i
=
1
n
∑
j
=
1
n
α
i
α
j
y
(
i
)
y
(
j
)
K
(
x
(
i
)
,
x
(
j
)
)
−
∑
i
=
1
n
α
i
W(\alpha)=\min\limits_\alpha L(w,b,\xi,\alpha,\beta)=\frac{1}{2}\sum\limits_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy^{(i)}y^{(j)}K(x^{(i)},x^{(j)})-\sum\limits_{i=1}^n\alpha_i
W(α)=αminL(w,b,ξ,α,β)=21i=1∑nj=1∑nαiαjy(i)y(j)K(x(i),x(j))−i=1∑nαi
W
(
α
1
,
α
2
)
=
1
2
α
1
2
K
11
+
1
2
α
2
2
K
22
+
α
1
α
2
y
1
y
2
K
12
+
y
1
v
1
α
1
+
y
2
v
2
α
2
−
(
α
1
+
α
2
)
+
O
W(\alpha_1,\alpha_2)=\frac{1}{2}\alpha_1^2K_{11}+\frac{1}{2}\alpha_2^2K_{22}+\alpha_1\alpha_2y_1y_2K_{12}+y_1v_1\alpha_1+y_2v_2\alpha_2-(\alpha_1+\alpha_2)+O
W(α1,α2)=21α12K11+21α22K22+α1α2y1y2K12+y1v1α1+y2v2α2−(α1+α2)+O
这里
O
O
O为其他无关常数项，对结果没什么影响，一会儿我们直接省去
前面我们已经说明过
α
1
=
ζ
y
(
1
)
−
α
2
y
(
2
)
y
(
1
)
\alpha_1=\zeta y^{(1)}-\alpha_2y^{(2)}y^{(1)}
α1=ζy(1)−α2y(2)y(1)，因此我们将
α
1
\alpha_1
α1替换掉得到：
W
(
α
2
)
=
1
2
(
ζ
−
α
2
y
2
)
2
K
11
+
1
2
α
2
2
K
22
+
(
ζ
−
α
2
y
2
)
α
2
y
2
K
12
+
v
1
(
ζ
−
α
2
y
2
)
+
y
2
v
2
α
2
−
[
(
ζ
y
1
−
α
2
y
2
y
1
)
+
α
2
]
W(\alpha_2)=\frac{1}{2}(\zeta-\alpha_2y_2)^2K_{11}+\frac{1}{2}\alpha_2^2K_{22}+(\zeta -\alpha_2y_2)\alpha_2y_2K_{12}+v_1(\zeta -\alpha_2y_2)+y_2v_2\alpha_2-[(\zeta y_1-\alpha_2y_2y_1)+\alpha_2]
W(α2)=21(ζ−α2y2)2K11+21α22K22+(ζ−α2y2)α2y2K12+v1(ζ−α2y2)+y2v2α2−[(ζy1−α2y2y1)+α2]
此时函数里只剩下
α
2
\alpha_2
α2一个未知项，我们对其求导得：
δ
W
δ
α
2
=
K
11
α
2
+
K
22
α
2
−
2
K
12
α
2
−
K
11
ζ
y
2
+
K
12
ζ
y
2
+
y
1
y
2
−
1
−
v
1
y
2
+
v
2
y
2
\frac{\delta W}{\delta\alpha_2}=K_{11}\alpha_2+K_{22}\alpha_2-2K_{12}\alpha_2-K_{11}\zeta y_2+K_{12}\zeta y_2+y_1y_2-1-v_1y_2+v_2y_2
δα2δW=K11α2+K22α2−2K12α2−K11ζy2+K12ζy2+y1y2−1−v1y2+v2y2
令其等于0得：
(
K
11
+
K
22
−
2
K
12
)
α
2
=
y
2
(
y
2
−
y
1
+
ζ
K
11
−
ζ
K
12
+
v
1
−
v
2
)
=
y
2
[
y
2
−
y
1
+
ζ
K
11
−
ζ
K
12
+
(
g
(
x
1
)
−
∑
j
=
1
2
α
j
y
j
K
1
j
−
b
)
−
(
g
(
x
2
)
−
∑
j
=
1
2
α
j
y
j
K
2
j
−
b
)
]
\begin{aligned}(K_{11}+K_{22}-2K_{12})\alpha_2&=y_2(y_2-y_1+\zeta K_{11}-\zeta K_{12}+v_1-v_2)\\&=y_2[y_2-y_1+\zeta K_{11}-\zeta K_{12}+(g(x_1)-\sum\limits_{j=1}^2\alpha_jy_jK_{1j}-b)-(g(x_2)-\sum\limits_{j=1}^2\alpha_jy_jK_{2j}-b)]\end{aligned}
(K11+K22−2K12)α2=y2(y2−y1+ζK11−ζK12+v1−v2)=y2[y2−y1+ζK11−ζK12+(g(x1)−j=1∑2αjyjK1j−b)−(g(x2)−j=1∑2αjyjK2j−b)]
我们令
η
=
(
K
11
+
K
22
−
2
K
12
)
\eta=(K_{11}+K_{22}-2K_{12})
η=(K11+K22−2K12)
我们将
ζ
=
α
1
o
l
d
y
1
+
α
2
o
l
d
y
2
\zeta=\alpha_1^{old}y_1+\alpha_2^{old}y_2
ζ=α1oldy1+α2oldy2代入式子得：
(
K
11
+
K
22
−
2
K
12
)
α
2
n
e
w
,
u
n
c
=
y
2
[
E
1
−
E
2
+
α
2
o
l
d
(
K
11
+
K
22
−
2
K
12
)
]
α
2
n
e
w
,
u
n
c
=
α
2
o
l
d
+
y
2
(
E
1
−
E
2
)
η
\begin{aligned}(K_{11}+K_{22}-2K_{12})\alpha_2^{new,unc}&=y_2[E_1-E_2+\alpha_2^{old}(K_{11}+K_{22}-2K_{12})]\\\\\alpha_2^{new,unc}&=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{\eta}\end{aligned}
(K11+K22−2K12)α2new,uncα2new,unc=y2[E1−E2+α2old(K11+K22−2K12)]=α2old+ηy2(E1−E2)
**2.求限制范围后的
α
2
n
e
w
\alpha_2^{new}
α2new**
其中
α
2
n
e
w
=
{
H
α
2
n
e
w
,
u
n
c
>
H
α
2
n
e
w
,
u
n
c
L
≤
α
2
n
e
w
,
u
n
c
≤
H
L
α
2
n
e
w
,
u
n
c
<
L
\alpha_2^{new}=\left\{ \begin{array}{rcl} H & & {\alpha_2^{new,unc}>H}\\\\ \alpha_2^{new,unc} & & {L\le\alpha_2^{new,unc}\le H}\\\\ L & &{\alpha_2^{new,unc}<L} \end{array} \right.
α2new=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧Hα2new,uncLα2new,unc>HL≤α2new,unc≤Hα2new,unc<L
这里我们的
α
2
n
e
w
\alpha_2^{new}
α2new是满足一定的约束关系的，
0
≤
α
i
≤
C
0\le \alpha_i\le C
0≤αi≤C，同时由于
α
1
y
(
1
)
+
α
2
y
(
2
)
=
ζ
\alpha_1y^{(1)}+\alpha_2y^{(2)}=\zeta
α1y(1)+α2y(2)=ζ，注意这里
y
(
i
)
∈
{
1
−
,
1
}
y^{(i)}\in\{1-,1\}
y(i)∈{1−,1}我们做下面两种假设：
y ( 1 ) y^{(1)} y(1)与 y ( 2 ) y^{(2)} y(2)同号，此时我们可以得到 α 1 + α 2 = k \alpha_1+\alpha_2=k α1+α2=k， α 2 = k − α 1 \alpha_2=k-\alpha_1 α2=k−α1，因为 α 1 ∈ [ 0 , C ] \alpha_1\in[0,C] α1∈[0,C]，所以 α 2 ∈ [ − C + k , k ] \alpha_2\in[-C+k,k] α2∈[−C+k,k]，又因为 k = α 1 + α 2 k=\alpha_1+\alpha_2 k=α1+α2，可得 α 2 ∈ [ α 1 + α 2 − C , α 1 + α 2 ] \alpha_2\in[\alpha_1+\alpha_2-C,\alpha_1+\alpha_2] α2∈[α1+α2−C,α1+α2]
因此可以得到
L
≤
α
2
n
e
w
≤
H
L\le \alpha_2^{new}\le H
L≤α2new≤H
L
=
m
a
x
(
0
,
α
1
o
l
d
+
α
2
o
l
d
−
C
)
,
H
=
m
i
n
(
C
,
α
1
o
l
d
+
α
2
o
l
d
)
L=max(0,\alpha_1^{old}+\alpha_2^{old}-C),\quad H=min(C,\alpha_1^{old}+\alpha_2^{old})
L=max(0,α1old+α2old−C),H=min(C,α1old+α2old)
y ( 1 ) y^{(1)} y(1)与 y ( 2 ) y^{(2)} y(2)异号，此时我们可以得到 α 1 − α 2 = k \alpha_1-\alpha_2=k α1−α2=k，因此可以得到 α 2 = α 1 − k \alpha_2=\alpha_1-k α2=α1−k，因为 α 1 ∈ [ 0 , C ] \alpha_1\in[0,C] α1∈[0,C]，所以 α 2 ∈ [ − k , C − k ] \alpha_2\in[-k,C-k] α2∈[−k,C−k]，又因为 k = α 1 − α 2 k=\alpha_1-\alpha_2 k=α1−α2，所以 α 2 ∈ [ α 2 − α 1 , C + α 2 − α 1 ] \alpha_2\in[\alpha_2-\alpha_1,C+\alpha_2-\alpha_1] α2∈[α2−α1,C+α2−α1]
因此可以得到
L
≤
α
2
n
e
w
≤
H
L\le \alpha_2^{new}\le H
L≤α2new≤H
L
=
m
a
x
(
0
,
α
2
o
l
d
−
α
1
o
l
d
)
,
H
=
m
i
n
(
C
,
C
+
α
2
o
l
d
−
α
1
o
l
d
)
L=max(0,\alpha_2^{old}-\alpha_1^{old}),\quad H=min(C,C+\alpha_2^{old}-\alpha_1^{old})
L=max(0,α2old−α1old),H=min(C,C+α2old−α1old)
**3.得到
α
1
n
e
w
\alpha_1^{new}
α1new的解**
根据
α
1
o
l
d
y
1
+
α
2
o
l
d
y
2
=
α
1
n
e
w
y
1
+
α
2
n
e
w
y
2
\alpha_1^{old}y_1+\alpha_2^{old}y_2=\alpha_1^{new}y_1+\alpha_2^{new}y_2
α1oldy1+α2oldy2=α1newy1+α2newy2
我们可以求得
α
1
n
e
w
=
α
1
o
l
d
+
y
1
y
2
(
α
2
o
l
d
−
α
2
n
e
w
)
\alpha_1^{new}=\alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})
α1new=α1old+y1y2(α2old−α2new)
**4.更新参数
b
b
b和
E
i
E_i
Ei**
前面我们已经证明，如果
0
≤
α
1
n
e
w
≤
C
0\le \alpha_1^{new}\le C
0≤α1new≤C，那么
α
1
n
e
w
\alpha_1^{new}
α1new为支持向量，我们可以利用它来更新参数
b
b
b
∑
i
=
1
n
α
i
y
i
K
i
1
+
b
=
y
1
\sum\limits_{i=1}^n\alpha_iy_iK_{i1}+b=y_1
i=1∑nαiyiKi1+b=y1
b
1
n
e
w
=
y
1
−
α
1
n
e
w
y
1
K
11
−
α
2
n
e
w
y
1
K
12
−
∑
i
=
3
n
α
i
y
i
K
i
1
b_1^{new}=y_1-\alpha_1^{new}y_1K_{11}-\alpha_2^{new}y_1K_{12}-\sum\limits_{i=3}^n\alpha_iy_iK_{i1}
b1new=y1−α1newy1K11−α2newy1K12−i=3∑nαiyiKi1
E
i
n
e
w
=
(
∑
S
α
j
y
j
K
(
x
j
,
x
i
)
+
b
n
e
w
)
−
y
i
E_i^{new}=(\sum\limits_{S}\alpha_jy_jK(x_j,x_i)+b^{new})-y_i
Einew=(S∑αjyjK(xj,xi)+bnew)−yi
其中
S
S
S为所有支撑向量的集合
变量的启发式选择
对于SMO算法，我们每次选择两个样本进行更新，那么其中至少有一个是要违反KKT条件的。
1.第一个变量的选择
- 违反KKT最严重的样本点，
- 检验样本点是否满足KKT条件 α i = 0 ⇒ y i g x ( x ) ≥ 0 \alpha_i=0\Rightarrow y_ig_x(x)\ge 0 αi=0⇒yigx(x)≥0 0 < α i < C ⇒ y i g x ( x ) = 0 0<\alpha_i<C\Rightarrow y_ig_x(x)=0 0<αi<C⇒yigx(x)=0 α i = C ⇒ y i g x ( x ) ≤ 1 \alpha_i=C\Rightarrow y_ig_x(x)\le1 αi=C⇒yigx(x)≤1 其中当 0 < α i < C 0<\alpha_i<C 0<αi<C时，对应点为支撑点，如果不满足KKT条件，对原始问题影响最大，所以我们一般选择 0 < α i < C 0<\alpha_i<C 0<αi<C并且 y i g x ( x ) ≠ 0 y_ig_x(x)\ne0 yigx(x)=0的点作为外循环
2.第二个变量的选择
我们的目的是希望目标函数能够有足够大的变化，即对应的
∣
E
1
−
E
2
∣
|E_1-E_2|
∣E1−E2∣最大，是目标函数下降的最快
- 如果内循环通过上述方法找到的点不能使目标函数有足够的下降，则： - 遍历间隔边界上的样本点，测试目标函数下降- 如果下降不大，则遍历所有样本点- 如果依然下降不大，则丢弃外循环点，重新选择
七、关于凸函数的补充
凸函数的定义
①其定义域为凸集
假设对于任意
x
,
y
∈
C
x,y \in C
x,y∈C并且任意参数
α
∈
[
0
,
1
]
\alpha \in [0,1]
α∈[0,1]，我们有
α
x
+
(
1
−
α
)
y
∈
C
\alpha x+(1-\alpha)y\in C
αx+(1−α)y∈C，(即两点之间的任何一点都在定义域内)则集合为凸集。
其中1为凸集，2、3不是
②函数定义域为凸集，对于定义域里的任意
x
,
y
x,y
x,y满足
f
(
θ
x
+
(
1
−
θ
)
y
)
<
=
θ
f
(
x
)
+
(
1
−
θ
)
f
(
y
)
f(\theta x+(1-\theta)y) <= \theta f(x)+(1-\theta)f(y)
f(θx+(1−θ)y)<=θf(x)+(1−θ)f(y)
凸函数的判定方法
对于一元函数
f
(
x
)
f(x)
f(x)，我们可以通过其二阶导数
f
″
(
x
)
f″(x)
f″(x) 的符号来判断。如果函数的二阶导数总是非负，即
f
′
′
(
x
)
≥
0
f′′(x)≥0
f′′(x)≥0f″ ，则
f
(
x
)
f(x)
f(x)是凸函数
对于多元函数
f
(
X
)
f(X)
f(X)，我们可以通过其Hessian矩阵（Hessian矩阵是由多元函数的二阶导数组成的方阵）的正定性来判断。如果Hessian矩阵是半正定矩阵，则是
f
(
X
)
f(X)
f(X)凸函数
常见的凸函数
- 线性函数为凸/凹函数
e x p x , − l o g x , x l o g x expx, −logx, xlogx expx,−logx,xlogx 是凸函数- 范数为凸函数范数 ∣ ∣ w ∣ ∣ 1 = ∣ w 1 ∣ + ∣ w 2 ∣ + . . . + ∣ w n ∣ ||w||_1=|w_1|+|w_2|+...+|w_n| ∣∣w∣∣1=∣w1∣+∣w2∣+...+∣wn∣ ∣ ∣ w ∣ ∣ 2 = w 1 2 + w 2 2 + . . . + w n 2 2 ||w||_2=\sqrt[2] {w_1^2+w_2^2+...+w_n^2} ∣∣w∣∣2=2w12+w22+...+wn2 ∣ ∣ w ∣ ∣ p = w 1 p + w 2 p + . . . + w n p p ||w||_p=\sqrt[p] {w_1^p+w_2^p+...+w_n^p} ∣∣w∣∣p=pw1p+w2p+...+wnp
x T x t \frac{x^Tx}{t} txTx为凸函数（ x > 0 x>0 x>0）
本文转载自: https://blog.csdn.net/chenjunheaixuexi/article/details/124945810
版权归原作者 小白学推荐 所有， 如有侵权，请联系我们删除。
版权归原作者 小白学推荐 所有， 如有侵权，请联系我们删除。