Distributed user profiling via spectral methods

DOI10.1214/11-SSY036MaRDI QIDQ2921183zbMATH OpenOpenAlexFDO

Authors Dan-Cristian Tomozei, Laurent Massoulié

Publication date 7 October 2014

Published in Stochastic Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.3318, https://projecteuclid.org/euclid.ssy/1411044991

zbMATH Keywords

random matrixspectral decompositionmessage passingdistributed recommendation systemdistributed spectral embedding

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) (68U35) Distributed systems (68M14)

Abstract: User profiling is a useful primitive for constructing personalised services, such as content recommendation. In the present paper we investigate the feasibility of user profiling in a distributed setting, with no central authority and only local information exchanges between users. We compute a profile vector for each user (i.e., a low-dimensional vector that characterises her taste) via spectral transformation of observed user-produced ratings for items. Our two main contributions follow: i) We consider a low-rank probabilistic model of user taste. More specifically, we consider that users and items are partitioned in a constant number of classes, such that users and items within the same class are statistically identical. We prove that without prior knowledge of the compositions of the classes, based solely on few random observed ratings (namely $O(NlogN)$ such ratings for $N$ users), we can predict user preference with high probability for unrated items by running a local vote among users with similar profile vectors. In addition, we provide empirical evaluations characterising the way in which spectral profiling performance depends on the dimension of the profile space. Such evaluations are performed on a data set of real user ratings provided by Netflix. ii) We develop distributed algorithms which provably achieve an embedding of users into a low-dimensional space, based on spectral transformation. These involve simple message passing among users, and provably converge to the desired embedding. Our method essentially relies on a novel combination of gossiping and the algorithm proposed by Oja and Karhunen.

Recommendations

• Distributed spectral pairwise ranking algorithms
• A decentralized algorithm for spectral analysis
• A decentralized algorithm for spectral analysis
• Learning theory of distributed spectral algorithms
• Distributed clustering using collective principal component analysis

Cites work

• scientific article; zbMATH DE number 6381736 (Why is no real title available?)
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 48067 (Why is no real title available?)
• A decentralized algorithm for spectral analysis
• A spectral heuristic for bisecting random graphs
• Comparison methods for stochastic models and risks
• Matrix completion from noisy entries
• Oja's algorithm for graph clustering, Markov spectral decomposition, and risk sensitive control
• On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix
• On the Early History of the Singular Value Decomposition
• Spectral Clustering by Recursive Partitioning
• Spectral techniques applied to sparse random graphs

Cited in

(3)

• Collaborative filtering with information-rich and~information-sparse entities
• On semidefinite relaxations for the block model
• A spectral method for community detection in moderately sparse degree-corrected stochastic block models

This page was built for publication: Distributed user profiling via spectral methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2921183)