In mathematics, a submodular set function (also known as a submodular function) is a
set function
In mathematics, especially measure theory, a set function is a function whose domain is a family of subsets of some given set and that (usually) takes its values in the extended real number line \R \cup \, which consists of the real numbers \R ...
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
In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
,
game theory
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
(as functions modeling user preferences) and
electrical network
An electrical network is an interconnection of electrical components (e.g., batteries, resistors, inductors, capacitors, switches, transistors) or a model of such an interconnection, consisting of electrical elements (e.g., voltage sou ...
s. Recently, submodular functions have also found utility in several real world problems in
machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
and
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
, including
automatic summarization
Automatic summarization is the process of shortening a set of data computationally, to create a subset (a summary) that represents the most important or relevant information within the original content. Artificial intelligence algorithms are comm ...
,
multi-document summarization,
feature selection,
active learning
Active learning is "a method of learning in which students are actively or experientially involved in the learning process and where there are different levels of active learning, depending on student involvement." states that "students particip ...
, sensor placement, image collection summarization and many other domains.
[
]
Definition
If is a finite set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
, a submodular function is a set function , where denotes the power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is po ...
of , which satisfies one of the following equivalent conditions.
# For every with and every we have that .
# For every we have that .
# For every and such that 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 and examples of submodular functions
Monotone
A set function is ''monotone'' if for every we have that . Examples of monotone submodular functions include:
; Linear (Modular) 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
Entropy is a scientific concept, most commonly associated with states of disorder, randomness, or uncertainty. The term and the concept are used in diverse fields, from classical thermodynamics, where it was first recognized, to the micros ...
: Let be a set of random variables
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. The term 'random variable' in its mathematical definition refers ...
. Then for any we have that is a submodular function, where is the entropy of the set of random variables , a fact known as Shannon's inequality. Further inequalities for the entropy function are known to hold, see entropic vector.
; Matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
rank functions : Let be the ground set on which a matroid is defined. Then the rank function of the matroid is a submodular function.[Fujishige (2005) p.22]
Non-monotone
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. More formally, the function is non-monotone if there are sets in its domain s.t. and .
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
In probability theory and information theory, the mutual information (MI) of two random variables is a measure of the mutual Statistical dependence, dependence between the two variables. More specifically, it quantifies the "Information conten ...
: Let be a set of random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
s. 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 of submodular set functions
Often, given a submodular set function that describes the values of various sets, we need to compute the values of ''fractional'' sets. For example: we know that the value of receiving house A and house B is V, and we want to know the value of receiving 40% of house A and 60% of house B. To this end, we need a ''continuous extension'' of the submodular set function.
Formally, a set function with can be represented as a function on , by associating each with a binary vector such that when , and otherwise. A ''continuous extension'' of is a continuous function , 1
The comma is a punctuation mark that appears in several variants in different languages. Some typefaces render it as a small line, slightly curved or straight, but inclined from the vertical; others give it the appearance of a miniature fille ...
\rightarrow \mathbb, that matches the value of on , i.e. .
Several kinds of continuous extensions of submodular functions are commonly used, which are described below.
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 ]
Multilinear extension
Consider any vector \mathbf=\ such that each 0\leq x_i\leq 1. Then the multilinear extension is defined as F(\mathbf)=\sum_ f(S) \prod_ x_i \prod_ (1-x_i).
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.
Convex closure
Consider any vector \mathbf=\ such that each 0\leq x_i\leq 1. Then the convex closure is defined as f^-(\mathbf)=\min\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf,\sum_S \alpha_S=1,\alpha_S\geq 0\right).
The convex closure of any set function is convex over ,1n.
Concave closure
Consider any vector \mathbf=\ such that each 0\leq x_i\leq 1. Then the concave closure is defined as f^+(\mathbf)=\max\left(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\mathbf,\sum_S \alpha_S=1,\alpha_S\geq 0\right).
Relations between continuous extensions
For the extensions discussed above, it can be shown that f^(\mathbf) \geq F(\mathbf) \geq f^(\mathbf)=f^L(\mathbf) when f is submodular.[
]
Properties
# The class of submodular functions is closed under non-negative linear combination
In mathematics, a linear combination or superposition is an Expression (mathematics), expression constructed from a Set (mathematics), set of terms by multiplying each term by a constant and adding the results (e.g. a linear combination of ''x'' a ...
s. Consider any submodular function f_1,f_2,\ldots,f_k and non-negative numbers \alpha_1,\alpha_2,\ldots,\alpha_k. Then the function g defined by g(S)=\sum_^k \alpha_i f_i(S) is submodular.
#For any submodular function f, the function defined by g(S)=f(\Omega \setminus S) is submodular.
#The function g(S)=\min(f(S),c), where c is a real number, is submodular whenever f is monotone submodular. More generally, g(S)=h(f(S)) is submodular, for any non decreasing concave function h.
# Consider a random process where a set T is chosen with each element in \Omega being included in T independently with probability p. Then the following inequality is true \mathbb (T)geq p f(\Omega)+(1-p) f(\varnothing) where \varnothing is the empty set. More generally consider the following random process where a set S is constructed as follows. For each of 1\leq i\leq l, A_i\subseteq \Omega construct S_i by including each element in A_i independently into S_i with probability p_i. Furthermore let S=\cup_^l S_i. Then the following inequality is true \mathbb (S)geq \sum_ \Pi_p_i \Pi_(1-p_i)f(\cup_A_i).
Optimization problems
Submodular functions have properties which are very similar to convex
Convex or convexity may refer to:
Science and technology
* Convex lens, in optics
Mathematics
* Convex set, containing the whole line segment that joins points
** Convex polygon, a polygon which encloses a convex set of points
** Convex polytop ...
and concave function
In mathematics, a concave function is one for which the function value at any convex combination of elements in the domain is greater than or equal to that convex combination of those domain elements. Equivalently, a concave function is any funct ...
s. For this reason, an optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
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 set function minimization
The hardness of minimizing a submodular set function depends on constraints imposed on the problem.
# The unconstrained problem of minimizing a submodular function is computable in polynomial time,[ and even in strongly-polynomial time.][ Computing the minimum cut in a graph is a special case of this minimization problem.
# The problem of minimizing a submodular function with a cardinality lower bound is ]NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
, with polynomial factor lower bounds on the approximation factor.[
]
Submodular set function maximization
Unlike the case of minimization, maximizing a generic submodular function is NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
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.
# The problem of maximizing a non-negative submodular function admits a 1/2 approximation algorithm.[ Computing the maximum cut of a graph is a special case of this problem.
# The problem of maximizing a monotone submodular function subject to a cardinality constraint admits a 1 - 1/e approximation algorithm.] The maximum coverage problem is a special case of this problem.
# The problem of maximizing a monotone submodular function subject to a matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
constraint (which subsumes the case above) also admits a 1 - 1/e 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, there are several other natural optimization problems related to submodular functions.
# Minimizing the difference between two submodular functions[ is not only NP hard, but also inapproximable.][
# Minimization/maximization of a submodular function subject to a submodular level set constraint (also known as submodular optimization subject to submodular cover or submodular knapsack constraint) admits bounded approximation guarantees.][
# Partitioning data based on a submodular function to maximize the average welfare is known as the submodular welfare problem, which also admits bounded approximation guarantees (see welfare maximization).
]
Applications
Submodular functions naturally occur in several real world applications, in economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goods and services.
Economics focuses on the behaviour and interac ...
, game theory
Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
, machine learning
Machine learning (ML) is a field of study in artificial intelligence concerned with the development and study of Computational statistics, statistical algorithms that can learn from data and generalise to unseen data, and thus perform Task ( ...
and computer vision
Computer vision tasks include methods for image sensor, acquiring, Image processing, processing, Image analysis, analyzing, and understanding digital images, and extraction of high-dimensional data from the real world in order to produce numerical ...
.[ 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.
]
See also
* Supermodular function
* Matroid
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...
, Polymatroid
* Utility functions on indivisible goods Some branches of economics and game theory deal with indivisible goods, discrete items that can be traded only as a whole. For example, in combinatorial auctions there is a finite set of items, and every agent can buy a subset of the items, but an i ...
Citations
References
*
*
*
*
*{{citation , last=Oxley , first=James G. , title=Matroid theory , series=Oxford Science Publications , location=Oxford , publisher=Oxford University Press
Oxford University Press (OUP) is the publishing house of the University of Oxford. It is the largest university press in the world. Its first book was printed in Oxford in 1478, with the Press officially granted the legal right to print books ...
, year=1992 , isbn=0-19-853563-5 , zbl=0784.05002
External links
* http://www.cs.berkeley.edu/~stefje/references.html has a longer bibliography
* http://submodularity.org/ includes further material on the subject
Matroid theory
In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...