第2章线性判别函数优秀课件.ppt

《第2章线性判别函数优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章线性判别函数优秀课件.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章线性判别函数第1页，本讲稿共92页2.1 2.1 线性判别函数和决策面线性判别函数和决策面 模式的表示模式的表示 在分类识别方法中，首先应该把代表事物的在分类识别方法中，首先应该把代表事物的那些那些特征特征抽取出来，构成代表这个模式的抽取出来，构成代表这个模式的特征特征向量向量。现在假定已经抽取到模式的若干特征：现在假定已经抽取到模式的若干特征：如果这如果这 个特征能够较好地描述原始的待识个特征能够较好地描述原始的待识别的事物，则可以用别的事物，则可以用 维空间的一个列向量来维空间的一个列向量来代表：代表：第2页，本讲稿共92页1.问题与解决思路问题与解决思路问题：问题：设有由设有由N个

2、待分类的个待分类的两类别两类别模式组成的一个模式组成的一个样本集，样本集，如何实现对样本集中的两类样本分类？如何实现对样本集中的两类样本分类？第3页，本讲稿共92页在一般情况下样本在特征空间的分布情况：在一般情况下样本在特征空间的分布情况：（二维两类别模式的例子）第4页，本讲稿共92页二维三类别模式的例子第5页，本讲稿共92页可以看出可以看出:不同类别的典型样本在特征空间中明显处于不同不同类别的典型样本在特征空间中明显处于不同的区域。的区域。表明表明:由于相同类别的模式具有由于相同类别的模式具有相似或相近的特征相似或相近的特征，因而，因而一类模式在特征空间中的某一区域分布，而另一一类模式在特征

3、空间中的某一区域分布，而另一类则在另外区域分布。类则在另外区域分布。第6页，本讲稿共92页 我们可以得到启发我们可以得到启发:用用已知类别的模式样本已知类别的模式样本产生一个代数表示产生一个代数表示的分界面的分界面 ，将特征空间分成两个互不，将特征空间分成两个互不重叠的区域，使不同类别的模式样本位于不同重叠的区域，使不同类别的模式样本位于不同的区域，再用的区域，再用 作为判别函数，对待作为判别函数，对待识别的模式进行分类。识别的模式进行分类。在特征空间可看作一个决策面。在特征空间可看作一个决策面。第7页，本讲稿共92页归纳解决问题的思路归纳解决问题的思路:(1)分类问题分类问题 特征空间的分布

4、特征空间的分布 寻找寻找 子区域的分界面子区域的分界面 确定判别函数确定判别函数(2)待识别模式待识别模式 判别函数判别函数 分类分类解决方法？解决方法？代入代入 判别判别第8页，本讲稿共92页 判别函数判别函数 可以有多种形式，哪种形式可以有多种形式，哪种形式最简单最简单呢？呢？线性函数线性函数 在二维空间是一条直线；在三维空间是一个在二维空间是一条直线；在三维空间是一个平面；在高维空间也是一个平面，由于是非平面；在高维空间也是一个平面，由于是非直观的，称为直观的，称为超平面超平面。第9页，本讲稿共92页 线性判别函数是所有模式特征的线性组合。线性判别函数是所有模式特征的线性组合。或或 式中

5、式中 是特征的系数，称为权，是特征的系数，称为权，称为阈值权。称为阈值权。用什么方法来确定用什么方法来确定 呢？呢？第10页，本讲稿共92页2.线性判别函数的确定方法线性判别函数的确定方法设有已知类别的两类别样本集，分布如下：设有已知类别的两类别样本集，分布如下：第11页，本讲稿共92页线性判别函数可以写成：线性判别函数可以写成：参数参数 决定了决定了 的方向和位置的方向和位置第12页，本讲稿共92页如何根据已知样本确定如何根据已知样本确定？由于要用由于要用 对两类样本在特征空间正确划对两类样本在特征空间正确划分两类模式的区域，我们可以假定一个规则：分两类模式的区域，我们可以假定一个规则：当样

