模式識別線性判別函數(shù)

1、模式識別線性判別函數(shù)第1頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四前面講過，各種決策規(guī)則都導(dǎo)致似然比檢驗(yàn)的形式：5.1 引言第2頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 若分布是正態(tài)的，其均值向量和協(xié)方差矩陣分別是mi 和 ki（i1, 2），則定義 ，則 第3頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 本質(zhì)上在比較離均值的馬氏距離。這是一個二次分類器。展開h(x)并整理后有：第4頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言式中： 第5頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言

2、 當(dāng)兩類的協(xié)方差矩陣相等時，即K=K1=K2， 決策規(guī)則變?yōu)椋旱?頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言其中： 這是一個線性分類器，是在正態(tài)分布、等協(xié)方差矩陣的情況下導(dǎo)出的。 這時的判別函數(shù)gk(x)的形式也是線性的，稱為線性判別函數(shù) 第7頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 線性判別函數(shù)由一些參數(shù)所規(guī)定，所以由它們所確定的分類器又稱為參數(shù)分類器。 參數(shù)分類器可以是線性（一次）的、二次的，或其它函數(shù)形式。 而近鄰法是一種非參數(shù)分類器。第8頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言在實(shí)際工作中， 所以發(fā)展了各

3、種直接從樣本中設(shè)計(jì)線性分類器的方法。這些方法本質(zhì)上都是要確定線性判別函數(shù)中的參數(shù)（參數(shù)分類器中的參數(shù)估計(jì)）。 第9頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言線性分類器的設(shè)計(jì)過程線性判別函數(shù)的一般形式為： 希望根據(jù)給出的已知類別的訓(xùn)練樣本，確定參數(shù)w和w0.第10頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言對分類器的性能提出要求使所確定的w和w0盡可能滿足這些要求。 利用各種 表示對應(yīng)于準(zhǔn)則函數(shù)的最優(yōu)化（方法），求準(zhǔn)則函數(shù)的極值問題。第11頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 線性判別函數(shù)分類的錯誤率可能比貝葉斯錯

