线性判别函数省公共课一等奖全国赛课获奖课件.pptx

v线性判别函数和决议面线性判别函数和决议面v感知准则函数和梯度下降法感知准则函数和梯度下降法v固定增量法及其收敛性固定增量法及其收敛性v最小平方误差准则函数最小平方误差准则函数v多类情况下线性判别函数多类情况下线性判别函数v分段线性判别函数分段线性判别函数vFisher 线性判别函数线性判别函数v支持向量机支持向量机第二章第二章 线性判别函数线性判别函数第1页2.1 2.1 线性判别函数和决议面线性判别函数和决议面 模式表示模式表示 在分类识别方法中，首先应该把代表事物那在分类识别方法中，首先应该把代表事物那些些特征特征抽取出来，组成代表这个模式抽取出来，组成代表这个模式特征向量特征向量。现在假定已经抽取到模式若干特征：现在假定已经抽取到模式若干特征：假如这假如这 个特征能够很好地描述原始待识别个特征能够很好地描述原始待识别事物，则能够用事物，则能够用 维空间一个列向量来代表：维空间一个列向量来代表：第2页1.问题与处理思绪问题与处理思绪问题：问题：设有由设有由N个待分类个待分类两类别两类别模式组成一个样模式组成一个样本集，本集，怎样实现对样本集中两类样本分类？怎样实现对样本集中两类样本分类？第3页在普通情况下样本在特征空间分布情况：在普通情况下样本在特征空间分布情况：（二维两类别模式例子）（二维两类别模式例子）第4页二维三类别模式例子二维三类别模式例子第5页能够看出能够看出:不一样类别经典样本在特征空间中显著处于不不一样类别经典样本在特征空间中显著处于不一样区域。一样区域。表明表明:因为相同类别模式含有因为相同类别模式含有相同或相近特征相同或相近特征，因而，因而一类模式在特征空间中某一区域分布，而另一类一类模式在特征空间中某一区域分布，而另一类则在另外区域分布。则在另外区域分布。第6页 我们能够得到启发我们能够得到启发:用用已知类别模式样本已知类别模式样本产生一个代数表示分产生一个代数表示分界面界面 ，将特征空间分成两个互不重合，将特征空间分成两个互不重合区域，使不一样类别模式样本位于不一样区域，区域，使不一样类别模式样本位于不一样区域，再用再用 作为判别函数，对待识别模式作为判别函数，对待识别模式进行分类。进行分类。在特征空间可看作一个决议面。在特征空间可看作一个决议面。第7页归纳处理问题思绪归纳处理问题思绪:(1)分类问题分类问题 特征空间分布特征空间分布 寻找寻找 子区域分界面子区域分界面 确定判别函数确定判别函数(2)待识别模式待识别模式 判别函数判别函数 分类分类处理方法？处理方法？代入代入 判别判别第8页 判别函数判别函数 能够有各种形式，哪种形式能够有各种形式，哪种形式最简单最简单呢？呢？线性函数线性函数 在二维空间是一条直线；在三维空间是一个在二维空间是一条直线；在三维空间是一个平面；在高维空间也是一个平面，因为是非平面；在高维空间也是一个平面，因为是非直观，称为直观，称为超平面超平面。第9页 线性判别函数是全部模式特征线性组合。线性判别函数是全部模式特征线性组合。或或 式中式中 是特征系数，称为权，是特征系数，称为权，称为阈值权。称为阈值权。用什么方法来确定用什么方法来确定 呢？呢？第10页2.线性判别函数确实定方法线性判别函数确实定方法设有已知类别两类别样本集，分布以下：设有已知类别两类别样本集，分布以下：第11页线性判别函数能够写成：线性判别函数能够写成：参数参数 决定了决定了 方向和位置方向和位置第12页怎样依据已知样本确定怎样依据已知样本确定？因为要用因为要用 对两类样本在特征空间正确划对两类样本在特征空间正确划分两类模式区域，我们能够假定一个规则：分两类模式区域，我们能够假定一个规则：当样本为一个类别时，当样本为一个类别时，使使 当样本为另一个类别时，使当样本为另一个类别时，使 第13页 对全部样本都按这个规则来做，不满足时，对全部样本都按这个规则来做，不满足时，调整调整 ，最终能够找到一个，最终能够找到一个 ，使全，使全部样本都满足这个规则。部样本都满足这个规则。这个过程称为这个过程称为训练学习训练学习，已知类别样本称为，已知类别样本称为训练样本训练样本。用训练学习方法确定线性判别函数。用训练学习方法确定线性判别函数。怎样训练学习？怎样训练学习？第14页3.线性判别函数普通表示线性判别函数普通表示 对于对于n维模式向量维模式向量 ，其线性，其线性判别函数是全部模式特征线性组合，即判别函数是全部模式特征线性组合，即 能够写成能够写成其中其中，称为权向量。称为权向量。第15页4.在向量空间几何表示在向量空间几何表示 取取 作为决议面。作为决议面。假如两个向量假如两个向量 和和 都在决议面上，则有：都在决议面上，则有：或写成或写成 因为因为 和和 是决议面上任意两点，所以是决议面上任意两点，所以 也是在决议面上任意向量。也是在决议面上任意向量。表明了什么？表明了什么？第16页 两个两个n维向量相互正交充要条件是两向维向量相互正交充要条件是两向量内积为零。即量内积为零。即 所以所以,表明表明:权向量和决议面上任一向量正交。所以权向权向量和决议面上任一向量正交。所以权向量方向就是决议面法线方向。量方向就是决议面法线方向。第17页 在两维模式下，决议面在两维模式下，决议面 把模式空间分成两个子空间，把模式空间分成两个子空间，分别是对分别是对 类决议域类决议域 和对和对 类决议域类决议域 。假如我们要求：假如我们要求：在在 中，中，；在；在 中，中，决议面法向量方向指向决议面法向量方向指向 。第18页 第19页我们能够把向量我们能够把向量 表示为：表示为：待求距离待求距离 决议面决议面 上一点上一点 与与 有什么样关系有什么样关系?第20页 则有：则有：或或判别函数值判别函数值 是是 到决议面距离度量。到决议面距离度量。第21页同理，能够得出：同理，能够得出：从原点到决议面从原点到决议面 距离为距离为 。假如假如 ，原点在，原点在 正面；正面；假如假如 ，原点在，原点在 反面；反面；假如假如 ，判别函数有齐次形式，判别函数有齐次形式 决议面经过原点。决议面经过原点。第22页二类模式线性分类器决议法则是：二类模式线性分类器决议法则是：假如假如 则决议则决议 ，即把，即把 归到归到 类；类；假如假如 则决议则决议 ，即把，即把 归到归到 类；类；对于线性判别函数，关键问题是求对于线性判别函数，关键问题是求怎样求？怎样求？第23页2.2 2.2 感知准则函数和梯度下降法感知准则函数和梯度下降法1.感知准则函数感知准则函数 由前面介绍知识，我们知道，由前面介绍知识，我们知道，对于一组两类别样本集：对于一组两类别样本集：我们能够设线性判别函数为：我们能够设线性判别函数为：决议面方程为：决议面方程为：即即 第24页 求得权向量求得权向量 ，就可确定决议面方程。，就可确定决议面方程。由数学知识，知由数学知识，知 齐次形式比较轻易。齐次形式比较轻易。能否将能否将 变换成齐次形式呢？变换成齐次形式呢？令令 ，则，则，n维维X空间空间 （n+1）维）维Y空间空间 Y称为增广模式向量，称为增广模式向量，A称为增广权向量称为增广权向量 第25页 经过这么变换，求解问题就变为：经过这么变换，求解问题就变为：设有一组两类模式增广模式向量样本集，设有一组两类模式增广模式向量样本集，利用这些样本确定一个线性判别函数利用这些样本确定一个线性判别函数权向量权向量 ，使，使 能够对能够对 正确分类。正确分类。第26页训练规则为：训练规则为：对于属于对于属于 类全部样本，有类全部样本，有:对于属于对于属于 类全部样本，有类全部样本，有:注意到注意到 和和能否使能否使？在属于在属于 类样本前加上负号，则类样本前加上负号，则第27页这么处理后，问题变为：这么处理后，问题变为：求使对于全部训练样本都满足：求使对于全部训练样本都满足：，权向量权向量怎样求怎样求？是一个线性不等式组，而是一个线性不等式组，而 是是 维，样本数量为维，样本数量为 ，普通，普通 比比 大多，大多，这么，这么，解不唯一。解不唯一。第28页 为了解线性不等式组为了解线性不等式组 ，需要结构一个，需要结构一个准则函数，并希望结构准则函数有极值形式。准则函数，并希望结构准则函数有极值形式。是因为使用权向量是因为使用权向量 而被误分类样本集合。而被误分类样本集合。当一个样本当一个样本 被误分类时，就有被误分类时，就有 ,所以所以 。仅当。仅当 时，时，到达最小值。到达最小值。第29页我们称我们称为为感知准则函数感知准则函数。有了准则函数之后，我们就能够用最优化方法寻有了准则函数之后，我们就能够用最优化方法寻找使准则函数到达极小值解权向量找使准则函数到达极小值解权向量 。怎样求怎样求？第30页2.2.梯度下降法梯度下降法 梯度定义梯度定义 梯度是函数梯度是函数 一阶偏导数组成向量一阶偏导数组成向量,记为记为 二元函数等值线二元函数等值线 定义定义:坐标面上函数相等各点连线叫等值线坐标面上函数相等各点连线叫等值线,也称也称等高线。等高线。第31页 函数函数 为不一样值时，得到一系列等值线，组成为不一样值时，得到一系列等值线，组成 等值线族等值线族 。在极值处等值线在极值处等值线聚成一点，并位于等值聚成一点，并位于等值线中心，当该中心为线中心，当该中心为极小值时，离开它越远，极小值时，离开它越远，值越大，反之，若值越大，反之，若该中心为极大值时，离开该中心为极大值时，离开它越远，它越远，值越小。值越小。第32页 梯度方向梯度方向 由梯度定义知，由梯度定义知，梯度方向就是函数法线方向。梯度方向就是函数法线方向。第33页 梯度方向性质梯度方向性质:v沿梯度方向，函数值增加最快，为最速沿梯度方向，函数值增加最快，为最速上升方向；上升方向；v沿负梯度方向，函数值下降最快，为最沿负梯度方向，函数值下降最快，为最速下降方向。速下降方向。第34页梯度下降法基本思想：梯度下降法基本思想：函数函数 在某点在某点 梯度梯度 是一个向量，它是一个向量，它方向与过点方向与过点 等量面等量面 法线方向重合，法线方向重合，指向指向 增加一方，是准则函数改变率最大方向。增加一方，是准则函数改变率最大方向。反之，负梯度方向则是函数反之，负梯度方向则是函数 降低最快方向。所降低最快方向。所以在求准则函数以在求准则函数 极小值时，极小值时，沿负梯度方向搜索沿负梯度方向搜索有可能最快找到最小值。有可能最快找到最小值。第35页梯度下降法实现：梯度下降法实现：先任意选择一个初始权向量先任意选择一个初始权向量 ，计算，计算 上梯上梯度度 ，从，从 出发在最陡方向（即负梯出发在最陡方向（即负梯度方向）上移动一个距离以得到下一个权向量度方向）上移动一个距离以得到下一个权向量 。可采取下面迭代方法从可采取下面迭代方法从 推出推出 。百分比因子，叫做步长或增量百分比因子，叫做步长或增量 因为因为 第第 个梯度分量是个梯度分量是 。第36页 所以，可得到梯度下降法迭代公式：所以，可得到梯度下降法迭代公式：当第当第 步迭代用权向量步迭代用权向量 来分类时被误分类样本集合来分类时被误分类样本集合 这种寻找解权向量梯度下降法简述以下这种寻找解权向量梯度下降法简述以下:把第把第 次权向量加上被误分类样本和与某个常次权向量加上被误分类样本和与某个常数数 乘积，就得到第乘积，就得到第 次权向量。次权向量。第37页 优点：优点：只要二类样本线性可分，这个算法只要二类样本线性可分，这个算法总可收敛。总可收敛。缺点：缺点：每次迭代必须遍历全部样本，才能每次迭代必须遍历全部样本，才能得到当前权向量得到当前权向量 下误分样本集下误分样本集 ，从，从而再对而再对 值进行修正。值进行修正。第38页用用训练样本集训练样本集求线性决议面方法关键点：求线性决议面方法关键点：v求线性决议面函数v转化成齐次形式v感知准则函数v梯度下降法v迭代公式第39页2.3 2.3 固定增量算法及其收敛性固定增量算法及其收敛性 针对梯度下降法缺点，作以下两点改变，针对梯度下降法缺点，作以下两点改变，得到固定增量算法：得到固定增量算法：（1）把全部样本看作是一个序列，每当前）把全部样本看作是一个序列，每当前一步迭代权向量把某个样本错误分类时，就一步迭代权向量把某个样本错误分类时，就对这一个权向量作一次修正，而不是等当前对这一个权向量作一次修正，而不是等当前权向量权向量 对全部样本计算后再找犯错分类对全部样本计算后再找犯错分类样本集样本集 去进行修改。去进行修改。（2）考虑每次迭代时）考虑每次迭代时 保持不变。保持不变。第40页二类模式下用固定增量法求解权向量：二类模式下用固定增量法求解权向量：设设已已知知二二类类模模式式样样本本集集 和和 ，这这些些样样本本都都已已被被变变成成增增广广模模式式向向量量形形式式，要要求求用用固固定定增增量量方方法法决决定定一一个个超超平平面面 ，使使它能正确划分样本集它能正确划分样本集 和和 。开开始始时时能能够够任任意意假假定定 和和 位位于于决决议议面面哪一边。一样能够任意选择广义向量哪一边。一样能够任意选择广义向量 初始值初始值 。然后把训练集然后把训练集 和和 中增广模式向量中增广模式向量 依次取出，计算依次取出，计算 与与 内积内积 。第41页假定假定 在在 正面，正面，在它反面在它反面权向量权向量 用以下规则调整：用以下规则调整：v假如假如 ，而，而 ，则用，则用 代替代替 ；v假如假如 ，而，而 ，则用，则用 代替代替 ；v假如假如 ，而，而 ，则，则 保持不变。保持不变。v假如假如 ，而，而 ，则，则 保持不变。保持不变。把属于把属于 和和 全部模式都用上述方法处理一全部模式都用上述方法处理一遍，称为一次迭代。遍，称为一次迭代。这个算法重复执行，直至权向量这个算法重复执行，直至权向量 不再改变，不再改变，则则 ，即求得解权向量，即求得解权向量 。第42页 2.7 Fisher 2.7 Fisher 线性判别函数线性判别函数 在应用统计方法进行模式识别时，许多问在应用统计方法进行模式识别时，许多问题包括维数，在低维空间行得通方法，往往在题包括维数，在低维空间行得通方法，往往在高维空间行不通。所以，发展了一些降低特征高维空间行不通。所以，发展了一些降低特征空间维数方法，空间维数方法，Fisher线性判别函数就是其中线性判别函数就是其中之一。之一。在介绍在介绍Fisher线性判别函数之前，先补充线性判别函数之前，先补充介绍要用到介绍要用到Lagrange乘子法乘子法一个带等式一个带等式约束函数极值求解方法。约束函数极值求解方法。第43页Lagrange乘子法乘子法一一.等式约束最优化问题等式约束最优化问题二二.Lagrange乘子概念乘子概念 第44页极值点必须满足两个条件极值点必须满足两个条件:1.目标函数目标函数 沿约束曲线沿约束曲线 切线切线方向方向 方向导数方向导数 ,即即2.约束函数约束函数 沿约束曲线沿约束曲线 切线切线 方向方向 方向导数方向导数 ,即即第45页比较上述两式能够得到比较上述两式能够得到:令令可得可得:为待定系数为待定系数,解这个联立解这个联立 方程能够求出方程能够求出 ,为问题极小点，为问题极小点，极小值为极小值为 。第46页 设设 对各变量分别求偏导数并令其等于对各变量分别求偏导数并令其等于0,可得到：可得到：实际上是求函数实际上是求函数 极值极值这个形式与前述形式一样。这个形式与前述形式一样。第47页 三、二维情况下三、二维情况下Lagrange乘子法乘子法 对于等式约束优化函数对于等式约束优化函数 结构结构Lagrange函数：函数：使使 到达极小值，到达极小值，称为称为Lagrange乘子。乘子。用用Lagrange乘子法能够将等式约束优化问题转化为无乘子法能够将等式约束优化问题转化为无约束优化问题。约束优化问题。第48页四、对于四、对于 维情况维情况 数学模型数学模型 首先由情况引入首先由情况引入Lagrange系数系数 ，结构，结构Lagrange函数：函数：第49页 Fisher方法基本思想：方法基本思想：把把 维空间全部模式投影到一条过原点直线上，就能够维空间全部模式投影到一条过原点直线上，就能够把维数压缩到把维数压缩到1。过原点直线有没有数条，投影到那条直线好呢？过原点直线有没有数条，投影到那条直线好呢？x1x2第50页 我们目标就是找到这么一条直线，使得模我们目标就是找到这么一条直线，使得模式样本在这条直线上投影最有利于分类。式样本在这条直线上投影最有利于分类。设给定两类模式样本集，设给定两类模式样本集，和和 ，它们它们各有各有 和和 个个 维样本。设维样本。设 为这条直线为这条直线正方向单位向量，正方向单位向量，。将样本集中样本。将样本集中样本向直线投影，对应地得到集合向直线投影，对应地得到集合 和和 。每个。每个 就是就是 在单位向量在单位向量 上投影。上投影。有：有：这么，就得到了一个一维样本集合，样本数这么，就得到了一个一维样本集合，样本数量为量为 第51页下面要处理问题是什么？下面要处理问题是什么？确定最好投影方向确定最好投影方向 为了找到最好为了找到最好 ，需要建立一个准则函数，需要建立一个准则函数，这个准则函数要能反应不一样类别模式在这条这个准则函数要能反应不一样类别模式在这条直线上投影分离程度好坏。直线上投影分离程度好坏。在确定建立准则函数之前，先介绍几个相关参在确定建立准则函数之前，先介绍几个相关参数。数。第52页1.在在d维维X空间空间（1）各类样本均值向量）各类样本均值向量（2）样本类内离散度，总类内离散度）样本类内离散度，总类内离散度 第53页（3）样本类间离散度）样本类间离散度第54页2.在一维在一维Y空间空间（1）各类样本均值）各类样本均值（2）样本类内离散度，总类内离散度）样本类内离散度，总类内离散度 第55页 我们希望投影后，在一维我们希望投影后，在一维Y空间两类样本尽可空间两类样本尽可能分得开一些，即能分得开一些，即 （1）两类样本离得越远越好）两类样本离得越远越好,也就是，两类均值也就是，两类均值之差之差 越大越好，越大越好，（2）各类样本内部越密集越好，也就是，类内）各类样本内部越密集越好，也就是，类内离散度越小越好，离散度越小越好，越小越好。越小越好。所以，能够结构准则函数为：所以，能够结构准则函数为：第56页 我们目标是使我们目标是使 尽可能大尽可能大 作为投影作为投影方向，但在上式中不显含方向，但在上式中不显含 ，所以，要将，所以，要将 变成变成 显函数。显函数。第57页准则函数分子项：准则函数分子项：第58页准则函数分母项：准则函数分母项：第59页所以，准则函数所以，准则函数 可改写为：可改写为：(2.43)这就是这就是Rayleigh比，它有以下性质：比，它有以下性质：（1）是一个实数。是一个实数。（2）极值与大小无关，只与极值与大小无关，只与 方向相关。方向相关。所以，所以，能够用能够用Lagrange乘数法求极值。乘数法求极值。由性质由性质(2)，可令式，可令式(2.43)分母为非零常数，即分母为非零常数，即第60页结构结构Lagrange函数函数 极大值条件为：极大值条件为：即即 假如假如 非奇异，左乘非奇异，左乘 ，则有则有 解这个式子，就是求矩阵解这个式子，就是求矩阵 本征值。本征值。第61页考虑到我们求解问题特殊性（考虑到我们求解问题特殊性（只确定方向只确定方向），），其中其中 是常数，所以是常数，所以 总是在总是在 方向上。从而方向上。从而 所以所以略去百分比因子略去百分比因子 ，它不影响直线方向，它不影响直线方向，得：得：第62页 这就是使准则函数这就是使准则函数 极大解。极大解。就是就是使模式样本投影在类间最分散，类内最集使模式样本投影在类间最分散，类内最集中最优解。有了中最优解。有了 后，得后，得 就可将各样本由维空间投影到一维空间，就可将各样本由维空间投影到一维空间，即直线上，变成一维样本，它们给出很好即直线上，变成一维样本，它们给出很好分类结果。分类结果。这类方法有一定不足：这类方法有一定不足：v只对准则函数最优；只对准则函数最优；v没有利用样本分布信息，错误概率不能到没有利用样本分布信息，错误概率不能到达最小。达最小。第63页2.8 2.8 支持向量机支持向量机 Support Vector Machine SVMSupport Vector Machine SVM 回顾：用线性判别函数方法处理分类问题方法回顾：用线性判别函数方法处理分类问题方法1.思绪思绪（1）训练样本集）训练样本集 特征空间划分特征空间划分 决议面决议面 线性判别线性判别函数函数（2）待识别模式）待识别模式 判别判别2.问题关键：问题关键：求线性判别函数权向量求线性判别函数权向量3.求解方法：感知准则函数，梯度下降法，固定增量法求解方法：感知准则函数，梯度下降法，固定增量法求得权向量求得权向量=确定了特征空间两类分界面（决议面）确定了特征空间两类分界面（决议面）第64页一一.最优分界面最优分界面 从线性判别函数讨论中，我们已经知道，从线性判别函数讨论中，我们已经知道，对于线性可分两类样本，总能够找到一个分对于线性可分两类样本，总能够找到一个分界面，将两类样本正确分类，而且，这么分界面，将两类样本正确分类，而且，这么分界面不是唯一。界面不是唯一。第65页H1和和H2都能够将两类训练样本正确分类，不过，对于训练都能够将两类训练样本正确分类，不过，对于训练样本以外样本，以哪个作为分界面，分类效果更加好呢？样本以外样本，以哪个作为分界面，分类效果更加好呢？H1H2第66页因为：因为：H2产生错误分类可能性更小。产生错误分类可能性更小。这就提出了分类器设计中一个很主要问题：这就提出了分类器设计中一个很主要问题：分类器通用性分类器通用性，也称，也称分类器推广能力分类器推广能力即：即：用训练样本设计分类器，对训练样本以外样本用训练样本设计分类器，对训练样本以外样本能够正确分类能力。能够正确分类能力。哪一个分界面能够使分类器含有最好通用性？哪一个分界面能够使分类器含有最好通用性？第67页 H1是两类各自最近样本距离相同分界面，是两类各自最近样本距离相同分界面，H2也也是两类各自最近样本距离相同分界面是两类各自最近样本距离相同分界面.H1H2第68页最优分界面：最优分界面：在样本空间中，使两类样本正确分类，而且在样本空间中，使两类样本正确分类，而且两类样本分开间隔最大分界面为最优分界面。两类样本分开间隔最大分界面为最优分界面。最优分界面能够使分类器含有最好通用性最优分界面能够使分类器含有最好通用性（推广能力）。（推广能力）。怎样求最优分界面？怎样求最优分界面？第69页 二二.支持向量支持向量对于给定线性可分训练样本集，对于给定线性可分训练样本集，假如假如 则则 假如假如 则则 能够得到分界面。能够得到分界面。因为两类样本之间总有间隔存在，所以能够因为两类样本之间总有间隔存在，所以能够有：有：假如假如 则则 假如假如 则则 其中其中 是一个正数。是一个正数。第70页为了方便，训练样本集样本用为了方便，训练样本集样本用二元对二元对来表示：来表示：其中其中 和和 分别是样本模式向分别是样本模式向量和它对应类别表示，量和它对应类别表示，假定当假定当 时，时，。而当。而当 时时 。设给定有穷训练样本集能够被设给定有穷训练样本集能够被超平面超平面 正确分开。正确分开。使每类离开分界超平面最近样本向量与超平面之使每类离开分界超平面最近样本向量与超平面之间距离最大，位于间隔中间超平面是最优。间距离最大，位于间隔中间超平面是最优。第71页我们已经知道，在模式向量空间，任何一个我们已经知道，在模式向量空间，任何一个模式向量到决议面距离为：模式向量到决议面距离为：对于决议面方程对于决议面方程 ，和和 并不是唯一并不是唯一。第72页构想：能够将构想：能够将 和和 进行某种百分比缩放，总能进行某种百分比缩放，总能够找到一个够找到一个 和和 ，使，使 到决议面距离最小，到决议面距离最小，为为 ，这么，两类模式分类规则能够写成：这么，两类模式分类规则能够写成：合并这两个式子，写成：合并这两个式子，写成：第73页这时两类模式间隔距离为：这时两类模式间隔距离为：为了使间隔最大，应该使为了使间隔最大，应该使 最小，等价于最小，等价于使使 最小，最小，所以，使所以，使 最小，且满足最小，且满足分界面就是最优分界面，距离最优分界面最分界面就是最优分界面，距离最优分界面最近模式向量就是近模式向量就是支持向量支持向量。能够看出，寻找支持向量，就是寻找最优分能够看出，寻找支持向量，就是寻找最优分界面。界面。第74页 设目标函数为：设目标函数为：将寻找最优分界面问题转化为有约束优化问题：将寻找最优分界面问题转化为有约束优化问题：怎样求解？怎样求解？第75页 结构结构Lagrange函数：函数：其中其中 为为Lagrange乘子，乘子，第76页 到达极值必要条件为：到达极值必要条件为：(1),得得(2),得得 而对于最优分界面，解而对于最优分界面，解 必须满足：必须满足：(1)(2)最优分界面解权向量是训练样本集中模式向量线性组最优分界面解权向量是训练样本集中模式向量线性组合合.第77页 对于约束条件对于约束条件,等号在支持向量下才成立，也等号在支持向量下才成立，也就是说，只有支持向量能够在就是说，只有支持向量能够在 展开中含有展开中含有非零系数非零系数 ，所以有，所以有 其中其中 是支持向量集。是支持向量集。怎样知道哪些样本是支持向量呢怎样知道哪些样本是支持向量呢?第78页求最优分类超平面问题：求最优分类超平面问题：等等价价转转换换对偶问题对偶问题第79页 这是一个二次函数优化问题，存在唯一解，解中这是一个二次函数优化问题，存在唯一解，解中不为零不为零 所对应样本就是所对应样本就是支持向量支持向量。求得支持向量后，可求得权向量求得支持向量后，可求得权向量 和和 式中式中 表示属于第一类支持向量，表示属于第一类支持向量，而而 表示属于第二类支持向量。表示属于第二类支持向量。这么，由这么，由 和和 就确定了最优超平面。就确定了最优超平面。第80页 举例：举例：设有四个两类样本，设有四个两类样本，类有两个样本：类有两个样本：类有两个样本：类有两个样本：求最优分界面。求最优分界面。第81页对偶问题：对偶问题：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，第82页求求 极值极值。令令 矛盾矛盾是凹凸函数是凹凸函数原原因因第83页利用利用 支持向量为：支持向量为：不满足要求不满足要求第84页利用利用 确定确定最优分界面：最优分界面：第85页三三.支持向量机支持向量机1.广义线性判别函数广义线性判别函数x1x2第86页 对图示两类分布，能够用一个对图示两类分布，能够用一个4次多项式决议函次多项式决议函数对其分类。数对其分类。这是一个两维函数这是一个两维函数第87页 做特征空间变换，令做特征空间变换，令 则有则有第88页 可将一个在低维空间很复杂决议面，变换成一可将一个在低维空间很复杂决议面，变换成一个高维空间线性函数：个高维空间线性函数：称之为称之为广义线性判别函数广义线性判别函数。即。即 在变换后空间在变换后空间中是线性，在原空间是非线性。中是线性，在原空间是非线性。普通来说，对于任意高次判别函数普通来说，对于任意高次判别函数 ，都能够经过，都能够经过适当变换变成广义线性判别函数适当变换变成广义线性判别函数 ，利用线性判别函数，利用线性判别函数简单性来处理复杂问题。简单性来处理复杂问题。不过，这种变换带来一个很严重问题：不过，这种变换带来一个很严重问题：维数大大增加，例中维数大大增加，例中2维变成维变成15维维 维数增加造成所需样本数呈指数增加。维数增加造成所需样本数呈指数增加。第89页2.支持向量机支持向量机 在求最优分界面时在求最优分界面时,最优分界面只与支持最优分界面只与支持向量相关向量相关,优化函数优化函数 只需要计算训练样本内积只需要计算训练样本内积,而映射到高维空而映射到高维空间中也只需内积运算。依据泛函理论，只间中也只需内积运算。依据泛函理论，只要一个核函数要一个核函数 (kernel)满足满足Mercer条件，它就对应某个变换空间中内条件，它就对应某个变换空间中内积。积。第90页 所以，只要找到适当核函数，就能够实现某个所以，只要找到适当核函数，就能够实现某个线性变换后线性分类。线性变换后线性分类。寻优函数为：寻优函数为：分类函数为：分类函数为：支持向量机基本思想：支持向量机基本思想：经过非线性变换将输入空间变换到一个高维空经过非线性变换将输入空间变换到一个高维空间，然后在这个变换空间中求最优分界面，实现间，然后在这个变换空间中求最优分界面，实现分类。这种非线性变换是经过定义适当内积函数，分类。这种非线性变换是经过定义适当内积函数，用内积运算实现。（无须真进行这种非线性变换）用内积运算实现。（无须真进行这种非线性变换）支支持持向向量量机机第91页支持向量机方法优势是什么？支持向量机方法优势是什么？第92页