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 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 Ω {\displaystyle \Omega } is a finite set, a submodular function is a set function f : 2 Ω → R {\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} } , where 2 Ω {\displaystyle 2^{\Omega }} denotes the power set of Ω {\displaystyle \Omega } , which satisfies one of the following equivalent conditions.
For every X , Y ⊆ Ω {\displaystyle X,Y\subseteq \Omega } with X ⊆ Y {\displaystyle X\subseteq Y} and every x ∈ Ω ∖ Y {\displaystyle x\in \Omega \setminus Y} we have that f ( X ∪ { x } ) − f ( X ) ≥ f ( Y ∪ { x } ) − f ( Y ) {\displaystyle f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)} . For every S , T ⊆ Ω {\displaystyle S,T\subseteq \Omega } we have that f ( S ) + f ( T ) ≥ f ( S ∪ T ) + f ( S ∩ T ) {\displaystyle f(S)+f(T)\geq f(S\cup T)+f(S\cap T)} . For every X ⊆ Ω {\displaystyle X\subseteq \Omega } and x 1 , x 2 ∈ Ω ∖ X {\displaystyle x_{1},x_{2}\in \Omega \backslash X} such that x 1 ≠ x 2 {\displaystyle x_{1}\neq x_{2}} we have that f ( X ∪ { x 1 } ) + f ( X ∪ { x 2 } ) ≥ f ( X ∪ { x 1 , x 2 } ) + f ( X ) {\displaystyle f(X\cup \{x_{1}\})+f(X\cup \{x_{2}\})\geq f(X\cup \{x_{1},x_{2}\})+f(X)} , or equivalently, f ( X ∪ { x 1 } ) − f ( X ) ≥ f ( X ∪ { x 1 , x 2 } ) − f ( X ∪ { x 2 } ) {\displaystyle f(X\cup \{x_{1}\})-f(X)\geq f(X\cup \{x_{1},x_{2}\})-f(X\cup \{x_{2}\})} . A nonnegative submodular function is also a subadditive function, but a subadditive function need not be submodular. If Ω {\displaystyle \Omega } is not assumed finite, then the above conditions are not equivalent. In particular a function
f {\displaystyle f} defined by f ( S ) = 1 {\displaystyle f(S)=1} if S {\displaystyle S} is finite and f ( S ) = 0 {\displaystyle f(S)=0} if S {\displaystyle S} is infinite satisfies the first condition above, but the second condition fails when S {\displaystyle S} and T {\displaystyle T} are infinite sets with finite intersection.
Types and examples of submodular functions
Monotone A set function f {\displaystyle f} is monotone if for every T ⊆ S {\displaystyle T\subseteq S} we have that f ( T ) ≤ f ( S ) {\displaystyle f(T)\leq f(S)} . Examples of monotone submodular functions include:
… excerpt ends here. Continue reading the full article.
