中科院-模式識別考題總結(詳細答案).doc

《中科院-模式識別考題總結(詳細答案).doc》由會員分享，可在線閱讀，更多相關《中科院-模式識別考題總結(詳細答案).doc（11頁珍藏版）》請在裝配圖網上搜索。

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