Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 411–418, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling Rada Mihalcea Department of Computer Science University of North Texas rada@cs.unt.edu Abstract This paper introduces a graph-based algo- rithm for sequence data labeling, using ran- dom walks on graphs encoding label de- pendencies. The algorithm is illustrated and tested in the context of an unsuper- vised word sense disambiguation problem, and shown to significantly outperform the accuracy achieved through individual label assignment, as measured on standard sense- annotated data sets. 1 Introduction Many natural language processing tasks consist of la- beling sequences of words with linguistic annotations, e.g. word sense disambiguation, part-of-speech tag- ging, named entity recognition, and others. Typical labeling algorithms attempt to formulate the annota- tion task as a traditional learning problem, where the correct label is individually determined for each word in the sequence using a learning process, usually con- ducted independent of the labels assigned to the other words in the sequence. Such algorithms do not have the ability to encode and thereby exploit dependen- cies across labels corresponding to the words in the sequence, which potentially limits their performance in applications where such dependencies can influence the selection of the correct set of labels. In this paper, we introduce a graph-based sequence data labeling algorithm well suited for such natural language annotation tasks. The algorithm simultane- ously annotates all the words in a sequence by ex- ploiting relations identified among word labels, us- ing random walks on graphs encoding label dependen- cies. The random walks are mathematically modeled through iterative graph-based algorithms, which are applied on the label graph associated with the given sequence of words, resulting in a stationary distribu- tion over label probabilities. These probabilities are then used to simultaneously select the most probable set of labels for the words in the input sequence. The annotation method is illustrated and tested on an unsupervised word sense disambiguation prob- lem, targeting the annotation of all open-class words in unrestricted text using information derived exclu- sively from dictionary definitions. The graph-based sequence data labeling algorithm significantly outper- forms the accuracy achieved through individual data labeling, resulting in an error reduction of 10.7%, as measured on standard sense-annotated data sets. The method is also shown to exceed the performance of other previously proposed unsupervised word sense disambiguation algorithms. 2 Iterative Graphical Algorithms for Sequence Data Labeling In this section, we introduce the iterative graphical al- gorithm for sequence data labeling. The algorithm is succinctly illustrated using a sample sequence for a generic annotation problem, with a more extensive il- lustration and evaluation provided in Section 3. Given a sequence of words W = {w1, w2, ..., wn}, each word wi with corresponding admissible labels Lwi = {l1 wi, l2 wi, ..., l Nwi wi }, we define a label graph G = (V,E) such that there is a …

Content truncated to 500 words