Overview and Goals
A common fundamental problem of value of information (VOI) analysis arises in inference, learning and sequential decision-making when one is allowed to actively select, rather than passively observe, the input information. VOI provides a principled methodology that enables acquiring information in a way that optimally trades off the cost of information gathering with the expected benefit in some overall objective (e.g., classification accuracy or cumulative reward). For example, in Bayesian problem diagnosis VOI analysis aims at selecting observations (e.g. medical tests) that are most informative about the unknown variables (e.g., diseases we are trying to diagnose) while minimizing the cost of collecting the information. In sequential decision-making problems, VOI can provide a principled solution to the well-known "exploration versus exploitation" dilemma, so that one can optimally trade off the immediate cost of exploratory actions with expected improvement in future decisions and future reward. Yet another example is active learning, where the goal is to minimize the cost of observations (e.g., the number of labeled samples) while maximizing the learners objective function. Finally, selecting the most relevant subset of features in supervised learning is another example where VOI analysis can provide a principled solution.
Clearly, these areas differ in their choices of a particular objective function and the approaches to active exploration, but have a common goal of selecting explorative actions that maximize the VOI. In this workshop, we plan to bring together researchers from several fields concerned with VOI analysis and hope to ignite cross-fertilization between the areas. This could lead to major theoretical progress as well as practical impact in applications such as medical diagnosis, quality control in product design, IT systems management and troubleshooting, and DNA library screening, just to name a few.
New! Workshop
Program (in pdf)
Invited Talks
- Prof. Craig Boutilier (University of Toronto)
- Prof. Sanjoy Dasgupta (University of California, San Diego)
- Prof. Carlos Guestrin (Carnegie Mellon University)
- Prof. Michael Littman (Rutgers University)
- Prof. Dale Schuurmans (University of Alberta)
Suggested Topics
The list of possible topics includes (but is not limited to) the following:
- VOI analysis in probabilistic inference and decision theory
- Feature selection and attribute-efficient learning
- Active learning (query learning, selective sampling)
- Exploration-exploitation trade-off in reinforcement learning
- Adaptive versus non-adaptive testing designs
- Comparison of different action selection criteria and objective functions
- Applications of VOI in diagnosis, systems control and management, coding theory, computational biology, neural coding, etc.
Format
This is a one-day workshop. There will be several invited talks and tutorials (roughly 30-40 minutes each) and shorter contributed talks from researchers in industry and academia, as well as a panel discussion. We will hold a poster session if we receive a sufficient number of good submissions. The workshop is intended to be accessible to the broader NIPS community and to encourage communication between different fields.
Workshop Schedule: Saturday, December 10, 2005
- Morning session: 7:30am–10:30am
- 7:30am Introduction, Irina Rish
- 7:45am Value of Information in Interactive Optimization, Craig Boutilier
- 8:15am Nonmyopic Value of Information in Graphical Models, Carlos Guestrin
- 8:45am Break and Poster Setup
- 9:00am Models of Active Learning, Sanjoy Dasgupta
- 9:30am Poster Spotlights
- 10:20am Poster Session
- Afternoon session: 3:30pm–6:30pm
- 3:30pm PAC bounds on the exploration-exploitation tradeoff, Michael Littman
- 4:00pm Bayesian Sparse Sampling for On-line Reward Optimization, Dale Schuurmans
- 4:30pm Optimal Experimental Design Models of Naive Human Information Acquisition, Jonathan Nelson, Gary Cottrell, Flavia Filimon, and Terry Sejnowski
- 4:45pm coffee break
- 5:00pm Compressed Sensing and Active Learning, Rui Castro, Jarvis Haupt, and Robert Nowak
- 5:15pm Active Learning in POMDPs, Robin Jaulmes, Joelle Pineau, and Doina Precup
- 5:30pm When Ignorance is Bliss, Peter Grunwald and Joseph Halpern
- 5:45pm Concluding Discussion
Abstract of Invited Talks
- Speaker: Craig Boutilier, University of Toronto, Canada (7:45am)
Title: Value of Information in Interactive Optimization Abstract: Interactive optimization requires assessing a decision maker’s preferences (or an objective function) during the course of optimization (e.g., recommending a decision or sequence of decisions to the decision maker). When interactions costs such as time costs or cognitive burden are considered, the value of information contained in any interaction proposed by a decision-support system must be traded off against these costs. In this talk, I will describe a general framework for interactive optimization and decision support in which the role of value of information is central. This framework will reveal the the close ties concepts in reinforcement learning, exploration vs. exploitation, and revealed preference (or inverse RL).
- Speaker: Carlos Guestrin, Carnegie Mellon University (8:15am)
Title: Nonmyopic Value of Information in Graphical Models Abstract: In decision making under uncertainty, where one can choose among several expensive queries, it is a central issue to decide which variables to observe in order to achieve a most effective increase in expected utility. This problem has previously only been approached myopically, without any known performance guarantees. In this talk, I will present efficient nonmyopic algorithms for selecting an optimal subset of observations and for computing an optimal conditional plan for a class of graphical models containing Hidden Markov Models. I will also show how our methods can be used for interactive structured classification and for sensor scheduling in a Civil Engineering domain. Many graphical models tasks which can be efficiently solved for chains, can be generalized to polytrees. I will present surprising hardness results, showing that the optimization problems are wildly intractable (NPPP complete) even in the case of discrete polytrees. Addressing these theoretical limits, I will present efficient approximation algorithms for selecting informative subsets of variables. Our algorithms are applicable to a large class of graphical models, and provide a constant factor approximation guarantee of 1-1/e, which is provably the best constant factor achievable unless P = NP. I will sketch how our methods can be extended to optimal experimental design in Gaussian processes, and present extensive evaluation of our algorithms on several real-world data sets. The material presented in this talk is joint work with Andreas Krause.
- Speaker: Sanjoy Dasgupta, University of California, San Diego (9:00am)
Title: Models of Active Learning Abstract: I will give an overview of the various models of active learning that have been proposed, including generative models (such as Castelli-Cover), query by committee, learning from membership queries, and some recent developments. I will talk about the strengths and weaknesses of these models, the kinds of learning algorithms they motivate, and the theoretical results that have been shown.
Slides (ppt)
- Speaker: Michael Littman, Rutgers University (3:30pm)
Title: PAC bounds on the exploration-exploitation tradeoff Abstract: Paraphrasing Frost, a system cannot make two decisions and be one decision maker—it can only observe the effects of the actions it actually chooses to make. The resulting explorationexploitation tradeoff can be solved optimally only for the simplest decision-making scenarios, necessitating the development of weaker goals. The PAC framework has emerged as a viable alternative, in which the decision maker has a polynomial number of interactions to obtain near optimal reward with high probability. I will survey existing PAC results for k-armed bandit problems and Markov decision processes, as well as progress from my own group in solving related decision problems.
- Speaker: Dale Schuurmans, University of Alberta (4:00pm)
Title: [Bayesian Sparse Sampling for On-line Reward Optimization Abstract: I will discuss progress toward developing sparser “sparse sampling” techniques for approximating Bayes optimal decision making in reinforcement learning. Our approach combines sparse sampling with Bayesian exploration to achieve improved decision making while controlling computational cost. The idea is to grow a sparse lookahead tree, intelligently, by exploiting information in a Bayesian posterior—rather than enumerate action branches (standard sparse sampling) or compensating myopically (value of perfect information). The outcome is a flexible, practical technique for improving action selection in simple reinforcement learning scenarios. Joint work with Tao Wang, Dan Lizotte and Mike Bowling.
Slides (pdf)
Slides (ppt)
Contributed talks
- Optimal Experimental Design Models of Naive Human Information Acquisition, Jonathan Nelson, Gary Cottrell, Flavia Filimon, and Terry Sejnowski Slides (ppt)
- Compressed Sensing and Active Learning, Rui Castro, Jarvis Haupt, and Robert Nowak
- Active Learning in POMDPs, Robin Jaulmes, Joelle Pineau, and Doina Precup
- When Ignorance is Bliss, Peter Grunwald and Joseph Halpern Slides (ppt)
Posters
- Nonmyopic VOI with Near-Optimal Collection Cost, Andreas Krause, Carlos Guestrin, Anupam Gupta and Jon Kleinberg
- Efficient VOI for Graphical Models, Brigham Anderson and Andrew Moore
- Efficient Selection of Disambiguating Actions for Stereo Vision, Monika Schaeffer and Ronald Parr
- Mechanism Design via Machine Learning, Maria-Florina Balcan, Avrim Blum, Jason Hartline and Yishay Mansour
- Gaussian Process Regression for Optimization, Daniel Lizotte, TaoWang, Michael Bowling and Dale Schuurmans
- Active Learning under Arbitrary Distributions, Claire Monteleoni and Matti KĻaĻariĻanen
- Active Learning, Loss Function Convexity, and Support Vectors, Leon Bottou, Ronan Collobert, Seyda Ertekin and Jason Weston
- Using Value of Information to Learn and Classify under Hard Budgets, Russel Greiner
- Active Learning and Optimal Predictions, Susanne Still
- Efficient Test Selection in Active Diagnosis via Entropy Approximation, Alice Zheng, Irina Rish and Alina Beygelzimer
Submission Instructions
We invite submissions of extended abstracts (up to 2 pages, not including bibliography) for the short contributed talks and/or posters. The submission should present a high-level description of recent or ongoing work related to the topics above. We will explore the possibility of publishing papers based on invited and submitted talks in a special issue of an appropriate journal.
Email submissions to nips05workshop@watson.ibm.com as attachments in Postscript or PDF, no later than October 24, 2005.
Important Dates and Deadlines
* October 24, 2005: Deadline for the submission of extended abstracts (up to 2 pages not including bibliography)
* October 31, 2005: Notification of acceptance/rejection
Organizing Committee
Dr. Alina Beygelzimer
IBM T. J. Watson Research Center
19 Skyline Drive
Hawthorne, NY 10532, USA
Dr. Rajarshi Das
IBM T. J. Watson Research Center
19 Skyline Drive
Hawthorne, NY 10532, USA
http://www.research.ibm.com/people/r/rajarshi
Dr. Irina Rish (primary contact)
IBM T. J. Watson Research Center
19 Skyline Drive,
Hawthorne, NY 10532, USA
http://www.research.ibm.com/people/r/rish
Dr. Gerry Tesauro
IBM T. J. Watson Research Center
19 Skyline Drive,
Hawthorne, NY 10532, USA
Information
* NIPS 2005 Conference URL: NIPS 2005
* Workshop URL: Value of Information in Inference, Learning and Decision-Making
* Workshop Program: Workshop Program
* Workshop Email: nips05workshop@watson.ibm.com
Attached files: NIPS05workshopCFP.doc, NIPS05workshopCFP.pdf, ATT3SJBH.pdf, active-models.ppt, nips05-wkshp-Schuurmans.pdf, nips05-wkshp-Schuurmans.ppt, nelsonNips2005Voi.ppt, NIPS2005b.ppt
Last updated 5 Jan 2006