15-854 Presentations and Projects

Here is a list of presentation and project topics that come to mind. It is not an exhaustive list: if somthing else strikes you, come talk with me. Roughly, a presentation is expected to require reading a research paper and then discussing it in class. A project might involve programming up and testing some algorithms, or it could be something larger and more open-ended. In any case, come talk with me before committing your presentation or project. If you do a project, then you would be expected to give a short (5-15 min) presentation of it in class.

Ideas for presentations:

Expansion on "sample complexity" and VC-dimension discussion. For example, maximizing the "margin", probabilistic concepts, or distribution-specific or bayesian refinements.
MDPs, Q-learning.
the EM algorithm and hidden Markov Models
Other topics in on-line learning
Further analysis of decision tree or neural net learning.

Ideas for projects:

Set up a program to repeatedly play some 2-player zero sum game against a human opponent. Try out several algorithms, including weighted-majority with "sharing".
Implement a multi-layer version of winnow. (make negated copies of inputs so effectively have negative weights too, and then can use threshold of 0). How to train...?

Ideas for presentations, more specifically:

Note: I've attempted to choose the most readable papers I could find on each topic. But, it's probably worth your while looking up other papers on the same topic (e.g., see the references in these papers) in case there is another that's better.

Relations between decision tree algorithms and boosting/weak-learning:
- Kearns-Mansour: On the Boosting Ability of Top-Down Decision Tree Learning Algorithms , in STOC '96, pp.459-468.
- See also Dietterich-Kearns-Mansour: Applying the Weak Learning Framework to Understand and Improve C4.5 in ICML '96, pp. 96-104.
Models/algorithms for learning probabilistic functions:
- Kearns-Schapire: Efficient Distribution-free Learning of Probabilistic Concepts Journal of Computer and System Sciences 48(3), pp. 464-497.
Online portfolio selection:
- Blum-Kalai: Universal Portfolios With and Without Transaction Costs , in COLT '97, pp. 309--313.
- Cover: "Universal portfolios", Math. Finance 1(1):1-29, January 1991.
- Helmbold-Schapire-Singer-Warmuth: On-line portfolio selection using multiplicative updates , in ICML '96.
Extensions to VC-dimension: bounds that depend on the "amount" of separation acheived (aka the "margin"):
- Bartlett: The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network, in NIPS '96.
- Schapire-Freund-Bartlett-Lee: Boosting the margin: A new explanation for the effectiveness of voting methods, in ICML '97.
Extensions to VC-dimension: bounds that depend on the input distribution and "error shells":
- Haussler-Kearns-Seung-Tishby: Rigorous Learning Curve Bounds from Statistical Mechanics, Machine Learning Vol. 25, pp. 195-236, 1997.
Extensions to VC-dimension: bounds based on metric entropy:
- Haussler-Opper: Metric Entropy and Minimax Risk in Classification , Lecture Notes in Computer Science: Studies in Logic and Computer Science Vol. 1261, 212-235 (1997)
Exploring an unknown environment:
- Awerbuch-Betke-Rivest-Singh: Piecemeal Graph Exploration by a Mobile Robot, in COLT '95. See also notes from Ron Rivest's class.

Avrim Blum

Last modified: Wed Mar 11 16:05:22 EST 1998