Automatic Learning of Context-Free Grammar.
Tai‐Hung Chen, Chun-Han Tseng, Chia-Ping Chen · 2006
In this paper we study the problem of learning context-free grammar from a cor-pus. We investigate a technique that is based on the notion of minimum description length of the corpus. A cost as a function of grammar is defined as the sum of the number of bits required for the representation of a grammar and the number of bits required for the derivation of the corpus using that grammar. On the Academia Sinica Balanced Corpus with part-of-speech tags, the overall cost, or description length, re-duces by as much as 14 % compared to the initial cost. In addition to the presentation of the experimental results, we also include a novel analysis on the costs of two special context-free grammars, where one derives only the set of strings in the corpus and the other derives the set of arbitrary strings from the alphabet. Index Terms: context-free grammar, Chinese language processing, description length, Academia Sinica Balanced Corpus.