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

1、v线性判别函数和决策面线性判别函数和决策面v感知准则函数和梯度下降法感知准则函数和梯度下降法v固定增量法及其收敛性固定增量法及其收敛性v最小平方误差准则函数最小平方误差准则函数v多类情况下的线性判别函数多类情况下的线性判别函数v分段线性判别函数分段线性判别函数vFisher 线性判别函数线性判别函数v支持向量机支持向量机第二章第二章 线性判别函数线性判别函数 模式的表示模式的表示 在分类识别方法中，首先应该把代表事物的在分类识别方法中，首先应该把代表事物的那些那些特征特征抽取出来，构成代表这个模式的抽取出来，构成代表这个模式的特征特征向量向量。现在假定已经抽取到模式的若干特征：现在假定已经抽取

2、到模式的若干特征：如果这如果这 个特征能够较好地描述原始的待识个特征能够较好地描述原始的待识别的事物，则可以用别的事物，则可以用 维空间的一个列向量来维空间的一个列向量来代表：代表：1,2,(.,)TnXx xx12,.,nx xxnn1.问题与解决思路问题与解决思路问题：问题：设有由设有由N个待分类的个待分类的两类别两类别模式组成的一模式组成的一个样本集，个样本集，如何实现对样本集中的两类样本分类？如何实现对样本集中的两类样本分类？,21NXXX在一般情况下样本在特征空间的分布情况：在一般情况下样本在特征空间的分布情况：1x2x0（二维两类别模式的例子）（二维两类别模式的例子）二维三类别模式

3、的例子二维三类别模式的例子123边界2x1x可以看出可以看出:不同类别的典型样本在特征空间中明显处于不不同类别的典型样本在特征空间中明显处于不同的区域。同的区域。表明表明:由于相同类别的模式具有由于相同类别的模式具有相似或相近的特征相似或相近的特征，因而一类模式在特征空间中的某一区域分布，而因而一类模式在特征空间中的某一区域分布，而另一类则在另外区域分布。另一类则在另外区域分布。我们可以得到启发我们可以得到启发:用用已知类别的模式样本已知类别的模式样本产生一个代数表示产生一个代数表示的分界面的分界面 ，将特征空间分成两个互，将特征空间分成两个互不重叠的区域，使不同类别的模式样本位于不不重叠的区

4、域，使不同类别的模式样本位于不同的区域，再用同的区域，再用 作为判别函数，对作为判别函数，对待识别的模式进行分类。待识别的模式进行分类。在特征空间可看作一个决策面。在特征空间可看作一个决策面。0)(Xg0)(Xg0)(Xg归纳解决问题的思路归纳解决问题的思路:(1)分类问题分类问题 特征空间的分布特征空间的分布 寻找寻找 子区域的分界面子区域的分界面 确定判别函数确定判别函数(2)待识别模式待识别模式 判别函数判别函数 分类分类解决方法？解决方法？代入代入 判别判别 判别函数判别函数 可以有多种形式，哪种形式可以有多种形式，哪种形式最简单最简单呢？呢？线性函数线性函数 在二维空间是一条直线；在

5、三维空间是一个在二维空间是一条直线；在三维空间是一个平面；在高维空间也是一个平面，由于是非平面；在高维空间也是一个平面，由于是非直观的，称为直观的，称为超平面超平面。)(Xg 线性判别函数是所有模式特征的线性组合。线性判别函数是所有模式特征的线性组合。或或 式中式中 是特征的系数，称为权，是特征的系数，称为权，称为阈值权。称为阈值权。用什么方法来确定用什么方法来确定 呢？呢？1 1220().,nng Xw xw xw xw01()nkkkg Xw xwkw0w)(Xg2.线性判别函数的确定方法线性判别函数的确定方法设有已知类别的两类别样本集，分布如下：设有已知类别的两类别样本集，分布如下：1

6、x2x0线性判别函数可以写成：线性判别函数可以写成：参数参数 决定了决定了 的方向和位置的方向和位置02211)(wxwxwXg021,www)(Xg1x2x0如何根据已知样本确定如何根据已知样本确定？由于要用由于要用 对两类样本在特征空间正确划对两类样本在特征空间正确划分两类模式的区域，我们可以假定一个规则：分两类模式的区域，我们可以假定一个规则：当样本为一个类别时，当样本为一个类别时，使使 当样本为另一个类别时，使当样本为另一个类别时，使 021,www)(Xg0)(Xg0)(Xg 对全部样本都按这个规则来做，不满足时，对全部样本都按这个规则来做，不满足时，调整调整 ，最终可以找到一个，最

7、终可以找到一个 ，使全，使全部样本都满足这个规则。部样本都满足这个规则。这个过程称为这个过程称为训练学习训练学习，已知类别的样本称，已知类别的样本称为为训练样本训练样本。用训练学习的方法确定线性判别函数。用训练学习的方法确定线性判别函数。如何训练学习？如何训练学习？021,www)(Xg3.线性判别函数的一般表示线性判别函数的一般表示 对于对于n维模式向量维模式向量 ，其线性，其线性判别函数是所有模式特征的线性组合，即判别函数是所有模式特征的线性组合，即 可以写成可以写成其中其中，称为权向量。称为权向量。TnxxxX),(2102211)(wxwxwxwXgnn0)(wXWXgTTnwwwW)

