Relational Markov models and their application to adaptive web navigation

ABSTRACT

Relational Markov models (RMMs) are a generalization of Markov models where states can be of different types, with each type described by a different set of variables. The domain of each variable can be hierarchically structured, and shrinkage is carried out over the cross product of these hierarchies. RMMs make effective learning possible in domains with very large and heterogeneous state spaces, given only sparse data. We apply them to modeling the behavior of web site users, improving prediction in our PROTEUS architecture for personalizing web sites. We present experiments on an e-commerce and an academic web site showing that RMMs are substantially more accurate than alternative methods, and make good predictions even when applied to previously-unvisited parts of the site.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: C. R. Anderson, P. Domingos, and D. S. Weld. Adaptive web navigation for wireless devices. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, 2001.
• 3: 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]
• 4: Igor Cadez , David Heckerman , Christopher Meek , Padhraic Smyth , Steven White, Visualization of navigation patterns on a Web site using model-based clustering, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.280-284, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347151]
• 5: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to construct knowledge bases from the World Wide Web, Artificial Intelligence, v.118 n.1-2, p.69-113, April 2000 [doi>10.1016/S0004-3702(00)00004-7]
• 6: T. Dean and K. Kanazawa. Probabilistic Temporal Reasoning. In Proceedings of the Seventh National Conference on Artificial Intelligence, 1988.
• 7: Thomas Dean , Keiji Kanazawa, A model for reasoning about persistence and causation, Computational Intelligence, v.5 n.3, p.142-150, Aug. 1990 [doi>10.1111/j.1467-8640.1989.tb00324.x]
• 8: T. G. Dietterich. State abstraction in MAXQ hierarchical reinforcement learning. In S. A. Solla, T. K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pages 994--1000. MIT Press, Cambridge, MA, 2000.
• 9: Saso Dzeroski , Luc De Raedt , Hendrik Blockeel, Relational Reinforcement Learning, Proceedings of the Fifteenth International Conference on Machine Learning, p.136-143, July 24-27, 1998
• 10: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 11: Xiaobin Fu , Jay Budzik , Kristian J. Hammond, Mining navigation history for recommendation, Proceedings of the 5th international conference on Intelligent user interfaces, p.106-112, January 09-12, 2000, New Orleans, Louisiana, United States [doi>10.1145/325737.325796]
• 12: L. Getoor, D. Koller, and N. Friedman. From instances to classes in probabilistic relational models. In Proceedings of the ICML-2000 Workshop on Attribute-Value and Relational Learning, Stanford, CA, 2000.
• 13: Zoubin Ghahramani , Michael I. Jordan, Factorial Hidden Markov Models, Machine Learning, v.29 n.2-3, p.245-273, Nov./Dec. 1997 [doi>10.1023/A:1007425814087]
• 14: I. J. Good. The Estimation of Probabilities: An Essay on Modern Bayesian Methods. MIT Press, Cambridge, MA, 1965.
• 15: T. Joachims, D. Freitag, and T. Mitchell. WebWatcher: A tour guide for the World Wide Web. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1997.
• 16: Ron Kohavi , Carla E. Brodley , Brian Frasca , Llew Mason , Zijian Zheng, KDD-Cup 2000 organizers' report: peeling the onion, ACM SIGKDD Explorations Newsletter, v.2 n.2, p.86-93, Dec. 2000 [doi>10.1145/380995.381033]
• 17: John D. Lafferty , Andrew McCallum , Fernando C. N. Pereira, Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, Proceedings of the Eighteenth International Conference on Machine Learning, p.282-289, June 28-July 01, 2001
• 18: H. Lieberman. Letizia: An agent that assists web browsing. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 1995.
• 19: Andrew McCallum , Ronald Rosenfeld , Tom M. Mitchell , Andrew Y. Ng, Improving Text Classification by Shrinkage in a Hierarchy of Classes, Proceedings of the Fifteenth International Conference on Machine Learning, p.359-367, July 24-27, 1998
• 20: S. Muggleton. Stochastic logic programs. In L. de Raedt, editor, Advances in Inductive Logic Programming, pages 254--264. IOS Press, Amsterdam, The Netherlands, 1996.
• 21: Liem Ngo , Peter Haddawy, Answering queries from context-sensitive probabilistic knowledge bases, Theoretical Computer Science, v.171 n.1-2, p.147-177, Jan. 15, 1997
• 22: M. Pazzani, J. Muramatsu, and D. Billsus. Syskill & Webert: Identifying interesting Web sites. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, 1996.
• 23: Michael J. Pazzani , Daniel Billsus, Adaptive Web site agents, Proceedings of the third annual conference on Autonomous Agents, p.394-395, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301256]
• 24: M. Perkowitz and O. Etzioni. Adaptive web sites: an AI challenge. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, 1997.
• 25: Mike Perkowitz , Oren Etzioni, Towards adaptive Web sites: conceptual framework and case study, Artificial Intelligence, v.118 n.1-2, p.245-275, April 2000 [doi>10.1016/S0004-3702(99)00098-3]
• 26: Foster Provost , Pedro Domingos, Tree Induction for Probability-Based Ranking, Machine Learning, v.52 n.3, p.199-215, September 2003 [doi>10.1023/A:1024099825458]
• 27: L. R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE, 77:257--286, 1989.
• 28: Ramesh R. Sarukkai, Link prediction and path analysis using Markov chains, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.377-386, June 2000, Amsterdam, The Netherlands
• 29: P. Smyth. Clustering sequences with hidden Markov models. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing 9, 1996.
• 30: Padhraic Smyth , David Heckerman , Michael I. Jordan, Probabilistic independence networks for hidden Markov probability models, Neural Computation, v.9 n.2, p.227-269, Feb. 15, 1997 [doi>10.1162/neco.1997.9.2.227]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

Keywords:
Markov models, Web mining, personalization, relational probabilistic models, shrinkage