Online feature elicitation in interactive optimization

ABSTRACT

Most models of utility elicitation in decision support and interactive optimization assume a predefined set of "catalog" features over which user preferences are expressed. However, users may differ in the features over which they are most comfortable expressing their preferences. In this work we consider the problem of feature elicitation: a user's utility function is expressed using features whose definitions (in terms of "catalog" features) are unknown. We cast this as a problem of concept learning, but whose goal is to identify only enough about the concept to enable a good decision to be recommended. We describe computational procedures for identifying optimal alternatives w.r.t. minimax regret in the presence of concept uncertainty; and describe several heuristic query strategies that focus on reduction of relevant concept uncertainty.

REFERENCES

• 1: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 2: Avrim Blum , Jeffrey Jackson , Tuomas Sandholm , Martin Zinkevich, Preference Elicitation and Query Learning, The Journal of Machine Learning Research, 5, p.649-667, 12/1/2004
• 3: Craig Boutilier , Relu Patrascu , Pascal Poupart , Dale Schuurmans, Constraint-based optimization and utility elicitation using the minimax decision criterion, Artificial Intelligence, v.170 n.8, p.686-713, June 2006 [doi>10.1016/j.artint.2006.02.003]
• 4: Braziunas, D., & Boutilier, C. (2007). Minimax regret-based elicitation of generalized additive utilities. Proc. 23rd Conf. on Uncertainty in AI (UAI-07) (pp. 25--32). Vancouver.
• 5: David Cohn , Les Atlas , Richard Ladner, Improving Generalization with Active Learning, Machine Learning, v.15 n.2, p.201-221, May 1994 [doi>10.1023/A:1022673506211]
• 6: Dasgupta, S., Hsu, D., & Monteleoni, C. (2008). A general agnostic active learning algorithm. Advances in Neural Information Processing Systems 20 (pp. 353--360). Cambridge, MA: MIT Press.
• 7: Fishburn, P. C. (1967). Interdependence and additivity in multivariate, unidimensional expected utility theory. International Economic Review, 8, 335--342.
• 8: Yoav Freund , H. Sebastian Seung , Eli Shamir , Naftali Tishby, Selective Sampling Using the Query by Committee Algorithm, Machine Learning, v.28 n.2-3, p.133-168, Aug./Sept. 1997 [doi>10.1023/A:1007330508534]
• 9: D. Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework, Artificial Intelligence, v.36 n.2, p.177-221, September 1988 [doi>10.1016/0004-3702(88)90002-1]
• 10: Lisa Hellerstein , Krishnan Pillaipakkamnatt , Vijay Raghavan , Dawn Wilkins, How many queries are needed to learn?, Journal of the ACM (JACM), v.43 n.5, p.840-862, Sept. 1996 [doi>10.1145/234752.234755]
• 11: Hirsh, H. (1992). Polynomial-time learning with version spaces. Proc. 10th National Conf. on AI (AAAI-92) (pp. 117--122). San Jose.
• 12: Mitchell, T. M. (1977). Version spaces: A candidate elimination approach to rule learning. Proc. 5th Intl. Joint Conf. on AI (IJCAI-77) (pp. 305--310). Cambridge.
• 13: Salo, A., & Häämäläinen, R. P. (2001). Preference ratios in multiattribute evaluation (PRIME)--elicitation and decision procedures under incomplete information. IEEE Trans. on Sys., Man and Cyber., 31, 533--545.
• 14: Savage, L. J. (1954). The foundations of statistics. New York: Wiley.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

Additional Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Uncertainty, "fuzzy," and probabilistic reasoning
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory