线性判别函数市公开课获奖课件

1、线性判别函数和决议面感知准则函数和梯度下降法固定增量法及其收敛性最小平方误差准则函数多类情况下线性判别函数分段线性判别函数Fisher 线性判别函数支持向量机第二章 线性判别函数第1页第1页2.1 线性判别函数和决议面 模式表示 在分类辨认办法中，首先应当把代表事物那些特性抽取出来，构成代表这个模式特性向量。 现在假定已经抽取到模式若干特性： 假如这 个特性能够较好地描述原始待辨认事物，则能够用 维空间一个列向量来代表：第2页第2页1.问题与处理思绪问题： 设有由N个待分类两类别模式构成一个样本集， 如何实现对样本集中两类样本分类？ 第3页第3页在普通情况下样本在特性空间分布情况：（二维两类别

2、模式例子）第4页第4页二维三类别模式例子第5页第5页能够看出: 不同类别经典样本在特性空间中显著处于不同区域。 表明: 因为相同类别模式含有相同或相近特性，因而一类模式在特性空间中某一区域分布，而另一类则在另外区域分布。第6页第6页 我们能够得到启发: 用已知类别模式样本产生一个代数表示分界面 ，将特性空间分成两个互不重合区域，使不同类别模式样本位于不同区域，再用 作为判别函数，对待识别模式进行分类。 在特性空间可看作一个决议面。第7页第7页归纳处理问题思绪:(1)分类问题 特性空间分布 寻找 子区域分界面 拟定判别函数(2)待辨认模式 判别函数 分类处理办法？代入 判别第8页第8页 判别函数

3、 能够有各种形式，哪种形式最简朴呢？ 线性函数 在二维空间是一条直线；在三维空间是一个平面；在高维空间也是一个平面，由于是非直观，称为超平面。第9页第9页 线性判别函数是所有模式特性线性组合。 或 式中 是特性系数，称为权， 称为阈值权。用什么办法来拟定 呢？第10页第10页2. 线性判别函数确实定办法设有已知类别两类别样本集，分布下列： 第11页第11页线性判别函数能够写成：参数 决定了 方向和位置第12页第12页如何依据已知样本拟定 ？ 由于要用 对两类样本在特性空间正确划分两类模式区域，我们能够假定一个规则： 当样本为一个类别时， 使 当样本为另一个类别时，使 第13页第13页 对所有样

4、本都按这个规则来做，不满足时，调整 ，最后能够找到一个 ，使所有样本都满足这个规则。 这个过程称为训练学习，已知类别样本称为训练样本。 用训练学习办法拟定线性判别函数。如何训练学习？第14页第14页3.线性判别函数普通表示 对于n维模式向量 ，其线性判别函数是所有模式特性线性组合，即 能够写成其中， 称为权向量。第15页第15页4. 在向量空间几何表示 取 作为决议面。 假如两个向量 和 都在决议面上，则有： 或写成 由于 和 是决议面上任意两点，因此 也是在决议面上任意向量。 表明了什么？第16页第16页 两个n维向量互相正交充要条件是两向量内积为零。即 因此, 表明: 权向量和决议面上任一

5、向量正交。因此权向量方向就是决议面法线方向。第17页第17页 在两维模式下，决议面 把模式空间分成两个子空间，分别是对 类决议域 和对 类决议域 。 假如我们要求： 在 中， ；在 中， ，决议面法向量方向指向 。 第18页第18页 第19页第19页我们能够把向量 表示为： 待求距离 决议面 上一点 与 有什么样关系? 第20页第20页 则有： 或判别函数值 是 到决议面距离度量。第21页第21页同理，能够得出：从原点到决议面 距离为 。 假如 ，原点在 正面； 假如 ，原点在 反面； 假如 ，判别函数有齐次形式 决议面通过原点。第22页第22页二类模式线性分类器决议法则是： 假如 则决议 ，