6、本为一个类别时，当样本为一个类别时，使使 当样本为另一个类别时，使当样本为另一个类别时，使 第13页，本讲稿共92页 对全部样本都按这个规则来做，不满足时，对全部样本都按这个规则来做，不满足时，调整调整 ，最终可以找到一个，最终可以找到一个 ，使全，使全部样本都满足这个规则。部样本都满足这个规则。这个过程称为这个过程称为训练学习训练学习，已知类别的样本称，已知类别的样本称为为训练样本训练样本。用训练学习的方法确定线性判别函数。用训练学习的方法确定线性判别函数。如何训练学习？如何训练学习？第14页，本讲稿共92页3.线性判别函数的一般表示线性判别函数的一般表示 对于对于n维模式向量维模式向量 ，

7、其线性，其线性判别函数是所有模式特征的线性组合，即判别函数是所有模式特征的线性组合，即 可以写成可以写成其中其中，称为权向量。称为权向量。第15页，本讲稿共92页4.在向量空间的几何表示在向量空间的几何表示 取取 作为决策面。作为决策面。如果两个向量如果两个向量 和和 都在决策面上，则有：都在决策面上，则有：或写成或写成 由于由于 和和 是决策面上的任意两点，所以是决策面上的任意两点，所以 也是在决策面上的任意向量。也是在决策面上的任意向量。表明了什么？表明了什么？第16页，本讲稿共92页 两个两个n维向量相互正交的充要条件是两维向量相互正交的充要条件是两向量的内积为零。即向量的内积为零。即

8、所以所以,表明表明:权向量和决策面上的任一向量正交。所以权向量的权向量和决策面上的任一向量正交。所以权向量的方向就是决策面的法线方向。方向就是决策面的法线方向。第17页，本讲稿共92页 在两维模式下，决策面在两维模式下，决策面 把模式空间分成两个子空间，分把模式空间分成两个子空间，分别是对别是对 类的决策域类的决策域 和对和对 类的决策域类的决策域 。如果我们规定：如果我们规定：在在 中，中，；在；在 中，中，决策面的，决策面的法向量的方向指向法向量的方向指向 。第18页，本讲稿共92页 第19页，本讲稿共92页我们可以把向量我们可以把向量 表示为：表示为：待求的距离待求的距离 决策面决策面

9、上一点上一点 与与 有什么样的关系有什么样的关系?第20页，本讲稿共92页 则有：则有：或或判别函数值判别函数值 是是 到决策面的距离的度量。到决策面的距离的度量。第21页，本讲稿共92页同理，可以得出：同理，可以得出：从原点到决策面从原点到决策面 的距离为的距离为 。如果如果 ，原点在，原点在 的正面；的正面；如果如果 ，原点在，原点在 的反面；的反面；如果如果 ，判别函数有齐次形式，判别函数有齐次形式 决策面通过原点。决策面通过原点。第22页，本讲稿共92页二类模式的线性分类器的决策法则是：二类模式的线性分类器的决策法则是：如果如果 则决策则决策 ，即把，即把 归到归到 类；类；如果如果

10、则决策则决策 ，即把，即把 归到归到 类；类；对于线性判别函数，关键的问题是求对于线性判别函数，关键的问题是求如何求？如何求？第23页，本讲稿共92页2.2 2.2 感知准则函数和梯度下降法感知准则函数和梯度下降法1.感知准则函数感知准则函数 由前面介绍的知识，我们知道，由前面介绍的知识，我们知道，对于一组两类别样本集：对于一组两类别样本集：我们可以设线性判别函数为：我们可以设线性判别函数为：决策面方程为：决策面方程为：即即 第24页，本讲稿共92页 求得权向量求得权向量 ，就可确定决策面方程。，就可确定决策面方程。由数学知识，知由数学知识，知 的齐次形式比较容易。的齐次形式比较容易。能否将能

11、否将 变换成齐次形式呢？变换成齐次形式呢？令令 ，则，则，n维维X空间空间 （n+1）维）维Y空间空间 Y称为增广模式向量，称为增广模式向量，A称为增广权向量称为增广权向量 第25页，本讲稿共92页 经过这样的变换，求解的问题就变为：经过这样的变换，求解的问题就变为：设有一组两类模式的增广模式向量样本集，设有一组两类模式的增广模式向量样本集，利用这些样本确定一个线性判别函数利用这些样本确定一个线性判别函数的权向量的权向量 ，使，使 能够对能够对 正确分类。正确分类。第26页，本讲稿共92页训练规则为：训练规则为：对于属于对于属于 类的所有样本，有类的所有样本，有:对于属于对于属于 类的所有样本

