nach oben

Knowledge and Information Systems

Erschienen in:

03.05.2018 | Regular Paper

EigenRec: generalizing PureSVD for effective and efficient top-N recommendations

verfasst von: Athanasios N. Nikolakopoulos, Vassilis Kalantzis, Efstratios Gallopoulos, John D. Garofalakis

Erschienen in: Knowledge and Information Systems | Ausgabe 1/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce EigenRec, a versatile and efficient latent factor framework for top-N recommendations that includes the well-known PureSVD algorithm as a special case. EigenRec builds a low-dimensional model of an inter-item proximity matrix that combines a similarity component, with a scaling operator, designed to control the influence of the prior item popularity on the final model. Seeing PureSVD within our framework provides intuition about its inner workings, exposes its inherent limitations, and also, paves the path toward painlessly improving its recommendation performance. A comprehensive set of experiments on the MovieLens and the Yahoo datasets based on widely applied performance metrics, indicate that EigenRec outperforms several state-of-the-art algorithms, in terms of Standard and Long-Tail recommendation accuracy, exhibiting low susceptibility to sparsity, even in its most extreme manifestations—the Cold-Start problems. At the same time, EigenRec has an attractive computational profile and it can apply readily in large-scale recommendation settings.

Vorheriger Artikel Rating the skill of synthetic agents in competitive multi-agent environments

Nächster Artikel A fuzzy ontology-based approach for tool-supported decision making in architectural design

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Note that even though the actual values of the reconstructed matrix do not have a meaning in terms of ratings, they induce an ordering of the items which is sufficient for recommending top-N lists.

A preliminary version of this work has been presented in [28].

High-level and MPI implementations of EigenRec can be found here: https://github.com/nikolakopoulos/EigenRec.

Remember that these “scores” are by definition the elements that replace the previously zero-valued entries of the original ratings matrix \({\mathbf {R}}\), after its reconstruction using only the f largest singular dimensions.

For which, if we assume scaling parameter d, matrix W equals \({\mathbf {R}}\,{\mathrm{diag}}\{\Vert {\mathbf {r}}_{{\mathbf {1}}}\Vert ,\Vert {\mathbf {r}}_{{\mathbf {2}}}\Vert ,\dots ,\Vert {\mathbf {r}}_{{\mathbf {m}}}\Vert \}^{d-1}.\)

Note that to alleviate this, one can use sophisticated parallel schemes that try to overlap communication with computations; however, their analysis goes deep into high-performance computing and lies outside the scope of this paper.

Different approaches to compute partial singular value decompositions of sparse matrices can be found in [38, 39].

Anderson C (2008) The long tail: Why the future of business is selling less of more. Hyperion, New York

Aurentz JL, Kalantzis V, Saad Y (2017) Cucheb: a GPU implementation of the filtered Lanczos procedure. Comput Phys Commun 220:332–340CrossRef

Bai Z, Demmel J, Dongarra J, Ruhe A, van der Vorst H (2000) Templates for the solution of algebraic eigenvalue problems: a practical guide, vol 11. SIAM, PhiladelphiaCrossRefMATH

Balakrishnan S, Chopra S (2012) Collaborative ranking. In: Proceedings of the fifth ACM international conference on Web search and data mining, WSDM ’12. ACM, New York, pp 143–152. https://doi.org/10.1145/2124295.2124314

Blackford LS, Petitet A, Pozo R, Remington K, Whaley RC, Demmel J, Dongarra J, Duff I, Hammarling S, Henry G et al (2002) An updated set of basic linear algebra subprograms (blas). ACM Trans Math Softw 28(2):135–151MathSciNetCrossRef

Blom K, Ruhe A (2004) A krylov subspace method for information retrieval. SIAM J Matrix Anal Appl 26(2):566–582MathSciNetCrossRefMATH

Bobadilla J, Ortega F, Hernando A, GutiéRrez A (2013) Recommender systems survey. Knowl. Based Syst 46:109–132. https://doi.org/10.1016/j.knosys.2013.03.012 CrossRef

Chebotarev P, Shamis E (1997) The matrix-forest theorem and measuring relations in small social groups. Autom Remote Control 58(9):1505–1514MATH

Chen J, Saad Y (2009) Lanczos vectors versus singular vectors for effective dimension reduction. IEEE Trans Knowl Data Eng 21(8):1091–1103CrossRef