6、即把 归到 类； 假如 则决议 ，即把 归到 类；对于线性判别函数，关键问题是求如何求？ 第23页第23页2.2 感知准则函数和梯度下降法1.感知准则函数 由前面简介知识，我们知道，对于一组两类别样本集：我们能够设线性判别函数为：决议面方程为：即 第24页第24页 求得权向量 ，就可拟定决议面方程。 由数学知识，知 齐次形式比较容易。能否将 变换成齐次形式呢？ 令 ，则， n维X空间 （n+1）维Y空间 Y称为增广模式向量，A称为增广权向量 第25页第25页 通过这样变换，求解问题就变为：设有一组两类模式增广模式向量样本集，利用这些样本拟定一个线性判别函数权向量 ，使 能够对 正确分类。第26

7、页第26页训练规则为：对于属于 类所有样本，有: 对于属于 类所有样本，有: 注意到 和能否使 ？ 在属于 类样本前加上负号，则第27页第27页这样处理后，问题变为：求使对于所有训练样本都满足： ， 权向量如何求 ？ 是一个线性不等式组，而 是 维，样本数量为 ，普通 比 大多， 这样， 解不唯一。 第28页第28页 为理解线性不等式组 ，需要结构一个准则函数，并希望结构准则函数有极值形式。 是由于使用权向量 而被误分类样本集合。当一个样本 被误分类时，就有 ,因此 。仅当 时， 达到最小值。 第29页第29页我们称为感知准则函数。有了准则函数之后，我们就能够用最优化办法寻找使准则函数达到极小

8、值解权向量 。 如何求 ？第30页第30页2. 梯度下降法 梯度定义 梯度是函数 一阶偏导数构成向量, 记为 二元函数等值线 定义:坐标面上函数相等各点连线叫等值线,也称等高线。 第31页第31页 函数 为不同值时，得到一系列等值线，组成 等值线族 。 在极值处等值线聚成一点，并位于等值线中心，当该中心为极小值时，离开它越远， 值越大，反之，若该中心为极大值时，离开它越远， 值越小。第32页第32页 梯度方向 由梯度定义知， 梯度方向就是函数法线方向。第33页第33页 梯度方向性质:沿梯度方向，函数值增长最快，为最速上升方向；沿负梯度方向，函数值下降最快，为最速下降方向。第34页第34页梯度下

9、降法基本思想：函数 在某点 梯度 是一个向量，它方向与过点 等量面 法线方向重叠，指向 增长一方，是准则函数改变率最大方向。反之，负梯度方向则是函数 减少最快方向。因此在求准则函数 极小值时，沿负梯度方向搜索有也许最快找到最小值。 第35页第35页梯度下降法实现： 先任意选择一个初始权向量 ，计算 上梯度 ，从 出发在最陡方向（即负梯度方向）上移动一个距离以得到下一个权向量 。可采用下面迭代办法从 推出 。 百分比因子，叫做步长或增量 由于 第 个梯度分量是 。 第36页第36页 因此，可得到梯度下降法迭代公式： 当第 步迭代用权向量 来分类时被误分类样本集合 这种寻找解权向量梯度下降法简述下

10、列: 把第 次权向量加上被误分类样本和与某个常数 乘积，就得到第 次权向量。第37页第37页 长处：只要二类样本线性可分，这个算法总可收敛。 缺点：每次迭代必须遍历所有样本，才干得到当前权向量 下误分样本集 ，从而再对 值进行修正。 第38页第38页用训练样本集求线性决议面办法要点：求线性决议面函数转化成齐次形式感知准则函数梯度下降法迭代公式第39页第39页2.3 固定增量算法及其收敛性 针对梯度下降法缺点，作下列两点改变，得到固定增量算法： （1）把所有样本看作是一个序列，每当前一步迭代权向量把某个样本错误分类时，就对这一个权向量作一次修正，而不是等当前权向量 对所有样本计算后再找犯错分类样

