論文の概要: Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality

• arxiv url: http://arxiv.org/abs/2304.06821v1
• Date: Thu, 13 Apr 2023 21:14:30 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-17 15:09:18.711131
• Title: Ranking from Pairwise Comparisons in General Graphs and Graphs with Locality
• Title（参考訳）: 一般グラフと局所性グラフの対関係比較によるランク付け
• Authors: Yanxi Chen
• Abstract要約: 本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較によるランキング問題について検討する。 十分に多くのサンプルを用いて,Cram'er-Rao の下界と一致するエントリワイズ推定誤差が得られることを示す。 我々は、最も広いサンプルを持つ体制においても、同様の保証を確実に達成できる分割対コンカマーのアルゴリズムについて検討する。
• 参考スコア（独自算出の注目度）: 3.1219977244201056
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This technical report studies the problem of ranking from pairwise comparisons in the classical Bradley-Terry-Luce (BTL) model, with a focus on score estimation. For general graphs, we show that, with sufficiently many samples, maximum likelihood estimation (MLE) achieves an entrywise estimation error matching the Cram\'er-Rao lower bound, which can be stated in terms of effective resistances; the key to our analysis is a connection between statistical estimation and iterative optimization by preconditioned gradient descent. We are also particularly interested in graphs with locality, where only nearby items can be connected by edges; our analysis identifies conditions under which locality does not hurt, i.e. comparing the scores between a pair of items that are far apart in the graph is nearly as easy as comparing a pair of nearby items. We further explore divide-and-conquer algorithms that can provably achieve similar guarantees even in the regime with the sparsest samples, while enjoying certain computational advantages. Numerical results validate our theory and confirm the efficacy of the proposed algorithms.
• Abstract（参考訳）: 本稿では,古典的Bradley-Terry-Luceモデル(BTL)のペア比較による順位付けの問題について,スコア推定に焦点をあてる。 一般グラフでは, 十分なサンプル数で最大確率推定 (mle) が, 実効的抵抗の観点で述べることのできる, cram\'er-rao 下界に適合する入射的推定誤差を達成することを示し, この解析の鍵となるのは, 統計的推定と事前条件付き勾配降下による反復最適化との相関性である。 また、局所性のあるグラフにも特に関心があり、近傍の項目のみをエッジで繋げることができる。この分析では、局所性が傷つくことのない条件、すなわち、グラフ内で遠く離れた項目のペアを比較することは、近傍の項目を比較するのと同じくらい簡単である。 我々はさらに,計算の利点を享受しながら,最もスパースなサンプルでも同様の保証を実現できる分割・探索アルゴリズムについて検討する。 この理論を検証し,提案アルゴリズムの有効性を検証した。

関連論文リスト

• Separation-based distance measures for causal graphs [15.37737222790121]
  最先端因果探索法は単一の因果グラフを出力するのではなく、それらの等価クラス(MEC)を出力する。 本稿では,分離距離の差が評価に適さないような距離の付加的な測定法を提案する。 我々は,既存の比較指標の違いを明らかにする実験と,おもちゃの例を用いて理論的解析を補完する。
  論文  参考訳（メタデータ） (2024-02-07T15:36:53Z)
• Spectral Ranking Inferences based on General Multiway Comparisons [7.222667862159246]
  本研究では,2段階のスペクトル法により,最大近似エスタと同じバニラ効率が得られることを示す。 有効な2サンプルランク試験法が提案されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2023-08-05T16:31:32Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  グラフに基づく相対的制約のない最小二乗重要度フィッティング(GRULSIF) 我々はこの考え方を、グラフベースの相対的非制約最小二乗重要度フィッティング(GRULSIF)と呼ばれる具体的な非パラメトリック手法で開発する。 我々は、ノード当たりの観測回数、グラフのサイズ、およびグラフ構造がタスク間の類似性をどの程度正確にエンコードしているかといった変数が果たす役割を強調する、協調的なアプローチの収束率を導出する。
  論文  参考訳（メタデータ） (2022-05-28T15:37:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• The Performance of the MLE in the Bradley-Terry-Luce Model in $\ell_{\infty}$-Loss and under General Graph Topologies [76.61051540383494]
  我々はBradley-Terry-Luceモデルの$ell_infty$推定誤差に関する新しい一般上限を導出する。 導出された境界は良好に機能し、場合によっては既知の結果よりもシャープであることを示す。
  論文  参考訳（メタデータ） (2021-10-20T23:46:35Z)
• Task Affinity with Maximum Bipartite Matching in Few-Shot Learning [28.5184196829547]
  本稿では,1つのタスクの知識を活用して,別のタスクを学習する複雑性を表現するための非対称親和性スコアを提案する。 特に、このスコアを用いて、テストデータに関連するトレーニングデータラベルを見つけ、発見した関連するデータを活用して、いくつかのショットモデルをエピソード的に微調整する。
  論文  参考訳（メタデータ） (2021-10-05T23:15:55Z)
• Optimal detection of the feature matching map in presence of noise and outliers [0.0]
  雑音観測から2組の$d$次元ベクトル間のマッチング写像を求める問題を考える。 一致する写像は射影であり、第二集合のベクトルが十分に分離されている場合に限り一貫して推定できる。
  論文  参考訳（メタデータ） (2021-06-13T17:08:29Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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