模式識別-線性分類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 線性判別函數(shù)和決策超平面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 線性判別函數(shù)和決策超平面(3-1)4模式識別Pattern Recognition Ch. 3 線性分類器 3.3 感知器算法(The Perceptron Algorithm)我們關(guān)心計算未知參數(shù)i(i=1,2,l)以定義決策超平面。 Assume linearly separable cla

3、sses, i.e., 上式也包含不經(jīng)過原點的超平面的情況： 作變換： 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、數(shù)并極小化定義代價函數(shù)并極小化)Choose an algorithm to minimize the cost function(尋找算法尋找算法)The minimum corresponds to a solution(求得與之相應(yīng)的解求得與之相應(yīng)的解)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當代價函數(shù)取最小值0 時，則意味著所有的訓(xùn)練向量的分類都是正確的。事實上，式(3-6)表示的代價函數(shù)是分段線性的，平滑改變權(quán)向量也導(dǎo)致代價函數(shù)線性變化，直到分類向量個數(shù)改變代價函數(shù)會有非線性改變。在這些點，其梯度沒有意義。為計算代價函數(shù)的最小值，梯度下降法是一個合理的方法，即：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方向修正權(quán)向量，其作用是修正超平面，使x能夠被正確分到1類。修正的幅度和迭代次數(shù)取決于修正系數(shù)，滿足分類的超平面不唯一，且不是一般的梯度算法，因而有必要證明其收斂性。8模式識別Pattern Recognition Ch. 3 線性分類

7、器 3.3 感知器算法(The Perceptron Algorithm)感知器算法的收斂性證明：由感知器算法0)() 1(tYxxtxtwtw，xwtwwtwwwoYxxt*)(*) 1(*,：的一個解，則可以寫成是設(shè)(3-12)兩邊取歐式范數(shù)：xwxwtwxwtwxwtwwtwTYxxtYxxtTYxxtYxxt*2|*)(|*)(2|*)(|*) 1(|2222222(3-13)xwxTYxxYYxxY*max,|max222121取：(3-14) (3-15)范數(shù)的最大值直訓(xùn)練特征向量的向量是能夠用來測試所有一和其中，29模式識別Pattern Recognition Ch. 3 線性

8、分類器 3.3 感知器算法(The Perceptron Algorithm)所以式的最后一項為負數(shù)，結(jié)束前，而且，由于迭代過程未)133( |2|*)(|*) 1(|2222ttwtwwtw(3-15)步，則有，并將上式應(yīng)用于第選擇：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(中間結(jié)果，決策線，綠色)有兩個點分類仍然錯誤(新決策線，黑色)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收斂于最佳分類結(jié)果(線性分類方法能夠達到的最佳分類結(jié)果)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、著選擇 使得代價函數(shù)w相應(yīng)的期望響應(yīng)最優(yōu)權(quán)值最小， )(minarg )()(2ywJwxwyEwJwTMinimizing)()()(20)()(12關(guān)向量分別為自相關(guān)陣、互相、xyxxxxyTTTRRxyERwRxyExyEwxxEwxyxExwyEwwwJ(3-19)16模式識別Pattern Recognition Ch. 3 線性分類器 3.4 最小二乘法(Least Squares Method)(3-20)向多類推廣：目標是根據(jù)MSE(最小方差)計算M個線性判別函數(shù)), 2 , 1()(MixwxgTii，otherwise 0 if 1iiiyxy考慮期望輸出：TMyyyY,.,21MwwwW,.,21令：計算 WMiTiiWTWxwyExWYEW122minargminarg17模式識別Pattern Recognition Ch. 3 線性分類器 3.4 最小二乘法(Least Squares Meth