12、，有类的所有样本，有:注意到注意到 和和能否使能否使？在属于在属于 类的样本前加上负号，则类的样本前加上负号，则第27页，本讲稿共92页这样处理后，问题变为：这样处理后，问题变为：求使对于所有训练样本都满足：求使对于所有训练样本都满足：，的权向量的权向量如何求如何求？是一个线性不等式组，而是一个线性不等式组，而 是是 维的，样本数量为维的，样本数量为 ，一般，一般 比比 大的多，大的多，这样，这样，的解不唯一。的解不唯一。第28页，本讲稿共92页 为了解线性不等式组为了解线性不等式组 ，需要构造一个准则，需要构造一个准则函数，并希望构造的准则函数有极值的形式。函数，并希望构造的准则函数有极值的

13、形式。是由于使用权向量是由于使用权向量 而被误分类的样本集合。而被误分类的样本集合。当一个样本当一个样本 被误分类时，就有被误分类时，就有 ,所以所以 。仅当。仅当 时，时，达到最小值。达到最小值。第29页，本讲稿共92页我们称我们称为为感知准则函数感知准则函数。有了准则函数之后，我们就可以用最优化方法寻找有了准则函数之后，我们就可以用最优化方法寻找使准则函数达到极小值的解权向量使准则函数达到极小值的解权向量 。如何求如何求？第30页，本讲稿共92页2.梯度下降法v 梯度的定义梯度的定义 梯度是函数梯度是函数 的一阶偏导数组成的向量的一阶偏导数组成的向量,记为记为v 二元函数的等值线二元函数的

14、等值线 定义定义:坐标面上函数相等的各点的连线叫等值线坐标面上函数相等的各点的连线叫等值线,也也称等高线。称等高线。第31页，本讲稿共92页 函数函数 为不同值时，得到一系列的等值线，构成为不同值时，得到一系列的等值线，构成 的的等值线族等值线族 。在极值处的等值线在极值处的等值线聚成一点，并位于等值聚成一点，并位于等值线的中心，当该中心为线的中心，当该中心为极小值时，离开它越远，极小值时，离开它越远，值越大，反之，若值越大，反之，若该中心为极大值时，离开该中心为极大值时，离开它越远，它越远，的值越小。的值越小。第32页，本讲稿共92页v 梯度方向梯度方向 由梯度的定义知，由梯度的定义知，梯度

15、的方向就是函数的法线的方向。梯度的方向就是函数的法线的方向。第33页，本讲稿共92页 梯度方向的性质梯度方向的性质:沿梯度方向，函数值增长最快，为最速沿梯度方向，函数值增长最快，为最速上升方向；上升方向；沿负梯度方向，函数值下降最快，为最沿负梯度方向，函数值下降最快，为最速下降方向。速下降方向。第34页，本讲稿共92页梯度下降法的基本思想：梯度下降法的基本思想：函数函数 在某点在某点 的梯度的梯度 是一个向量，它的方向是一个向量，它的方向与过点与过点 的等量面的等量面 的法线方向重合，指向的法线方向重合，指向 增加的一方，是准则函数变化率最大的方向。反之，负梯度的增加的一方，是准则函数变化率最

16、大的方向。反之，负梯度的方向则是函数方向则是函数 减少的最快的方向。所以在求准则函数减少的最快的方向。所以在求准则函数 的极小值时，的极小值时，沿负梯度方向搜索有可能最快的找到最小值。沿负梯度方向搜索有可能最快的找到最小值。第35页，本讲稿共92页梯度下降法的实现：梯度下降法的实现：先任意选择一个初始的权向量先任意选择一个初始的权向量 ，计算，计算 上的梯上的梯度度 ，从，从 出发在最陡方向（即负梯度方向）出发在最陡方向（即负梯度方向）上移动一个距离以得到下一个权向量上移动一个距离以得到下一个权向量 。可采用下面的迭代方法从可采用下面的迭代方法从 推出推出 。比例因子，叫做步长或增量比例因子，

