03第三章非参数判别分类方法3.7.ppt

最大间隔准则 最大间隔准则 扩展的拉格朗日乘子理论 唯一解的充分必要条件 *中国矿业大学 计算机科学与技术学院 第三章 非参数判别分类方法 3.7 支持向量机 Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机(Support Vector Machine,简称SVM)。 在学习这种方法时，首先要弄清楚这种方法考虑问题的特点，这就要从线性可分的最简单情况讨论起，在没有弄懂其原理之前，不要急于学习线性不可分等较复杂的情况。 支持向量机在设计时，需要用到条件极值问题的求解，因此需用拉格朗日乘子理论，要用到以不等式作为必须满足的条件，此时我们只要了解拉格朗日理论的有关结论就行。 3.7.1 线性可分条件下的 支持向量机最优分界面 SVM的思路 隔离带 支持向量 最大间隔准则 最优分类面示意图 训练样本集表示成{ xi,yi },i=1,…,N,其中xi为d维向量，也即特征向量，而yi∈{-1，+1}，即用yi是+1或-1表示其类别。 并且令 对在H1与H2平面上的点，上两式取等号。上两式也可合并成 对于分界面H表示成： H1平面到坐标原点的距离为： H1到H2的间隔为： H2平面到坐标原点的距离为： 因此欲达到Vapnik提出的使间隔最大的准则，则应使 最小。 其约束条件为： 按这个理论构造拉格朗日函数的原则为：目标函数减去用拉格朗日乘子(乘子值必须不小于0)与约束条件函数的乘积。 最大间隔准则的问题可写成： KKT条件：目标函数是二次函数，而约束条件为线性函数，按拉格朗日理论该问题存在唯一解。 目标函数： (3.7-1) 只有满足yi(WTXi+W0)-1=0 条件的点，其拉格朗日乘子才可能不为零；而对满足yi(WTXi+W0)-10的样本数据来说，其拉格朗日乘子必须为零。 显然只有部分(经常是少量)的样本数据的ai不为零，而线性分界面的权向量W则是这些ai不为零的样本数据的线性组合，ai不为零的样本数据也因而被称为支持向量。 (3.7-2) (3.7-3) (3.7-4) (3.7-5) (3.7-6) 最佳的权向量 最佳的权向量W就是这些支持向量数据的线性求和。 (3.7-7) 求解 为了求出最佳的ai，拉格朗日理论中引入一种对偶函数，与L(W,a)式相对偶的函数的构造方法是：对L(W,a)分别求它对W及w0的偏微分，并置为零，然后再代回到L(W,a)式中，从而得到： 通过求L(W,a)式的极大值来求解。 (3.7-8) 拉格朗日理论证明：满足上述条件(3.7-2)到(3.7-6)时，找(3.7-8)式极大值的解就是(3.7-1)式的条件极小值，因此由(3.7-8)可求得各个最佳值 ，代入(3.7-7)即可得到 ，在W确定之后w0值也可利用(3.7-5)对某个 的数据求出。 对(3.7-8)式的来源不要求弄懂，只需知道，它的极大值解与(3.7-1)式的极小值解是一致的就行了。 3.7.2 线性不可分条件下的 广义最优线性分界面 对于线性不可分的情况下，如果仍要使用线性分界面，则必然有部分训练样本向量被错分。 保留求最宽隔离带的框架，但允许有些数据能进入隔离带，甚至到对方的决策域中。但是对这部分数据的数量要严加控制。 为了实行控制，增加一种起缓冲作用的量，ξi (ξi 0)称为缓冲量， 此时 (3.7-9) (3.7-10) 线性不可分条件下的广义最优线性分界面 线性不可分条件下的广义最优线性分界面 目标函数可写为 拉格朗日函数 (3.7-11) 比较线性可分条件下的拉格朗日函数 (3.7-1) 由于(3.7-11)仍满足KKT条件，因此唯一解的充要条件是 线性不可分条件下的广义最优线性分界面 (3.7-12) (3.7-13) (3.7-14) (3.7-15) (3.7-16) (3.7-17) (3.7-18) (3.7-19) 问题：思考一下，这一堆式子与线性可分条件下的解相比，哪些式子是增加的？哪些式子略有改变？ (3.7-2) (3.7-3) (3.7-4) (3.7-5) (3.7-6) 线性不可分 线性可分 (3.7-12) (3.7-13) (3.7-14) (3.7-15) (3.7-16) (3.7-17) (3.7-18) (3.7-19) 答： (3.7-14)是增加的，它对ai的值有了限制。(3.7-17)是增加的，(3.7-19)是增加的，它们都与ξi有关。(3.7-12)，(3.7-18)及(3.7-13)没有明显变化。 很有意思