模式识别 Pattern Recognition

Presentation on theme: "模式识别 Pattern Recognition"— Presentation transcript:

1 模式识别 Pattern Recognition
IPL 武汉大学电子信息学院 模式识别 Pattern Recognition 第四章 线性判别函数

2 内容目录 模式识别与神经网络 IPL 4.3 感知器准则 4.4 最小平方误差准则 4.5 多类问题 4.6 分段线性判别函数 4.7 讨论
第四章 线性判别函数 4.1 引言 1 4.2 Fisher线性判别 2 4.3 感知器准则 3 4.4 最小平方误差准则 4 4.5 多类问题 5 4.6 分段线性判别函数 6 4.7 讨论 7

3 4.1 引言 分类器 功能结构 基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数 g1 MAX g2 gc
xn a(x) 基于样本的Bayes分类器：通过估计类条件概率密度函数，设计相应的判别函数 最一般情况下适用的“最优”分类器：错误率最小，对分类器设计在理论上有指导意义。 获取统计分布及其参数很困难，实际问题中并不一定具备获取准确统计分布的条件。 训练样本集 样本分布的 统计特征： 概率密度函数 决策规则： 判别函数 决策面方程 第四章 线性判别函数

4 决策边界的估计 Classification is viewed as “learning good decision boundaries” that separate the examples belonging to different classes in a data set. 第四章 线性判别函数

5 决策边界的估计 Specify a parametric form of the decision boundary (e.g., linear or quadratic) . Find the “best” decision boundary of the specified form using a set of training examples. This is done by minimizing a criterion function e.g., “training error” (or “sample risk”) 第四章 线性判别函数

6 直接确定判别函数 基于样本的直接确定判别函数方法： 引言 设定判别函数形式，用样本集确定参数。 使用准则函数，表达分类器应满足的要求。
这些准则的“最优”并不一定与错误率最小相一致：次优分类器。 实例：正态分布最小错误率贝叶斯分类器在特殊情况下，是线性判别函数g(x)=wTx（决策面是超平面），能否基于样本直接确定w? 训练样本集 决策规则： 判别函数 决策面方程 选择最佳准则 第四章 线性判别函数

7 线性判别函数 d维空间中的线性判别函数的一般形式： x是样本向量，即样本在d维特征空间中的描述， w是权向量，w0是一个常数(阈值权)。
引言 d维空间中的线性判别函数的一般形式： x是样本向量，即样本在d维特征空间中的描述， w是权向量，w0是一个常数(阈值权)。 第四章 线性判别函数

8 两类问题的分类决策规则 引言 第四章 线性判别函数

9 线性判别函数的几何意义 If g(x) is linear, the decision boundary is a hyperplane.
The orientation of the hyperplane is determined by w and its location by w0. w is the normal to the hyperplane. If w0=0, the hyperplane passes through the origin. 第四章 线性判别函数

10 线性判别函数的几何意义 g(x) provides an algebraic measure of the distance of x from the hyperplane. specifies direction of r 第四章 线性判别函数

11 线性判别函数的几何意义 Substitute the above expression in g(x):
This gives the distance of x from the hyperplane: w0 determines the distance of the hyperplane from the origin: 第四章 线性判别函数

12 线性判别函数的几何意义 引言 g(x)是点x到决策面H的距离的一种代数度量 决策面(decision boundary)H方程：g(x)=0
向量w是决策面H的法向量 g(x)是点x到决策面H的距离的一种代数度量 x1 x2 w x xp r H: g=0 R1: g>0 R2: g<0 第四章 线性判别函数

13 广义线性判别函数 线性判别函数是形式最为简单的判别函数，但是它不能用于复杂情况。 二次函数的一般形式： 引言
例：设计一个一维分类器，使其功能为： 二次函数的一般形式： 第四章 线性判别函数

14 广义线性判别函数(2) 引言 二次函数的一般形式： 映射X→Y g(x)又可表示成： 第四章 线性判别函数

15 广义线性判别函数(3) 按照上述原理，任何非线性函数g(x)用级数展开成高次多项式后，都可转化成线性判别函数来处理。 引言
第四章 线性判别函数

16 广义线性判别函数 Generalized discriminant - a is a dimensional weight vector
- the functions yi(x) are called φ functions The functions yi(x) map points from the d-dimensional x-space to the -dimensional y-space (usually >> d ) 第四章 线性判别函数

