論文の概要: Partial-Adaptive Submodular Maximization
- arxiv url: http://arxiv.org/abs/2111.00986v1
- Date: Mon, 1 Nov 2021 14:48:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-02 19:54:29.185633
- Title: Partial-Adaptive Submodular Maximization
- Title(参考訳): 部分適応部分モジュラー最大化
- Authors: Shaojie Tang and Jing Yuan
- Abstract要約: 適応部分モジュラー問題に関するほとんどの研究は、完全に適応的な設定に焦点を当てている。
本稿では,バッチ内で複数の選択を同時に行うことができる部分適応部分モジュラーの問題について検討する。
我々のアプローチは、過去の選択から観察を待つ時間を削減するとともに、適応性の利点を享受します。
- 参考スコア(独自算出の注目度): 28.24164217929491
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The goal of a typical adaptive sequential decision making problem is to
design an interactive policy that selects a group of items sequentially, based
on some partial observations, to maximize the expected utility. It has been
shown that the utility functions of many real-world applications, including
pooled-based active learning and adaptive influence maximization, satisfy the
property of adaptive submodularity. However, most of existing studies on
adaptive submodular maximization focus on the fully adaptive setting, i.e., one
must wait for the feedback from \emph{all} past selections before making the
next selection. Although this approach can take full advantage of feedback from
the past to make informed decisions, it may take a longer time to complete the
selection process as compared with the non-adaptive solution where all
selections are made in advance before any observations take place. In this
paper, we explore the problem of partial-adaptive submodular maximization where
one is allowed to make multiple selections in a batch simultaneously and
observe their realizations together. Our approach enjoys the benefits of
adaptivity while reducing the time spent on waiting for the observations from
past selections. To the best of our knowledge, no results are known for
partial-adaptive policies for the non-monotone adaptive submodular maximization
problem. We study this problem under both cardinality constraint and knapsack
constraints, and develop effective and efficient solutions for both cases. We
also analyze the batch query complexity, i.e., the number of batches a policy
takes to complete the selection process, of our policy under some additional
assumptions.
- Abstract(参考訳): 典型的な適応的逐次決定問題の目標は、いくつかの部分的な観測に基づいて項目群を逐次選択する対話的ポリシーを設計し、期待される有用性を最大化することである。
プール型能動学習や適応的影響最大化を含む実世界の多くのアプリケーションの有用性は適応的部分モジュラリティの性質を満たすことが示されている。
しかしながら、適応部分モジュラー最大化に関する既存の研究のほとんどは、完全な適応設定に焦点を当てており、次の選択を行う前に、次の選択からフィードバックを待つ必要がある。
このアプローチは過去のフィードバックを最大限に活用して情報的決定を行うことができるが、すべての選択が事前に行われる非適応的なソリューションと比較して、選択プロセスを完成させるのに長い時間がかかるかもしれない。
本稿では,バッチ内で複数の選択を同時に行い,それらの実現を同時に観察できる部分適応部分モジュラー最大化の問題について検討する。
我々のアプローチは、過去の選択から観察を待つ時間を削減するとともに、適応性の利点を享受します。
最善の知識では、非単調適応部分モジュラー最大化問題に対する部分適応ポリシーは知られていない。
我々はこの問題を,濃度制約とknapsack制約の両方の下で検討し,どちらの場合においても効果的かつ効率的な解法を開発する。
我々はまた、バッチクエリの複雑さ、すなわち、ポリシーが選択プロセスの完了に要するバッチの数を、いくつかの仮定の下で分析する。
関連論文リスト
- Evolutionary Solution Adaption for Multi-Objective Metal Cutting Process
Optimization [59.45414406974091]
我々は,従来の最適化タスクから解を転送するアルゴリズムの能力を研究することのできる,システムの柔軟性のためのフレームワークを提案する。
NSGA-IIの柔軟性を2つの変種で検討し,1)2つのタスクの解を同時に最適化し,より適応性が高いと期待されるソース間の解を得る,2)活性化あるいは非活性化の異なる可能性に対応する能動的非アクティブなジェノタイプについて検討した。
その結果,標準NSGA-IIによる適応は目標目標への最適化に必要な評価回数を大幅に削減し,提案した変種は適応コストをさらに向上することがわかった。
論文 参考訳(メタデータ) (2023-05-31T12:07:50Z) - Generative Slate Recommendation with Reinforcement Learning [49.75985313698214]
強化学習アルゴリズムは、レコメンデータシステムのユーザエンゲージメントを最適化するために使用することができる。
しかし、RLアプローチはスレートレコメンデーションシナリオでは難解である。
この設定では、アクションはアイテムの組み合わせを含むことができるスレートに対応する。
本研究では,変分オートエンコーダによって学習された連続低次元ラテント空間におけるスレートの符号化を提案する。
我々は、(i)以前の作業で要求される仮定を緩和し、(ii)完全なスレートをモデル化することで、アクション選択の品質を向上させることができる。
論文 参考訳(メタデータ) (2023-01-20T15:28:09Z) - Balancing Utility and Fairness in Submodular Maximization (Technical
Report) [27.20340546154524]
実用性と公平性のバランスをとるために,emphBi Maxim Submodularization (BSM) と呼ばれる新しい問題を提案する。
BSMは任意の定数係数で近似できないため、効率的なインスタンス依存近似スキームの設計に焦点をあてる。
論文 参考訳(メタデータ) (2022-11-02T09:38:08Z) - Streaming Adaptive Submodular Maximization [19.29174615532181]
実用関数の新しいクラス、半政治的な部分モジュラー関数を導入する。
本研究では,ストリームベース環境下での半政治的部分モジュラ関数の最大化に有効なアルゴリズムの開発を行う。
論文 参考訳(メタデータ) (2022-08-17T02:05:10Z) - Group Equality in Adaptive Submodular Maximization [13.619980548779687]
非適応的条件と適応的条件の両方で群等式制約を受ける古典的部分モジュラー問題について検討する。
この問題に対する最初の定数近似アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-07-07T15:12:02Z) - Fast Feature Selection with Fairness Constraints [49.142308856826396]
モデル構築における最適特徴の選択に関する基礎的問題について検討する。
この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。
適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。
提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
論文 参考訳(メタデータ) (2022-02-28T12:26:47Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳(メタデータ) (2022-01-28T05:53:28Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
提案手法は, 事前決定の順序に対して, スパース変化のみを必要とする伝達問題に対して, 政策段階の手法よりも, より標本効率が高いことを示す。
我々は最近提案された社会的意思決定の枠組みをマルコフ決定プロセスよりもよりきめ細かい形式主義として一般化する。
論文 参考訳(メタデータ) (2021-06-28T21:29:13Z) - Learning MDPs from Features: Predict-Then-Optimize for Sequential
Decision Problems by Reinforcement Learning [52.74071439183113]
我々は、強化学習を通して解決された逐次決定問題(MDP)の文脈における予測列最適化フレームワークについて検討した。
2つの重要な計算課題は、意思決定中心の学習をMDPに適用することである。
論文 参考訳(メタデータ) (2021-06-06T23:53:31Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint [26.171841086317574]
ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
論文 参考訳(メタデータ) (2021-04-10T20:11:11Z) - Adaptive Cascade Submodular Maximization [19.29174615532181]
本研究では,適応条件下でのカスケード部分モジュラー問題について検討する。
本研究の目的は,選択項目の有効性を最大化するために,選択項目の最適シーケンスを特定することである。
論文 参考訳(メタデータ) (2020-07-07T16:21:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。