論文の概要: On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting
- arxiv url: http://arxiv.org/abs/2204.05742v1
- Date: Mon, 11 Apr 2022 16:31:37 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-13 14:30:57.850492
- Title: On Top-$k$ Selection from $m$-wise Partial Rankings via Borda Counting
- Title(参考訳): ボルダ数による$m$-wise部分ランキングの上位$k$選択について
- Authors: Wenjing Chen, Ruida Zhou, Chao Tian, Cong Shen
- Abstract要約: 非パラメトリックモデルを用いてボルダカウントアルゴリズムの性能を解析する。
Delta_k$が特定の値より大きい場合、アルゴリズムが選択した上位$k$は、ほぼ確実に正確であることを示す。
- 参考スコア(独自算出の注目度): 23.290889341552898
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We analyze the performance of the Borda counting algorithm in a
non-parametric model. The algorithm needs to utilize probabilistic rankings of
the items within $m$-sized subsets to accurately determine which items are the
overall top-$k$ items in a total of $n$ items. The Borda counting algorithm
simply counts the cumulative scores for each item from these partial ranking
observations. This generalizes a previous work of a similar nature by Shah et
al. using probabilistic pairwise comparison data. The performance of the Borda
counting algorithm critically depends on the associated score separation
$\Delta_k$ between the $k$-th item and the $(k+1)$-th item. Specifically, we
show that if $\Delta_k$ is greater than certain value, then the top-$k$ items
selected by the algorithm is asymptotically accurate almost surely; if
$\Delta_k$ is below certain value, then the result will be inaccurate with a
constant probability. In the special case of $m=2$, i.e., pairwise comparison,
the resultant bound is tighter than that given by Shah et al., leading to a
reduced gap between the error probability upper and lower bounds. These results
are further extended to the approximate top-$k$ selection setting. Numerical
experiments demonstrate the effectiveness and accuracy of the Borda counting
algorithm, compared with the spectral MLE-based algorithm, particularly when
the data does not necessarily follow an assumed parametric model.
- Abstract(参考訳): 本研究では,非パラメトリックモデルにおけるボルダ計数アルゴリズムの性能解析を行う。
このアルゴリズムは、$m$サイズのサブセット内のアイテムの確率的ランキングを利用して、合計$n$のアイテムの中で、どのアイテムが上位k$のアイテムであるかを正確に決定する必要がある。
ボルダカウントアルゴリズムは、これらの部分的なランキング観測から各項目の累積スコアを単純にカウントする。
これは、確率的対比較データを用いて、Shahらによる同様の性質の以前の研究を一般化する。
bordaカウントアルゴリズムの性能は、関連するスコア分離 $\delta_k$ が $k$-th 項目と $(k+1)$-th 項目の間で決定的に依存する。
具体的には、$\Delta_k$が特定の値より大きい場合、アルゴリズムによって選択された上位$k$アイテムはほぼ確実に漸近的に正確であることを示し、もし$\Delta_k$が特定の値以下であれば、結果は一定の確率で不正確なものになる。
m=2$の特別な場合、すなわち対比較の場合、結果のバウンドはシャーらによって与えられるバウンドよりも厳密であり、エラー確率の上限と下限の間のギャップを小さくする。
これらの結果は、近似のトップ$k$選択設定にさらに拡張される。
数値実験により、ボルダカウントアルゴリズムの有効性と精度をスペクトルMLEベースのアルゴリズムと比較し、特にデータが仮定されたパラメトリックモデルに従わない場合と比較した。
関連論文リスト
- Top-$K$ ranking with a monotone adversary [19.871049853222132]
比較グラフがランダムに生成され、敵が任意のエッジを追加することができるシナリオを考える。
統計学者の目標は、ペア比較に基づいて、上位$K$の推奨項目を正確に識別することである。
本論文の主な貢献は, ほぼ最適サンプル複雑性を実現するための重み付き最大極大推定器(MLE)を開発することである。
論文 参考訳(メタデータ) (2024-02-12T06:57:34Z) - Sorting with Predictions [1.7042264000899532]
学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。
我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。
比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
論文 参考訳(メタデータ) (2023-11-01T18:00:03Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳(メタデータ) (2023-06-29T14:57:56Z) - Ranking Inferences Based on the Top Choice of Multiway Comparisons [2.468314282946207]
本稿では、各試行においてランダムに選択された項目のうち、上位選択の観測データに基づいて、$n$アイテムのランキングを考察する。
これは、M$-wayランキングに対するプラケット=リュックモデルの有用な修正であり、最高選択のみを観測し、M=2$に対応する祝賀されたブラッドリー=テリー=リュックモデルの延長である。
論文 参考訳(メタデータ) (2022-11-22T02:34:52Z) - List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。
特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。
Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
論文 参考訳(メタデータ) (2022-06-10T17:38:18Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳(メタデータ) (2020-11-19T17:21:37Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳(メタデータ) (2020-04-16T19:16:38Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。