机器学习教程 之 支持向量机：模型篇3–对偶问题的求解: SMO算法 |
您所在的位置：网站首页 › 对偶问题的求解思路和方法 › 机器学习教程 之 支持向量机：模型篇3–对偶问题的求解: SMO算法 |
机器学习教程 之 支持向量机：模型篇3–对偶问题的求解: SMO算法
|
支持向量机是机器学习领域里最强的几种分类器之一，被广泛的运用于各种分类回归问题，如果不考虑集成学习算法以及近几年出现的深度学习算法，支持向量机的性能可以说是在学习领域具有统治地位，在一些中小型的数据集上它的性能甚至能够超过一些深度学习网络。其基本原理相当简单，但是模型的求解和优化却十分复杂，很难描述清楚，这里我会一步一步，尽我所能分章节的将它总结完善 ##模型篇 · 支持向量机：模型篇1–支持向量与间隔 · 支持向量机：模型篇2–支持向量的拉格朗日对偶 · 支持向量机：模型篇3–对偶问题的求解: SMO算法 · 支持向量机：模型篇4–核函数与非线性优化 · 支持向量机：模型篇5–向量机的软间隔拓展 ##代码篇 · 支持向量机：代码篇1-基于CVXPT优化函数求解 · 支持向量机：代码篇2-基于SMO算法求解 对偶问题的求解: SMO算法在上一章节中，我们将支持向量机的原始模型转化为了对偶形式。之前有提到，这一转化的重要意义在于提前计算 w w w 并消除了 w w w，将优化函数变为了关于拉格朗日乘子的二次规划问题。对于这一问题，学者们有针对性的提出了很多解法，其中目前被普遍应用的是由Microsoft Research的John C.Platt在1998年发表的论文《Sequential Minimal Optimaization A Fast Algorithm for Training Support Vector Machines》中提出的SMO算法，它成为当时最快的二次规划优化算法，特别是在针对线性SVM和数据稀疏等问题时更表现出强大的性能。 Platt论文中的符号表示与本文有所不同，现在，我们首先会重新列出上一章节中我们得到的优化目标，描述SMO算法的主要思想，再将优化目标转化为Platt论文中的形式，以方便描述，最后给出解决方案 1. 对偶优化目标和SMO算法原理上一章节中我们得到的对偶优化目标为： m a x a ∑ i = 1 n a i − 1 2 ∑ i , j = 1 n a i a j y i y j x i T x j max_{a} \sum_{i = 1}^{n}a_{i}- \frac{1}{2} \sum_{i,j = 1}^{n}a_{i}a_{j}y_{i}y_{j}x_{i}^{T}x_{j} maxa∑i=1nai−21∑i,j=1naiajyiyjxiTxj s . t . a i > = 0 , i = 1 , . . . , n s.t. a_{i} >= 0,i= 1,...,n s.t.ai>=0,i=1,...,n ∑ i = 1 n a i y i = 0 \sum_{i = 1}^{n}a_{i}y_{i} = 0 ∑i=1naiyi=0 为了求解的完整性，这里我们需要提前对 a i a_{i} ai 加上一个关于松弛变量的约束，关于这一约束我们会在之后第五章节的软间隔与正则化中详细描述，读者们不需要过于纠结（加入松弛变量的目的是为了让模型在训练时 不必完全的将两类样本划分开，允许一些离群的样本点出现在向量机所划分的间隔当中，以获得在测试集上更好的划分效果）。加入松弛变量后，模型转化为 m a x a ∑ i = 1 n a i − 1 2 ∑ i , j = 1 n a i a j y i y j x i T x j max_{a} \sum_{i = 1}^{n}a_{i}- \frac{1}{2} \sum_{i,j = 1}^{n}a_{i}a_{j}y_{i}y_{j}x_{i}^{T}x_{j} maxa∑i=1nai−21∑i,j=1naiajyiyjxiTxj s . t . C > = a i > = 0 , i = 1 , . . . , n s.t. C >= a_{i} >= 0,i= 1,...,n s.t.C>=ai>=0,i=1,...,n ∑ i = 1 n a i y i = 0 \sum_{i = 1}^{n}a_{i}y_{i} = 0 ∑i=1naiyi=0现在我们要解决的是调节参数 a 1 , a 2 , . . . , a n {a_{1},a_{2}, ... ,a_{n}} a1,a2,...,an 以求得优化目标的最大值， x i x_{i} xi 和 y i y_{i} yi 都是已知数， C C C 由我们预先设定，也是已知数。在SMO算法中，我需要固定住参数 a i a_{i} ai 中的除了 a 1 , a 2 a_{1},a_{2} a1,a2（这里的 a 1 , a 2 a_{1},a_{2} a1,a2只是代表其中的两个，下标不一定是1，2） 的其他所有 a a a，然后在 a 1 a_{1} a1 上求极值。那么既然是在 a 1 a_{1} a1 上求极值，为什么要保留两个参数变化呢？ 这是因为，如果固定住了 a 1 a_{1} a1 以外的所有参数，则根据式子 ∑ i = 1 n a i y i = 0 \sum_{i = 1}^{n}a_{i}y_{i} = 0 ∑i=1naiyi=0 我们可以推出 a 1 a_{1} a1 将是个定值，而不再是一个变量。因此，我们需要一次选取两个参数进行优化。比如 a 1 , a 2 a_{1},a_{2} a1,a2 ，此时 a 2 a_{2} a2 可以由 a 1 a_{1} a1 和其它式子表示出来，这样回代到目标函数中，原目标函数就是单一变量 a 1 a_{1} a1 的函数了，可解。 SMO算法主要分为两步操作以及循环： · 使用启发式的方法选取一对 a 1 ， a 2 a_{1}，a_{2} a1，a2 · 固定除了 a 1 ， a 2 a_{1}，a_{2} a1，a2 外的其它参数，确定使目标函数达到极值的 a 1 a_{1} a1 ，其中 a 2 a_{2} a2 可以由 a 1 a_{1} a1 表示 · 重复上述步骤直至算法收敛 这里只是SMO算法的简单描述供读者对SMO有一个大致的把握，关于当中的一些具体细节，我们会在后面详细描述，比如如何进行启发式选取参数、如何更新 a 1 ， a 2 a_{1}，a_{2} a1，a2 等。不要着急，我们先把目标函数转化为Platt文章中描述的形式。 m i n a 1 2 ∑ i , j = 1 n a i a j y i y j K ( x i , x j ) − ∑ i = 1 n a i min_{a} \frac{1}{2} \sum_{i,j = 1}^{n}a_{i}a_{j}y_{i}y_{j}K(x_{i},x_{j}) - \sum_{i = 1}^{n}a_{i} mina21∑i,j=1naiajyiyjK(xi,xj)−∑i=1nai s . t . C > = a i > = 0 , i = 1 , . . . , n s.t. C >= a_{i} >= 0,i= 1,...,n s.t.C>=ai>=0,i=1,...,n ∑ i = 1 n a i y i = 0 \sum_{i = 1}^{n}a_{i}y_{i} = 0 ∑i=1naiyi=0可以看出其实质并未发生变化，只是将目标函数取负，由求极大，变为了求极小而已，又将目标函数中的 x i T x j x_{i}^{T}x_{j} xiTxj记为 K ( x i , x j ) K(x_{i},x_{j}) K(xi,xj) 表示内积。还有一点，在Platt的文章中，它将向量机划分的超平面 f ( x ) = w T x + b f(x) = w^{T}x+b f(x)=wTx+b 写成了如下形式 u = w T x − b u = w^{T}x-b u=wTx−b 其实质都是一样的，相应的， w w w 可表示为（上一篇有具体推导） w = ∑ i = 1 n a i y i x i w = \sum_{i = 1}^{n}a_{i}y_{i}x_{i} w=∑i=1naiyixi 2.KKT条件与启发式选取参数在上一节SMO两个主要步骤中的第一步就是以启发式的方法选取一对 a 1 ， a 2 a_{1}，a_{2} a1，a2，现在我们来结合KKT条件具体说一下这个启发式方法。SMO算法注意到只需选取的 a 1 ， a 2 a_{1}，a_{2} a1，a2 中有一个不满足 KKT条件，目标函数就会越优，直观来看，**KKT条件违背的程度越大，则变量更新后可能导致的目标函数值优化程度越大。**那么什么是违背KKT条件的 a a a 呢？ 在加入了松弛条件C后,我们可以将上一篇博客中提到的KKT重写为 { C > = a i > = 0 y i u i − 1 > = 0 a i ( y i u i − 1 ) = 0 \left\{\begin{matrix}C>=a_{i} >=0\\y_{i}u_{i}-1 >= 0 \\ a_{i}(y_{i}u_{i}-1) = 0\end{matrix}\right. ⎩⎨⎧C>=ai>=0yiui−1>=0ai(yiui−1)=0 对于这三个式子，结合向量机划分超平面的几何意义（下图）我们可以理解为以下几种情况
a
i
=
0
,
y
i
u
i
−
1
>
=
0
a_{i} = 0 , y_{i}u_{i}-1 >= 0
ai=0,yiui−1>=0 ，对于这一情况，表明
a
i
a_{i}
ai 对应的样本点
(
x
i
,
y
i
)
(x_{i},y_{i})
(xi,yi)是正常分类,即被超平面合理的划分到了两边，同时在间隔之外
C
>
a
i
>
0
,
y
i
u
i
−
1
=
0
C > a_{i} > 0 , y_{i}u_{i}-1 = 0
C>ai>0,yiui−1=0 ，对于这一情况，表明
a
i
a_{i}
ai 对应的样本点
(
x
i
,
y
i
)
(x_{i},y_{i})
(xi,yi)是在分类间隔的边界上，是支持向量
C
=
a
i
,
y
i
u
i
−
1
<
=
0
C = a_{i} , y_{i}u_{i}-1 0则是不满足的,而原本
a
i
=
0
a_{i} = 0
ai=0
y
i
u
i
−
1
=
0
,
a
i
=
0
或
a
i
=
C
y_{i}u_{i} - 1 = 0,a_{i}=0或a_{i}=C
yiui−1=0,ai=0或ai=C则是不满足的,而原本
0
<
a
i
<
C
0 < a_{i} < C
0
=
0
C>=a>=0
C>=a>=0 的约束，可以得到
a
1
a_{1}
a1 的更新公式为：
a
1
n
e
w
=
a
1
+
y
1
(
E
2
−
E
1
)
η
a_{1}^{new} = a_{1} + \frac{y_{1}(E_{2}-E_{1})}{\eta }
a1new=a1+ηy1(E2−E1)
这里的
E
i
=
u
i
−
y
i
,
η
=
K
(
x
1
,
x
1
)
+
K
(
x
2
,
x
2
)
−
K
(
x
1
,
x
2
)
E_{i} = u_{i}-y_{i},\eta = K(x_{1},x_{1})+K(x_{2},x_{2})-K(x_{1},x_{2})
Ei=ui−yi,η=K(x1,x1)+K(x2,x2)−K(x1,x2)
然后再根据 a 1 y 1 + a 2 y 2 = ξ ( 常 数 ) a_{1}y_{1} + a_{2}y_{2} = \xi(常数) a1y1+a2y2=ξ(常数) 考虑约束 C > = a > = 0 C>=a>=0 C>=a>=0 ,由于支持向量机为二分类问题， y y y的取值可以为 1或者 -1，我们可以将问题分为两种情况即 y 1 , y 2 y_{1},y_{2} y1,y2同号和 y 1 , y 2 y_{1},y_{2} y1,y2异号，我们以两者异号为例，可以做图如下
同理， y 1 , y 2 y_{1},y_{2} y1,y2同号时 下界 L = m a x ( 0 , a 2 + a 1 − C ) L = max(0,a_{2}+a_{1}-C) L=max(0,a2+a1−C) 上界 H = m i n ( C , a 2 + a 1 ) H = min(C,a_{2}+a_{1}) H=min(C,a2+a1)我们就可以得到 a 1 a_{1} a1 的迭代更新解析解为 a 1 n e w , c l i p p e d = { H i f a 1 n e w > = H a 1 n e w i f L < a 1 n e w < H L i f a 1 n e w < = L a_{1}^{new,clipped} = \left\{\begin{matrix}H if a_{1}^{new} >=H\\ a_{1}^{new} if L < a_{1}^{new} |
根据约束，
a
1
,
a
2
a_{1},a_{2}
a1,a2既要在矩形方框上，也要在直线上，因此【本文地址】
今日新闻 |
推荐新闻 |