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

1、模式識別第講線性判別函數(shù)第1頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第5講 線性判別函數(shù)（1）第2頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四本節(jié)課主要內(nèi)容線性判別函數(shù)和決策面 Fisher準(zhǔn)則3 感知準(zhǔn)則第3頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四1 線性判別函數(shù)和決策面線性判別函數(shù)是決策論模式識別方法中的一種重要的基本方法，是形式最簡單的判別函數(shù)，由于它具有計(jì)算簡單，在一定條件下能夠?qū)崿F(xiàn)最優(yōu)分類的性質(zhì)，因此在實(shí)際中得到了廣泛的應(yīng)用。此外，許多其它決策論識別方法也可用判別函數(shù)來研究（非線性判別函數(shù)），它也是研究神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)?，F(xiàn)在我們就從線性判別函

2、數(shù)開始介紹統(tǒng)計(jì)模式識別的各種方法。第4頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四在統(tǒng)計(jì)模式識別方法中，首先應(yīng)把能代表模式的那些特征抽取出來，構(gòu)成一個(gè)代表這個(gè)模式的特征向量，表示為當(dāng)我們觀察待分類模式時(shí)，每次觀察到的樣本都是不同的，他們可以看成是隨機(jī)產(chǎn)生的。所以每次抽取到的模式特征都應(yīng)看成是隨機(jī)變量，從而代表這些模式的 n 維向量也應(yīng)是隨機(jī)向量。第5頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四所以，如果根據(jù)以往大量的觀察，知道模式類別的分布，從而能找出n 維空間中模式類之間的分界，就能解決模式的分類問題。這在實(shí)際上是一個(gè)通過給定樣本的學(xué)習(xí)過程。 簡便起見，在本章中我們假

3、定抽取到的模式樣本的邊界是“整齊”而不混雜的，而且以后遇到的待分類模式基本上不超過學(xué)習(xí)樣本的分布范圍，從而利用這些樣本得出的分類邊界是無誤差的。為找出這些模式之間的分界面，可以利用判別函數(shù)來進(jìn)行。對于n 維空間中的 c 個(gè)模式類別各給出一個(gè)由 n 個(gè)特征組成的單值函數(shù)，這叫做判別函數(shù)。在 c 類的情況下，我們共有 c個(gè)判別函數(shù)，記為第6頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四判別函數(shù) 假設(shè)對一模式X已抽取n個(gè)特征，表示為：模式識別問題就是根據(jù)模式X的n個(gè)特征來判別模式屬于1 ,2 , , c 類中的那一類。第7頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四例如下圖：三

4、類的分類問題，它們的邊界線就是一個(gè)判別函數(shù)判別函數(shù)第8頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四判別函數(shù)包含兩類：一類 是線性判別函數(shù)： 線性判別函數(shù) 廣義線性判別函數(shù)（所謂廣義線性判別函數(shù)就是把非線性判別函數(shù)映射到另外一個(gè)空間變成線性判別函數(shù)）非線性判別函數(shù)分段線性判別函數(shù)二次判別函數(shù)判別函數(shù)第9頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四判別函數(shù)的性質(zhì)假如一個(gè)模式 X 屬于第 i 類，則有而如果這個(gè)模式在第 i 類和第 j 類的分界面上，則有事實(shí)上，這是由 n 維模式降為1維或1個(gè)數(shù)的一種變換。線性判別函數(shù)是所有模式特征的線性組合，表示為第10頁，共76頁，202

5、2年，5月20日，6點(diǎn)30分，星期四二類情況下的線性判別函數(shù)可將其任意分類，或拒絕第11頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四用其可以構(gòu)造一個(gè)二類模式的線性分類器，如圖所示。第12頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四二類情況下，決策面與模式向量的幾何關(guān)系 是決策面方程，它是兩類模式的分界，對于二維空間的情況，它是一條直線。下面，對一些關(guān)系作幾何解釋，如圖所示。第13頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第14頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四 廣義線性判別函數(shù)這樣一個(gè)非線性判別函數(shù)通過映射，變換成線性判別函數(shù)。判別函

6、數(shù)的一般形式：第15頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四廣義線性判別函數(shù)例：如右圖。第16頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四廣義線性判別函數(shù)要用二次判別函數(shù)才可把二類分開：212第17頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四廣義線性判別函數(shù)從圖可以看出：在陰影上面是1類，在陰影下面是2類，結(jié)論：在X空間的非線性判別函數(shù)通過變換到Y(jié)空間成為線性的，但X變?yōu)楦呔S空間.212第18頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四設(shè)計(jì)線性分類器的主要步驟一組具有類別標(biāo)志的樣本集 X=x1,x2,xn 或增廣樣本集Y。確定一個(gè)準(zhǔn)則函數(shù)J，

