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.

Related Publications

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 patrick.w.langley@gmail.com