Incremental Learning of Context Free Grammars and Its Application

语法推理，即从正反样本中自动合成形式语法，是机器学习的一个重要研究课题。我们一直致力于从示例字符串中学习通用上下文无关文法，这是在“Synapse”系统中实现的。我们的方法的主要特点是增量学习，规则生成的基础上自下而上的解析积极的样本，并搜索规则集。在项目实施过程中，我们对系统进行了改进，实现了一些新的方法。最重要的一个是规则生成过程，称为“桥接”，从每个正字符串的解析结果，合成的产生式规则，弥补任何缺乏部分的不完整的派生tree.To解决的根本问题的复杂性学习CFG，我们采用的方法，搜索非最小，半最优的规则集，以及增量学习相关的语法。一种搜索策略，称为串行搜索，是一种方法，找到半最优集搜索任何额外的规则，为每个正样本，而不是找到最小的规则集，为所有的正samples在global search.We还研究了我们的方法的扩展和应用到一些更广泛的类的语法，包括确定性子句语法（DCG）和逻辑grammars.We。未来的问题包括进一步改进Synapse，使系统可以在更短的时间内合成更复杂的语法，并应用到其他领域的机器学习，包括句法模式识别。

Grammatical inference, i.e. automatic synthesis of formal grammars from positive and negative samples, is an important research subject in machine learning. We have been working on learning general context free grammars from sample strings, which is implemented in "Synapse" system. Main features of our approach are incremental learning, rule generation based on bottom-up parsing of positive samples, and search for rule sets. In the term of the project, we improved the system by implementing several novel methods. The most important one is the rule generation process, called "bridging," from the results of parsing for each positive string, which synthesizes production rules that make up any lacking parts of the incomplete derivation tree.To solve the fundamental problem of complexity for learning CFG, we employ methods of searching for non-minimum, semi-optimum sets of rules as well as incremental learning based on related grammars. A search strategy, called serial search, is a method of finding the semi-optimum sets by searching for any additional rules for each positive sample and not to find the minimum rule set for all positive samples as in global search.We also investigated extensions of and applications of our approach to some broader classes of grammars including definite clause grammars (DCG) and logic grammars. Future problems include further improvement of Synapse so that the system can synthesize more complex grammars in shorter time and applications to other area of machine learning including syntactic pattern recognition.