文法推断

文法推断属于形式语言的归纳学习问题，它研究如何从语言的有限信息出发，通过归纳推断得到语言的语法定义。文法推断根据给定的有限样本集推断产生该样本集所属语言类的文法规则的学习算法。它是句法模式识别（结构模式识别）的重要组成部分。

定义在统计模式识别方法中，经常用已知类别的模式样本集训练判别函数，同样在句法模式识别中，也可以用已知类别的模式样本集来训练类别文法，这种训练过程或者说学习过程称为文法推断。文法推断就是要构造出能正确描述某类模式的文法，其中主要是求生成式集合P。前面关于模式描述方法的讨论是在假定文法已知的前提下进行的。

每一类模式有一个文法，由于模式用句子表示，而句子可以由链、树、图表示，所以相应地就有链文法、树文法和图文法的推断问题。当选择了文法的形式之后，就可以根据一组数目足够且具有代表性的样本来推断文法。

研究意义通过文法推断可以得到一组重写规则，它们除了能描述给定的有限样本集外，还能描述那些虽不在给定样本集内但却与给定样本集在某种意义上有同样性质(属于同一类)的模式，从而可以用这一组重写规则对输入模式进行句法分析以达到识别的目的。

文法推断过程就是对模式类进行描述的过程，它的正确性在很大程度上决定于所给样本集的完备性和人们对模式性质了解的程度，文法推断算法至今仍然是句法模式识别中的一个重要研究课题。1

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

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

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

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

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

②归纳文法推断算法：从正样本S+中求得语言L的递归结构，从而使一个恰好产生给定正样本的非递归性文法成为一个能够产生任意多语句的递归性文法。

区别与联系文法推断（Grammatical Inference）与机器学习（Machine Learning）的区别，机器学习是狭义的（或标准的）机器学习。从广义上讲，文法推断也属于机器学习的范畴。

两者的共同之处都是从有限的经验数据自动学习知识，尝试找到一种隐藏在样本数据背后的模式。机器学习的处理对象是数值型数据，学习结果是对数据分类和回归分析；文法推断的处理对象是字符序列，学习结果是生成字符序列的形式文法。2

本词条内容贡献者为:

张静 - 副教授 - 西南大学