4、誤率大，但它簡單，容易實(shí)現(xiàn)，它是P.R.中最基本的方法之一，人們對它進(jìn)行了大量的研究工作。（分段線性可以逼近任意復(fù)雜的判別邊界面）第12頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言幾種常用的準(zhǔn)則函數(shù)：第13頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言線性判別函數(shù)的基本概念形式： 其中：( w 稱為權(quán)向量 ）第14頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四 線性判別函數(shù)g(x)=0 定義了一個超平面H，稱為決策面，即分界面，它把特征空間分成了三部分，5.1 引言 對于兩類問題，決策規(guī)則 正負(fù)半空間和超平面本身。第15頁，共82頁，20

5、22年，5月20日，6點(diǎn)30分，星期四5.1 引言 假定x1和x2是超平面H（分界面）上的任意兩點(diǎn)，由于 即w是H的法向量，它和H上的任一向量正交。 判別函數(shù)g(x)是特征空間中的某點(diǎn)x到超平面g(x)=0的代數(shù)距離（有正負(fù)）的一種度量。超平面的一些性質(zhì)第16頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 第17頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四 兩類情況第18頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 則代入g(x) 中有：第19頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言 （點(diǎn)面距離）點(diǎn) (x0,

6、 y0, z0) 到平面 Ax+By+Cz+D=0的距離為：第20頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言若x為原點(diǎn)，則若w00，則原點(diǎn)在H的正側(cè)；若w0b，三個區(qū)域，兩類 這樣做的結(jié)果是增加了特征的維數(shù)。如上例由一維三維。第24頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言另外,為了處理上的方便，線性判別函數(shù)常寫成齊次的形式第25頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言其中 ，增廣樣本向量 廣義權(quán)向量第26頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.1 引言y和x相比，維數(shù)增加了一維 各次形式的線性

7、判別函數(shù)（即增廣的權(quán)及樣本向量）以后常用。 第27頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四第五章 線性判別函數(shù)（分類器，參數(shù)分類器）5.1 引言5.2 Fisher 線性判別5.3 感知準(zhǔn)則函數(shù)（Perception）5.4 最小平方誤差準(zhǔn)則函數(shù)5.5 多層感知的學(xué)習(xí)算法 誤差反向傳播算法 第28頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四對于線性判別函數(shù)（5.2 Fisher 線性判別），的樣本投影到一條直線上（設(shè)b (w) 的長度為1）。 相當(dāng)于把n維特征空間第29頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.2 Fisher 線性判別第30頁，共

8、82頁，2022年，5月20日，6點(diǎn)30分，星期四5.2 Fisher 線性判別 要找一個最好的投影方向b，使下面的準(zhǔn)則函數(shù)達(dá)到最大值。第31頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.2 Fisher 線性判別其中： 而 投影后的 投影前的 第32頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.2 Fisher 線性判別由求JF的極值問題，最后得到 和貝葉斯最小錯誤率決策的b只差一個常數(shù)，方向相同。 投影到一維后的兩類分界點(diǎn)，可以用一維分類時的一些辦法作。 當(dāng)k1=k2=k時，第33頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四第五章 線性判別函數(shù)（分類

9、器，參數(shù)分類器）5.1 引言5.2 Fisher 線性判別5.3 感知準(zhǔn)則函數(shù)（Perceptron）5.4 最小平方誤差準(zhǔn)則函數(shù)5.5 多層感知的學(xué)習(xí)算法 誤差反向傳播算法 第34頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）一幾個基本概念1線性可分性 對一組樣本y1, , yN（增廣表示），假定來自兩類，若存在一個權(quán)向量a，使得當(dāng)時，有 時，有則稱這組樣本是線性可分的。第35頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 若樣本是線性可分的，則總存在權(quán)向量a能把每個樣本正確分類。即使

10、得2樣本的規(guī)范化，對，對 對第二類的樣本，若在yj前加一負(fù)號 yj=-yj，則 aTyi0 。第36頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）即若令 ，當(dāng) ，當(dāng) 這時問題就化為找一個a，使對所有的yn，有aTyn0。 上述的處理稱為規(guī)范化。 稱為規(guī)范化的增廣樣本。 以后為書寫方便，仍用y來表示規(guī)范化的增廣樣本。（可根據(jù)上下文定 ）第37頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）3解向量和解區(qū) 在線性可分的情況下，滿足aTyi0，i=1, 2, , N的a稱為權(quán)向量，記為a*。 方

11、程aTyi=0中的a和yi的作用是對偶的。 一個權(quán)向量a是權(quán)空間中的一個點(diǎn)。每個樣本yi對a的可能位置都起到限制作用。即要滿足aTyi0。對所有樣本滿足aTyi0的a即為一個解。第38頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 方程aTyi=0確定了權(quán)空間中過原點(diǎn)的一個超平面Hi，它的法向量是yi。解應(yīng)在Hi的正側(cè)（因?yàn)橐骯Tyi0） 正半空間。 N個樣本確定了權(quán)空間中的N個平面，每個平面把權(quán)空間分成了三部分，正側(cè)、負(fù)側(cè)和平面本身。第39頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perception

12、） 所以，如果解存在，則必定在N個超平面的正半空間的相交區(qū)。這個區(qū)域稱為解區(qū)。區(qū)域中的每個向量都是解向量a*。 解和解區(qū)的兩維示意圖如下： 第40頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）第41頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四 為使所得的a*對新的樣本也能正確分類，a*最好位于解區(qū)的中央。 為提高泛化能力，使解更可靠，引入余量b0，尋找滿足aTyi=b, i=1, 2, , N的解區(qū)。 顯然，滿足aTyi=b0的解區(qū)位于原aTyi0的解區(qū)之內(nèi)，且離原解區(qū)邊界的距離為5.3 感知準(zhǔn)則函數(shù)（Perceptron）4對

