John Langford

1427 E 60th Street
Chicago, IL 60637

Phone: 773-834-7493
E-mail: jl@hunch.net
Web: http://hunch.net/~jl/

Research Interests

I want to understand the robust and automatable methods for machine learning. This includes research in learning theory, reinforcement learning, planning, nearest neighbor algorithms, online learning, active learning, and other domains.

research statement, teaching statement

Education

Employment History

TTI-Chicago, Chicago, IL September 2003 - Present Research Assistant Professor

IBM, TJ Watson, Yorktown, NY September 2002 - August 2003 Herman Goldstine Fellow

University of Pennsylvania, Philadelphia, PA June 2002 - August 2002 Postdoc with Michael Kearns on game theory and reinforcement learning

ATnT Shannon Labs, Florham Park, NJ Summer 2001 "Summer Manager"
Learning theory and sample complexity bounds

IBM, Almaden, CA Summer 2000 Summer research with Shiv Vaithyanathan and Nimrod Megiddo
Hidden markov models for parsing and PAC Averaging bounds.

Activities

Tutorial: Learning Reductions IJCAI2005 and MLSS 2005
School: Organized Machine Learning Summer School Chicago 2005
Workshop: Organized (Ab)Use of Bounds NIPS 2004
Workshop: Organized Machine Learning Reductions TTI-Chicago, 2003
Tutorial: Practical Prediction Theory for Classification ICML2003 and MLSS 2005
Blog: Machine Learning (Theory) at http://hunch.net

Service

Area chair: ICML 2004
Program committee: ICML 2003 & 2005, AAAI 2005, ALT 2004, AIStat 2005
Reviewing: NIPS 2001, 2002, 2003 & 2005, AAAI 2002, MLJ, JMLR, JAIR and others
Treasurer of COLT

Publications (Conferences and Journals, multiple versions on same line)

  1. Alina Beygelzimer, Sham Kakade, and John Langford Cover Trees for Nearest Neighbor (forthcoming)
  2. Jacob Abernethy, John Langford, Manfred Warmuth The Binning Algorithm (forthcoming)
  3. Nina Balcan, Alina Beygelzimer, John Langford, Agnostic Active Learning (forthcoming)
  4. John Langford and Bianca Zadrozny Relating Reinforcement Learning Performance to Classification Performance ICML 2005
  5. Matti Kaariainen and John Langford A Comparison of Tight Generalization Bounds ICML 2005
  6. Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, and Bianca Zadrozny Reductions Between Classification Tasks ICML 2005
  7. Alina Beygelzimer, John Langford, and Bianca Zadrozny Weighted One Against All AAAI 2005
  8. John Langford and Alina Beygelzimer Sensitive Error Correcting Output Codes COLT 2005
  9. Luis von Ahn, Nick Hopper, and John Langford Covert Two-Party Computation STOC 2005
  10. John Langford and Bianca Zadrozny Estimating Class Membership Probabilities Using Classifier Learners AISTAT 2005
  11. John Langford Tutorial on Practical Prediction Theory for Classification JMLR 2005
  12. Arindam Banerjee and John Langford An Objective Evaluation Criterion for Clustering KDD 2004
  13. Naoki Abe, Bianca Zadrozny, and John Langford An Iterative Method for Multi-class Cost-sensitive Learning KDD 2004
  14. Peter Grunwald and John Langford Suboptimal Behavior of Bayes and MDL in Classification under Misspecification COLT 2004
  15. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003
  16. Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz, Correlated Equilibria in Graphical Games, ACM EC 2003.
  17. Bianca Zadrozny, John Langford, and Naoki Abe Cost Sensitive Learning by Cost-Proportionate Example Weighting ICDM 2003
  18. Avrim Blum and John Langford PAC-MDL Bounds COLT 2003
  19. Sham Kakade, Michael Kearns, and John Langford Exploration in Metric State Spaces ICML2003
  20. John Langford and John Shawe-Taylor PAC-Bayes and Margins. NIPS2002
  21. Sham Kakade, John Langford Approximately Optimal Approximate Reinforcement Learning ICML2002
  22. John Langford, Martin Zinkevich, Sham Kakade Competitive Analysis of the Explore/Exploit Tradeoff ICML2002
  23. John Langford Generic Quantum Block Compression (at xxx.lanl.gov and Phys. rev. A.) May 2002
  24. Nick Hopper, John Langford, and Luis von Ahn Provably Secure Steganography Crypto 2002
  25. Sebastian Thrun, John Langford, and Vandi Verma, Risk Sensitive Particle Filters, NIPS2001.
  26. John Langford and Rich Caruana, (Not) Bounding the True Error NIPS2001
  27. John Langford, Matthias Seeger, and Nimrod Megiddo. An Improved Predictive Accuracy Bound for Averaging Classifiers ICML2001
  28. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site
  29. John Langford and David McAllester. Computable Shell Decomposition Bounds. COLT2000 and JMLR
  30. Joseph O'Sullivan, John Langford, Rich Caruana and Avrim Blum. FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. ICML2000
  31. John Langford and Avrim Blum 1999. Microchoice Bounds and Self Bounding learning algorithms. COLT99 also, Machine Learning Journal
  32. Avrim Blum, Adam Kalai, and John Langford 1999. Beating the Holdout: Bounds for KFold and Progressive Cross-Validation. COLT99
  33. S. Thrun, John Langford, and Dieter Fox 1999. Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Proecesses. ICML99
  34. Avrim Blum and John Langford Probabilistic Planning in the Graphplan Framework. ECP 1999.
  35. Avrim Blum, Carl Burch, and John Langford, 1998. On Learning Monotone Boolean Functions FOCS 1998.
Skills
  • Algorithm development and analyses specializing in probabilistic algorithms and machine learning.
Algorithms
  • Machine learning including Neural Nets, Bayes Nets, Decision Trees, Hidden Markov Models and Support Vector Machines.
Citizenship
  • U.S.
Awards

References

Avrim Blum (Phd advisor) avrim+@cs.cmu.edu
Department of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213-3891
Michael Kearns mkearns@cis.upenn.edu
Department of Computer and Information Science
University of Pennsylvania
Moore School Building/GRW, Room 555
200 South 33rd Street
Philadelphia, PA 19104-6389
David McAllester mcallester@tti-c.org
TTI-Chicago
1427 E 60th street
Chicago, IL 60637
Naoki Abe nabe@us.ibm.com
(914) 945-3872
John Shawe-Taylor jst@ecs.soton.ac.uk
School of Electronics and Computer Science
University of Southampton
SO17 1BJ
United Kingdom
Manfred Warmuth manfred@cse.ucsc.edu
Department of Computer Science
Univ. of Calif.
E2 Building, MS: SOE3
1156 High Street
Santa Cruz, CA 95064