第十讲 句法模式识别.doc

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