17、叫做步长或增量 因为因为 的第的第 个梯度分量是个梯度分量是 。第36页，本讲稿共92页 所以，可得到梯度下降法的迭代公式：所以，可得到梯度下降法的迭代公式：当第当第 步迭代用权向量步迭代用权向量 来分类时被误分类的样本集合来分类时被误分类的样本集合 这种寻找解权向量的梯度下降法简述如下这种寻找解权向量的梯度下降法简述如下:把第把第 次的权向量加上被误分类的样本的和与某个常次的权向量加上被误分类的样本的和与某个常数数 的乘积，就得到第的乘积，就得到第 次的权向量。次的权向量。第37页，本讲稿共92页 优点：优点：只要二类样本线性可分的，这个算只要二类样本线性可分的，这个算法总可收敛。法总可收敛

18、。缺点：缺点：每次迭代必须遍历全部样本，才能每次迭代必须遍历全部样本，才能得到当前权向量得到当前权向量 下的误分样本集下的误分样本集 ，从而再对从而再对 的值进行修正。的值进行修正。第38页，本讲稿共92页用用训练样本集训练样本集求线性决策面方法要点：求线性决策面方法要点：v求线性决策面函数v转化成齐次形式v感知准则函数v梯度下降法v迭代公式第39页，本讲稿共92页2.3 固定增量算法及其收敛性 针对梯度下降法的缺点，作以下两点改变，得到针对梯度下降法的缺点，作以下两点改变，得到固定增量算法：固定增量算法：（1）把全部样本看作是一个序列，每当前一步迭）把全部样本看作是一个序列，每当前一步迭代的

19、权向量把某个样本错误分类时，就对这一个权代的权向量把某个样本错误分类时，就对这一个权向量作一次修正，而不是等当前权向量向量作一次修正，而不是等当前权向量 对全部样对全部样本计算后再找出错分类样本集本计算后再找出错分类样本集 去进行修改。去进行修改。（2）考虑每次迭代时）考虑每次迭代时 保持不变。保持不变。第40页，本讲稿共92页二类模式下用固定增量法求解权向量：二类模式下用固定增量法求解权向量：设设已已知知二二类类模模式式的的样样本本集集 和和 ，这这些些样样本本都都已已被被变变成成增增广广模模式式向向量量的的形形式式，要要求求用用固固定定增增量量的的方方法法决决定定一一个个超超平平面面 ，使

20、使它它能能正正确确划划分分样本集样本集 和和 。开开始始时时可可以以任任意意假假定定 和和 位位于于决决策策面面的的哪一边。同样可以任意选择广义向量哪一边。同样可以任意选择广义向量 的初始值的初始值 。然后把训练集然后把训练集 和和 中的增广模式向量中的增广模式向量 依次取出，计算依次取出，计算 与与 的内积的内积 。第41页，本讲稿共92页假定假定 在在 的正面，的正面，在它的反面在它的反面权向量权向量 用以下规则调整：用以下规则调整：v如果如果 ，而，而 ，则用，则用 代替代替 ；v如果如果 ，而，而 ，则用，则用 代替代替 ；v如果如果 ，而，而 ，则，则 保持不变。保持不变。v如果如果

21、 ，而，而 ，则，则 保持不变。保持不变。把属于把属于 和和 的全部模式都用上述方法处理一遍，的全部模式都用上述方法处理一遍，称为一次迭代。称为一次迭代。这个算法重复执行，直至权向量这个算法重复执行，直至权向量 不再变化，则不再变化，则 ，即求得解权向量，即求得解权向量 。第42页，本讲稿共92页 2.7 Fisher 线性判别函数 在应用统计方法进行模式识别时，许多问题在应用统计方法进行模式识别时，许多问题涉及维数，在低维空间行得通的方法，往往在高涉及维数，在低维空间行得通的方法，往往在高维空间行不通。因此，发展了一些降低特征空间维空间行不通。因此，发展了一些降低特征空间维数的方法，维数的方

