論文の概要: Submodular Function Minimization and Polarity
- arxiv url: http://arxiv.org/abs/1912.13238v3
- Date: Tue, 8 Dec 2020 06:41:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-16 21:17:44.159061
- Title: Submodular Function Minimization and Polarity
- Title（参考訳）: 部分モジュラ関数最小化と極性
- Authors: Alper Atamturk and Vishnu Narayanan
- Abstract要約: 対応する極緩和が部分モジュラ函数に対して完全であることを証明する。
極性アプローチは、部分モジュラ函数のエピグラフの凸包記述の代替的証明を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Using polarity, we give an outer polyhedral approximation for the epigraph of
set functions. For a submodular function, we prove that the corresponding polar
relaxation is exact; hence, it is equivalent to the Lov\'asz extension. The
polar approach provides an alternative proof for the convex hull description of
the epigraph of a submodular function. Computational experiments show that the
inequalities from outer approximations can be effective as cutting planes for
solving submodular as well as non-submodular set function minimization
problems.
- Abstract（参考訳）: 極性を用いて、集合関数のエピグラフに対する外部多面体近似を与える。
部分モジュラ関数に対して、対応する極緩和が完全であることを証明するので、これはlov\'asz拡大と同値である。
極性アプローチは、部分モジュラ函数のエピグラフの凸包記述の代替的な証明を提供する。
計算実験により、外部近似の不等式は、部分モジュラーおよび非部分モジュラー集合関数最小化問題に対する切断平面として有効であることが示された。
関連論文リスト
- Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。
この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文 参考訳（メタデータ） (2023-03-17T13:32:33Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。
本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
論文 参考訳（メタデータ） (2022-10-20T06:00:45Z) - Deep Learning Approximation of Diffeomorphisms via Linear-Control
Systems [91.3755431537592]
我々は、制御に線形に依存する$dot x = sum_i=1lF_i(x)u_i$という形の制御系を考える。
対応するフローを用いて、コンパクトな点のアンサンブル上の微分同相写像の作用を近似する。
論文 参考訳（メタデータ） (2021-10-24T08:57:46Z) - Feature Cross Search via Submodular Optimization [58.15569071608769]
機能工学の基本的な基礎として機能横断探索について研究する。
この問題に対して単純なgreedy $(1-1/e)$-approximationアルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2021-07-05T16:58:31Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - On Additive Approximate Submodularity [30.831477850153224]
実数値集合関数は、加法誤差で部分モジュラリティ条件を満たす場合、およそ部分モジュラリティである。
我々は、$n$要素の基底集合上で定義されるおよそ部分モジュラー函数が、部分モジュラー函数に対して$O(n2)$ポイントワイズであることを示す。
論文 参考訳（メタデータ） (2020-10-06T17:48:28Z) - Concave Aspects of Submodular Functions [0.0]
部分モジュラー関数はエントロピーや相互情報などの情報理論の量を一般化する。
部分モジュラ函数も凹凸の兆候を示す。
上界に付随する超微分と多面体を特徴付け, 微分を用いた部分モジュラーの最適条件を提供する。
論文 参考訳（メタデータ） (2020-06-27T17:06:24Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。