Qualitative decision making in adaptive presentation of structured information

ABSTRACT

We present a new approach for adaptive presentation of structured information, based on preference-based constrained optimization techniques rooted in qualitative decision-theory. In this approach, document presentation is viewed as a configuration problem whose goal is to determine the optimal presentation of a document, while taking into account the preferences of the content provider, viewer interaction with the browser, and, possibly, some layout constraints. The preferences of the content provider are represented by a CP-net, a graphical, qualitative preference model developed in Boutilier et al. [1999]. The layout constraints are represented as geometric constraints, integrated within the optimization process. We discuss the theoretical basis of our approach, as well as implemented prototype systems for Web pages and for general media-rich document presentation.

REFERENCES

• 1: Corin R. Anderson , Pedro Domingos , Daniel S. Weld, Personalizing web sites for mobile users, Proceedings of the 10th international conference on World Wide Web, p.565-575, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.380716]
• 2: Corin R. Anderson , Eric Horvitz, Web montage: a dynamic personalized start page, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511537]
• 3: Asher, N. and Morreau, M. 1995. What some generic sentences mean. In The Generic Book, G. Carlson and F. J. Pelletier, Eds. Chicago University Press, Chicago, IL, 300--338.
• 4: Bacchus, F. and Grove, A. 1996. Utility independence in qualitative decision theory. In Proceedings of the 5th Conference on Knowledge Representation (Cambridge, MA.), 542--552.
• 5: 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]
• 6: Beaumont, I. 1994. User modeling in the interactive anatomy tutoring system ANATOMTUTOR. User Model. User-Adapt. Interact. 4, 1, 21--45.
• 7: Berkelaar, M. 1996. lpsolve---Simplex-based code for linear and integer programming. Available online at ftp://ftp.es.ele.tue.nl/pub/lp_solve/lp_solve.tar.gz.
• 8: Timothy W. Bickmore , Bill N. Schilit, Digestor: device-independent access to the World Wide Web, Selected papers from the sixth international conference on World Wide Web, p.1075-1082, September 1997, Santa Clara, California, United States
• 9: S. Bistarelli , U. Montanari , F. Rossi , T. Schiex , G. Verfaillie , H. Fargier, Semiring-Based CSPs and Valued CSPs: Frameworks, Properties,and Comparison, Constraints, v.4 n.3, p.199-240, September 1999 [doi>10.1023/A:1026441215081]
• 10: M. Bordegoni , G. Faconti , S. Feiner , M. T. Maybury , T. Rist , S. Ruggieri , P. Trahanias , M. Wilson, A standard reference model for intelligent multimedia presentation systems, Computer Standards & Interfaces, v.18 n.6-7, p.477-496, Dec. 1997 [doi>10.1016/S0920-5489(97)00013-5]
• 11: Alan Borning , Richard Kuang-Hsu Lin , Kim Marriott, Constraint-based document layout for the Web, Multimedia Systems, v.8 n.3, p.177-189, October 2000 [doi>10.1007/s005300000043]
• 12: Boutilier, C., Brafman, R., Domshlak, C., Hoos, H., and Poole, D. 2004a. CP-nets: A tool for representing and reasoning about conditional ceteris paribus preference statements. J. Art. Intell. Res. 21, 135--191.
• 13: Boutilier, C., Brafman, R., Domshlak, C., Hoos, H., and Poole, D. 2004b. Preference-based constrained optimization with CP-nets. Comput. Intell. (Special Issue on Preferences in AI and CP) 20, 2, 137--157.
• 14: Boutilier, C., Brafman, R., Hoos, H., and Poole, D. 1999. Reasoning with conditional ceteris paribus preference statements. In Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (Stockholm, Sweden). 71--80.
• 15: Boyle, C. and Encarnacion, A. 1994. Metadoc: An adaptive hypertext reading system. User Model. User-Adapt. Interact. 4, 1--19.
• 16: Brafman, R. I. and Dimopoulos, Y. 2003. A new look at the semantics and optimization methods of CP-networks. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (Acapulco, Maxico). 1033--1038.
• 17: Brafman, R. I., Domshlak, C., and Shimony, S. E. 2003. Qualitative decision making in adaptive presentation of structured information. Tech. rep. CS-03-17. Department of Computer Science, Ben-Gurion University, Beer-Sheva, Israel.
• 18: Peter Brusilovsky, Adaptive Hypermedia, User Modeling and User-Adapted Interaction, v.11 n.1-2, p.87-110, 2001 [doi>10.1023/A:1011143116306]
• 19: Peter Brusilovsky, Adaptive Hypermedia, User Modeling and User-Adapted Interaction, v.11 n.1-2, p.87-110, 2001 [doi>10.1023/A:1011143116306]
• 20: Paul De Bra , Peter Brusilovsky , Geert-Jan Houben, Adaptive hypermedia: from systems to framework, ACM Computing Surveys (CSUR), v.31 n.4es, Dec. 1999 [doi>10.1145/345966.345996]
• 21: de Bra, P. and Calvi, L. 1998. AHA!---An open adaptive hypermedia architecture. New Rev. Hypermed. Multimed. 4, 115--139.
• 22: Domshlak, C. and Brafman, R. 2002. CP-nets---reasoning and consistency testing. In Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (Toulouse, France). 121--132.
• 23: Domshlak, C., Rossi, F., Venable, C., and Walsh, T. 2003. Reasoning about soft constraints and conditional preferences: Complexity results and approximation techniques. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (Acapulco, Maxico). 215--220.
• 24: Domshlak, C. and Shimony, S. E. 2002. Improving the dynamic behavior of CP-net based multimedia systems by predicting likely components. In AAAI/KDD/UAI Joint Workshop on Real-Time Decision Support and Diagnosis Systems (Edmonton, Alta., Canada).
• 25: Domshlak, C. and Shimony, S. E. 2003. Efficient probabilistic reasoning in Bayes nets with mutual exclusion and context specific independence. In Proceedings of the 16th International FLAIRS Conference, Special Track on Uncertain Reasoning (St. Augustine, FL). 496--500.
• 26: Jon Doyle , Yoav Shoham , Michael P. Wellman, A Logic of Relative Desire (Preliminary Report), Proceedings of the 6th International Symposium on Methodologies for Intelligent Systems, p.16-31, October 16-19, 1991
• 27: Doyle, J. and Thomason, R. H. 1999. Background to qualitative decision theory. AI Mag. 20, 2, 55--68.
• 28: Doyle, J. and Wellman, M. 1994. Representing preferences as ceteris paribus comparatives. In Proceedings of the AAAI Spring Symposium on Decision-Theoretic Planning (Stanford, CA). 69--75.
• 29: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 30: Armando Fox , Eric A. Brewer, Reducing WWW latency and bandwidth requirements by real-time distillation, Proceedings of the fifth international World Wide Web conference on Computer networks and ISDN systems, p.1445-1456, May 1996, Paris, France
• 31: Friedman, N. and Goldszmidt, M. 1996. Learning Bayesian networks with local structure. In Proceedings of 12th Conference on Uncertainty in Artificial Intelligence. 252--262.
• 32: Glass, J. 1999. Challenges for spoken dialogue systems. In IEEE Workshop on Automatic Speech Recognition and Understanding (Keystone, CO). Available online at http://www.sls.lcs.mit.edu/sls/publications/1999/asru99-jrg.pdf.
• 33: Ehud Gudes , Carmel Domshlak , Natalia Orlov, Remote Conferencing with Multimedia Objects, Proceedings of the Worshops XMLDM, MDDE, and YRWS on XML-Based Data Management and Multimedia Engineering-Revised Papers, p.526-543, March 24-28, 2002
• 34: Hansson, S. O. 1996. What is ceteris paribus preference. J. Philosoph. Logic 25, 3, 307--332.
• 35: Hohl, H., Böcker, H.-D., and Gunzenhäuser, R. 1996. HYPADAPTER: An adaptive hypertext system for exploratory learning and programming. User Model. User-Adapt. Interact. 6, 2-3, 131--155.
• 36: Nathan Hurst , Kim Marriott , Peter Moulder, Dynamic approximation of complex graphical constraints by linear constraints, Proceedings of the 15th annual ACM symposium on User interface software and technology, October 27-30, 2002, Paris, France [doi>10.1145/571985.572012]
• 37: C. Karagiannidis , A. Koumpis , C. Stephanidis, Adaptation in IMMPS as a decision making process, Computer Standards & Interfaces, v.18 n.6-7, p.509-514, Dec. 1997 [doi>10.1016/S0920-5489(97)00015-9]
• 38: Keeney, R. L. and Raiffa, H. 1976. Decision with Multiple Objectives: Preferences and Value Tradeoffs. Wiley, New York, NY.
• 39: Wen-Syan Li , Quoc Vu , Edward Chang , Divyakant Agrawal , Kyoji Hirata , Sougata Mukherjea , Yi-Leh Wu , Corey Bufi , Chen-Chuan Kevin Chang , Yoshinori Hara , Reiko Ito , Yutaka Kimura , Kezuyuki Shimazu , Yukiyoshi Saito, PowerBookmarks: a system for personalizable Web information organization, sharing, and management, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.565-567, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 40: Håkon Wium Lie , Bert Bos, Cascading style sheets: designing for the Web, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 41: Kim Marriott , Peter Moulder , Peter J. Stuckey , Alan Borning, Solving Disjunctive Constraints for Interactive Graphical Applications, Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, p.361-376, November 26-December 01, 2001
• 42: Mohan, R., Smith, J. R., and Li, C.-S. 1999. Adapting multimedia Internet content for universal access. IEEE Trans. Multimed. 1, 1, 104--114.
• 43: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 44: Steven F. Roth , William E Hefley, Intelligent multimedia presentation systems: research and principles, Intelligent multimedia interfaces, American Association for Artificial Intelligence, Menlo Park, CA, 1993
• 45: Jeff Rule, Dynamic HTML: the HTML developers' guide, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 46: Santos, Jr., E. 1993. Modelling cyclicity and generalized cost-based abduction using linear constraint satisfaction. J. Exp. Theoret. Art. Intell. 5, 359--390.
• 47: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• 48: Shimony, S. E. and Santos, Jr., E. 1996. Exploiting case-based independence for approximating marginal probabilities. International J. Approx. Reason. 14, 1, 25--54.
• 49: Shoham, Y. 1997. Conditional utility, utility independence, and utility networks. In Proceedings of the 13th Conference on Uncertainty in Artificial Intelligence (San Francisco, CA). 429--436.
• 50: Sek-Wah Tan , Judea Pearl, Qualitative decision theory, Proceedings of the twelfth national conference on Artificial intelligence (vol. 2), p.928-933, October 1994, Seattle, Washington, United States
• 51: von Wright, G. H. 1963. The Logic of Preference: An Essay. Edinburgh University Press, Edinburgh, Scotland.

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.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.2 Types of Systems
          Subjects: Decision support (e.g., MIS)
      H.4.3 Communications Applications
          Subjects: Information browsers
  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); User interface management systems (UIMS)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Design, Management, Theory

Keywords:
Adaptive information presentation, preference representation, qualitative decision theory