Soft-Supervised Learning for Text Classification

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 1090–1099, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Soft-Supervised Learning for Text Classification Amarnag Subramanya & Jeff Bilmes Dept. of Electrical Engineering, University of Washington, Seattle, WA 98195, USA. {asubram,bilmes}@ee.washington.edu Abstract We propose a new graph-based semi- supervised learning (SSL) algorithm and demonstrate its application to document categorization. Each document is represented by a vertex within a weighted undirected graph and our proposed framework minimizes the weighted Kullback-Leibler divergence between distributions that encode the class membership probabilities of each vertex. The proposed objective is convex with guaranteed convergence using an alternating minimiza- tion procedure. Further, it generalizes in a straightforward manner to multi-class problems. We present results on two stan- dard tasks, namely Reuters-21578 and WebKB, showing that the proposed algorithm significantly outperforms the state-of-the-art. 1 Introduction Semi-supervised learning (SSL) employs small amounts of labeled data with relatively large amounts of unlabeled data to train classifiers. In many problems, such as speech recognition, doc- ument classification, and sentiment recognition, annotating training data is both time-consuming and tedious, while unlabeled data are easily ob- tained thus making these problems useful appli- cations of SSL. Classic examples of SSL algo- rithms include self-training (Yarowsky, 1995) and co-training (Blum and Mitchell, 1998). Graph- based SSL algorithms are an important class of SSL techniques that have attracted much of attention of late (Blum and Chawla, 2001; Zhu et al., 2003). Here one assumes that the data (both labeled and unlabeled) is embedded within a low-dimensional manifold expressed by a graph. In other words, each data sample is represented by a vertex within a weighted graph with the weights providing a mea- sure of similarity between vertices. Most graph-based SSL algorithms fall under one of two categories – those that use the graph structure to spread labels from labeled to unlabeled samples (Szummer and Jaakkola, 2001; Zhu and Ghahra- mani, 2002) and those that optimize a loss function based on smoothness constraints derived from the graph (Blum and Chawla, 2001; Zhu et al., 2003; Joachims, 2003; Belkin et al., 2005). Sometimes the two categories are similar in that they can be shown to optimize the same underlying objective (Zhu and Ghahramani, 2002; Zhu et al., 2003). In general graph-based SSL algorithms are non-parametric and transductive.1 A learning algorithm is said to be transductive if it is expected to work only on a closed data set, where a test set is revealed at the time of training. In practice, however, transductive learners can be modified to handle unseen data (Zhu, 2005a; Sindhwani et al., 2005). A common drawback of many graph-based SSL algorithms (e.g. (Blum and Chawla, 2001; Joachims, 2003; Belkin et al., 2005)) is that they assume binary classification tasks and thus require the use of sub-optimal (and often com- putationally expensive) approaches such as one vs. rest to solve multi-class problems, let alone struc- tured domains such as strings and trees. There are also issues related to degenerate solutions (all …

Content truncated to 500 words