Interactive Learning | This research project is to address learning in interactive situations. It includes active learning (where the algorithm chooses which examples to label), contextual bandits (which is similar, except less label information is returned), and online learning (where the label is revealed after each prediction). |
Learning Reductions |
The goal of this project is to learn the relationships between the learning problems common in the machine learning community. Typical statements are of the form "Ability to approximately solve problem A implies ability to approximately solve problem B" and typical algorithms are reductions/compilers/transformers from one problem to another. |
Nearest Neighbors |
The "Cover Tree" is a datastructure on which nearest neighbor (and similar) queries can be calculated. The algorithm relies upon only a metric, so it is applicable to noneuclidean spaces. |
Prediction Bounds |
The goal is gaining a fine understanding of how well a machine can learn to predict things. Typical statements are of the form "assuming samples are independently drawn from an unknown distribution, this classifier errs less than a 0.4 portion of the time". Algorithms optimize these bounds to find a classifier with a low guaranteed error rate. |
CAPTCHA |
The goal of the captcha project is to construct tests which a computer can generate and grade, but not pass.
These are simultaneously tightly specified challenges for AI research and useful to prevent robotic attacks on
resources. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003 .ps.gz, .pdf, .tex Luis von Ahn, Manuel Blum, and John Langford Telling Humans and Computers Apart (Automatically) CMU Tech Report .ps.gz, .pdf, .tex
|
Isomap |
This is an "unsupervised learning" algorithm. Given many points in some high (1000000) dimensional space, isomap
attempts to extract a low (1-10) dimensional manifold containing the points. If the high dimensional points are an
isometric embedding of a low dimensional manifold (and some niceness conditions apply) isomap is guaranteed to recoever
it. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, 2319-2323, 2000 isomap site a comment and response Mira Bernstein, Vin de Silva, John Langford and Josh Tenenbaum Graph approximations to geodesics on embedded manifolds Technical report 2000 |
Reinforcement Learning |
Reinforcement Learning is a formalization of the general AI problem. It is thus very general and capable of capturing many other machine learning problems. One of the fundamental problems arising is the "exploration/exploitation tradeoff". |
Steganography |
Encryption hides the content of a message. Steganography hides the existence of a message. Where and how is
steganography possible? Nick Hopper, John Langford, and Luis von Ahn Provably Secure Steganography Crypto 2002/CMU Tech report .ps.gz, .pdf, .tex (revised corrections .tex w.r.t. crypto submission) It turns out that anonmyous two-party computation is also possible. Luis von Ahn, Nick Hopper, and John Langford Covert Two-Party Computation STOC 2005 .ps.gz .pdf .tex |
Self-financed Prediction | How do you setup a mechanism for resolving bets on outcomes which is incentive compatible and self financing? Nicolas Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel Reeves, Yoav Shoham, and David Pennock Self-financed Wagering Mechanisms for Forecasting EC 2008. |
Incentive Compatible Exploration | Does the exploration required for learning a policy messup the incentives for ad auctions on the internet? Jennifer Wortman, Yevgeniy Vorobeychik, Lihong Li, and John Langford, Maintaining Equilibria During Exploration in Sponsored Search Auctions WINE 2007 (This is the longer journal draft.) |
Quantum Compression |
Any classical compression algorithm can be compiled into a quantum compression algorithm. John Langford Generic Quantum Block Compression (at xxx.lanl.gov and Phys. rev. A.) May 2002
|
Graphical Games |
With many players interacting locally, what correlated equilibria exist? Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz, Correlated Equilibria in Graphical Games, ACM EC 2003. .ps.gz, .pdf, .tex |
Probabilistic Graphplan |
Avrim Blum and John Langford Probabilistic Planning in the Graphplan Framework. ECP, 1999. |
Particle Filters |
Particle filters are a flexible nonparametric approximate Bayes posterior algorithm. Sebastian Thrun, John Langford, and Vandi Verma, Risk Sensitive Particle Filters, NIPS2001. .pdf, .ps.gz, .tex S. Thrun and John Langford, 1998. Monte Carlo Hidden Markov Models. Technical Report S. Thrun, John Langford, and Dieter Fox 1999. Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Proecesses. ICML99 |
FeatureBoost |
FeatureBoost is a boosting-style algorithm intendended to improve the robustness of a learned classifier
to perturbations in the underlying algorithm. Joseph O'Sullivan, John Langford, Rich Caruana and Avrim Blum. FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. ICML2000 .pdf, .ps.gz, .tex |