Get another label? improving data quality and data mining using multiple, noisy labelers

ABSTRACT

This paper addresses the repeated acquisition of labels for data items when the labeling is imperfect. We examine the improvement (or lack thereof) in data quality via repeated labeling, and focus especially on the improvement of training labels for supervised induction. With the outsourcing of small tasks becoming easier, for example via Rent-A-Coder or Amazon's Mechanical Turk, it often is possible to obtain less-than-expert labeling at low cost. With low-cost labeling, preparing the unlabeled part of the data can become considerably more expensive than labeling. We present repeated-labeling strategies of increasing complexity, and show several main results. (i) Repeated-labeling can improve label quality and model quality, but not always. (ii) When labels are noisy, repeated labeling can be preferable to single labeling even in the traditional setting where labels are not particularly cheap. (iii) As soon as the cost of processing the unlabeled data is not free, even the simple strategy of labeling everything multiple times can give considerable advantage. (iv) Repeatedly labeling a carefully chosen set of points is generally preferable, and we present a robust technique that combines different notions of uncertainty to select data points for which quality should be improved. The bottom line: the results show clearly that when labeling is not perfect, selective acquisition of multiple labels is a strategy that data miners should have in their repertoire; for certain label-quality/cost regimes, the benefit is substantial.

REFERENCES

