Discriminative Training of Clustering Functions: Theory and Experiments with Entity Identification

Proceedings of the 9th Conference on Computational Natural Language Learning (CoNLL), pages 64–71, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Discriminative Training of Clustering Functions: Theory and Experiments with Entity Identification Xin Li and Dan Roth Department of Computer Science University of Illinois, Urbana, IL 61801 (xli1,danr)@cs.uiuc.edu Abstract Clustering is an optimization procedure that partitions a set of elements to optimize some criteria, based on a fixed distance metric de- fined between the elements. Clustering ap- proaches have been widely applied in natural language processing and it has been shown re- peatedly that their success depends on defin- ing a good distance metric, one that is appro- priate for the task and the clustering algorithm used. This paper develops a framework in which clustering is viewed as a learning task, and proposes a way to train a distance metric that is appropriate for the chosen clustering al- gorithm in the context of the given task. Ex- periments in the context of the entity identifi- cation problem exhibit significant performance improvements over state-of-the-art clustering approaches developed for this problem. 1 Introduction Clustering approaches have been widely applied to nat- ural language processing (NLP) problems. Typically, natural language elements (words, phrases, sentences, etc.) are partitioned into non-overlapping classes, based on some distance (or similarity) metric defined between them, in order to provide some level of syntactic or se- mantic abstraction. A key example is that of class-based language models (Brown et al., 1992; Dagan et al., 1999) where clustering approaches are used in order to parti- tion words, determined to be similar, into sets. This enables estimating more robust statistics since these are computed over collections of “similar” words. A large number of different metrics and algorithms have been ex- perimented with these problems (Dagan et al., 1999; Lee, 1997; Weeds et al., 2004). Similarity between words was also used as a metric in a distributional clustering algo- rithm in (Pantel and Lin, 2002), and it shows that func- tionally similar words can be grouped together and even separated to smaller groups based on their senses. At a higher level, (Mann and Yarowsky, 2003) disambiguated personal names by clustering people’s home pages using a TFIDF similarity, and several other researchers have ap- plied clustering at the same level in the context of the entity identification problem (Bilenko et al., 2003; Mc- Callum and Wellner, 2003; Li et al., 2004). Similarly, ap- proaches to coreference resolution (Cardie and Wagstaff, 1999) use clustering to identify groups of references to the same entity. Clustering is an optimization procedure that takes as input (1) a collection of domain elements along with (2) a distance metric between them and (3) an algorithm se- lected to partition the data elements, with the goal of op- timizing some form of clustering quality with respect to the given distance metric. For example, the K-Means clustering approach (Hartigan and Wong, 1979) seeks to maximize a measure of tightness of the resulting clusters based on the Euclidean distance. Clustering is …

Content truncated to 500 words