Unit 10: Computational Learning Theory and Statistical Learning

Commentary

This unit introduces both computational learning theory and statistical learning methods. The basic question computational learning theory wants to answer is: How can we know that the hypothesis h is close to the target function f, if we don't know what f is? Computational learning theory analyses the sample complexity and computational complexity of inductive learning, which can guide the learning process to a balance between proper samples and fair correctness. Statistical learning, the main topic of this unit, covers a number of learning methods that range from the simple calculation of averages to the construction of complex models, such as Bayesian networks and neural networks. This unit discusses several major methods in current use, such as Bayesian learning, maximum a posteriori (MAP) and maximum likelihood (ML) learning, naive Bayes learning, EM algorithm, instance-based learning, and neural network learning.

Unit Purpose

When you complete this unit, you will be able to

• Define computational learning theory and PAC-learning.
• Discuss Bayesian learning and other simplified methods, such as MAP, MDL, ML, and naive Bayes learning methods.
• Describe the maximum-likelihood parameter learning in both discrete and continuous models, and the Bayesian parameter learning.
• Discuss the EM algorithm, which can perform learning with hidden variables.
• Explain instance-based learning, including nearest-neighbour models and kernel models.
• Discuss neural networks and their learning algorithms.
• Explain the principle of kernel machines.

Section 1: Computational learning theory
Section 2: Bayesian learning and EM algorithm
Section 3: Instance-based learning
Section 4: Neural networks
Section 5: Kernel machines

Readings

Flach, P. A. (2001). On the state of the art in machine learning: A personal review. Artificial Intelligence, 131(1-2), 199-222.

Supplemental Unit Readings

Unit 10: Computational Learning Theory and Statistical Learning

Books:

Kearns, M., and Vazirani, U. (1994). An introduction to computational learning theory. Cambridge, MA: MIT Press.

Bishop, C. M. (2006). Pattern recognition and machine learning. Springer. ISBN 0-387-31073-8. (Refer primarily to the sections covering Graphical Models)

Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausible inference. San Mateo, CA: Morgan Kaufmann.

Activities

• Explore some applications in the fields with which you are most familiar to see how and why statistical learning methods are helpful. Report your findings in the online course conference.
• Explore open source software for statistical learning from the Web, and compare their usability. Report your findings to the course conference.