15-859(B) Ideas for Projects

One of the course requirements is to do a small project, which you may do individually or in a group of 2. A project might involve conducting an experiment or thinking about a theoretical problem, or trying to relate two problems. It could even just be reading 2-3 research papers and explaining how they relate. The end result should be a 5-10 page report, and a 5-10 minute presentation. Here are a few ideas for possible topics for projects. You might also want to take a look at recent COLT proceedings.

Project Ideas

Active learning: The idea of much of the work on this topic is to try to reduce the 1/epsilon term in the number of labeled examples needed to get error epsilon down to log(1/epsilon), by allowing the algorithm to choose which examples in the dataset to have labeled. Sometimes you can do this and sometimes you can't. The theory is still not that fully developed. Some recent papers: Structured Prediction: This looks at problems where instead of making a binary "positive"/"negative" classification (or even a k-way classification), you instead have a much more complex output space. E.g., say you want to parse an English sentence, or output its translation into a different language. Here are a couple papers: Efficient agnostic learning: there are not a lot of efficient algorithms for agnostic learning (finding the approximately best h in H, when data is not necessarily consistent), but here are a couple results, including one interesting algorithm using fourier techniques: Algorithms for learning DNF formulas in various models: There is no known efficient algorithm for learning DNF in the standard PAC model, but there has been interesting work getting positive results in other models. Learning kernel functions: See, e.g., N. Srebro and S. Ben-David, Learning Bounds for Support Vector Machines with Learned Kernels, 19th Annual Conference on Learning Theory (COLT), 2006. Here is an earlier paper on the topic.

Computational hardness results: Some recent papers:

Relationship between convex cost functions and discrete loss: These papers look at relationships between different kinds of objective functions for learning problems. Extension of experts setting to "bandit" or other limited-information settings. Extensions to "internal regret". See. e.g.,

Learning in Markov Decision Processes: See Michael Kearns's home page and Yishay Mansour's home page for a number of good papers. Also Sham Kakade's thesis.

PAC-Bayes bounds, shell-bounds, other methods of obtaining confidence bounds. Some papers:

Learning in Graphical Models (Bayes Nets)

Last modified: Fri Mar 9 21:21:27 EST 2007