• 1: Yoram Baram , Ran El-Yaniv , Kobi Luz, Online Choice of Active Learning Algorithms, The Journal of Machine Learning Research, 5, p.255-291, 12/1/2004
• 2: Blake, C. L., and Merz, C. J. UCI repository of machine learning databases. http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
• 3: Boutell, M. R., Luo, J., Shen, X., and Brown, C. M. Learning multi-label scene classification. Pattern Recognition 37, 9 (Sept. 2004), 1757--1771.
• 4: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 5: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 6: Dawid, A. P., and Skene, A. M. Maximum likelihood estimation of observer error-rates using the EM algorithm. Applied Statistics 28, 1 (Sept. 1979), 20--28.
• 7: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 8: Elkan, C. The foundations of cost-sensitive learning. In IJCAI (2001), pp. 973--978.
• 9: Gelman, A., Carlin, J. B., Stern, H. S., and Rubin, D. B. Bayesian Data Analysis, 2nd ed. Chapman and Hall/CRC, 2003.
• 10: Jin, R., and Ghahramani, Z. Learning with multiple labels. In NIPS (2002), pp. 897--904.
• 11: Kapoor, A., and Greiner, R. Learning and classifying under hard budgets. In ECML (2005), pp. 170--181.
• 12: Lizotte, D. J., Madani, O., and Greiner, R. Budgeted learning of naive-bayes classifiers. In UAI) (2003), pp. 378--385.
• 13: Gábor Lugosi, Learning with an unreliable teacher, Pattern Recognition, v.25 n.1, p.79-87, Jan. 1992 [doi>10.1016/0031-3203(92)90008-7]
• 14: Margineantu, D. D. Active cost-sensitive learning. In IJCAI) (2005), pp. 1622--1613.
• 15: McCallum, A. Multi-label text classification with a mixture model trained by EM. In AAAI'99 Workshop on Text Learning (1999).
• 16: Prem Melville , Maytal Saar-Tsechansky , Foster Provost , Raymond Mooney, An Expected Utility Approach to Active Feature-Value Acquisition, Proceedings of the Fifth IEEE International Conference on Data Mining, p.745-748, November 27-30, 2005 [doi>10.1109/ICDM.2005.23]
• 17: Prem Melville , Maytal Saar-Tsechansky , Foster Provost , Raymond Mooney, Active Feature-Value Acquisition for Classifier Induction, Proceedings of the Fourth IEEE International Conference on Data Mining, p.483-486, November 01-04, 2004
• 18: Clayton T. Morrison , Paul R. Cohen, Noisy information value in utility-based decision making, Proceedings of the 1st international workshop on Utility-based data mining, p.34-38, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1089827.1089831]
• 19: Foster Provost, Toward economic machine learning and utility-based data mining, Proceedings of the 1st international workshop on Utility-based data mining, August 21-21, 2005, Chicago, Illinois [doi>10.1145/1089827.1089841]
• 20: Provost, F., and Danyluk, A. Learning from Bad Data. In Proceedings of the ML-95 Workshop on Applying Machine Learning in Practice (1995).
• 21: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 22: Saar-Tsechansky, M., Melville, P., and Provost, F. J. Active feature-value acquisition. Tech. Rep. IROM-08-06, University of Texas at Austin, McCombs Research Paper Series, Sept. 2007.
• 23: Maytal Saar-Tsechansky , Foster Provost, Active Sampling for Class Probability Estimation and Ranking, Machine Learning, v.54 n.2, p.153-178, February 2004 [doi>10.1023/B:MACH.0000011806.12374.c3]
• 24: Silverman, B. W. Some asymptotic properties of the probabilistic teacher. IEEE Transactions on Information Theory 26, 2 (Mar. 1980), 246--249.
• 25: Smyth, P. Learning with probabilistic supervision. In Computational Learning Theory and Natural Learning Systems, Vol. III: Selecting Good Models, T. Petsche, Ed. MIT Press, Apr. 1995.
• 26: Padhraic Smyth, Bounds on the mean classification error rate of multiple experts, Pattern Recognition Letters, v.17 n.12, p.1253-1257, Oct. 25, 1996 [doi>10.1016/0167-8655(96)00105-5]
• 27: Smyth, P., Burl, M. C., Fayyad, U. M., and Perona, P. Knowledge discovery in large image databases: Dealing with uncertainties in ground truth. In Knowledge Discovery in Databases: Papers from the 1994 AAAI Workshop (KDD'94) (1994), pp. 109--120.
• 28: Smyth, P., Fayyad, U. M., Burl, M. C., Perona, P., and Baldi, P. Inferring ground truth from subjective labelling of Venus images. In NIPS (1994), pp. 1085--1092.
• 29: K. M. Ting, An Instance-Weighting Method to Induce Cost-Sensitive Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.659-665, May 2002 [doi>10.1109/TKDE.2002.1000348]
• 30: Turney, P. D. Cost-sensitive classification: Empirical evaluation of a hybrid genetic decision tree induction algorithm. Journal of Artificial Intelligence Research 2 (1995), 369--409.
• 31: Turney, P. D. Types of cost in inductive concept learning. In Proceedings of the ICML-2000 Workshop on Cost-Sensitive Learning (2000), pp. 15--21.
• 32: Weiss, G. M., and Provost, F. J. Learning when training data are costly: The e ect of class distribution on tree induction. Journal of Artificial Intelligence Research 19 (2003), 315--354.
• 33: Whittle, P. Some general points in the theory of optimal experimental design. Journal of the Royal Statistical Society, Series B (Methodological) 35, 1 (1973), 123--130.
• 34: Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 35: Bianca Zadrozny , John Langford , Naoki Abe, Cost-Sensitive Learning by Cost-Proportionate Example Weighting, Proceedings of the Third IEEE International Conference on Data Mining, p.435, November 19-22, 2003
• 36: Zhiqiang Zheng , Balaji Padmanabhan, Selectively Acquiring Customer Information: A New Data Acquisition Problem and an Active Learning-Based Solution, Management Science, v.52 n.5, p.697-712, May 2006 [doi>10.1287/mnsc.1050.0488]
• 37: Xingquan Zhu , Xindong Wu, Cost-Constrained Data Acquisition for Intelligent Data Preparation, IEEE Transactions on Knowledge and Data Engineering, v.17 n.11, p.1542-1556, November 2005 [doi>10.1109/TKDE.2005.176]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation

General Terms:
Algorithms, Design, Experimentation, Management, Measurement, Performance

Keywords:
data preprocessing, data selection