13、解區(qū)的限制 。 第42頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）。 二感知準(zhǔn)則函數(shù)及其梯度下降算法 設(shè)有一組樣本y1, , yN（規(guī)范的增廣樣本向量）。目的是求一a*，使得a*Tyi0, i=1, 2, , N。第43頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）。 構(gòu)造一個準(zhǔn)則函數(shù)， Ye ：被a所錯分的樣本集合。 即aTy=0。 第44頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）。 只有當(dāng)Ye為空集時，不存在錯分樣本，才有

14、這一準(zhǔn)則函數(shù)是Rosenblat在五十年代末提出來的，用來模擬人腦神經(jīng)細(xì)胞的模型，所以一般稱為感知準(zhǔn)則函數(shù)。 第45頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）可以用梯度下降法求使Jp(a)最小的a*。Ye 是被a所錯分的樣本集。 第46頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 函數(shù)Jp(a)在某點(diǎn)ak的梯度Jp(ak)是一個向量，其方向是Jp(a)增長最快的方向，而負(fù)梯度是減小最快的方向。 沿梯度方向極大值 沿負(fù)梯度 極小值第47頁，共82頁，2022年，5月20日，6點(diǎn)30分

15、，星期四 ：被a(k)錯分的樣本集。即，當(dāng)任意給定初始權(quán)向量a(1)后，a(k+1)等于a(k)加上5.3 感知準(zhǔn)則函數(shù)（Perceptron）迭代公式： 第48頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perception） 可以證明，若樣本線性可分，則經(jīng)過有限次迭代修正后，一定可以找到一個解向量，即算法收斂。 上述的算法是一種“批處理”方式。用a(k)把所有的樣本分類一次，然后統(tǒng)計(jì)錯分的樣本，修改一次權(quán)。 第49頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 也可采用“單樣本修正”：順序?qū)Ω鱾€樣本進(jìn)行

16、分類，分錯了就修正權(quán)。 單樣本修正算法為： 第50頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 假定令，則 第51頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron） 當(dāng)為固定值時，稱為固定增量法。隨k變化時，稱為可變增量法。選的一次越過超平面時，即當(dāng)當(dāng)稱為絕對增量法。第52頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）例1線性可分與不可分的情況第53頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四 下面證明在線性可分的情況下，單

17、樣本固定增量法（5.3 感知準(zhǔn)則函數(shù)（Perceptron）收斂，即經(jīng)過有限次修正后，一定可以找到解向量a*。 ）一定第54頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）證明：假定固定的增量系數(shù)這并不失一般性，因?yàn)楦淖儍H僅是改變了坐標(biāo)系的比例。坐標(biāo)系比例的改變并不影響數(shù)據(jù)結(jié)構(gòu)和線性分類器。 ，第55頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）這時的迭代規(guī)則為yk是被a(k)錯分的，即由于假定兩類是線性可分的，則一定存在一個as，使得astyi0, i=1, , N. 第56頁，共82頁

18、，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）令 可以改變a的比例，使得改變a的比例并不影響（并不改變）決策規(guī)則。 ( * ) ( * )常數(shù)第57頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）a(k)和as間的距離平方為（記a(k)ak, a(k+1)ak+1）而 第58頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron），和 ( * ) 及 ( * ) 式， 上式說明，當(dāng)利用一個yk時（被錯分的樣本），|as-ak|2就減少了一定的量。因此，經(jīng)過有

19、限次的利用錯分樣本后，ak應(yīng)收斂于as。 絕對增量法的證明，可以利用上面固定增量法的結(jié)果。P373 第59頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四對兩類問題線性分類器的設(shè)計(jì)可以推廣到多維。對C類問題，可以建立C個線性判別函數(shù)aiTy, i=1, , C. 判決規(guī)則為：5.3 感知準(zhǔn)則函數(shù)（Perceptron）。 三多類問題的線性分類器當(dāng)所有樣本( i=1, , C ) 都滿足上式時，若稱這C類是線性可分的。 第60頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.3 感知準(zhǔn)則函數(shù)（Perceptron）* 求多類問題的ai (i=1, , C)的算法如下：， 則 若

