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 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 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 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.
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 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 , 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 . The Lovász extension is a convex function if and only if is a submodular function.
Multilinear extension
Consider any vector such that each . Then the multilinear extension is defined as .