第七讲-句法模式识别

《模式识别》讲义2011版：第七讲句法模式识别第1页自动化学院模式识别与智能系统研究所高琪[e-mail]第七讲句法模式识别一、基本概念1、结构模式识别统计模式识别中，样本用特征空间中的向量来表达。每个样本在每个特征维度上都有各自的特征值，统计模式识别是依据样本集在特征空间中的统计分布来实现类别划分的。但是在模式识别任务中，有一些无法用统计模式识别来解决，例如：汉字识别：汉字由偏旁部首和笔划构成，偏旁部首的大小，笔划的长短粗细，都不影响所表达的汉字，而偏旁部首和笔划的类型及其相互结构关系确定了所表达的汉字是什么。字符识别：对于一般的字符识别，不仅字符的大小、字体不影响其意义，而且变形的字符，只要其结构特征没有被根本地改变，也不影响识别。语音识别：语音信息由连续的音素构成，包括音节、字或词。音素的种类并不多，但是其排列顺序却构成了非常多的组合形式，也代表了非常丰富的意义。因此，语音识别不仅要识别出音素，更重要的是要识别出音素之间的顺序关系，也就是结构关系。图像识别：对于图像识别问题，首先要将待识别的目标从背景中分割出来，然后识别出目标的类型。在图像中，目标的大小是不确定的，也存在形变、旋转和遮挡，只要其结构要素能被检测出来，并且结构关系与已知目标之间存在相似性，就能被识别。生物识别：在生物识别领域，例如基因序列的识别、染色体识别、心电图识别中，结构要素及其之间的结构关系，都是识别的依据，而不是某些特征值。结构模式识别就是专门用以解决这类问题的一大类模式识别方法，其定义为：以结构基元为基础，利用模式的结构信息完成分类的过程，称为“结构模式识别”。其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的结构信息。基元的选取与应用有关，例如：文字识别：可选取笔划或偏旁部首作为基元语音识别：可选取音素作为基元心电图识别：可选取收缩波和扩张波作为基元图形识别：可选取边缘线段、角点作为基元下例中，如选取四种线段作为基元，则图像中一个目标的轮廓，可以用基元《模式识别》讲义2011版：第七讲句法模式识别第2页自动化学院模式识别与智能系统研究所高琪[e-mail]之间的结构关系来表达，也就是用基元的连接顺序来表达。图1用基元表达轮廓结构结构模式识别是与统计模式识别完全不同的模式识别方法，虽然识别的依据都是样本间的“相似性”，但在统计模式识别中，相似性可以用特征向量之间的“距离”来计算，而结构模式识别中，相似性是结构关系上的相似性，不能用特征值及特征向量之间的“距离“来表达。在实现结构模式识别的过程中，不仅能得到分类结果，而且同时可以得到样本的结构性质。因此，如何表达样本的结构特征，是结构模式识别的关键问题。依据不同的结构特征描述，结构模式识别有句法方法、拓扑分析方法、图论方法等多种方法。但是由于基元提取和分类器训练上的困难未得到根本解决，结构模式识别未能像统计模式识别一样得到深入的发展和广泛的应用，其理论基础也远未成熟。目前对于结构模式识别问题，还是常常通过对结构信息描述的特殊处理，将其转换成统计模式识别问题来解决，或者是混合使用结构模式识别算法和统计模式识别算法，这在字符识别等领域有非常典型的实例。但是，由于多媒体信息（包括视频、音频等）在现代模式识别系统中越来越成为重要的模式信息来源，而多媒体信息中的结构性质比特征值统计性质更能表达其本质的含义，对结构模式识别算法的研究仍旧具有重大的理论和实践意义，值得去认真研究和探讨。2、句法模式识别结构模式识别算法中，最早提出的系统性方法是句法模式识别，它是由美籍华裔科学家傅京孙首先提出的。（1）句法模式识别的定义句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构模式识别的方法。傅京孙（1930-1985）浙江丽水人，1930年生于南京。1953年毕业于台湾大学电机系，1955年在加拿大多伦多大学获理学硕士学位，1959年在美国伊利诺伊大学获哲学博士学位。1960年起在美国普度大学任教，普度大学授予他工程学特级教授称号。1976年当选为美国国家工程院院士，1978年当选为台湾中央研究院院士。傅京孙教授是国际人工智能和模式识别领域的著名学者，1965年首先accbbbdddcccbbbddabcd轮廓基元《模式识别》讲义2011版：第七讲句法模式识别第3页自动化学院模式识别与智能系统研究所高琪[e-mail]提出把人工智能的启发式推理规则用于学习控制系统，1971年提出由人工智能和自动控制两个学科交叉形成的智能控制学科，70年代中期在形式语言理论的基础上建立了句法模式识别理论。傅京孙是美国IEEE计算机学会机器智能与模式识别委员会的第一任主席，模式分析与机器智能学报主编，国际模式识别协会(InternationalAssociationforPatternRecognition:IAPR)创始人和首任主席。1980年～1982年，作为我国派出的首批赴美访问学者，戴汝为院士曾到普度大学进修，师从傅京孙教授。（2）句法和文法句法模式识别中两个重要概念是句法和文法。句法来源于语言学，是指由字（词）构成句子的方式，也就是一个句子组成的规则。句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂的结构。因此，可以用句法来表达结构模式识别中一个样本的各个基元之间的结构关系。文法是指一类相似的句子的共同语法规则，它不一定直接描述句法，而可以是一些可以产生具有某类句法的句子的推导规则。因此，可以用文法来表示一类样本的共同特征，对某个具体的句子进行句法分析，判别其与某类的文法是否相似，就可以实现结构模式识别。（3）形式语言理论形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语言的“数学化”，它由按一定规律构成的句子或符号串的有限或无限的集合组成。形式语言理论是由美国语言学家乔姆斯基在1956年首先提出的，最初目的是为了研究自然语言的构成规则，以实现机器自动翻译。乔姆斯基的形式语言理论称为“转换－生成语法”，即有限的文法规则是语言的基础，它可以生成无限的句子和意义，但其深层结构都是相同的。形式语言理论在自然语言研究上仍旧存在巨大的争议，也未能彻底解决自然语言翻译的问题，但随着计算机技术的发展，形式语言理论为人－机之间的交流建立了桥梁，在计算机编程语言、自动机理论、模式识别等方面都得到了广泛的验证和应用。乔姆斯基（NoamChomsky,1928--）美国语言学家，1928年出生于费城。1955年在宾夕法尼亚大学完成博士论文《转换分析》，获得博士学位，后一直在麻省理工学院工作，曾任该校语言学与哲学系主任，并任该校认知科学研究中心主任，1957年出版了重要著作《句法结构》。乔姆斯基是美国科学促进会委员、美国科学院院士和美国文理科学院院士，是美国《科学》杂志评选出的包括爱因斯坦在内的20《模式识别》讲义2011版：第七讲句法模式识别第4页自动化学院模式识别与智能系统研究所高琪[e-mail]世纪全世界前10位最伟大科学家中目前唯一在世者。（4）句法模式识别系统图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*包括空句λ；而V*去除掉空句λ后称为V＋，即V＋＝V*－(λ)。（3）句子(链)的长度句子所包含的符号数目称为句子的长度，例如：|a3b3c3|=9（4）语言由字母表中的符号组成的一个句子集合称为一种语言，用L表示，它是V*的一个子集。例：有字母表V={a,b}，则L1={ab,aab,abab}和L2={anbm|n,m=0,1,2….}都是定义在V上的语言，其中L1被称为有限语言，L2被称为无限语言。在一种语言中，构成任何句子都必须遵循统一的规则，正是这些规则的限制从V*中选择了一些句子构成V*的一个子集，这些规则的集合称为文法，用G表示，因此用L(G)表示由文法G生成的语言。（5）文法《模式识别》讲义2011版：第七讲句法模式识别第5页自动化学院模式识别与智能系统研究所高琪[e-mail]在形式语言理论中，文法是一个四元式，由四个参数构成：G={VN,VT,P,S}VT：终止符，是不能再分割的最简基元的集合，用小写字母表示，即VT={a,b,c}VN：非终止符，由基元组成的子模式和句子的集合，用大写字母表示，VN={A,B,C}。非终止符不是最终句子的组成单元，而是推导句子的中间符号。VT∩VN=Φ(空集)，VT∪VN=V（全部字母表）S：起始符，属于VN非终止符中的一个符号，所有句子的生成都是由起始符开始的。P：产生式(再写规则)，存在于字母表符号或句子之间的关系式，表示左侧的符号或句子可以转换为右侧的符号或句子。例：α→β，α↔VN，β↔VN,VT例：VT＝{你，我，他，吃，饭，水果}；VN＝{句子，主语，谓语，宾语}；S＝“句子”；P：S→“主语”“谓语”“宾语”；“主语”→“你”，“主语”→“我”，“主语”→“他”；“谓语”→“吃”；“宾语”→“饭”，“宾语”→“水果”，则该文法可以生成的一个句子为：S→“主语”“谓语”“宾语”→“你”“吃”“水果”2、四种类型的文法在乔姆斯基的形式语言理论中，文法被划分为不同层次的四种类型。（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,c}P:①S→aSb②Sb→bA③abA→c该文法可产生的句子为：S→aSb→aaSbb→anSbn→anbAbn-1→an-1abAbn-1→an-1cbn-1因此，该文法G可产生的语言为：L(G)={ancbn|n=0,1,2...}.（2）上下文有关文法（1型文法）设文法G=(VN,VT,P,S)VN：非终止符，用大写字母表示VT：终止符，用小写字符表示S：起始符《模式识别》讲义2011版：第七讲句法模式识别第6页自动化学院模式识别与智能系统研究所高琪[e-mail]：α1Aα2→α1βα2其中A↔VN（不一定是单个非终止符），β↔V+,α1,α2↔V*|α1Aα2|≤|α1βα2|,或|A|≤|β|1型文法的特点是，产生式左右两端有相同的上下文（空句也可以作为上下文），但左端除上下文外，只能是非终止符，且进行转换后句子长度不能缩短。例：文法G=(VN,VT,P,S)，VN={S,B,C}，VT={a,b,c}P:①S→aSBC②S→abC③CB→BC④bB→bb⑤bC→bc⑥cC→ccP可改写为：①λSλ→λaSBCλ②λSλ→λabCλ③λCBλ→λBCλ④bBλ→bbλ⑤bCλ→bcλ⑥cCλ→ccλ都符合1型文法规则该文法可产生的句子为：S→abC→abcS→aSBC→aabCBC→aabBCC→aabbCC→aabbcC→aabbccS→aSBC→aaSBCBC→aaabCBCBC→aaabBCCBC→aaabBCBCC→aaabBBCCC→aaabbB