第十讲 句法模式识别.doc

1、1第十讲 句法模式识别一、 基本概念1、结构模式识别：有一些模式识别任务，不能在特征空间中用统计模式识别的方法得到解决。汉字的识别：汉字有偏旁部首、笔划构成字符的识别：字符的字体不影响识别语言的识别：语言由音节、字、词构成图像识别：画面分割，目标识别生物识别：基因序列，染色体结构，心电图分类定义：以结构基元为基础，利用模式的结构信息完成分类的过程，称为“结构模式识别” 。其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的结构信息。基元的选取与应用有关：文字：笔划或偏旁部首作为基元语音：音素作为基元心电图：收缩波和扩张波作为基元图形：边缘线段、角点都可作为基元 a ccbbbdddcc

2、cbbbd dabcd轮廓基元讨论：结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个基于结构信息，一个基于特征值结构模式识别不仅能完成分类，还可以得到每个模式的结构性质结构模式识别的依据是模式间结构上的“相似性” ，这种相似度的度量不能用一般特征空间中的距离来表示结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟结构模式识别系统的模式信息通常来源于图像、音频等多媒体信息源2、句法模式识别（1）句法模式识别的定义：句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构2模式识别的方法。傅京荪（1930-1

3、985）美国工程院院士、Purdue 大学讲座教授、台湾中央研究院院士，国际模式识别协会(International Association for Pattern Recognition:IAPR)创始人和首任主席，上世纪 60 年代提出句法模式识别。（2）句法和文法：句法句法来源于语言学，是指由字（词）构成句子的方式，也就是一个句子组成的规则。句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂的结构。可以用句法来表达结构模式识别中基元间的结构关系。文法文法是指一类相似的句子的共同句法规则。可以用文法来表示一类样本的共同特点。对某个具体的句子进行句法分析，判别与某类的文法是否相似，可

4、以实现模式识别。（3）形式语言：形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语言的“数学化 ”，它由按 一 定 规 律 构 成 的 句 子 或 符 号 串 的 有 限 或 无 限 的 集 合 组成 。乔 姆 斯 基 （ Noam Chomsky, 1928-）美 国 语 言 学 家 ， 麻省理工学院語言学与哲学系荣誉退休教授，曾 任 该 系 主 任 ， 并 任 该 校认 知 科 学 研 究 中 心 主 任 。 1957 年 出 版 了 句法 结 构 一 书 ， 提 出 了 形 式 语 言 理 论 ， 其 最初目的是为了研究人类语言抽象和通用的结构规则，后来在计算机编程语言、自

5、动机理论、模式识别等方面都得到了广泛的验证和应用。在 1980年到 1992 年，乔姆斯基是被文献引用数最多的健在 学者，并是有史以来被引用数第八多的学者。3、句法模式识别系统的组成3预处理 特征提取（基元提取）句法分析文法推断模式信息分类结果类别文法训练过程分类过程（1（ 句法分析：判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。（2（文法推断：从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文法规则。利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结构模式识别问题的求解二、 形式语言理论1、基本概念：（1）字母表：与所研究的问题有关的符号集合

6、。例：V 1=A,B,C,D, V2=a,b,c,d,V3=0,2,6,8（2）句子(链) ：由字母表中的符号所组成的有限长度的符号串。例如有字母表0,1，则0,1,00,01,0110 就是有效句子的集合。不包括任何符号的句子称为空句，记为 。V*：由字母表 V 中的符号组成的所有句子的集合，包括空句子 在内。例： V* ,01, 001V ：不包括空句子在内的句子集合，即 V V *()（3）句子(链) 的长度：句子所包含的符号数目，例: |a 3b3c3|=9（4）语言：由字母表中的符号组成的句子集合，用 L 表示。例：字母表 V=a,bL1=ab,aab,abab 有限语言L2=anb

