In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a 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 immense 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.
Contents
Definition
If
- For every
X , Y ⊆ Ω withX ⊆ Y and everyx ∈ Ω ∖ Y we have thatf ( X ∪ { x } ) − f ( X ) ≥ f ( Y ∪ { x } ) − f ( Y ) . - For every
S , T ⊆ Ω we have thatf ( S ) + f ( T ) ≥ f ( S ∪ T ) + f ( S ∩ T ) . - For every
X ⊆ Ω andx 1 , x 2 ∈ Ω ∖ X we have thatf ( X ∪ { x 1 } ) + f ( X ∪ { x 2 } ) ≥ f ( X ∪ { x 1 , x 2 } ) + f ( X ) .
A nonnegative submodular function is also a subadditive function, but a subadditive function need not be submodular. If
Monotone
A submodular function
Non-monotone
A submodular function which is not monotone is called non-monotone.
Symmetric
A non-monotone submodular function
Asymmetric
A non-monotone submodular function which is not symmetric is called asymmetric.
Lovász extension
This extension is named after mathematician László Lovász. Consider any vector
Multilinear extension
Consider any vector
Convex closure
Consider any vector
Concave closure
Consider any vector
Properties
- The class of submodular functions is closed under non-negative linear combinations. Consider any submodular function
f 1 , f 2 , … , f k α 1 , α 2 , … , α k g defined byg ( S ) = ∑ i = 1 k α i f i ( S ) is submodular. Furthermore, for any submodular functionf , the function defined byg ( S ) = f ( Ω ∖ S ) is submodular. The functiong ( S ) = min ( f ( S ) , c ) , wherec is a real number, is submodular wheneverf is monotonic. - If
f : 2 Ω → R + g : 2 Ω → R + g ( S ) = ϕ ( f ( S ) ) whereϕ is a concave function, is also a submodular function. - Consider a random process where a set
T is chosen with each element inΩ being included inT independently with probabilityp . Then the following inequality is trueE [ f ( T ) ] ≥ p f ( Ω ) + ( 1 − p ) f ( ∅ ) where∅ is the empty set. More generally consider the following random process where a setS is constructed as follows. For each of1 ≤ i ≤ l , A i ⊆ Ω constructS i A i S i p i S = ∪ i = 1 l S i E [ f ( S ) ] ≥ ∑ R ⊆ [ l ] Π i ∈ R p i Π i ∉ R ( 1 − p i ) f ( ∪ i ∈ R A i ) .
Optimization problems
Submodular functions have properties which are very similar to convex and concave functions. 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.
Submodular Minimization
The simplest minimization problem is to find a set
Submodular Maximization
Unlike minimization, maximization of submodular functions is usually NP-hard. Many problems, such as max cut and the maximum coverage problem, can be cast as special cases of this general maximization problem under suitable constraints. Typically, the approximation algorithms for these problems are based on either greedy algorithms or local search algorithms. The problem of maximizing a symmetric non-monotone submodular function subject to no constraints admits a 1/2 approximation algorithm. Computing the maximum cut of a graph is a special case of this problem. The more general problem of maximizing an arbitrary non-monotone submodular function subject to no constraints also admits a 1/2 approximation algorithm. The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a
Related Optimization Problems
Apart from submodular minimization and maximization, another natural problem is Difference of Submodular Optimization. Unfortunately, this problem is not only NP hard, but also inapproximable. A related optimization problem is minimize or maximize a submodular function, subject to a submodular level set constraint (also called submodular optimization subject to submodular cover or submodular knapsack constraint). This problem admits bounded approximation guarantees. Another optimization problem involves partitioning data based on a submodular function, so as to maximize the average welfare. This problem is called the submodular welfare problem.
Applications
Submodular functions naturally occur in several real world applications, in economics, game theory, machine learning and computer vision. Owing 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. For more information on applications of submodularity, particularly in machine learning, see