Implementing a lexicalised statistical parser

Implementing a lexicalised statistical parser Corrin Lakeland, Alistair Knott Department of Computer Science University of Otago New Zealand {lakeland,alik}@cs.otago.ac.nz Abstract Statistical parsers are extremely complex sys- tems, yet papers describing them almost always only discuss theoretical issues instead of imple- mentation issues. This paper attempts to ad- dress the imbalance by describing the imple- mentation issues faced in building a state-of- the-art statistical parser. In the process, we will describe our own implementation of a statistical parser. 1 Introduction Between 1996 and 1999, Michael Collins devel- oped a statistical parser (Collins, 1996; 1999) which has become tremendously influential in NLP. Collins’ thesis and published papers dis- cuss the theoretical underpinnings of his system in a great deal of detail; he devotes considerable space to describing and justifying the grammar formalism and the probability model which his parser uses. His description of his parsing algo- rithm is much less detailed; it is given as a set of pseudocode routines in an appendix. However, the scale and complexity of a lexicalised statis- tical parser is such that implementing this pseu- docode presents significant software engineering difficulties. The pseudocode actually disguises many of the interesting optimisations present in Collins’ system. As far as we can tell, no- body has published how to actually implement such a system. The aim of this paper is to de- scribe the important software engineering issues involved in implementing a lexicalised statisti- cal parser, using the parser we implemented as an example. What we found was that if you ever consider performance a secondary consid- eration then the parser will go so slow as to be impossible to debug. Because of this, we will concentrate on the efficiency of algorithms not so much to improve on Collins’, but just to get a working system. We will begin in Section 2 by describing Collins’ probability model. In Section 3 we de- scribe Collins’ parsing algorithm in high-level detail. The remainder of the paper describes our way of implementing the difficult parts of this algorithm. The chart data structure is de- scribed in Section 4; the generation of probabili- ties from the probability model in Section 5; the search strategy used by the parser is described in Section 6; Some general advice about soft- ware engineering in building a statistical parser is discussed in Section 7. And we conclude by noting that our parser performs almost the same as Collins’ in Section 8. 2 Collins’ probability model The key idea in any statistical parser is to asso- ciate probabilities with grammatical rules. The probability of any given parse tree is then sim- ply the product of the probabilities of all the rules applied in creating this tree. However, in practice, the probability of a parse tree being the correct parse of a sentence depends not just on the rules which are applied, but on the words which appear at the leaves of the tree. To illus- trate, consider this well-known example of syn- tactic ambiguity: (1) The man saw the …

Content truncated to 500 words