Discriminative training of clustering functions
Published 1 January 2005Open access
Xin Li, Dan Roth
Citations9
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A framework in which clustering is viewed as a learning task is developed, and a way to train a distance metric that is appropriate for the chosen clustering algorithm in the context of the given task is proposed.
Abstract
Clustering is an optimization procedure that partitions a set of elements to optimize some criteria, based on a fixed distance metric defined between the elements. Clustering approaches have been widely applied in natural language processing and it has been shown repeatedly that their success depends on defining a good distance metric, one that is appropriate 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 algorithm in the context of the given task. Experiments in the context of the entity identification problem exhibit significant performance improvements over state-of-the-art clustering approaches developed for this problem.
Keywords
Computer Science
Class-based n -gram models of natural language
2,893 Citations1992Peter F. Brown, P.V. deSouza +3 more
This work addresses the problem of predicting a word from previous words in a sample of text and discusses n-gram models based on classes of words, finding that these models are able to extract classes that have the flavor of either syntactically based groupings or semanticallybased groupings, depending on the nature of the underlying statistics.
Distance Metric Learning with Application to Clustering with Side-Information
2,710 Citations2002Eric P. Xing, Michael I. Jordan +2 more
This paper presents an algorithm that, given examples of similar (and, if desired, dissimilar) pairs of points in �”n, learns a distance metric over ℝn that respects these relationships.
A comparison of string distance metrics for name-matching tasks
1,375 Citations2003William W. Cohen, Pradeep Ravikumar +1 more
This work investigates a number of different metrics proposed by different communities, including edit-distance metrics, fast heuristic string comparators, token-based distance metrics, and hybrid methods, and finds the best-performing method is a hybrid scheme combining a TFIDF weighting scheme with the Jaro-Winkler string-distance scheme.
Large margin classification using the perceptron algorithm
1,099 Citations1998Yoav Freund, Robert E. Schapire
Integrating constraints and metric learning in semi-supervised clustering
851 Citations2004Mikhail Bilenko, Sugato Basu +1 more
Experimental results demonstrate that the unified approach produces better clusters than both individual approaches as well as previously proposed semi-supervised clustering algorithms.
Learning a Distance Metric from Relative Comparisons
600 Citations2003Matthew Schultz, Thorsten Joachims
Taking a Support Vector Machine (SVM) approach, an algorithm is developed that provides a flexible way of describing qualitative training data as a set of constraints that leads to a convex quadratic programming problem that can be solved by adapting standard methods for SVM training.
Discovering word senses from text
597 Citations2002Patrick Pantel, Dekang Lin
A clustering algorithm called CBC (Clustering By Committee) that automatically discovers word senses from text that initially discovers a set of tight clusters called committees that are well scattered in the similarity space.
CLUTO - A Clustering Toolkit
551 Citations2002George Karypis
Clustering algorithms divide data into meaningful or useful groups, called clusters, such that the intra-cluster similarity is maximized and the inter-clusters similarity is minimized.
IEEE Intelligent SystemsAdaptive name matching in information integration
475 Citations2003Mikhail Bilenko, Razvan Bunescu and Raymond J. Mooney +3 more
The authors compare and describe methods for combining and learning textual similarity measures for name matching that are essential for information integration.
Learning distance functions using equivalence relations
435 Citations2003Aharon Bar-Hillel, Tomer Hertz +2 more
It is empirically demonstrate that learning a distance metric using the RCA algorithm significantly improves clustering performance, similarly to the alternative algorithm.
UC BerkeleyLearning Spectral Clustering
431 Citations2003Francis R. Bach, Michael I. Jordan
A new cost function for spectral clustering is derived based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem.
Machine LearningSimilarity-Based Models of Word Cooccurrence Probabilities
346 Citations1999Ido Dagan, Lillian Lee +1 more
This work proposes a method for estimating the probability of such previously unseen word combinations using available information on “most similar” words, and describes probabilistic word association models based on distributional word similarity, and applies them to two tasks, language modeling and pseudo-word disambiguation.
Learning to match and cluster large high-dimensional data sets for data integration
345 Citations2002William W. Cohen, Jacob Richman
Techniques for clustering and matching identifier names that are both scalable and adaptive, in the sense that they can be trained to obtain better performance in a particular domain are described.
Overview of the TREC 2005 Question Answering Track
326 Citations2005Ellen M. Voorhees
In its third year, the TREC question answering track continued to focus on retrieving small snippets of text that contain an answer to a question, however, several new conditions were added to increase the realism, and the difficulty, of the task.
Unsupervised personal name disambiguation
310 Citations2003Gideon Mann, David Yarowsky
This paper presents a set of algorithms for distinguishing personal names with multiple real referents in text, based on little or no supervision, using an unsupervised clustering technique over a rich feature space of biographic facts, which are automatically extracted via a language-independent bootstrapping process.
Characterising measures of lexical distributional similarity
304 Citations2004Julie Weeds, David Weir +1 more
A three-way connection is demonstrated between relative frequency of similar words, a concept of distributional gnerality and the semantic relation of hyponymy in a word's distributionally nearest neighbours with respect to the similarity measure.
arXiv (Cornell University)Learning to Resolve Natural Language Ambiguities: A Unified Approach
175 Citations1998Dan Roth
An extensive experimental comparison of the approach with other methods on several well studied lexical disambiguation tasks such as context-sensitive spelling correction, prepositional phrase attachment and part of speech tagging shows that it outperforms other methods tried for these tasks or performs comparably to the best.
Empirical Methods in Natural Language ProcessingNoun Phrase Coreference as Clustering
158 Citations1999Claire Cardie, Kiri L. Wagstaff
A new, unsupervised algorithm for noun phrase coreference resolution that appears to provide a flexible mechanism for coordinating the application of context-independent and context-dependent coreference constraints and preferences for accurate partitioning of noun phrases into coreference equivalence classes.
ScholarWorks@UMassAmherst (University of Massachusetts Amherst)Toward Conditional Models of Identity Uncertainty with Application to Proper Noun Coreference
150 Citations2003Andrew McCallum, Ben Wellner
This paper introduces several discriminative, conditionalprobability models for coreference analysis, all examples of undirected graphical models that can incorporate a great variety of features of the input without having to be concerned about their dependencies.
Learning to match and cluster large high-dimensional data sets for data integration
83 Citations2002William W. Cohen, Jacob Richman
Interpreting and Extending Classical Agglomerative Clustering Algorithms using a Model-Based approach
78 Citations2002Sepandar Kamvar, Dan Klein +1 more
It is shown formally that the common heuristic agglomerative clustering algorithms -- single-link, complete- link, group-average, and Ward's method -- are each equivalent to a hierarchical model-based method.
arXiv (Cornell University)Similarity-Based Approaches to Natural Language Processing
76 Citations1997Lillian Lee
The clustering method, which uses the technique of deterministic annealing, represents (to the authors' knowledge) the first application of soft clustering to problems in natural language processing, and is compared to several such nearest-neighbor approaches on a word sense disambiguation task and finds that as a whole, their performance is far superior to that of standard methods.
arXiv (Cornell University)Similarity-Based Models of Word Cooccurrence Probabilities
70 Citations1998Ido Dagan, Lillian Lee +1 more
Identification and tracing of ambiguous names: discriminative and generative approaches
54 Citations2004Xin Li, Paul Morie +1 more
This work presents two machine learning approaches to the problem of identifying whether different mentions of a name, within and across documents, represent the same entity, which it calls the "Robust Reading" problem.
Feature vector quality and distributional similarity
39 Citations2004Maayan Geffet, Ido Dagan
A new goal and evaluation criterion - meaning-entailing substitutability - fits the needs of semantic-oriented NLP applications and can be evaluated directly (independent of an application) at a good level of human agreement.