7、m|n,m=0,1,2.无限语言在一种语言中，构成任何句子都必须遵循统一的规则，这些规则的集合称为文法，用 G 表示。L(G)表示由文法 G 构成的语言。（5）文法文法的数学定义：它是一个四元式，由四个参数构成：4G=VN, VT, P, SVT：终止符，不能再分割的最简基元的集合，用小写字母表示。 VT=a,b,cVN：非终止符，由基元组成的子模式和句子的集合。用大写字母表示。VN=A,B,CVT， VN 的关系： VTV N= (空集)VT V N= V（全部字母表）S：起始符：属于 VN 非终止符中的一个符号P：产生式 (再写规则)，存在于终止符和非终止符间的关系式。 例： ， V N

8、， V N, VT.例：V T 你，我，他，吃，饭，水果；VN 句子，主语，谓语，宾语； S“句子” ；P：S “主语”“ 谓语 ”“宾语”；“主语 ” “你”， “主语” “我”， “主语 ” “他”；“谓语 ” “吃”；“宾语 ” “饭”， “宾语” “水果”，2、4 种类型的文法：（1）无约束文法（0 型文法）设文法 G = (VN,VT, P, S)VN：非终止符，用大写字母表示VT：终止符，用小写字符表示S：起始符P： ， 其中 V +，V * ， 无任何限制例： 0 型文法 G = (VN,VT, P, S)，V N = S,A，V T = a,b,cP: SaSb SbbA ab

9、AcSaSb aaSbba nSbna nbAbn-1 a n-1abAbn-1a n-1cbn-1此文法 G 可产生的语言为： L(G)=ancbn|n=0,1,2.（2）上下文有关文法（1 型文法）设文法 G = (VN,VT, P, S)P： 1A 2 1 2 其中 A V N ， V +, 1, 2V * | 1A 2| 1 2|, 或|A| | 1 和 2 被视为 A 的上下文例：G = (VN,VT, P, S)， VN = S, B, C VT = a, b, c5P: SaSBC SabC CBBC bB bb bC bc cCccP 可改写为：S aSBC SabCCB BC

10、 bBbb bCbc cCcc 都符合 1 型文法规则所以 G 属于上下文有关文法SabC abcSaSBCaabCBCaabBCC aabbCCaabbcC aabbcc SaSBC aaSBCBC aaabCBCBC aaabBCCBC aaabBCBCC aaabBBCCC aaabbBCCC aaabbbCCC aaabbbcCC aaabbbccC aaabbbccc 此文法 G 可产生的语言为：L(G)=anbncn|n=1,2.L(G)=anbncn|n=1,2.acba cbaa ccb baa ccb bacb基元 结构相似的样本（3）上下文无关文法（2 型文法）设文法 G

11、= (VN,VT, P, S)产生式 P： A 其中 AV N（是单个的非终止符) V + (可以是终止符，非终止符，不能是空句)6对产生式的限制更严格例：文法 G = (VN,VT, P, S)，V N = S, A, B，V T = a, bP: SaB SbA Aa AaS AbAA Bb BbS BaBB 各生成式左侧均为 VN，右侧为 VN 和 VT 的混合，满足上下文无关文法的生成规则，SaBabSabaBababSaBabSabbAabbaSbAbaSbaaB baabSbAbaSbabAbabaSaB abSbAba两种方法替换非终止符： 最左推导：每次替换都是先从最左边的非终

12、止符开始。 最右推导：每次替换都是先从最右边的非终止符开始，（4）正则文法（3 型文法）设文法 G = (VN,VT, P, S)产生式 P：A aB 或 Aa，其中 A,BV N（且是单个字符） ，aV T（且是单个字符）产生式右端必须含有终止符正则文法可用状态图表示，非终止符代表状态，终止符代表状态转移的类型例：文法 G = (S, A,0, 1, P, S)P: S 0A A0A A1 上述生成式满足正则文法生成规则。S0A00A000A0001 此文法 G 可产生的语言为：L(G)=0n1|n=1,2.此文法对应的状态图为：7SA T100 状态图（5）四种文法的关系3型 2型 1型0

