Cascaded Markov Models

Proceedings of EACL '99 Cascaded Markov Models Thorsten Brants Universit/it des Saarlandes, Computerlinguistik D-66041 Saarbriicken, Germany thorsten@coli, uni-sb, de Abstract This paper presents a new approach to partial parsing of context-free structures. The approach is based on Markov Mod- els. Each layer of the resulting structure is represented by its own Markov Model, and output of a lower layer is passed as input to the next higher layer. An em- pirical evaluation of the method yields very good results for NP/PP chunking of German newspaper texts. 1 Introduction Partial parsing, often referred to as chunking, is used as a pre-processing step before deep analysis or as shallow processing for applications like in- formation retrieval, messsage extraction and text summarization. Chunking concentrates on con- structs that can be recognized with a high degree of certainty. For several applications, this type of information with high accuracy is more valuable than deep analysis with lower accuracy. We will present a new approach to partial pars- ing that uses Markov Models. The presented models are extensions of the part-of-speech tag- ging technique and are capable of emitting struc- ture. They utilize context-free grammar rules and add left-to-right transitional context information. This type of model is used to facilitate the syntac- tic annotation of the NEGRA corpus of German newspaper texts (Skut et al., 1997). Part-of-speech tagging is the assignment of syn- tactic categories (tags) to words that occur in the processed text. Among others, this task is ef- ficiently solved with Markov Models. States of a Markov Model represent syntactic categories (or tuples of syntactic categories), and outputs represent words and punctuation (Church, 1988; DeRose, 1988, and others). This technique of sta- tistical part-of-speech tagging operates very suc- cessfully, and usually accuracy rates between 96 and 97% are reported for new, unseen text. Brants et al. (1997) showed that the technique of statistical tagging can be shifted to the next level of syntactic processing and is capable of as- signing grammatical functions. These are func- tions like subject, direct object, head, etc. They mark the function of a child node within its par- ent phrase. Figure 1 shows an example sentence and its structure. The terminal sequence is complemen- ted by tags (Stuttgart-Tiibingen-Tagset, Thielen and Schiller, 1995). Non-terminal nodes are la- beled with phrase categories, edges are labeled with grammatical functions (NEGRA tagset). In this paper, we will show that Markov Mod- els are not restricted to the labeling task (i.e., the assignment of part-of-speech labels, phrase labels, or labels for grammatical functions), but are also capable of generating structural elements. We will use cascades of Markov Models. Starting with the part-of-speech layer, each layer of the result- ing structure is represented by its own Markov Model. A lower layer passes its output as input to the next higher layer. The output of a layer can be ambiguous and it is complemented by a probability distribution for the alternatives. This type of parsing is inspired by finite state cascades which are presented by several …

Content truncated to 500 words