Distinguishing Word Senses in Untagged Text

Distinguishing Word Senses in Untagged Text Ted Pedersen and Rebecca Bruce Department of Computer Science and Engineering Southern Methodist University Dallas, TX 75275-0112 {pedersen,rbruce)@seas.smu.edu Abstract This paper describes an experimental com- parison of three unsupervised learning al- gorithms that distinguish the sense of an ambiguous word in untagged text. The methods described in this paper, McQuitty's similarity analysis, Ward's minimum-variance method, and the EM algorithm, assign each instance of an am- biguous word to a known sense definition based solely on the values of automatically identifiable features in text. These meth- ods and feature sets are found to be more successful in disambiguating nouns rather than adjectives or verbs. Overall, the most accurate of these procedures is McQuitty's similarity analysis in combination with a high dimensional feature set. 1 Introduction Statistical methods for natural language process- ing are often dependent on the availability of costly knowledge sources such as manually annotated text or semantic networks. This limits the applicability of such approaches to domains where this hard to acquire knowledge is already available. This paper presents three unsupervised learning algorithms that are able to distinguish among the known senses (i.e., as defined in some dictionary) of a word, based only on features that can be automatically extracted from untagged text. The object of unsupervised learning is to deter- mine the class membership of each observation (i.e. each object to be classified), in a sample without us- ing training examples of correct classifications. We discuss three algorithms, McQuitty's similarity anal- ysis (McQuitty, 1966), Ward's minimum-variance method (Ward, 1963) and the EM algorithm (Demp- ster, Laird, and Rubin, 1977), that can be used to distinguish among the known senses of an ambigu- ous word without the aid of disambiguated exam- ples. The EM algorithm produces maximum likeli- hood estimates of the parameters of a probabilistic model, where that model has been specified in ad- vance. Both Ward's and McQuitty's methods are ag- glomerative clustering algorithms that form classes of unlabeled observations that minimize their respec- tive distance measures between class members. The rest of this paper is organized as follows. First, we present introductions to Ward's and Mc- Quitty's methods (Section 2) and the EM algorithm (Section 3). We discuss the thirteen words (Section 4) and the three feature sets (Section 5) used in our experiments. We present our experimental results (Section 6) and close with a discussion of related work (Section 7). 2 Agglomerative Clustering In general, clustering methods rely on the assump- tion that classes occupy distinct regions in the fea- ture space. The distance between two points in a multi-dimensional space can be measured using any of a wide variety of metrics (see, e.g. (Devijver and Kittler, 1982)). Observations are grouped in the manner that minimizes the distance between the members of each class. Ward's and McQuitty's method are agglomerative clustering algorithms that differ primarily in how they compute the distance between clusters. All such algorithms begin by placing each observation in a unique cluster, i.e. a cluster of …

Content truncated to 500 words