Research Projects/Papers

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.

Hashing Representations

We investigate the use of hashing functions to define feature indicies, allowing radical space savings and substantial speed improvements in learning algorithms.

Scaling Up Machine Learning

This is a book that I edited with Ron Bekkerman and Misha Bilenko that has many kinds of parallel learning algorithms. See also, our survey tutorial of the field.

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.


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


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


Shard Goel, Jake Hofman, John Langford, David M. Pennock, and Daniel M. Reeves. CentMail: Rate Limiting via Certified Micro-Donations at the WWW2009 developers track. This is about a scheme to eliminate spam by introducing microdonations to the email system.

Predictive Indexing

If you have a machine learned rule for ranking elements, how do you arrange objects so that not all of them need to be evaluated to produce a top-k ranking? This is a classic problem that we provide a new and experimentally effective twist on.
Sharad Goel, John Langford and Alexander Strehl, Predictive Indexing for Fast Search, NIPS 2008.


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

Online Learning for Information Markets

It turns out rational agents produce learning information markets.

Alina Beygelzimer, John Langford, and David Pennock, Learning Performance of Prediction Markets with Kelly Bettors, AAMAS 2012

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 also Algorithmica 2010. (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 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 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

Cloud Control

John Langford, Lihong Li, Preston McAfee, Kishore Papineni, Cloud control: Voluntary admission control for Intranet traffic management Information Systems and e-Business Management 2010.