論文の概要: Sparsification of Decomposable Submodular Functions

• arxiv url: http://arxiv.org/abs/2201.07289v1
• Date: Tue, 18 Jan 2022 20:05:25 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-20 15:26:33.224831
• Title: Sparsification of Decomposable Submodular Functions
• Title（参考訳）: 可逆的部分モジュラー関数のスパース化
• Authors: Akbar Rafiey, Yuichi Yoshida
• Abstract要約: サブモジュール関数は多くの機械学習とデータマイニングタスクの中核にある。 元の関数の根底にある部分モジュラ関数の数がとても多いので、処理に多くの時間が必要で、あるいはメインメモリに収まらない場合もあります。 分解可能部分モジュラ函数に対するスパーシフィケーションの概念を導入し、元の関数の正確な近似を得る目的は、少数の部分モジュラ函数の(重み付けされた)和である。
• 参考スコア（独自算出の注目度）: 27.070004659301162
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Submodular functions are at the core of many machine learning and data mining tasks. The underlying submodular functions for many of these tasks are decomposable, i.e., they are sum of several simple submodular functions. In many data intensive applications, however, the number of underlying submodular functions in the original function is so large that we need prohibitively large amount of time to process it and/or it does not even fit in the main memory. To overcome this issue, we introduce the notion of sparsification for decomposable submodular functions whose objective is to obtain an accurate approximation of the original function that is a (weighted) sum of only a few submodular functions. Our main result is a polynomial-time randomized sparsification algorithm such that the expected number of functions used in the output is independent of the number of underlying submodular functions in the original function. We also study the effectiveness of our algorithm under various constraints such as matroid and cardinality constraints. We complement our theoretical analysis with an empirical study of the performance of our algorithm.
• Abstract（参考訳）: サブモジュール関数は多くの機械学習とデータマイニングタスクの中核にある。 これらのタスクの多くに対する根底となる部分モジュラ函数は分解可能である、すなわちいくつかの単純部分モジュラ函数の和である。 しかし、多くのデータ集約型アプリケーションでは、元の関数の根底にある部分モジュラ関数の数が非常に多いため、処理には非常に多くの時間が必要であり、あるいはメインメモリに収まらない。 そこで本研究では,少数の部分モジュラー関数の(重み付けされた)和である元の関数の正確な近似を求めることを目的とした,分解可能な部分モジュラー関数に対するスパーシフィケーションの概念を導入する。 我々の主な結果は多項式時間ランダム化スパーシフィケーションアルゴリズムであり、出力で使用される関数の期待数は、元の関数の基底部分モジュラ函数の数に依存しない。 また,マトロイドや濃度制約などの制約下でのアルゴリズムの有効性についても検討した。 我々は,アルゴリズムの性能に関する実証的研究により,理論解析を補完する。

関連論文リスト

• Maximizing Submodular Functions for Recommendation in the Presence of Biases [25.081136190260015]
  サブセット選択タスクはシステムや検索エンジンで発生し、ユーザの価値を最大化する項目のサブセットを選択するように要求する。 多くの応用において、入力は出力サブセットの有用性を減らす社会的バイアスを持つことが観察されている。 公平性制約に基づく介入は,比例表現の確保だけでなく,バイアスの存在下での準最適性も達成できることを示す。
  論文  参考訳（メタデータ） (2023-05-03T15:20:00Z)
• Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection [50.14730810124592]
  サブモジュール関数と変種は、多様性とカバレッジを特徴付ける能力を通じて、データ選択と要約のための重要なツールとして登場した。 本稿では,モノトーンおよび非モノトーン部分モジュラー関数のためのフレキシブルニューラルネットワークであるFLEXSUBNETを提案する。
  論文  参考訳（メタデータ） (2022-10-20T06:00:45Z)
• Provable General Function Class Representation Learning in Multitask Bandits and MDPs [58.624124220900306]
  マルチタスク表現学習は、サンプル効率を高めるために強化学習において一般的なアプローチである。 本研究では,解析結果を一般関数クラス表現に拡張する。 バンディットと線形MDPの一般関数クラスにおけるマルチタスク表現学習の利点を理論的に検証する。
  論文  参考訳（メタデータ） (2022-05-31T11:36:42Z)
• Using Partial Monotonicity in Submodular Maximization [13.23676270963484]
  多くの標準部分モジュラーアルゴリズムに対して、単調性比に依存する新しい近似保証を証明できることが示される。 これにより、映画レコメンデーション、二次プログラミング、画像要約の一般的な機械学習応用に対する近似比が向上する。
  論文  参考訳（メタデータ） (2022-02-07T10:35:40Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Multi-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences [44.11102526976392]
  本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。 EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。 例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
  論文  参考訳（メタデータ） (2021-04-20T10:36:10Z)
• Fast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints [27.070004659301162]
  差分プライバシーの枠組みにおいて, マットロイド制約を受ける単調部分モジュラ函数を最大化する問題について検討する。 マットロイド制約を受けるべき$k$submodular関数を保存する最初の$frac12$-approximationアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-28T23:18:58Z)
• 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)

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

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