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:

S. Dasgupta, Coarse sample complexity bounds for active learning. Advances in 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.
M.-F. Balcan, A. Beygelzimer, J. Langford, Agnostic active learning. ICML 2006.
S. Fine, Y. Mansour, Active Sampling for Multiple Output Identification. COLT 2006.
See also the NIPS 2005 Workshop on Foundations of Active Learning.

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:

H. Daume, J. Langford, D. Marcu, Search-based Structured Prediction.
B. Taskar, V. Chatalbashev, D. Koller and C. Guestrin. Learning Structured Prediction Models: A Large Margin Approach. ICML 2005.
There has also been work on more traditional k-way classification. See, e.g.,
- T. Zhang, Statistical analysis of some multi-category large margin classification methods, JMLR, 2004.
- A. Tewari and P. Bartlett, On the consistency of multiclass classification methods, COLT, 2005.
- J. Langford and A. Beygelzimer, Sensitive Error Correcting Output Codes, COLT 2005.

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:

A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. Agnostically Learning Halfspaces. FOCS 2005. (Link points to Adam Kalai's home page. Scroll down for paper & ppt)
W. S. Lee, P. L. Bartlett, and R. C. Williamson. Efficient agnostic learning of neural networks with bounded fan-in. IEEE Trans Info Theory, 1996.

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.

J. Jackson, An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. Journal of Computer and System Sciences 55(3), 1997. N. Bshouty, J. Jackson, and T. Tamon, More Efficient PAC-learning of DNF with Membership Queries Under the Uniform Distribution. Proceedings of the 12th Annual Workshop on Computational Learning Theory, 1999.
These papers show how to use membership queries to learn DNF formulas respect to the uniform distribution. Combination of fourier analysis with boosting and a clever analysis of the distributions produced.
N. Bshouty and E. Mossel and R. O'Donnell and R. Servedio, Learning DNF from Random Walks. 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003, pp. 189-198.
Improves on above results by replacing membership queries with passive observation of a random walk on {0,1}^n. That is, you get to observe a sequence of examples where each new example is a random neighbor of the previous one.

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:

V. Feldman, P. Gopalan, S. Khot, A. Ponnuswami. New Results for Learning Noisy Parities and Halfspaces, FOCS 2006.
V. Feldman, Optimal Hardness Results for Maximizing Agreements with Monomials, CCC 2006.
V. Guruswami and P. Raghavendra, Hardness of learning halfspaces with noise. FOCS 2006.

Relationship between convex cost functions and discrete loss: These papers look at relationships between different kinds of objective functions for learning problems.

P.L. Bartlett, M.I. Jordan, J.D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138-156, 2006.
T.Zhang, Statistical behavior and consistency of classification methods based on convex risk minimization.
I.Steinwart, How to compare different loss functions and their risks.

Extension of experts setting to "bandit" or other limited-information settings. Extensions to "internal regret". See. e.g.,

P. Auer, N. Cesa-Bianchi, Y. Freund, R. Schapire, The Nonstochastic Multiarmed Bandit Problem, SIAM J. Comput. 32(1): 48-77 (2002).
V. Dani and T. Hayes, Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. SODA 2006.
A. Blum and Y. Mansour, From External to Internal Regret. COLT 2005.

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:

D. McAllester, Simplified PAC-BAyesian Margin Bounds. COLT 2003.
A. Ambroladze, E. Parrado-Hernandez, J. Shawe-Taylor, Tighter PAC-Bayes Bounds. NIPS 2006.
J. Langford and D. McAllester. Computable Shell Decomposition Bounds. COLT 2000.

Learning in Graphical Models (Bayes Nets)

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