《模式识别第6讲线性判别函数2汇编》由会员分享，可在线阅读，更多相关《模式识别第6讲线性判别函数2汇编（50页珍藏版）》请在金锄头文库上搜索。
1、 模式识别 授课教师 薛耀红 xueyh 第6讲 线性判别函数（2） 优化算法（补充知识） 1.梯度（下降）法 / 最速下降法 2.共轭梯度法 1. 1. 梯度梯度( (下降下降) )法（最速下降法法（最速下降法 ） 基本原理 无约束最优化问题 u如何产生下降方向Pk? （1）给定初始近似点x(0)及精度O若 ，则x(0)即为近似极小点。 （2）若 ，求步长0,并计算 算法步骤 （3） 若 ，则 x(k) 即为求的近似解； 若 ，则求步长k，并确定下一个近似点。 如此继续，直至达到要求的精度为止。 若f(x)具有二阶连续偏导数，在x(k)作 的泰勒展开： 对求导并令其等于零，则得近似最佳步长
2、2. 2. 共轭梯度法共轭梯度法 共轭方向和共轭方向法 共轭是正交的推广 。 定理1 设A为nn对称正定矩阵，P(1)， P(2) ， ，P(n) ，为A共 轭的非零向量，则这一组向量线性独立。 几何意义 正定二次函数极小问题 定理2 共轭方向法 如何选取一组共轭方向？ 共轭梯度法 以下分析算法的具体步骤。 一般函数的共轭梯度法 本节课主要内容 uu最小错分样本数准则最小错分样本数准则 共轭梯度法共轭梯度法 搜索法搜索法 uu最小平方误差准则函数最小平方误差准则函数( (MSE)MSE) 1 1 最小错分样本数准则最小错分样本数准则 uu感知准则函数及其梯度下降算法感知准则函数及其梯度下降算法
3、只适用于线只适用于线 性可分情况。对于线性不可分情况，迭代过程性可分情况。对于线性不可分情况，迭代过程 永远不会终结，即算法不收敛。永远不会终结，即算法不收敛。 x x1 1 X X4 4 (1,1)(1,1) X X2 2 (1,0)(1,0) X X1 1 (0,0)(0,0) X X3 3 (0,1)(0,1) x x2 2 x x1 1 X X4 4 (1,1)(1,1) X X2 2 (1,0)(1,0) X X1 1 (0,0)(0,0) X X3 3 (0,1)(0,1) x x2 2 uu在实际问题中往往无法事先知道样在实际问题中往往无法事先知道样 本集是否线性可分，因此，希望
4、找到本集是否线性可分，因此，希望找到 一种既适用于线性可分情况，又适用一种既适用于线性可分情况，又适用 于线性不可分情况的算法。于线性不可分情况的算法。 uu这种算法具有特点：这种算法具有特点： 对于线性可分问题，可以得到一个如对于线性可分问题，可以得到一个如 感知准则函数那样的感知准则函数那样的解向量解向量a*a* 对于线性可分问题，使得对两类样对于线性可分问题，使得对两类样 本集做到将全部样本正确分类；本集做到将全部样本正确分类； 对于线性不可分问题，则得到一个对于线性不可分问题，则得到一个 使两类样本集使两类样本集错分数目最少错分数目最少的的权向权向 量量a a，记为记为a*a*。 uu
5、这样的算法准则称为这样的算法准则称为最小错分样本最小错分样本 数准则数准则。 uu目前已提出不少最优化这种准则的目前已提出不少最优化这种准则的 算法，这里仅介绍两种算法。算法，这里仅介绍两种算法。 uu两种算法：解线性不等式组的两种算法：解线性不等式组的共轭共轭 法法/ /搜索法搜索法 uu前者定义的准则为前者定义的准则为( (1 1) )式，后者定式，后者定 义的准则为义的准则为( (2 2) )式；式； uud d维维向量样本集向量样本集 x x 1 1 ，x x 2 2 ，x x N N , ,变成增变成增 广向量广向量样本集样本集 y y 1 1 ，y y 2 2 ，y y N N ,
6、 ,再通过再通过 得到得到规范化增广样本向量规范化增广样本向量，线性判别，线性判别 函数可写作：函数可写作： uu如果存在如果存在权向量权向量a a，使得下式成立使得下式成立 则则yy n n 被正确分类。对单个样本被正确分类。对单个样本yy n n 存存 在线性不等式解。在线性不等式解。 uu设计线性分类器可以看成求一组设计线性分类器可以看成求一组N N 个个线性不等式的解的问题：线性不等式的解的问题： 若不等式组有解，即不等式组存若不等式组有解，即不等式组存 在公共解在公共解( (相一致的情况相一致的情况) )，说明样，说明样 本集是线性可分的，找到这个本集是线性可分的，找到这个解解 向量
7、向量a*a*。 若不等式组无解，即不等式组无若不等式组无解，即不等式组无 公共解公共解( (不一致的情况不一致的情况) )，说明样本，说明样本 集是线性不可分的。集是线性不可分的。 uu在线性不可分的前提下，在线性不可分的前提下，对于对于 任何任何权向量权向量a a，必有某些样本被必有某些样本被 错分类。错分类。 uu寻找一个满足最多数目的不等寻找一个满足最多数目的不等 式的式的权向量权向量a a的问题转变成解线的问题转变成解线 性不等式组的问题。性不等式组的问题。 引入引入余量余量b,其维数为其维数为N, ,数值大于零，数值大于零， 任何实数，使得下列等式成立。任何实数，使得下列等式成立。
8、1 1.1 .1 共轭梯度法共轭梯度法 uu定义的准则为定义的准则为: : uu准则的理解：准则的理解： 如果如果YaYa b b，则，则( (YaYa- -b b) )和和| |YaYa- -b b| |同号，其同号，其 结果结果J Jq1 q1(a) (a)=0=0。 如果存在某些规范化增广样本向量如果存在某些规范化增广样本向量y y i i ， 使得使得y y i i a a0。 y y i i a a0; ; b bi i 是任意给定的正常数。是任意给定的正常数。N N个方程写成书上个方程写成书上 的表达式。的表达式。 样本数样本数N N总是大于维数总是大于维数( (d d+1)+1)
9、 ，因此，因此Y Y是长是长 方阵。一般为列满秩阵。方阵。一般为列满秩阵。 方程个数多于未知数，它为矛盾方程组，方程个数多于未知数，它为矛盾方程组， 通常没有精确解存在。但可以寻找最小二通常没有精确解存在。但可以寻找最小二 乘解。乘解。 定义一个定义一个误差向量误差向量e e 最小平方误差准则函数最小平方误差准则函数 ( (MSE)MSE) Y YT T Y Y是是( (d d+1)+1) ( (d d+1)+1) 方阵。存在逆矩阵。方阵。存在逆矩阵。 解向量解向量a a* *是依赖是依赖向量向量b b。 uu两个结论：两个结论： 若若N N 1 1 个训练样本属于个训练样本属于 1 1, ,
10、N N2 2 个训练样本属于个训练样本属于 2 2 ，取，取b b i i = =N/NN/N 1 1 , ,N=NN=N 1 1 + +N N2 2 (i=1,2,N(i=1,2,N 1 1 ), ), b b i i =N/N=N/N 2 2 ,( ,(i=Ni=N 1 1 +1,+1,N N), ),则在线性可分的情况则在线性可分的情况 下，下，MSEMSE解解与与FisherFisher线性判别函数等价。线性判别函数等价。 若选取全部若选取全部b b i i =1,(i=N=1,(i=N 1 1 +1,+1,N)N)，MSEMSE解与解与 BayesBayes决策解之间的均方误差到达极
11、小。决策解之间的均方误差到达极小。 uu计算（计算（4 4）式伪逆存在问题：）式伪逆存在问题： 要求矩阵要求矩阵 是非奇异的。是非奇异的。 计算量大。计算量大。 uu采用（采用（5 5）式梯度下降法递归求解）式梯度下降法递归求解 uu样本看成无限重复的序列，即样本看成无限重复的序列，即单样本修单样本修 改权向量改权向量，如下式所示，如下式所示: : 其中，其中， 为使得为使得 的样本。的样本。 uu随机随机MSEMSE准则函数及其随机逼近算法准则函数及其随机逼近算法- - -样本看成是随机样本集，权向量求样本看成是随机样本集，权向量求 解也看随机最优化问题。解也看随机最优化问题。 举例 利用MSE求解权向量 x x2 2 x x1 1 X X4 4 (1,1) (1,1) X X3 3 (1,0) (1,0) X X1 1 (0,0) (0,0) X X2 2 (0,1) (0,1)