7、滿足: a. 是樣本集w,w0,或a的函數(shù)； b. J的值反映分類器的性能,極值解對應(yīng)最好策略。用最優(yōu)化技術(shù)求出準(zhǔn)則函數(shù)的極值w*, w0*, 或a*。這樣就可以得到線性判別函數(shù)第19頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四2. Fisher線性判別函數(shù)在以后的統(tǒng)計(jì)模式識別方法中，維數(shù)或特征數(shù)是一個(gè)很大的問題，因此，降低維數(shù)有時(shí)就成為處理實(shí)際問題的關(guān)鍵。Fisher線性判別函數(shù)法就是其中一種，是R.A.Fisher（1936）在他的一篇論文中提出來的，其基本思想是把 d 維模式投影到一條通過原點(diǎn)的直線上，把維數(shù)壓縮到1。參照如圖所示的例子，進(jìn)行分析。第20頁，共76頁，2022

8、年，5月20日，6點(diǎn)30分，星期四第21頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四基于這個(gè)例子可以看到， 投影線的方向起著至關(guān)重要的作用。下面著重討論如何從數(shù)學(xué)上尋求最優(yōu)的投影線方向。首先討論從 d 維空間到 1 維空間的數(shù)學(xué)變換，從幾何上看， 就是相對應(yīng)的 到方向?yàn)?的直線上的投影。尋找最好的投影方向即是尋找最好的變換向量 的問題。第22頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第23頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第24頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四這里建立一個(gè)準(zhǔn)則函數(shù)，它能反映不同類別模式在 直線上投影分離程度

9、的好壞。綜合上述考慮，希望兩類模式特征向量投影均值之差越大越好；同時(shí)希望同類模式特征向量的投影內(nèi)部盡量密集。定義Fisher準(zhǔn)則函數(shù)尋找使 分子盡可能大，而分母盡可能小，也就是使 盡可能大的 作為投影方向。第25頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四將 變?yōu)?的顯函數(shù)第26頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四稱為 Rayleigh比,其具有以下性質(zhì)： ，a 是一個(gè)實(shí)數(shù)； 的極值與 的大小無關(guān)，只與 的方向有關(guān)。下面求準(zhǔn)則函數(shù)的極大值。將標(biāo)量 對向量 求導(dǎo)并令其為零向量，注意到 的分子分母均為標(biāo)量，利用二次型關(guān)于向量求導(dǎo)的公式可得：第27頁，共76頁，202

10、2年，5月20日，6點(diǎn)30分，星期四上式表明： 是矩陣 相應(yīng)于特征值 的特征向量（本特值）。第28頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四 由于我們的目的是尋求最好的投影方向， 的比例因子對此并無影響，因此，可得第29頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四線性可分性討論如下的兩個(gè)問題 對于4個(gè)二維樣本，其在平面上的分布如圖所示。若把每個(gè)樣本任意分到 兩種類別之一 或 ，舉出其中的兩種線性不可分情況。 驗(yàn)證 N 個(gè) d 維樣本線性可分的概率閾值是3感知準(zhǔn)則函數(shù) 第30頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四線性可分性第31頁，共76頁，2022年

11、，5月20日，6點(diǎn)30分，星期四樣本的規(guī)范化 二類模式的線性分類器的決策規(guī)則為引入增廣樣本向量和廣義權(quán)向量可將其任意分類，或拒絕第32頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四代入，決策規(guī)則可變?yōu)?取可得 叫做規(guī)范化增廣樣本向量，為方便起見仍用 表示第33頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四解向量和解區(qū)解向量：在線性可分情況下，滿足的權(quán)向量稱作解向量。解區(qū)：解向量往往不唯一，而是由無窮多個(gè)解向量組成的區(qū)域。我們稱這樣的區(qū)域?yàn)榻鈪^(qū)。第34頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第35頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第36頁

