Time-homogeneous top-K ranking using tensor decompositions

• Published in: Optimization methods & software 2020-11, Vol.35 (6), p.1119-1143
• Main Authors: Ataei, Masoud, Chen, Shengyuan, Yang, Zijiang, Peyghami, M. Reza
• Format: Article
• Language: English
• Subjects: Bradley-Terry-Luce (BTL) model; cardinality-constrained portfolio optimization; Decomposition; Mathematical analysis; non-stationary spatio-temporal data analysis; Rank aggregation; rank centrality; Ranking; S&P500; tensor decomposition; Tensors; top-K ranking
• ISSN: 1055-6788; 1029-4937
• DOI: 10.1080/10556788.2019.1584623

Given N items, all having positive latent strengths, top-K ranking problem aims to identify the K items ( ) receiving the highest ranks based on partially revealed comparisons among the items. This problem has been widely studied in the case for which comparisons are performed independently. However, identifying the top-K rankings becomes a more intricate task when comparisons per se are performed along some temporal dimension. In this paper, we investigate potential impacts of temporality on sequences of top-K items and propose a time-homogeneous ranking scheme. Our framework relies mainly on tensor decompositions, rank centrality, and an innovative continuous extension of the Bradley-Terry-Luce (BTL) model. The proposed continuous BTL model extends the win/loss nature of the logistic model to a continuous setting, further reflecting preference degrees that may exist among the compared items. Our computations, which pertain to the analysis of S&P500 data from January 2008 to December 2017, confirm that the proposed top-K ranking scheme is an effective approach to optimize cardinality-constrained portfolios which involve large volumes of noisy and incomplete data.