論文の概要: 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制約の両方の下で検討し,どちらの場合においても効果的かつ効率的な解法を開発する。
我々はまた、バッチクエリの複雑さ、すなわち、ポリシーが選択プロセスの完了に要するバッチの数を、いくつかの仮定の下で分析する。
関連論文リスト
- Learning Joint Models of Prediction and Optimization [56.04498536842065]
Predict-Then-Thenフレームワークは、機械学習モデルを使用して、最適化問題の未知のパラメータを、解決前の機能から予測する。
本稿では,共同予測モデルを用いて観測可能特徴から最適解を直接学習する手法を提案する。
論文 参考訳（メタデータ） (2024-09-07T19:52:14Z) - An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
まず最適化モデルを構築し,非単調な選好をモデル化する。
本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。
2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
論文 参考訳（メタデータ） (2024-09-04T14:36:20Z) - Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
オンライン報酬指標の偏りのないオフライン推定を最適化する意思決定ポリシーを学習することを目指している。
学習シナリオにおける同値性に基づく単一のフレームワークを提案する。
我々のフレームワークは、分散最適非バイアス推定器の特徴付けを可能にし、それに対する閉形式解を提供する。
論文 参考訳（メタデータ） (2024-05-09T12:52:22Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。