Cross-Instance Tuning of Unsupervised Document Clustering Algorithms

Proceedings of NAACL HLT 2007, pages 252–259, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Cross-Instance Tuning of Unsupervised Document Clustering Algorithms∗ Damianos Karakos, Jason Eisner and Sanjeev Khudanpur Center for Language and Speech Processing Johns Hopkins University Baltimore, MD 21218 {damianos,eisner,khudanpur}@jhu.edu Carey E. Priebe Dept. of Applied Mathematics and Statistics Johns Hopkins University Baltimore, MD 21218 cep@jhu.edu Abstract In unsupervised learning, where no train- ing takes place, one simply hopes that the unsupervised learner will work well on any unlabeled test collection. How- ever, when the variability in the data is large, such hope may be unrealistic; a tuning of the unsupervised algorithm may then be necessary in order to perform well on new test collections. In this paper, we show how to perform such a tuning in the context of unsupervised document clustering, by (i) introducing a degree of freedom, α, into two leading information- theoretic clustering algorithms, through the use of generalized mutual informa- tion quantities; and (ii) selecting the value of α based on clusterings of similar, but supervised document collections (cross- instance tuning). One option is to perform a tuning that directly minimizes the error on the supervised data sets; another option is to use “strapping” (Eisner and Karakos, 2005), which builds a classifier that learns to distinguish good from bad clusterings, and then selects the α with the best pre- dicted clustering on the test set. Experi- ments from the “20 Newsgroups” corpus show that, although both techniques im- prove the performance of the baseline al- gorithms, “strapping” is clearly a better choice for cross-instance tuning. ∗This work was partially supported by the DARPA GALE program (Contract No¯ HR0011-06-2-0001) and by the JHU WSE/APL Partnership Fund. 1 Introduction The problem of combining labeled and unlabeled examples in a learning task (semi-supervised learn- ing) has been studied in the literature under various guises. A variety of algorithms (e.g., bootstrapping (Yarowsky, 1995), co-training (Blum and Mitchell, 1998), alternating structure optimization (Ando and Zhang, 2005), etc.) have been developed in order to improve the performance of supervised algorithms, by automatically extracting knowledge from lots of unlabeled examples. Of special interest is the work of Ando and Zhang (2005), where the goal is to build many supervised auxiliary tasks from the unsuper- vised data, by creating artificial labels; this proce- dure helps learn a transformation of the input space that captures the relatedness of the auxiliary prob- lems to the task at hand. In essence, Ando and Zhang (2005) transform the semi-supervised learning prob- lem to a multi-task learning problem; in multi-task learning, a (usually large) set of supervised tasks is available for training, and the goal is to build mod- els which can simultaneously do well on all of them (Caruana, 1997; Ben-David and Schuller, 2003; Ev- geniou and Pontil, 2004). Little work, however, has been devoted to study the situation where lots of labeled examples, of one kind, are used to build a model which is tested on unlabeled data of a “different” kind. This …

Content truncated to 500 words