《3第三章线性判别函数.ppt》由会员分享，可在线阅读，更多相关《3第三章线性判别函数.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 线性判别函数3.1 引言3.2 线性判别函数和决策面3.3 广义线性判别函数3.4 两类线性可分情况3.5 梯度下降算法3.6 感知准则函数最小化3.7 松弛算法3.8 最小平方误差方法1第三章 线性判别函数 郝红卫引 言贝叶斯公式中需要知道类条件概率密度函数和先验概率在实际中，我们通常只能得到有限数目的样本因此，分类器的设计过程可以分为两步：利用样本集估计先验概率和类条件概率密度函数将估计值代入贝叶斯公式，完成分类器设计2第三章 线性判别函数 郝红卫引 言先验概率的估计：比较容易。比如，癌细胞识别中，可以根据细胞病理检查的统计结果得到正常与异常的大致比例。密度函数的估计：非常困难。只
2、能根据样本进行估计。3第三章 线性判别函数 郝红卫引 言解决的思路：迎难而上参数估计：假定密度函数是种分布，即分布形式已知但参数未知，通过训练样本估计分布的参数 比如，假定分布为正态，可以利用样本估计其均值和方差。非参数方法：分布的形式未知，直接通过样本估计密度函数的形式和参数另辟蹊径4第三章 线性判别函数 郝红卫引 言在对正态分布下贝叶斯决策理论的讨论中，我们看到，在正态假设下，可以得到一些简单方便的判别函数。如：最小距离，线性判别函数。我们可以绕过对密度的估计，直接得到判别函数在所有的判别函数中，最简单的是线性判别函数5第三章 线性判别函数 郝红卫引 言线性判别函数的优点：特定条件下为最优
3、 正态、独立、等方差，可以通过对特征的选择来达到相对简单，容易实现 牺牲精度，享受简便性能和代价的折中是复杂方法的基础 线性判别函数中的基本方法可以推广到非线性判别函数中6第三章 线性判别函数 郝红卫引 言思路：假定判别函数的形式已知：线性判别函数未知的是判别函数的参数参数由样本约束：合适的参数将使错误率最小通过训练样本确定其参数：找出使训练样本错误率最小的参数最优化方法7第三章 线性判别函数 郝红卫引 言设计线性分类器的主要步骤：根据需求确定准则函数，使准则函数的值反映分类器的性能（如错误率），其极值解对应最优决策用最优化技术求出准则函数的极值解将该极值解代入线性判别函数的表达式中，完成分类
4、器的设计8第三章 线性判别函数 郝红卫线性判别函数和决策面线性判别函数是x各分量的线性组合：g(x)=wtx+w0 其中 x=(x1,x2,xd)t 是d维特征向量 w=(w1,w2,wd)t 是d维权向量（weight vector）w0 为常数，称为偏置（bias）或阈值权（threshold weight）9第三章 线性判别函数 郝红卫线性判别函数和决策面通常，我们需要设计c个判别函数，分别与c个类别相对应先来看两类的情况：Decide 1 if g(x)0 and 2 if g(x)-w0 and 2 otherwise10第三章 线性判别函数 郝红卫线性判别函数和决策面11第三章 线
5、性判别函数 郝红卫线性判别函数和决策面 方程 g(x)=0 定义了一个决策面，它将分属两类的样本分开。假设x1和x2都在决策面H上，则有：wtx1+w0=wtx2+w0 wt(x1-x2)=0 这表明，w和超平面H上任一向量正交，即w是H的法向量。超平面H将特征空间分成两部分，即对1类的决策域R1和对2类的决策域R2。由于当x在R1中时，g(x)为正，所以法向量是指向R1的，故称R1中的x在H的正侧，称R2中的x在H的负侧。12第三章 线性判别函数 郝红卫线性判别函数和决策面判别函数g(x)是特征空间中某点到超平面距离的一种代数度量。如图所示：13第三章 线性判别函数 郝红卫线性判别函数和决策
6、面可以将x表示成其中 xp：是x在H上的投影向量 r：是x到H的垂直距离 w/|w|：是w方向上的单位向量 14第三章 线性判别函数 郝红卫线性判别函数和决策面代入g(x)：或写作：15第三章 线性判别函数 郝红卫线性判别函数和决策面 若x为原点，则 g(x)=w0 因此原点到超平面H的距离为 r0=w0/|w|总之，利用线性判别函数进行分类，就是用一个超平面把特征空间分割成两个决策区域。超平面的方向由权向量w确定。超平面的位置由阈值权w0确定。判别函数正比于x到超平面的代数距离（带正负号）。当x在超平面正侧时，g(x)0；在负侧时，g(x)gj(x)，则把 x 归为 i 类；如果gi(x)=
7、gj(x)，则拒识。这样得到的分类器称为“线性机器”(linear machine)。线性机器把特征空间分成c个决策区域，当x在Ri中时，gi(x)具有最大值。如果Ri和Ri是相邻的，则它们的分界就是超平面H的一部分，其定义为gi(x)=gj(x)。19第三章 线性判别函数 郝红卫线性判别函数和决策面共有c个决策区域，实际中，超平面的个数往往会少于c(c-1)/2个。如图所示：20第三章 线性判别函数 郝红卫广义线性判别函数 线性判别函数可以写成 通过增加高次项，可以得到二次判别函数（quadratic discriminant function)21第三章 线性判别函数 郝红卫广义线性判别函
8、数继续增加更高次的项，得到多项式判别函数(polynomial discriminant function)。这可以看作对某一判别函数做级数展开，然后取其截尾逼近。由此得到广义线性判别函数(generalized linear discriminant function)或22第三章 线性判别函数 郝红卫广义线性判别函数在 中，yi(x)可以是x的任意函数，通过选择合适的y，就可以逼近任意复杂的判别函数，得到的判别函数并不是x的线性函数，但却是y的线性函数。虽然理论上我们可以通过这种方式来解决非线性问题，但这种变换却使得维数大大增加，陷入“维数灾难”。23第三章 线性判别函数 郝红卫广义线性判
9、别函数 其中一个特例却是有用的，我们可以把线性判别函数写成如下的形式 式中 y称为增广样本向量，a称为增广权向量。这样做带来的好处是将两个参数w和w0合并成一个参数a。24第三章 线性判别函数 郝红卫两类线性可分情况线性可分 设有一个包含n个样本的集合，y1,y2,yn，其中某些样本为1类，某些为2类。如果有一个线性机器能把每个样本正确分类，即如果存在一个权向量a，使得对于任何y 1都有aty0，而对于任何y 2都有aty 0。因此，如果我们令 则就可以不管样本原来的类别标志，只要找一个对全部样本yn都满足atyn0的权向量a即可。上述过程称为样本的规范化，yn叫规范化增广样本向量，在后面仍用
10、yn来表示它。26第三章 线性判别函数 郝红卫两类线性可分情况解向量和解区 在线性可分的情况下，满足atyn0的权向量称为解向量，记为a*。解向量往往不止一个，而是由无穷多个解向量组成一个区域，这样的区域称为解区。27第三章 线性判别函数 郝红卫两类线性可分情况对解区的限制 对解区加以限制的目的在于使得解向量更可靠。通常认为，越靠近解区中间的解向量，似乎越能对新的样本正确分类。因此，我们可以引入余量b0，并寻找满足atynb的解向量a*。实际上，我们主要关心的是求解权向量的算法不至于收敛到解区域的边界上。显然，余量的引入可以很好地避免这个问题。28第三章 线性判别函数 郝红卫两类线性可分情况引
11、入余量的解区29第三章 线性判别函数 郝红卫梯度下降算法求解线性不等式组atyi0的方法：定义一个准则函数J(a)，使得当a是解向量时，J(a)为最小。这样就将问题简化为一个标量函数的极小化问题，通常可以用梯度下降法来解决。梯度下降法的基本步骤：首先任意选择一个初始的权向量a(1)，计算梯度向量J(a(1)，然后自a(1)沿梯度负方向移动一段距离得到下一个值a(2)，反复迭代，最终收敛到一个使J(a)极小化的解上。30第三章 线性判别函数 郝红卫梯度下降算法取初值a(1)迭代 其中，是正的比例因子，是用于设定步长的“学习率”(learning rate)。31第三章 线性判别函数 郝红卫梯度下
12、降算法32第三章 线性判别函数 郝红卫感知准则函数最小化 定义感知准则函数 其中 是被a错分的样本集合。如果没有样本被错分，我们定义Jp(a)为0。由于当atyi b for all k return aEnd40第三章 线性判别函数 郝红卫感知准则函数最小化批处理变增量感知机算法41第三章 线性判别函数 郝红卫松弛算法为了使搜索表面更为平滑，我们可以采用二次的准则函数其梯度是连续的，但存在两个问题有可能得到无意义的解a=0模值大的样本对其影响太大42第三章 线性判别函数 郝红卫松弛算法改进后，得梯度迭代公式43第三章 线性判别函数 郝红卫松弛算法批处理余量松弛算法 44第三章 线性判别函数
13、郝红卫松弛算法单样本余量松弛算法45第三章 线性判别函数 郝红卫最小平方误差方法 前面的准则函数依然存在两个问题只能利用被错分的样本实际上是在解线性不等式组，不如解线性方程组方便 为此，我们可以引入余量bi，bi是任意取定的正常数，这样就可以将一个求解线性不等式组atyi0的问题转化为求解线性方程组atyi=bi，同时，利用平方误差来定义准则函数，无论是否错分只要有误差就进行调整。46第三章 线性判别函数 郝红卫最小平方误差方法由此可得新的准则函数为梯度迭代公式47第三章 线性判别函数 郝红卫最小平方误差方法LMS(least-mean-squared)算法48第三章 线性判别函数 郝红卫最小平方误差方法LMS算法是后续机器学习算法的基础感知机模型是多层感知机网络的基础为解决非线性分类问题，感知机扩展为多层感知机；LMS算法改进成BP算法。多层感知机网络及其BP算法，构成了应用最为广泛、功能强大的神经网络模型。49第三章 线性判别函数 郝红卫讨论50第三章 线性判别函数 郝红卫