1第十讲第十讲 句法模式识别句法模式识别一、一、 基本概念基本概念1、结构模式识别：、结构模式识别： 有一些模式识别任务，不能在特征空间中用统计模式识别的方法得到解决。汉字的识别：汉字有偏旁部首、笔划构成 字符的识别：字符的字体不影响识别 语言的识别：语言由音节、字、词构成 图像识别：画面分割，目标识别 生物识别：基因序列，染色体结构，心电图分类 定义： 以结构基元为基础，利用模式的结构信息完成分类的过程，称为“结 构模式识别”。 其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的 结构信息。 基元的选取与应用有关： 文字：笔划或偏旁部首作为基元 语音：音素作为基元 心电图：收缩波和扩张波作为基元 图形：边缘线段、角点都可作为基元 accbb bdddcccb b b ddabcd轮廓基元轮廓基元 讨论： 结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个 基于结构信息，一个基于特征值 结构模式识别不仅能完成分类，还可以得到每个模式的结构性质 结构模式识别的依据是模式间结构上的“相似性”，这种相似度的度量不 能用一般特征空间中的距离来表示 结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法 基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟 结构模式识别系统的模式信息通常来源于图像、音频等多媒体信息源 2、句法模式识别、句法模式识别 （1）句法模式识别的定义： 句法模式识别是利用模式的结构信息，以形式语言理论为基础来行结构2模式识别的方法。 傅京荪（1930-1985） 美国工程院院士、Purdue 大学讲座教授、台湾 中央研究院院士，国际模式识别协会(International Association for Pattern Recognition:IAPR)创始人 和首任主席，上世纪 60 年代提出句法模式识别。（2）句法和文法： 句法 句法来源于语言学，是指由字（词）构成句子的方式，也就是一 个句子组成的规则。 句法具有递归性，可以重复组合使用，用简单的规则可以表达复 杂的结构。 可以用句法来表达结构模式识别中基元间的结构关系。 文法 文法是指一类相似的句子的共同句法规则。 可以用文法来表示一类样本的共同特点。 对某个具体的句子行句法分析，判别与某类的文法是否相似， 可以实现模式识别。 （3）形式语言：形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语 言的“数学化”，它由按一定规律构成的句子或符号串的有限或无限的集合 组 成。乔姆斯基（Noam Chomsky, 1928-） 美国语言学家，麻省理工学院語言学与哲 学系荣誉退休教授，曾任该系主任，并任该校 认知科学研究中心主任 。1957 年出版了句 法结构一书，提出了形式语 言理论，其最初 目的是为了研究人类语言抽象和通用的结构规则 ，后来在计算机编程语言、自动机理论、模式识 别等方面都得到了广泛的验证和应用。在 1980 年到 1992 年，乔姆斯基是被文献引用数最多的 健在学者，并是有史以来被引用数第八多的学者 。3、句法模式识别系统的组成、句法模式识别系统的组成3预处理特征提取 （基元提取）句法分析文法推断模式信息分类结果类别文法训练过程分类过程（1（句法分析： 判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。（2（文法推断： 从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的 文法规则。 利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现 结构模式识别问题的求解二、二、 形式语言理论形式语言理论1、基本概念：基本概念： （1）字母表：与所研究的问题有关的符号集合。例：V1=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, 001 V：不包括空句子在内的句子集合，即 VV*() （3）句子(链)的长度：句子所包含的符号数目，例: |a3b3c3|=9 （4）语言：由字母表中的符号组成的句子集合，用 L 表示。例：字母表 V=a,bL1=ab,aab,abab 有限语言L2=anbm|n,m=0,1,2.无限语言 在一种语言中，构成任何句子都必须遵循统一的规则，这些规则的集合 称为文法，用 G 表示。L(G)表示由文法 G 构成的语言。 （5）文法文法的数学定义：它是一个四元式，由四个参数构成：4G=VN, VT, P, S VT：终止符，不能再分割的最简基元的集合，用小写字母表示。 VT=a,b,c VN：非终止符，由基元组成的子模式和句子的集合。用大写字母表示。 VN=A,B,C VT， VN的关系： VTVN= (空集)VT VN= V（全部字母表）S：起始符：属于 VN非终止符中的一个符号 P：产生式(再写规则)，存在于终止符和非终止符间的关系式。 例： ， VN ， VN, VT. 例：VT你，我，他，吃，饭，水果；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)，VN = S,A，VT = a,b,cP: SaSb SbbA abAcSaSbaaSbbanSbnanbAbn-1 an-1abAbn-1an-1cbn-1此文法 G 可产生的语言为： L(G)=ancbn|n=0,1,2. （2）上下文有关文法（1 型文法） 设文法 G = (VN,VT, P, S)P：1A212 其中 A VN ，V+, 1,2V* |1A2|12|, 或|A|1和 2被视为 A 的上下文例：G = (VN,VT, P, S)， VN = S, B, C VT = a, b, c5P: SaSBC SabC CBBC bBbb bCbc cCccP 可改写为：SaSBC SabCCBBC bBbb bCbc cCcc都符合 1 型文法规则 所以 G 属于上下文有关文法SabCabcSaSBCaabCBCaabBCCaabbCCaabbcCaabbcc SaSBC aaSBCBC aaabCBCBC aaabBCCBC aaabBCBCC aaabBBCCC aaabbBCCC aaabbbCCC aaabbbcCC aaabbbccC aaabbbccc 此文法 G 可产生的语言为：L(G)=anbncn|n=1,2.L(G)=anbncn|n=1,2.acbacbaaccbbaaccbba cb基元基元结构相似的样本结构相似的样本（3）上下文无关文法（2 型文法）设文法 G = (VN,VT, P, S)产生式 P： A 其中 AVN（是单个的非终止符) V+ (可以是终止符，非终止符，不能是空句)6对产生式的限制更严格 例：文法 G = (VN,VT, P, S)，VN = S, A, B，VT = a, bP: SaB SbA Aa AaS AbAA Bb BbS BaBB 各生成式左侧均为 VN，右侧为 VN和 VT的混合，满足上下文无关文法 的生成规则，SaBabSabaBababSaBabSabbAabbaSbAbaSbaaBbaabSbAbaSbabAbabaSaBabSbAba两种方法替换非终止符： 最左推导：每次替换都是先从最左边的非终止符开始。 最右推导：每次替换都是先从最右边的非终止符开始， （4）正则文法（3 型文法） 设文法 G = (VN,VT, P, S)产生式 P：AaB 或 Aa，其中 A,BVN（且是单个字符） ，aVT（且是单个字符）产生式右端必须含有终止符 正则文法可用状态图表示，非终止符代表状态，终止符代表状态转移的 类型 例：文法 G = (S, A,0, 1, P, S)P: S0A A0A A1 上述生成式满足正则文法生成规则。S0A00A000A0001 此文法 G 可产生的语言为：L(G)=0n1|n=1,2.此文法对应的状态图为：7SAT100状态图状态图（5）四种文法的关系3型2型1型0型限制不严格的文法必然包含限制严格的文法。 （6）四种文法和自动机的关系0 型无约束文法 图灵机1 型上下文有关文法 线性界限自动机2 型上下文无关文法 下推自动机3 型正则文法 有限状态自动机三、三、 句法分析句法分析1、模式识别中的句法分析：、模式识别中的句法分析： 设有 m 个模式类，分别为 1, 2, m ，又有对应的 m 种文法 G1，G2，Gm，如对于任意样本 x，当有 x L（Gi）时，可判定 xi，则 分类器可由句法分析判别构成。8判决判决X X L L（G G1 1）？）？X X L L（G Gmm）？）？分类结果分类结果待分类样本待分类样本x x2、句法分析的主要方法：、句法分析的主要方法： （1）参考匹配法：x参考链参考链X1 xx 参考链参考链X2 x参考链参考链XN 判决判决xixX将待识别的样本 x（句子）与代表各类的模板或参考链 行匹配，将 x 分类到匹配得最好的参考链对应的类 特点：简单快速，但未充分利用句法信息，也无法得到 x 的句法结构。 （2）状态图法（适用于正则文法）：）状态图法（适用于正则文法）： 先画出正则文法对应的状态图： 方法一：从状态图的起始符开始，依次处理输入模式 x 的各个字符，如 果可以找到一条通往终止状态 T 的通路，则表示 x 可以由该状态图生成。方法二：从状态图推导中出该文法可产生的所有句子的形式，再用待识 别模式 x 去匹配； 例：正则文法 G = (S, A,0, 1, P, S)P: S0A A0A A1状态图中的每一个状态（节点）为1 个非终止符，T 为终止状态AaB 代表两个节点间的状态转移，Aa 代表状态转移的结束。法一：x1=0100 不属于该类，x20001 属于该类 法二：可推导出该文法可产生的语言为：L(G)=0n1|n=1,2.9SAT100状态图状态图例：G = (VN,VT, P, S)，VN =（S, A, B, C） ，VT =（0,1）P: S1A，S0B，S1C，A0A，A0，B0，C0C，C0，C1BSCBAT110001000状态图状态图法一： x1=