论文标题
动态排名和翻译同步
Dynamic Ranking and Translation Synchronization
论文作者
论文摘要
在许多应用程序（例如运动锦标赛或推荐系统）中，我们拥有由一组$ n $项目（或玩家）之间的成对比较组成的处理数据。目的是使用这些数据来推断每个项目和/或其排名的潜在强度。此问题的现有结果主要集中在由单个比较图$ g $组成的设置上。但是，存在成对比较数据随时间发展的情况（例如运动锦标赛）。这种动态设置的理论结果相对有限，是本文的重点。 我们研究\ emph {翻译同步}问题的扩展，到动态设置。在此设置中，我们给出了一个比较图的顺序$（g_t）_ {t \ in \ Mathcal {t}} $，其中$ \ Mathcal {t} \ subset [0,1] $是一个网格，是一个时间域，代表每个项目$ i $ i $ i $ i $ i $ i $ t \ nations \ national \ national \ mathcal ins an \ national and \ nist an \ nistain and \ nis \ nistain art \ nistaim and \ nistain and \ nistain and \ mathcal cam $ z^*_ {t，i} \ in \ mathbb {r} $。我们的目的是恢复，以$ t \ in \ nathcal {t} $，强度向量$ z^*_ t =（z^*_ {t，1}，\ dots，z^*_ {t，n}）$从noisy的噪声测量中的$ z^*_} - i} - i} - i} - i} - i} - i} - i} - i} - i} - i} - 是$ g_t $的优势。假设$ z^*_ t $在$ t $中顺利演变，我们提出了两个估计器 - 一个基于平滑度含量的最小二乘方法，另一个基于对合适平滑度操作员低频特征性特征空间的投影。 For both estimators, we provide finite sample bounds for the $\ell_2$ estimation error under the assumption that $G_t$ is connected for all $t\in \mathcal{T}$, thus proving the consistency of the proposed methods in terms of the grid size $|\mathcal{T}|$.我们通过有关合成和真实数据的实验来补充理论发现。
In many applications, such as sport tournaments or recommendation systems, we have at our disposal data consisting of pairwise comparisons between a set of $n$ items (or players). The objective is to use this data to infer the latent strength of each item and/or their ranking. Existing results for this problem predominantly focus on the setting consisting of a single comparison graph $G$. However, there exist scenarios (e.g., sports tournaments) where the the pairwise comparison data evolves with time. Theoretical results for this dynamic setting are relatively limited and is the focus of this paper. We study an extension of the \emph{translation synchronization} problem, to the dynamic setting. In this setup, we are given a sequence of comparison graphs $(G_t)_{t\in \mathcal{T}}$, where $\mathcal{T} \subset [0,1]$ is a grid representing the time domain, and for each item $i$ and time $t\in \mathcal{T}$ there is an associated unknown strength parameter $z^*_{t,i}\in \mathbb{R}$. We aim to recover, for $t\in\mathcal{T}$, the strength vector $z^*_t=(z^*_{t,1},\dots,z^*_{t,n})$ from noisy measurements of $z^*_{t,i}-z^*_{t,j}$, where $\{i,j\}$ is an edge in $G_t$. Assuming that $z^*_t$ evolves smoothly in $t$, we propose two estimators -- one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. For both estimators, we provide finite sample bounds for the $\ell_2$ estimation error under the assumption that $G_t$ is connected for all $t\in \mathcal{T}$, thus proving the consistency of the proposed methods in terms of the grid size $|\mathcal{T}|$. We complement our theoretical findings with experiments on synthetic and real data.
