Learning optimal ranking with tensor factorization for tag recommendation

ABSTRACT

Tag recommendation is the task of predicting a personalized list of tags for a user given an item. This is important for many websites with tagging capabilities like last.fm or delicious. In this paper, we propose a method for tag recommendation based on tensor factorization (TF). In contrast to other TF methods like higher order singular value decomposition (HOSVD), our method RTF ('ranking with tensor factorization') directly optimizes the factorization model for the best personalized ranking. RTF handles missing values and learns from pairwise ranking constraints. Our optimization criterion for TF is motivated by a detailed analysis of the problem and of interpretation schemes for the observed data in tagging systems. In all, RTF directly optimizes for the actual problem using a correct interpretation of the data. We provide a gradient descent algorithm to solve our optimization problem. We also provide an improved learning and prediction method with runtime complexity analysis for RTF. The prediction runtime of RTF is independent of the number of observations and only depends on the factorization dimensions. Besides the theoretical analysis, we empirically show that our method outperforms other state-of-the-art tag recommendation methods like FolkRank, PageRank and HOSVD both in quality and prediction runtime.

REFERENCES

• 1: Alan Herschtal , Bhavani Raskutti, Optimising area under the ROC curve using gradient descent, Proceedings of the twenty-first international conference on Machine learning, p.49, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015366]
• 2: Paul Heymann , Daniel Ramage , Hector Garcia-Molina, Social tag prediction, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390425]
• 3: A. Hotho, R. Jaschke, C. Schmitz, and G. Stumme. Information Retrieval in Folksonomies: Search and Ranking. 2006.
• 4: Robert Jäschke , Leandro Marinho , Andreas Hotho , Lars Schmidt-Thieme , Gerd Stumme, Tag Recommendations in Folksonomies, Proceedings of the 11th European conference on Principles and Practice of Knowledge Discovery in Databases, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74976-9_52]
• 5: Robert Jäschke , Leandro Marinho , Andreas Hotho , Lars Schmidt-Thieme , Gerd Stumme, Tag recommendations in social bookmarking systems, AI Communications, v.21 n.4, p.231-247, December 2008
• 6: Tamara G. Kolda , Jimeng Sun, Scalable Tensor Decompositions for Multi-aspect Data Mining, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.363-372, December 15-19, 2008 [doi>10.1109/ICDM.2008.89]
• 7: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, A Multilinear Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1253-1278, March – May 2000 [doi>10.1137/S0895479896305696]
• 8: Lieven De Lathauwer , Bart De Moor , Joos Vandewalle, On the Best Rank-1 and Rank-(R₁,R₂,. . .,R_N) Approximation of Higher-Order Tensors, SIAM Journal on Matrix Analysis and Applications, v.21 n.4, p.1324-1342, March – May 2000 [doi>10.1137/S0895479898346995]
• 9: Steffen Rendle , Lars Schmidt-Thieme, Online-updating regularized kernel matrix factorization models for large-scale recommender systems, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454047]
• 10: Jasson D. M. Rennie , Nathan Srebro, Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd international conference on Machine learning, p.713-719, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102441]
• 11: Amnon Shashua , Tamir Hazan, Non-negative tensor factorization with applications to statistics and computer vision, Proceedings of the 22nd international conference on Machine learning, p.792-799, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102451]
• 12: Yang Song , Lu Zhang , C. Lee Giles, A sparse gaussian processes classification framework for fast tag suggestions, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458098]
• 13: Yang Song , Ziming Zhuang , Huajing Li , Qiankun Zhao , Jia Li , Wang-Chien Lee , C. Lee Giles, Real-time automatic tag recommendation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390423]
• 14: Panagiotis Symeonidis , Alexandros Nanopoulos , Yannis Manolopoulos, Tag recommendations based on tensor dimensionality reduction, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454017]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Parameter learning

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
ranking, tag recommendation, tensor factorization