Submodular Functions

Submodularity is a rich yet tractable sub-field of non-linear combinatorial optimization which ensures tractable algorithms [KG14] and nice connections to convexity and concavity [Bac11, IB15, Lovasz83].

Let \(\mathcal{V}\) denote the ground-set of \(n\) data points \(\mathcal{V} = \{1, 2, 3,...,n\}\) and a set function \(f: 2^{\mathcal{V}} \xrightarrow{} \Re\). The function \(f\) is submodular [Fuj05] if it satisfies the diminishing marginal returns, namely:

\[f(j | \mathcal{X}) \geq f(j | \mathcal{Y})\]

for all \(\mathcal{X} \subseteq \mathcal{Y} \subseteq \mathcal{V}, j \notin \mathcal{Y}\).

Submodular functions exhibit a property that intuitively formalizes the idea of diminishing returns. That is, adding some instance \(j\) to the set \(\mathcal{X}\) provides more gain in evaluation than adding \(j\) to a larger set \(\mathcal{Y}\). Informally, since \(\mathcal{Y}\) is a superset of \(\mathcal{X}\) and already contains more information, adding \(j\) does not help as much.

Note

Using a greedy algorithm to optimize a submodular function (for selecting a subset) gives a lower-bound performance guarantee of around 63% of optimal [NWF78] to the above problem, and in practice these greedy solutions are often within 98% of optimal [Kra08].

Owing to their property of diminishing returns, they naturally model the notions of representation, coverage, diversity etc. which are useful in many applications like subset selection, summarization, etc.

Examples of Submodular functions modeling representation:

• FacilityLocationFunction

• GraphCutFunction

Examples of Submodular functions modeling coverage:

• FeatureBasedFunction

• SetCoverFunction

• ProbabilisticSetCoverFunction

Examples of Submodular functions modeling diversity:

• LogDeterminantFunction