Conference proceeding
Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs
ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), v 29, pp 1578-1586
01 Jan 2016
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We define and study the problem of predicting the solution to a linear program (LP) given only partial information about its objective and constraints. This generalizes the problem of learning to predict the purchasing behavior of a rational agent who has an unknown objective function, that has been studied under the name "Learning from Revealed Preferences". We give mistake bound learning algorithms in two settings: in the first, the objective of the LP is known to the learner but there is an arbitrary, fixed set of constraints which are unknown. Each example is defined by an additional known constraint and the goal of the learner is to predict the optimal solution of the LP given the union of the known and unknown constraints. This models the problem of predicting the behavior of a rational agent whose goals are known, but whose resources are unknown. In the second setting, the objective of the LP is unknown, and changing in a controlled way. The constraints of the LP may also change every day, but are known. An example is given by a set of constraints and partial information about the objective, and the task of the learner is again to predict the optimal solution of the partially known LP.
Metrics
8 Record Views
Details
- Title
- Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs
- Creators
- Shahin Jabbari - Univ Penn, Philadelphia, PA 19104 USARyan Rogers - Univ Penn, Philadelphia, PA 19104 USAAaron Roth - Univ Penn, Philadelphia, PA 19104 USAZhiwei Steven Wu - Univ Penn, Philadelphia, PA 19104 USA
- Contributors
- D D Lee (Editor)M Sugiyama (Editor)U V Luxburg (Editor)I Guyon (Editor)R Garnett (Editor)
- Publication Details
- ADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS 29 (NIPS 2016), v 29, pp 1578-1586
- Series
- Advances in Neural Information Processing Systems
- Publisher
- Neural Information Processing Systems (Nips)
- Number of pages
- 9
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Web of Science ID
- WOS:000458973701007
- Other Identifier
- 991021868088504721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Artificial Intelligence