論文の概要: Improved theoretical guarantee for rank aggregation via spectral method

• arxiv url: http://arxiv.org/abs/2309.03808v2
• Date: Sun, 10 Sep 2023 05:25:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-12 18:07:27.867847
• Title: Improved theoretical guarantee for rank aggregation via spectral method
• Title（参考訳）: スペクトル法によるランクアグリゲーションの理論的保証の改善
• Authors: Ziliang Samuel Zhong, Shuyang Ling
• Abstract要約: 複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? ランクアグリゲーションとして知られるこの問題は、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションに多くの応用を見出している。 ここで、各ペア比較は真のスコア差の破損したコピーである。
• 参考スコア（独自算出の注目度）: 1.0152838128195467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given pairwise comparisons between multiple items, how to rank them so that the ranking matches the observations? This problem, known as rank aggregation, has found many applications in sports, recommendation systems, and other web applications. As it is generally NP-hard to find a global ranking that minimizes the mismatch (known as the Kemeny optimization), we focus on the Erd\"os-R\'enyi outliers (ERO) model for this ranking problem. Here, each pairwise comparison is a corrupted copy of the true score difference. We investigate spectral ranking algorithms that are based on unnormalized and normalized data matrices. The key is to understand their performance in recovering the underlying scores of each item from the observed data. This reduces to deriving an entry-wise perturbation error bound between the top eigenvectors of the unnormalized/normalized data matrix and its population counterpart. By using the leave-one-out technique, we provide a sharper $\ell_{\infty}$-norm perturbation bound of the eigenvectors and also derive an error bound on the maximum displacement for each item, with only $\Omega(n\log n)$ samples. Our theoretical analysis improves upon the state-of-the-art results in terms of sample complexity, and our numerical experiments confirm these theoretical findings.
• Abstract（参考訳）: 複数の項目間のペアワイズ比較を与えられた場合、ランキングが観測値と一致するようにランク付けする方法? この問題はランクアグリゲーションと呼ばれ、スポーツ、レコメンデーションシステム、その他のウェブアプリケーションで多くの応用が見られた。 ミスマッチを最小化するグローバルランキング(ケメニー最適化として知られる)を見つけるのは通常np困難であるため、このランキング問題に対するerd\"os-r\'enyi outliers (ero)モデルに焦点を当てる。 ここで、各ペア比較は真のスコア差の破損したコピーである。 非正規化および正規化データ行列に基づくスペクトルランキングアルゴリズムについて検討する。 重要なのは,観測データから各項目の下位スコアを回復する上で,そのパフォーマンスを理解することだ。 これにより、非正規化/正規化データ行列の最上位固有ベクトルとその集団行列との間の入射摂動誤差が導かれる。 leave-one-out技術を用いることで、固有ベクトルのよりシャープな$\ell_{\infty}$-norm摂動境界を提供し、各アイテムの最大変位にバインドされた誤差を導出し、わずか$\omega(n\log n)$のサンプルだけを得る。 我々の理論解析は, 試料の複雑さの観点から, 最先端の結果を改良し, 数値実験によりこれらの理論的知見が裏付けられる。

関連論文リスト

• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property [11.332742187228524]
  本研究では,あるユーザが質問(項目)をし,他のユーザが回答(ラベル)を返却するクラウドソース環境での一般的な問題を解析する。 我々はこの問題を「能力発見」と呼び、「真理発見」というよりよく研究された問題とのつながりと双対性を強調する。 実験の結果,我々の新しいHITSは,最先端の真理発見手法と比較して,精度の高いユーザランキングを生成することがわかった。
  論文  参考訳（メタデータ） (2023-12-21T18:47:17Z)
• Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models [63.714662435555674]
  大規模言語モデル(LLM)は、文脈の使い方に位置バイアスを示す。 我々は,ブラックボックスLLMのランキングリスト出力に対して,自己整合性(permutation self-consistency)を提案する。 LLaMA v2 (70B) では GPT-3.5 では 7-18% , LLaMA v2 (70B) では 8-16% である。
  論文  参考訳（メタデータ） (2023-10-11T17:59:02Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Lagrangian Inference for Ranking Problems [18.70913621061314]
  両比較の結果のベルヌーイ分布を決定する正の選好スコアが各項目に割り当てられるブラッドリー・テリー・ルーシ(BTL)モデルについて考察する。 提案手法は,BTLモデルの一般的なランク付け特性を推定することを目的としている。 フレームワークを複数のテスト問題に一般化し、偽発見率(FDR)を制御し、上位のK$アイテムを推測する手法を適用する。
  論文  参考訳（メタデータ） (2021-10-01T01:16:25Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Optimal Full Ranking from Pairwise Comparisons [16.852801934478475]
  ランキングの最小最大レートは、問題の信号対雑音比の大きさに応じて指数レートと率の間の遷移を示す。 ミニマックスレートを達成するために,まず,n$ プレーヤーを類似したスキルのグループに分割し,次に各グループ内のローカル mle を計算する分割・コンクエストランキングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-21T03:34:44Z)
• PiRank: Learning To Rank via Differentiable Sorting [85.28916333414145]
  ランク付けのための新しい分類可能なサロゲートであるPiRankを提案する。 ピランクは所望の指標をゼロ温度の限界で正確に回収する。
  論文  参考訳（メタデータ） (2020-12-12T05:07:36Z)
• Adversarial Crowdsourcing Through Robust Rank-One Matrix Completion [17.615174152419133]
  明らかな記載が損なわれているかは分かっていない。 提案アルゴリズムは,ErdHos-R'enyiランダムグラフを用いて,抽出されたエントリの集合が与えられたときに最適であることを示す。 特に, 提案アルゴリズムは, ErdHos-R'enyiランダムグラフを用いて, 与えられたエントリの集合が与えられたときに最適であることを示す。
  論文  参考訳（メタデータ） (2020-10-23T06:23:20Z)
• Partial Recovery for Top-$k$ Ranking: Optimality of MLE and Sub-Optimality of Spectral Method [20.81132428224778]
  上位ランクのミスの割合で部分回復誤差を特徴づける。 また、最上位のk$セットの正確な回復のために最適な信号対雑音比条件を導出する。
  論文  参考訳（メタデータ） (2020-06-30T02:32:42Z)
• Towards Discriminability and Diversity: Batch Nuclear-norm Maximization under Label Insufficient Situations [154.51144248210338]
  Batch Nuclear-norm Maximization (BNM) は、学習シナリオのラベルが不十分な場合の学習を促進するために提案されている。 BNMはライバルより優れており、既存のよく知られた手法でうまく機能する。
  論文  参考訳（メタデータ） (2020-03-27T05:04:24Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。