Incremental Learning of Context Free Grammars by Parsing-Based Rule Generation and Rule Set Search

• Nakamura Katsuhiko

  Tokyo Denki University

• Hoshina Akemi

  Apex Corporation

Bibliographic Information

Other Title

• 構文解析にもとづく規則生成と規則集合探索による文脈自由文法の漸次学習
• コウブン カイセキ ニ モトヅク キソク セイセイ ト キソク シュウゴウ タンサク ニ ヨル ブンミャク ジユウ ブンポウ ノ ゼンジ ガクシュウ

Abstract

This paper discusses recent improvements and extensions in Synapse system for inductive inference of context free grammars (CFGs) from sample strings. Synapse uses incremental learning, rule generation based on bottom-up parsing, and the search for rule sets. The form of production rules in the previous system is extended from Revised Chomsky Normal Form A→βγ to Extended Chomsky Normal Form, which also includes A→B, where each of β and γ is either a terminal or nonterminal symbol. From the result of bottom-up parsing, a rule generation mechanism synthesizes minimum production rules required for parsing positive samples. Instead of inductive CYK algorithm in the previous version of Synapse, the improved version uses a novel rule generation method, called ``bridging,'' which bridges the lacked part of the derivation tree for the positive string. The improved version also employs a novel search strategy, called serial search in addition to minimum rule set search. The synthesis of grammars by the serial search is faster than the minimum set search in most cases. On the other hand, the size of the generated CFGs is generally larger than that by the minimum set search, and the system can find no appropriate grammar for some CFL by the serial search. The paper shows experimental results of incremental learning of several fundamental CFGs and compares the methods of rule generation and search strategies.

Journal

• Transactions of the Japanese Society for Artificial Intelligence

  Transactions of the Japanese Society for Artificial Intelligence 21 (4), 371-379, 2006

  The Japanese Society for Artificial Intelligence

Keywords

• grammatical inference
• CFL
• incremental learning
• bottom-up parsing
• iterative deepening
• CYK algorithm
• bridging rule generation

Details

• CRID: 1390001205107618048
• NII Article ID: 10022006566
• NII Book ID: AA11579226
• DOI: 10.1527/tjsai.21.371
• ISSN: 13468030
• ISSN: 13460714
• NDL BIB ID: 8686520
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I8686520
• Web Site: http://www.jstage.jst.go.jp/article/tjsai/21/4/21_4_371/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed