Learning when to stop thinking and do something!

ABSTRACT

An anytime algorithm is capable of returning a response to the given task at essentially any time; typically the quality of the response improves as the time increases. Here, we consider the challenge of learning when we should terminate such algorithms on each of a sequence of iid tasks, to optimize the expected average reward per unit time. We provide a system for addressing this challenge, which combines the global optimizer Cross-Entropy method with local gradient ascent. This paper theoretically investigates how far the estimated gradient is from the true gradient, then empirically demonstrates that this system is effective by applying it to a toy problem, as well as on a real-world face detection task.

REFERENCES

• 1: Baxter, J., & Bartlett, P. (2001). Infinite-horizon policy-gradient estimation. Journal of Artificial Intelligence Research, 15, 319--350.
• 2: Bradski, G., & Kaehler, A. (2008). Learning Open CV: Computer vision with the Open CV library. O'Reilly Press.
• 3: Evan Greensmith , Peter L. Bartlett , Jonathan Baxter, Variance Reduction Techniques for Gradient Estimates in Reinforcement Learning, The Journal of Machine Learning Research, 5, p.1471-1530, 12/1/2004
• 4: Russell Greiner , Adam J. Grove , Dan Roth, Learning cost-sensitive active classifiers, Artificial Intelligence, v.139 n.2, p.137-174, August 2002 [doi>10.1016/S0004-3702(02)00209-6]
• 5: Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58, 13--30.
• 6: Lienhart, R., Kuranov, A., & Pisarevsky, V. (2003). Empirical analysis of detection cascades of boosted classifiers for rapid object detection. DAGM'03, 25th Pattern Recognition Symposium (pp. 297--304).
• 7: Volodymyr Mnih , Csaba Szepesvári , Jean-Yves Audibert, Empirical Bernstein stopping, Proceedings of the 25th international conference on Machine learning, p.672-679, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390241]
• 8: Rubinstein, R. Y., & Kroese, D. P. (2004). The crossentropy method. Information Science and Statistics. Springer.
• 9: Russell, S., & Subramanian, D. (1995). Provably bounded-optimal agents. Journal of Artificial Intelligence Research, 2, 575--609.
• 10: Shiryaev, A. (2007). Optimal stopping rules. Springer.
• 11: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 12: Turney, P. (2000). Types of cost in inductive concept learning. Workshop on Cost-Sensitive Learning (International Conference on Machine Learning).
• 13: Viola, P., & Jones, M. (2001). Rapid object detection using a boosted cascade of simple features. Computer Vision and Pattern Recognition (pp. 511--518).
• 14: Wald, A., & Wolfowitz, J. (1948). Optimum character of the sequential probability ratio test. Annals of Mathematical Statistics, 19, 326--339.
• 15: Ronald J. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning, v.8 n.3-4, p.229-256, May 1992 [doi>10.1007/BF00992696]
• 16: Zilberstein, S. (1996). Using anytime algorithms in intelligent systems. AI magazine, 17, 73--83.

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
          Subjects: Gradient methods; Global optimization

  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