論文の概要: Using Partial Monotonicity in Submodular Maximization
- arxiv url: http://arxiv.org/abs/2202.03051v1
- Date: Mon, 7 Feb 2022 10:35:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-08 15:37:31.455450
- Title: Using Partial Monotonicity in Submodular Maximization
- Title（参考訳）: 部分単調性を用いた部分モジュラー最大化
- Authors: Loay Mualem and Moran Feldman
- Abstract要約: 多くの標準部分モジュラーアルゴリズムに対して、単調性比に依存する新しい近似保証を証明できることが示される。
これにより、映画レコメンデーション、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比が向上する。
- 参考スコア（独自算出の注目度）: 13.23676270963484
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Over the last two decades, submodular function maximization has been the
workhorse of many discrete optimization problems in machine learning
applications. Traditionally, the study of submodular functions was based on
binary function properties. However, such properties have an inherit weakness,
namely, if an algorithm assumes functions that have a particular property, then
it provides no guarantee for functions that violate this property, even when
the violation is very slight. Therefore, recent works began to consider
continuous versions of function properties. Probably the most significant among
these (so far) are the submodularity ratio and the curvature, which were
studied extensively together and separately.
The monotonicity property of set functions plays a central role in submodular
maximization. Nevertheless, and despite all the above works, no continuous
version of this property has been suggested to date (as far as we know). This
is unfortunate since submoduar functions that are almost monotone often arise
in machine learning applications. In this work we fill this gap by defining the
monotonicity ratio, which is a continues version of the monotonicity property.
We then show that for many standard submodular maximization algorithms one can
prove new approximation guarantees that depend on the monotonicity ratio;
leading to improved approximation ratios for the common machine learning
applications of movie recommendation, quadratic programming and image
summarization.
- Abstract（参考訳）: 過去20年間で、サブモジュラー関数の最大化は、機械学習アプリケーションにおける多くの離散最適化問題の課題となっている。
伝統的に、部分モジュラ関数の研究は二元関数の性質に基づいている。
しかし、そのような性質には継承の弱点があり、アルゴリズムが特定の性質を持つ関数を仮定すると、その特性に違反する関数に対する保証は提供されない。
そのため、最近の研究は函数特性の連続バージョンを考察し始めた。
これらのうち(今のところ)おそらく最も重要なのは、亜モジュラリティ比と曲率であり、これらが広範囲にまた別々に研究された。
集合函数の単調性は部分モジュラー最大化において中心的な役割を果たす。
それでも、上記のすべての作品にもかかわらず、このプロパティの継続的なバージョンは、現在まで(我々が知る限り)提案されていない。
これは、ほとんど単調な部分モジュラー関数が機械学習アプリケーションでしばしば発生するため不運である。
本研究では、単調性特性の連続バージョンである単調性比を定義することにより、このギャップを埋める。
そして、多くの標準部分モジュラー最大化アルゴリズムにおいて、単調性比に依存する新しい近似保証を証明できることを示し、映画推薦、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比率を改善する。
関連論文リスト
- Stochastic Submodular Maximization via Polynomial Estimators [13.498923494159312]
未知分布を持つ部分モジュラ函数のクラスに対する期待値として定義される部分モジュラ函数の最大化に焦点をあてる。
この形の単調関数に対して、グリーディ連続アルゴリズムは、推定を用いて、任意に$(1-1/e)近似63%の近似比(期待値)を得ることを示す。
論文 参考訳（メタデータ） (2023-03-17T13:32:33Z) - 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) - Sparsification of Decomposable Submodular Functions [27.070004659301162]
サブモジュール関数は多くの機械学習とデータマイニングタスクの中核にある。
元の関数の根底にある部分モジュラ関数の数がとても多いので、処理に多くの時間が必要で、あるいはメインメモリに収まらない場合もあります。
分解可能部分モジュラ函数に対するスパーシフィケーションの概念を導入し、元の関数の正確な近似を得る目的は、少数の部分モジュラ函数の(重み付けされた)和である。
論文 参考訳（メタデータ） (2022-01-18T20:05:25Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Removing Bias in Multi-modal Classifiers: Regularization by Maximizing
Functional Entropies [88.0813215220342]
いくつかのモダリティは、他のものよりも分類結果に容易に寄与することができる。
機能的エントロピーと機能的フィッシャー情報とを結合した対数ソボレフの不等式に基づく手法を開発した。
VQA-CPv2 と SocialIQ の2つの挑戦的マルチモーダルデータセットに対して,より均一にモダリティを活用しながら,最先端の結果を得る。
論文 参考訳（メタデータ） (2020-10-21T07:40:33Z) - Fast and Private Submodular and $k$-Submodular Functions Maximization
with Matroid Constraints [27.070004659301162]
差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。
マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-28T23:18:58Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。