22、法，Fisher线性判别函数就是其中之一。线性判别函数就是其中之一。在介绍在介绍Fisher线性判别函数之前，先补充介绍要用线性判别函数之前，先补充介绍要用到的到的Lagrange乘子法乘子法一种带等式约束的函数极值一种带等式约束的函数极值求解方法。求解方法。第43页，本讲稿共92页Lagrange乘子法乘子法一一.等式约束最优化问题等式约束最优化问题二二.Lagrange乘子的概念乘子的概念 第44页，本讲稿共92页极值点必须满足两个条件极值点必须满足两个条件:1.目标函数目标函数 沿约束曲线沿约束曲线 的切线方向的切线方向 的方向导数的方向导数 ,即即2.约束函数约束函数 沿约束曲线沿约束

23、曲线 的切线的切线 方向方向 的方向导数的方向导数 ,即即第45页，本讲稿共92页比较上述两式可以得到比较上述两式可以得到:令令可得可得:为待定系数为待定系数,解这个联立解这个联立 方程可以求出方程可以求出 ,为问题的极小点，为问题的极小点，极小值为极小值为 。第46页，本讲稿共92页 设设 对各变量分别求偏导数并令其等于对各变量分别求偏导数并令其等于0,可得到：可得到：实际上是求函数实际上是求函数 的极值的极值这个形式与前述形式一样。这个形式与前述形式一样。第47页，本讲稿共92页 三、二维情况下的三、二维情况下的Lagrange乘子法乘子法 对于等式约束优化函数对于等式约束优化函数 构造构

24、造Lagrange函数：函数：使使 达到极小值，达到极小值，称为称为Lagrange乘子。乘子。用用Lagrange乘子法可以将等式约束优化问题转化为无约束优化问乘子法可以将等式约束优化问题转化为无约束优化问题。题。第48页，本讲稿共92页四、对于四、对于 维的情况维的情况 数学模型数学模型 首先由情况引入首先由情况引入Lagrange系数系数 ，构造，构造Lagrange函数：函数：第49页，本讲稿共92页 Fisher方法的基本思想：方法的基本思想：把把 维空间的所有模式投影到一条过原点的直线上，就可以把维维空间的所有模式投影到一条过原点的直线上，就可以把维数压缩到数压缩到1。过原点的直线

25、有无数条，投影到那条直线好呢？过原点的直线有无数条，投影到那条直线好呢？x1x2第50页，本讲稿共92页 我们的目标就是找到这样一条直线，使得模我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。式样本在这条直线上的投影最有利于分类。设给定两类模式样本集，设给定两类模式样本集，和和 ，它们各有它们各有 和和 个个 维样本。设维样本。设 为这条直线正方向的单位为这条直线正方向的单位向量，向量，。将样本集中的样本向直线投影，。将样本集中的样本向直线投影，相应地得到集合相应地得到集合 和和 。每个。每个 就是就是 在在单位向量单位向量 上的投影。上的投影。有：有：这样，就得到

26、了一个一维样本集合，样本数量为这样，就得到了一个一维样本集合，样本数量为 第51页，本讲稿共92页下面要解决的问题是什么？下面要解决的问题是什么？确定最好的投影方向确定最好的投影方向 的的 为了找到最好的为了找到最好的 ，需要建立一个准则函数，需要建立一个准则函数，这个准则函数要能反映不同类别模式在这条直这个准则函数要能反映不同类别模式在这条直线上投影分离程度的好坏。线上投影分离程度的好坏。在确定建立准则函数之前，先介绍几个有关参在确定建立准则函数之前，先介绍几个有关参数。数。第52页，本讲稿共92页1.在在d维维X空间空间（1）各类样本的均值向量）各类样本的均值向量（2）样本类内离散度，总类

27、内离散度）样本类内离散度，总类内离散度 第53页，本讲稿共92页（3）样本类间离散度）样本类间离散度第54页，本讲稿共92页2.在一维在一维Y空间空间（1）各类样本的均值）各类样本的均值（2）样本类内离散度，总类内离散度）样本类内离散度，总类内离散度 第55页，本讲稿共92页 我们希望投影后，在一维我们希望投影后，在一维Y空间两类样本尽可空间两类样本尽可能分得开一些，即能分得开一些，即 （1）两类样本离得越远越好）两类样本离得越远越好,也就是，两类均值也就是，两类均值之差之差 越大越好，越大越好，（2）各类样本内部越密集越好，也就是，类内）各类样本内部越密集越好，也就是，类内离散度越小越好，离