17 广义线性判别函数 The resulting discriminant function is not linear in x but it is linear in y. The generalized discriminant separates points in the transformed space by a hyperplane passing through the origin. 第四章 线性判别函数

18 广义线性判别函数 Maps a line in x-space to a parabola in y-space.
Example: Maps a line in x-space to a parabola in y-space. The plane aty=0 divides the y-space in two decision regions The corresponding decision regions R1,R2 in the x-space are not simply connected! φ functions 第四章 线性判别函数

19 广义线性判别函数 第四章 线性判别函数

20 广义线性判别函数 Practical issues. Computationally intensive.
Lots of training examples are required to determine a if is very large (i.e.,curse of dimensionality). Example: A Full quadratics, the dimension of Y space is: 第四章 线性判别函数

21 广义线性判别函数 一种特殊映射方法：增广样本向量y与增广权向量a 第四章 线性判别函数

22 广义线性判别函数(4) 线性判别函数的齐次简化：
引言 线性判别函数的齐次简化： 增广样本向量使特征空间增加了一维，但保持了样本间的欧氏距离不变，对于分类效果也与原决策面相同，只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点，因此经常用到。 第四章 线性判别函数

23 线性分类器设计步骤 对于未知样本x，计算g(x)，判断其类别。 引言
线性分类器设计任务：给定样本集K，确定线性判别函数g(x)=wTx的各项系数w。步骤： 收集一组样本K={x1,x2,…,xN} 按需要确定一准则函数J(K,w)，其值反映分类器的性能，其极值解对应于“最好”决策。 用最优化技术求准则函数J的极值解w*，从而确定判别函数，完成分类器设计。 对于未知样本x，计算g(x)，判断其类别。 第四章 线性判别函数

24 4.2 Fisher线性判别 线性判别函数y=g(x)=wTx:
如果|| w ||=1，则视作向量x在向量w上的投影 Fisher准则的基本原理：找到一个最合适的投影轴，使两类样本在该轴上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。 第四章 线性判别函数

25 Fisher线性判别图例 Fisher准则的描述：用投影后数据的统计性质 —均值和离散度的函数作为判别优劣的标准。 x2 w1 H: g=0
第四章 线性判别函数

26 d维空间样本分布的描述量 各类样本均值向量mi 样本类内离散度矩阵Si与总类内离散度矩阵Sw 样本类间离散度矩阵Sb：
Fisher判别 各类样本均值向量mi 样本类内离散度矩阵Si与总类内离散度矩阵Sw 样本类间离散度矩阵Sb： 离散度矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度 第四章 线性判别函数

27 一维Y空间样本分布的描述量 各类样本均值 样本类内离散度和总类内离散度 样本类间离散度
Fisher判别 各类样本均值 样本类内离散度和总类内离散度 样本类间离散度 以上定义描述d维空间样本点到一向量投影的分散情况，因此也就是对某向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似 第四章 线性判别函数

28 样本与其投影统计量间的关系 Fisher判别 样本x与其投影y的统计量之间的关系： 第四章 线性判别函数

29 样本与其投影统计量间的关系 Fisher判别 第四章 线性判别函数

30 Fisher准则函数 Fisher最佳投影方向的求解
评价投影方向w的原则，使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内尽可能密集的要求 Fisher准则函数的定义： Fisher最佳投影方向的求解 第四章 线性判别函数

31 Fisher最佳投影方向的求解 采用拉格朗日乘子算法解决
m1-m2是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2 向量按Sw-1作一线性变换，从而使Fisher准则函数达到极值点 第四章 线性判别函数

32 判别函数的确定 前面讨论了使Fisher准则函数极大的d维向量w*的计算方法，判别函数中的另一项w0（阈值）可采用以下几种方法确定：
分类规则: 第四章 线性判别函数

33 Fisher公式的推导 Fisher判别 第四章 线性判别函数

34 4.3 感知器准则 感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器(Perceptron)，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。 第四章 线性判别函数

35 基本概念 感知器：Perceptron，Rosenblatt，50d/20thc
感知器准则 感知器：Perceptron，Rosenblatt，50d/20thc 线性可分性：训练样本集中的两类样本在特征空间可以用一个线性分界面正确无误地分开。在线性可分条件下，对合适的(广义)权向量a应有： 规范化样本向量 ：将第二类样本取其反向向量 第四章 线性判别函数

