第十講 句法模式識(shí)別

1、1第十講第十講句法模式識(shí)別句法模式識(shí)別一、一、基本概念基本概念1、結(jié)構(gòu)模式識(shí)別：、結(jié)構(gòu)模式識(shí)別：有一些模式識(shí)別任務(wù)，不能在特征空間中用統(tǒng)計(jì)模式識(shí)別的方法得到解決。漢字的識(shí)別：漢字有偏旁部首、筆劃構(gòu)成字符的識(shí)別：字符的字體不影響識(shí)別語(yǔ)言的識(shí)別：語(yǔ)言由音節(jié)、字、詞構(gòu)成圖像識(shí)別：畫(huà)面分割，目標(biāo)識(shí)別生物識(shí)別：基因序列，染色體結(jié)構(gòu)，心電圖分類(lèi)定義：以結(jié)構(gòu)基元為基礎(chǔ)，利用模式的結(jié)構(gòu)信息完成分類(lèi)的過(guò)程，稱(chēng)為“結(jié)構(gòu)模式識(shí)別”。其中“基元”指構(gòu)成模式結(jié)構(gòu)

2、信息的基本單元，本身不包含有意義的結(jié)構(gòu)信息?；倪x取與應(yīng)用有關(guān)：文字：筆劃或偏旁部首作為基元語(yǔ)音：音素作為基元心電圖：收縮波和擴(kuò)張波作為基元圖形：邊緣線段、角點(diǎn)都可作為基元accbbbdddcccbbbddabcd輪廓基元輪廓基元討論：結(jié)構(gòu)模式識(shí)別是與統(tǒng)計(jì)模式識(shí)別完全不同的一大類(lèi)模式識(shí)別問(wèn)題，一個(gè)基于結(jié)構(gòu)信息，一個(gè)基于特征值結(jié)構(gòu)模式識(shí)別不僅能完成分類(lèi)，還可以得到每個(gè)模式的結(jié)構(gòu)性質(zhì)結(jié)構(gòu)模式識(shí)別的依據(jù)是模式間結(jié)構(gòu)上的“相似性”，這種相似度

3、的度量不能用一般特征空間中的距離來(lái)表示結(jié)構(gòu)模式識(shí)別可以采用句法方法、拓?fù)浞治龇椒?、圖論方法等多種方法基元提取和分類(lèi)器訓(xùn)練上的困難使得結(jié)構(gòu)模式識(shí)別方法仍未成熟結(jié)構(gòu)模式識(shí)別系統(tǒng)的模式信息通常來(lái)源于圖像、音頻等多媒體信息源2、句法模式識(shí)別、句法模式識(shí)別（1）句法模式識(shí)別的定義：句法模式識(shí)別是利用模式的結(jié)構(gòu)信息，以形式語(yǔ)言理論為基礎(chǔ)來(lái)進(jìn)行結(jié)構(gòu)3預(yù)處理特征提取（基元提?。┚浞ǚ治鑫姆ㄍ茢嗄Ｊ叫畔⒎诸?lèi)結(jié)果類(lèi)別文法訓(xùn)練過(guò)程分類(lèi)過(guò)程（1（句法分析：判斷

4、一個(gè)樣本是否符合一定的文法，從而得到該樣本與已知類(lèi)別的相似性。（2（文法推斷：從分好類(lèi)的訓(xùn)練集中獲得該類(lèi)所有樣本的共同特征，形成代表每個(gè)類(lèi)別的文法規(guī)則。利用形式語(yǔ)言理論完善和堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，可用句法分析的方法來(lái)實(shí)現(xiàn)結(jié)構(gòu)模式識(shí)別問(wèn)題的求解二、二、形式語(yǔ)言理論形式語(yǔ)言理論1、基本概念：基本概念：（1）字母表：與所研究的問(wèn)題有關(guān)的符號(hào)集合。例：V1=ABCDV2=abcdV3=0268（2）句子(鏈)：由字母表中的符號(hào)所組成的有限長(zhǎng)度的符號(hào)串

5、。例如有字母表01，則0100010110就是有效句子的集合。不包括任何符號(hào)的句子稱(chēng)為空句，記為λ。V：由字母表V中的符號(hào)組成的所有句子的集合，包括空句子λ在內(nèi)。例：V＝λ01001V＋：不包括空句子在內(nèi)的句子集合，即V＋＝V－(λ)（3）句子(鏈)的長(zhǎng)度：句子所包含的符號(hào)數(shù)目，例:|a3b3c3|=9（4）語(yǔ)言：由字母表中的符號(hào)組成的句子集合，用L表示。例：字母表V=abL1=abaababab有限語(yǔ)言L2=anbm|nm=012….