模式识别课件Ch5part1ok.pptVIP

Chapter 5: 线性判别函数 基本概念 Fisher线性判别 感知器准则函数 松弛算法 最小平方误差准则函数 支持向量机 多类问题 分段线性判别函数 为什么要研究线性判别函数？ 形式最简单的判别函数，相对容易分析和计算。 在一定条件下能够实现最优分类（比如通过适当的选择特征提取方法，可以使得各个高斯函数具有相等的协方差矩阵）。 即使不是最优，我们也愿意牺牲一些分类准确率，以换取处理简便的优点。 最近，应用核方法发展出相应的非线性判别函数。 5.1 基本概念 线性判别函数(linear discriminant function) g(x)=wTx+w0 w称为权向量(weight vector)，w0称为阈值权(threshold weight)或偏置(bias) 对具有上述形式判别函数的两类线性分类器， 如果g(x) 0 则判定?1 ，如果g(x) 0 则判定?2 ? 如果内积wtx -w0则判定?1，反之为?2 g(x) = 0 拒绝 方程g(x) = 0 定义了一个决策面，把归类于?1的点与归类于?2的点分开 当g(x)是线性时，这个平面被称为超平面(hyperplane) 通常，一个超平面H将特征空间分成两个半空间，即对应于?1类的决策域R1和对应于?2类的决策域R2。决策面的法向量w指向R1。 判别函数g(x)是特征空间中某点x到超平面的距离的一种代数度量。特别地， 线性判别函数利用一个超平面决策面把特征空间分割成两个区域。超平面的方向由法向量w确定，它的位置由阈值权w0确定。如果w0=0，那么具有齐次形式，说明超平面H通过原点。 多类问题 定义c个判别函数 如果对一切i≠j有gi(x) gj(x)，则把x归为?i类；如果gi(x) = gj(x)，则拒绝判定。 线性机(linear machine)，它把特征空间分为c个决策域Ri，当x在Ri中时，gi(x)具有最大值。如果Ri和Rj相邻，则它们的分界就是超平面的一部分Hij。 gi(x) = gj(x) (wi – wj)tx + (wi0 – wj0) = 0 wi – wj是Hij的法向量， 线性机的决策域是凸的，限制了分类器的适应性和精确性。 特别地，每一个决策域是单连通的，对条件概率密度P(x|?i)为单峰的问题设计线性机是很适合的。 注意，对某些单峰分布线性判别函数给出很好的结果，而对另一些单峰分布给出很差的分类结果。 广义线性判别函数 a叫做广义权向量 一般来说，对于任意高次判别函数g(x)都可以通过适当的变换，化为广义线性判别函数来处理。 aty不是x的线性函数，但却是y的齐次线性函数。aty=0在Y空间确定了一个通过原点的超平面。 维数灾难：一个完整的二次型判别函数包含项的个数是(d+1)(d+2)/2。 广义线性判别函数的特例 其中 y称为增广特征向量，a称为增广权向量。 x空间上的所有样本间距离在变换后保持不变；得到的y向量都在d维子空间中。 两类线性可分的情况 有一个包含n个样本的集合{y1，y2，…，yn} 一些标记为?1，另一些标记为?2 用样本来确定判别函数g(x)=aty的权向量a 一个很合理的想法是寻找一个能将所有这些样本正确分类的权向量。如果这个权向量存在，这些样本就被称为“线性可分”的（linearly separable） 经过“规范化”(normalization)，问题转变为寻找一个对所有样本都有atyi0的权向量a。a被称为“解向量”(solution vector) 解向量如果存在的话，通常不唯一。 引入附加条件对解向量进行限制： 找到一个单位长度的解向量，使得从样本到分类平面的最小距离达到最大。 引入间隔(margin) b0，使得新的解区在原解区中，且和原解区边界隔开一段距离，这样递归过程能够不收敛到边界点上。背后的动机：位于解区“中间”位置的解向量更能将新的测试样本正确地分类。 如何得到解向量a：定义一个准则函数J(a)，使J(a)最小的a即为解。问题简化为标量函数的极小化问题，通常用梯度下降法来解决。 梯度下降法的原理 其中η(k)是设定步长的学习率(learning rate) 如何选择学习率η(k) η(k)如果太小，收敛非常慢；如果太大，可能过冲(overshoot)，甚至发散