論文の概要: Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank
Centrality Method
- arxiv url: http://arxiv.org/abs/2109.13743v2
- Date: Wed, 12 Jul 2023 10:02:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-13 20:44:21.868456
- Title: Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank
Centrality Method
- Title（参考訳）: BTLモデルによる動的ランク付け:最も近い隣のランク中心性法
- Authors: Eglantine Karl\'e and Hemant Tyagi
- Abstract要約: 静的設定から動的設定への古典的BTL(Bradley-Terry-Luce)モデルの拡張について検討する。
我々は mathbbRn$ のアイテム $w_t* の潜在強度をいつでも回復することを目指している。
また、実データおよび合成データに関する実験で理論解析を補完する。
- 参考スコア（独自算出の注目度）: 5.025654873456756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many applications such as recommendation systems or sports tournaments
involve pairwise comparisons within a collection of $n$ items, the goal being
to aggregate the binary outcomes of the comparisons in order to recover the
latent strength and/or global ranking of the items. In recent years, this
problem has received significant interest from a theoretical perspective with a
number of methods being proposed, along with associated statistical guarantees
under the assumption of a suitable generative model.
While these results typically collect the pairwise comparisons as one
comparison graph $G$, however in many applications - such as the outcomes of
soccer matches during a tournament - the nature of pairwise outcomes can evolve
with time. Theoretical results for such a dynamic setting are relatively
limited compared to the aforementioned static setting. We study in this paper
an extension of the classic BTL (Bradley-Terry-Luce) model for the static
setting to our dynamic setup under the assumption that the probabilities of the
pairwise outcomes evolve smoothly over the time domain $[0,1]$. Given a
sequence of comparison graphs $(G_{t'})_{t' \in \mathcal{T}}$ on a regular grid
$\mathcal{T} \subset [0,1]$, we aim at recovering the latent strengths of the
items $w_t^* \in \mathbb{R}^n$ at any time $t \in [0,1]$. To this end, we adapt
the Rank Centrality method - a popular spectral approach for ranking in the
static case - by locally averaging the available data on a suitable
neighborhood of $t$. When $(G_{t'})_{t' \in \mathcal{T}}$ is a sequence of
Erd\"os-Renyi graphs, we provide non-asymptotic $\ell_2$ and $\ell_{\infty}$
error bounds for estimating $w_t^*$ which in particular establishes the
consistency of this method in terms of $n$, and the grid size
$\lvert\mathcal{T}\rvert$. We also complement our theoretical analysis with
experiments on real and synthetic data.
- Abstract（参考訳）: レコメンデーションシステムやスポーツトーナメントのような多くのアプリケーションは、n$アイテムのコレクション内でペアで比較を行い、そのゴールは、アイテムの潜在強度および/またはグローバルなランキングを回復するために比較の2値の結果を集約することである。
近年、この問題は、適切な生成モデルの仮定の下で関連する統計的保証とともに、多くの方法が提案されている理論的な観点から大きな関心を集めている。
これらの結果は通常、1つの比較グラフ$G$としてペア比較を収集するが、トーナメント中のサッカーの試合の結果のような多くのアプリケーションでは、ペア比較の結果の性質は時間とともに進化する。
このような動的設定の理論的結果は、上記の静的設定と比較して相対的に制限される。
本稿では、時間領域$[0,1]$でペアワイズ結果の確率が円滑に変化するという仮定の下で、静的設定から動的設定への古典的BTL(Bradley-Terry-Luce)モデルの拡張について検討する。
G_{t'})_{t' \in \mathcal{T}}$ on a regular grid $\mathcal{T} \subset [0,1]$ の一連の比較グラフが与えられたとき、我々は、アイテム $w_t^* \in \mathbb{R}^n$ の潜在強度をいつでも $t \in [0,1]$ で回復することを目指している。
この目的のために、静的ケースにおけるランク付けのための一般的なスペクトルアプローチであるランク中央化法を、適当な$t$の近傍で利用できるデータを局所的に平均化することで適用する。
G_{t'})_{t' \in \mathcal{T}}$ が Erd\"os-Renyi グラフの列であるとき、$w_t^*$ を推定するための非漸近的な $\ell_2$ と $\ell_{\infty}$ エラー境界を与える。
また、実データおよび合成データに関する実験で理論解析を補完する。
関連論文リスト
- Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time [19.25942907402098]
動的相関クラスタリング問題について,textitadaptive$ edge label flipsを用いて検討した。
相関クラスタリングでは、エッジを$(+)$または$(-)$とラベル付けした$n$-vertex完全グラフが与えられる。
本稿では, 対数ロバスト性を持つ動的設定について考察する。ここでは, $textitadaptive$ adversary がアルゴリズムの現在の出力に基づいてエッジのラベルを反転させることができる。
論文 参考訳（メタデータ） (2024-11-15T06:26:37Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - Uncertainty Quantification of MLE for Entity Ranking with Covariates [3.2839905453386162]
本稿では,ペア比較に基づくランキング問題の統計的推定と推定について検討する。
我々は、有名なBradley-Terry-Luceモデルを拡張した新しいモデルCAREモデルを提案する。
我々は、スパース比較グラフの下で、$alpha_i*_i=1n$と$beta*$の最大確率推定器を導出する。
大規模数値研究による理論結果の検証と相互資金保有データセットへの適用について検討する。
論文 参考訳（メタデータ） (2022-12-20T02:28:27Z) - Dynamic Ranking and Translation Synchronization [3.946250592943285]
本研究では, エン翻訳同期問題の動的設定への拡張について検討する。
そこで我々は,2つの推定器を提案し,その1つはスムーズネスの最小二乗法に基づくものであり,もう1つは適切な滑らかさ演算子の低周波固有空間への射影に基づくものである。
論文 参考訳（メタデータ） (2022-07-04T14:45:12Z) - Supervised Training of Conditional Monge Maps [107.78770597815242]
最適輸送(OT)理論は、多くの可能な選択の中から確率測度を他のものにマッピングする最も効率的な方法を定義し、選択する一般的な原理を記述している。
本研究では,コンテキスト変数に条件付きOTマップの族を推定するマルチタスク手法であるCondOTを紹介する。
本研究では,CondOTの遺伝的・治療的摂動の任意の組み合わせが単一細胞に与える影響を推測する能力を示す。
論文 参考訳（メタデータ） (2022-06-28T19:34:44Z) - Seeded graph matching for the correlated Gaussian Wigner model via the projected power method [5.639451539396459]
グラフマッチングアルゴリズムとして,Emphprojected Power Method (PPM) の性能解析を行った。
PPM は定数 $sigma$ の反復でも機能し、(Mao et al. 2023) のスパース相関エルドス・レニー(CER) モデルに対する解析を (dense) CGW モデルに拡張する。
論文 参考訳（メタデータ） (2022-04-08T14:31:26Z) - Accelerating Optimization and Reinforcement Learning with
Quasi-Stochastic Approximation [2.294014185517203]
本稿では、収束理論を準確率近似に拡張することを目的とする。
強化学習のためのグラデーションフリー最適化とポリシー勾配アルゴリズムへの応用について説明する。
論文 参考訳（メタデータ） (2020-09-30T04:44:45Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Second-Order Information in Non-Convex Stochastic Optimization: Power
and Limitations [54.42518331209581]
私たちは発見するアルゴリズムを見つけます。
epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using
$(epsilon,gamma)$surimateランダムランダムポイント。
ここでの私たちの下限は、ノイズのないケースでも新規です。
論文 参考訳（メタデータ） (2020-06-24T04:41:43Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。