Proceedings

Learning from Partial Observations

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 968-973.

© 2007 International Joint Conferences on Artificial Intelligence

Abstract

We present a general machine learning framework for modelling the phenomenon of missing information in data. We propose a masking process model to capture the stochastic nature of information loss. Learning in this context is employed as a means to recover as much of the missing information as is recoverable. We extend the Probably Approximately Correct semantics to the case of learning from partial observations with arbitrarily hidden attributes. We establish that simply requiring learned hypotheses to be consistent with observed values suffices to guarantee that hidden values are recoverable to a certain accuracy; we also show that, in some sense, this is an optimal strategy for achieving accurate recovery. We then establish that a number of natural concept classes, including all the classes of monotone formulas that are PAC learnable by monotone formulas, and the classes of conjunctions, disjunctions, k-CNF, k-DNF, and linear thresholds, are consistently learnable from partial observations. We finally show that the concept classes of parities and monotone term 1-decision lists are not properly consistently learnable from partial observations, if RP ≠ NP. This implies a separation of what is consistently learnable from partial observations versus what is learnable in the complete or noisy setting.

  1. [Angluin and Laird, 1987] Dana Angluin and Philip D. Laird. Learning from noisy examples. Machine Learn- ing, 2(4):343-370, 1987.
  2. [Blumer et al., 1987] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K. Warmuth. Occam's razor. Information Processing Letters, 24:377-380, 1987.
  3. [Decatur and Gennaro, 1995] Scott E. Decatur and Rosario Gennaro. On learning from noisy and incomplete ex- amples. In Eighth Annual Conference on Computational Learning Theory, pages 353-360, 1995.
  4. [Dietterich et al., 1997] Thomas G. Dietterich, Richard H. Lathrop, and Tomás Lozano-Pérez. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31-71, 1997.
  5. [Goldman et al., 1997] Sally A. Goldman, Stephen Kwek, and Stephen D. Scott. Learning from examples with un- specified attribute values (extended abstract). In Tenth Annual Conference on Computational Learning Theory, pages 231-242, 1997.
  6. [Helmbold et al., 1992] David Helmbold, Robert Sloan, and Manfred K. Warmuth. Learning integer lattices. SIAM Journal on Computing, 21(2):240-266, 1992.
  7. [Kearns and Li, 1993] Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Jour- nal on Computing, 22(4):807-837, 1993.
  8. [Kearns and Vazirani, 1994] Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computa- tional Learning Theory. The MIT Press, Cambridge, Massachusetts, U.S.A., 1994.
  9. [Kearns, 1998] Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6):983-1006, 1998.
  10. [Pitt and Valiant, 1988] Leonard Pitt and Leslie G. Valiant. Computational limitations on learning from examples. Journal of the ACM, 35(4):965-984, 1988.
  11. [Rivest, 1987] Ronald L. Rivest. Learning decision lists. Ma- chine Learning, 2(3):229-246, 1987.
  12. [Schafer and Graham, 2002] Joseph L. Schafer and John W. Graham. Missing data: Our view of the state of the art. Journal of Psychological Methods, 7(2):147-177, 2002.
  13. [Schuurmans and Greiner, 1994] Dale Schuurmans and Rus- sell Greiner. Learning default concepts. In Tenth Canadian Conference on Artificial Intelligence, pages 99-106, 1994.
  14. [Shackelford and Volper, 1988] George Shackelford and Dennis Volper. Learning k-DNF with noise in the attributes. In First Annual Workshop on Computational Learning Theory, pages 97-103, 1988.
  15. [Valiant, 1984] Leslie G. Valiant. A theory of the learnable. Communications of the ACM, 27:1134-1142, 1984.
  16. [Valiant, 1985] Leslie G. Valiant. Learning disjunctions of conjunctions. In Ninth International Joint Conference on Artificial Intelligence, Vol. 1, pages 560-566, 1985.
  17. [Valiant, 2000] Leslie G. Valiant. Robust logics. Artificial Intelligence, 117(2):231-253, 2000.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards