.png){kind=icon}
.png){kind=icon}
Return
Result diversification by multi-objective evolutionary algorithms with theoretical guarantees
.png){kind=icon}
OA
AI
DOI：10.1016/j.artint.2022.103737.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 an asymptotically optimal polynomial-time approximation ratio, 1/2 - epsilon/(4n), where epsilon > 0 and n is the size of the ground set of items. 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. [7]. 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 stateof-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments. (C) 2022 Published by Elsevier B.V.
Keywords:
Result diversification
Monotone submodular functions
Diversities
Cardinality constraints
Matroid constraints
Dynamic environments
Multi-objective evolutionary algorithms
Running time analysis
Experimental studies
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
13.9
Papers:
6.1K
Citations:
1.9W