- 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.

- 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...?

**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*.

- Kearns-Schapire:
Efficient Distribution-free Learning of Probabilistic Concepts
**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.

- Haussler-Kearns-Seung-Tishby:
Rigorous Learning Curve Bounds from Statistical
Mechanics,
**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)

- Haussler-Opper:
Metric Entropy and Minimax Risk in Classification
,
**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