Section 1 : Computational learning theory
Commentary
Section Goals
- To introduce the concepts and basic principles of computational learning theory, and discuss probably approximately correct learning (PAC-learning) and learning decision tree methods.
Learning Objectives
Learning Objective 1
- Outline how computational learning theory analyses the sample complexity and computational complexity of inductive learning.
- Explain the ideas behind decision list learning, and discuss its associated algorithm.
- Explain the following concepts or terms:
- Probably approximately correct (PAC)
- PAC-learning
- Decision list
Objective Readings
Required readings:
Reading topics:
Computational Learning Theory (see Chapter 18.5 of AIMA3ed).
Supplemental Readings
Kearns, M., and Vazirani, U. (1994). An Introduction to computational learning theory. Cambridge, MA: MIT Press.
Gentile, C., and Bshouty, N. H. (eds.). (2008). Special issue on Learning Theory (COLT-2007). Machine Learning, 72(1-2), 1-153.
Objective Questions
- What is the dilemma we face regarding sample complexity of the hypothesis space, and how do we resolve it?
Objective Activities
- Explore the source code of decision list learning algorithm downloadable from the textbook's website:
