論文の概要: Multi-objective Evolutionary Algorithms are Generally Good: Maximizing
Monotone Submodular Functions over Sequences
- arxiv url: http://arxiv.org/abs/2104.09884v1
- Date: Tue, 20 Apr 2021 10:36:10 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-21 13:31:57.598461
- Title: Multi-objective Evolutionary Algorithms are Generally Good: Maximizing
Monotone Submodular Functions over Sequences
- Title（参考訳）: 多目的進化アルゴリズムは一般に良い:シーケンス上の単調部分モジュラー関数を最大化する
- Authors: Chao Qian, Dan-Xuan Liu, Chao Feng, Ke Tang
- Abstract要約: 本稿では,シーケンス上のモノトーン部分モジュラ関数を最大化する問題クラスについて検討する。
EAは、部分モジュラ最適化の問題を解くための優れた近似保証を達成できる。
例えば、タスクの達成、情報ゲインの最大化、探索と追跡、レコメンデーションシステムなど、様々なアプリケーションに関する実証研究は、GSEMOの優れた性能を示している。
- 参考スコア（独自算出の注目度）: 44.11102526976392
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evolutionary algorithms (EAs) are general-purpose optimization algorithms,
inspired by natural evolution. Recent theoretical studies have shown that EAs
can achieve good approximation guarantees for solving the problem classes of
submodular optimization, which have a wide range of applications, such as
maximum coverage, sparse regression, influence maximization, document
summarization and sensor placement, just to name a few. Though they have
provided some theoretical explanation for the general-purpose nature of EAs,
the considered submodular objective functions are defined only over sets or
multisets. To complement this line of research, this paper studies the problem
class of maximizing monotone submodular functions over sequences, where the
objective function depends on the order of items. We prove that for each kind
of previously studied monotone submodular objective functions over sequences,
i.e., prefix monotone submodular functions, weakly monotone and strongly
submodular functions, and DAG monotone submodular functions, a simple
multi-objective EA, i.e., GSEMO, can always reach or improve the best known
approximation guarantee after running polynomial time in expectation. Note that
these best-known approximation guarantees can be obtained only by different
greedy-style algorithms before. Empirical studies on various applications,
e.g., accomplishing tasks, maximizing information gain, search-and-tracking and
recommender systems, show the excellent performance of the GSEMO.
- Abstract（参考訳）: 進化アルゴリズム(EA)は、自然進化にインスパイアされた汎用最適化アルゴリズムである。
近年の理論的研究により、easは、最大カバレッジ、疎回帰、影響最大化、文書要約、センサー配置など、広範囲の応用がある部分モジュラー最適化の問題クラスを解決するための優れた近似保証を達成できることが示されている。
それらはeasの汎用性に関する理論的な説明を提供してきたが、部分モジュラー対象関数は集合や多重集合上でのみ定義される。
本研究を補完するために,目的関数がアイテムの順序に依存するシーケンス上の単調部分モジュラー関数を最大化する問題クラスについて検討する。
従来研究されてきたモノトン部分モジュラー目的関数,すなわちプレフィックスモノトン部分モジュラー関数,弱モノトンおよび強サブモジュラー関数,およびDAGモノトン部分モジュラー関数に対して,単純な多目的EA,すなわちGSEMOは,期待される多項式時間の実行後に常に最もよく知られた近似保証に到達または改善可能であることを証明した。
これらの最もよく知られた近似保証は、以前にも異なる欲望型のアルゴリズムによってのみ得られることに注意されたい。
タスク達成,情報ゲインの最大化,探索と追跡,レコメンダシステムなど,さまざまなアプリケーションに関する実証研究は,GSEMOの優れた性能を示している。
関連論文リスト
- Non-monotone Sequential Submodular Maximization [13.619980548779687]
我々は、$k$の重み付けが最大になるように、基底セット$V$から$k$の項目群を選択してランク付けすることを目指している。
本研究の結果は,レコメンデーションシステムや最適化など,様々な分野に影響を及ぼす。
論文 参考訳（メタデータ） (2023-08-16T19:32:29Z) - Result Diversification by Multi-objective Evolutionary Algorithms with
Theoretical Guarantees [94.72461292387146]
両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。
GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。
目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
論文 参考訳（メタデータ） (2021-10-18T14:00:22Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳（メタデータ） (2021-06-09T01:59:55Z) - Planning with Submodular Objective Functions [118.0376288522372]
準モジュラー目的関数を用いて計画を行い、累積報酬を最大化する代わりに、劣モジュラー関数によって誘導される値の最大化を目標とする。
本フレームワークは, 基本性制約を特別な場合として, 標準計画と準モジュラー目標を仮定する。
論文 参考訳（メタデータ） (2020-10-22T16:55:12Z) - 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) - Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
ここでは制約は成分を伴い、制約はアルファの小さな確率でのみ破ることができる。
GSEMOアルゴリズムは, 単調な部分モジュラ関数に対して, 最悪の性能保証が得られることを示す。
実験結果から, 進化的多目的アルゴリズムを用いることで, 性能が大幅に向上することが示唆された。
論文 参考訳（メタデータ） (2020-06-20T00:17:44Z) - From Sets to Multisets: Provable Variational Inference for Probabilistic
Integer Submodular Models [82.95892656532696]
サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。
本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。
整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
論文 参考訳（メタデータ） (2020-06-01T22:20:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。