論文の概要: Supermodular Rank: Set Function Decomposition and Optimization
- arxiv url: http://arxiv.org/abs/2305.14632v1
- Date: Wed, 24 May 2023 02:09:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-25 20:38:10.357920
- Title: Supermodular Rank: Set Function Decomposition and Optimization
- Title（参考訳）: 超モジュラランク:集合関数分解と最適化
- Authors: Rishi Sonthalia and Anna Seigal and Guido Montufar
- Abstract要約: 格子上の函数の超モジュラー階数を定義する。
準モジュラーランクを類似的に定義する。
部分モジュラ分解を用いて集合関数を最適化する。
- 参考スコア（独自算出の注目度）: 2.578242050187029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We define the supermodular rank of a function on a lattice. This is the
smallest number of terms needed to decompose it into a sum of supermodular
functions. The supermodular summands are defined with respect to different
partial orders. We characterize the maximum possible value of the supermodular
rank and describe the functions with fixed supermodular rank. We analogously
define the submodular rank. We use submodular decompositions to optimize set
functions. Given a bound on the submodular rank of a set function, we formulate
an algorithm that splits an optimization problem into submodular subproblems.
We show that this method improves the approximation ratio guarantees of several
algorithms for monotone set function maximization and ratio of set functions
minimization, at a computation overhead that depends on the submodular rank.
- Abstract（参考訳）: 格子上の関数の超モジュラー階数を定義する。
これは超モジュラ函数の和に分解するのに必要となる最小の項数である。
超モジュラー和は異なる部分順序に関して定義される。
超モジュラー階数の最大値を特徴付け、固定された超モジュラー階数の関数を記述する。
準モジュラーランクを類似的に定義する。
部分モジュラ分解を用いて集合関数を最適化する。
集合関数の部分モジュラーランクに境界が与えられると、最適化問題を部分モジュラー部分問題に分割するアルゴリズムを定式化する。
本手法は,単調集合関数の最大化と集合関数の最小化に対する数アルゴリズムの近似比の保証を,部分モジュラー階数に依存する計算オーバーヘッドで改善することを示す。
関連論文リスト
- Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Randomized Greedy Learning for Non-monotone Stochastic Submodular
Maximization Under Full-bandit Feedback [98.29086113546045]
本稿では,非拘束型マルチアームバンディットのフルバンドフィードバックとサブモジュール性に対する報奨問題について検討する。
RGLは、サブモジュールおよび非サブモジュール設定において、他のフルバンド変種よりも経験的に優れていることを示す。
論文 参考訳（メタデータ） (2023-02-02T18:52:14Z) - Neural Estimation of Submodular Functions with Applications to
Differentiable Subset Selection [50.14730810124592]
サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。
本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
論文 参考訳（メタデータ） (2022-10-20T06:00:45Z) - Randomized Algorithms for Monotone Submodular Function Maximization on
the Integer Lattice [5.543220407902113]
濃度制約を受ける有界整数格子上の単調部分モジュラ函数を最大化する問題を考える。
特に、DR-部分モジュラ函数の最大化、すなわち減少するリターン特性を示す整数格子上で定義される関数に焦点をあてる。
提案したアルゴリズムを整数格子に適用することは、設定された領域に対する目標問題を減らし、最も高速に設定された部分モジュラーアルゴリズムを適用するなど、他のアルゴリズムよりも高速である。
論文 参考訳（メタデータ） (2021-11-19T12:07:16Z) - 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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。