第三章线性判别函数

1、第三章线性判别函数1第三章 线性判别函数 3.1 引言 3.2 线性判别函数和决策面 3.3 广义线性判别函数 3.4 两类线性可分情况 3.5 梯度下降算法 3.6 感知准则函数最小化 3.7 3.8 最小平方误差方法第三章线性判别函数2引 言 贝叶斯公式中需要知道类条件概率密度函数和先验概率 在实际中，我们通常只能得到有限数目的样本 因此，分类器的设计过程可以分为两步： 利用样本集估计先验概率和类条件概率密度函数 将估计值代入贝叶斯公式，完成分类器设计第三章线性判别函数3引 言 先验概率的估计： 比较容易。 比如，癌细胞识别中，可以根据细胞病理检查的统计结果得到正常与异常的大致比例。 密度

2、函数的估计： 非常困难。只能根据样本进行估计。第三章线性判别函数4引 言解决的思路： 迎难而上 参数估计：假定密度函数是种分布，即分布形式已知但参数未知，通过训练样本估计分布的参数 比如，假定分布为正态，可以利用样本估计其均值和方差。 非参数方法：分布的形式未知，直接通过样本估计密度函数的形式和参数 另辟蹊径第三章线性判别函数5引 言 在对正态分布下贝叶斯决策理论的讨论中，我们看到，在正态假设下，可以得到一些简单方便的判别函数。如：最小距离，线性判别函数。 我们可以绕过对密度的估计，直接得到判别函数 在所有的判别函数中，最简单的是线性判别函数第三章线性判别函数6引 言线性判别函数的优点： 特定

3、条件下为最优 正态、独立、等方差，可以通过对特征的选择来达到相对简单，容易实现 牺牲精度，享受简便性能和代价的折中是复杂方法的基础 线性判别函数中的基本方法可以推广到非线性判别函数中第三章线性判别函数7引 言思路： 假定判别函数的形式已知：线性判别函数 未知的是判别函数的参数 参数由样本约束：合适的参数将使错误率最小 通过训练样本确定其参数：找出使训练样本错误率最小的参数最优化方法第三章线性判别函数8引 言设计线性分类器的主要步骤： 根据需求确定准则函数，使准则函数的值反映分类器的性能（如错误率），其极值解对应最优决策 用最优化技术求出准则函数的极值解 将该极值解代入线性判别函数的表达式中，完

4、成分类器的设计第三章线性判别函数9线性判别函数和决策面 线性判别函数是x各分量的线性组合：g(x) = wtx + w0 其中 x = (x1, x2, , xd)t 是d维特征向量 w = (w1, w2, , wd)t 是d维权向量（weight vector） w0 为常数，称为偏置 （bias）或阈值权（threshold weight）第三章线性判别函数10线性判别函数和决策面 通常，我们需要设计c个判别函数，分别与c个类别相对应 先来看两类的情况： Decide 1 if g(x) 0 and 2 if g(x) -w0 and 2 otherwise第三章线性判别函数11线性判别

5、函数和决策面第三章线性判别函数12线性判别函数和决策面 方程 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的负侧。第三章线性判别函数13线性判别函数和决策面判别函数g (x)是特征空间中某点到超平面距离的一种代数度量。如图所示：第三章线性判别函数14线性

6、判别函数和决策面可以将x表示成其中 xp： 是x在H上的投影向量 r： 是x到H的垂直距离 w/|w|： 是w方向上的单位向量 第三章线性判别函数15线性判别函数和决策面代入g (x) ：或写作：00( )()|tpttpgrwwrrwxw xww ww xww( )|gr xw第三章线性判别函数16线性判别函数和决策面 若x为原点，则 g(x) = w0 因此原点到超平面H的距离为 r0 = w0 / |w| 总之，利用线性判别函数进行分类，就是用一个超平面把特征空间分割成两个决策区域。 超平面的方向由权向量w确定。 超平面的位置由阈值权w0确定。 判别函数正比于x到超平面的代数距离（带正负

7、号）。 当x在超平面正侧时， g(x) 0 ；在负侧时， g(x) gj(x)，则把 x 归为 i 类；如果gi(x) = gj(x) ，则拒识。 这样得到的分类器称为“线性机器”(linear machine)。 线性机器把特征空间分成c个决策区域，当x在Ri中时， gi(x)具有最大值。 如果Ri和Ri是相邻的，则它们的分界就是超平面H的一部分，其定义为gi(x) = gj(x) 。0( ) tiiigw i=1,.,cxw x第三章线性判别函数20线性判别函数和决策面共有c个决策区域，实际中，超平面的个数往往会少于c(c-1)/2个。如图所示：第三章线性判别函数21广义线性判别函数 线性

