句法模式识别.doc

第十讲句法模式识别

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

讨论：
结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个基于结构信息，一个基于特征值
结构模式识别不仅能完成分类，还可以得到每个模式的结构性质
结构模式识别的依据是模式间结构上的“相似性”，这种相似度的度量不能用一般特征空间中的距离来表示
结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法
基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟
结构模式识别系统的模式信息通常来源于图像、音频等多媒体信息源
2、句法模式识别
（1）句法模式识别的定义：
句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构模式识别的方法。
傅京荪（1930-1985）
美国工程院院士、Purdue大学讲座教授、台湾中央研究院院士，国际模式识别协会(InternationalAssociationforPatternRecognition:IAPR)创始人和首任主席，上世纪60年代提出句法模式识别。

（2）句法和文法：
句法
句法来源于语言学，是指由字（词）构成句子的方式，也就是一个句子组成的规则。
句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂的结构。
可以用句法来表达结构模式识别中基元间的结构关系。
文法
文法是指一类相似的句子的共同句法规则。
可以用文法来表示一类样本的共同特点。
对某个具体的句子进行句法分析，判别与某类的文法是否相似，可以实现模式识别。
（3）形式语言：
形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语言的“数学化”，它由按一定规律构成的句子或符号串的有限或无限的集合组成。

乔姆斯基（NoamChomsky,1928--）
美国语言学家，HYPERLINK"http://zh.wikipedia.org/w/index.php?title=%E9%BA%BB%E7%9C%81%E7%90%86%E5%B7%A5%E5%AD%A6%E9%99%A2&variant=zh-tw"\o"麻省理工學院"麻省理工学院語言学与哲学系荣誉退休教授，曾任该系主任，并任该校认知科学研究中心主任。1957年出版了《句法结构》一书，提出了形式语言理论，其最初目的是为了研究人类语言抽象和通用的结构规则，后来在计算机编程语言、自动机理论、模式识别等方面都得到了广泛的验证和应用。在1980年到1992年，乔姆斯基是被文献引用数最多的健在HYPERLINK"http://zh.wikipedia.org/w/index.php?title=%E5%AD%A6%E8%80%85&variant=zh-tw"\o"學者"学者，并是有史以来被引用数第八多的学者。

3、句法模式识别系统的组成
预处理
特征提取
（基元提取）
句法分析
文法推断
模式信息
分类结果
类别文法
训练过程
分类过程

句法分析：
判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。
文法推断：
从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文法规则。
利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结构模式识别问题的求解

形式语言理论
基本概念：
（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＋：不包括空句子在内的句子集合，即V＋＝V*－(λ)
（3）句子(链)的长度：
句子所包含的符号数目，例:|a3b3c3|=9
（4）语言：
由字母表中的符号组成的句子集合，用L表示。
例：字母表V={