論文の概要: Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization

• arxiv url: http://arxiv.org/abs/2606.14764v1
• Date: Mon, 08 Jun 2026 17:20:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:32.057801
• Title: Avoiding Exponential Blow-Up in Distributive Lattice Submodular Minimization
• Title（参考訳）: 分散格子サブモジュール最小化における指数ブラウアップの回避
• Authors: Ishant Shanu,
• Abstract要約: サブモジュール関数の最小化は、コンピュータビジョンと機械学習の領域で高い適用性を持つ。 現在、それを扱う最良の方法は、各格子に対して部分モジュラ函数を外挿する変換を使うことである。 本稿では,分散格子内でのみ機能する分散格子を扱うための汎用フレームワークを提案する。
• 参考スコア（独自算出の注目度）: 0.2538209532048866
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Submodular function minimization has gained a lot of interest in recent years. They are highly applicable in the area of Computer Vision and Machine Learning. Often such applications require to work with submodular functions defined on distributive lattice. Current best way of dealing with it is using a transformation which extrapolates the submodular function for the respective boolean lattice. It makes optimization system too inefficient due to enlargement of the working space. Quantitatively, the expanded space has additional exponential (in set size) number of elements. We propose a generic framework for dealing with distributive lattice which only works within distributive lattice. Our framework allows one to use already established submodular function minimization algorithms for boolean lattice. In our experiment, we show the huge improvement in terms of running time over tranditional methods for handling distributive lattice.
• Abstract（参考訳）: サブモジュール関数の最小化は近年、大きな関心を集めている。 それらはコンピュータビジョンと機械学習の分野に非常に応用できる。 そのようなアプリケーションは、しばしば分配格子上で定義される部分モジュラ函数を扱う必要がある。 現在、それを扱う最良の方法は、各ブール格子に対する部分モジュラ函数を外挿する変換を使うことである。 作業空間の拡大により最適化システムが非効率になる。 定量的に、拡張空間は追加の指数(セットサイズ)要素数を持つ。 本稿では,分散格子内でのみ機能する分散格子を扱うための汎用フレームワークを提案する。 我々のフレームワークは、ブール格子に対して既に確立された部分モジュラ関数最小化アルゴリズムを使用できる。 実験では,分散格子を扱うためのトランジッショナル手法に比べて,実行時間の大幅な改善が示された。

関連論文リスト

• Mini-batch Submodular Maximization [5.439020425819001]
  単調デコンポーザブルな部分モジュラ関数,$F=sum_i=1N fi$ を制約の下で最大化する,最初のミニバッチアルゴリズムを提案する。 我々は、一様と重み付けの2つのサンプリング手法を検討する。 意外なことに, 実験結果から, 均一サンプリングは加重サンプリングよりも優れていることが示された。
  論文  参考訳（メタデータ） (2024-01-23T04:16:58Z)
• Supermodular Rank: Set Function Decomposition and Optimization [2.578242050187029]
  格子上の函数の超モジュラー階数を定義する。 準モジュラーランクを類似的に定義する。 部分モジュラ分解を用いて集合関数を最適化する。
  論文  参考訳（メタデータ） (2023-05-24T02:09:28Z)
• 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)
• Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
  ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。 連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。 提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
  論文  参考訳（メタデータ） (2021-11-01T21:06:35Z)
• 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)
• 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)

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

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