10.

Cremonesi P, Koren Y, Turrin R (2010) Performance of recommender algorithms on top-n recommendation tasks. In: Proceedings of the fourth ACM conference on Recommender systems, RecSys ’10. ACM, pp 39–46. https://doi.org/10.1145/1864708.1864721

11.

Desrosiers C, Karypis G (2011) A comprehensive survey of neighborhood-based recommendation methods. In: Ricci F, Rokach L, Shapira B, Kantor PB (eds) Recommender systems handbook. Springer, US, pp 107–144. https://doi.org/10.1007/978-0-387-85820-3_4 CrossRef

12.

Elbadrawy A, Karypis G (2015) User-specific feature-based similarity models for top-n recommendation of new items. ACM Trans Intell Syst Technol 6(3):33:1–33:20. https://doi.org/10.1145/2700495 CrossRef

13.

Fouss F, Francoisse K, Yen L, Pirotte A, Saerens M (2012) An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification. Neural Netw 31:53–72CrossRefMATH

14.

Fouss F, Pirotte A, Renders J, Saerens M (2007) Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans Knowl Data Eng 19(3):355–369CrossRef

15.

Gallopoulos E, Philippe B, Sameh AH (2015) Parallelism in matrix computations, 1st edn. Springer, BerlinMATH

16.

Gantner Z, Drumond L, Freudenthaler C, Rendle S, Schmidt-Thieme L (2010) Learning attribute-to-feature mappings for cold-start recommendations. In: 2010 IEEE 10th international conference on data mining (ICDM), pp 176–185. https://doi.org/10.1109/ICDM.2010.129

17.

Goldberg K, Roeder T, Gupta D, Perkins C (2001) Eigentaste: a constant time collaborative filtering algorithm. Inf Retr 4(2):133–151. https://doi.org/10.1023/A:1011419012209 CrossRefMATH

18.

Harper FM, Konstan JA (2015) The movielens datasets: history and context. ACM Trans Interact Intell Syst 5(4):19:1–19:19. https://doi.org/10.1145/2827872 CrossRef

19.

Huang Z, Chen H, Zeng D (2004) Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering. ACM Trans Inf Syst 22(1):116–142. https://doi.org/10.1145/963770.963775 CrossRef

20.

Joachims T, Swaminathan A, Schnabel T (2017) Unbiased learning-to-rank with biased feedback. In: Proceedings of the tenth ACM international conference on web search and data mining, WSDM ’17. ACM, New York, pp 781–789. https://doi.org/10.1145/3018661.3018699

21.

Kabbur S, Ning X, Karypis G (2013) Fism: factored item similarity models for top-n recommender systems. In: Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’13. ACM, New York, pp 659–667. https://doi.org/10.1145/2487575.2487589

22.

Kalantzis V, Li R, Saad Y (2016) Spectral schur complement techniques for symmetric eigenvalue problems. Electron Trans Numer Anal 45:305–329MathSciNetMATH

23.

Koren Y (2008) Factorization meets the neighborhood: a multifaceted collaborative filtering model. In: Proceedings of the 14th ACM SIGKDD international conference on knowledge discovery and data mining, KDD’08. ACM, New York, pp 426–434. https://doi.org/10.1145/1401890.1401944

24.

Koren Y, Bell R, Volinsky C (2009) Matrix factorization techniques for recommender systems. Computer 42(8):30–37CrossRef

25.

Lanczos C (1950) An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. United States Government Press Office, Washington, D.CCrossRefMATH

26.

Nikolakopoulos A, Garofalakis J (2014) NCDREC: a decomposability inspired framework for top-n recommendation. In: 2014 IEEE/WIC/ACM international joint conferences on web intelligence (WI) and intelligent agent technologies (IAT), vol 1, pp 183–190. https://doi.org/10.1109/WI-IAT.2014.32

27.

Nikolakopoulos AN, Kalantzi M, Garofalakis JD (2014) On the use of lanczos vectors for efficient latent factor-based top-n recommendation. In: Proceedings of the 4th international conference on web intelligence, mining and semantics (WIMS14), WIMS ’14. ACM, New York, pp 28:1–28:6. https://doi.org/10.1145/2611040.2611078

28.

Nikolakopoulos AN, Kalantzis V, Gallopoulos E, Garofalakis JD (2017) Factored proximity models for top-n recommendations. In: 2017 IEEE international conference on big knowledge (ICBK), pp 80–87. https://doi.org/10.1109/ICBK.2017.14

