- Michael Kearns, Umesh Vazirani, "Introduction to Computational Learning Theory," The MIT Press, 1994.
- (recommended) Richard Durbin, Sean Eddy, Anders Krogh, Graeme Michison, "Biological Sequence Analysis," Cambridge University Press, 1999.

- Exams: 40%
- Assignments and Projects: 60%

- Online learning: perceptrons, WINNOW and weighted majority.
- Exact learning: deterministic finite automata (DFA) and beyond.
- Negative results: combinatorial arguments, complexity theory, and cryptography.
- Hidden Markov models: Viterbi's algorithm.
- Decision graph learning: decision lists and trees.
- PAC learning: VC dimension and Occam's razor. Geometric concepts.
- Boosting: AdaBoost and others.

Tuesday | Thursday |
---|---|

01/09/07 | 01/11/07: Introduction; Learning models; Examples |

01/16/07: Online model; Disjunction/Halfspaces | 01/18/07: Perceptron/WINNOW; Weighted Majority; Experts |

01/23/07: Exact model; DFA; Angluin's algorithm | 01/25/07: Exact model; DFA; other algorithms |

01/30/07: PAC model; Chernoff bounds; Rivest's DL algorithm | 02/01/07: Occam's razor |

02/06/07: Lower bounds; VC dimension and fingerprints | 02/08/07: Lower bounds; cryptography and complexity |

02/13/07: short break | 02/15/07: Boosting; AdaBoost |

02/20/07: More boosting; C4.5 | 02/22/07: DNF: Verbeugt's algorithm; Greedy |

02/27/07: DNF; Harmonic Sieve | 03/01/07: HMMs; Viterbi's algorithm |

03/06/07: More HMMs; Applications | 03/08/07: Learning with noise; XOR problem |

03/13/07: SQ model | 03/15/07: Reinforcement learning |

03/20/07: break | 03/22/07: break |

03/27/07 | 03/29/07 |

04/03/07 | 04/05/07 |

04/10/07 | 04/12/07 |

04/17/07 | 04/19/07 |

04/24/07 | 04/26/07 |

- Dana Angluin, "Learning Regular Sets from Queries and Counterexamples," Information and Computation 75, 87-106 (1987).
- Nick Littlestone, "Learning Quickly When Irrelevant Attributes Abound: A New Linear-threshold Algorithm," Machine Learning 2, 285-318 (1988).
- Michael J. Kearns and Leslie G. Valiant, "Cryptographic Limitations on Learning Boolean Formulae and Finite Automata," Journal of the ACM 41, 67-95 (1994).
- Avrim Blum and Ronald L. Rivest, "Training a 3-Node Neural Network is NP-Complete," Proc. of the 1988 Workshop in Computational Learning Theory, 9-18 (1988).
- Karsten Verbeurgt, "Learning DNF Under the Uniform Distribution in Quasi-Polynomial Time," Proc. 3rd Annual Workshop on Computational Learning Theory (COLT 1990), 314-326 (1990).
- Ronald L. Rivest, "Learning Decision Lists," Machine Learning 2, 229-246 (1987).
- Avrim Blum, "Rank-r decision trees are a subclass of r-decision lists," Information Processing Letters 42, 183-185 (1992).
- Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred Warmuth, "Occam's Razor," Information Processing Letters 24, 377-380 (1987).
- Nader H. Bshouty, "A subexponential exact learning algorithm for DNF using equivalence queries," Information Processing Letter 59, 37-39 (1996).
- Yoav Freund and Robert E. Schapire, "A Decision-Theoretic Generalizations of On-Line Learning and an Application to Boosting," Journal of Computer and System Sciences 55, 119-139 (1997).
- Avrim Blum, "Empirical support for Winnow and Weighted-Majority based algorithms: results on a calendar scheduling domain," Proc. 12th International Conference in Machine Learning (ICML 1995), 64-72 (1995).
- Michael J. Kearns and Satinder Singh," Near-Optimal Reinforcement Learning in Polynomial Time," Proc. 15th International Conference on Machine Learning (ICML 1998), 260-268 (1998).
- Chinda Wongngamnit and Dana Angluin, "Robot localization in a grid," Information Processing Letter 77, 261-267 (2001).
- Yoav Freund and Robert Schapire, "Adaptive game playing using multiplicative weights," Games and Economic Behavior 29, 79-103 (1999).
- Robert Schapire and Yoram Singer, "BostTexter: A Boosting-based System for Text Categorization," Machine Learning 39, 135-168 (2000).