36 基本概念 Every training sample yi places a constraint on the weight vector a. Given n examples, the solution must lie on the intersection of n half-spaces. a2 g(x)=aty a1 第四章 线性判别函数

37 解向量与解区 感知器准则 第四章 线性判别函数

38 解向量与解区 Constrain margin: find min-length a with
Move solution to the center of the feasible region 第四章 线性判别函数

39 感知器准则函数 对于任何一个增广权向量a ， 定义一准则函数JP(a) (感知准则函数)： 对样本y正确分类，则有：aTy>0
被错分类的规范化增广样本集 恒有JP(a)≥0，且仅当a为解向量，Yk为空集（不存在错分样本）时， JP(a)=0，即达到极小值。确定向量a的问题变为对JP(a)求极小值的问题。 第四章 线性判别函数

40 梯度下降算法 感知器准则 梯度下降算法：对(迭代)向量沿某函数的负梯度方向修正，可较快到达该函数极小值。 第四章 线性判别函数

41 a(k+1)= a(k)+ rk×Sum (被错分类的所有样本)
算法(step by step) 感知器准则 1. 初值: 任意给定一向量初始值a(1) 2. 迭代: 第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与rk的乘积 3. 终止: 对所有样本正确分类 任意给定一向量 初始值a(1) a(k+1)= a(k)+ rk×Sum (被错分类的所有样本) 所有样本 正确分类 得到合理的a 完成 分类器设计 N Y 第四章 线性判别函数

42 感知器方法例解 固定增量法与可变增量法 批量样本修正法与单样本修正法 单样本修正法：样本集视为不断重复出现的序列，逐个样本检查，修正权向量
感知器准则 固定增量法与可变增量法 批量样本修正法与单样本修正法 单样本修正法：样本集视为不断重复出现的序列，逐个样本检查，修正权向量 批量样本修正法：样本成批或全部检查后，修正权向量 第四章 线性判别函数

43 Gradient Descent 第四章 线性判别函数

44 Gradient Descent too large learning rate! η η 第四章 线性判别函数

45 感知器方法小结 感知器准则 感知准则函数方法的思路是：先随意找一个初始向量a(1)，然后用训练样本集中的每个样本来计算。若发现一个y出现aTy<0，则只要a(k+1) = a(k) + rky，rk为正(步长系数)，则必有a(k+1)Ty = a(k)Ty + rkyTy，就有趋势做到使a(k+1)Ty >0。当然，修改后的a(k+1)还可以使某些y出现a(k+1)Ty <0的情况，理论证明，只要训练样本集线性可分，无论a(1)的初值是什么，经过有限次叠代，都可收敛。 第四章 线性判别函数

46 4.4 最小平方误差准则 规范化增广样本向量yi，增广权向量a，正确分类要求： aTyi>0, i=1,…,N
样本集增广矩阵Y及一组N个线性不等式的的矩阵表示： 引入余量(目标向量) b=[b1, b2, …, bN]T， bi任意给定正常数， aTyi = bi >0 N个线性方程的的矩阵表示： 第四章 线性判别函数

47 平方误差准则函数 定义误差向量 e=Ya-b： 定义平方误差准则函数Js(a): 最小二乘近似解（MSE解）： 第四章 线性判别函数

48 MSE准则函数的伪逆解 MSE 准则 Y的 伪逆矩阵 第四章 线性判别函数

49 MSE方法与Fisher方法的关系 MSE解等价于Fisher解 与Fisher方法的关系：当 N1个 N2个 第四章 线性判别函数

50 MSE方法与Bayes方法的关系 当N→∞，b=uN= [1,1, …, 1]T 时，则它以最小均方误差逼近Bayes判别函数：
第四章 线性判别函数

51 MSE方法的迭代解 单样本修正法 a*=Y+b, Y+=(YTY)-1YT，计算量大 实际中常用梯度下降法： 批量样本修正法
rk是递减的序列 单样本修正法 第四章 线性判别函数

52 4.5 多类问题 两类别问题可以推广到多类别问题 ωi/~ωi 法：将C类别问题化为(C-1)个两类（第i类与所有非i类）问题，按两类问题确定其判别函数与决策面方程 ωi/ωj 法：将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数 R1 R3 R2 ω1 非ω1 ω2 非ω2 R1 R3 R2 ω1 ω2 ω3 第四章 线性判别函数

