In mathematics, a submodular set 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 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. Definition
If is a finite set, a submodular function is a set function , where
denotes the power set of , which satisfies one of the following
equivalent definitions. For every with and every we have that
For every we have that . For every and we have that .
A nonnegative submodular function is also a subadditive function, but a
subadditive function need not be submodular. If is not assumed finite,
then the above conditions are not equivalent. In particular a function
defined by if is finite and if is infinite satisfies the first condition
above, but the second condition fails when and are infinite sets with finite
intersection. Types of submodular functions
= Monotone = A submodular function is monotone if
for every we have that . Examples of monotone submodular functions include:
Linear functions Any function of the form is called a
linear function. Additionally if then f is monotone.
Budget-additive functions Any function of the form for each and
is called budget additive. Coverage functions
Let be a collection of subsets of some ground set . The function for is
called a coverage function. This can be generalized by adding non-negative
weights to the elements. Entropy
Let be a set of random variables. Then for any we have that is a submodular
function, where is the entropy of the set of random variables
Matroid rank functions Let be the ground set on which a
matroid is defined. Then the rank function of the matroid is a submodular
function. = Non-monotone =
A submodular function which is not monotone is called non-monotone.
Symmetric A non-monotone submodular function is
called symmetric if for every we have that . Examples of symmetric
non-monotone submodular functions include:
Graph cuts Let be the vertices of a graph. For any
set of vertices let denote the number of edges such that and . This can be
generalized by adding non-negative weights to the edges.
Mutual information Let be a set of random variables. Then
for any we have that is a submodular function, where is the mutual
information. Asymmetric
A non-monotone submodular function which is not symmetric is called asymmetric.
Directed cuts Let be the vertices of a directed
graph. For any set of vertices let denote the number of edges such that
and . This can be generalized by adding non-negative weights to the directed
edges. Continuous extensions
= Lovász extension = This extension is named after
mathematician László Lovász. Consider any vector such that each . Then the
Lovász extension is defined as where the expectation is over chosen from the
uniform distribution on the interval . The Lovász extension is a convex
function. = Multilinear extension =
Consider any vector such that each . Then the multilinear extension is
defined as . = Convex closure =
Consider any vector such that each . Then the convex closure is defined as .
It can be shown that . = Concave closure =
Consider any vector such that each . Then the concave closure is defined as .
Properties The class of submodular functions is
closed under non-negative linear combinations. Consider any submodular
function and non-negative numbers . Then the function defined by is
submodular. Furthermore, for any submodular function , the function
defined by is submodular. The function , where is a real number, is submodular
whenever is monotonic. If is a submodular function then
defined as where is a concave function, is also a submodular function.
Consider a random process where a set is chosen with each element in being
included in independently with probability . Then the following
inequality is true where is the empty set. More generally consider the
following random process where a set is constructed as follows. For each of
construct by including each element in independently into with probability .
Furthermore let . Then the following inequality is true .
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 which minimizes a submodular
function subject to no constraints. This problem is computable in polynomial
time. Computing the minimum cut in a graph is a special case of this general
minimization problem. Unfortunately, however, even simple constraints like
cardinality lower bound constraints make this problem NP hard, with polynomial
lower bound approximation factors. = 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 approximation algorithm. The maximum coverage problem
is a special case of this problem. The more general problem of maximizing a
monotone submodular function subject to a matroid constraint also admits a
approximation algorithm. Many of these algorithms can be unified within a
semi-differential based framework of algorithms.
= 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. 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
See also Supermodular function
Matroid, Polymatroid Utility functions on indivisible goods
Citations References
Schrijver, Alexander, Combinatorial Optimization, Springer, ISBN
3-540-44389-4 Lee, Jon, A First Course in
Combinatorial Optimization, Cambridge University Press, ISBN 0-521-01012-8
Fujishige, Satoru, Submodular Functions and Optimization, Elsevier, ISBN
0-444-52086-4 Narayanan, H., Submodular Functions and
Electrical Networks, ISBN 0-444-82523-1 Oxley, James G., Matroid theory, Oxford
Science Publications, Oxford: Oxford University Press, ISBN 0-19-853563-5,
Zbl 0784.05002 External links
http:www.cs.berkeley.edureferences.html has a longer bibliography