Automatic Learning of Context-Free Grammar

Automatic Learning of Context-Free Grammar Tai-Hung Chen Chun-Han Tseng M9430400{71,41}@student.nsysu.edu.tw Chia-Ping Chen cpchen@cse.nsysu.edu.tw Department of Computer Science and Engineering National Sun Yat-Sen University Abstract 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. 1 Introduction and Overview In this paper we study the problem of learning context-free grammar (CFG) [1] from a corpus of part-of-speech tags. The framework of CFG, although not complex enough to enclose all human languages [2], is an approximation good enough for many purposes. For a natural language, a “decent” CFG can derive most sentences in the language. Put differently, with high probability, a sentence can be parsed by a parser based on the CFG. The main issue with CFG is how to get one. Generally speaking, learning context- free grammar from sample text is a difficult task. In [3], a context-free grammar which derives exactly one string is reduced to a simpler grammar generating the same string. This achieves a lossless data compression. In [4], an algorithm of time complexity O(N 2) for learning stochastic context-free grammar (SCFG) is proposed, where N is the number of non-terminal symbols. This is a great reduction from the inside-outside algorithm which requires O(N 3). Context-free grammars can be used in many applications. In [5], an automatic speech recognition system uses a dynamic programming algorithm for recognizing and parsing spoken word strings of a context-free grammar in the Chomsky normal form. CFG can 1 also be used in software engineering. In [6], the components in a source code that need to be renovated are recognized and new code segments are generated from context-free grammars. In addition, since parsing outputs larger and less-ambiguous meaning-bearing structures in the sentence, for high-level natural language processing tasks such as question answering [7] and interactive voice response [8] systems, the design and implementation of CFG can be crucial to their success. If the goal of learning is to acquire a grammar that derives most sentences in the domain of interest, then a good one is apparently domain-specific. An all-purpose CFG is not likely to be the best since it tends to derive a much larger set …

Content truncated to 500 words