28、散度越小越好，越小越好。越小越好。因此，可以构造准则函数为：因此，可以构造准则函数为：第56页，本讲稿共92页 我们的目标是使我们的目标是使 尽可能大的尽可能大的 作为作为投影方向，但在上式中不显含投影方向，但在上式中不显含 ，因此，要，因此，要将将 变成变成 的显函数。的显函数。第57页，本讲稿共92页准则函数的分子项：准则函数的分子项：第58页，本讲稿共92页准则函数的分母项：准则函数的分母项：第59页，本讲稿共92页因此，准则函数因此，准则函数 可改写为：可改写为：(2.43)这就是这就是Rayleigh比，它有如下性质：比，它有如下性质：（1）是一个实数。是一个实数。（2）的极值与大小

29、无关，只与的极值与大小无关，只与 的方向有关。的方向有关。因此，因此，可以用可以用Lagrange乘数法求极值。乘数法求极值。由性质由性质(2)，可令式，可令式(2.43)分母为非零常数，即分母为非零常数，即第60页，本讲稿共92页构造构造Lagrange函数函数 极大值的条件为：极大值的条件为：即即 如果如果 非奇异，左乘非奇异，左乘 ，则有则有 解这个式子，就是求矩阵解这个式子，就是求矩阵 的本征值。的本征值。第61页，本讲稿共92页考虑到我们求解问题的特殊性（考虑到我们求解问题的特殊性（只确定方向只确定方向），），其中其中 是常数，所以是常数，所以 总是在总是在 的方向上。从而的方向上。

30、从而 所以所以略去比例因子略去比例因子 ，它不影响直线的方向，它不影响直线的方向，得：得：第62页，本讲稿共92页 这就是使准则函数这就是使准则函数 极大的解。极大的解。就是使就是使模式样本的投影在类间最分散，类内最集中的模式样本的投影在类间最分散，类内最集中的最优解。有了最优解。有了 后，得后，得 就可将各样本由维空间投影到一维空间，即直就可将各样本由维空间投影到一维空间，即直线上，变成一维样本，它们给出较好的分类线上，变成一维样本，它们给出较好的分类结果。结果。此类方法有一定的局限性：此类方法有一定的局限性：v只对准则函数最优；只对准则函数最优；v没有利用样本的分布信息，错误概率不能达到最

31、没有利用样本的分布信息，错误概率不能达到最小。小。第63页，本讲稿共92页2.8 支持向量机 Support Vector Machine SVM 回顾：用线性判别函数方法解决分类问题的方法回顾：用线性判别函数方法解决分类问题的方法1.思路思路（1）训练样本集）训练样本集 特征空间划分特征空间划分 决策面决策面 线性判别函数线性判别函数（2）待识别模式）待识别模式 判别判别2.问题核心：问题核心：求线性判别函数的权向量求线性判别函数的权向量3.求解方法：感知准则函数，梯度下降法，固定增量法求解方法：感知准则函数，梯度下降法，固定增量法求得权向量求得权向量=确定了特征空间的两类分界面（决策面）确

32、定了特征空间的两类分界面（决策面）第64页，本讲稿共92页一一.最优分界面最优分界面 从线性判别函数的讨论中，我们已经知道，对从线性判别函数的讨论中，我们已经知道，对于线性可分的两类样本，总可以找到一个分界于线性可分的两类样本，总可以找到一个分界面，将两类样本正确分类，而且，这样的分界面，将两类样本正确分类，而且，这样的分界面不是唯一的。面不是唯一的。第65页，本讲稿共92页H1和H2都可以将两类训练样本正确分类，但是，对于训练样本以外的样本，以哪个作为分界面，分类效果更好呢？H1H2第66页，本讲稿共92页因为：因为：H2产生错误分类的可能性更小。产生错误分类的可能性更小。这就提出了分类器设