8、判别函数可以写成 通过增加高次项，可以得到二次判别函数（quadratic discriminant function)01( )diiigww xx0111( )dddiiijijiijgww xw x xx第三章线性判别函数22广义线性判别函数继续增加更高次的项，得到多项式判别函数(polynomial discriminant function)。这可以看作对某一判别函数做级数展开，然后取其截尾逼近。由此得到广义线性判别函数(generalized linear discriminant function)或( )tgxa y第三章线性判别函数23广义线性判别函数 在 中，yi(x)可以

9、是x的任意函数，通过选择合适的y，就可以逼近任意复杂的判别函数，得到的判别函数并不是x的线性函数，但却是y的线性函数。 虽然理论上我们可以通过这种方式来解决非线性问题，但这种变换却使得维数大大增加，陷入“维数灾难”。( )tgxa y第三章线性判别函数24广义线性判别函数 其中一个特例却是有用的，我们可以把线性判别函数写成如下的形式 式中 y称为增广样本向量，a称为增广权向量。 这样做带来的好处是将两个参数w和w0合并成一个参数a。010( )ddtiiiiiigww xa yxa y第三章线性判别函数25两类线性可分情况 线性可分 设有一个包含n个样本的集合，y1,y2,yn，其中某些样本为

10、1类，某些为2类。如果有一个线性机器能把每个样本正确分类，即如果存在一个权向量a，使得对于任何y 1都有aty0，而对于任何y 2都有aty 0。 因此，如果我们令 则就可以不管样本原来的类别标志，只要找一个对全部样本yn都满足atyn0的权向量a即可。上述过程称为样本的规范化， yn叫规范化增广样本向量，在后面仍用yn来表示它。120,0,tiitjja yya yy对于一切对于一切12,iinjjyyyyy对于一切对于一切第三章线性判别函数27两类线性可分情况 解向量和解区 在线性可分的情况下，满足atyn0的权向量称为解向量，记为a*。 解向量往往不止一个，而是由无穷多个解向量组成一个区

11、域，这样的区域称为解区。第三章线性判别函数28两类线性可分情况 对解区的限制 对解区加以限制的目的在于使得解向量更可靠。通常认为，越靠近解区中间的解向量，似乎越能对新的样本正确分类。因此，我们可以引入余量b0，并寻找满足atynb的解向量a*。 实际上，我们主要关心的是求解权向量的算法不至于收敛到解区域的边界上。显然，余量的引入可以很好地避免这个问题。第三章线性判别函数29两类线性可分情况引入余量的解区第三章线性判别函数30梯度下降算法 求解线性不等式组atyi0的方法： 定义一个准则函数J(a) ，使得当a是解向量时， J(a)为最小。这样就将问题简化为一个标量函数的极小化问题，通常可以用梯

12、度下降法来解决。 梯度下降法的基本步骤：首先任意选择一个初始的权向量a(1)，计算梯度向量J(a(1)，然后自a(1)沿梯度负方向移动一段距离得到下一个值a(2) ，反复迭代，最终收敛到一个使J(a)极小化的解上。第三章线性判别函数31梯度下降算法 取初值a(1) 迭代 其中， 是正的比例因子，是用于设定步长的“学习率” (learning rate)。(1)( )( )( ( )kkkJkaaa第三章线性判别函数32梯度下降算法第三章线性判别函数33感知准则函数最小化 定义感知准则函数 其中 是被a错分的样本集合。如果没有样本被错分，我们定义Jp(a)为0。 由于当atyi b for al

13、l k return aEnd第三章线性判别函数41感知准则函数最小化批处理变增量感知机算法第三章线性判别函数42松弛算法为了使搜索表面更为平滑，我们可以采用二次的准则函数其梯度是连续的，但存在两个问题 有可能得到无意义的解a=0 模值大的样本对其影响太大第三章线性判别函数43松弛算法改进后，得梯度迭代公式第三章线性判别函数44松弛算法批处理余量松弛算法 第三章线性判别函数45松弛算法单样本余量松弛算法第三章线性判别函数46最小平方误差方法 前面的准则函数依然存在两个问题 只能利用被错分的样本 实际上是在解线性不等式组，不如解线性方程组方便 为此，我们可以引入余量bi， bi是任意取定的正常数，这样就可以将一个求解线性不等式组atyi0的问题转化为求解线性方程组atyi= bi ，同时，利用平方误差来定义准则函数，无论是否错分只要有误差就进行调整。第三章线性判别函数47最小平方误差方