Efficient Incremental Model for Learning Context-Free Grammars from Positive Structural Examples
Efficient Incremental Model for Learning Context-Free Grammars from Positive Structural Examples
复制标题
从正面结构示例中学习上下文无关语法的高效增量模型
DOI：
10.1007/978-3-540-87881-0_23
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Chandwani
中科院分区：
文献类型：
--
作者：
G. L. Prajapati;N. Chaudhari;M. Chandwani
本文描述了一种基于树自动机的上下文无关文法的形式化方法，用于从其结构描述的正样本中增量学习上下文无关文法。上下文无关文法的结构化描述是文法的派生树，其中去除了标签。这种范式中基于树自动机的学习最早由Sakakibara在1992年引入，然而他的方案假设所有训练示例在开始时都可用于学习算法（即，它不能用作在线学习），并且它也没有优化存储要求。我们的模型有几个理想的功能，运行在O（n3）的时间在输入示例的大小的总和，获得O（n）的存储空间节省，实现良好的增量行为，通过增量更新猜测和推断语法从积极的只有例子有效。给出了几个例子和实验结果来说明该方案及其有效的执行。
This paper describes a formalization based on tree automata for incremental learning of context-free grammars from positive samples of their structural descriptions. A structural description of a context-free grammar is a derivation tree of the grammar in which labels are removed. The tree automata based learning in this paradigm is early introduced by Sakakibara in 1992, however his scheme assumes that all training examples are available to the learning algorithm at the beginning (i.e., it cannot be employed as an online learning) and also it doesn’t optimize the storage requirements as well. Our model has several desirable features that runs inO(n3) time in the sum of the sizes of the input examples, obtainsO(n) storage space saving, achieves good incremental behavior by updating a guess incrementally and infers a grammar from positive-only examples efficiently. Several examples and experimental results are given to illustrate the scheme and its efficient execution.