Learning from incomplete data with infinite imputations

ABSTRACT

We address the problem of learning decision functions from training data in which some attribute values are unobserved. This problem can arise, for instance, when training data is aggregated from multiple sources, and some sources record only a subset of attributes. We derive a generic joint optimization problem in which the distribution governing the missing values is a free parameter. We show that the optimal solution concentrates the density mass on finitely many imputations, and provide a corresponding algorithm for learning from incomplete data. We report on empirical results on benchmark data, and on the email spam application that motivates our work.

REFERENCES

• 1: Argyriou, A., Micchelli, C., & Pontil, M. (2005). Learning convex combinations of continuously parameterized basic kernels. Proceedings of the 18th Conference on Learning Theory.
• 2: Chechik, G., Heitz, G., Elidan, G., Abbeel, P., & Koller, D. (2007). Max-margin classification of incomplete data. Advances in Neural Information Processing Systems 19.
• 3: Xuejun Liao , Hui Li , Lawrence Carin, Quadratically gated mixture of experts for incomplete data classification, Proceedings of the 24th international conference on Machine learning, p.553-560, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273566]
• 4: Charles A. Micchelli , Massimiliano Pontil, Feature space perspectives for learning the kernel, Machine Learning, v.66 n.2-3, p.297-319, March 2007 [doi>10.1007/s10994-006-0679-0]
• 5: Pannagadatta K. Shivaswamy , Chiranjib Bhattacharyya , Alexander J. Smola, Second Order Cone Programming Approaches for Handling Missing and Uncertain Data, The Journal of Machine Learning Research, 7, p.1283-1314, 12/1/2006
• 6: Smola, A., Vishwanathan, S., & Hofmann, T. (2005). Kernel methods for missing variables. Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics.
• 7: Williams, D., & Carin, L. (2005). Analytical kernel matrix completion with incomplete multi-view data. Proceedings of the ICML 2005 Workshop on Learning With Multiple Views.
• 8: David Williams , Xuejun Liao , Ya Xue , Lawrence Carin, Incomplete-data classification using logistic regression, Proceedings of the 22nd international conference on Machine learning, p.972-979, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102474]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory