Fast Statistical Grammar Induction

Language, Information and Computation(PACLIC 11), 1996, 383-392 Fast Statistical Grammar Induction Wide R. Hogenhout� Yuji Matsumoto Nara Institute of Science and Technology { marc-h,matsu } ©is. aist-nara. ac. jp Abstract The statistical induction of context free grammars from bracketed cor- pora with the Inside Outside Algorithm has often inspired researchers, but the computational complexity has made it impossible to generate a large scale grammar. The method we suggest achieves the same re- sults as earlier research, but at a much smaller expense in computer time. We explain the modifications needed to the algorithm, give re- sults of experiments and compare these to results reported in other literature. 1 Introduction The availability of large treebanks creates the opportunity to model the struc- tures humans recognize in sentences that appear in everyday natural language. One well known method for modeling such structures is the Inside Outside Al- gorithm, which was first described by Baker (1979). The statistical induction of context free grammars has the attractiveness that it does not require any presumptions about the grammar that is being created, other than those that limit the size. However, the major problem with this kind of modeling has always been the computational complexity; the algorithm requires 0(n3 1w13) of training time per sentence w for a grammar with n nonterminals, per iteration. The algorithm has been used in two different ways, both of which reduce the computational complexity. First, there is a line of research (Black, Garside, and Leech, 1993; Hogenhout and Matsumoto, 1996) that concentrates on the reestimation of hand written grammars. This has none or much less problems with time complexity since the structure of the grammar is already decided and usually generates a limited number of parses for a given sentence. However, it completely loses the original attractiveness of modeling without presumptions. A second line of research, which concentrates on inducting a new grammar from scratch, is described in, amongst others, (Pereira and Schabes, 1992; Schabes, Roth, and Osborne, 1993). In these experiments the algorithm was applied to a treebank. The brackets of the treebank were used to reduce the number of possible structures by disallowing any structure that crosses some treebank bracket. This greatly 383 reduces training time, and they were able to parse short sentences of the Wall Street Journal corpus with 90.2% accuracy using a 15-nonterminal grammar. The extension to the algorithm and the experiments we present aims at improving the efficiency of induction of grammars from scratch. We have been able to strongly reduce the time complexity of the training, and at the same time achieved equivalent results when parsing short sentences of the Wall Street Journal Corpus. Instead of starting with a grammar consisting of all possible rules for a given number of nonterminals, we start with a small number of nonterminals and gradually increase this to the desired number. At the same time we remove rules that have become obsolete so we can work with a much smaller grammar. In this paper we describe the …

Content truncated to 500 words