論文の概要: Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees

• arxiv url: http://arxiv.org/abs/2110.09332v1
• Date: Mon, 18 Oct 2021 14:00:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-19 21:29:39.399107
• Title: Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees
• Title（参考訳）: 理論的保証付き多目的進化アルゴリズムによる結果の多様化
• Authors: Chao Qian, Dan-Xuan Liu, Zhi-Hua Zhou
• Abstract要約: 両目的探索問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA)を用いて解くことを提案する。 GSEMOが最適時間近似比1/2$を達成できることを理論的に証明する。 目的関数が動的に変化すると、GSEMOはこの近似比をランニングタイムで維持することができ、Borodinらによって提案されたオープンな問題に対処する。
• 参考スコア（独自算出の注目度）: 94.72461292387146
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a ground set of items, the result diversification problem aims to select a subset with high "quality" and "diversity" while satisfying some constraints. It arises in various real-world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi-objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, $1/2$. For more general matroid constraints, the GSEMO can achieve the asymptotically optimal polynomial-time approximation ratio, $1/2-\epsilon/(4n)$. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by Borodin et al. This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the state-of-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments.
• Abstract（参考訳）: 結果の多様化問題は、いくつかの制約を満たすとともに、高い「品質」と「多様性」のサブセットを選択することを目的としている。 ウェブベースの検索、文書要約、特徴選択など、様々な現実世界の人工知能アプリケーションに現れ、計算幾何学、データベース、ファイナンス、オペレーション研究など他の分野にも応用されている。 従来のアルゴリズムは主に欲求や局所探索に基づいている。 本稿では,二目的最大化問題として結果の多様化問題を再構成し,多目的進化アルゴリズム(EA),すなわちGSEMOを用いて解くことを提案する。 我々はGSEMOが静的環境と動的環境の両方において(漸近的に)最適な理論的保証を達成できることを理論的に証明する。 濃度制約に対して、GSEMO は最適多項式時間近似比 1/2$ を達成することができる。 より一般的なマットロイドの制約に対して、GSEMO は漸近的に最適な多項式時間近似比 1/2-\epsilon/(4n)$ を達成することができる。 さらに、目的関数(すなわち品質と多様性の線形結合)が動的に変化するとき、GSEMOはこの近似比を多項式実行時間で維持することができ、ボロディンらによって提案された開問題に対処することができる。 これはまた、局所探索による動的最適化問題の解法よりもEAの優位性を示し、EAの突然変異演算子の動的変化に対する堅牢性を明らかにする。 web-based search, multi-label feature selection, document summarizationの応用実験では,静的および動的環境下でのgsemoの性能が最先端のアルゴリズム(すなわちgreedyアルゴリズムとローカル検索)よりも優れていることが示されている。

関連論文リスト

• Multi-Objective GFlowNets [59.16787189214784]
  機械学習の多くの応用において、目標は、目的の集合を同時に最大化する候補を生成することである。 実際には、これらの目的はしばしば過小評価されており、候補者の多様性が重要な考慮事項となっている。 GFlowNetsの単一目的設定における多種多様な候補生成の成功により、我々はMOGFN(Multi-Objective GFlowNets)を考える。 また,MOGFNは,ハイパーボリューム,R2距離,候補者の多様性において,既存の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-23T16:15:36Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  エネルギーシステムの最適化問題は、強い非線形系の挙動と複数の競合する目的のために複雑である。 場合によっては、提案された最適解は、物理的性質や安全クリティカルな操作条件に関連する明示的な入力制約に従う必要がある。 本稿では,ブラックボックス問題に対する制約付き多目的最適化のためのツリーアンサンブルを用いた新しいデータ駆動戦略を提案する。
  論文  参考訳（メタデータ） (2021-11-04T20:18:55Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  サブグループフィードバックを取り入れた新しいGPレグレッションを導入する。 我々の修正された回帰は、以前のアプローチと比べて、明らかにばらつきを減らし、したがってより正確な後続を減らした。 我々は2つの異なる社会問題に対してアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2021-07-07T03:57:22Z)
• Evolutionary Diversity Optimization and the Minimum Spanning Tree Problem [13.264683014487376]
  多様性最適化の文脈において、よく知られた最小スパンニングツリー問題(MST)について検討する。 単純な$(mu+1)$-EAは、高品質の木々の多様化した個体群を効果的に計算できることを示す。
  論文  参考訳（メタデータ） (2020-10-21T11:50:49Z)
• Optimising Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [15.389164392812276]
  本稿では、確率制約付き部分モジュラー関数に対する進化的多目的アルゴリズムの最初の実行時解析について述べる。 本稿では,GSEMOアルゴリズムが最近解析されたgreedyアルゴリズムと同等の性能保証が得られることを示す。
  論文  参考訳（メタデータ） (2020-06-20T00:17:44Z)
• Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
  本稿では、MoHAEAと呼ばれるハイブリッド適応進化アルゴリズム(HAEA)の拡張として、新しい多目的アルゴリズムを提案する。 MoHAEAは、MOEA/D、pa$lambda$-MOEA/D、MOEA/D-AWA、NSGA-IIの4つの状態と比較される。
  論文  参考訳（メタデータ） (2020-04-29T02:16:49Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  古典的knapsack問題に対する単目的・多目的ベースライン進化アルゴリズムについて検討する。 この結果から, 動的変化を考慮に入れた集団を用いた多目的アプローチは, 多くのベンチマークシナリオにおいて明らかな優位性を有することが示された。
  論文  参考訳（メタデータ） (2020-04-27T03:50:24Z)
• Multifactorial Cellular Genetic Algorithm (MFCGA): Algorithmic Design, Performance Comparison and Genetic Transferability Analysis [17.120962133525225]
  多目的最適化は先進的な研究領域であり、近年顕著な研究の勢いを増している。 本稿では,多因子最適化シナリオのための新しいアルゴリズムスキームを提案する。 提案したMFCGAはセルオートマタの概念に基づいて,問題間の知識交換機構を実装している。
  論文  参考訳（メタデータ） (2020-03-24T11:03:55Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)

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

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