論文の概要: Adaptive Cascade Submodular Maximization
- arxiv url: http://arxiv.org/abs/2007.03592v2
- Date: Fri, 12 Feb 2021 21:57:43 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-12 18:21:20.697874
- Title: Adaptive Cascade Submodular Maximization
- Title（参考訳）: 適応カスケード部分モジュラ最大化
- Authors: Shaojie Tang and Jing Yuan
- Abstract要約: 本研究では,適応条件下でのカスケード部分モジュラー問題について検討する。
本研究の目的は,選択項目の有効性を最大化するために,選択項目の最適シーケンスを特定することである。
- 参考スコア（独自算出の注目度）: 19.29174615532181
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose and study the cascade submodular maximization
problem under the adaptive setting. The input of our problem is a set of items,
each item is in a particular state (i.e., the marginal contribution of an item)
which is drawn from a known probability distribution. However, we can not know
its actual state before selecting it. As compared with existing studies on
stochastic submodular maximization, one unique setting of our problem is that
each item is associated with a continuation probability which represents the
probability that one is allowed to continue to select the next item after
selecting the current one. Intuitively, this term captures the externality of
selecting one item to all its subsequent items in terms of the opportunity of
being selected. Therefore, the actual set of items that can be selected by a
policy depends on the specific ordering it adopts to select items, this makes
our problem fundamentally different from classical submodular set optimization
problems. Our objective is to identify the best sequence of selecting items so
as to maximize the expected utility of the selected items. We propose a class
of stochastic utility functions, \emph{adaptive cascade submodular functions},
and show that the objective functions in many practical application domains
satisfy adaptive cascade submodularity. Then we develop a $0.12$ approximation
algorithm to the adaptive cascade submodular maximization problem.
- Abstract（参考訳）: 本稿では,適応設定下でのカスケード部分モジュラー最大化問題を提案し,検討する。
問題の入力はアイテムの集合であり、各アイテムは既知の確率分布から引き出される特定の状態(すなわち、アイテムの限界寄与)にある。
しかし、選択する前に実際の状態を知ることはできない。
確率的サブモジュラー最大化に関する既存の研究と比較すると、問題の1つの独特な設定は、各項目が、現在の項目を選択した後に次の項目を選択できる確率を表す継続確率に関連付けられていることである。
直感的には、この用語は選択される機会の観点から、次の全ての項目に対して1つの項目を選択することの外部性を捉えている。
したがって、ポリシーによって選択できるアイテムの実際のセットは、アイテムの選択に採用する特定の順序に依存するため、従来のサブモジュラー集合最適化問題とは根本的に異なる問題となる。
本研究の目的は,選択項目の有効性を最大化するために,選択項目の最適シーケンスを特定することである。
確率的ユーティリティ関数のクラスである \emph{adaptive cascade submodular function} を提案し,多くの応用領域における目的関数が適応的カスケード部分モジュラリティを満たすことを示す。
次に、適応カスケード部分モジュラー最大化問題に対する0.12$近似アルゴリズムを開発する。
関連論文リスト
- An incremental preference elicitation-based approach to learning potentially non-monotonic preferences in multi-criteria sorting [53.36437745983783]
まず最適化モデルを構築し,非単調な選好をモデル化する。
本稿では,情報量測定手法と質問選択戦略を考案し,各イテレーションにおいて最も情報に富む選択肢を特定する。
2つのインクリメンタルな選好に基づくアルゴリズムは、潜在的に単調な選好を学習するために開発された。
論文 参考訳（メタデータ） (2024-09-04T14:36:20Z) - Feature Selection as Deep Sequential Generative Learning [50.00973409680637]
本研究では, 逐次再構成, 変分, 性能評価器の損失を伴って, 深部変分変圧器モデルを構築した。
提案モデルでは,特徴選択の知識を抽出し,連続的な埋め込み空間を学習し,特徴選択決定シーケンスをユーティリティスコアに関連付けられた埋め込みベクトルにマッピングする。
論文 参考訳（メタデータ） (2024-03-06T16:31:56Z) - Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - 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) - Partial-Adaptive Submodular Maximization [28.24164217929491]
適応部分モジュラー問題に関するほとんどの研究は、完全に適応的な設定に焦点を当てている。
本稿では,バッチ内で複数の選択を同時に行うことができる部分適応部分モジュラーの問題について検討する。
我々のアプローチは、過去の選択から観察を待つ時間を削減するとともに、適応性の利点を享受します。
論文 参考訳（メタデータ） (2021-11-01T14:48:41Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular
Maximization subject to a Knapsack Constraint [26.171841086317574]
ナップサック制約を受ける非モノトーン適応サブモジュラ問題について研究する。
アイテムの状態は最初不明であり、そのアイテムの状態を明らかにするためにアイテムを選択する必要がある。
私たちの主な貢献は、適応サブモジュール関数を最大化する$frac1$近似を実現するサンプリングベースのランダム化アルゴリズムを開発することです。
論文 参考訳（メタデータ） (2021-04-10T20:11:11Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。
本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。
整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
論文 参考訳（メタデータ） (2020-06-01T22:20:45Z) - Stepwise Model Selection for Sequence Prediction via Deep Kernel
Learning [100.83444258562263]
本稿では,モデル選択の課題を解決するために,新しいベイズ最適化(BO)アルゴリズムを提案する。
結果として得られる複数のブラックボックス関数の最適化問題を協調的かつ効率的に解くために,ブラックボックス関数間の潜在的な相関を利用する。
我々は、シーケンス予測のための段階的モデル選択(SMS)の問題を初めて定式化し、この目的のために効率的な共同学習アルゴリズムを設計し、実証する。
論文 参考訳（メタデータ） (2020-01-12T09:42:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。