Maximizing submodular functions using probabilistic graphical models
We consider the problem of maximizing submodular functions; while this problem is known to be NP-hard, several numerically efficient local search techniques with approximation guarantees are available. In this paper, we propose a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models. In a graphical model, the entropy of the joint distribution decomposes as a sum of marginal entropies of subsets of variables; moreover, for any distribution, the entropy of the closest distribution factorizing in the graphical model provides an bound on the entropy. For directed graphical models, this last property turns out to be a direct consequence of the submodularity of the entropy function, and allows the generalization of graphical-model-based upper bounds to any submodular functions. These upper bounds may then be jointly maximized with respect to a set, while minimized with respect to the graph, leading to a convex variational inference scheme for maximizing submodular functions, based on outer approximations of the marginal polytope and maximum likelihood bounded treewidth structures. By considering graphs of increasing treewidths, we may then explore the trade-off between computational complexity and tightness of the relaxation. We also present extensions to constrained problems and maximizing the difference of submodular functions, which include all possible set functions.
Code (0)
등록된 구현이 없습니다.
Tasks
Variational InferenceSimilar Papers 제목 키워드 기반
Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice
Optimization problems with set submodular objective functions have many real-world applications. In discrete scenarios, where the same item can be selected more than once, the domain is generalized from a 2-element set t…
Regularized Submodular Maximization at Scale
In this paper, we propose scalable methods for maximizing a regularized submodular function $f = g - \ell$ expressed as the difference between a monotone submodular function $g$ and a modular function $\ell$. Indeed, sub…
Data SummarizationDiversityPoint ProcessesProduct RecommendationFast and Private Submodular and $k$-Submodular Functions Maximization with Matroid Constraints
The problem of maximizing nonnegative monotone submodular functions under a certain constraint has been intensively studied in the last decade, and a wide range of efficient approximation algorithms have been developed f…
Data SummarizationMaximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms
Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two deca…
Combinatorial OptimizationEvolutionary AlgorithmsMulti-objective Evolutionary Algorithms are Generally Good: Maximizing Monotone Submodular Functions over Sequences
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 c…
Document SummarizationEvolutionary AlgorithmsRecommendation Systems