論文の概要: Best-item Learning in Random Utility Models with Subset Choices
- arxiv url: http://arxiv.org/abs/2002.07994v1
- Date: Wed, 19 Feb 2020 03:57:16 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 12:40:29.995003
- Title: Best-item Learning in Random Utility Models with Subset Choices
- Title（参考訳）: サブセット選択を考慮したランダムユーティリティモデルにおけるベストプラクティス学習
- Authors: Aadirupa Saha and Aditya Gopalan
- Abstract要約: 我々は、$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて、$n$アイテムのプールから最も価値のあるアイテムをPACで学習する問題を考察する。
そのようなRUMの新たな性質を最小限の利点と呼び、アイテムのペアを分離する複雑さを特徴づけるのに役立つ。
一般RUMの学習アルゴリズムとして,アイテムの相対的な数と階層的除去と,新しいPACサンプルの複雑性保証を併用した学習アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 40.17224226373741
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of PAC learning the most valuable item from a pool of
$n$ items using sequential, adaptively chosen plays of subsets of $k$ items,
when, upon playing a subset, the learner receives relative feedback sampled
according to a general Random Utility Model (RUM) with independent noise
perturbations to the latent item utilities. We identify a new property of such
a RUM, termed the minimum advantage, that helps in characterizing the
complexity of separating pairs of items based on their relative win/loss
empirical counts, and can be bounded as a function of the noise distribution
alone. We give a learning algorithm for general RUMs, based on pairwise
relative counts of items and hierarchical elimination, along with a new PAC
sample complexity guarantee of $O(\frac{n}{c^2\epsilon^2} \log
\frac{k}{\delta})$ rounds to identify an $\epsilon$-optimal item with
confidence $1-\delta$, when the worst case pairwise advantage in the RUM has
sensitivity at least $c$ to the parameter gaps of items. Fundamental lower
bounds on PAC sample complexity show that this is near-optimal in terms of its
dependence on $n,k$ and $c$.
- Abstract（参考訳）: PAC学習の課題は,サブセットを再生する際,RUM(Random Utility Model)によってサンプリングされた相対的なフィードバックを受け取り,遅延したアイテムユーティリティにノイズを分散させることによって,$k$アイテムのサブセットの逐次的かつ適応的に選択されたプレイを用いて,$n$アイテムのプールから最も価値の高いアイテムを学習することにある。
このようなRUMの新たな特性を最小限の利点と呼び、相対的な勝利/損失経験数に基づいてアイテムのペアを分離することの複雑さを特徴づけ、ノイズ分布のみの関数として有界化することができる。
一般的なrumsの学習アルゴリズムは、アイテムのペアワイズ相対数と階層的除去に基づいており、新しいpacサンプル複雑性保証である$o(\frac{n}{c^2\epsilon^2} \log \frac{k}{\delta})$ roundsを用いて、rumにおける最悪のペアワイズアドバンテージがアイテムのパラメータギャップに対して少なくとも$c$である場合に、$\epsilon$-optimalアイテムを特定する。
PACサンプルの複雑さの基本的な下限は、これは$n,k$および$c$への依存に関してほぼ最適であることを示している。
関連論文リスト
- Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - Sample Complexity Bounds for Robustly Learning Decision Lists against
Evasion Attacks [25.832511407411637]
敵機械学習の根本的な問題は、回避攻撃の存在下でどれだけのトレーニングデータが必要とされるかを定量化することである。
我々は、リプシッツ条件を満たす入力データ上の確率分布を扱う。
すべての固定$k$に対して、$k$-決定リストのクラスは、$log(n)$-bounded adversaryに対してサンプル複雑性を持つ。
論文 参考訳（メタデータ） (2022-05-12T14:40:18Z) - Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
我々は,不均衡な分類問題に対して,textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) というアンサンブル学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-01T14:10:38Z) - An Online Riemannian PCA for Stochastic Canonical Correlation Analysis [37.8212762083567]
投影行列の再パラメータ化を用いた正準相関解析(CCA)のための効率的なアルゴリズム(RSG+)を提案する。
本論文は,その特性の定式化と技術的解析に主眼を置いているが,本実験により,一般的なデータセットに対する経験的挙動が極めて有望であることが確認された。
論文 参考訳（メタデータ） (2021-06-08T23:38:29Z) - The Sample Complexity of Best-$k$ Items Selection from Pairwise
Comparisons [33.66975831989357]
ペア比較から選択したアクティブベスト$k$アイテムに対するサンプル複雑性(いわゆる比較数)バウンダリについて検討する。
学習者はいつでも、過去の観察に基づいて比較する一対のアイテムを適応的に選択することができる。
PACベストアイテム選択アルゴリズムに基づく2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-07-06T23:53:09Z) - 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) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。