Preference elicitation for interface optimization

ABSTRACT

Decision-theoretic optimization is becoming a popular tool in the user interface community, but creating accurate cost (or utility) functions has become a bottleneck --- in most cases the numerous parameters of these functions are chosen manually, which is a tedious and error-prone process. This paper describes ARNAULD, a general interactive tool for eliciting user preferences concerning concrete outcomes and using this feedback to automatically learn a factored cost function. We empirically evaluate our machine learning algorithm and two automatic query generation approaches and report on an informal user study.

REFERENCES

• 1: Maneesh Agrawala , Chris Stolte, Rendering effective route maps: improving usability through generalization, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.241-249, August 2001 [doi>10.1145/383259.383286]
• 2: A. Arnauld. The Art of Thinking. The Bobbs-Merrill Company, inc., 1662.
• 3: Greg J. Badros , Alan Borning , Peter J. Stuckey, The Cassowary linear arithmetic constraint solving algorithm, ACM Transactions on Computer-Human Interaction (TOCHI), v.8 n.4, p.267-306, December 2001 [doi>10.1145/504704.504705]
• 4: Craig Boutilier, A POMDP formulation of preference elicitation problems, Eighteenth national conference on Artificial intelligence, p.239-246, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 5: C. Boutilier, R. Patrascu, P. Poupart, and D. Schuurmans. Constraint-based optimization with the minimax decision criterion. In International Conference on Principles and Practice of Constraint Programming, 2003.
• 6: Christopher J. C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, v.2 n.2, p.121-167, June 1998 [doi>10.1023/A:1009715923555]
• 7: Urszula Chajewska , Daphne Koller, Utilities as Random Variables: Density Estimation and Structure Discovery, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.63-71, June 30-July 03, 2000
• 8: Urszula Chajewska , Daphne Koller , Dirk Ormoneit, Learning an Agent's Utility Function by Observing Behavior, Proceedings of the Eighteenth International Conference on Machine Learning, p.35-42, June 28-July 01, 2001
• 9: Urszula Chajewska , Daphne Koller , Ronald Parr, Making Rational Decisions Using Adaptive Utility Elicitation, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.363-369, July 30-August 03, 2000
• 10: James Fogarty , Jodi Forlizzi , Scott E. Hudson, Aesthetic information collages: generating decorative displays that contain information, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502369]
• 11: James Fogarty , Scott E. Hudson, GADGET: a toolkit for optimization-based approaches to interface and display generation, Proceedings of the 16th annual ACM symposium on User interface software and technology, p.125-134, November 02-05, 2003, Vancouver, Canada [doi>10.1145/964696.964710]
• 12: K. Gajos, D. Christianson, R. Hoffmann, T. Shaked, K. Henning, J. J. Long, and D. S. Weld. Fast and robust interface generation for ubiquitous applications. In Proceedings of Ubicomp'05, Tokyo, Japan, 2005.
• 13: Krzysztof Gajos , Daniel S. Weld, SUPPLE: automatically generating user interfaces, Proceedings of the 9th international conference on Intelligent user interface, January 13-16, 2004, Funchal, Madeira, Portugal [doi>10.1145/964442.964461]
• 14: Melinda T. Gervasio , Michael D. Moffitt , Martha E. Pollack , Joseph M. Taylor , Tomas E. Uribe, Active preference learning for personalized calendar scheduling assistance, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040857]
• 15: D. Heckerman , E. Horvitz , B. Middleton, An Approximate Nonmyopic Computation for Value of Information, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.3, p.292-298, March 1993 [doi>10.1109/34.204912]
• 16: Eric Horvitz, Principles of mixed-initiative user interfaces, Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, p.159-166, May 15-20, 1999, Pittsburgh, Pennsylvania, United States [doi>10.1145/302979.303030]
• 17: Eric Horvitz , Johnson Apacible, Learning and reasoning about interruption, Proceedings of the 5th international conference on Multimodal interfaces, November 05-07, 2003, Vancouver, British Columbia, Canada [doi>10.1145/958432.958440]
• 18: E. Horvitz, A. Jacobs, and D. Hovel. Attention-sensitive alerting. In UAI-99, San Francisco, CA, 1999.
• 19: Eric Horvitz , Paul Koch , Johnson Apacible, BusyBody: creating and fielding personalized models of the cost of interruption, Proceedings of the 2004 ACM conference on Computer supported cooperative work, November 06-10, 2004, Chicago, Illinois, USA [doi>10.1145/1031607.1031690]
• 20: R. L. Keeney and H. Raiffa. Decisions with Multiple Objectives: Preferences and Value Tradeoffs. John Wiley and Sons, 1976. Republished in 1993 by Cambridge University Press.
• 21: G. Linden, S. Hanks, and N. Lesh. Interactive assessment of user preference models: The automated travel assistant. In User Modeling '97, 1997.
• 22: Thomas P. Minka, Expectation Propagation for approximate Bayesian inference, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.362-369, August 02-05, 2001
• 23: P. Pu, B. Faltings, and M. Torrens. User-involved preference elicitation. In IJCAI'03 Workshop on Configuration, Acapulco, Mexico, 2003.
• 24: Greg Schohn , David Cohn, Less is More: Active Learning with Support Vector Machines, Proceedings of the Seventeenth International Conference on Machine Learning, p.839-846, June 29-July 02, 2000
• 25: Sybil Shearin , Henry Lieberman, Intelligent profiling by example, Proceedings of the 6th international conference on Intelligent user interfaces, p.145-151, January 14-17, 2001, Santa Fe, New Mexico, United States [doi>10.1145/359784.360325]
• 26: Simon Tong , Daphne Koller, Support vector machine active learning with applications to text classification, The Journal of Machine Learning Research, 2, p.45-66, 3/1/2002
• 27: Michelle X. Zhou , Vikram Aggarwal, An optimization-based approach to dynamic data content selection in intelligent multimedia interfaces, Proceedings of the 17th annual ACM symposium on User interface software and technology, October 24-27, 2004, Santa Fe, NM, USA [doi>10.1145/1029632.1029673]
• 28: Michelle X. Zhou , Zhen Wen , Vikram Aggarwal, A graph-matching approach to dynamic media allocation in intelligent multimedia interfaces, Proceedings of the 10th international conference on Intelligent user interfaces, January 10-13, 2005, San Diego, California, USA [doi>10.1145/1040830.1040861]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems

General Terms:
Algorithms, Human Factors

Keywords:
active learning, optimization, utility elicitation