12、，共76頁，2022年，5月20日，6點(diǎn)30分，星期四對解區(qū)的限制對解區(qū)加以限制的目的在于使解向量更可靠。因?yàn)樵娇拷鈪^(qū)中間的解向量越能對新的樣本正確分類。同時(shí)也可避免求解向量 的算法不致收斂到解區(qū)邊界的某點(diǎn)上。第37頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四為了解線性不等式 （ 已規(guī)范化 ）需要構(gòu)造一個(gè)準(zhǔn)則函數(shù)。這里我們介紹一種常用的準(zhǔn)則函數(shù)即所謂的感知準(zhǔn)則函數(shù)，定義為如下的形式： 是由于使用權(quán)向量 而被誤分類的樣本集合。感知準(zhǔn)則函數(shù)及其梯度下降算法第38頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四也就是說，當(dāng)對于某個(gè)向量 ，準(zhǔn)則函數(shù) 達(dá)到極小值的話， 就是解向量，

13、這時(shí)沒有樣本被錯(cuò)分類?，F(xiàn)在用最優(yōu)化方法梯度下降算法尋找使 達(dá)到極小值的解權(quán)向量。梯度下降算法基本思想函數(shù) 在某點(diǎn) 的梯度 是一個(gè)向量，它的方向與過點(diǎn) 的等量面 的法線方向重合，指向 增加的一方，是準(zhǔn)則函數(shù)變化率最大的方向。反之，負(fù)梯度的方向則是函數(shù) 減小最快的方向。所以在求準(zhǔn)則函數(shù) 的極小值時(shí) ，沿負(fù)梯度方向搜索有可能最快地找到極小值。 第39頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四梯度下降算法的實(shí)現(xiàn)先任意選擇一個(gè)初始的權(quán)向量 ，計(jì)算 上的梯度 ，從 出發(fā)在最陡方向（負(fù)梯度）上移動一個(gè)距離以得到下一個(gè)權(quán)向量值 ，用迭代公式表示為請簡述梯度下降算法？ 第40頁，共76頁，2022

14、年，5月20日，6點(diǎn)30分，星期四梯度下降算法應(yīng)用舉例單樣本修正法把樣本看作一個(gè)不斷重復(fù)出現(xiàn)的序列而逐個(gè)加以考慮，樣本組成的樣本序列為：第41頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第42頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第43頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四第44頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四2.3最小平方誤差準(zhǔn)則函數(shù) 2.2.1平方誤差準(zhǔn)則函數(shù)及其偽逆解 2.2.2 MSE準(zhǔn)則函數(shù)的梯度下降算法返回本章首頁第45頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四前面我們介紹的感知器準(zhǔn)則函數(shù)是在誤分

15、類樣本的基礎(chǔ)上建立的，它要求對于所有樣本都能滿足不等式 本節(jié)介紹的最小平方誤差準(zhǔn)則函數(shù)，它是一個(gè)基于全體樣本的準(zhǔn)則函數(shù)，要求滿足等式這樣就可以將原來解一組線性不等式的問題轉(zhuǎn)化為解一組線性方程組的問題。返回本章首頁2.3.1 平方誤差準(zhǔn)則函數(shù)及其偽逆解 第46頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四引入其中 是規(guī)范化增廣樣本向量將 寫成聯(lián)立方程組得形式若 是非奇異方陣，則可以得到解 ； 若 是長方陣（一般為列滿秩），則是矛盾方程組，沒有精確解。定義誤差向量返回本章首頁第47頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四引入其中 是規(guī)范化增廣樣本向量將 寫成聯(lián)立方程組得形

16、式若 是非奇異方陣，則可以得到解 ； 若 是長方陣（一般為列滿秩），則是矛盾方程組，沒有精確解存在。返回本章首頁第48頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四定義誤差向量定義平方和準(zhǔn)則函數(shù)為使廣義權(quán)向量為最優(yōu)，只需使平方和準(zhǔn)則函數(shù)極小化，然后把相應(yīng)的 作為問題的解，稱其為矛盾方程組的最小二乘解（MSE解）。 返回本章首頁第49頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四 返回本章首頁第50頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四這里 是一個(gè) 維方陣，且常為非奇異； 方陣 稱為 的偽逆（矩陣論里稱其為廣義逆），且具有以下性質(zhì)：當(dāng) 為非奇異方陣時(shí)， 的偽

17、逆和它的逆相等一般來說返回本章首頁第51頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四從上述推倒過程可以看出，MSE解依賴于向量 ， 的不同選擇可以給予解以不同的性質(zhì)（參考教材P102）。返回本章首頁第52頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四從前面的推導(dǎo)過程我們可以看到，用MSE方法按式 的計(jì)算工作量很大，首先要求證明 是非奇異的，然后計(jì)算 ，為 維矩陣的逆。 這樣，我們引入梯度下降算法以避免這種問題。誤差平方和準(zhǔn)則函數(shù)的梯度返回本章首頁2.3.2 MSE準(zhǔn)則函數(shù)的梯度下降算法第53頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四梯度下降算法為：（1）首先

