論文の概要: 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データセット上で数値的に研究し、分類のためのトレーニングサブセットを選択する。
これらの例を通して,アルゴリズムの性能と,問題のみを部分モジュラーとして見る際の欠点を実証する。
関連論文リスト
- Data Summarization beyond Monotonicity: Non-monotone Two-Stage
Submodular Maximization [11.296845424426062]
2段階の準モジュラー問題の目的は、サブモジュラーである与えられた訓練関数を用いて、基底集合を減少させることである。
この問題は、データの要約を含む様々な領域に応用されている。
論文 参考訳（メタデータ） (2023-09-11T01:00:10Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Can SAM Boost Video Super-Resolution? [78.29033914169025]
単純な有効モジュールであるSAM-guidEd refinEment Module (SEEM)を提案する。
この軽量プラグインモジュールは、セマンティック・アウェア機能の生成にアテンションメカニズムを活用するように設計されている。
我々はSEEMをEDVRとBasicVSRの2つの代表的手法に適用し、最小限の実装労力で継続的に性能を向上する。
論文 参考訳（メタデータ） (2023-05-11T02:02:53Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - USER: Unified Semantic Enhancement with Momentum Contrast for Image-Text
Retrieval [115.28586222748478]
Image-Text Retrieval (ITR) は、与えられたクエリに意味のあるターゲットインスタンスを、他のモダリティから検索することを目的としている。
既存のアプローチは通常、2つの大きな制限に悩まされる。
論文 参考訳（メタデータ） (2023-01-17T12:42:58Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-07-07T15:12:02Z) - Planning with Submodular Objective Functions [118.0376288522372]
準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。
本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
論文 参考訳（メタデータ） (2020-10-22T16:55:12Z) - 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) - Streaming Submodular Maximization under a $k$-Set System Constraint [42.31117997337689]
非単調な部分モジュラーのストリーミングを非単調な部分モジュラーのストリーミングに変換する新しいフレームワークを提案する。
また,$k$ible $k$-setシステム制約を考慮したモノトンサブモジュールストリーミングのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-02-09T12:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。