論文の概要: The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons

• arxiv url: http://arxiv.org/abs/2007.03133v2
• Date: Thu, 29 Jul 2021 19:41:20 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-13 01:51:47.042003
• Title: The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons
• Title（参考訳）: Pairwise Comparisons による Best-k$ Items Selection のサンプル複雑度
• Authors: Wenbo Ren, Jia Liu, Ness B. Shroff
• Abstract要約: ペア比較から選択したアクティブベスト$k$アイテムに対するサンプル複雑性(いわゆる比較数)バウンダリについて検討する。 学習者はいつでも、過去の観察に基づいて比較する一対のアイテムを適応的に選択することができる。 PACベストアイテム選択アルゴリズムに基づく2つのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 33.66975831989357
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper studies the sample complexity (aka number of comparisons) bounds for the active best-$k$ items selection from pairwise comparisons. From a given set of items, the learner can make pairwise comparisons on every pair of items, and each comparison returns an independent noisy result about the preferred item. At any time, the learner can adaptively choose a pair of items to compare according to past observations (i.e., active learning). The learner's goal is to find the (approximately) best-$k$ items with a given confidence, while trying to use as few comparisons as possible. In this paper, we study two problems: (i) finding the probably approximately correct (PAC) best-$k$ items and (ii) finding the exact best-$k$ items, both under strong stochastic transitivity and stochastic triangle inequality. For PAC best-$k$ items selection, we first show a lower bound and then propose an algorithm whose sample complexity upper bound matches the lower bound up to a constant factor. For the exact best-$k$ items selection, we first prove a worst-instance lower bound. We then propose two algorithms based on our PAC best items selection algorithms: one works for $k=1$ and is sample complexity optimal up to a loglog factor, and the other works for all values of $k$ and is sample complexity optimal up to a log factor.
• Abstract（参考訳）: 本稿では,ペアワイズ比較から選択したベストk$項目のサンプル複雑性(すなわち比較数)について検討する。 与えられたアイテムセットから、学習者は各アイテムに対してペアワイズ比較を行い、各比較は好みのアイテムについて独立したノイズ結果を返す。 いつでも、学習者は過去の観察(すなわちアクティブラーニング)に基づいて比較するアイテムのペアを適応的に選択することができる。 学習者のゴールは、可能な限り少ない比較を行おうとしながら、信頼度のある(およそ)$kのアイテムを見つけることである。 本稿では,2つの問題について考察する。 (i)おそらくほぼ正しい(pac)最良の$k$アイテムを見つけること、及び (II)強い確率推移性と確率三角形の不等式の下で、正確なk$の項目を見つける。 PACベスト-k$アイテム選択の場合、まず下界を示し、次に、サンプル複雑性上界が下界と定数係数に一致するアルゴリズムを提案する。 正確な$kのアイテム選択のために、まず最低値の低い境界を証明します。 次に、PACベストアイテム選択アルゴリズムに基づく2つのアルゴリズムを提案する。1つは$k=1$で、もう1つはloglog factorで最適で、もう1つは$k$で最適で、サンプル複雑性はlog factorで最適である。

関連論文リスト

• Active Preference Learning for Ordering Items In- and Out-of-sample [7.0774164818430565]
  アイテムペアを積極的にサンプリングすることで、正確な順序付けを学ぶのに必要なアノテーションの数を減らすことができる。 多くのアルゴリズムはアイテム間の共有構造を無視している。 また、比較におけるノイズがアイテムペア間でどのように変化するかは無視することが一般的である。
  論文  参考訳（メタデータ） (2024-05-05T21:44:03Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Sorting with Predictions [1.7042264000899532]
  学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。 我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。 比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
  論文  参考訳（メタデータ） (2023-11-01T18:00:03Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Ranking Inferences Based on the Top Choice of Multiway Comparisons [2.468314282946207]
  本稿では、各試行においてランダムに選択された項目のうち、上位選択の観測データに基づいて、$n$アイテムのランキングを考察する。 これは、M$-wayランキングに対するプラケット=リュックモデルの有用な修正であり、最高選択のみを観測し、M=2$に対応する祝賀されたブラッドリー=テリー=リュックモデルの延長である。
  論文  参考訳（メタデータ） (2022-11-22T02:34:52Z)
• Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise Comparisons [85.5955376526419]
  ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。 本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。 提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
  論文  参考訳（メタデータ） (2021-10-08T13:51:55Z)
• Sampling from a $k$-DPP without looking at all items [58.30573872035083]
  カーネル関数とサブセットサイズ$k$が与えられた場合、我々のゴールは、サブセットによって誘導されるカーネル行列の行列式に比例する確率を持つ$n$アイテムから$k$をサンプリングすることである(つまり$k$-DPP)。 既存の$k$-DPPサンプリングアルゴリズムは、すべての$n$アイテムを複数回パスする高価な前処理ステップを必要とするため、大規模なデータセットでは利用できない。 そこで我々は, 十分大きなデータの均一なサンプルを適応的に構築し, より小さな$k$のアイテムを効率よく生成するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-06-30T16:40:44Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Best-item Learning in Random Utility Models with Subset Choices [40.17224226373741]
  我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。 そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。 一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-19T03:57:16Z)

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

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