15-859(B) Projects and Presentations

Here is some more information on what is expected, and some ideas to get you started.

Presentations:

These should be done in groups of 2. You will read one or more papers and produce two things: a class presentation, and a 5-page class handout on the topic. You can have one person do the presentation and one person do the handout, or split both 50/50. The topic should be chosen in consultation with the instructor.

Projects:

These can be done individually or in groups of 2. A project might involve conducting an experiment or thinking about a theoretical problem, or trying to relate two problems. The end result should be a 5-10 page report, and if you wish, a 5-10 minute presentation.

Presentation Ideas

Algorithms

• Support vector machines, kernel-based algorithms. (The latest issue of Machine Learning is a special issue on this topic. I have it in my office).
• Membership-query algorithms such as
  • Jackson's fourier-based DNF algorithm (original paper, more recent improvement)
  • Bshouty's decision tree algorithm.
• Online learning algorithms:
  • switching experts (fancier versions of the tracking-a-moving-target problem on hwk2). E.g., recent paper of Bousquet and Warmuth.
  • Use of upper confidence bounds for online learning. E.g., Peter Auer's paper in FOCS'2000.
  • Bandit problems (where you only see the result of the expert that you chose). E.g., see Rob Schapire's page.
  • On-line learning and Bregman divergences. The top couple entries on this page are some tutorials by Manfred Warmuth.
• Boosting-related topics
  • FOCS'99 paper "Boosting and hard-core sets" [Klivans, Servedio]. Relates boosting to roughly contrapositive notion in cryptography.
  • COLT'01 paper "Agnostic Boosting" [Ben-David, Long, Mansour]
• Maximum entropy learning (If I don't do it first)

• Margins and luckiness functions. (Similar to SVM topic, but focusing on sample size argument). Here is a good paper by Shawe-Taylor, Bartlett, Williamson, and Anthony. Also you can look at Peter Bartlett's home page.
• A random projection viewpoint on margin bounds: see Arriaga & Vempala, "An algorithmic theory of learning: Robust Concepts and Random Projection", FOCS'99.
• PAC-Bayes bounds, related approaches
• Analysis of leave-one-out cross-validation. E.g., "Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation" by Kearns and Ron (see Michael Kearns's home page.) Or, some really nice older papers by Luc Devroye (see refs in Kearns-Ron paper).

• Relating machine learning and statistics viewpoints

Project Ideas

• do an experiment, or
• try to simplify the results, or
• try to improve/extend the results in some way, see what happens if you modify the model, etc.

• You could experiment with learning algorithms based on random projection, as suggested by the above Arriaga-Vempala paper. I see that some experiments of a related sort were done by Sanjoy DasGupta (best student paper at UAI2000).
• Experiment with applying machine learning to a topic that's unusual for machine learning. E.g., Helmbold et al. use a "switching experts" algorithm to predict disk idle times for conserving energy on laptops.
• Read two papers coming from different communities that seem related and try to relate them.
• Or come up with your own idea. Make up your own problem and work on it.