20、對 2. 若 ，對，則且 這個多類問題的迭代算法的證明，可以通過把上述算法轉(zhuǎn)換為兩類問題，然后利用上面的結(jié)果進(jìn)行。 有：第61頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四第五章 線性判別函數(shù)（分類器，參數(shù)分類器）5.1 引言5.2 Fisher 線性判別5.3 感知準(zhǔn)則函數(shù)（Perceptron）5.4 最小平方誤差準(zhǔn)則函數(shù)5.5 多層感知的學(xué)習(xí)算法 誤差反向傳播算法 第62頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù)一引言 上節(jié)的感知準(zhǔn)則函數(shù)只適合于線性可分的情況。對線性不可分情況，算法不收斂。但在實(shí)際問題中， 1有許多問題不是線性可分的

21、2事先不知道是否線性可分 第63頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù) 因此我們希望找到一些算法既適合線性可分的情況，又適合線性不可分的情況。 對線性可分的問題，算法求得的解能把兩類正確分開； 而對線性不可分的問題，算法也能找到在一定準(zhǔn)則下的最優(yōu)解。 第64頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù) 對于規(guī)范化的增廣樣本向量，yi=1, , N，要找a，使得aTyi0, i=1, , N。這是求N個不等式組解的問題。 若線性可分-線性不等式組是一致的，有解-能求出a，使aTyi0, i=1, , N； 若線

22、性不可分-線性不等式組不一致，無解-求一個a，比如說使正確分類的樣本數(shù)最多，使成立的不等式的個數(shù)最多。第65頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù) 這樣，線性分類器的設(shè)計(jì)就轉(zhuǎn)化為解線性不等式組的問題。 這時的準(zhǔn)則函數(shù)是一類最少錯分樣本數(shù)準(zhǔn)則。（略） 下面要介紹的方法是把線性分類器的設(shè)計(jì)轉(zhuǎn)換為解線性方程組。第66頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù)二最小平方誤差準(zhǔn)則函數(shù)把a(bǔ)Tyi0, i=1, , N寫成聯(lián)立方程的形式 Ya=b 第67頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四 求使 極小

23、的a作為問題的解。這是矛盾方程組的最小二乘解。 稱為最小平方誤差準(zhǔn)則函數(shù)（MSE）。 和平方誤差準(zhǔn)則函數(shù)大于未知數(shù)的個數(shù)，所以上述方程組一般為矛盾方程組，沒有準(zhǔn)確解。但可以定義一個誤差向量 5.4 最小平方誤差準(zhǔn)則函數(shù) 由于通常，即樣本數(shù)（方程的個數(shù)）（向量）第68頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四對 求梯度5.4 最小平方誤差準(zhǔn)則函數(shù)下面推導(dǎo)在MSE下的解。令，有 而是的矩陣，一般是非奇異的。( * ) 第69頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù)式中是y的偽逆。 在a*的解( * )式中，a*顯然依賴于b。如何選擇b呢？

24、當(dāng)b取某些特殊值時，MSE（最小平方誤差）解有較好的性質(zhì)。的矩陣，稱為( * ) 第70頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù) 當(dāng)取MSE解a*等價于Fisher解。時，第71頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四時，MSE的解a*在最小均方誤差意5.4 最小平方誤差準(zhǔn)則函數(shù) 當(dāng)取式中時，當(dāng)義逼近貝葉斯判別函數(shù)：最小。即使MSE最小的解使第72頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù) 還可以由實(shí)際問題確定bi，aTyi=bi第73頁，共82頁，2022年，5月20日，6點(diǎn)30分，星期四5.4 最小平方誤差準(zhǔn)則函數(shù)三MSE準(zhǔn)則函數(shù)的梯度下降法 在偽逆解中，需要計(jì)算Y+。 這時要求 存在 的計(jì)算量大，而且可能引入更大的計(jì)算誤差。 第74頁，共82頁，2022年，5月2