論文の概要: Continuous Submodular Function Maximization

• arxiv url: http://arxiv.org/abs/2006.13474v1
• Date: Wed, 24 Jun 2020 04:37:31 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 09:14:50.875385
• Title: Continuous Submodular Function Maximization
• Title（参考訳）: 連続部分モジュラー関数最大化
• Authors: Yatao Bian, Joachim M. Buhmann, Andreas Krause
• Abstract要約: 連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
• 参考スコア（独自算出の注目度）: 91.17492610120324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Continuous submodular functions are a category of generally non-convex/non-concave functions with a wide spectrum of applications. The celebrated property of this class of functions - continuous submodularity - enables both exact minimization and approximate maximization in poly. time. Continuous submodularity is obtained by generalizing the notion of submodularity from discrete domains to continuous domains. It intuitively captures a repulsive effect amongst different dimensions of the defined multivariate function. In this paper, we systematically study continuous submodularity and a class of non-convex optimization problems: continuous submodular function maximization. We start by a thorough characterization of the class of continuous submodular functions, and show that continuous submodularity is equivalent to a weak version of the diminishing returns (DR) property. Thus we also derive a subclass of continuous submodular functions, termed continuous DR-submodular functions, which enjoys the full DR property. Then we present operations that preserve continuous (DR-)submodularity, thus yielding general rules for composing new submodular functions. We establish intriguing properties for the problem of constrained DR-submodular maximization, such as the local-global relation. We identify several applications of continuous submodular optimization, ranging from influence maximization, MAP inference for DPPs to provable mean field inference. For these applications, continuous submodularity formalizes valuable domain knowledge relevant for optimizing this class of objectives. We present inapproximability results and provable algorithms for two problem settings: constrained monotone DR-submodular maximization and constrained non-monotone DR-submodular maximization. Finally, we extensively evaluate the effectiveness of the proposed algorithms.
• Abstract（参考訳）: 連続部分モジュラ関数(continuous submodular function)は、広い応用範囲を持つ一般に非凸/非凸関数の圏である。 この種類の函数の有名な性質 - 連続部分モジュラリティは、ポリの完全最小化と近似最大化の両方を成す。 時間だ 連続部分モジュラリティは、離散領域から連続領域への部分モジュラリティの概念を一般化することによって得られる。 定義した多変量関数の異なる次元における反発効果を直感的に捉える。 本稿では,連続部分モジュラリティと非凸最適化問題のクラスである連続部分モジュラリティ最大化について体系的に研究する。 まず、連続部分モジュラー函数のクラスを徹底的に特徴づけ、連続部分モジュラリティが減少するリターン(DR)特性の弱いバージョンと同値であることを示す。 したがって、連続 DR-部分モジュラ函数と呼ばれる連続部分モジュラ函数の部分クラスも導出し、完全な DR 特性を享受する。 そして、連続(DR-)部分モジュラリティを保ち、新しい部分モジュラリティ関数を構成するための一般的な規則を与える。 局所-グローバル関係のような制約付きdr-サブモジュラー最大化問題に対する興味深い性質を定めている。 我々は,dppに対する影響最大化,マップ推論から証明可能な平均場推論まで,連続部分モジュラー最適化のいくつかの応用を明らかにした。 これらのアプリケーションでは、連続サブモジュラリティは、このタイプの目的の最適化に関連する価値あるドメイン知識を形式化する。 制約付き単調 dr-サブモジュラー最大化と制約付き非単調 dr-サブモジュラー最大化である。 最後に,提案アルゴリズムの有効性を広範囲に評価する。

関連論文リスト

• Non-monotone Sequential Submodular Maximization [13.619980548779687]
  我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。 本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
  論文  参考訳（メタデータ） (2023-08-16T19:32:29Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。 本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
  論文  参考訳（メタデータ） (2022-10-20T06:00:45Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  多くの標準部分モジュラーアルゴリズムに対して、単調性比に依存する新しい近似保証を証明できることが示される。 これにより、映画レコメンデーション、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比が向上する。
  論文  参考訳（メタデータ） (2022-02-07T10:35:40Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。 EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。 例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
  論文  参考訳（メタデータ） (2021-04-20T10:36:10Z)
• Planning with Submodular Objective Functions [118.0376288522372]
  準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。 本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
  論文  参考訳（メタデータ） (2020-10-22T16:55:12Z)
• Concave Aspects of Submodular Functions [0.0]
  部分モジュラー関数はエントロピーや相互情報などの情報理論の量を一般化する。 部分モジュラ函数も凹凸の兆候を示す。 上界に付随する超微分と多面体を特徴付け, 微分を用いた部分モジュラーの最適条件を提供する。
  論文  参考訳（メタデータ） (2020-06-27T17:06:24Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。