Active Learning

D. Cohn, L. Atlas, R. Ladner. Improving generalization with active learning, Machine Learning, 15(2), 1994.

S. Dasgupta, D.J. Hsu, and C. Monteleoni. A general agnostic active learning algorithm.
Neural Information Processing Systems (NIPS), 2007.

S. Dasgupta. Coarse sample complexity bounds for active learning.
Neural Information Processing Systems (NIPS), 2005.

S. Dasgupta, A. Kalai, and C. Monteleoni. Analysis of perceptron-based active learning.
Eighteenth Annual Conference on Learning Theory (COLT), 2005.

The algorithm A² described in the class:
M-F. Balcan, A. Beygelzimer, and J. Langford. Agnostic Active Learning, ICML 2006.
Video lecture on A².

Hanneke, S. (2007). Teaching Dimension and the Complexity of Active Learning. In proceedings of the 20^th Annual Conference on Learning Theory (COLT).

Hanneke, S. (2007). A Bound on the Label Complexity of Agnostic Active Learning. In proceedings of the 24^th Annual International Conference on Machine Learning (ICML).

M-F. Balcan, A. Broder, and T. Zhang. Margin Based Active Learning, COLT 2007.

Midterm statistics

Midterm statistics:

Average grade: 17.14
Median grade: 18
Min: 0
Max: 33
Total number of students: 53

Deergha will email the individual grades.

Midterm

The midterm is worth 25 points (25% of your final grade).

There will be three problems (8 points each) and three simple exercises (3 points each). Thus if you solve any two problems + all exercises, you will still get the maximum grade. If you do everything, you will get 8 bonus points.

The material covered in the following lectures will NOT be on the midterm:

1. Generalization bounds (the lecture before the midterm)
   
2. Reductions
3. Sanjoy's talk on projections, Gaussian scale mixtures, and the EM

One of the problems will be on the semantics of loss functions. You should be able to answer questions of the form: What loss function does the following quantity minimize? (See this post, for example.)

The other two problems will be on any two of the following algorithms:

1. Winnow
2. Halving
   
3. (Randomized) Weighted Majority
4. Perceptron

The exercises will cover the rest of the material.