中科院-模式識(shí)別考題總結(jié)(詳細(xì)答案).doc

1. 簡(jiǎn)述模式的概念及其直觀(guān)特性，模式識(shí)別的分類(lèi)，有哪幾種方法。（6）答（1）：什么是模式？廣義地說(shuō)，存在于時(shí)間和空間中可觀(guān)察的物體，如果我們可以區(qū)別它們是否相同或是否相似，都可以稱(chēng)之為模式。模式所指的不是事物本身，而是從事物獲得的信息，因此，模式往往表現(xiàn)為具有時(shí)間和空間分布的信息。模式的直觀(guān)特性：可觀(guān)察性；可區(qū)分性；相似性。答（2）：模式識(shí)別的分類(lèi)：假說(shuō)的兩種獲得方法（模式識(shí)別進(jìn)行學(xué)習(xí)的兩種方法）：l 監(jiān)督學(xué)習(xí)、概念驅(qū)動(dòng)或歸納假說(shuō)；l 非監(jiān)督學(xué)習(xí)、數(shù)據(jù)驅(qū)動(dòng)或演繹假說(shuō)。模式分類(lèi)的主要方法：l 數(shù)據(jù)聚類(lèi)：用某種相似性度量的方法將原始數(shù)據(jù)組織成有意義的和有用的各種數(shù)據(jù)集。是一種非監(jiān)督學(xué)習(xí)的方法，解決方案是數(shù)據(jù)驅(qū)動(dòng)的。l 統(tǒng)計(jì)分類(lèi)：基于概率統(tǒng)計(jì)模型得到各類(lèi)別的特征向量的分布，以取得分類(lèi)的方法。特征向量分布的獲得是基于一個(gè)類(lèi)別已知的訓(xùn)練樣本集。是一種監(jiān)督分類(lèi)的方法，分類(lèi)器是概念驅(qū)動(dòng)的。l 結(jié)構(gòu)模式識(shí)別：該方法通過(guò)考慮識(shí)別對(duì)象的各部分之間的聯(lián)系來(lái)達(dá)到識(shí)別分類(lèi)的目的。（句法模式識(shí)別）l 神經(jīng)網(wǎng)絡(luò)：由一系列互相聯(lián)系的、相同的單元（神經(jīng)元）組成。相互間的聯(lián)系可以在不同的神經(jīng)元之間傳遞增強(qiáng)或抑制信號(hào)。增強(qiáng)或抑制是通過(guò)調(diào)整神經(jīng)元相互間聯(lián)系的權(quán)重系數(shù)來(lái)（weight）實(shí)現(xiàn)。神經(jīng)網(wǎng)絡(luò)可以實(shí)現(xiàn)監(jiān)督和非監(jiān)督學(xué)習(xí)條件下的分類(lèi)。2. 什么是神經(jīng)網(wǎng)絡(luò)？有什么主要特點(diǎn)？選擇神經(jīng)網(wǎng)絡(luò)模式應(yīng)該考慮什么因素？（8）答（1）：所謂人工神經(jīng)網(wǎng)絡(luò)就是基于模仿生物大腦的結(jié)構(gòu)和功能而構(gòu)成的一種信息處理系統(tǒng)（計(jì)算機(jī)）。由于我們建立的信息處理系統(tǒng)實(shí)際上是模仿生理神經(jīng)網(wǎng)絡(luò)，因此稱(chēng)它為人工神經(jīng)網(wǎng)絡(luò)。這種網(wǎng)絡(luò)依靠系統(tǒng)的復(fù)雜程度，通過(guò)調(diào)整內(nèi)部大量節(jié)點(diǎn)之間相互連接的關(guān)系，從而達(dá)到處理信息的目的。人工神經(jīng)網(wǎng)絡(luò)的兩種操作過(guò)程：訓(xùn)練學(xué)習(xí)、正常操作（回憶操作）。答（2）：人工神經(jīng)網(wǎng)絡(luò)的特點(diǎn)：l 固有的并行結(jié)構(gòu)和并行處理；l 知識(shí)的分布存儲(chǔ)；l 有較強(qiáng)的容錯(cuò)性；l 有一定的自適應(yīng)性；人工神經(jīng)網(wǎng)絡(luò)的局限性：l 人工神經(jīng)網(wǎng)絡(luò)不適于高精度的計(jì)算；l 人工神經(jīng)網(wǎng)絡(luò)不適于做類(lèi)似順序計(jì)數(shù)的工作；l 人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)和訓(xùn)練往往是一個(gè)艱難的過(guò)程；l 人工神經(jīng)網(wǎng)絡(luò)必須克服時(shí)間域順序處理方面的困難；l 硬件限制；l 正確的訓(xùn)練數(shù)據(jù)的收集。答（3）：選取人工神經(jīng)網(wǎng)絡(luò)模型，要基于應(yīng)用的要求和人工神經(jīng)網(wǎng)絡(luò)模型的能力間的匹配，主要考慮因素包括：l 網(wǎng)絡(luò)大小；l 所需輸出類(lèi)型；l 聯(lián)想記憶類(lèi)型；l 訓(xùn)練方法；l 時(shí)間的限定。3. 畫(huà)出句法模式識(shí)別的框圖，并解釋其工作原理。（8）答（1）：句法模式識(shí)別框圖如下： 答（2）：句法模式識(shí)別系統(tǒng)的組成：圖像預(yù)處理，圖像分割，基元及其關(guān)系識(shí)別，句法分析?；诿枋瞿Ｊ降慕Y(jié)構(gòu)信息，用形式語(yǔ)言中的規(guī)則進(jìn)行分類(lèi)，可以更典型地應(yīng)用于景物圖片的分析。因?yàn)樵谶@類(lèi)問(wèn)題中，所研究的模式通常十分復(fù)雜，需要的特征也很多，僅用數(shù)值上的特征不足以反映它們的類(lèi)別。句法模式識(shí)別系統(tǒng)處理過(guò)程：基元本身包含的結(jié)構(gòu)信息已不多，僅需少量特征即可識(shí)別。如果用有限個(gè)字符代表不同的基元，則由基元按一定結(jié)構(gòu)關(guān)系組成的子圖或圖形可以用一個(gè)有序的字符串來(lái)代表。假如事先用形式語(yǔ)言的規(guī)則從字符串中推斷出能生成它的文法，則可以通過(guò)句法分析，按給定的句法（文法）來(lái)辨識(shí)由基元字符組成的句子，從而判別它是否屬于由該給定文法所能描述的模式類(lèi)，達(dá)到分類(lèi)的目的。4. （1）解釋線(xiàn)性判別函數(shù)進(jìn)行模式分類(lèi)的概念；（2）既然有了線(xiàn)性判別函數(shù)，為什么還要用非線(xiàn)性判別函數(shù)進(jìn)行模式分類(lèi)？（3）兩類(lèi)模式，每類(lèi)包括5個(gè)3維不同的模式，且良好分布。如果它們是線(xiàn)性可分的，問(wèn)權(quán)向量至少需要幾個(gè)系數(shù)分量？假如要建立二次的多項(xiàng)式判別函數(shù)，又至少需要幾個(gè)系數(shù)分量？（設(shè)模式的良好分布不因模式變化而改變。）（8）答（1）：模式識(shí)別系統(tǒng)的主要作用是判別各個(gè)模式所屬的類(lèi)別。線(xiàn)性判別函數(shù)分類(lèi)就是使用線(xiàn)性判別函數(shù)將多類(lèi)樣本模式分開(kāi)。 一個(gè)n維線(xiàn)性判別函數(shù)的一般形式：其中稱(chēng)為權(quán)向量（或參數(shù)向量），。也可表示為：其中，稱(chēng)為增廣模式向量，稱(chēng)為增廣權(quán)向量。兩類(lèi)情況：判別函數(shù)：多類(lèi)情況：設(shè)模式可分成共M類(lèi)，則有三種劃分方法：l 多類(lèi)情況1用線(xiàn)性判別函數(shù)將屬于類(lèi)的模式與不屬于類(lèi)的模式分開(kāi)，其判別函數(shù)為：這種情況稱(chēng)為兩分法，即把M類(lèi)多類(lèi)問(wèn)題分成M個(gè)兩類(lèi)問(wèn)題，因此共有M個(gè)判別函數(shù)，對(duì)應(yīng)的判別函數(shù)的權(quán)向量為。l 多類(lèi)情況2采用每對(duì)劃分，即兩分法，此時(shí)一個(gè)判別界面只能分開(kāi)兩種類(lèi)別，但不能把它與其余所有的界面分開(kāi)。其判別函數(shù)為：若，則重要性質(zhì)：要分開(kāi)M類(lèi)模式，共需M(M-1)/2個(gè)判別函數(shù)。不確定區(qū)域：若所有，找不到，的情況。l 多類(lèi)情況3（多類(lèi)情況2的特例）這是沒(méi)有不確定區(qū)域的兩分法。假若多類(lèi)情況2中的可分解成：，則相當(dāng)于，。這時(shí)不存在不確定區(qū)域。此時(shí)，對(duì)M類(lèi)情況應(yīng)有M個(gè)判別函數(shù)：即，則，也可寫(xiě)成，若，則。該分類(lèi)的特點(diǎn)是把M類(lèi)情況分成M-1個(gè)兩類(lèi)問(wèn)題。模式分類(lèi)若可用任一個(gè)線(xiàn)性函數(shù)來(lái)劃分，則這些模式就稱(chēng)為線(xiàn)性可分的，否則就是非線(xiàn)性可分的。一旦線(xiàn)性函數(shù)的系數(shù)wk被確定，這些函數(shù)就可用作模式分類(lèi)的基礎(chǔ)。對(duì)于M類(lèi)模式的分類(lèi)，多類(lèi)情況1需要M個(gè)判別函數(shù)，而多類(lèi)情況2需要M*(M-1)/2個(gè)判別函數(shù)，當(dāng)M較大時(shí)，后者需要更多的判別式（這是多類(lèi)情況2的一個(gè)缺點(diǎn)）。采用多類(lèi)情況1時(shí)，每一個(gè)判別函數(shù)都要把一種類(lèi)別的模式與其余M-1種類(lèi)別的模式分開(kāi)，而不是將一種類(lèi)別的模式僅與另一種類(lèi)別的模式分開(kāi)。由于一種模式的分布要比M-1種模式的分布更為聚集，因此多類(lèi)情況2對(duì)模式是線(xiàn)性可分的可能性比多類(lèi)情況1更大一些（這是多類(lèi)情況2的一個(gè)優(yōu)點(diǎn)）。答（2）廣義線(xiàn)性判別函數(shù)出發(fā)點(diǎn)：l 線(xiàn)性判別函數(shù)簡(jiǎn)單，容易實(shí)現(xiàn)；l 非線(xiàn)性判別函數(shù)復(fù)雜，不容易實(shí)現(xiàn)；l 若能將非線(xiàn)性判別函數(shù)轉(zhuǎn)換為線(xiàn)性判別函數(shù)，則有利于模式分類(lèi)的實(shí)現(xiàn)。采用廣義線(xiàn)性判別函數(shù)的概念，可以通過(guò)增加維數(shù)來(lái)得到線(xiàn)性判別，但維數(shù)的大量增加會(huì)使在低維空間里在解析和計(jì)算上行得通的方法在高維空間遇到困難，增加計(jì)算的復(fù)雜性。所以某些情況下使用非線(xiàn)性判別函數(shù)或分段線(xiàn)性判別函數(shù)效果更好。解（3）假設(shè)該兩類(lèi)模式是線(xiàn)性可分的，則在三維空間中一個(gè)線(xiàn)性平面可以將這兩類(lèi)模式分開(kāi)，所以判別函數(shù)可以寫(xiě)成： 所以權(quán)向量需要4個(gè)系數(shù)。對(duì)于n維x向量，采用r次多項(xiàng)式，d(x)的權(quán)系數(shù)w的項(xiàng)數(shù)為： 當(dāng)r=2，n=3時(shí)， 所以，此時(shí)權(quán)向量需要10個(gè)系數(shù)分量。5. 設(shè)一有限態(tài)自動(dòng)機(jī)，定義如下： 試求等價(jià)的正則文法，使得L(G)=T(A)。（10）解：設(shè)由A得一正則文法，則，由，得生成式 由，得生成式 由，得生成式 由，得生成式 由，得生成式 由，得生成式 對(duì)比實(shí)例：當(dāng)掃描字符串1110時(shí)，A按以下?tīng)顟B(tài)序列接受該字符串用對(duì)應(yīng)的正則文法G推導(dǎo)，得：l 按有限態(tài)自動(dòng)機(jī)確定正則文法給定一個(gè)有限態(tài)自動(dòng)機(jī)，可確定一個(gè)正則文法，使得L(G) = T(A)。由 ，可確定：，。從求G中的生成式P可按如下原則：(1)若，則(2)若，則6. K-均值算法聚類(lèi)：K=2，初始聚類(lèi)中心為，數(shù)據(jù)為：（10） 算法：第一步：選個(gè)初始聚類(lèi)中心，其中括號(hào)內(nèi)的序號(hào)為尋找聚類(lèi)中心的迭代運(yùn)算的次序號(hào)?？蛇x開(kāi)始的 個(gè)模式樣本的向量值作為初始聚類(lèi)中心。第二步：逐個(gè)將需分類(lèi)的模式樣本按最小距離準(zhǔn)則分配給個(gè)聚類(lèi)中心中的某一個(gè)。即，則，其中 為迭代運(yùn)算的次序號(hào)，第一次迭代，表示第個(gè)聚類(lèi)，其聚類(lèi)中心為。第三步：計(jì)算各個(gè)聚類(lèi)中心的新的向量值，求各聚類(lèi)域中所包含樣本的均值向量：其中為第個(gè)聚類(lèi)域中所包含的樣本個(gè)數(shù)。以均值向量作為新的聚類(lèi)中心，可使如下聚類(lèi)準(zhǔn)則函數(shù)最?。涸谶@一步中要分別計(jì)算K個(gè)聚類(lèi)中的樣本均值向量，所以稱(chēng)之為K-均值算法。第四步：若，則返回第二步，將模式樣本逐個(gè)重新分類(lèi)，重復(fù)迭代運(yùn)算；若，則算法收斂，計(jì)算結(jié)束。7. 給出兩類(lèi)模式分布，每一列代表一個(gè)樣本： ： ：試用K-L變換來(lái)做一維特征的提取（12）。解：首先將所有樣本看作一個(gè)整體，求出樣本均值向量： 由于均值為0，符合K-L變換的最佳條件。如果均值不為0，則所有樣本要減去均值向量。由于和的樣本數(shù)相同，所以認(rèn)為他們的先驗(yàn)概率相同，即：求出總體的自相關(guān)矩陣或協(xié)方差矩陣： 解特征方程，求出的特征值： 求出對(duì)應(yīng)于特征值的特征向量： 選取對(duì)應(yīng)的特征向量作為變換矩陣，由得出變換后的一維模式： ： ：8. 用第二類(lèi)勢(shì)函數(shù)的算法進(jìn)行分類(lèi)（10）選擇指數(shù)型勢(shì)函數(shù)，取=1，在二維情況下勢(shì)函數(shù)為：這里：1類(lèi)為x=(0 0)T, x=(2 0)T；2類(lèi)為x=(1 1)T, x=(1 -1)T解：可以看出，這兩類(lèi)模式是線(xiàn)性不可分的。算法步驟如下：第一步：取 ，則 第二步：取因，故 第三步：取因，故 后面同理，就是不斷將樣本帶入，如果分類(lèi)正確，則勢(shì)函數(shù)保持不變，即： 如果分類(lèi)錯(cuò)誤，則有兩種情況：l ，則l ，則經(jīng)過(guò)迭代，全部模式都已正確分類(lèi)，因此算法收斂于判別函數(shù)。得出：9. 有一種病，正常為 ，不正常為 ，已知： 現(xiàn)對(duì)某人進(jìn)行檢查，結(jié)果為，由概率曲線(xiàn)查出： 風(fēng)險(xiǎn)代價(jià)矩陣為： 對(duì)該檢查者進(jìn)行判決：（1） 用貝葉斯最小錯(cuò)誤概率判別，求出判決函數(shù)和決策分界面。（2） 用貝葉斯最小風(fēng)險(xiǎn)判別，求出判別函數(shù)和決策分界面。解（1）： 由于 所以。解（2）： 由于 所以。10. 闡述誤差反傳算法（BP算法）的原理，并寫(xiě)出其訓(xùn)練步驟。答（1）：l BP算法推算過(guò)程：當(dāng)加入第k個(gè)輸入時(shí)，隱蔽層h結(jié)點(diǎn)的輸入加權(quán)和為：如果令第一層的加權(quán)矩陣為 ，則還可以表示為： 相應(yīng)節(jié)點(diǎn)的輸出為：寫(xiě)成矩陣形式為： 同樣，輸出層j結(jié)點(diǎn)的輸入加權(quán)和為：令第二次的加權(quán)矩陣為，則可以寫(xiě)成： 相應(yīng)點(diǎn)的輸出：寫(xiě)成矩陣形式為： 這里，各結(jié)點(diǎn)的閾值等效為一個(gè)連接的加權(quán)或，這些連接由各結(jié)點(diǎn)連到具有固定值-1的偏置結(jié)點(diǎn)，其連接加權(quán)也是可調(diào)的，同其它加權(quán)一樣參與調(diào)節(jié)過(guò)程。誤差函數(shù)為：為了使誤差函數(shù)最小，用梯度下降法求得最優(yōu)的加權(quán)，權(quán)值先從輸出層開(kāi)始修正，然后依次修正前層權(quán)值，因此含有反傳的含義。根據(jù)梯度下降法，由隱蔽層到輸出層的連接的加權(quán)調(diào)節(jié)量為：其中為輸出結(jié)點(diǎn)的誤差信號(hào)：在BP算法中常采用Sigmoid函數(shù)：其導(dǎo)數(shù)為： 對(duì)應(yīng)的誤差為：對(duì)于輸入層到隱蔽層結(jié)點(diǎn)連接的加權(quán)修正量，必須考慮將對(duì)求導(dǎo)，因此利用分層鏈路法，有：其中：這樣就可以根據(jù)和分別調(diào)整輸出層和隱層的權(quán)值了。l BP訓(xùn)練算法實(shí)現(xiàn)步驟準(zhǔn)備：設(shè)網(wǎng)絡(luò)具有m層，表示第m層中第j個(gè)結(jié)點(diǎn)的輸出，（零層輸出）等于，即第j個(gè)輸入。表示從到的連接加權(quán)。這里，m代表層號(hào)，而不是向量的類(lèi)號(hào)。1.（初始化加權(quán)矩陣）將各加權(quán)隨機(jī)置為小的隨機(jī)數(shù)?？捎镁鶆蚍植嫉碾S機(jī)數(shù)，以保證網(wǎng)絡(luò)不被大的加權(quán)值所飽和。2.（輸入數(shù)據(jù)）從訓(xùn)練數(shù)據(jù)組中選一數(shù)據(jù)對(duì)，將輸入向量加到輸入層（m=0），使得對(duì)所有端點(diǎn)i：，k表示向量類(lèi)號(hào)。3.（輸出預(yù)測(cè)數(shù)據(jù)）信號(hào)通過(guò)網(wǎng)絡(luò)向前傳播，即利用關(guān)系式：計(jì)算從第一層開(kāi)始的各層內(nèi)每個(gè)結(jié)點(diǎn)i的輸出，直到輸出層的每個(gè)結(jié)點(diǎn)的輸出計(jì)算完為止。4.（計(jì)算輸出層誤差）計(jì)算輸出層每個(gè)結(jié)點(diǎn)的誤差值，對(duì)Sigmod函數(shù)：它是由實(shí)際輸出和要求目標(biāo)值之差獲得。5.（誤差反傳）計(jì)算前面各層各結(jié)點(diǎn)的誤差值這里逐層計(jì)算反傳誤差，直到將每層內(nèi)每個(gè)結(jié)點(diǎn)的誤差值算出為止。6.（修改權(quán)值）利用加權(quán)修正公式：修正所有連接權(quán)。一般，稱(chēng)為訓(xùn)練速率系數(shù)。7.（運(yùn)算至權(quán)值收斂）返回第2步，為下一個(gè)輸入向量重復(fù)上述步驟，直至網(wǎng)絡(luò)收斂。