Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees

• URL: http://arxiv.org/abs/2110.09332v1
• Date: Mon, 18 Oct 2021 14:00:22 GMT
• Title: Result Diversification by Multi-objective Evolutionary Algorithms with Theoretical Guarantees
• Authors: Chao Qian, Dan-Xuan Liu, Zhi-Hua Zhou
• Abstract summary: We propose to reformulate the result diversification problem as a bi-objective search problem, and solve it by a multi-objective evolutionary algorithm (EA) We theoretically prove that the GSEMO can achieve the optimal-time approximation ratio, $1/2$. When the objective function changes dynamically, the GSEMO can maintain this approximation ratio in running time, addressing the open question proposed by Borodin et al.
• Score: 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.

Related papers

• Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem [10.697103866816958]
  We prove evolutionary diversity optimization (EDO) on a 3-objective function LOTZ$_k$. We show that the GSEMO computes a set of all Pareto-optimal solutions in $O(kn3)$ expected iterations. We complement our theoretical analysis with an empirical study, which shows a very similar behavior for both diversity measures.
  arXiv  Detail & Related papers  (2024-04-17T15:51:15Z)
• Rigorous Runtime Analysis of Diversity Optimization with GSEMO on OneMinMax [13.026567958569965]
  We study how the GSEMO algorithm with additional diversity-enhancing enhancements optimize a diversity of its population on a bi-objective benchmark problem OneMin. We prove that it finds a population with optimal diversity in expected time $O(n2)$, when the problem size $n$ is odd. For reaching our goal, we analyse the random walk of the population, which reflects the frequency of changes in the population and their outcomes.
  arXiv  Detail & Related papers  (2023-07-14T09:43:29Z)
• Multi-Objective GFlowNets [59.16787189214784]
  We study the problem of generating diverse candidates in the context of Multi-Objective Optimization. In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives. We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
  arXiv  Detail & Related papers  (2022-10-23T16:15:36Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling [68.69431580852535]
  We introduce a novel GP regression to incorporate the subgroup feedback. Our modified regression has provably lower variance -- and thus a more accurate posterior -- compared to previous approaches. We execute our algorithm on two disparate social problems.
  arXiv  Detail & Related papers  (2021-07-07T03:57:22Z)
• Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms [11.807734722701786]
  Here the constraint involves components and the constraint can only be violated with a small probability of alpha. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements.
  arXiv  Detail & Related papers  (2020-06-20T00:17:44Z)
• Hybrid Adaptive Evolutionary Algorithm for Multi-objective Optimization [0.0]
  This paper proposed a new Multi-objective Algorithm as an extension of the Hybrid Adaptive Evolutionary algorithm (HAEA) called MoHAEA. MoHAEA is compared with four states of the art MOEAs, namely MOEA/D, pa$lambda$-MOEA/D, MOEA/D-AWA, and NSGA-II.
  arXiv  Detail & Related papers  (2020-04-29T02:16:49Z)
• Single- and Multi-Objective Evolutionary Algorithms for the Knapsack Problem with Dynamically Changing Constraints [13.896724650508087]
  We investigate single- and multi-objective baseline evolutionary algorithms for the classical knapsack problem. Our results show that the multi-objective approaches using a population that caters for dynamic changes have a clear advantage on many benchmarks scenarios.
  arXiv  Detail & Related papers  (2020-04-27T03:50:24Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  Adaptivity is an important yet under-studied property in modern optimization theory. Our algorithm is proved to achieve the best-available convergence for non-PL objectives simultaneously while outperforming existing algorithms for PL objectives.
  arXiv  Detail & Related papers  (2020-02-13T05:42:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.