論文の概要: On Additive Approximate Submodularity

• arxiv url: http://arxiv.org/abs/2010.02912v2
• Date: Wed, 7 Oct 2020 16:59:21 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 08:06:38.377273
• Title: On Additive Approximate Submodularity
• Title（参考訳）: 付加近似部分モジュラリティについて
• Authors: Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar
• Abstract要約: 実数値集合関数は、加法誤差で部分モジュラリティ条件を満たす場合、およそ部分モジュラリティである。 我々は、$n$要素の基底集合上で定義されるおよそ部分モジュラー函数が、部分モジュラー函数に対して$O(n2)$ポイントワイズであることを示す。
• 参考スコア（独自算出の注目度）: 30.831477850153224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A real-valued set function is (additively) approximately submodular if it satisfies the submodularity conditions with an additive error. Approximate submodularity arises in many settings, especially in machine learning, where the function evaluation might not be exact. In this paper we study how close such approximately submodular functions are to truly submodular functions. We show that an approximately submodular function defined on a ground set of $n$ elements is $O(n^2)$ pointwise-close to a submodular function. This result also provides an algorithmic tool that can be used to adapt existing submodular optimization algorithms to approximately submodular functions. To complement, we show an $\Omega(\sqrt{n})$ lower bound on the distance to submodularity. These results stand in contrast to the case of approximate modularity, where the distance to modularity is a constant, and approximate convexity, where the distance to convexity is logarithmic.
• Abstract（参考訳）: 実数値集合関数は、加法誤差で部分モジュラリティ条件を満たすとき(加法的に)ほぼ部分モジュラーである。 近似部分モジュラリティは、特に関数評価が正確でない機械学習において、多くの設定で発生する。 本稿では,そのような準モジュラー関数が真の部分モジュラー関数にどの程度近いかを検討する。 n$要素の基底集合上で定義される概準モジュラー函数は、部分モジュラー函数に対して点的に閉じた $o(n^2)$ である。 この結果は、既存の部分モジュラ最適化アルゴリズムをおよそ部分モジュラ関数に適応させるアルゴリズムツールも提供する。 補足するために、$\Omega(\sqrt{n})$ の部分モジュラリティへの距離上の下界を示す。 これらの結果は、モジュラリティへの距離が一定であるような近似モジュラリティと、凸性への距離が対数となる近似凸性とは対照的である。

関連論文リスト

• Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
  格子上の函数の超モジュラー階数を定義する。 準モジュラーランクを類似的に定義する。 部分モジュラ分解を用いて集合関数を最適化する。
  論文  参考訳（メタデータ） (2023-05-24T02:09:28Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。 本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
  論文  参考訳（メタデータ） (2022-10-20T06:00:45Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  このアプローチは,既存の手法よりもはるかに単純であるにもかかわらず,最適/最先端の結果をもたらすことを示す。 我々は,映像要約,位置情報要約,映画推薦タスクにおけるアルゴリズムの有効性を実証的に示す。
  論文  参考訳（メタデータ） (2021-04-06T20:25:57Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• A Parameterized Family of Meta-Submodular Functions [3.233545237942899]
  我々は、部分モジュラ函数と多様性関数を含む超モジュラ函数のクラスを含む広いパラメータ化された単調関数群を与える。 我々は、$gamma$-submodular familyはメタ部分モジュラ函数、計量多様性関数、部分モジュラ函数などのよく知られた関数のクラスを含むことを示した。
  論文  参考訳（メタデータ） (2020-06-23T16:45:12Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)
• Regularized Submodular Maximization at Scale [45.914693923126826]
  亜モジュラリティは本質的に多様性、カバレッジ、代表性の概念に関係している。 正規化部分モジュラ函数 $f = g ell$ を行列式部分モジュラ関数 $g$ とモジュラ関数 $ell$ の差分として最大化する手法を提案する。
  論文  参考訳（メタデータ） (2020-02-10T02:37:18Z)

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

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