8、,(214.在向量空间的几何表示在向量空间的几何表示 取取 作为决策面。作为决策面。如果两个向量如果两个向量 和和 都在决策面上，则有：都在决策面上，则有：或写成或写成 由于由于 和和 是决策面上的任意两点，所以是决策面上的任意两点，所以 也是在决策面上的任意向量。也是在决策面上的任意向量。表明了什么？表明了什么？0)(wXWXgT()0g X 1X2X1020TTW XwW Xw12()0TWXX12()XX1X2X12()0TWXX 两个两个n维维向量向量相互正交的充要条件是两相互正交的充要条件是两向量的内积为零。即向量的内积为零。即 所以所以,表明表明:权向量和决策面上的任一向量正交。所

9、以权权向量和决策面上的任一向量正交。所以权向量的方向就是决策面的法线方向。向量的方向就是决策面的法线方向。0),(BABAT12()0TWXX 在两维模式下，决策面在两维模式下，决策面 把模式空间分成两个子空间，把模式空间分成两个子空间，分别是对分别是对 类的决策域类的决策域 和对和对 类的决策域类的决策域 。如果我们规定：如果我们规定：在在 中，中，；在；在 中，中，决策面的法向量的方向指向决策面的法向量的方向指向 。1x2x0WX0)(Xg1R2R0)(Xg0)(XgHH121R2RX1R0)(Xg2R0)(Xg1R 1x2x0WX0)(Xg1R2R0)(Xg0)(XgHpX我们可以把向量

10、我们可以把向量 表示为：表示为：待求的距离待求的距离 决策面决策面 上一点上一点 与与 有什么样的关系有什么样的关系?X|PWXXWH()g X 则有：则有：或或判别函数值判别函数值 是是 到决策面的距离的度量。到决策面的距离的度量。()|g XWWWWXgWWWWXWWWWXWwXWXgpTpTpTT2000)()()()g XX同理，可以得出：同理，可以得出：从原点到决策面从原点到决策面 的距离为的距离为 。如果如果 ，原点在，原点在 的正面；的正面；如果如果 ，原点在，原点在 的反面；的反面；如果如果 ，判别函数有齐次形式，判别函数有齐次形式 决策面通过原点。决策面通过原点。0|wW00

11、w H00w H00w HXWXgT)(二类模式的线性分类器的决策法则是：二类模式的线性分类器的决策法则是：如果如果 则决策则决策 ，即把，即把 归到归到 类；类；如果如果 则决策则决策 ，即把，即把 归到归到 类；类；对于线性判别函数，关键的问题是求对于线性判别函数，关键的问题是求如何求？如何求？()0,g X X()0,g X X1212TnwwwW),(211.感知准则函数感知准则函数 由前面介绍的知识，我们知道，由前面介绍的知识，我们知道，对于一组两类别样本集：对于一组两类别样本集：我们可以设线性判别函数为：我们可以设线性判别函数为：决策面方程为：决策面方程为：即即 ,21NXXX0)

