Good learners for evil teachers

ABSTRACT

We consider a supervised machine learning scenario where labels are provided by a heterogeneous set of teachers, some of which are mediocre, incompetent, or perhaps even malicious. We present an algorithm, built on the SVM framework, that explicitly attempts to cope with low-quality and malicious teachers by decreasing their influence on the learning process. Our algorithm does not receive any prior information on the teachers, nor does it resort to repeated labeling (where each example is labeled by multiple teachers). We provide a theoretical analysis of our algorithm and demonstrate its merits empirically. Finally, we present a second algorithm with promising empirical results but without a formal analysis.

REFERENCES

• 1: Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., & Wortman, J. (2007). Learning bounds for domain adaptation. Advances in Neural Information Processing Systems 21 (pp. 129--136).
• 2: Koby Crammer , Michael Kearns , Jennifer Wortman, Learning from Multiple Sources, The Journal of Machine Learning Research, 9, p.1757-1774, 6/1/2008
• 3: Ofer Dekel , Felix Fischer , Ariel D. Procaccia, Incentive compatible regression learning, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.884-893, January 20-22, 2008, San Francisco, California
• 4: Ofer Dekel , Ohad Shamir, Learning to classify with missing and corrupted features, Proceedings of the 25th international conference on Machine learning, p.216-223, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390184]
• 5: Michael Kearns, Efficient noise-tolerant learning from statistical queries, Journal of the ACM (JACM), v.45 n.6, p.983-1006, Nov. 1998 [doi>10.1145/293347.293351]
• 6: David D. Lewis , Yiming Yang , Tony G. Rose , Fan Li, RCV1: A New Benchmark Collection for Text Categorization Research, The Journal of Machine Learning Research, 5, p.361-397, 12/1/2004
• 7: Shai Shalev-Shwartz , Yoram Singer , Nathan Srebro, Pegasos: Primal Estimated sub-GrAdient SOlver for SVM, Proceedings of the 24th international conference on Machine learning, p.807-814, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273598]
• 8: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 9: Victor S. Sheng , Foster Provost , Panagiotis G. Ipeirotis, Get another label? improving data quality and data mining using multiple, noisy labelers, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401965]
• 10: Smyth, P., Fayyad, U., Burl, M., Perona, P., & Baldi, P. (1994). Inferring ground truth from subjective labeling of Venus images. Advances in Neural Information Processing Systems 8 (pp. 1085--1092).
• 11: Teo, C. H., Globerson, A., Roweis, S. T., & Smola, A. (2007). Convex learning with invariances. Advances in Neural Information Processing Systems 21 (pp. 1489--1496).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory