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