11、本集 去进行修改。（2）考虑每次迭代时 保持不变。第40页第40页二类模式下用固定增量法求解权向量： 设已知二类模式样本集 和 ，这些样本都已被变成增广模式向量形式，要求用固定增量办法决定一个超平面 ，使它能正确划分样本集 和 。 开始时能够任意假定 和 位于决议面哪一边。同样能够任意选择广义向量 初始值 。 然后把训练集 和 中增广模式向量 依次取出，计算 与 内积 。第41页第41页假定 在 正面， 在它反面权向量 用下列规则调整：假如 ，而 ，则用 代替 ；假如 ，而 ，则用 代替 ；假如 ，而 ，则 保持不变。假如 ，而 ，则 保持不变。 把属于 和 所有模式都用上述办法处理一遍，称为

12、一次迭代。 这个算法重复执行，直至权向量 不再改变，则 ，即求得解权向量 。 第42页第42页 2.7 Fisher 线性判别函数 在应用统计办法进行模式辨认时，许多问题涉及维数，在低维空间行得通办法，往往在高维空间行不通。因此，发展了一些减少特性空间维数办法，Fisher线性判别函数就是其中之一。 在简介Fisher线性判别函数之前，先补充简介要用到Lagrange乘子法一个带等式约束函数极值求解办法。 第43页第43页Lagrange乘子法一. 等式约束最优化问题二. Lagrange乘子概念 第44页第44页极值点必须满足两个条件:1.目的函数 沿约束曲线 切线方向 方向导数 , 即2.

13、约束函数 沿约束曲线 切线 方向 方向导数 , 即第45页第45页比较上述两式能够得到:令可得: 为待定系数,解这个联立 方程能够求出 , 为问题极小点， 极小值为 。第46页第46页 设 对各变量分别求偏导数并令其等于0,可得到： 事实上是求函数 极值这个形式与前述形式同样。第47页第47页 三、二维情况下Lagrange乘子法 对于等式约束优化函数 结构Lagrange函数： 使 达到极小值， 称为Lagrange乘子。 用Lagrange乘子法能够将等式约束优化问题转化为无约束优化问题。第48页第48页四、对于 维情况 数学模型 首先由情况引入Lagrange系数 ，结构Lagrange

14、函数：第49页第49页 Fisher办法基本思想： 把 维空间所有模式投影到一条过原点直线上，就能够把维数压缩到1。 过原点直线有无数条，投影到那条直线好呢？x1x2第50页第50页 我们目的就是找到这样一条直线，使得模式样本在这条直线上投影最有助于分类。 设给定两类模式样本集， 和 ， 它们各有 和 个 维样本。设 为这条直线正方向单位向量， 。将样本集中样本向直线投影，相应地得到集合 和 。每个 就是 在单位向量 上投影。 有： 这样，就得到了一个一维样本集合，样本数量为 第51页第51页下面要处理问题是什么？ 确定最好投影方向 为了找到最好 ，需要建立一个准则函数，这个准则函数要能反应不

15、同类别模式在这条直线上投影分离程度好坏。 在确定建立准则函数之前，先介绍几个相关参数。 第52页第52页1.在d维X空间 （1）各类样本均值向量 （2）样本类内离散度，总类内离散度 第53页第53页（3）样本类间离散度第54页第54页2.在一维Y空间 （1）各类样本均值 （2）样本类内离散度，总类内离散度 第55页第55页 我们希望投影后，在一维Y空间两类样本尽也许分得开一些，即 （1）两类样本离得越远越好,也就是，两类均值之差 越大越好， （2）各类样本内部越密集越好，也就是，类内离散度越小越好， 越小越好。 因此，能够结构准则函数为：第56页第56页 我们目标是使 尽也许大 作为投影方向，

16、但在上式中不显含 ，因此，要将 变成 显函数。第57页第57页准则函数分子项：第58页第58页准则函数分母项：第59页第59页因此，准则函数 可改写为： (2.43)这就是Rayleigh比，它有下列性质：（1） 是一个实数。（2） 极值与大小无关，只与 方向相关。 因此， 能够用Lagrange乘数法求极值。由性质(2)，可令式(2.43)分母为非零常数，即第60页第60页结构Lagrange函数 极大值条件为：即 假如 非奇异，左乘 ，则有 解这个式子，就是求矩阵 本征值。 第61页第61页考虑到我们求解问题特殊性（只拟定方向 ），其中 是常数，因此 总是在 方向上。从而 因此略去百分比因

