Average-Case Analyses of Induction and Planning
My initial interests in computational learning focused on its
psychological and experimental aspects, but I watched with
interest as the community of COLT (computational learning
theory) researchers developed in parallel. Although the PAC
treatments that dominated the COLT literature were a clear
advance over earlier analyses of learning in the limit, most
still emphasized worst-case scenarios.
Following the lead of Michael Pazzai, I started to explore
average-case analyses of specific induction algorithms. Wayne
Iba played an important role in much of this work, which led
to the publication of average-case analyses for the induction
of decision stumps (one-level decision trees), the naive Bayesian
classifier, and the nearest neighbor algorithm. My continuing
interest in resource-limited problem solving and execution led
to similar analyses in these areas.
Most recently, drawing on work by Mostefa Golea, our analyses
have used normal distributions to approximate binomials. This
approximation makes them much more tractable, computationally,
with little loss in predictive accuracy. Our reanalysis of naive
Bayes takes advantage of this new approach.
Langley, P., & Sage, S. (1999).
Tractable average-case analysis of naive Bayesian classifiers.
Proceedings of the Sixteenth International Conference on Machine
Learning (pp. 220-228). Bled, Slovenia: Morgan Kaufmann.
Langley, P., Iba, W., & Shrager, J. (1994).
Reactive and automatic behavior in plan execution.
Proceedings of the Second International Conference on AI Planning
Systems (pp. 299-304). Chicago: AAAI Press.
Langley, P., & Iba, W. (1993).
Average-case analysis of a nearest neighbor algorithm.
Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence (pp. 889-894). Chambery, France.
Langley, P., Iba, W., & Thompson, K. (1992).
An analysis of Bayesian classifiers.
Proceedings of the Tenth National Conference on Artificial Intelligence
(pp. 223-228). San Jose, CA: AAAI Press.
Langley, P. (1992).
Systematic and nonsystematic search strategies.
Proceedings of the First International Conference on AI Planning
Systems (pp. 145-152). College Park, MD: Morgan Kaufmann.
Iba, W., & Langley, P. (1992).
Induction of one-level decision trees.
Proceedings of the Ninth International Conference on Machine
Learning (pp. 233-240). Aberdeen, Scotland: Morgan Kaufmann.
Thompson, K., Langley, P., & Iba, W. F. (1991).
Using background knowledge in concept formation.
Proceedings of the Eighth International Workshop on Machine
Learning (pp. 554-558). Evanston, IL: Morgan Kaufmann.
For more information, send electronic mail to