John Langford

Phone: 914-948-1871
E-mail: jl@hunch.net
Web: http://hunch.net/~jl/

Research Interests

I want to solve machine learning. In a solved form, machine learning is automatic, robust, scalable, and easily used for many problems. In the last several years, we have made great progress in this direction.

Education

Employment History

Yahoo! Research, New York, NY June 2006-present Senior Research Scientist

TTI-Chicago, Chicago, IL September 2003 - May 2006 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

Activities

Blog: Machine Learning (Theory) at http://hunch.net
Tutorial: Scaling up Machine Learning at KDD 2011.
Tutorial: Learning through Exploration Video at ICML 2010 and KDD 2010.
Workshop: Organizer Cores, Clusters, and Clouds at NIPS 2010.
Tutorial: Active Learning Video at ICML 2009.
Tutorial: Reductions in Machine Learning Video at
Workshop: Organizer Principles of Learning Problem Design at NIPS 2007
Tutorial: Learning Reductions IJCAI2005 and MLSS 2005
School: Organizer Machine Learning Summer School Chicago 2005
Workshop: Organizer (Ab)Use of Bounds NIPS 2004
Workshop: Organizer Machine Learning Reductions TTI-Chicago, 2003
Tutorial: Practical Prediction Theory for Classification ICML2003 and MLSS 2005

Service

Program Chair: ICML 2012
New York ML Symposium co-organizer: 2008 2009 2010 2011
Area chair/Senior PC: ICML 2004 NIPS 2006 ICML 2007 ICML 2009 ICML 2010 KDD 2010 NIPS 2010 ICML 2011
Program committee: ICML 2003, 2005 & 2008, SODA 2008, AAAI 2005, AAAI 2007ALT 2004, UAI 2007 AIStat 2005 COLT 2008 COLT 2009 and others
Reviewing: NIPS 2001, 2002, 2003, 2005 & 2007, AAAI 2002, MLJ, JMLR, JAIR, JCSS, TCS, JACM, and others

Mentoring

I have worked with many students over time. In all cases, I try to learn something from them as well.
  1. Jacob Abernethy (Postdoc UPenn)
  2. Alekh Agarwal (phd student UC Berkeley)
  3. Luis von Ahn (*) (Professor Carnegie Mellon)
  4. Nina Balcan (Professor Georgia Tech)
  5. Arindam Banerjee (*)(Professor UMinnesota)
  6. Carl Burch (*) (Professor Hendrix U)
  7. Hal Daume (*) (Professor U Maryland)
  8. Varsha Dani (Research Professor U New Mexico)
  9. Nick Hopper (*) (Professor UMinnesota)
  10. Daniel Hsu (*) (Postdoc, Microsoft Research)
  11. Nikos Karampatziakis (phd student Cornell)
  12. Matti Kääriäinen (*) (Nokia)
  13. Sham Kakade (*) (Microsoft Research)
  14. Adam Kalai (*) (Microsoft Research)
  15. Nicolas Lambert (Professor Stanford)
  16. Lihong Li (Yahoo! Research)
  17. Joseph O'Sullivan (ex-Google :-)
  18. Pradeep Ravikumar (Professor UTAustin)
  19. Ruslan Salakhutdinov (Professor UToronto)
  20. Matthias Seeger (*) (Professor EPFL)
  21. Vin de Silva (*) (Professor Pomona)
  22. Alex Strehl (*) (Facebook)
  23. Jennifer Wortman Vaughan (Professor UCLA)
  24. Vandi Verma (*) (JPL)
  25. Yevgeniy Vorobeychik (Sandia)
  26. Eric Weiwiora
  27. Bianca Zadrozny (*) (Professor UFF)
  28. Martin Zinkevich (Y! Research)
(*) = on work which became part of their thesis

Select Publications

  1. Ron Bekkerman, Misha Bilenko, and John Langford (Editors) Scaling Up Machine Learning, Cambridge University Press, 2011.
  2. Miroslav Dudík, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang: Efficient Optimal Learning for Contextual Bandits, UAI 2011
  3. Alina Beygelzimer, Sham Kakade, and John Langford Cover Trees for Nearest Neighbor, ICML-2006 [Pat Goldberg Best Paper Award in Computer Science, Electrical Engineering, and Mathematics]
  4. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003
  5. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site

Papers, forthcoming

  1. Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, John Langford: A Reliable Effective Terascale Linear Learning System, CoRR abs/1110.4198 (2011)
  2. John Langford, Preston McAfee, Kishore Papineni, Sergei Vasilvitskii, Bidding Bandits: Bounded Budget Exploration in Auctions

