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
In economics, diminishing returns are the decrease in marginal (incremental) output of a production process as the amount of a single factor of production is incrementally increased, holding all other factors of production equal (ceteris pari ...
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 s ...
,
game theory
Game theory is the study of mathematical models of strategic interactions among rational agents. Myerson, Roger B. (1991). ''Game Theory: Analysis of Conflict,'' Harvard University Press, p.&nbs1 Chapter-preview links, ppvii–xi It has applic ...
(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
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech 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 commo ...
,
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 partici ...
, 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 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 submodular 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 : 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
, a fact known as
Shannon's inequality. Further inequalities for the entropy function are known to hold, see
entropic vector.
;
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.
[Fujishige (2005) p.22]
Non-monotone
A submodular function that 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
Definition
A set-valued function
with
can also be represented as a function on
, by associating each
with a binary vector
such that
when
, and
otherwise.
The ''continuous
extension
Extension, extend or extended may refer to:
Mathematics
Logic or set theory
* Axiom of extensionality
* Extensible cardinal
* Extension (model theory)
* Extension (predicate logic), the set of tuples of values that satisfy the predicate
* Ext ...
'' of
is defined to be any continuous function
such that it matches the value of
on
, i.e.
.
In the context of submodular functions, there are a few examples of continuous extensions that are commonly used, which are described as follows.
Examples
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
Uniform distribution may refer to:
* Continuous uniform distribution
* Discrete uniform distribution
* Uniform distribution (ecology)
* Equidistributed sequence
See also
*
* Homogeneous distribution
In mathematics, a homogeneous distribution ...
on the interval