29.

Nikolakopoulos AN, Korba A, Garofalakis JD (2016) Random surfing on multipartite graphs. In: 2016 IEEE international conference on big data (big data), pp 736–745. https://doi.org/10.1109/BigData.2016.7840666

30.

Nikolakopoulos AN, Kouneli MA, Garofalakis JD (2015) Hierarchical itemspace rank: exploiting hierarchy to alleviate sparsity in ranking-based recommendation. Neurocomputing 163:126–136. https://doi.org/10.1016/j.neucom.2014.09.082 CrossRef

31.

Sarwar B, Karypis G, Konstan J, Riedl J (2000) Application of dimensionality reduction in recommender system-a case study. Tech. rep., DTIC Document

32.

Schnabel T, Swaminathan A, Singh A, Chandak N, Joachims T (2016) Recommendations as treatments: debiasing learning and evaluation. In: Proceedings of the 33rd international conference on international conference on machine learning, ICML’16, vol 48, pp 1670–1679. JMLR.org. http://dl.acm.org/citation.cfm?id=3045390.3045567

33.

Shani G, Gunawardana A (2011) Evaluating recommendation systems. In: Ricci F, Rokach L, Shapira B, Kantor PB (eds) Recommender systems handbook. Springer, Boston, pp 257–297. https://doi.org/10.1007/978-0-387-85820-3_8 CrossRef

34.

Sharma M, Zhou J, Hu J, Karypis G (2015) Feature-based factorized bilinear similarity model for cold-start top-n item recommendation. In: Proceedings of the 2015 SIAM international conference on data mining, SDM’15, pp 190–198. https://doi.org/10.1137/1.9781611974010.22

35.

Snir M, Otto S, Huss-Lederman S, Walker D, Dongarra J (1998) MPI-the complete reference, vol 1: the MPI core, 2nd. (revised) edn. MIT Press, Cambridge

36.

Takács G, Pilászy I, Németh B, Tikk D (2009) Scalable collaborative filtering approaches for large recommender systems. J Mach Learn Res 10:623–656 http://dl.acm.org/citation.cfm?id=1577069.1577091

37.

Wu K, Simon H (2000) Thick-restart lanczos method for large symmetric eigenvalue problems. SIAM J Matrix Anal Appl 22(2):602–616MathSciNetCrossRefMATH

38.

Wu L, Romero E, Stathopoulos A (2016) Primme_svds: A high-performance preconditioned svd solver for accurate large-scale computations. arXiv preprint arXiv:1607.01404

39.

Wu L, Stathopoulos A (2015) A preconditioned hybrid svd method for accurately computing singular triplets of large matrices. SIAM J Sci Comput 37(5):S365–S388MathSciNetCrossRefMATH

40.

Yahoo Webscope Program: Yahoo!R2Music Dataset. https://webscope.sandbox.yahoo.com/

41.

Yin H, Cui B, Li J, Yao J, Chen C (2012) Challenging the long tail recommendation. Proc VLDB Endow 5(9):896–907CrossRef

42.

Zhou D, Bousquet O, Lal TN, Weston J, Schölkopf B (2003) Learning with local and global consistency. In: Thrun S, Saul LK, Schölkopf B (eds) Advances in neural information processing systems 16 [Neural information processing systems, NIPS 2003, 8–13 Dec 2003, Vancouver and Whistler, British Columbia, Canada]. MIT Press, pp 321–328. http://papers.nips.cc/paper/2506-learning-with-local-and-global-consistency

Titel: EigenRec: generalizing PureSVD for effective and efficient top-N recommendations
verfasst von: Athanasios N. Nikolakopoulos
Vassilis Kalantzis
Efstratios Gallopoulos
John D. Garofalakis
Publikationsdatum: 03.05.2018
Verlag: Springer London
Erschienen in: Knowledge and Information Systems / Ausgabe 1/2019
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI: https://doi.org/10.1007/s10115-018-1197-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2019

Answering why-not questions on SPARQL queries

On big wisdom

Connectedness-based subspace clustering

Complex-valued encoding symbiotic organisms search algorithm for global optimization

A fuzzy ontology-based approach for tool-supported decision making in architectural design

Deployment of social nets in multilayer model to identify key individuals using majority voting