12、(wXWXgT()0g X 00wXWT 求得权向量求得权向量 ，就可确定决策面方程。，就可确定决策面方程。由数学知识，知由数学知识，知 的齐次形式比较容易。的齐次形式比较容易。能否将能否将 变换成齐次形式呢？变换成齐次形式呢？令令 ，则，则，n维维X空间空间 （n+1）维）维Y空间空间 Y称为增广模式向量，称为增广模式向量，A称为增广权向量称为增广权向量 W00 wXWT0)(wXWXgTTnwwwwA),(210TnxxxY),1(210)(wXWXgTYAYgT)(经过这样的变换，求解的问题就变为：经过这样的变换，求解的问题就变为：设有一组两类模式的增广模式向量样本集，设有一组两类模式的

13、增广模式向量样本集，利用这些样本确定一个线性判别函数利用这些样本确定一个线性判别函数的权向量的权向量 ，使，使 能够对能够对 正确分类。正确分类。,21NYYYYAYgT)(A0)(YgiY训练规则为：训练规则为：对于属于对于属于 类的所有样本，有类的所有样本，有:对于属于对于属于 类的所有样本，有类的所有样本，有:注意到注意到 和和能否使能否使？在属于在属于 类的样本前加上负号，则类的样本前加上负号，则120iTYA1,2,1Ni0jTYA2,2,1Nj0iTYA0jTYA0,jiTYA20)(jTYA这样处理后，问题变为：这样处理后，问题变为：求使对于所有训练样本都满足：求使对于所有训练样

14、本都满足：，的权向量的权向量如何求如何求？是一个线性不等式组，而是一个线性不等式组，而 是是 维的，样本数量为维的，样本数量为 ，一般，一般 比比 大的多，大的多，这样，这样，的解不唯一。的解不唯一。0iTYANi,2,1AA0iTYAY1nNNn0iTYA 为了解线性不等式组为了解线性不等式组 ，需要构造一，需要构造一个准则函数，并希望构造的准则函数有极值的形个准则函数，并希望构造的准则函数有极值的形式。式。是由于使用权向量是由于使用权向量 而被误分类的样本集合。而被误分类的样本集合。当一个样本当一个样本 被误分类时，就有被误分类时，就有 ,所以所以 。仅当。仅当 时，时，达到最小值。达到最

15、小值。0TiA Y()()ATpYyJAA YAyAY0TA Y()0pJ A Ay()pJA我们称我们称为为感知准则函数感知准则函数。有了准则函数之后，我们就可以用最优化方法寻有了准则函数之后，我们就可以用最优化方法寻找使准则函数达到极小值的解权向量找使准则函数达到极小值的解权向量 。如何求如何求？AA()()ATpYyJAA Y2.2.梯度下降法梯度下降法 梯度的定义梯度的定义 梯度是函数梯度是函数 的一阶偏导数组成的向量的一阶偏导数组成的向量,记为记为 二元函数的等值线二元函数的等值线 定义定义:坐标面上函数相等的各点的连线叫等值线坐标面上函数相等的各点的连线叫等值线,也称等高线。也称等

16、高线。f x 12,.,nfffff xxxxx 函数函数 为不同值时，得到一系列的等值线，构为不同值时，得到一系列的等值线，构成成 的等值线族的等值线族 。在极值处的等值线在极值处的等值线聚成一点，并位于等值聚成一点，并位于等值线的中心，当该中心为线的中心，当该中心为极小值时，离开它越远，极小值时，离开它越远，值越大，反之，若值越大，反之，若该中心为极大值时，离开该中心为极大值时，离开它越远，它越远，的值越小。的值越小。fx,a b c d f x f x f x 梯度方向梯度方向 由梯度的定义知，由梯度的定义知，梯度的方向就是函数的法线的方向。梯度的方向就是函数的法线的方向。1x2xTxf

17、xfXf21,)(梯度方向的性质梯度方向的性质:v沿梯度方向，函数值增长最快，为最速沿梯度方向，函数值增长最快，为最速上升方向；上升方向；v沿负梯度方向，函数值下降最快，为最沿负梯度方向，函数值下降最快，为最速下降方向。速下降方向。梯度下降法的基本思想：梯度下降法的基本思想：函数函数 在某点在某点 的梯度的梯度 是一个向量，是一个向量，它的方向与过点它的方向与过点 的等量面的等量面 的法线方的法线方向重合，指向向重合，指向 增加的一方，是准则函数变化率增加的一方，是准则函数变化率最大的方向。反之，负梯度的方向则是函数最大的方向。反之，负梯度的方向则是函数 减减少的最快的方向。所以在求准则函数少

18、的最快的方向。所以在求准则函数 的极小的极小值时，值时，沿负梯度方向搜索有可能最快的找到最小值。沿负梯度方向搜索有可能最快的找到最小值。()pJAkA()pkG JAkA()pkJAC()pkJA()pJA()pJA梯度下降法的实现：梯度下降法的实现：先任意选择一个初始的权向量先任意选择一个初始的权向量 ，计算，计算 上的梯度上的梯度 ，从，从 出发在最陡方向出发在最陡方向（即负梯度方向）上移动一个距离以得到下一（即负梯度方向）上移动一个距离以得到下一个权向量个权向量 。可采用下面的迭代方法从可采用下面的迭代方法从 推出推出 。比例因子，叫做步长或增量比例因子，叫做步长或增量 因为因为 的第的

19、第 个梯度分量是个梯度分量是 。1A1A1()pG JA1A2AkA1kA1()kkkpkAAG JA()pJAj()pjJAA()()ApYyG JAY 所以，可得到梯度下降法的迭代公式：所以，可得到梯度下降法的迭代公式：当第当第 步迭代用权向量步迭代用权向量 来分类时被误分类的样本集合来分类时被误分类的样本集合 这种寻找解权向量的梯度下降法简述如下这种寻找解权向量的梯度下降法简述如下:把第把第 次的权向量加上被误分类的样本的和次的权向量加上被误分类的样本的和与某个常数与某个常数 的乘积，就得到第的乘积，就得到第 次的权次的权向量。向量。1AkkkkYyAAYKkAKk(1)K v 优点：只

20、要二类样本线性可分的，这个算法总可收敛。v 缺点：每次迭代必须遍历全部样本，才能得到当前权向量 下的误分样本集 ，从而再对 的值进行修正。v kAkAykA用用训练样本集训练样本集求线性决策面方法要点：求线性决策面方法要点：v求线性决策面函数v转化成齐次形式v感知准则函数v梯度下降法v迭代公式0)(wXWXgTYAYgT)()()ATpYyJAA Y1AkkkkYyAAY1()kkkpkAAG JA2.3 2.3 固定增量算法及其收敛性固定增量算法及其收敛性 针对梯度下降法的缺点，作以下两点改变，针对梯度下降法的缺点，作以下两点改变，得到固定增量算法：得到固定增量算法：kAkAy（1 1）把全

