Learning user preferences for sets of objects

ABSTRACT

Most work on preference learning has focused on pairwise preferences or rankings over individual items. In this paper, we present a method for learning preferences over sets of items. Our learning method takes as input a collection of positive examples---that is, one or more sets that have been identified by a user as desirable. Kernel density estimation is used to estimate the value function for individual items, and the desired set diversity is estimated from the average set diversity observed in the collection. Since this is a new learning problem, we introduce a new evaluation methodology and evaluate the learning method on two data collections: synthetic blocks-world data and a new real-world music data collection that we have gathered.

REFERENCES

• 1: Analytical Methods Committee (2001). Representing data distributions with kernel density estimates (Technical Report AMC Technical Brief No. 4). Royal Society of Chemistry.
• 2: Barberà, S., Bossert, W., & Pattanaik, P. K. (2004). Ranking sets of objects. In S. Barberàà, P. J. Hammond and C. Seidl (Eds.), Handbook of utility theory, vol. 2: Extensions, chapter 17. Springer.
• 3: Craig Boutilier, Solving concisely expressed combinatorial auction problems, Eighteenth national conference on Artificial intelligence, p.359-366, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 4: Brafman, R. I., Domshlak, C., Shimony, S. E., & Silver, Y. (2005). Preferences over sets. Working Notes of the IJCAI-05 Workshop on Advances in Preference Handling.
• 5: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 6: Robin Burke, Hybrid Recommender Systems: Survey and Experiments, User Modeling and User-Adapted Interaction, v.12 n.4, p.331-370, November 2002 [doi>10.1023/A:1021240730564]
• 7: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 8: Caruana, R., Baluja, S., & Mitchell, T. (1996). Using the future to 'sort out' the present: Rankprop and multitask learning for medical risk evaluation. Advances in Neural Information Processing Systems (Proceedings of NIPS 95) (pp. 959--965). MIT Press.
• 9: Wei Chu , Zoubin Ghahramani, Preference learning with Gaussian processes, Proceedings of the 22nd international conference on Machine learning, p.137-144, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102369]
• 10: Cohen, W. W., Schapire, R. E., & Singer, Y. (1999). Learning to order things. Journal of Artificial Intelligence Research, 10, 243--270.
• 11: Crammer, K., & Singer, Y. (2001). Pranking with ranking. Proceedings of the Neural Information Processing Systems Conference (pp. 641--647).
• 12: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 13: desJardins, M., & Wagstaff, K. L. (2005). DD-PREF: A language for expressing preferences over sets. Proceedings of the Twentieth National Conference on Artificial Intelligence (pp. 620--626).
• 14: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 15: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 16: Gill, P. E., & Murray, W. (1976). Minimization subject to bounds on the variables. National Physical Laboratory.
• 17: Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical optimization. Academic Press.
• 18: Herbrich, R., Graepel, T., Bollmann-Sdorra, P., & Obermayer, K. (1998). Learning preference relations for information retrieval. Proceedings of the Learning for Text Categorization AAAI Workshop (pp. 83--86).
• 19: Price, B., & Messinger, P. R. (2005). Optimal recommendation sets: Covering uncertainty over user preferences. Proceedings of the Twentieth National Conference on Artificial Intelligence (pp. 541--548).
• 20: Witten, I. H., & Frank, E. (2005). Data mining: Practical machine learning tools and techniques. Morgan Kaufmann. Second edition.
• 21: Cheng Xiang Zhai , William W. Cohen , John Lafferty, Beyond independent relevance: methods and evaluation metrics for subtopic retrieval, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860440]
• 22: Zwicker, E., & Fastl, H. (1990). Psychoacoustics, facts and models. Springer-Verlag.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Distribution functions

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical; Neural nets

General Terms:
Algorithms, Theory