論文の概要: Interactive Combinatorial Bandits: Balancing Competitivity and
Complementarity
- arxiv url: http://arxiv.org/abs/2207.03091v1
- Date: Thu, 7 Jul 2022 05:10:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-08 14:02:59.796193
- Title: Interactive Combinatorial Bandits: Balancing Competitivity and
Complementarity
- Title(参考訳): interactive combinatorial bandits: 競合性と相補性のバランス
- Authors: Adhyyan Narang, Omid Sadeghi, Lillian J Ratliff, Maryam Fazel, Jeff
Bilmes
- Abstract要約: オンライン対話型バンディット設定における非モジュール機能について検討する。
純粋に劣モジュラーなアプローチを2つの方法で拡張する。
我々は、MovieLensデータセットと、分類のためのトレーニングサブセットの選択を数値的に研究する。
- 参考スコア(独自算出の注目度): 20.31674763393817
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study non-modular function maximization in the online interactive bandit
setting. We are motivated by applications where there is a natural
complementarity between certain elements: e.g., in a movie recommendation
system, watching the first movie in a series complements the experience of
watching a second (and a third, etc.). This is not expressible using only
submodular functions which can represent only competitiveness between elements.
We extend the purely submodular approach in two ways. First, we assume that the
objective can be decomposed into the sum of monotone suBmodular and
suPermodular function, known as a BP objective. Here, complementarity is
naturally modeled by the supermodular component. We develop a UCB-style
algorithm, where at each round a noisy gain is revealed after an action is
taken that balances refining beliefs about the unknown objectives (exploration)
and choosing actions that appear promising (exploitation). Defining regret in
terms of submodular and supermodular curvature with respect to a full-knowledge
greedy baseline, we show that this algorithm achieves at most $O(\sqrt{T})$
regret after $T$ rounds of play. Second, for those functions that do not admit
a BP structure, we provide analogous regret guarantees in terms of their
submodularity ratio; this is applicable for functions that are almost, but not
quite, submodular. We numerically study the tasks of movie recommendation on
the MovieLens dataset, and selection of training subsets for classification.
Through these examples, we demonstrate the algorithm's performance as well as
the shortcomings of viewing these problems as being solely submodular.
- Abstract(参考訳): オンライン対話型バンディット設定における非モジュラ関数の最大化について検討する。
例えば、映画のレコメンデーションシステムでは、シリーズの第1の映画を見ることは、第2の映画(と第3の映画)を見る体験を補完する。
これは要素間の競合性のみを表現できる部分モジュラ関数だけでは表現できない。
純粋な部分モジュラーアプローチを2つの方法で拡張する。
まず、目的を単調部分モジュラー関数と超モジュラー関数(bp目的関数)の和に分解できると仮定する。
ここで、相補性は自然に超モジュラー成分によってモデル化される。
UCB方式のアルゴリズムを開発し、未知の目的(探索)に関する信念を補充し、有望(探索)な行動を選択するアクションを採った後、各ラウンドでノイズゲインが明らかにされる。
部分モジュラーおよび超モジュラーな曲率の点において、全知識のグリードベースラインに対する後悔を定義すると、このアルゴリズムは少なくとも$O(\sqrt{T})$後悔を$T$ラウンドで達成することを示す。
第二に、BP構造を含まない関数に対しては、その部分モジュラリティ比の点で類似の後悔の保証を与える。
映画レコメンデーションのタスクをMovieLensデータセット上で数値的に研究し、分類のためのトレーニングサブセットを選択する。
これらの例を通して,アルゴリズムの性能と,問題のみを部分モジュラーとして見る際の欠点を実証する。
関連論文リスト
- Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳(メタデータ) (2023-08-16T19:32:29Z) - Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
格子上の函数の超モジュラー階数を定義する。
準モジュラーランクを類似的に定義する。
部分モジュラ分解を用いて集合関数を最適化する。
論文 参考訳(メタデータ) (2023-05-24T02:09:28Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳(メタデータ) (2023-02-02T18:52:14Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。
本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
論文 参考訳(メタデータ) (2022-10-20T06:00:45Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳(メタデータ) (2021-06-09T01:59:55Z) - The Power of Subsampling in Submodular Maximization [51.629656762796564]
このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。
我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
論文 参考訳(メタデータ) (2021-04-06T20:25:57Z) - On Additive Approximate Submodularity [30.831477850153224]
実数値集合関数は、加法誤差で部分モジュラリティ条件を満たす場合、およそ部分モジュラリティである。
我々は、$n$要素の基底集合上で定義されるおよそ部分モジュラー函数が、部分モジュラー函数に対して$O(n2)$ポイントワイズであることを示す。
論文 参考訳(メタデータ) (2020-10-06T17:48:28Z) - Continuous Submodular Function Maximization [91.17492610120324]
連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。
連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
論文 参考訳(メタデータ) (2020-06-24T04:37:31Z) - Batch greedy maximization of non-submodular functions: Guarantees and
applications to experimental design [0.0]
非部分モジュラーな非退化集合関数の濃度制約に対するグリーディを解析する。
我々の理論的保証は、部分モジュラリティと超モジュラリティ比の組み合わせによって特徴づけられる。
論文 参考訳(メタデータ) (2020-06-03T18:58:06Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。
本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。
整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
論文 参考訳(メタデータ) (2020-06-01T22:20:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。