21、部样本看作是一个序列，每当前）把全部样本看作是一个序列，每当前一步迭代的权向量把某个样本错误分类时，一步迭代的权向量把某个样本错误分类时，就对这一个权向量作一次修正，而不是等当就对这一个权向量作一次修正，而不是等当前权向量前权向量 对全部样本计算后再找出错对全部样本计算后再找出错分类样本集分类样本集 去进行修改。去进行修改。（2 2）考虑每次迭代时）考虑每次迭代时 保持不变。保持不变。kAkkAy二类模式下用固定增量法求解权向量：二类模式下用固定增量法求解权向量：设已知二类模式的样本集设已知二类模式的样本集 和和 ，这些，这些样本都已被变成增广模式向量的形式，要样本都已被变成增广模式向量的形式

22、，要求 用 固 定 增 量 的 方 法 决 定 一 个 超 平求 用 固 定 增 量 的 方 法 决 定 一 个 超 平面面 ，使它能正确划分样本集，使它能正确划分样本集 和和 。开始时可以任意假定开始时可以任意假定 和和 位于决策面位于决策面的哪一边。同样可以任意选择广义向量的哪一边。同样可以任意选择广义向量 的初始值的初始值 。然后把训练集然后把训练集 和和 中的增广模式向量中的增广模式向量 依次取出，计算依次取出，计算 与与 的内积的内积 。*1R*2R0TA Y*1R*2R*1R*2RA1A*1R*2RYAYTA Y假定假定 在在 的正面，的正面，在它的反面在它的反面权向量权向量 用以

23、下规则调整：用以下规则调整：如果如果 ，而，而 ，则用，则用 代替代替 ；如果如果 ，而，而 ，则用，则用 代替代替 ；如果如果 ，而，而 ，则，则 保持不变。保持不变。如果如果 ，而，而 ，则，则 保持不变。保持不变。把属于把属于 和和 的全部模式都用上述方法处理的全部模式都用上述方法处理一遍，称为一次迭代。一遍，称为一次迭代。这个算法重复执行，直至权向量这个算法重复执行，直至权向量 不再变化，不再变化，则则 ，即求得解权向量，即求得解权向量 。A*1YRAYA*2YR0TA Y A YA*1YR0TA Y A*2YR0TA Y A*1R0TA Y*2R*1R*2RA*AA0TA Y*A 2

24、.7 Fisher 2.7 Fisher 线性判别函数线性判别函数 在应用统计方法进行模式识别时，许多问在应用统计方法进行模式识别时，许多问题涉及维数，在低维空间行得通的方法，往往题涉及维数，在低维空间行得通的方法，往往在高维空间行不通。因此，发展了一些降低特在高维空间行不通。因此，发展了一些降低特征空间维数的方法，征空间维数的方法，Fisher线性判别函数就是线性判别函数就是其中之一。其中之一。在介绍在介绍Fisher线性判别函数之前，先补充线性判别函数之前，先补充介绍要用到的介绍要用到的Lagrange乘子法乘子法一种带等一种带等式约束的函数极值求解方法。式约束的函数极值求解方法。Lagr

