The second in-class examination will take place on Tuesday, December
3, during the usual class time, **in McConnell Room 103**. It is
open-book, open-notes and will cover lectures 12-23. In particular,
the list of topics is as follows:

- Instance-based learning
- Bias and variance of learning algorithms
- Ensembles of classifiers; bagging and boosting
- Support Vector Machines for classification and regression
- Markov Decision Processes. Formulating optimization problems as MDPs
- Dynamic programming and Monte Carlo methods
- Temporal difference learning and eligibility traces
- Using function approximators with reinforcement learning
- K-means clustering
- Expectation maximization algorithm. Gaussian mixture models

The first in-class examination will take place on Tuesday, October 29, during the usual class time. It is open-book, open-notes and will cover lectures 1-11. In particular, the list of topics is as follows:

- Formulating learning problems
- Kinds of learning algorithms
- Version spaces and candidate elimination
- Representation and search bias. Think of what these are for all algorithms we studied!
- Basic probabilities. Bayes theorem.
- MAP and ML hypotheses
- Naive Bayes, Bayes optimal classifier and Gibbs classifier
- Basic of information theory: information, entropy, conditional entropy, information gain
- Decision trees: what they are, how they are constructed
- Overfitting in general; ways in which overfitting appears in all learning algorithms discussed; ways of avoiding overfitting for all the algorithms discussed
- Minimum description length principle: what it is, how it is applied in the learning algorithms discussed
- Gradient descent principle; applications of gradient decent in the learning algorithms studied
- Linear regression
- Perceptrons and sigmoid neurons
- Feed-forward artificial neural networks; backpropagation algorithm and variations
- For all learning algorithms, think of advantages, disadvantages, potential applications.
- Empirical evaluation of learning algorithms: experiment design, cross-validation, confidence intervals on the error
- Comparing learning algorithms; t-tests
- PAC-learning: basic setup, sample complexity vs. computational complexity; computing sample complexity for different kinds of hypotheses
- VC dimension: definition; computing VC dimension for different classes of hypotheses.
- Sample complexity in terms of VC dimension

- Show a Boolean function (or draw a picture) corresponding to a decision tree
- Show a Boolean function (or draw a picture) corresponding to a perceptron
- Construct a decision tree (or perceptron) to represent a given function
- Given a hypothesis class, say how many hypotheses are in the class. Compute its VC dimension. Give a PAC-style bound on the number of examples needed to learn with some precision and confidence
- Apply gradient descent to a learning problem.
- Given an application domain, specify how it would be implemented as a learning problem (what will the data look like, what learning algorithm you would use and why)
- Basic probability and information theory questions
- Experimental design questions

Prof. Doina PRECUP Last modified: Wed Nov 27 22:13:04 EST 2002