All Publications, appended

Research Programs

Much of my work can be organized into coherent programs.
  1. Creating and using tight sample complexity bounds for evaluation and machine learning algorithm design. This was my thesis work, and a small program of work by others has grown out of it.
  2. Learning Reductions. We transform complex learning problems into simple ones and then use good algorithms for the simple ones to solve the complex problems. Here we designed the method of analysis as well as the algorithms, and again a small program of work by others is growing out of it.
  3. Scalable learning. The goal here is to scale up learning algorithms in all ways. We have addressed scaling in the number of parameters, the number of examples, and the number of labels.
  4. Active Learning. We proved that active learning was possible in the same noisy settings as supervised learning and eventually refined the algorithm to efficiently use any supervised algorithm as an oracle.
  5. Contextual Bandits. In many real-life situations, we only get feedback about choices taken rather than choices not taken, as is assumed in normal supervised learning. This requires a ground-up rethink of what machine learning means. We have developed evaluators (equivalent to test sets in supervised learning), optmized the use of exploration information, and developed exponentially faster algorithms.
  6. Vowpal Wabbit is an open source machine learning system which encodes some of the above. It is currently the most scalable public (generalized) linear learning algorithm by a wide margin.

Patents

  1. US8108323 Distributed Personal Spam Filtering
  2. US 2011/0110231 VOLUNTARY ADMISSION CONTROL FOR TRAFFIC YIELD MANAGEMENT
  3. 8006157 Resource-light method and apparatus for outlier detection
  4. 8032535 Personalized web search ranking
  5. US 2012/0016642 CONTEXTUAL-BANDIT APPROACH TO PERSONALIZED NEWS ARTICLE RECOMMENDATION
  6. US 2010/0057546 SYSTEM AND METHOD FOR ONLINE ADVERTISING USING USER SOCIAL INFORMATION
  7. US 2010/0010891 METHODS FOR ADVERTISEMENT SLATE SELECTION
  8. US 2009/0265227 Methods for Advertisement Display Policy Exploration
  9. US 2005/0091524 Confidential fraud detection system and method
  10. US 2010/0131496 PREDICTIVE INDEXING FOR FAST SEARCH

References

Avrim Blum (Phd advisor) avrim+@cs.cmu.edu
Michael Kearns mkearns@cis.upenn.edu
Robert Schapire schapire@cs.princeton.edu
Sanjoy Dasgupta dasgupta@cs.ucsd.edu
Preston McAfee preston@mcafee.cc
Prabhakar Raghavan pragh@acm.org
Citizenship
  • U.S.
Awards

