Partially Supervised Classification

Learning from Positive and Unlabeled Examples


Recent talk given in Boeing, UIUC, University of Trento (Italy) and University of Siena (Italy) which summarizes the theory and some algorithms.


Text classification is the automated assignment of text documents to pre-defined categories/classes. Traditionally, a classifier is built using training documents labeled (often manually) with pre-defined classes. This classifier is then used to classify new documents into those classes. This classic model is called supervised classification because the training documents all have pre-labeled classes. Although this model is important, in practice it may not be applicable in some common situations. For example, given a set of documents of a particular class P (positive class) and a set U of mixed or unlabeled documents that contains documents from class P along with other types of documents (negative documents), one may want to classify documents in U into documents from P and documents not from P. Since there are no labeled negative documents, the traditional classification techniques are inapplicable. This problem is called partially supervised classification (PSC). Existing methods for solving PSC are based on heuristics, which are prone to error. Researchers typically use the evaluation method for supervised classification to evaluate PSC techniques, which is inadequate because supervised classification approaches assume the availability of labeled negative documents.

The objectives of this project are to design a robust and principled technique to solve PSC, implement a system for PSC, devise a method to evaluate such techniques, and identify methods for determining the minimum number of labeled documents needed to achieve the optimal accuracy in order to reduce manual labeling efforts. The results of this research should be widely useful because the identification of targeted information/documents is of great value in this information age.

In our work in (Liu et al. 2002), it was shown theoretically that P and U provide sufficient information for learning, and the problem can be posed as a constrained optimization problem. This theoretical result provides a good guidance for designing practical algorithems. Some of our algorithms are reported in (Liu et al 2003), (Lee and Liu 2003) and (Li and Liu 2003).

Publications

  1. Bing Liu Xiaoli Li, Wee Sun Lee and and Philip Yu. "Text Classification by Labeling Words." To appear in Proceedings of The Nineteenth National Conference on Artificial Intelligence (AAAI-2004), July 25-29, 2004, San Jose, California. [ReadySoon]

  2. Bing Liu, Yang Dai, Xiaoli Li, Wee Sun Lee and and Philip Yu. "Building Text Classifiers Using Positive and Unlabeled Examples." To appear in Proceedings of the Third IEEE International Conference on Data Mining (ICDM-03), Melbourne, Florida, November 19-22, 2003. [PDF]

  3. Xiaoli Li, Bing Liu. Learning to classify text using positive and unlabeled data. To appear in Proceedings of Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Aug 9-15, 2003, Acapulco, Mexico.

  4. Wee Sun Lee, Bing Liu. Learning with Positive and Unlabeled Examples using Weighted Logistic Regression. To appear in Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), August 21-24, 2003, Washington, DC USA.

  5. Bing Liu, Wee Sun Lee, Philip S Yu and Xiaoli Li. Partially Supervised Classification of Text Documents. Proceedings of the Nineteenth International Conference on Mach ine Learning (ICML-2002), 8-12, July 2002, Sydney, Australia.

Software


Created on July 20, 2003 by Bing Liu.