33、计中一个很重要的问题：这就提出了分类器设计中一个很重要的问题：分类器的通用性分类器的通用性，也称，也称分类器的推广能力分类器的推广能力即：即：用训练样本设计的分类器，对训练样本以外的样用训练样本设计的分类器，对训练样本以外的样本能够正确分类的能力。本能够正确分类的能力。哪一个分界面可以使分类器具有最好的通用性？哪一个分界面可以使分类器具有最好的通用性？第67页，本讲稿共92页 H1是两类各自最近样本距离相同的分界面，H2也是两类各自最近样本距离相同的分界面.H1H2第68页，本讲稿共92页最优分界面：最优分界面：在样本空间中，使两类样本正确分类，而且两类样本在样本空间中，使两类样本正确分类，而

34、且两类样本分开的间隔最大的分界面为最优分界面。分开的间隔最大的分界面为最优分界面。最优分界面可以使分类器具有最好的通用性最优分界面可以使分类器具有最好的通用性（推广能力）。（推广能力）。如何求最优分界面？如何求最优分界面？第69页，本讲稿共92页 二二.支持向量支持向量对于给定的线性可分训练样本集，对于给定的线性可分训练样本集，如果如果 则则 如果如果 则则 可以得到分界面。可以得到分界面。由于两类样本之间总有间隔存在，所以可以有：由于两类样本之间总有间隔存在，所以可以有：如果如果 则则 如果如果 则则 其中其中 是一个正数。是一个正数。第70页，本讲稿共92页为了方便，训练样本集的样本用为了

35、方便，训练样本集的样本用二元对二元对来表示：来表示：其中其中 和和 分别是样本模式向量分别是样本模式向量和它的相应的类别表示，和它的相应的类别表示，假定当假定当 时，时，。而当。而当 时时 。设给定的有穷训练样本集可以被设给定的有穷训练样本集可以被超平面超平面 正确分开。正确分开。使每类离开分界超平面最近的样本向量与超平面之使每类离开分界超平面最近的样本向量与超平面之间的距离最大，位于间隔中间的超平面是最优的。间的距离最大，位于间隔中间的超平面是最优的。第71页，本讲稿共92页我们已经知道，在模式向量空间，任何一个我们已经知道，在模式向量空间，任何一个模式向量到决策面的距离为：模式向量到决策面

36、的距离为：对于决策面方程对于决策面方程 ，和和 并不是唯一的并不是唯一的。第72页，本讲稿共92页设想：可以将设想：可以将 和和 进行某种比例缩放，总可以进行某种比例缩放，总可以找到一个找到一个 和和 ，使，使 到决策面的距离最小，到决策面的距离最小，为为 ，这样，两类模式的分类规则可以写成：这样，两类模式的分类规则可以写成：合并这两个式子，写成：合并这两个式子，写成：第73页，本讲稿共92页这时两类模式间隔的距离为：这时两类模式间隔的距离为：为了使间隔最大，应当使为了使间隔最大，应当使 最小，等价于最小，等价于使使 最小，最小，所以，使所以，使 最小，且满足最小，且满足的分界面就是最优分界面

37、，距离最优分界面的分界面就是最优分界面，距离最优分界面最近的模式向量就是最近的模式向量就是支持向量支持向量。可以看出，寻找支持向量，就是寻找最优分可以看出，寻找支持向量，就是寻找最优分界面。界面。第74页，本讲稿共92页 设目标函数为：设目标函数为：将寻找最优分界面问题转化为有约束优化问题：将寻找最优分界面问题转化为有约束优化问题：如何求解？如何求解？第75页，本讲稿共92页 构造构造Lagrange函数：函数：其中其中 为为Lagrange乘子，乘子，第76页，本讲稿共92页 达到极值的必要条件为：达到极值的必要条件为：(1),得得(2),得得 而对于最优分界面，解而对于最优分界面，解 必须

38、满足：必须满足：(1)(2)最优分界面的解权向量是训练样本集中模式向量的线性组合最优分界面的解权向量是训练样本集中模式向量的线性组合.第77页，本讲稿共92页 对于约束条件对于约束条件,等号在支持向量下才成立，也就是等号在支持向量下才成立，也就是说，只有支持向量可以在说，只有支持向量可以在 的展开中具有的展开中具有非零系非零系数数 ，因此有，因此有 其中其中 是支持向量集。是支持向量集。如何知道哪些样本是支持向量呢如何知道哪些样本是支持向量呢?第78页，本讲稿共92页求最优分类超平面问题：求最优分类超平面问题：等价转换对偶问题第79页，本讲稿共92页 这是一个二次函数优化问题，存在唯一解，解中