18、任意指定初始權(quán)向量 ；（2）如第 k 步不能滿足要求 則按下式求第 (k+1) 步的權(quán)向量對于任意的正常數(shù)，算法得到的權(quán)向量序列收斂于使返回本章首頁第54頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁MSE最小平方誤差方法與Fisher線性判別的關(guān)系在此，我們將通過適當(dāng)選擇 b 來說明 MSE 判別函數(shù)是和 Fisher 線性判別有直接聯(lián)系的。我們假設(shè)一組 d 維樣本集 ，其中 個(gè)屬于 類的樣本記為子集 ，其中 個(gè)屬于 類的樣本記為子集 。進(jìn)一步，得到增廣模式向量 ，并進(jìn)行規(guī)范化。不失一般性，可以假設(shè)前 個(gè)樣本屬于 類，后 個(gè)樣本屬于 。這樣矩陣 就可以寫成分塊矩陣第55

19、頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁 是 個(gè) 1 的列向量， 是一個(gè)矩陣，它的行是屬于 。接下來，我們將證明MSE解和Fisher線性判別關(guān)系。第56頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第57頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第58頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第59頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁對于任意的 ，向量 都是在 的方向上，則就有代入第60頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四2.5 多類情況下

20、的線性判別函數(shù)前面我們重點(diǎn)討論了二類模式情況下的線性判別方法，不難把它們推廣到多類別的情況?？梢园讯囝悊栴}化為二類問題來解決，也可以直接按多類問題來解。1、按二類問題解是把 c 類問題轉(zhuǎn)化為 個(gè)二類模式的分類問題。其中第 i 個(gè)問題就是用線性判別函數(shù)把屬于 類的模式同不屬于 的模式分開。 是用 次二類模式線性判別，每次只從樣本集中判別指定的二類的決策面。兩種方法都會產(chǎn)生模糊區(qū)域，結(jié)合下圖進(jìn)行分析。返回本章首頁第61頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第62頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第63頁，共76頁，2022年，5月20

21、日，6點(diǎn)30分，星期四2 按多類問題解（結(jié)合第一節(jié)內(nèi)容）如果不用區(qū)別二類問題的線性判別函數(shù)，可采用一般的c 類線性判別函數(shù)：如果對于所有的 ，有則把模式 歸到 類去而如果這個(gè)模式在第 i 類和第 j 類的分界面上，則有返回本章首頁第64頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第65頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第66頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四線性機(jī)器的決策區(qū)域的特點(diǎn)（1）所有決策區(qū)域是凸的；（2）每個(gè)決策區(qū)域都是單連通的；（3）不存在拒絕分類的死區(qū)；返回本章首頁第67頁，共76頁，2022年，5月2

22、0日，6點(diǎn)30分，星期四2.6 分段線性判別函數(shù)以上我們介紹了線性判別函數(shù)，它的一個(gè)顯著的優(yōu)點(diǎn)是：算法簡單和具有“學(xué)習(xí)”的能力，就是說，給定分好類的樣本集后，能夠根據(jù)樣本“學(xué)習(xí)”，自動找到線性分界面。它的另一個(gè)優(yōu)點(diǎn)是：如果給定的 分好類的n維模式樣本集是線性可分的，則基于感知準(zhǔn)則函數(shù)的算法一定收斂。不足是：必須線性可分，得到的分界面是一個(gè)超平面，應(yīng)用有限，對于比較復(fù)雜的問題，如果樣本不是線性可分時(shí)，就會導(dǎo)致較大的分類錯(cuò)誤率。返回本章首頁第68頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四返回本章首頁第69頁，共76頁，2022年，5月20日，6點(diǎn)30分，星期四為了解決比較復(fù)雜的線性不可分樣本分類問題，提出了非線性判別函數(shù)，如圖的分界面所示，為超曲面，非線性判別函數(shù)計(jì)算復(fù)雜，實(shí)際應(yīng)用上受到較大的限制。解決問題比較簡便的方法是采用多個(gè)線性分界面，將它們分段連接，用分段線性判別劃分去逼近分界的超曲面，如圖。 其優(yōu)點(diǎn)是：由于它的各段都是超平面，有可能利用已知的線性判別函數(shù)來解決分類問題；它由若干超平面組成，可以較好地逼近分類的超曲面，從而減少分類錯(cuò)誤。返回本章首頁第70頁，共76頁，2022年，5月20日，6點(diǎn)