25、ange乘子法乘子法一一.等式约束最优化问题等式约束最优化问题二二.Lagrange乘子的概念乘子的概念 0mins.t.f x数学模型 g xf(x1,x2)的等值线x2x1s是g(x1,x2)=0的法线方向g(x1,x2)=0极值点必须满足两个条件极值点必须满足两个条件:1.目标函数目标函数 沿约束曲线沿约束曲线 的切的切线方向线方向 的方向导数的方向导数 ,即即2.约束函数约束函数 沿约束曲线沿约束曲线 的切线的切线 方向方向 的方向导数的方向导数 ,即即12,f x x12,0g x xs0fs12120 xxfffsxsxs12,g x x12,0g x xs0gs12120 xxg

26、ggsxsxs比较上述两式可以得到比较上述两式可以得到:令令可得可得:为待定系数为待定系数,解这个联立解这个联立 方程可以求出方程可以求出 ,为问题的极小点，为问题的极小点，极小值为极小值为 。1122fgfgxxxx1122fgfgxxxx11221200,0fgxxfgxxg xx*12,x x*12,xx*12,f x x 设设 对各变量分别求偏导数并令其等于对各变量分别求偏导数并令其等于0,可得到：可得到：实际上是求函数实际上是求函数 的极值的极值这个形式与前述形式一样。这个形式与前述形式一样。121212,L x xf x xg x x1112221200,0LfgxxxLfgxxx

27、Lg x x12,L xx 三、二维情况下的三、二维情况下的Lagrange乘子法乘子法 对于等式约束优化函数对于等式约束优化函数 构造构造Lagrange函数：函数：使使 达到极小值，达到极小值，称为称为Lagrange乘子。乘子。用用Lagrange乘子法可以将等式约束优化问题转化为无乘子法可以将等式约束优化问题转化为无约束优化问题。约束优化问题。min().()0f xstg x ,L xf xg x,L x四、对于四、对于 维的情况维的情况 数学模型数学模型 首先由情况引入首先由情况引入Lagrange系数系数 ，构造，构造Lagrange函数：函数：min.01,2,.,nif xx

28、Est gxim12,.,m 121 122,.,.mm mL xf xg xg xgx 1miiif xgxn Fisher方法的基本思想：方法的基本思想：把把 维空间的所有模式投影到一条过原点的直线上，就维空间的所有模式投影到一条过原点的直线上，就可以把维数压缩到可以把维数压缩到1。过原点的直线有无数条，投影到那条直线好呢？过原点的直线有无数条，投影到那条直线好呢？dx1x1x2x2 我们的目标就是找到这样一条直线，使得我们的目标就是找到这样一条直线，使得模式样本在这条直线上的投影最有利于分类。模式样本在这条直线上的投影最有利于分类。设给定两类模式样本集，设给定两类模式样本集，和和 ，它们

29、它们各有各有 和和 个个 维样本。设维样本。设 为这条直线为这条直线正方向的单位向量，正方向的单位向量，。将样本集中的。将样本集中的样本向直线投影，相应地得到集合样本向直线投影，相应地得到集合 和和 。每个每个 就是就是 在单位向量在单位向量 上的投影。上的投影。有：有：这样，就得到了一个一维样本集合，样本数这样，就得到了一个一维样本集合，样本数量为量为 1n2ndW1WW1X2X1Y2YiYyiXxXWyT21nnN下面要解决的问题是什么？下面要解决的问题是什么？确定最好的投影方向确定最好的投影方向 的的 为了找到最好的为了找到最好的 ，需要建立一个准则函数，需要建立一个准则函数，这个准则函

