Knows what it knows: a framework for self-aware learning

ABSTRACT

We introduce a learning framework that combines elements of the well-known PAC and mistake-bound models. The KWIK (knows what it knows) framework was designed particularly for its utility in learning settings where active exploration can impact the training examples the learner is exposed to, as is true in reinforcement-learning and active-learning problems. We catalog several KWIK-learnable classes and open problems.

REFERENCES

• 1: Dana Angluin, Queries revisited, Theoretical Computer Science, v.313 n.2, p.175-194, 17 February 2004 [doi>10.1016/j.tcs.2003.11.004]
• 2: Bagnell, J., Ng, A. Y., & Schneider, J. (2001). Solving uncertain Markov decision problems (Technical Report CMU-RI-TR-01-25). Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
• 3: Avrim L. Blum, Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain, SIAM Journal on Computing, v.23 n.5, p.990-1000, Oct. 1994 [doi>10.1137/S009753979223455X]
• 4: Ronen I. Brafman , Moshe Tennenholtz, R-max - a general polynomial time algorithm for near-optimal reinforcement learning, The Journal of Machine Learning Research, 3, p.213-231, 3/1/2003
• 5: Nicolò Cesa-Bianchi , Claudio Gentile , Luca Zaniboni, Worst-Case Analysis of Selective Sampling for Linear Classification, The Journal of Machine Learning Research, 7, p.1205-1230, 12/1/2006
• 6: Cesa-Bianchi, N., Lugosi, G., & Stoltz, G. (2005). Minimizing regret with label efficient prediction. IEEE Transactions on Information Theory, 51, 2152--2162.
• 7: 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]
• 8: Fong, P. W. L. (1995). A quantitative study of hypothesis selection. Proceedings of the Twelfth International Conference on Machine Learning (ICML-95) (pp. 226--234).
• 9: Yoav Freund , Robert E. Schapire , Yoram Singer , Manfred K. Warmuth, Using and combining predictors that specialize, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.334-343, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258616]
• 10: David P. Helmbold , Nicholas Littlestone , Philip M. Long, Apple tasting, Information and Computation, v.161 n.2, p.85-139, Sept. 15 2000 [doi>10.1006/inco.2000.2870]
• 11: Kakade, S., Kearns, M., & Langford, J. (2003). Exploration in metric state spaces. Proceedings of the 20th International Conference on Machine Learning.
• 12: Kakade, S. M. (2003). On the sample complexity of reinforcement learning. Doctoral dissertation, Gatsby Computational Neuroscience Unit, University College London.
• 13: Michael J. Kearns , Daphne Koller, Efficient Reinforcement Learning in Factored MDPs, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.740-747, July 31-August 06, 1999
• 14: Michael Kearns , Satinder Singh, Near-Optimal Reinforcement Learning in Polynomial Time, Machine Learning, v.49 n.2-3, p.209-232, November-December 2002 [doi>10.1023/A:1017984413808]
• 15: Terran Lane , Carla E. Brodley, An Empirical Study of Two Approaches to Sequence Learning for Anomaly Detection, Machine Learning, v.51 n.1, p.73-107, April 2003 [doi>10.1023/A:1021830128811]
• 16: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 17: Strehl, A. L., Diuk, C., & Littman, M. L. (2007). Efficient structure learning in factored-state MDPs. Proceedings of the Twenty-Second National Conference on Artificial Intelligence (AAAI-07).
• 18: Strehl, A. L., & Littman, M. L. (2008). Online linear regression and its application to model-based reinforcement learning. Advances in Neural Information Processing Systems 20.
• 19: Alexander L. Strehl , Chris Mesterharm , Michael L. Littman , Haym Hirsh, Experience-efficient learning in associative bandit problems, Proceedings of the 23rd international conference on Machine learning, p.889-896, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143956]
• 20: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 21: Gary M. Weiss , Ye Tian, Maximizing classifier utility when training data is costly, ACM SIGKDD Explorations Newsletter, v.8 n.2, p.31-38, December 2006 [doi>10.1145/1233321.1233325]

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.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory