Examples of applications where submodular functions are used to promote diversity?

Question

I have often seen the terms submodular functions / submodular function optimization and promoting diversity thrown together. What are examples of standard submodular functions that are used to promote diversity? Also, what is the intuition for the co-occurrence of the two phenomenon?

Answer 1

This comes up in several contexts. The Wikipedia article Submodular set function states

Submodular functions naturally occur in several real world applications, in economics, game theory, machine learning and computer vision. 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.

Notice the difference between minimization and maximization context. Diversity is "promoted" in the maximization context.

For example, in Maximizing a Submodular Function with Viability Constraints

We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant {depth}. The goal is to select a subset of $k$ species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms

Here the explicit goal is maximization of phylogenetic diversity given viability contraints.

Answer 2

I will first give an intuition of why submodular functions promote diversity and later on will provide some commonly used submodular functions in practice (for example Machine Learning).

Intuition

Submodular functions are a specific class of discrete set functions, which satisfy the property of diminishing returns. $f: 2^P \to \mathbb{R}$ (where $P$ is a ground set of elements) will be a submodular function if it satisfies the following for all $A \subseteq B \subseteq P$ and $e \in P \setminus B$

$$ f(A \cup {e}) - f(A) \geq f(B \cup {e}) - f(B)$$

Maximizing a monotone non decreasing and normalized ($f(\emptyset)=0$) submodular functions under set cardinality constraint (say size $k$) is NP-Hard, but there exists a simple greedy algorithm that returns the solution which is no worse than ($1 - 1/e$)*OPT, where OPT is the true solution. The greedy solution can be summarized as follows

• Start with an empty set $A_0 \leftarrow \emptyset $ and have $k$ passes over the ground set.
• At each t-th step $A_{t+1} \gets A_{t} \cup argmax_{e \in V \setminus A_t} f(A_t \cup {e}) - f(A_t) $

At each step, we choose an example "e" that maximally increases the $gain$, which intuitively is some kind of information we have given the current set of examples $A_t$. Therefore, the final solution we have resulted in a diverse subset.

Some examples

I will state two very common submodular functions

Facility Location Function

Refer to page 18 here. Let A denote the set of locations where we can build facilities and V denote the set of sites that benefit from these facilities. Let $S_{ij} \geq 0$ encode the benefit to site i from facility j. Then, given a set of sites V, the benefit of building facilities at locations A is given by

$$f(A; V) = \sum_{i \in V} \max_{j \in A} s_{i, j}$$

This is a submodular function in argument A. We can easily write the gain for this function as

$$f(A \cup {e}) - f(A) = \sum_{i \in V} \max(0, s_{i, e} - \max_{j \in A} s_{i, j})$$

Sums of Concave Composed with Modular Functions (SCMMs)

Modular functions are the set function that satisfies the equality in the diminishing return equation I mentioned at the beginning. Let us say we have u nonnegative modular function, $m_u: 2^P \to \mathbb{R}^+ \cup \{0\}$, such that $m_u(A) = \sum_{a \in A} m_u(a)$. We can show that if we compose this modular function by a concave function, then it will be submodular. More precisely, let $\phi_u$ be a concave function, then

$$g(A) = \sum_{u \in U} \phi_u(m_u(A))$$

is submodular. This is indeed a Sum of Concave Composed with modular functions, and hence the name. Please have a look at a wide class originating from SCMMs called Deep Submodular Functions. Moreover, see Figure 1 in this paper.