53 多类线性判别函数 将特征空间确实划分为c个决策域，共有c个判别函数 决策规则：
多类 问题 将特征空间确实划分为c个决策域，共有c个判别函数 决策规则： 决策域的边界由相邻决策域的判别函数共同决定，此时应有gi(x)=gj(x) 线性分类器的决策面是凸的，决策区域是单连通的 多类分类器的分界面是分段线性的 第四章 线性判别函数

54 多类线性决策面图例 R2 R1 R2 R1 R3 R3 R5 第四章 线性判别函数 g1>g2 g2>g1 g1>g3
多类 问题 R1 R3 R2 g1>g2 g1>g3 g3>g1 g3>g2 g2>g3 g2>g1 R1 R3 R2 R5 R4 第四章 线性判别函数

55 决策树简介 决策树：一种多极分类器，它采用分级的形式，综合用多个决策规则，逐步把复杂的多类别分类问题转化为若干个简单的分类问题来解决 n1
多类 问题 决策树：一种多极分类器，它采用分级的形式，综合用多个决策规则，逐步把复杂的多类别分类问题转化为若干个简单的分类问题来解决 n1 n2 n3 n4 n5 t1 t2 t3 t4 t5 t6 t7 第四章 线性判别函数

56 二叉决策树 多类 问题 二叉决策树：除叶节点外，决策树的每个节点ni都有且只有两个子节点nil和nir。二叉决策树把复杂的多类别分类问题转化为多级两类分类问题来解决。在每个节点ni ，都把样本集分成两个子集。每个子集可能仍包含多类别的样本，继续分直至仅包含单类别样本的叶节点 n1 n2 n3 n4 t1 t2 t5 x2≤5 x1≤2 x3≤4 x2≤2 ω1 ω2 ω3 t3 t4 第四章 线性判别函数

57 4.6 分段线性判别函数 有些复杂模式识别问题不是线性可分的，需使用非线性的分类方法
分段线性判别函数：一种特殊的非线性判别函数，它的决策面是若干超平面 树分类器的各节点上采用线性判别规则，即构成分段线性分类器 R1 R3 R2 III I II I: 线性判别 II：分段线性判别 III: 二次判别 第四章 线性判别函数

58 分段线性距离分类器 分段线性判别 最小距离分类器：把各类别样本特征的均值向量作为各类的代表点(prototype) ，根据待识样本到各类别代表点的最小距离判别其类别。决策面是两类别均值连线的垂直平分面 分段线性距离分类器：将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类 第四章 线性判别函数

59 分段线性距离分类器图例 分段线性判别 x m1 m2 g(x)=0 m2 x m1 第四章 线性判别函数

60 基于距离的分段线性判别函数 分段线性判别 判别函数定义：ωi有li个子类，即属于ωi 的决策域Ri分成li个子域Ri1, Ri2,…, Rili)，每个子区域用均值mik代表点 判别规则： or 第四章 线性判别函数

61 分段线性判别函数 分段线性判别 分段线性判别函数的形式: gik(x)表示第i类第k段线性判别函数，li为i类所具有的判别函数个数，wik与wi0k分别是第k段的权向量与阈值 第i类的判别函数: 第四章 线性判别函数

62 分段线性判别函数(II) 判别规则: 决策面取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为
第四章 线性判别函数

63 4.7 讨论 基于样本的直接确定判别函数方法主要包含两个步骤：
确定使用的判别函数类型或决策面方程类型，如线性分类器，分段线性分类器等 在选定函数类型的条件下，确定相应的参数，从而完成整个分类器设计 线性判别函数计算简单，在一定条件下能实现最优分类，经常是一种“有限合理”的选择 分段线性分类器可以实现更复杂的分类面 第四章 线性判别函数

64 习题 有一个三次判别函数：z=g(x)=x3+2x2+3x+4。试建立一映射x→y，使得z转化为y的线性判别函数。
证明决策面H：wTx+w0=0的系数向量w是决策面H的法向量 设五维空间的线性方程为55x1+68x2+32x3+16x4+26x5+10 =0，试求出其权向量与样本向量点积的表达式wTx+w0=0中的w，x以及增广权向量与增广样本向量形式aTy中的a与y 第四章 线性判别函数

65 习题（续） 4. 设在三维空间中一个类别分类问题拟采用二次曲面。如欲采用广义线性方程求解，试问其广义样本向量与广义权向量的表达式，其维数是多少？ 第四章 线性判别函数