Learning from Implicit Feedback Through Online Experimentation

NSF-Project IIS-0905467

2009-2013

Cornell University
Department of Computer Science

Project Goals

The goal of the project is to harness the information contained in users' interactions with information systems (e.g. query reformulations, clicks, dwell time) to train those systems to better serve their users' information needs. The key challenge lies in properly interpreting this implicit feedback and collecting it in a way that provides valid training data. Moving beyond existing passive data collection methods, the project draws on multi-armed bandit algorithms, experiment design, and machine learning to actively collect implicit feedback data. Developing these interactive experimentation methods goes hand-in-hand with developing machine learning algorithms that can use the resulting training data, and empirical evaluations that validate the models of user behavior assumed by the algorithms.

This research will improve retrieval quality for important applications like intranet search and desktop search. Additionally, the project will provide an operational full-text search engine for the Physics E-Print ArXiv and potentially other digital libraries, thus forming a test-bed for the research while also providing a valuable service and dissemination tool to the academic community beyond computer science. Including an REU Supplement, the project provides interesting and motivating research opportunities to undergrads and international exchange students, and the PI's will include relevant material into the undergraduate and graduate curriculum. Finally, the project will provide easy-to-use software that enables research and teaching, via this project website.

People

Related Publications

[Raman/Joachims/13a] K. Raman, T. Joachims, Learning Socially Optimal Information Systems from Egoistic Users, European Conference on Machine Learning (ECML), 2013.
[Raman/etal/13a] K. Raman, T. Joachims, P. Shivaswamy, T. Schnabel, Stable Coactive Learning via Perturbation, International Conference on Machine Learning (ICML), 2013.
[Sipos/Joachims/13a] R. Sipos, T. Joachims, Generating Comparative Summaries from Reviews, short paper, Conference on Information and Knowledge Management (CIKM), 2013.
[Shivaswamy/Joachims/12a] P. Shivaswamy, T. Joachims, Online Structured Prediction via Coactive Learning, International Conference on Machine Learning (ICML), 2012.
[Badanidiyuru/etal/12c] Ashwinkumar Badanidiyuru, Robert Kleinberg, Yaron Singer, "Learning on a Budget: Posted Price Mechanisms for Online Procurement" , Proceedings of the 13th ACM Conference on Electronic Commerce (EC), Valencia, Spain, June 4-8, 2012.
[Kleinberg/etal/12a] Robert Kleinberg, S. Matthew Weinberg, "Matroid Prophet Inequalities" , Proceedings of the 44th Symposium on Theory of Computing Conference (STOC), New York, NY, USA, May 19-22, 2012.
[Badanidiyuru/etal/12b] Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan, Tim Roughgarden, "Sketching Valuation Functions" , Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Kyoto, Japan, January 17-19, 2012.
[Badanidiyuru/etal/12a] Badanidiyuru, Ashwinkumar; Kleinberg, Robert; Lee, Hooyeon, "Approximating Low-Dimensional Coverage Problems" , Symposium on Computational Geometry, ACM, Chapel Hill, NC, USA, June 17-20, 2012.
[Raman/etal/12a] K. Raman, P. Shivaswamy, T. Joachims, Online Learning to Diversify from Implicit Feedback, ACM Conference on Knowledge Discovery and Data Mining (KDD), 2012.
[PDF] [BibTeX]
[Chapelle/etal/12a] O. Chapelle, T. Joachims, F. Radlinski, Yisong Yue, Large-Scale Validation and Analysis of Interleaved Search Evaluation, ACM Transactions on Information Systems (TOIS), 30(1):6.1-6.41, 2012.
[PDF] [BibTeX]
[Shivaswamy/Joachims/12b] P. Shivaswamy, T. Joachims, Multi-armed Bandit Problems with History, Conference on Artificial Intelligence and Statistics (AISTATS), 2012.
[PDF] [BibTeX]
[Raman/etal/11a K. Raman, T. Joachims, P. Shivaswamy, Structured Learning of Two-Level Dynamic Rankings, Conference on Information and Knowledge Management (CIKM), 2011.
[PDF] [BibTeX]
[Kleinberg/etal/11b] Kleinberg, Robert; Ligett, Katrina; Piliouras, Georgios; Tardos, Eva, "Beyond the Nash Equilibrium Barrier" , Innovations in Computer Science (ICS), Tsinghua University, Beijing, China, January 7-9, 2011, pp. 125-140, 2011.
[Kleinberg/etal/11a] Kleinberg, R; Piliouras, G; Tardos, E, "Load balancing without regret in the bulletin board model", DISTRIBUTED COMPUTING, vol. 24, p. 21, 2011.
[Yue/Joachims/11a] Yisong Yue, T. Joachims, Beat the Mean Bandit, International Conference on Machine Learning (ICML), 2011.
[PDF] [BibTeX
[Yue/Joachims/11a] C. Brandt, T. Joachims, Yisong Yue, J. Bank, Dynamic Ranked Retrieval, ACM International Conference on Web Search and Data Mining (WSDM), 2011.
[PDF] [BibTeX
[Shivaswamy/Joachims/11a] P. Shivaswamy, T. Joachims, Multi-Armed Bandit Problems with History, The Learning Workshop, 2011.
[PDF] [BibTeX
[Xu/etal/10a] Z. Xu, K. Kersting, T. Joachims, Fast Active Exploration for Link-Based Preference Learning using Gaussian Processes, Proceedings of the European Conference on Machine Learning (ECML), 2010.
[PDF] [BibTeX
[Kleinberg/etal/10a] Kleinberg, Robert; Slivkins, Aleksandrs, "Sharp Dichotomies for Regret Minimization in Metric Spaces" , Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Austin, Texas, January 17-19, 2010.
[Yue/etal/10a] Yisong Yue, Yue Gao, Olivier Chapelle, Ya Zhang, and T. Joachims, Learning More Powerful Statistical Tests for Click-Based Retrieval Evaluation, Proceedings of the ACM Conference on Research and Development in Information Retrieval (SIGIR), 2010.
[PDF] [BibTeX
[Yue/Joachims/09a] Yisong Yue and T. Joachims, Interactively Optimizing Information Retrieval Systems as a Dueling Bandits Problem, Proceedings of the International Conference on Machine Learning (ICML), 2009.
[PDF] [BibTeX
[Yue/etal/09a] Yisong Yue and J. Broder and R. Kleinberg and T. Joachims, The K-armed Dueling Bandits Problem, Proceedings of the Conference on Learning Theory (COLT), 2009.
[PDF] [BibTeX
[Radlinski/etal/08b] F. Radlinski, M. Kurup, T. Joachims, How Does Clickthrough Data Reflect Retrieval Quality?, Proceedings of the ACM Conference on Information and Knowledge Management (CIKM), 2008.
[PDF] [BibTeX]
[Yue/Joachims/08a] Yisong Yue and T. Joachims, Predicting Diverse Subsets Using Structural SVMs, Proceedings of the International Conference on Machine Learning (ICML), 2008.
[PDF] [BibTeX] [Software]
[Radlinski/etal/08a] F. Radlinski and R. Kleinberg and T. Joachims, Learning Diverse Rankings with Multi-Armed Bandits, Proceedings of the International Conference on Machine Learning (ICML), 2008.
[PDF] [BibTeX
[Radlinski/Joachims/07a] F. Radlinski, T. Joachims, Active Exploration for Learning Rankings from Clickthrough Data, Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), ACM, 2007.
[PDF] [BibTeX]
[Joachims/Radlinski/07a] T. Joachims, F. Radlinski, Search Engines that Learn from Implicit Feedback, IEEE Computer, Vol. 40, No. 8,August, 2007.
[IEEE Digital Library] [BibTeX] [Software]

Related Software

Related Courses

Related Presentations

Acknowledgement and Disclaimer

This material is based upon work supported by the National Science Foundation under Award IIS-0905467. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF).

Last change: 12/20/2013