論文の概要: A Parameterized Family of Meta-Submodular Functions

• arxiv url: http://arxiv.org/abs/2006.13754v1
• Date: Tue, 23 Jun 2020 16:45:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 23:59:55.963448
• Title: A Parameterized Family of Meta-Submodular Functions
• Title（参考訳）: メタサブモジュラー関数のパラメータ化ファミリー
• Authors: Mehrdad Ghadiri, Richard Santiago, Bruce Shepherd
• Abstract要約: 我々は、部分モジュラ函数と多様性関数を含む超モジュラ函数のクラスを含む広いパラメータ化された単調関数群を与える。 我々は、$gamma$-submodular familyはメタ部分モジュラ函数、計量多様性関数、部分モジュラ函数などのよく知られた関数のクラスを含むことを示した。
• 参考スコア（独自算出の注目度）: 3.233545237942899
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular function maximization has found a wealth of new applications in machine learning models during the past years. The related supermodular maximization models (submodular minimization) also offer an abundance of applications, but they appeared to be highly intractable even under simple cardinality constraints. Hence, while there are well-developed tools for maximizing a submodular function subject to a matroid constraint, there is much less work on the corresponding supermodular maximization problems. We give a broad parameterized family of monotone functions which includes submodular functions and a class of supermodular functions containing diversity functions. Functions in this parameterized family are called \emph{$\gamma$-meta-submodular}. We develop local search algorithms with approximation factors that depend only on the parameter $\gamma$. We show that the $\gamma$-meta-submodular families include well-known classes of functions such as meta-submodular functions ($\gamma=0$), metric diversity functions and proportionally submodular functions (both with $\gamma=1$), diversity functions based on negative-type distances or Jensen-Shannon divergence (both with $\gamma=2$), and $\sigma$-semi metric diversity functions ($\gamma = \sigma$).
• Abstract（参考訳）: サブモジュール関数の最大化は、過去数年間で機械学習モデルに多くの新しい応用を見出した。 関連する超モジュラー最大化モデル(部分モジュラー最小化)も多くの応用を提供するが、単純な濃度制約の下でも非常に難解であるように見える。 したがって、マトロイド制約を受ける部分モジュラ函数を最大化するツールが十分に開発されているが、対応する超モジュラー最大化問題に対する作業ははるかに少ない。 部分モジュラ函数と多様性関数を含む超モジュラ函数のクラスを含む広いパラメータ化された単調関数群を与える。 このパラメータ化された族内の関数は \emph{$\gamma$-meta-submodular} と呼ばれる。 パラメータ$\gamma$ のみに依存する近似係数を持つ局所探索アルゴリズムを開発した。 我々は、$\gamma$-meta-submodular familyは、メタ劣モジュラ関数($\gamma=0$)、計量多様性関数($\gamma=1$)、負の型距離に基づく多様性関数($\gamma=2$)、および$\sigma$-semiメトリック多様性関数($\gamma = \sigma$)などのよく知られた関数のクラスを含むことを示した。

関連論文リスト

• 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)
• On Additive Approximate Submodularity [30.831477850153224]
  実数値集合関数は、加法誤差で部分モジュラリティ条件を満たす場合、およそ部分モジュラリティである。 我々は、$n$要素の基底集合上で定義されるおよそ部分モジュラー函数が、部分モジュラー函数に対して$O(n2)$ポイントワイズであることを示す。
  論文  参考訳（メタデータ） (2020-10-06T17:48:28Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  連続部分モジュラリティ (continuous submodularity) は、幅広い応用を持つ関数のクラスである。 連続的な部分モジュラ最適化の応用は、影響、推論のMAP、フィールドへの推論など多岐にわたる。
  論文  参考訳（メタデータ） (2020-06-24T04:37:31Z)
• 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)

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

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