Decision Tree Models Applied to the Labeling of Text with Parts-of-Speech

Decision Tree Models Applied to the Labeling of Text with Parts-of-Speech Ezra Black Fred Jelinek John Lafferty Robert Mercer Salim Roukos IBM Thomas J. Watson Research Center ABSTRACT We describe work which uses decision trees to estimate marginal probabilities in a maximum entropy model for pre- dicting the part-of-speech of a word given the context in which it appears. Two experiments are presented which ex- hibit improvements over the usual hidden Markov model ap- proach. 1. Introduction In this paper we describe work which uses decision trees to estimate probabilities of words appearing with various parts-of-speech, given the context in which the words ap- pear. In principle, this approach affords the optimal so- lution to the problem of predicting the correct sequence of parts-of-speech. In practice, the method is limited by the lack of large, hand-labeled training corpora, as well as by the difficulty inherent in constructing a set of ques- tions to be used in the decision procedure. Nevertheless, decision trees provide a powerful mechanism for tackling the problem of modeling long-distance dependencies. The following sentence is typical of the difficulties facing a tagging program: The new energy policy announced in December by the Prime Minister will guarantee sufficien~ oil sup- plies at one price only. structed a complete set of binary questions to be asked of words, using a mutual information clustering procedure [2]. We then extracted a set of events from a 2-million word corpus of hand-labeled text. Using an algorithm similar to that described in [1], the set of contexts was divided into equivalence classes using a decision proce- dure which queried the binary questions, splitting the data based upon the principle of maximum mutual in- formation between tags and questions. The resulting tree was then smoothed using the forward-backward al- gorithm [6] on a set of held-out events, and tested on a set of previously unseen sentences from the hand-labeled corpus. The results showed a modest improvement over the usual hidden Markov model approach. We present explana- tions and examples of the results obtained and suggest ideas for obtaining further improvements. 2. Decision Trees The problem at hand is to predict a tag for a given word in a sentence, taking into consideration the tags assigned to previous words, as well as the remaining words in the sentence. Thus, if we wish to predict tag S,~ for word w~ in a sentence S -- wl, w2, • • •, wN, then we must form an estimate of the probability The usual hidden Markov model, trained as described the last section of this paper, incorrectly labeled the verb announced as having the active rather than the passive aspect. If, however, a decision procedure is used to re- solve the ambiguity, the context may be queried to de- termine the nature of the verb as well its agent. We can easily imagine, for example, that if the battery of avail- able questions is rich enough to include such queries as "Is the previous noun inanimate?" and "Does …

Content truncated to 500 words