Uncertainty sampling and transductive experimental design for active dual supervision

ABSTRACT

Dual supervision refers to the general setting of learning from both labeled examples as well as labeled features. Labeled features are naturally available in tasks such as text classification where it is frequently possible to provide domain knowledge in the form of words that associate strongly with a class. In this paper, we consider the novel problem of active dual supervision, or, how to optimally query an example and feature labeling oracle to simultaneously collect two different forms of supervision, with the objective of building the best classifier in the most cost effective manner. We apply classical uncertainty and experimental design based active learning schemes to graph/kernel-based dual supervision models. Empirical studies confirm the potential of these schemes to significantly reduce the cost of acquiring labeled data for training high-quality models.

REFERENCES

• 1: Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. Conference on Learning Theory (COLT) (pp. 486--500).
• 2: Gregory Druck , Gideon Mann , Andrew McCallum, Learning from labeled features using generalized expectation criteria, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390436]
• 3: Amir Globerson , Gal Chechik , Fernando Pereira , Naftali Tishby, Euclidean Embedding of Co-occurrence Data, The Journal of Machine Learning Research, 8, p.2265-2295, 12/1/2007
• 4: Shantanu Godbole , Abhay Harpale , Sunita Sarawagi , Soumen Chakrabarti, Document classification through interactive supervision of document and term labels, Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Databases, p.185-196, September 20-24, 2004, Pisa, Italy
• 5: Ho, & Dooren, P. (2005). On the pseudo-inverse of the laplacian of a bipartite graph. Appl. Math. Letters, 8, 917--922.
• 6: Prem Melville , Wojciech Gryc , Richard D. Lawrence, Sentiment analysis of blogs by combining lexical knowledge with text classification, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France [doi>10.1145/1557019.1557156]
• 7: Melville, P., & Sindhwani, V. (2009). Active dual supervision: Reducing the cost of annotating examples and features. NAACL HLT Workshop on Active Learning for NLP.
• 8: Hema Raghavan , James Allan, An interactive algorithm for asking and incorporating feature feedback into support vector machines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277758]
• 9: Maytal Saar-Tsechansky , Prem Melville , Foster Provost, Active Feature-Value Acquisition, Management Science, v.55 n.4, p.664-684, April 2009 [doi>10.1287/mnsc.1080.0952]
• 10: Sindhwani, V., Hu, J., & Mojsilovic, A. (2008). Regularized co-clustering with dual supervision. Neural Information Processing Systems (NIPS) (pp. 976--983).
• 11: Smola, A., & Kondor, R. (2004). Kernels and regularization on graphs. Conf. on Learning Theory (COLT) (pp. 144--158).
• 12: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002 [doi>10.1162/153244302760185243]
• 13: Kai Yu , Jinbo Bi , Volker Tresp, Active learning via transductive experimental design, Proceedings of the 23rd international conference on Machine learning, p.1081-1088, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143980]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Experimental design

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Experimentation, Performance, Theory