Publications, All

  1. Alekh Agarwal, Miroslav Dudík, Satyen Kale, John Langford, Robert E. Schapire: Contextual Bandit Learning with Predictable Rewards, AIStats 2012.
  2. Alina Beygelzimer, John Langford, David Pennock: Learning Performance of Prediction Markets with Kelly Bettors, AAMAS 2012
  3. Ron Bekkerman, Misha Bilenko, and John Langford (Editors) Scaling Up Machine Learning, Cambridge University Press, 2011.
  4. Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, John Langford: A Reliable Effective Terascale Linear Learning System, CoRR abs/1110.4198 (2011)
  5. Daniel Hsu, Nikos Karampatziakis, John Langford, Alexander J. Smola: Parallel Online Learning, in Scaling Up Machine Learning, Cambridge University Press, 2011.
  6. Miroslav Dudík, John Langford, Lihong Li: Doubly Robust Policy Evaluation and Learning, ICML 2011
  7. Miroslav Dudík, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, Tong Zhang: Efficient Optimal Learning for Contextual Bandits, UAI 2011
  8. Nikos Karampatziakis, John Langford: Online Importance Weight Aware Updates, UAI 2011
  9. John Langford, Lihong Li, Preston McAfee, Kishore Papineni: Cloud Control: Voluntary Admission Control for Intranet Traffic Management, Information Systems and e-Business Management
  10. Lihong Li, Wei Chu, John Langford, Xuanhui Wang: Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms, WSDM 2011 [Best Paper Award]
  11. Alina Beygelzimer, John Langford, Lihong Li, Lev Reyzin, Robert E. Schapire: Contextual Bandit Algorithms with Supervised Learning Guarantees, Journal of Machine Learning Research, Proceedings Track 15 (AISTATS 2011): 19-26 (2011) [Notable Paper Award]
  12. Alina Beygelzimer, Daniel Hsu, John Langford, Tong Zhang: Agnostic Active Learning Without Constraints, NIPS 2010
  13. Alexander L. Strehl, John Langford, Lihong Li, Sham Kakade: Learning from Logged Implicit Exploration Data, NIPS 2010
  14. Lihong Li, Wei Chu, John Langford, Robert E. Schapire: A contextual-bandit approach to personalized news article recommendation, WWW 2010
  15. John Langford: Efficient Exploration in Reinforcement Learning. Encyclopedia of Machine Learning 2010: 309-311
  16. John Langford Open Problem: Robust Efficient Conditional Probability Estimation, COLT 2010.
  17. John Langford, Lihong Li, Yevgeniy Vorobeychik, Jennifer Wortman: Maintaining Equilibria During Exploration in Sponsored Search Auctions, Algorithmica 58(4): 990-1021 (2010). Conference version in WINE 2007.
  18. Alina Beygelzimer, John Langford, Pradeep D. Ravikumar: Error-Correcting Tournaments, ALT 2009
  19. Kilian Q. Weinberger, Anirban Dasgupta, John Langford, Alexander J. Smola, Josh Attenberg: Feature hashing for large scale multitask learning, ICML 2009
  20. Alina Beygelzimer, Sanjoy Dasgupta, John Langford: Importance weighted active learning, ICML 2009
  21. John Langford, Ruslan Salakhutdinov, Tong Zhang: Learning nonlinear dynamic models, ICML 2009
  22. Alina Beygelzimer, John Langford: The offset tree for learning with partial labels, KDD 2009
  23. Martin Zinkevich, Alexander J. Smola, John Langford: Slow Learners are Fast, NIPS 2009
  24. Daniel Hsu, Sham Kakade, John Langford, Tong Zhang: Multi-Label Prediction via Compressed Sensing, NIPS 2009
  25. Alina Beygelzimer, John Langford, Yury Lifshits, Gregory B. Sorkin, Alexander L. Strehl: Conditional Probability Tree Estimation Analysis and Algorithms, UAI 2009
  26. Nicholas J. Hopper, John Langford, and Luis von Ahn: Provably Secure Steganography, Crypto 2002. Journal version: IEEE Transactions on Computers 58(5): 662-676 (2009)
  27. Maria-Florina Balcan, Alina Beygelzimer, John Langford: Agnostic active learning, ICML 2006. Journal version: JCSS 75(1): 78-89 (2009)
  28. Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alexander J. Smola, S. V. N. Vishwanathan: Hash Kernels for Structured Data, Journal of Machine Learning Research 10: 2615-2637 (2009)
  29. Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alexander J. Smola, Alexander L. Strehl, Vishy Vishwanathan: Hash Kernels, Journal of Machine Learning Research - Proceedings Track 5 (AISTATS 2009): 496-503 (2009)
  30. John Langford, Lihong Li, Tong Zhang: Sparse Online Learning via Truncated Gradient, NIPS 2008. Journal version: Journal of Machine Learning Research 10: 777-801 (2009)
  31. Hal Daumé III, John Langford, Daniel Marcu: Search-based structured prediction, Machine Learning 75(3): 297-325 (2009)
  32. Nicolas S. Lambert, John Langford, Jennifer Wortman, Yiling Chen, Daniel M. Reeves, Yoav Shoham, David M. Pennock: Self-financed wagering mechanisms for forecasting, EC 2008. [Winner of an Outstanding Paper Award]
  33. John Langford, Alexander L. Strehl, Jennifer Wortman: Exploration scavenging, ICML 2008
  34. Sharad Goel, John Langford, Alexander L. Strehl: Predictive Indexing for Fast Search, NIPS 2008
  35. Maria-Florina Balcan, Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, Gregory B. Sorkin: Robust reductions from ranking to classification, COLT 2007. Journal version: Machine Learning 72(1-2): 139-153 (2008)
  36. John Langford, Tong Zhang: The Epoch-Greedy Algorithm for Multi-armed Bandits with Side Information. NIPS 2007
  37. Alexander L. Strehl, Lihong Li, Eric Wiewiora, John Langford, Michael L. Littman: PAC model-free reinforcement learning, ICML 2006
  38. Alina Beygelzimer, Sham Kakade, and John Langford Cover Trees for Nearest Neighbor, ICML-2006 [Pat Goldberg Best Paper Award in Computer Science, Electrical Engineering, and Mathematics]
  39. Naoki Abe, Bianca Zadrozny, John Langford: Outlier detection by active learning, KDD 2006
  40. John Langford, Roberto Oliveira, Bianca Zadrozny: Predicting Conditional Quantiles via Reduction to Classification, UAI 2006
  41. Jacob Abernethy, John Langford, Manfred Warmuth Continuous Experts and the Binning Algorithm, COLT 2006
  42. John Langford and Bianca Zadrozny Relating Reinforcement Learning Performance to Classification Performance ICML 2005
  43. Matti Kääriäinen and John Langford A Comparison of Tight Generalization Bounds ICML 2005
  44. Matti Kääriäinen, John Langford: A comparison of tight generalization error bounds. ICML 2005
  45. Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford, and Bianca Zadrozny Error limiting reductions between classification tasks ICML 2005
  46. Alina Beygelzimer, John Langford, and Bianca Zadrozny Weighted One Against All AAAI 2005
  47. John Langford and Alina Beygelzimer Sensitive Error Correcting Output Codes COLT 2005
  48. Luis von Ahn, Nick Hopper, and John Langford Covert Two-Party Computation STOC 2005
  49. John Langford and Bianca Zadrozny Estimating Class Membership Probabilities Using Classifier Learners AISTAT 2005
  50. John Langford Tutorial on Practical Prediction Theory for Classification JMLR 2005
  51. Arindam Banerjee and John Langford An Objective Evaluation Criterion for Clustering KDD 2004
  52. Naoki Abe, Bianca Zadrozny, and John Langford An Iterative Method for Multi-class Cost-sensitive Learning KDD 2004
  53. Peter Grünwald and John Langford Suboptimal Behavior of Bayes and MDL in Classification under Misspecification COLT 2004. Journal version: Machine Learning 66(2-3): 119-149 (2007)
  54. Luis von Ahn, Manuel Blum, Nick Hopper and John Langford CAPTCHA: Using Hard AI Problems for Security Eurocrypt 2003
  55. Luis von Ahn, Manuel Blum and John Langford: Telling humans and computers apart automatically. Commun. ACM 47(2): 56-60 (2004)
  56. Sham Kakade, Michael Kearns, John Langford, and Luis Ortiz, Correlated Equilibria in Graphical Games, ACM EC 2003.
  57. Bianca Zadrozny, John Langford, and Naoki Abe Cost Sensitive Learning by Cost-Proportionate Example Weighting ICDM 2003
  58. Avrim Blum and John Langford PAC-MDL Bounds COLT 2003
  59. Sham Kakade, Michael Kearns, and John Langford Exploration in Metric State Spaces ICML2003
  60. John Langford and John Shawe-Taylor PAC-Bayes and Margins. NIPS-2002
  61. Sham Kakade, John Langford Approximately Optimal Approximate Reinforcement Learning ICML-2002
  62. John Langford: Combining Trainig Set and Test Set Bounds. ICML 2002: 331-338
  63. John Langford, Martin Zinkevich, Sham Kakade Competitive Analysis of the Explore/Exploit Tradeoff ICML-2002
  64. John Langford Generic Quantum Block Compression (at xxx.lanl.gov and Phys. rev. A.) May 2002
  65. Sebastian Thrun, John Langford, and Vandi Verma, Risk Sensitive Particle Filters, NIPS2001.
  66. John Langford and Rich Caruana, (Not) Bounding the True Error NIPS2001
  67. John Langford, Matthias Seeger, and Nimrod Megiddo. An Improved Predictive Accuracy Bound for Averaging Classifiers ICML2001
  68. Josh Tenenbaum, Vin de Silva and John Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction . Science 290, pages 2319-2323, 2000 isomap site
  69. John Langford and David McAllester. Computable Shell Decomposition Bounds. COLT2000 and JMLR 5: 529-547 (2004)
  70. Joseph O'Sullivan, John Langford, Rich Caruana and Avrim Blum. FeatureBoost: A Meta-Learning Algorithm that Improves Model Robustness. ICML2000
  71. John Langford and Avrim Blum 1999. Microchoice Bounds and Self Bounding learning algorithms. COLT99 also, Machine Learning Journal 51(2): 165-179 (2003)
  72. Avrim Blum, Adam Kalai, and John Langford 1999. Beating the Holdout: Bounds for KFold and Progressive Cross-Validation. COLT99
  73. S. Thrun, John Langford, and Dieter Fox 1999. Monte Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially Observable Stochastic Proecesses. ICML99
  74. Avrim Blum and John Langford: Probabilistic Planning in the Graphplan Framework, ECP 1999.
  75. Avrim Blum, Carl Burch, and John Langford: On Learning Monotone Boolean Functions, FOCS 1998.