语法归纳

语法归纳（或语法推理）是机器学习中的一个过程，即从一组观察结果中学习一个正式的语法（通常作为重写规则或生成的集合，或者作为某种有限状态机或自动机），从而构建一个模型，说明观察对象的特征。更广泛地说，语法推理是机器学习的一个分支，其实例空间由离散的组合对象组成，如字符串、树和图。

语法推理通常非常注重学习各种类型的有限状态机的问题（关于这些方法的细节，请参见《正则语言的归纳》一文），因为自20世纪80年代以来，已经有针对这个问题的高效算法。自本世纪初以来，这些方法已被扩展到无语境语法和更丰富的形式主义的推理问题，如多语境无语境语法和平行多语境无语境语法。其他研究过语法推理的语法类别有组合分类语法、随机语境无语境语法、语境语法和模式语言。

最简单的学习形式是学习算法仅仅接收一组从有关语言中抽取的例子：目的是从它的例子中学习语言（很少从反例中学习，即不属于该语言的例子）。然而，其他学习模式也被研究。一个经常被研究的替代方案是，学习者可以像Angluin介绍的精确查询学习模型或最小充分的教师模型那样，提出会员查询的情况。

语法推理的方法有很多种。其中两个经典的来源是Fu（1977）和Fu（1982）。Duda,Hart&Stork(2001)也用了一个简短的章节来讨论这个问题，并引用了一些参考资料。下面将讨论他们提出的基本试错方法。关于特别是推断正则语言的子类的方法，见正则语言的推导。最近的一本教科书是delaHiguera(2010)，其中包括正则语言和有限状态自动机的语法推理理论。D'Ulizia,Ferri和Grifoni提供了一份调查，探讨了自然语言的语法推理方法。

Duda,Hart&Stork(2001)的第8.7节中提出的方法建议连续猜测语法规则（制作），并根据正面和负面的观察结果对它们进行测试。规则集的扩展是为了能够产生每个正面的例子，但是如果一个给定的规则集也产生了一个负面的例子，它就必须被丢弃。这种特殊的方法可以被描述为假设检验，并与Mitchel的版本空间算法有一些相似之处。Duda,Hart&Stork(2001)的文章提供了一个简单的例子，很好地说明了这个过程，但是对于更多的实质性问题，这种无指导的试错方法的可行性是值得怀疑的。

使用进化算法的语法归纳是通过某种进化过程来演化目标语言的语法表征的过程。形式化的语法可以很容易地被表示为生产规则的树状结构，可以受制于进化运算符。这类算法源于JohnKoza开创的遗传编程范式。其他关于简单形式语言的早期工作使用了遗传算法的二进制字符串表示，但是用EBNF语言表述的语法的固有层次结构使树成为一种更灵活的方法。Koza将Lisp程序表示为树。他能够在标准的树形运算符中找到与遗传运算符类似的东西。例如，交换子树等同于遗传交叉的相应过程，即把遗传密码的子串移植到下一代的个体中。

健身是通过对Lisp代码的函数输出进行评分来衡量的。树状结构的Lisp表示法与语法的树状表示法之间的类似，使遗传编程技术在语法归纳中的应用成为可能。在语法归纳的情况下，子树的移植对应于生产规则的交换，使一些语言的短语得到解析。语法的适配性运算符是基于对它在解析目标语言的某些句子组时的表现的某种衡量。在语法的树状表示法中，生产规则的终端符号对应于树的叶子节点。其父节点对应于规则集中的非终端符号（如名词短语或动词短语）。U