模式识别支持向量机导引

《模式识别支持向量机导引》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、模式识别支持向量机导引3线性支持向量机3.1数据可分情况我们从最简单的情况开始：用线性机器训练可分数据（正如我们将看到的，对一般情况的分析－非线性机器训练不可分数据－导致了一个非常熟悉的二次规划问题）。归类训练数d{x,y},i=1,L,l,y∈{−1,1},x∈R据iiii。假定我们有一些超平面能够分开正b/ω负样本（一个分类超平面）。在超平面上的点满足ωx+b=0，其中ω是超平面的法线，ω是超平面到原点的垂直距离，是ω的Euclidean范数。令d+(d−)为分类超平面到最近正（负）样本的最短

2、距离。定义一个分类超平面的间隔为d++d−。对于线性可分情况，支持向量机算法就是简单的寻找最大间隔的分类超平面。如下面的公式所述：假定所有的训练数据满足下面的约束条件：xbω+≥+1fory=+1ii(10)xbω+≤−1fory=−1ii(11)上面两式可以合并为一个不等式集合：yx(ω+−≥∀b)10iii（12）现在考虑使得方程（10）成立的点（要求存在这样一个点就等价于为ω和b选择了一个Hxb1:ω+=−1尺度）。这些点位于超平面i上，具有法线ω和垂直距离（距离原点）1/−bωdd==1/

3、ω2/ω。因此+−，间隔为。注意超平面H1和H2是平行的（它们2ω有相同的法线）并且没有训练点落在它们中间。这样我们就可以通过最小化（受12式约束）找到一对具有最大间隔的超平面。图5线性可分超平面，支持向量用画圈点表示对于一个典型的二维情况，我们期望具有图5所示的形状的解。使得不等式（12）成立的那些点（也就是那些处于超平面H1,H2上的点）称为支持向量，并且去除这些点将改变所建立的解。它们在图5中用画圈的点表示。我们现在将转向问题的Lagrangian形式。这样做有两个原因。首先是约束式（12）

4、将被Lagrangian乘子本身替代，这样就使问题变的更见容易处理。第二个原因就是问题的这种变形使得训练数据仅仅以向量点积的形式出现（在实际的训练和测试算法中）。这个关键特性将允许我们把这个过程推广到非线性的情况（第4节）。α,1il=,,Lα我们引入正的Lagrange乘子i，每一个i都对应着一个不等式约束（12）。c≥0回忆具有约束形式为i的规则：将等式约束乘以正Lagrange乘子，然后从目标函数中减去形成了Lagrange函数。对于等式约束，Lagrange乘子是不受约束的。形成的Lagr

5、ange函数如下：ll12LyPi=−ω∑∑αωi()xi+b+αi2ii==11（13）LLαα≥0我们必须关于ω,b最小化P，并且同时要求P关于所有i的导数为零，都受i的C约束（我们称这个特殊的约束集合为1）。由于目标函数本身是凸的，所以这是一个凸二次规划问题，满足不等式的所有点也形成一个凸集（任何一个线性约束都定义了一个凸集，N个线性约束集合定义了N个凸集的交集，这个交集也是一个凸集）。这就意味着我们可以等LLα≥0价的求解下面的对偶问题：最大化D，受P关于ω,b的梯度为零和i的约束（我们称

6、C那个特殊的约束集合为2）。这个问题的对偶形式被称为Wolfe对偶（Fletcher，1987）。它LCLC具有属性：最小化P，受约束1，同最大化D，受约束2，具有相同的ω,b和α值。L由P关于ω,b的梯度为零得到条件：ωα=∑iiiyxi（14）∑αiiy=0i（15）因为上面两式在对偶公式中为等式约束，我们把其代入方程（13）中得到：1LD=−∑∑ααiiαjyyxxiji⋅jii2,j（16）注意我们给出的Lagrange函数的不同标记（P代表初始问题，D代表对偶问题）来强调LL这两个公式的

7、不同：P和D都是从同样的目标函数得到，但是具有不同的约束；解的求解LL是通过最小化P或者最大化D得到。加入我们令公式中的b=0，就等于要求超平面通过原点，约束（15）式就可以消去。也就是说自由度的数目减一，因此这对高维空间来说是一个有益的限制。αLα因此，训练支持向量就等价于关于i最大化D，受（15）式和i非负性的约束，解由α的那些点被称（14）式给出。注意：每一个训练点都对应一个Lagrange乘子i。在所有解α>0α=0中，对应i为支持向量，位于HH12或超平面上。所有其它训练点有i，并且要么

8、在H1或H2上（使得方程（12）的等式成立），要么在H1或H2的旁边（使得方程（12）的不等式严格成立）。对于这些机器来说，支持向量是训练集里面的关键元素。它们离决策边界最近。假如移除所有其他的训练点（或者移动一个位置，但是不要同H1或H2交叉），然后重复这样的训练，能建立同样的分类超平面。3.2Karush-Kuhn-Tucker条件Karush-Kuhn-Tucker（KKT）条件在约束优化理论和实践中起到了一个非常重要的作用。对于上述初始问题，KKT条件可以表述为（Fletc