《句法模式识别.docx》由会员分享，可在线阅读，更多相关《句法模式识别.docx（12页珍藏版）》请在三一文库上搜索。
1、第十讲句法模式识别、 基本概念1、结构模式识别：有一些模式识别任务，不能在特征空间中用统计模式识别的方法得到解决。 汉字的识别：汉字有偏旁部首、笔划构成 字符的识别：字符的字体不影响识别 语言'的识别：语言'由首节、字、词构成 图像识别：画面分割，目标识别 生物识别：基因序列，染色体结构，心电图分类定义：以结构基元为基础，利用模式的结构信息完成分类的过程，称为结构模式识别”。其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的结构信息。基元的选取与应用有关： 文字：笔划或偏旁部首作为基元 语音：音素作为基元 心电图：收缩波和扩张波作为基元 图形：边缘线段、角点都可作为基
2、元轮廓基元讨论：结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个基丁结构信息，一个基丁特征值结构模式识别不仅能完成分类，还可以得到每个模式的结构性质结构模式识别的依据是模式问结构上的 相似性”，这种相似度的度量不能用一般特征空间中的距离来表示结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟结构模式识别系统的模式信息通常来源丁图像、音频等多媒体信息源2、句法模式识别(1) 句法模式识别的定义：句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构模式识别的方法。傅京苏(1930-1985)美国工程院院士
3、、 Purdue大学讲座教授、台湾 中央研究院院士，国际模式识别协会 (International Association for Pattern Recognition:IAPR) 创始人和 首任主席，上世纪60年代提出句法模式识别。(2) 句法和文法：句法句法来源丁语言学，是指由字(词)构成句子的方式，也就是一个 句子组成的规则。句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂 的结构。可以用句法来表达结构模式识别中基元间的结构关系。寺文法文法是指一类相似的句子的共同句法规则。可以用文法来表示一类样本的共同特点。对某个具体的句子进行句法分析，判别与某类的文法是否相似，可 以实现模
4、式识别。(3) 形式语言':形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言， 是语言 的数学化”，它由按一定规律构成的句子或符号申的有限或无限的集合组成。乔姆斯基(Noam Chomsky, 1928-)美国语言学家，麻省理工学院言吾吉学与哲学 系荣誉退休教授，曾任该系主任，并任该校认 知科学研究中心主任。1957年出版了句法结 构一书，提出了形式语言理论，其最初目的 是为了研究人类语言抽象和通用的结构规则，后 来在计算机编程语言'、自动机理论、模式识别等 方面都得到了广泛的验证和应用。 在1980年到1 992年，乔姆斯基是被文献引用数最多的健在学 者，并是有史以
5、来被引用数第八多的学者。3、句法模式识别系统的组成分类过程训练过程(1) 句法分析：判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。(2) 文法推断：从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文 法规则。利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结构模式识别问题的求解二、形式语言理论1、基本概念：(1) 字母表：与所研究的问题有关的符号集合。例：Vi=A,B,C,D, V 2=a,b,c,d,V 3=0,2,6,8(2) 句子(链)：由字母表中的符号所组成的有限长度的符号申。例如有字母表0,1，则0,1,00,01,0110就是有效句
6、子的集合。不包括任何符号的句子称为空句，记为入。V*:由字母表V中的符号组成的所有句子的集合，包括空句子入在内c例：V*= 入,01, 001工一,一、44.»、A一.工*V :不包括空句子在内的句子集合，即 V = V -(入) Vt:终止符，不能再分割的最简基元的集合，用小写字母表示。VT=a,b,c Vn：非终止符，由基元组成的子模式和句子的集合。用大写字母表示。Vn=A,B,C Vt, Vn的关系：VtA Vn=(空集) Vt U Vn= V (全部字母表)卷S:起始符：届丁 Vn非终止符中的一个符号 P:产生式(再写规则)，存在丁终止符和非终止符问的关系式。例：a ? Vn
7、 , 0 ? Vn, Vt.例：Vt = 你，我，他，吃，饭，水果;Vn= 句子，主语，谓语，宾语;S=句子”；P: S t生语”十胃语”宾语”；主语” t弥”， 生语” t我”， 生语” t他”；谓语” T吃”；宾语” T饭”，宾语” T朱果”，2、4种类型的文法：(1) 无约束文法(0型文法)设文法 G = (Vn,Vt, P, S)Vn：非终止符，用大写字母表示Vt:终止符，用小写字符表示S:起始符*P: a t 6 ,其中 a ? V+, 6 ? V* a , 6无任何限制例：0型文法 G = (Vn,Vt, P, S), Vn = S,A , Vt = a,b,cP: StaSb S
8、bbA abAcSt aSA aaSbA anSbnT anbAbn-1 n-1n-1n-1 , n-1t a abAb t a cb此文法G可产生的语言为：L(G)=a ncbn|n=0,1,2.(2) 上下文有关文法(1型文法)设文法 G = (Vn,Vt, P, S)P： a iA a 2T a 10a 2其中 A ? Vn , 6 ? V+, a 1,a 2? V*|a iA a 2|V |a 邛 a 2|,或 |A|< |0 | a 1和a 2被视为A的上下文例：G = (Vn,Vt, P, S) Vn = S, B, CVt = a, b, cP:StaSBCStabCCBt
9、BCbBT bbbC t bccCt ccP可改写为： 入S入t入aSBC入入S入t入abC入入CB入t入BC入 bB入t bb入bC入Tbc入cC入tcc入都符合1型文法规则所以G届丁上下文有关文法St abCT abcSt aSBb aabCBA aabBCC aabbCA aabbcA aabbccStaSBb aaSBCBC aaabCBCBC aaabBCCBC t aaabBCBCC t aaabBBCCC t aaabbBCCCt aaabbbCCC aaabbbcCC aaabbbccC aaabbbccc此文法G可产生的语言为:L(G)=a nbncn|n=1,2.结构相似的
10、样本(3) 上下文无关文法(2型文法)设文法 G = (Vn,Vt, P, S)产生式P: AT 6其中A? Vn (是单个的非终止符)6 ? v+ (可以是终止符，非终止符，不能是空句) 对产生式的限制更严格例：文法 G = (Vn,Vt, P, S), Vn = S, A, B , Vt = a, bP:StaBStbAAta AtaSAtbAABtbBtbSBt aBB 各生成式左侧均为Vn,右侧为Vn和Vt的混合，满足上下文无关文法的 生成规则，St aBT abST abaB ababSt aBT abST abbA abbaSt bA t baA baaJ baabSt bA t
11、baA babA babaSt aBT abSt bA t ba两种方法替换非终止符： 最左推导：每次替换都是先从最左边的非终止符开始。 最右推导：每次替换都是先从最右边的非终止符开始，(4) 正则文法(3型文法)设文法 G = (Vn,Vt, P, S)产生式P： ATaB或 ATa,其中A,B? Vn (且是单个字符)，a? Vt (且是单个字符)广生式右端必须含有终止符 正则文法可用状态图表示，非终止符代表状态，终止符代表状态转移的 类型例：文法 G = (S, A,0, 1, P, S)P: St0A At0A At 1上述生成式满足正则文法生成规则。St 0A t 00A t000A
12、 t 0001此文法G可产生的语言为：L(G)=0 n1|n=1,2.此文法对应的状态图为：(5)四种文法的关系限制不严格的文法必然包含限制严格的文法(6) 四种文法和自动机的关系0型无约束文法1型上下文有关文法2型上下文无关文法3型正则文法T 图灵机T线性界限自动机T 下推自动机T 有限状态自动机三、句法分析1、模式识别中的句法分析：设有m个模式类，分别为31, 3 2,3 m，乂有对应的m种文法Gl , G2, Gm,如对丁任意样本X,当有x ? L (Gi)时，可判定X? 3 i,则分类器可由句 法分析判别构成。122、句法分析的主要方法:(1)参考匹配法：xX? 3 i将待识别的样本x
13、 (句子)与代表各类的模板或参考链 Xi进行匹配，将x 分类到匹配得最好的参考链对应的类 特点：简单快速，但未充分利用句法信息，也无法得到X的句法结构。(2)状态图法(适用丁正则文法)：先画出正则文法对应的状态图： 方法一：从状态图的起始符开始，依次处理输入模式X的各个字符，如果可以找到一条通往终止状态 T的通路，则表示x可以由该状态图生成。 方法二：从状态图推导中出该文法可产生的所有句子的形式，再用待识别模式x去匹配；例：正则文法 G = (S, A,0, 1, P, S)P: St0A At0A At 1状态图中的每一个状态(节点)为1个非终止符，T为终止状态At aB代表两个节点间的状态
14、转移，Ata代表状态转移的结束。法一：X1=0100不届丁该类，X2= 0001届丁该类法二：可推导出该文法可产生的语言为：L(G)=0n1|n=1,2.例：G = (Vn,Vt, P, S) Vn = (S, A, B, C), Vt = (0,1)B T 0, Ct 0C, Ct 0, Ct 1Bxi=10010,存在通路，可以识别；x2=10110,不存在通路，不可识别 法二：此文法可生成的句子类型有：X1=10n+1 , X2=00 , X3=10n10, n=0,1,2,(3) 填充树法(适用丁上下文无关文法)：当给定某待识别句子X及某个模式类的文法G时，我们建立一个以X为底， S为
15、顶的三角形，按文法 G的产生式来填充此三角形。若填充成功表明， X可 分到该模式类。填充树法是一种穷举法S填充树图法在填充三角形时应遵守三条原则： 首位考察：首先考虑选用某个产生式后能导出x的第一个字符； 用某产生式后，不能出现x中不包含的终止符； 用某产生式后，不能导致最终符号申变长(变短)，即保证单向递增(递减) 填充树有二种方法：由顶向底和由底向顶由顶向底剖析 从起始符S开始，依次向下利用产生式来产生x中的某个终止符，- 直到产生完整的x为止。 如已不存在非终止符，但是仍旧没有得到 x;或还存在非终止符，但 已得到的句子长度超过了 x,则表小x不届丁该文法定义的类。例：G = (Vn,V
16、t, P, S) Vt = (0,1) Vn = (S, A, B)P： St 1 StB1 StB Bt 1A Bt B1A A t0A A t 0问：x=1000，用由顶向底剖析方法判断x是否届丁 L(G) ?x=1000? L(G)由底向顶剖析 从待识别的句子x开始，依次看x中的每个终止符可以由哪个非终 止符产生，一直推导到所有x中的终止符都可以由起始符 S逐步产 生为止。 先生成那些可直接生成的单个终止符，再推导那些无法单独生成的 终止符。例：G = (Vn,Vt, P, S) Vt = (a,b,c,d,e Vn = (S, T, I)P: SF It a SFdS It b T t
17、 IeT I t c I问：x=adbec,用由底向顶剖析方法判断x是否届丁 L(G)?T T TJJJIII&JJa d b e ca d b e cSa d b e c(TdS)a d b e cx=adbec? L(G)课后作业：已知一文法：G = (Vn,Vt, P, S)Vn = S, A, B Vt = a, b, cP: Stabc StaAbc AbtbA ActBbcc bBTBb aBaaA aBT aa问：(1) 该文法是哪种类型的文法？(2) 某样本的句法为aaabbbccd',请问能否将它划归到该类?(3)句子(链)的长度： 句子所包含的符号数目，例：|a3b3 4 5c3|=9(4)语言':由字母表中的符号组成的句子集合，用L表示。例：字母表V=a,bL1=ab,aab,abab有限语言L2=anbm|n,m=0,1,2 顼限语言 在一种语言中，构成任何句子都必须遵循统一的规则，这些规则的集合 称为文法，用G表小。L(G)表小由文法G构成的语言"。(5)文法文法的数学定义：它是一个四元式，由四个参数构成：G=Vn, Vt, P, S