Incremental learning of context free grammars based on bottom-up parsing and search
Incremental learning of context free grammars based on bottom-up parsing and search
复制标题
DOI：
10.1016/j.patcog.2005.01.004
复制
发表时间：
2005-09-01
影响因子：
8
通讯作者：
Matsumoto, M
中科院分区：
文献类型：
--
作者：
Nakamura, K;Matsumoto, M
本文描述了上下文无关文法（CFG）的机器学习方法，从积极和消极的样本串，这是在Synapse系统实现。语法推理包括一个规则生成的“归纳CYK算法”，增量学习和搜索机制。当CYK算法自底向上解析不成功时，归纳CYK算法生成解析正样本所需的最小产生式规则。增量学习不仅用于通过按照长度顺序给予系统正串来合成语法，而且还用于从其他类似语法中学习语法。Synapse可以合成基本的模糊和明确的CFG，包括非平凡的语法，例如不具有omega omega形式的字符串集合，其中omega是{a，B}（+）的元素。(c)2005模式识别学会。由爱思唯尔有限公司出版。保留所有权利。
This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by "inductive CYK algorithm," mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form omega omega with omega is an element of {a, b}(+). (c) 2005 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.