17、子 ，它不影响直线方向，得： 第62页第62页 这就是使准则函数 极大解。 就是使模式样本投影在类间最分散，类内最集中最优解。有了 后，得 就可将各样本由维空间投影到一维空间，即直线上，变成一维样本，它们给出较好分类结果。 这类办法有一定不足：只对准则函数最优；没有利用样本分布信息，错误概率不能达到最小。 第63页第63页2.8 支持向量机 Support Vector Machine SVM 回顾：用线性判别函数办法处理分类问题办法1.思绪（1）训练样本集 特性空间划分 决议面 线性判别函数（2）待辨认模式 判别2.问题关键： 求线性判别函数权向量3.求解办法：感知准则函数，梯度下降法，固定

18、增量法求得权向量=拟定了特性空间两类分界面（决议面） 第64页第64页一. 最优分界面 从线性判别函数讨论中，我们已经知道，对于线性可分两类样本，总能够找到一个分界面，将两类样本正确分类，并且，这样分界面不是唯一。第65页第65页H1和H2都能够将两类训练样本正确分类，但是，对于训练样本以外样本，以哪个作为分界面，分类效果更加好呢？H1H2第66页第66页由于：H2产生错误分类也许性更小。 这就提出了分类器设计中一个很主要问题： 分类器通用性，也称分类器推广能力即： 用训练样本设计分类器，对训练样本以外样本能够正确分类能力。 哪一个分界面能够使分类器含有最好通用性？第67页第67页 H1是两类

19、各自最近样本距离相同分界面， H2也是两类各自最近样本距离相同分界面.H1H2第68页第68页最优分界面： 在样本空间中，使两类样本正确分类，并且两类样本分开间隔最大分界面为最优分界面。 最优分界面能够使分类器含有最好通用性（推广能力）。 如何求最优分界面？ 第69页第69页 二. 支持向量对于给定线性可分训练样本集， 假如 则 假如 则 能够得到分界面。 由于两类样本之间总有间隔存在，因此能够有： 假如 则 假如 则 其中 是一个正数。第70页第70页为了以便，训练样本集样本用二元对来表示： 其中 和 分别是样本模式向量和它相应类别表示， 假定当 时， 。而当 时 。 设给定有穷训练样本集能

20、够被超平面 正确分开。 使每类离开分界超平面最近样本向量与超平面之间距离最大，位于间隔中间超平面是最优。第71页第71页我们已经知道，在模式向量空间，任何一个模式向量到决议面距离为：对于决议面方程 ， 和 并不是唯一。第72页第72页设想：能够将 和 进行某种百分比缩放，总能够找到一个 和 ，使 到决议面距离最小，为 ， 这样，两类模式分类规则能够写成：合并这两个式子，写成：第73页第73页这时两类模式间隔距离为：为了使间隔最大，应当使 最小，等价于使 最小，因此，使 最小，且满足分界面就是最优分界面，距离最优分界面最近模式向量就是支持向量。能够看出，寻找支持向量，就是寻找最优分界面。 第74

21、页第74页 设目的函数为：将寻找最优分界面问题转化为有约束优化问题： 如何求解？ 第75页第75页 结构Lagrange函数： 其中 为Lagrange乘子，第76页第76页 达到极值必要条件为： (1) , 得(2) , 得 而对于最优分界面，解 必须满足：(1)(2) 最优分界面解权向量是训练样本集中模式向量线性组合. 第77页第77页 对于约束条件,等号在支持向量下才成立，也就是说，只有支持向量能够在 展开中含有非零系数 ，因此有 其中 是支持向量集。 如何知道哪些样本是支持向量呢? 第78页第78页求最优分类超平面问题： 等价转换对偶问题第79页第79页 这是一个二次函数优化问题，存在唯一解，解中不为零 所相应样本就是支持向量。 求得支持向量后，可求得权向量 和 式中 表示属于第一类支持向量，而 表示属于第二类支持向量。这样，由 和 就拟定了最优超平面。 第80页第80页 举例： 设有四个两类样本， 类有两个样本： 类有两个样本： 求最优分界面。第81页第81页