論文の概要: Byzantine Spectral Ranking

• arxiv url: http://arxiv.org/abs/2211.07902v1
• Date: Tue, 15 Nov 2022 05:18:19 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-16 15:19:25.388242
• Title: Byzantine Spectral Ranking
• Title（参考訳）: ビザンチンスペクトルランク付け
• Authors: Arnhav Datar, Arun Rajkumar, John Augustine
• Abstract要約: 本研究では,一組の項目に対する有権者のペアワイズ比較を集約することで,グローバルランキングの獲得を目標とするランクアグリゲーションの問題について検討する。 我々はビザンツのスペクトルランク付けアルゴリズムを導入し、良質な有権者数がビザンツの有権者数を上回った場合に信頼性の高いランク付けを行う。
• 参考スコア（独自算出の注目度）: 3.4272203252843294
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of rank aggregation where the goal is to obtain a global ranking by aggregating pair-wise comparisons of voters over a set of items. We consider an adversarial setting where the voters are partitioned into two sets. The first set votes in a stochastic manner according to the popular score-based Bradley-Terry-Luce (BTL) model for pairwise comparisons. The second set comprises malicious Byzantine voters trying to deteriorate the ranking. We consider a strongly-adversarial scenario where the Byzantine voters know the BTL scores, the votes of the good voters, the algorithm, and can collude with each other. We first show that the popular spectral ranking based Rank-Centrality algorithm, though optimal for the BTL model, does not perform well even when a small constant fraction of the voters are Byzantine. We introduce the Byzantine Spectral Ranking Algorithm (and a faster variant of it), which produces a reliable ranking when the number of good voters exceeds the number of Byzantine voters. We show that no algorithm can produce a satisfactory ranking with probability > 1/2 for all BTL weights when there are more Byzantine voters than good voters, showing that our algorithm works for all possible population fractions. We support our theoretical results with experimental results on synthetic and real datasets to demonstrate the failure of the Rank-Centrality algorithm under several adversarial scenarios and how the proposed Byzantine Spectral Ranking algorithm is robust in obtaining good rankings.
• Abstract（参考訳）: 本研究では,一組の項目に対する有権者のペアワイズ比較を集約することで,グローバルランキングの獲得を目標とするランクアグリゲーションの問題を検討する。 我々は、有権者を2つのセットに分割する敵の設定を考える。 最初の投票は、ペア比較のための人気スコアベースのBradley-Terry-Luce(BTL)モデルに従って確率的に設定された。 第2セットは悪質なビザンツ人有権者がランクを低下させようとしている。 我々は、ビザンツの有権者がBTLのスコア、良い有権者の投票、アルゴリズム、そして互いに衝突できるような強い対立的なシナリオを考える。 まず、BTLモデルに最適ではあるが、人気のあるスペクトルランクに基づくランクセントラリティアルゴリズムは、有権者のごく一部がビザンチン系であっても、うまく機能しないことを示す。 我々は,ビザンツの投票者数がビザンツの投票者数を超えると,信頼性の高いランキングを生成するビザンツのスペクトルランク付けアルゴリズム(およびそれより早いバリエーション)を紹介する。 ベザンチンの有権者がよい有権者よりも多い場合、BTLの重みに確率 > 1/2 で満足できるランクを付けるアルゴリズムは存在しないことを示し、我々のアルゴリズムが全ての可能な人口比率で機能することを示している。 提案手法は,いくつかの逆シナリオ下でのランク・セントラリティアルゴリズムの故障と,Byzantine Spectral Rankingアルゴリズムが優れたランキングを得る上でいかに堅牢かを示すために,合成データセットと実データセットに関する実験結果をサポートする。

関連論文リスト

• Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  このアルゴリズムは,アクションクラスのサイズが指数関数的に大きい場合でも,最良のアクションを識別できる最初のアルゴリズムである。 CSAアルゴリズムの誤差確率の上限は指数の対数係数までの下界と一致することを示す。 提案手法を従来手法と実験的に比較し,アルゴリズムの性能が向上したことを示す。
  論文  参考訳（メタデータ） (2023-10-24T09:47:32Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Bipartite Ranking Fairness through a Model Agnostic Ordering Adjustment [54.179859639868646]
  本稿では,二部類ランキングにおける公平性を実現するためのモデルに依存しない後処理フレームワークxOrderを提案する。 xOrderは、教師なしおよび教師なしの公正度メトリックを含む、さまざまな分類モデルとランキングフェアネスメトリクスと互換性がある。 提案アルゴリズムを,4つのベンチマークデータセットと2つの実世界の患者電子健康記録リポジトリ上で評価した。
  論文  参考訳（メタデータ） (2023-07-27T07:42:44Z)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。 提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
  論文  参考訳（メタデータ） (2022-10-11T13:21:59Z)
• Byzantine-Robust Online and Offline Distributed Reinforcement Learning [60.970950468309056]
  本稿では,複数のエージェントが環境を探索し,その経験を中央サーバを通じて伝達する分散強化学習環境について考察する。 エージェントの$alpha$-fractionは敵対的であり、任意の偽情報を報告することができる。 我々は、これらの対立エージェントの存在下で、マルコフ決定プロセスの根底にある準最適政策を特定することを模索する。
  論文  参考訳（メタデータ） (2022-06-01T00:44:53Z)
• Robust Voting Rules from Algorithmic Robust Statistics [25.313563663123354]
  サンプルの一定割合が任意に破損しても,精度よく中央ランクを推定できるアルゴリズムを提案する。 我々の研究は、アルゴリズムによる頑健な統計から、投票や情報集約における中心的な推論問題への視点の自然な注入と考えることができる。
  論文  参考訳（メタデータ） (2021-12-13T02:30:26Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)
• Guaranteed Fixed-Confidence Best Arm Identification in Multi-Armed Bandit [1.5469452301122177]
  我々は,n個体群(腕)が最大の平均値を持つ適応サンプリングによる探索の問題を考える。 本研究の目的は, できるだけ少ない観測値を用いて, 最良集団を最小限の信頼度で識別するルールを決定することである。
  論文  参考訳（メタデータ） (2021-06-12T20:05:29Z)
• Concentric mixtures of Mallows models for top-$k$ rankings: sampling and identifiability [0.0]
  上位ランクの2つのMallowsモデルの混合について検討する。 我々はMallows Top-k$ランキングの効率的なサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:00:37Z)
• User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets [28.537935838669423]
  ユーザフェアネス、アイテムフェアネス、多様性は根本的に異なる概念であることを示す。 3つのデシラタを明示的に強制する最初のランク付けアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-04T02:53:09Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)

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

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