39、这是一个二次函数优化问题，存在唯一解，解中不为零的不为零的 所对应的样本就是所对应的样本就是支持向量支持向量。求得支持向量后，可求得权向量求得支持向量后，可求得权向量 和和 式中式中 表示属于第一类的支持向量，表示属于第一类的支持向量，而而 表示属于第二类的支持向量。表示属于第二类的支持向量。这样，由这样，由 和和 就确定了最优超平面。就确定了最优超平面。第80页，本讲稿共92页 举例：举例：设有四个两类样本，设有四个两类样本，类有两个样本：类有两个样本：类有两个样本：类有两个样本：求最优分界面。求最优分界面。第81页，本讲稿共92页对偶问题：对偶问题：i=1，j=1，2，3，4，i=2，j=

40、2，j=3，j=4，i=3，j=2，j=3，j=4，i=4，j=4，第82页，本讲稿共92页求求 的极值的极值。令令 矛盾是凹凸函数原因第83页，本讲稿共92页利用利用 支持向量为：支持向量为：不满足要求第84页，本讲稿共92页利用利用 确定确定最优分界面：最优分界面：第85页，本讲稿共92页三三.支持向量机支持向量机1.广义线性判别函数广义线性判别函数x1x2第86页，本讲稿共92页 对图示的两类分布，可以用一个对图示的两类分布，可以用一个4次多项式决策函数次多项式决策函数对其分类。对其分类。这是一个两维函数这是一个两维函数第87页，本讲稿共92页 做特征空间变换，令做特征空间变换，令 则有

41、则有第88页，本讲稿共92页 可将一个在低维空间很复杂的决策面，变换成一个可将一个在低维空间很复杂的决策面，变换成一个高维空间的线性函数：高维空间的线性函数：称之为称之为广义线性判别函数广义线性判别函数。即。即 在变换后的空间中在变换后的空间中是线性的，在原空间是非线性的。是线性的，在原空间是非线性的。一般来说，对于任意高次判别函数一般来说，对于任意高次判别函数 ，都可以通过适当，都可以通过适当的变换变成广义线性判别函数的变换变成广义线性判别函数 ，利用线性判别函数的简，利用线性判别函数的简单性来解决复杂问题。单性来解决复杂问题。但是，这种变换带来一个很严重的问题：但是，这种变换带来一个很严重

42、的问题：维数大大增加，例中维数大大增加，例中2维变成维变成15维维 维数增加导致所需样本数呈指数增加。维数增加导致所需样本数呈指数增加。第89页，本讲稿共92页2.支持向量机支持向量机 在求最优分界面时在求最优分界面时,最优分界面只与支持最优分界面只与支持向量有关向量有关,优化函数优化函数 只需要计算训练样本的内积只需要计算训练样本的内积,而映射到高维而映射到高维空间中也只需内积运算。根据泛函理论，空间中也只需内积运算。根据泛函理论，只要一种核函数只要一种核函数 (kernel)满足满足Mercer条件，它就对应某个变换空间中的条件，它就对应某个变换空间中的内积。内积。第90页，本讲稿共92页

43、 因此，只要找到适当的核函数，就可以实现某个线性变因此，只要找到适当的核函数，就可以实现某个线性变换后的线性分类。换后的线性分类。寻优函数为：寻优函数为：分类函数为：分类函数为：支持向量机的基本思想：支持向量机的基本思想：通过非线性变换将输入空间变换到一个高维空间，通过非线性变换将输入空间变换到一个高维空间，然后在这个变换空间中求最优分界面，实现分类。然后在这个变换空间中求最优分界面，实现分类。这种非线性变换是通过定义适当的内积函数，用内这种非线性变换是通过定义适当的内积函数，用内积运算实现的。（不必真的进行这种非线性变换）积运算实现的。（不必真的进行这种非线性变换）支持向量机第91页，本讲稿共92页支持向量机方法的优势是什么？支持向量机方法的优势是什么？第92页，本讲稿共92页