In mathematics, a submodular set function (also known as a submodular function) is a set function that, informally, describes the relationship between a set of inputs and an output, where adding more of one input has a decreasing additional benefit (diminishing returns).
The natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks.
Recently, submodular functions have also found utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains.
denotes the power set of
, which satisfies one of the following equivalent conditions.
is not assumed finite, then the above conditions are not equivalent.
are infinite sets with finite intersection.
Examples of monotone submodular functions include: A submodular function that is not monotone is called non-monotone.
In particular, a function is called non-monotone if it has the property that adding more elements to a set can decrease the value of the function.
Examples of symmetric non-monotone submodular functions include: A non-monotone submodular function which is not symmetric is called asymmetric.
To this end, we need a continuous extension of the submodular set function.
Several kinds of continuous extensions of submodular functions are commonly used, which are described below.
This extension is named after mathematician László Lovász.
Then the Lovász extension is defined as
chosen from the uniform distribution on the interval
The Lovász extension is a convex function if and only if
Then the multilinear extension is defined as [10][11]
Intuitively, xi represents the probability that item i is chosen for the set.
For every set S, the two inner products represent the probability that the chosen set is exactly S. Therefore, the sum represents the expected value of f for the set formed by choosing each item i at random with probability xi, independently of the other items.
Then the convex closure is defined as
Then the concave closure is defined as
For this reason, an optimization problem which concerns optimizing a convex or concave function can also be described as the problem of maximizing or minimizing a submodular function subject to some constraints.
The hardness of minimizing a submodular set function depends on constraints imposed on the problem.
Unlike the case of minimization, maximizing a generic submodular function is NP-hard even in the unconstrained setting.
Thus, most of the works in this field are concerned with polynomial-time approximation algorithms, including greedy algorithms or local search algorithms.
[18] Apart from submodular minimization and maximization, there are several other natural optimization problems related to submodular functions.
Submodular functions naturally occur in several real world applications, in economics, game theory, machine learning and computer vision.
[4][29] Owing to the diminishing returns property, submodular functions naturally model costs of items, since there is often a larger discount, with an increase in the items one buys.
Submodular functions model notions of complexity, similarity and cooperation when they appear in minimization problems.
In maximization problems, on the other hand, they model notions of diversity, information and coverage.