文法推断

[拼音]：wenfa tuiduan

[外文]：grammaticalinference

根据给定的有限样本集推断产生该样本集所属语言类的文法规则的学习算法。它是句法模式识别（见结构模式识别）的重要组成部分。通过文法推断可以得到一组重写规则（见短语结构文法），它们除了能描述给定的有限样本集外，还能描述那些虽不在给定样本集内但却与给定样本集在某种意义上有同样性质(属于同一类)的模式，从而可以用这一组重写规则对输入模式进行句法分析以达到识别的目的。文法推断过程就是对模式类进行描述的过程，它的正确性在很大程度上决定于所给样本集的完备性和人们对模式性质了解的程度，文法推断算法至今仍然是句法模式识别中的一个重要研究课题。

文法推断课题的一般性质是：

（1）给定某个文法G所产生的语言L(G)的一个有限子集S⁺(叫正样本集)和不属于这个语言的集合的一个有限子集S ^-(叫负样本集)，须假定S⁺是结构完整的，即描述L(G)的每一条重写规则在描述S ⁺中的样本时至少使用一次。

（2）推断得到的文法G_a应满足S⁺吇L(G_a)和。在理想情况下,L(G_a)=L(G)。在实际问题中,由于所提供样本的局限性,S⁺往往不是结构完整的，推断得到的文法G_a只是G 的一种近似。对于同样的有限样本集，不同的推断算法可以得到不同的G_a，因此需要定义一个所推断出的文法对于给定样本集的优度度量，从而能在某种意义上得到一个满意的结果。

文法推断算法有穷举文法推断算法和归纳文法推断算法两种形式。

（1）穷举文法推断算法：在一个文法类中进行搜索，以求得与所给样本集和学习系统（教师）所提供的其他附加信息一致的文法。为了提高搜索的效率可以利用覆盖这个重要概念：如果某个文法G₁不产生S⁺中所有的语句，在穷举中可以删去被G₁所覆盖的所有文法；而如果文法G₁产生S^-中某些句子，则在穷举中可删去所有覆盖G₁的文法。

（2）归纳文法推断算法：从正样本S⁺中求得语言L的递归结构,从而使一个恰好产生给定正样本的非递归性文法成为一个能够产生任意多语句的递归性文法。以规范微商文法为基础的推断算法和基于k尾的文法是文法推断算法的两个例子。

以规范微商文法为基础的推断算法

首先用形式微商概念求出一个只产生学习样本集（语句集合）的规范文法。语句集合A对于终止符a∈Σ的形式微商是D_aA={x|ax∈A}。A对于空符号链λ（即符号数为0的链）的微商D_λA＝A。A对于某个子句a₁a₂的形式微商是 D_ɑ1ɑ2A＝D_ɑ2(D_ɑ1A)。类似地，D_ɑ1ɑ2…ɑnA＝D_ɑn(D_ɑn-1(…(D_ɑ1A…)))。对应正样本集S ⁺的规范微商有限状态文法G_CD＝(N，Σ，P，S)按下列方法求得：

（1）∑是S ⁺中所有语句中包含的所有互异的终止符集合。

（2）N是S ⁺对于∑的不为空的形式微商集合,N＝{u₁,…,u_r},其中u₁=D_λS ⁺。

（3）S＝u₁。

（4）按下列条件得到P中的重写规则:(i)u_i→au_j在P中的充分必要条件是D_ɑu_i=u_j;(ii)u_i→a在P中的充分必要条件是λ∈D_ɑu_i。例如S ⁺＝{01,1001}的规范微商文法G_CD＝(N，∑，P，s)，其中∑＝{0,1}；N＝{u₁,u₂,u₃,u₄}(u₁＝D_λS ⁺＝{01,1001}，u₂＝D₀u₁＝{1},u₃＝D₁u₁＝{001},u₄＝D₀u₃＝{01},此外D₀u₄＝{1}＝u₂);S＝u₁；P:u₁─→0u₂,u₂─→1，u₁─→1u₃，u₃─→0u₄，u₄─→0u₂。在求得G_CD的基础上可以得到相应的递归性文法G＝(N′，∑，P′，s′)。这时把G_CD的非终止符集划分为若干互不相交的子集，例如N₁={u₁,u₂},N₂＝{u₃,u₄},则N′＝{N₁,N₂}。为了求P′,只要把原来P 中的非终止符按它属于哪一个划分子集而改为N′中的相应符号,因此P′:N₁─→0N₁,N₁─→1,N₁─→1N₂，N₂─→0N₂，N₂─→0N₁,此外s′＝N₁，∑＝{0,1}。显然G产生的语言除了 S ⁺外还有无限多的语句。G_CD 中的非终止符集可以用有限的不同方法划分为互不相交的子集，因此相应地有有限个递归性文法，其中至少有一个文法是推断问题的解。

基于k尾的文法

语言集合s对于终止符构成的子句_z的k尾微商是

例如，对于语句集合S⁺＝{01,100,111,0010}而言，

设u_i和u_i是规范微商有限状态文法G_CD 中两个互异的非终止状态,u_i和u_j分别对应于微商D_xiS ⁺ 和D_xjS ⁺，其中x_i，x_j∈∑ ^*。则u_i和u_j为k尾等价状态的充分必要条件是

g(x_i，S⁺,k)＝g(x_j，S⁺,k)

把规范微商文法中等价的状态合并，可得到从G_CD导出的可数个递归性文法，其中包含至少一个文法可作为推断问题的解。

对于正则文法，已研究出以规范微商文法为基础的推断算法和基于 k尾的文法推断算法，但对于上下文无关文法的推断则尚无普遍适用的算法，只是对某些特殊限制的上下文无关文法有了一些启发式的算法。例如应用结构信息序列推断算子优先文法以及k齐次、k互异文法和枢轴文法推断，图形描述文法的启发式推断等。在随机文法的推断方面，曾经提出一种直接综合随机有限状态自动机算法。其中状态转移概率可以从随机语句集合中相应的概率信息中导出。

此外，在人机对话式的文法推断系统结构、正则树文法、网状文法等推断方法方面都已经取得了一定的成果。

参考书目

1. K.S.Fu and　P.H.Swain，On Synthatic Pattern Recognition，In Software　Engineering，Vol.2, Academic Press, New York,1971.