语法归纳是从一组观察到的字符串或句子中自动推断形式语法（如上下文无关语法或概率上下文无关语法）的任务。其目标是捕捉语言中潜在的句法规律，使系统能够生成新的有效句子或解析未见过的句子。这一问题处于机器学习、人工智能和计算语言学的交叉领域，自计算机科学早期以来就受到研究。与带有显式标签的监督学习不同，语法归纳通常作用于未标注文本，因此是一种无监督或弱监督学习形式。
该领域在理论计算机科学和认知科学中都有深厚根基。经典的高尔德定理（1967年）表明，某些类别的语法无法仅从正例中在极限情况下学习，这促使研究者引入额外约束或概率框架。后来的工作，如内外算法（前向-后向算法对概率上下文无关语法的推广）的发展，为参数估计提供了实用方法。现代方法通常利用神经网络架构，特别是基于变换器的模型，从大规模语料库中归纳类似语法的结构。
历史基础
语法归纳的形式化研究始于20世纪50年代和60年代，以诺姆·乔姆斯基等人对形式语言理论的工作为开端。乔姆斯基层级根据生成能力对语法进行分类，从正则语法到递归可枚举语法。1967年，E. 马克·高尔德证明上下文无关语法无法仅从正例中学习，这一结果塑造了后续研究。这导致了对从正例和反例中学习的探索，以及概率语法的使用，其目标是在给定数据下找到最可能的语法。
在20世纪80年代和90年代，计算方法随着CYK解析器和内外算法等算法的引入而取得进展。这些算法使得概率上下文无关语法中的高效解析和参数估计成为可能。达纳·安格鲁因等研究者开发了主动学习框架，其中学习者可以查询关于字符串成员资格的预言机，这绕过了高尔德定理的一些限制。该领域还从认知科学中汲取灵感，特别是人类婴儿如何从有限输入中习得语言的问题，这一主题由布伦丹·莱克和约书亚·特南鲍姆等研究者在类人学习的背景下进行了探索。
概率与贝叶斯方法
语法归纳的一个重大转变是采用概率和贝叶斯方法。这些方法不是搜索单一语法，而是维护可能语法的分布，并在观察到更多数据时更新该分布。詹姆斯·贝克于1979年引入的内外算法是一个关键例子，它提供了估计概率上下文无关语法参数的期望最大化（EM）过程。该算法类似于隐马尔可夫模型中使用的前向-后向算法。
贝叶斯方法，如马克·约翰逊等人开发的方法，将语法结构的先验分布纳入考虑，从而能够归纳出更紧凑且更具泛化能力的语法。这些方法通常使用马尔可夫链蒙特卡洛（MCMC）采样来探索语法空间。一个显著例子是自然语言的贝叶斯语法归纳工作，该工作已应用于小规模语料库，并显示出能够恢复与人类语法相似的句法类别。这些技术也被用于认知建模，以检验关于语言习得的假设。
神经与深度学习方法
随着深度学习的兴起，语法归纳被重新审视，使用神经网络架构。早期的神经方法使用循环神经网络（RNN）和长短期记忆（LSTM）网络来建模序列数据，但这些方法并未显式归纳语法。最近，基于变换器的模型，如大型语言模型中使用的模型，已被证明能隐式捕捉句法结构。例如，探测研究表明，这些模型在其内部表示中编码了层级和语法信息，尽管它们并未接受显式语法监督的训练。
显式神经语法归纳模型也被开发出来。沈一康等人于2019年提出的ON-LSTM（有序神经元LSTM）使用一种特殊的门控机制来归纳潜在树结构。安德鲁·德罗兹多夫等人提出的DIORA（动态推断递归标注本体）模型使用内外算法的可微版本归纳成分树。这些模型在原始文本上训练，并能生成与人工标注树库相当吻合的解析树，在无监督解析基准上取得了最先进的结果。
应用与挑战
语法归纳在多个领域具有实际应用。在自然语言处理中，归纳出的语法可用于无监督解析，这对缺乏标注树库的低资源语言尤为有价值。在机器学习中，语法归纳可以通过提供结构性归纳偏置来提高模型的样本效率。在认知科学中，它为理解语言习得提供了计算框架。此外，语法归纳还被应用于其他领域，如生物信息学（例如RNA二级结构预测）和程序合成，其中底层结构是语法性的。
尽管取得了进展，语法归纳仍然是一个具有挑战性的问题。可能语法的搜索空间巨大，且目标函数通常是非凸的，导致局部最优。评估也很困难，因为对于给定语言没有唯一正确的语法；不同的语法可能同样有效。该领域持续发展，最近的工作探索将语法归纳与大型语言模型相结合，以提高其可解释性和组合泛化能力。麻省理工学院计算机科学与人工智能实验室和斯坦福人工智能实验室等机构的研究者正在积极研究这些方向，旨在弥合语言符号主义与联结主义方法之间的鸿沟。