30、数要能反映不同类别模式在这条直这个准则函数要能反映不同类别模式在这条直线上投影分离程度的好坏。线上投影分离程度的好坏。在确定建立准则函数之前，先介绍几个有关参在确定建立准则函数之前，先介绍几个有关参数。数。XWyTWW1.在在d维维X空间空间（1）各类样本的均值向量）各类样本的均值向量（2）样本类内离散度，总类内离散度）样本类内离散度，总类内离散度 imiXxiixnm12,1iTiXxiimxmxSi)(21SSSw2,1i（3）样本类间离散度）样本类间离散度TBmmmmS)(21212.在一维在一维Y空间空间（1）各类样本的均值）各类样本的均值（2）样本类内离散度，总类内离散度）样本类内离

31、散度，总类内离散度 2,1i2,1i*imiyyiiynm1*2*2*)(iYyiimyS2*22*1*SSSw 我们希望投影后，在一维我们希望投影后，在一维Y空间两类样本尽可空间两类样本尽可能分得开一些，即能分得开一些，即 （1）两类样本离得越远越好）两类样本离得越远越好,也就是，两类均值也就是，两类均值之差之差 越大越好，越大越好，（2）各类样本内部越密集越好，也就是，类内）各类样本内部越密集越好，也就是，类内离散度越小越好，离散度越小越好，越小越好。越小越好。因此，可以构造准则函数为：因此，可以构造准则函数为：2*12*2*212()mmJ WSS)(*2*1mm 2*22*1*SSSw

32、 我们的目标是使我们的目标是使 尽可能大的尽可能大的 作为作为投影方向，但在上式中不显含投影方向，但在上式中不显含 ，因此，要，因此，要将将 变成变成 的显函数。的显函数。)(WJWWW)(WJ*11iiTTiiy yx xiimyW XW mnn准则函数的分子项：准则函数的分子项：WSWWmmmmWmmWmmWmWmWmWmWmWmWmmBTTTTTTTTTTT)()()()(2121212121212212*2*1准则函数的分母项：准则函数的分母项：WSWWmxmxWWmxmxWmWxWmySiTTiXxiTTiiXxTiTXxTiYyiiiii)()()()(22*2*WSWWSSWWS

33、WWSWSSWTTTT)(21212*22*1因此，准则函数因此，准则函数 可改写为：可改写为：(2.43)这就是这就是Rayleigh比，它有如下性质：比，它有如下性质：（1）是一个实数。是一个实数。（2）的极值与大小无关，只与的极值与大小无关，只与 的方向有的方向有关。关。因此，因此，可以用可以用Lagrange乘数法求极值。乘数法求极值。由性质由性质(2)，可令式，可令式(2.43)分母为非零常数，即分母为非零常数，即()TBTWW S WJ WW S W()J W()(),J WJ aWa()J WW0TWW S WC()J W构造构造Lagrange函数函数 极大值的条件为：极大值的

34、条件为：即即 如果如果 非奇异，左乘非奇异，左乘 ，则有则有 解这个式子，就是求矩阵解这个式子，就是求矩阵 的本征值。的本征值。(,)()TTBWL WW S WCW S W(,)220BWL WS WS WW0BWS WS WBWS WS W1WS1WBSS WWWSBWSS1考虑到我们求解问题的特殊性（考虑到我们求解问题的特殊性（只确定方向只确定方向），），其中其中 是常数，所以是常数，所以 总是在总是在 的方向上。从而的方向上。从而 所以所以略去比例因子略去比例因子 ，它不影响直线的方向，它不影响直线的方向，得：得：121212()()()TBS WmmmmWmmR12()TRmmWBS

35、 W12()mm112()WWSmm R112()WRWSmmR112()WWSmm 这就是使准则函数这就是使准则函数 极大的解。极大的解。就就是使模式样本的投影在类间最分散，类内是使模式样本的投影在类间最分散，类内最集中的最优解。有了最集中的最优解。有了 后，得后，得 就可将各样本由维空间投影到一维空间，就可将各样本由维空间投影到一维空间，即直线上，变成一维样本，它们给出较好即直线上，变成一维样本，它们给出较好的分类结果。的分类结果。此类方法有一定的局限性：此类方法有一定的局限性：只对准则函数最优；只对准则函数最优；没有利用样本的分布信息，错误概率不能没有利用样本的分布信息，错误概率不能达到

36、最小。达到最小。()J WWW,TiiyW X yy Xx2.8 2.8 支持向量机支持向量机 Support Vector Machine SVMSupport Vector Machine SVM 回顾：用线性判别函数方法解决分类问题的方法回顾：用线性判别函数方法解决分类问题的方法1.思路思路（1）训练样本集）训练样本集 特征空间划分特征空间划分 决策面决策面 线性判别线性判别函数函数（2）待识别模式）待识别模式 判别判别2.问题核心：问题核心：求线性判别函数的权向量求线性判别函数的权向量3.求解方法：感知准则函数，梯度下降法，固定增量法求解方法：感知准则函数，梯度下降法，固定增量法求得权

37、向量求得权向量=确定了特征空间的两类分界面（决策面）确定了特征空间的两类分界面（决策面）一一.最优分界面最优分界面 从线性判别函数的讨论中，我们已经知道，从线性判别函数的讨论中，我们已经知道，对于线性可分的两类样本，总可以找到一个对于线性可分的两类样本，总可以找到一个分界面，将两类样本正确分类，而且，这样分界面，将两类样本正确分类，而且，这样的分界面不是唯一的。的分界面不是唯一的。1x2x0H1和和H2都可以将两类训练样本正确分类，但是，对于训练都可以将两类训练样本正确分类，但是，对于训练样本以外的样本，以哪个作为分界面，分类效果更好呢？样本以外的样本，以哪个作为分界面，分类效果更好呢？H1H

38、2因为：因为：H2产生错误分类的可能性更小。产生错误分类的可能性更小。这就提出了分类器设计中一个很重要的问题：这就提出了分类器设计中一个很重要的问题：分类器的通用性分类器的通用性，也称，也称分类器的推广能力分类器的推广能力即：即：用训练样本设计的分类器，对训练样本以外的用训练样本设计的分类器，对训练样本以外的样本能够正确分类的能力。样本能够正确分类的能力。哪一个分界面可以使分类器具有最好的通用性？哪一个分界面可以使分类器具有最好的通用性？1x2x0 H1是两类各自最近样本距离相同的分界面，是两类各自最近样本距离相同的分界面，H2也也是两类各自最近样本距离相同的分界面是两类各自最近样本距离相同的

39、分界面.H1H2最优分界面：最优分界面：在样本空间中，使两类样本正确分类，而且在样本空间中，使两类样本正确分类，而且两类样本分开的间隔最大的分界面为最优分界两类样本分开的间隔最大的分界面为最优分界面。面。最优分界面可以使分类器具有最好的通用性最优分界面可以使分类器具有最好的通用性（推广能力）。（推广能力）。如何求最优分界面？如何求最优分界面？二二.支持向量支持向量对于给定的线性可分训练样本集，对于给定的线性可分训练样本集，如果如果 则则 如果如果 则则 可以得到分界面。可以得到分界面。由于两类样本之间总有间隔存在，所以可以由于两类样本之间总有间隔存在，所以可以有：有：如果如果 则则 如果如果

40、则则 其中其中 是一个正数。是一个正数。1XCXg)(2XCXg)(C1X2X0)(Xg0)(Xg为了方便，训练样本集的样本用为了方便，训练样本集的样本用二元对二元对来表示：来表示：其中其中 和和 分别是样本模式向分别是样本模式向量和它的相应的类别表示，量和它的相应的类别表示，假定当假定当 时，时，。而当。而当 时时 。设给定的有穷训练样本集可以被设给定的有穷训练样本集可以被超平面超平面 正确分开。正确分开。使每类离开分界超平面最近的样本向量与超平面使每类离开分界超平面最近的样本向量与超平面之间的距离最大，位于间隔中间的超平面是最之间的距离最大，位于间隔中间的超平面是最优的。优的。niXR1,

41、1iy 00TW Xw1iy 1iy 1iX2iX),(,),(),(2211nlyXyXyX我们已经知道，在模式向量空间，任何一个我们已经知道，在模式向量空间，任何一个模式向量到决策面的距离为：模式向量到决策面的距离为：对于决策面方程对于决策面方程 ，和和 并不是唯一的并不是唯一的。WwXWWXgT0)(0)(wXWXgTW0wWXH设想：可以将设想：可以将 和和 进行某种比例缩放，总可以进行某种比例缩放，总可以找到一个找到一个 和和 ，使，使 到决策面的距离最小，到决策面的距离最小，为为 ，这样，两类模式的分类规则可以写成：这样，两类模式的分类规则可以写成：合并这两个式子，写成：合并这两个

42、式子，写成：1TiW Xb W0w0wWXW11TiW Xb 1iy 1iy 1,1,2,.,Tiiy W Xbil这时两类模式间隔的距离为：这时两类模式间隔的距离为：为了使间隔最大，应当使为了使间隔最大，应当使 最小，等价于最小，等价于使使 最小，最小，所以，使所以，使 最小，且满足最小，且满足的分界面就是最优分界面，距离最优分界的分界面就是最优分界面，距离最优分界面最近的模式向量就是面最近的模式向量就是支持向量支持向量。可以看出，寻找支持向量，就是寻找最优可以看出，寻找支持向量，就是寻找最优分界面。分界面。W2W2W2W1bXWyiTi 设目标函数为：设目标函数为：将寻找最优分界面问题转化

43、为有约束优化问题：将寻找最优分界面问题转化为有约束优化问题：如何求解？如何求解？221)(WW)(2121)(2WWWWT1,1,2,.,Tiiy W Xbilmin.ts 构造构造Lagrange函数：函数：其中其中 为为Lagrange乘子，乘子，1)(21),(1iiTliiTybXWWWbWLi0i 达到极值的必要条件为：达到极值的必要条件为：(1),得得(2),得得 而对于最优分界面，解而对于最优分界面，解 必须满足：必须满足：(1)(2)最优分界面的解权向量是训练样本集中模式向量的线最优分界面的解权向量是训练样本集中模式向量的线性组合性组合.(,)0L W b ab10liiiiW

44、X y(,)0L W b aW10liiiy0i0010,0,1,2,.,liiiiyil001liiiiWyX),(bWL 对于约束条件对于约束条件,等号在支持向量下才成立，也等号在支持向量下才成立，也就是说，只有支持向量可以在就是说，只有支持向量可以在 的展开中具的展开中具有有非零系数非零系数 ，因此有，因此有 其中其中 是支持向量集。是支持向量集。如何知道哪些样本是支持向量呢如何知道哪些样本是支持向量呢?0W0i00iiiSWyXS求最优分类超平面问题：求最优分类超平面问题：1,112llTiijijijii jWy yX X1)(21),(1iiTliiTybXWWWbWL1,1,2,

45、.,Tiiy W Xbil0imax等等价价转转换换对偶问题对偶问题 这是一个二次函数优化问题，存在唯一解，解中这是一个二次函数优化问题，存在唯一解，解中不为零的不为零的 所对应的样本就是所对应的样本就是支持向量支持向量。求得支持向量后，可求得权向量求得支持向量后，可求得权向量 和和 式中式中 表示属于第一类的支持向量，表示属于第一类的支持向量，而而 表示属于第二类的支持向量。表示属于第二类的支持向量。这样，由这样，由 和和 就确定了最优超平面。就确定了最优超平面。i0b0W0W0b00iiiSWyX 0001*1*12TTbW XW X*1X*1X 举例：举例：设有四个两类样本，设有四个两类

46、样本，类有两个样本：类有两个样本：类有两个样本：类有两个样本：求最优分界面。求最优分界面。2TX0,01TX0,1 2TX0,23TX2,041对偶问题：对偶问题：i=1，j=1，2，3，4，i=2，j=2，j=3，j=4，i=3，j=2，j=3，j=4，i=4，j=4，0jTiXX122XXT22232XXT322042XXT00322433XXT234043XXT0444XXT244)(21)(1,1jTijijnjiiniiXXyyW求求 的极值的极值。令令 )444(21242332224321)(W0)(iW01)(1W0)(2W0)(3W0)(4W01021320421320414

47、矛盾矛盾是凹凸函数是凹凸函数)(W原原因因)(21)(1,1jTijijnjiiniiXXyyW利用利用 支持向量为：支持向量为：01iniiy0432102132043210104140421320432101041421243312433432,XXX不满足要求不满足要求利用利用 确定确定最优分界面：最优分界面：32,XX0bTTTTiiSiXyW21,212,0410,2430,1 00 0001*1*12TTbW XW X43)0,20,1(21,2121TT04321,21)(2100 xxbXWXgT0322)(21xxXg三三.支持向量机支持向量机1.广义线性判别函数广义线性判别

48、函数x1x1x2x2 对图示的两类分布，可以用一个对图示的两类分布，可以用一个4次多项式决策次多项式决策函数对其分类。函数对其分类。这是一个两维函数这是一个两维函数0214113211222112110221922183273163215231422213422411)(wxwxwxxwxwxwxxwxxwxwxwxxwxxwxxwxwxwXg 做特征空间变换，令做特征空间变换，令 则有则有4422333321212121 212122221 2121 212(1,)TYx x x x x x x x x x x xx x x x x x x xTwwwwA),(14210YAYgT)(可将一

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

50、加，例中2维变成维变成15维维 维数增加导致所需样本数呈指数增加。维数增加导致所需样本数呈指数增加。YAYgT)()(Yg)(Xg)(Yg2.支持向量机支持向量机 在求最优分界面时在求最优分界面时,最优分界面只与支持向最优分界面只与支持向量有关量有关,优化函数优化函数 只需要计算训练样本的内积只需要计算训练样本的内积,而映射到高维而映射到高维空间中也只需内积运算。根据泛函理论，空间中也只需内积运算。根据泛函理论，只要一种核函数只要一种核函数 (kernel)满足满足Mercer条件，它就对应某个变换空间中的条件，它就对应某个变换空间中的内积。内积。),(jiXXK)(21)(1,1jTijij