Ranking from Crowdsourced Pairwise Comparisons via Smoothed Riemannian Optimization

摘要

Social Internet of Things has recently become a promising paradigm for augmenting the capability of humans and devices connected in the networks to provide services. In social Internet of Things network, crowdsourcing that collects the intelligence of the human crowd has served as a powerful tool for data acquisition and distributed computing. To support critical applications (e.g., a recommendation system and assessing the inequality of urban perception), in this article, we shall focus on the collaborative ranking problems for user preference prediction from crowdsourced pairwise comparisons. Based on the Bradley-Terry-Luce (BTL) model, a maximum likelihood estimation (MLE) is proposed via low-rank approach in order to estimate the underlying weight/score matrix, thereby predicting the ranking list for each user. A novel regularized formulation with the smoothed surrogate of elementwise infinity norm is proposed in order to address the unique challenge of the coupled the non-smooth elementwise infinity norm constraint and non-convex low-rank constraint in the MLE problem. We solve the resulting smoothed rank-constrained optimization problem via developing the Riemannian trust-region algorithm on quotient manifolds of fixed-rank matrices, which enjoys the superlinear convergence rate. The admirable performance and algorithmic advantages of the proposed method over the state-of-the-art algorithms are demonstrated via numerical results. Moreover, the proposed method outperforms state-of-the-art algorithms on large collaborative filtering datasets in both success rate of inferring preference and normalized discounted cumulative gain.