Preference elicitation with subjective features

ABSTRACT

Utility or preference elicitation is a critical component in many recommender and decision support systems. However, most frameworks for elicitation assume a predefined set of features (e.g., as derived from catalog descriptions) over which user preferences are expressed. Just as user preferences vary considerably, so too can the features over which they are most comfortable expressing these preferences. In this work, we consider preference elicitation in the presence of subjective or user-defined features. We treat the problem of learning a user's feature definition as one of concept learning, but whose goal is to learn only enough about the concept definition to enable a good decision to be made. This is complicated by the fact that user preferences are unknown. We describe computational procedures for identifying optimal alternatives w.r.t minimax regret in the presence of both utility and concept uncertainty; and develop several heuristic query strategies that focus on reduction of relevant concept and utility uncertainty. Computational experiments verify the efficacy of these strategies.

REFERENCES

• 1: D. Angluin. Queries and concept learning. Mach. Learn., 2(4):319--342, 1987.
• 2: C. Boutilier, R. Patrascu, P. Poupart, and D. Schuurmans. Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence, 170(8--9):686--713, 2006.
• 3: C. Boutilier, K. Regan, and P. Viappiani. Online feature elicitation in interactive optimization. The 26th International Conference on Machine Learning (ICML-09), pp.73--80, Montreal, 2009.
• 4: R. Burke. Interactive critiquing for catalog navigation in e-commerce. Artif. Intel. Rev., 18(3-4):245--267, 2002.
• 5: D. Haussler. Learning conjunctive concepts in structural domains. Machine Learning, 4:7--40, 1989.
• 6: H. Hirsh. Polynomial-time learning with version spaces. 10th Natl. Conf. on Artif. Intel. (AAAI-92), San Jose, pp.117--122, 1992.
• 7: J. A. Konstan, B. N. Miller, D. Maltz, J. L. Herlocker, Lee R. Gordon, and John Riedl. rouplens: Applying collaborative filtering to usenet news. Comm. ACM, 40(3):77--87, 1997.
• 8: T. M. Mitchell. Version spaces: A candidate elimination approach to rule learning. 5th Intl. Joint Conf. on Artif. Intel. (IJCAI-77), pp.305--310, Cambridge, 1977.
• 9: Leonard J. Savage. The Foundations of Statistics. Wiley, New York, 1954.
• 10: P. Viappiani, B. Faltings, and P. Pu. Preference-based search using example-critiquing with suggestions. Journal of Artificial Intelligence Research, 27:465--503, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

General Terms:
Algorithms, Human Factors

Keywords:
concept learning, minimax regret, preference elicitation, recommender systems, version space