「句法模式识别」

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

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

3、ue大学讲座教授、台湾 中央研究院院士，国际模式识别协会(Intern a tional Ass o ci a t i on f or Pa t tern Recognit i on: I AP R)创始人和首任主席，上世纪60年代提出句法模式 识别。(2)句法和文法：句法 句法来源于语言学，是指由字(词)构成句子的方式，也就是一个句 子组成的规则。 句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂 的结构。 可以用句法来表达结构模式识别中基元间的结构关系。文法 文法是指一类相似的句子的共同句法规则。 可以用文法来表示一类样本的共同特点。 对某个具体的句子进行句法分析，判别与某类的文

4、法是否相似，可以实现模式识别。(3)形式语言：形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言， 是语言 的数学化”，它由按一定规律构成的句子或符号用的有限或无限的集合组成。乔姆斯基(No a m Chom s ky, 1928-)美国语言学家，麻省理工学院言吾言学与哲学 系荣誉退休教授，曾任该系主任，并任该校认知 科学研究中心主任。19 5 7年出版了句法结 构一书，提出了形式语言理论，其最初目的是 为了研究人类语言抽象和通用的结构规则，后来 在计算机编程语言、自动机理论、模式识别等方 面都得到了广泛的验证和应用。在1 9 80年到19 92年,乔姆斯基是被文献引用数最多的健在学者

5、， 并是有史以来被引用数第八多的学者。3、句法模式识别系统的组成分类过程训练过程(1) 句法分析：判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。(2) 文法推断：从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文 法规则。利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结 构模式识别问题的求解形式语言理论1、基本概念：(1)字母表：与所研究的问题有关的符号集合。例:Vi= 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%3|二9语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V= a ,b ? Li= ab,aab , a bab 有限语言L2 = a nbm|n,m =0,1, 2无限语言 在一种语言中，构成任何