IEICE Trans - Search for Minimal and Semi-Minimal Rule Sets in Incremental Learning of Context-Free and Definite Clause Grammars

Search for Minimal and Semi-Minimal Rule Sets in Incremental Learning of Context-Free and Definite Clause Grammars

Keita IMADA
Katsuhiko NAKAMURA

Publication
IEICE TRANSACTIONS on Information and Systems Vol.E93-D No.5 pp.1197-1204
Publication Date: 2010/05/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1197
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Artificial Intelligence, Data Mining
Keyword:
grammatical inference, CFG, DCG, beam search, Synapse,

Full Text: PDF(854KB)>>

Summary:
This paper describes recent improvements to Synapse system for incremental learning of general context-free grammars (CFGs) and definite clause grammars (DCGs) from positive and negative sample strings. An important feature of our approach is incremental learning, which is realized by a rule generation mechanism called "bridging" based on bottom-up parsing for positive samples and the search for rule sets. The sizes of rule sets and the computation time depend on the search strategies. In addition to the global search for synthesizing minimal rule sets and serial search, another method for synthesizing semi-optimum rule sets, we incorporate beam search to the system for synthesizing semi-minimal rule sets. The paper shows several experimental results on learning CFGs and DCGs, and we analyze the sizes of rule sets and the computation time.

open access publishing via