资源描述：
《第十讲 句法模式识别》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第十讲句法模式识别一、基本概念1、结构模式识别：有一些模式识别任务，不能在特征空间中用统计模式识别的方法得到解决。l汉字的识别：汉字有偏旁部首、笔划构成l字符的识别：字符的字体不影响识别l语言的识别：语言由音节、字、词构成l图像识别：画面分割，目标识别l生物识别：基因序列，染色体结构，心电图分类定义：以结构基元为基础，利用模式的结构信息完成分类的过程，称为“结构模式识别”。其中“基元”指构成模式结构信息的基本单元，本身不包含有意义的结构信息。基元的选取与应用有关：·文字：笔划或偏旁部首作为基元·语音
2、：音素作为基元·心电图：收缩波和扩张波作为基元·图形：边缘线段、角点都可作为基元accbbbdddcccbbbddabcd轮廓基元讨论：·结构模式识别是与统计模式识别完全不同的一大类模式识别问题，一个基于结构信息，一个基于特征值·结构模式识别不仅能完成分类，还可以得到每个模式的结构性质·结构模式识别的依据是模式间结构上的“相似性”，这种相似度的度量不能用一般特征空间中的距离来表示·结构模式识别可以采用句法方法、拓扑分析方法、图论方法等多种方法·基元提取和分类器训练上的困难使得结构模式识别方法仍未成熟
3、·结构模式识别系统的模式信息通常来源于图像、音频等多媒体信息源2、句法模式识别（1）句法模式识别的定义：句法模式识别是利用模式的结构信息，以形式语言理论为基础来进行结构模式识别的方法。10傅京荪（1930-1985）美国工程院院士、Purdue大学讲座教授、台湾中央研究院院士，国际模式识别协会(InternationalAssociationforPatternRecognition:IAPR)创始人和首任主席，上世纪60年代提出句法模式识别。（2）句法和文法：·句法·句法来源于语言学，是指由字（词
4、）构成句子的方式，也就是一个句子组成的规则。·句法具有递归性，可以重复组合使用，用简单的规则可以表达复杂的结构。·可以用句法来表达结构模式识别中基元间的结构关系。·文法·文法是指一类相似的句子的共同句法规则。·可以用文法来表示一类样本的共同特点。·对某个具体的句子进行句法分析，判别与某类的文法是否相似，可以实现模式识别。（3）形式语言：形式语言是自然语言的抽象，是用一组明确的数学规则描述的语言，是语言的“数学化”，它由按一定规律构成的句子或符号串的有限或无限的集合组成。乔姆斯基（NoamChomsk
5、y,1928--）美国语言学家，麻省理工学院語言学与哲学系荣誉退休教授，曾任该系主任，并任该校认知科学研究中心主任。1957年出版了《句法结构》一书，提出了形式语言理论，其最初目的是为了研究人类语言抽象和通用的结构规则，后来在计算机编程语言、自动机理论、模式识别等方面都得到了广泛的验证和应用。在1980年到1992年，乔姆斯基是被文献引用数最多的健在学者，并是有史以来被引用数第八多的学者。3、句法模式识别系统的组成10预处理特征提取（基元提取）句法分析文法推断模式信息分类结果类别文法训练过程分类过程
6、（1）句法分析：判断一个样本是否符合一定的文法，从而得到该样本与已知类别的相似性。（2）文法推断：从分好类的训练集中获得该类所有样本的共同特征，形成代表每个类别的文法规则。l利用形式语言理论完善和坚实的数学基础，可用句法分析的方法来实现结构模式识别问题的求解一、形式语言理论1、基本概念：（1）字母表：与所研究的问题有关的符号集合。例：V1={A,B,C,D},V2={a,b,c,d},V3={0,2,6,8}（2）句子(链)：由字母表中的符号所组成的有限长度的符号串。例如有字母表{0,1}，则{0,
7、1,00,01,0110}就是有效句子的集合。不包括任何符号的句子称为空句，记为λ。V*：由字母表V中的符号组成的所有句子的集合，包括空句子λ在内。例：V*＝{λ,01,001}V＋：不包括空句子在内的句子集合，即V＋＝V*－(λ)（3）句子(链)的长度：句子所包含的符号数目，例:
8、a3b3c3
9、=9（4）语言：由字母表中的符号组成的句子集合，用L表示。例：字母表V={a,b}L1={ab,aab,abab}有限语言L2={anbm
10、n,m=0,1,2….}无限语言l在一种语言中，构成任何句子都必须
11、遵循统一的规则，这些规则的集合称为文法，用G表示。L(G)表示由文法G构成的语言。（5）文法文法的数学定义：它是一个四元式，由四个参数构成：G={VN,VT,P,S}10lVT：终止符，不能再分割的最简基元的集合，用小写字母表示。VT={a,b,c}lVN：非终止符，由基元组成的子模式和句子的集合。用大写字母表示。VN={A,B,C}lVT，VN的关系：VT∩VN=Φ(空集)lVT∪VN=V（全部字母表）lS：起始符：属于VN非终止符中的一个符号lP：产生式(再写规则
