模式识别课件--句法模式识别

第10章句法模式识别，10.1句法模式识别概要10.2形式语言的基本概念10.3模式的记述方法10.4句法推断10.5句法解析10.6句法结构的自动机识别，第10章句法模式识别，10.1句法模式识别概要，模式用句法记述，结构信息很重要。模式、子模式、基元、句子、短语、单词、组合关系、自然语言的语法、句法模式识别用小的简单基元和语法规则记述识别，通过识别基元，识别子模式，最终识别复杂的模式。符合某一语法的所有句子集合，一个模式类，图10.1场景结构描述与英语句法描述的对比，句法模式识别系统的构成：句法模式识别的理论基础：形式语言，20世纪50年代中期乔姆斯基(Chomsky )。*基元的选择还没有共同的方法*语法推断理论远不如统计学习成熟。 语法模式识别中存在的主要问题：以10.2格式语言的基本概念、10.2.1基本定义、1 .字母、问题符号的有限集合、v或表示。 2 .由句子、字母符号构成的有限长度的符号串，也称为链条。 空文用表示。 构成：英文小写，数字。 例如：可以由中央要素构成的句子：例如，abc、aacc、改写次数、句子长度：句子包含符号数，用|表示。 有语言、字母符号的句子集合。 v * :由v中的符号构成的所有句子的集合。 包含空语句的v :不包含空语句的语句集合。 例：4 .构成语法、语言的句子必须遵守的规则。 VN :非终结符的有限集合、子图形的集合、大写表示。VT :结束符限制集、图元集合、字母开头部分的小写字母表示。 由终止符号和非终止符号构成的混合字符串：用英文字母末尾的小写字母x、y、v、w等表示。 由结尾符号构成的字符串：由希腊字母、等表示。 p :生成式的有限集合。 用语法造句时的改写规则。 字符串、字符串、置换、s :表示起始符、模式本身，特殊的非终止符。 以生成式构成句子时，必须从左边为s的生成式开始。 另外，用L(G )表示一种语言中由语法g构成的语言，由语法g构成的句子由终止符构成，在利用VT中的由字符构成的所有句子的集合、语法g的导出关系、语法构成句子的情况下，除了最初的生成式必须利用以左边为起点的s的生成式以外是的，说明：解：10.2.2语法分类，4种： 0型语法，1型语法，2型语法，3型语法。 1.0型语法：不受约束的语法。 p :其中，2.1型语法：上下文相关语法。 含义：3.2型语法：上下文相关语法。 解：各生成式的左侧是单一变量，右侧不是空白字符串，所以g是与上下文无关的语法。 属于L(G )的句子：结果不唯一。 4.3型语法：正则语法，有限状态语法。 后者的语法限制比前者的语法限制更严格的限制越多，语法越容易推断，句法模式识别多采用不依赖于语境的语法和正则语法。 10.3根据图案描述方法，10.3.1要素的确定，结构特征描述图案。 结构描述法也称为句法表现法。 图案的显示：链表示、树表示、图表表示。 对应的语法：连锁语法(串语法)、树语法、文字法。 还有网络语法和数组语法等。 目前对基本要素的确定没有共同的解决办法。 基本要素的选择遵循两个基本原则：1.基本要素应该是模式的基本要素，能够以一定的结构关系紧凑且简单地描述数据。 2 .可以以现有的非语法方式容易地提取或识别基元。 例如，语音识别中音素； 识别手写字符的笔划。以10.3.2模式的链表示、1 .链码法、链码：不同斜率的直线段或曲线段为图元表示图形模式。 自由人链接代码：以8个基本方向的有向线为基础，用07的8个数字符号表示。 以字符表示基本体后，所描述的图形表示的字符串。 自由链路基元，数字“2”的折线化和量化结果，编码：矩形网格复盖； 形成折线化和量化链码(有序结构)。 例如，“2”链码表示为2 .图形描述语法，PDL(PictureDescriptionLanguage，PDL )。 基本图元：有向线段(直线段、圆弧段)。 由“头(箭头端)”和“尾”构成。 关系图元：表示图元之间的连接关系的操作员。 头和尾相接，头和尾相接，尾和尾相接，头和尾相接，头和尾相反，(，)，例：用PDL法表示大写字母a。 (a b )，(a b)*c )，(a b)*c) b )，(a (a b)*c) b ) )，链条表示：仅从左或右与其他符号连接，一维连接。 10.3.3模式的树表现，高维表现。 1 .树的定义，树t是一个或多个节点的有限集合，并且1 )存在唯一根指定的节点2 )其馀节点被划分成m个不相交集合T1、T2、Tm，其中各集合本身为称作t的树。 的双曲馀弦值。 树的规则性：一个节点有子树的数量，节点a的等级记为r(a )。 叶节点的等级为零。 秩：长方体、基元、树结构描述符、节点a的秩可以是2、l或0。 例如，节点a可以具有2、1或0个分支，其中，树语法是以四元表达式、2 .树语法、字母表达式、字母表达式作为根节点的树的秩、原始树的有限集合、生成表达式的有限集合、以树语法Gt的语言L(Gt )是某些树的集合，即模式所有的节点都是终止子树的集合，树t从s中的原始树Ti开始，用语法Gt的生成式导出，用图10.7模式的树表示，解：生成式中右边，尝试判断图10.7所示的树是否属于L(Gt )的句子。 3 .扩展木文法，其中，p有式，木文法有对应的扩展木文法。 例10.6构成例10.5中与树语法对应的扩展树语法。 10.4语法估计，10.4.1基本概念，语法估计：用已知类模式样本训练类语法的过程。 统计模式识别训练判别函数，句法模式识别训练类语法，目的：构建能正确描述某一模式的语法，其中主要求出生成式集合p。 选择* *语法格式(链接语法、树语法、文字法)。 根据* *样本推定语法。 基本步骤：1.语言L(G )的正取样集和负取样集，2 .语法估计的基本概念，从取样集RR，R-导出语法g，简化时仅为r。 给出*r型的训练样本集，合计n句接连发送给“语法推断机”。 *输入句子后，生成该句子的语法G1被初步推定。 *输入第二个句子，补充或修改G1，推断生成这两个句子的语法G2。 *估计语法Gn。 对*gn的各项条文进行合并处理。*先估计几种不同的语法，然后选择一个。简化语法的方法：10.4.2馀码语法的估计，1 .馀码的定义，2 .馀码语法的估计，馀码语法又称形式微商语法。 10.4.3扩展树文法的推定，第三步：合并等价非终端子，删除所有合并的非终端子的子孙生成式。 例10.8某种句法模式树记述的样本是树T1和T2:解：第一步：分别写出产生树T1和T2的产生式。 另外，生成树T1的生成式：追加一个，生成树T2的生成式：10.5句法分析，10.5.1参照链匹配法，利用语法识别或分类未知类的句法模式的过程。 解析：*为每个模式提供一个示例链(参考链)。 的双曲馀弦值。 *将输入链x与每类参照链进行比较，并指定比较公差。x被认为与其匹配的“最佳”参考链所属的模式类。 10.5.2填充树图法用于分析与上下文无关的语法。 当某种语言的语法Gi被已知时，给出某种被识别的连锁x，如图10.8所示，产生以x为底、以起始符s为顶点的三角形。 用语法Gi的生成式填充这个三角形，作为分析树。 如果填充成功，则表示x可以从语法Gi导出，图10.8应填充的三角形，填充三角形的方法：自上而下法的基础上法，解：填充三角形的成功，图10.9语法g的生成式填充的三角形，10.5.3CYK分析法，库克(Cocke)-杨格(Younger)-卡塞(Kasami ) 用于分析分析法、语境依赖语法的1 .乔姆斯基的正规形式，要求：生成式应表示为乔姆斯基的正规形式。 或者，a、b、c是非终止符号，a是终止符号。 例如，乔姆斯基范式是2.CYK分析法，输入：与乔姆斯基范式的语境无关的语法g，输入链x； 输出：关于链x的分析表。 重要信息：如何构建x分析表，步骤：步骤5 :停止，完成填写。 10.5.4查询分析法，有效上下文相关语法分析算法。 点：划分分析的部分和未考虑的部分。 重复思路：步骤：2和3，直到新项目不再加入I0。 重复执行5和6直到项目没有添加到Ij。 解：10.6句法结构的机器人识别，机器人：句法模式识别器。 并且识别输入链是否符合与该机器相对应的语法。 0型语法、图灵机器、1型语法、线性有界机器人、2型语法、下推机器人、3型语法、有限状态机器人、各类语法对应于一类机器人：链语法：树语法、树机器人。 另外：1 .有限状态机器人、10.6.1有限状态机器人和正则语法、字母输入、内部状态限制集、状态转移规则、初始状态、结束状态集、机器人一次只能从一个状态转移到另一个指定状态。 已确定的有限状态自动机：未确定的有限状态自动机：自动机一次可以从一个状态转变为指定状态集中的一个状态。 例如：2 .有限状态机器人接受语言的方式，有限状态机器人接受的语言：指有限状态机器人接受的链x的集合，记为L(A )。 结构：*x的字符从左到右依次记录在输入带中。 动作方式：*只读头从输入带的最左边的单元格开始依次读取输入字符。 每次读取* *字符时，状态控制器都会搜索原始状态转换规则，并接受/拒绝该字符。*机器人连续接受输入链的各字符，最后停止在一个结束状态时，输入链是该机器人接受的语言，解：将链x输入机器人a，进入状态转移图：状态、结束状态、箭头，状态变化、状态变化方向、3 .有限状态机器人与正则语法的对应状态、1 ) 应用：qi、qj :a分别接受链x的过程为：2 )有限状态机器人分别接受正则语法、对应关系：qi、qj分别接受Ai、Aj :10.6.2下推机器人和上下文相关语法、1 .下推机器人、有限状态机器人的限制： 下推自动机(PDA ) :有限状态自动机推送内存，只能接受正规语法的语言，不能接受上下文相关语法的语言。 的双曲馀弦值。 结构：*初始状态q0:堆栈顶部为最初的非结束符，*读取头读取输入字符：输入链的结束符和堆栈顶部的结束符决定机器人状态的迁移，*状态迁移的同时堆栈顶部的内容发生变化。*机器人内部状态为结束状态或堆栈为空时，输入链被机器人接受(识别)。 下推机器人定义：有限状态机器人加Z0和，下推符号有限集，最初在栈顶的非终止符号，内部状态转变和栈顶内容变化的规则，规则:讨论： *或单个非终止符号。*不是结束字符串。有按下按钮，最左边