模式识别-线性分类1

1、1模式识别Pattern Recognition Chapter 3(I)2模式识别Pattern Recognition Ch. 3 线性分类器 3.1 线性分类器(LINEAR CLASSIFIERS)-引言022110.0)(wxwxwxwwxwxgllT2121020121, 0)(0:hyperplanedecision on the , AssumexxxxwwxwwxwxxTTT Hence:0)(0wxwxgThyperplane on the )( 21xxw3.2 线性判别函数和决策超平面The Problem: Consider a two class task with

2、 1, 2 3模式识别Pattern Recognition Ch. 3 线性分类器 222122210)( wwxgzwwwdFig.3-1 Graph of Decision Line；One side satisfysg(x)0(+) and the other side g(x)0(-)3.2 线性判别函数和决策超平面(3-1)4模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Perceptron Algorithm)我们关心计算未知参数i(i=1,2,l)以定义决策超平面。 Assume linearly separable cla

3、sses, i.e., 上式也包含不经过原点的超平面的情况： 作变换： 21 0* 0* :* xxwxxwwTT*0*wxwT1 ,*0 xxwww0*0 xwwxwTT(3-2)可以得到：(3-3)(3-4)5模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Perceptron Algorithm)Our goal: Compute a solution, i.e., a hyper plane (超平面超平面 ) w,so thatThe stepsDefine a cost function to be minimized(定义代价函

4、数并极小化定义代价函数并极小化)Choose an algorithm to minimize the cost function(寻找算法寻找算法)The minimum corresponds to a solution(求得与之相应的解求得与之相应的解)21 0)(xxwTThe Cost Function其中，其中，Y 是被是被w 错误分类的向量的子集，当错误分类的向量的子集，当 Y=(empty set) 则获得则获得了一个解并且了一个解并且YxTxxwwJ)()(3-5)(3-6)0)(wJ6模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法

5、(The Perceptron Algorithm)如果在上式中定义：21 and if 1 and if 1xYxxYxxx(3-7)则有：0)(wJ当代价函数取最小值0 时，则意味着所有的训练向量的分类都是正确的。事实上，式(3-6)表示的代价函数是分段线性的，平滑改变权向量也导致代价函数线性变化，直到分类向量个数改变代价函数会有非线性改变。在这些点，其梯度没有意义。为计算代价函数的最小值，梯度下降法是一个合理的方法，即：old)()(,(old)(new)wwtwwJwwww(3-8)、(3-9)xxwwwwJYxYxxTx)()(0)() 1(tYxxtxtwtw， (3-10)、(3

6、-11)这就是著名的感知器算法(Perceptron Algorithm) 7Fig.3-2 感知器算法的几何解释，在唯一错误分类点x，x =-1模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Perceptron Algorithm) 1( )()() 1(xtxtxtwxtwtw，Perceptron 在x方向修正权向量，其作用是修正超平面，使x能够被正确分到1类。修正的幅度和迭代次数取决于修正系数，满足分类的超平面不唯一，且不是一般的梯度算法，因而有必要证明其收敛性。8模式识别Pattern Recognition Ch. 3 线性分类

7、器 3.3 感知器算法(The Perceptron Algorithm)感知器算法的收敛性证明：由感知器算法0)() 1(tYxxtxtwtw，xwtwwtwwwoYxxt*)(*) 1(*,：的一个解，则可以写成是设(3-12)两边取欧式范数：xwxwtwxwtwxwtwwtwTYxxtYxxtTYxxtYxxt*2|*)(|*)(2|*)(|*) 1(|2222222(3-13)xwxTYxxYYxxY*max,|max222121取：(3-14) (3-15)范数的最大值直训练特征向量的向量是能够用来测试所有一和其中，29模式识别Pattern Recognition Ch. 3 线性

8、分类器 3.3 感知器算法(The Perceptron Algorithm)所以式的最后一项为负数，结束前，而且，由于迭代过程未)133( |2|*)(|*) 1(|2222ttwtwwtw(3-15)步，则有，并将上式应用于第选择：0,.,1,|22tttkktkkwwwtw002222|*)0(|*) 1(|(3-16)非负。因此，使上式的右边为则存在常量，和满足：选择otkkttkkttt,limlim020*) 1(, 0|*) 1(|000wtwwtw即：(3-17)10模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Percep

9、tron Algorithm)另外一种有用的感知器算法：otherwise )() 1( and 0)( if ,)() 1( and 0)( if, )() 1(2)()()(1)()()(twtwxxtwxtwtwxxtwxtwtwttTtttTt(3-18)It is a reward and punishment type of algorithm感知器： It is a learning machine that learns from the training vectors via the perceptron algorithm The network is called pe

10、rceptron or neuron11模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Perceptron Algorithm)shold thre weightssynapticor synapses 0wswi Example: At some stage t the perceptron algorithm results in The corresponding hyperplane is5 . 0 , 1 , 1021www05 . 021 xx05 . 051. 042. 1,5 . 051. 042. 1175. 02 . 0

11、) 1(7 . 0105. 04 . 0) 1(7 . 05 . 011) 1(21xxtw=0.7(中间结果，决策线，绿色)有两个点分类仍然错误(新决策线，黑色)13模式识别Pattern Recognition Ch. 3 线性分类器 3.3 感知器算法(The Perceptron Algorithm)感知器算法要求的基本条件是类的线性可分。在类非线性可分的情况下，袋式算法(Pocket Algorithm, Gallant S. I, Perceptron based learning Algorithms, IEEE Trans. Neural Networks, 1(2), 199

12、0:179-191)、热量感知器算法(Thermal Perceptron Algorithm, Frean M., A thermal perceptron learning rule, Neural Computation, Vol.4, 1992:946-957)、损失最小算法(Loss Minimization Algorithm, Hrycej T., Modular learning in neural networks, New York：Wiley,1992)和重心修正法(Barycentric CorrectionProcedure, Poulard H., Barycent

13、ric correction procedure: A fast methodof learning threshold units, Proc. WCNN95, Vol.1, Washington, D.C., July, 1995:710-713)等，也可以以概率1收敛于最佳分类结果(线性分类方法能够达到的最佳分类结果)14模式识别Pattern Recognition Ch. 3 线性分类器 3.4 最小二乘法(Least Squares Method)If classes are linearly separable, the perceptron output results inI

14、f classes are NOT linearly separable, we shall compute the weights1021 w,.,w,wso that the difference betweenThe actual output of the classifier, , andThe desired outputs, e.g.to be MinimizedxwT21 if 1 if 1xx15模式识别Pattern Recognition Ch. 3 线性分类器 3.4 最小二乘法(Least Squares Method)Minimization, 在均方差意义上,意味

15、着选择 使得代价函数w相应的期望响应最优权值最小， )(minarg )()(2ywJwxwyEwJwTMinimizing)()()(20)()(12关向量分别为自相关阵、互相、xyxxxxyTTTRRxyERwRxyExyEwxxEwxyxExwyEwwwJ(3-19)16模式识别Pattern Recognition Ch. 3 线性分类器 3.4 最小二乘法(Least Squares Method)(3-20)向多类推广：目标是根据MSE(最小方差)计算M个线性判别函数), 2 , 1()(MixwxgTii，otherwise 0 if 1iiiyxy考虑期望输出：TMyyyY,.,21MwwwW,.,21令：计算 WMiTiiWTWxwyExWYEW122minargminarg17模式识别Pattern Recognition Ch. 3 线性分类器 3.4 最小二乘法(Least Squares Meth