13、型限制不严格的文法必然包含限制严格的文法。（6）四种文法和自动机的关系0 型无约束文法 图灵机1 型上下文有关文法 线性界限自动机2 型上下文无关文法 下推自动机3 型正则文法 有限状态自动机三、 句法分析1、模式识别中的句法分析：设有 m 个模式类，分别为 1, 2, m ，又有对应的 m 种文法G1，G 2，G m，如对于任意样本 x，当有 x L （G i）时，可判定 x i，则分类器可由句法分析判别构成。8判决XL（ G1）？XL（ Gm）？分类结果待分类样本 x2、句法分析的主要方法：（1）参考匹配法：x参考链X 1 xx 参考链X 2 x参考链X N 判决 x ixX i将待识别的

14、样本 x（句子）与代表各类的模板或参考链 Xi 进行匹配，将 x分类到匹配得最好的参考链对应的类特点：简单快速，但未充分利用句法信息，也无法得到 x 的句法结构。（2）状态图法（适用于正则文法）：先画出正则文法对应的状态图：方法一：从状态图的起始符开始，依次处理输入模式 x 的各个字符，如果可以找到一条通往终止状态 T 的通路，则表示 x 可以由该状态图生成。方法二：从状态图推导中出该文法可产生的所有句子的形式，再用待识别模式 x 去匹配；例：正则文法 G = (S, A,0, 1, P, S)P: S 0A A0A A1状态图中的每一个状态（节点）为1 个非终止符，T 为终止状态AaB 代表

15、两个节点间的状态转移，Aa 代表状态转移的结束。法一：x 1=0100 不属于该类，x 20001 属于该类法二：可推导出该文法可产生的语言为：L(G)=0 n1|n=1,2.9SA T100 状态图例：G = (VN,VT, P, S)，V N =（S, A, B, C） ，V T =（0,1）P: S1A，S0B，S1C，A0A，A0，B0，C0C，C0，C1BSCBAT1 10001000状态图法一： x1=10010，存在通路，可以识别；x2=10110 ，不存在通路，不可识别法二： 此文法可生成的句子类型有：X1=10n+1 , X2=00 , X3=10n10, n=0,1,2,（

16、3）填充树法（适用于上下文无关文法）：当给定某待识别句子 x 及某个模式类的文法 G 时，我们建立一个以 x 为底，S 为顶的三角形，按文法 G 的产生式来填充此三角形。若填充成功表明， x 可分到该模式类。填充树法是一种穷举法10Sx填充填充树图法在填充三角形时应遵守三条原则：首位考察：首先考虑选用某个产生式后能导出 x 的第一个字符；用某产生式后，不能出现 x 中不包含的终止符；用某产生式后，不能导致最终符号串变长(变短)，即保证单向递增（递减）填充树有二种方法：由顶向底和由底向顶由顶向底剖析从起始符 S 开始，依次向下利用产生式来产生 x 中的某个终止符，一直到产生完整的 x 为止。如已

17、不存在非终止符，但是仍旧没有得到 x；或还存在非终止符，但已得到的句子长度超过了 x，则表示 x 不属于该文法定义的类。例：G = (VN,VT, P, S)，V T =（0,1） VN =（S, A, B）P: S1 SB1 SB B 1A B B1A A0A A 0问：x=1000，用由顶向底剖析方法判断 x 是否属于 L(G)？ x=1000 L(G)BSBS1 AB10 AASB10 AAS0 AB10 AAS0 A0由底向顶剖析从待识别的句子 x 开始，依次看 x 中的每个终止符可以由哪个非终止符产生，一直推导到所有 x 中的终止符都可以由起始符 S 逐步产生为止。先生成那些可直接生成的单个终止符，再推导那些无法单独生成的终止符。例：G = (VN,VT, P, S)，V T =（a,b,c,d,e）V N =（S, T, I）