Submodular Combinatorial Information Measures with Applications in Machine Learning

Introduction

Submodular functions generalize a number of combinatorial and information theoretic functions such as entropy, set cover, facility location, graph cut, and provide a general class of expressive models. They model aspects like diversity, coverage, information (Lin and Bilmes, 2011; Tschiatschek et al., 2014), attractive potentials (Iyer and Bilmes, 2019) and cooperation (Jegelka and Bilmes, 2011). They are closely related to convexity and concavity (Lovász, 1983; Iyer and Bilmes, 2015) and enable efficient optimization algorithms with guarantees both in the minimization (Fujishige, 2005) and maximization settings (Krause and Golovin, 2013; Lee et al., 2009; Buchbinder et al., 2015). Submodular Functions also occur naturally in several machine learning applications such as sensor placement (Krause et al., 2008; Krause and Guestrin, 2005; Guestrin et al., 2005), structured learning of graphical models (Narasimhan and Bilmes, 2004), social networks (Kempe et al., 2003), summarization (Lin and Bilmes, 2011; Tschiatschek et al., 2014; Xu et al., 2015), and data subset selection (Wei et al., 2015a), to name only a few.

Information theoretic concepts (Cover and Thomas, 1991; Yeung, 2008; Polyanskiy and Wu, 2014) such as entropy, mutual information, conditional mutual information and independence have also been extensively analyzed and used in machine learning settings. The connection between submodular optimization and information theory is even more evident when seen from the perspective of information measures over a set of random variables. Given a set of random variables $\{X_{1},\dots,X_{n}\}$, we denote $X_{A}$ as the set of random variables indexed by the set $A\subseteq\Omega$. Then the entropy (Cover and Thomas, 1991) function $H(X_{A})$, and the mutual information between a set of variables and the complement set $I(X_{A};X_{\Omega\backslash A})$, are both submodular functions (Fujishige, 2005). These have been widely used in applications such as sensor placement (Guestrin et al., 2005; Krause et al., 2008), feature selection (Krause and Guestrin, 2005; Balagani and Phoha, 2010; Hanchuan Peng et al., 2005; Liu et al., 2013), observation selection, and causal modeling (Zhou and Spanos, 2016; Steudel et al., 2010).

In this paper, we generalize concepts like conditional gain, (conditional) mutual information, total correlation, and the variation-of-information metric to general submodular functions. Many of the properties, results, and inequalities that hold for entropy, (conditional) mutual information etc. are closely associated with the underlying submodularity of the entropy function. Note that while we draw inspiration from the information theoretic quantities, there is however one fundamental difference. Entropic quantities such as entropy and mutual information are defined on sets of random variables and hence have well-defined statistical interpretations. The generalizations discussed in this paper, however, assume that the submodular functions are defined on subsets of a not-necessarily stochastic set of elements $\{x_{1},\dots,x_{n}\}$ and hence the generalizations do not necessarily have immediate stochastic implications, although they do always have combinatorial implications. We use the constructs defined in this paper in a number of optimization problems and applications related to data summarization, data selection, clustering and partitioning.

The submodular information measures we study in this work have been investigated before in special cases. (Steudel et al., 2010) generalizes an information measure to elements of any ground set, primarily in order to introduce a causal Markov condition not over random variables. Also, in (Guillory and Bilmes, 2011), an objective that corresponds to our submodular mutual information was used to show error bounds and hardness for general batch active semi-supervised learning. (Cunningham, 1983) introduce the symmetric submodular mutual information (what they call the connectivity function) and use it in studying the decomposition of submodular functions. (McGill, 1954; Shannon, 1948) were the first to show the submodular inequalities of the entropy function, and (Zhang and Yeung, 1997) showed that the class of polymatroid functions (i.e., those that are normalized, monotone, non-negative, and submodular) are strictly more general than entropy (since entropy must satisfy certain inequalities not required by a polymatroid function), thereby ensuring that the combinatorial information measures studied herein are also strictly more general. Finally, (Bilmes and Bai, 2017) uses the concept of the multi-set total correlation (Watanabe, 1960) to study properties of families of deep submodular functions. Finally, Gupta and Levin (2020) also study the submodular mutual information (which they call the Mutual Coverage). They study a few of its properties and use it in characterizing an LP relaxation to the online submodular cover problem.

This paper provides a complete picture of the combinatorial information measures defined via general submodular functions, by studying various properties, examples, optimization problems, and applications. A road-map of this paper is as follows. Section 2 introduces the information measures. Section 3 takes a closer look at their properties. Section 4 then instantiates the submodular information measures on a number of submodular functions. In Section 5, we look at a number of optimization problems around optimizing the submodular mutual information, its conditional variant, and its multi-set extension. We then connect them to applications in summarization and data selection. The proofs of all the results, along with some additional properties, examples, and optimization problems are in the Appendices. Appendix A covers the proofs of the results from Section 3, along with some more properties of the submodular information measures. Appendix B studies proofs of the instantiations of the submodular information measures presented in Section 4, and Appendix C presents the proofs for the results shown in Section 5 along with some more variants of optimization problems.

Submodular Information Theoretic Quantities

We begin by introducing the combinatorial information measures parametrized by submodular functions. Since monotone non-decreasing submodular functions generalize entropy (Zhang and Yeung, 1997), the measures below generalize the corresponding purely entropic measures.

Monotone non-negative non-decreasing submodular (or “polymatroid” (Cunningham, 1983)) functions can be viewed as information functions:

since they satisfy all of the requisite Shannon inequalities (Yeung, 2008; McGill, 1954; Shannon, 1948) that make them natural for such a purpose.

When $f(A)=H(X_{A})$, $f(A|B)$ corresponds to the conditional entropy: $H(X_{A}|X_{B})$.

We define the submodular mutual information between two sets $A,B$ denoted by $I_{f}(A;B)$ as:

It is again easy to see that $I_{f}(A;B)$ is equal to the mutual information between two random variables when $f$ is the entropy function. Note that $I_{f}(A;B)=f(A)-f(A|B)$. Also, define the submodular conditional mutual information of sets $A,B$ given set $C$ as

Define the $k$ way submodular multi-set mutual information $I_{f}(A_{1};A_{2};\dots;A_{k})$, with $A_{1},A_{2},\dots,A_{k}\subseteq\Omega$ as:

which is defined via the principle of inclusion-exclusion. We also define the submodular conditional $k$-set mutual information as

Finally, define the submodular total correlation and its conditional version as:

When $k=2$, the (conditional) multi-set mutual information and total correlation both yield the (conditional) 2-set submodular mutual information, but they are different when $k>2$. When $k=1$, the multi-set mutual information gives the submodular information function.

To encode the notion of a distance between sets $A$ and $B$ we define the submodular variation of information distance measure and denote it as

As we shall see in the next section, this quantity is actually pseudo-metric for a monotone submodular function $f$. The submodular information metric also has the intuitive form:

Properties of the Submodular Information Measures

The properties of the submodular information measures, that we introduce in this section, generally hold for all monotone submodular functions. In certain cases, interestingly and as we point out below, they hold even for relaxed versions (i.e., just submodular, or just subadditive, or just monotone). Proofs of the results here are in Appendix A.

We start with a very simple property of the submodular information functions:

Given a monotone, non-negative submodular function $f$, it holds that $f(\cup_{i}A_{i})=I_{f}(\cup_{i}A_{i})\leq\sum_{i}f(A_{i})=\sum_{i}I_{f}(A_{i})$. Furthermore, $I_{f}(A)=0$ iff $f(j)=0,\forall j\in A$. In other words, the elements $j$ are dummy variables with no information.

Below, we study three properties of the submodular conditional gain. The first and second are well known. The second property can be also viewed as the “conditioning reduces valuation” counterpart of the conditional entropy.

The conditional gain is non-negative, i.e., $f(A|B)\geq 0$ if $f$ is a monotone function. We also have the upper bound $f(A|B)\leq f(A)$ if $f$ is monotone and subadditive. Finally, $f(A|B)$ is submodular in $A$ for a given set $B$ (but not vice-versa) if $f$ is submodular.

Now we take a look at the basic properties of the submodular mutual information. Before getting into more details on the properties, we show one very interesting connection between the submodular mutual information and the submodular conditional mutual information.

Given a monotone, non-negative and normalized submodular function $f$, the conditional submodular mutual information $I_{f}(A;B\ |\ C)=I_{g}(A;B)$ where $g(A)=f(A|C)$ is also a normalized, monotone and non-negative submodular function. In other words, the conditional submodular mutual information is equal to the submodular mutual information of the conditional function.

This result follows by definition since $I_{f}(A;B\ |\ C)=f(A|C)+f(B|C)-f(A\cup B|C)=g(A)+g(B)-g(A\cup B)=I_{g}(A;B)$. While this is a very simple result, the take-away is very interesting. This means that whatever results hold for the submodular mutual information, will also hold with the conditional mutual information since it is in fact the submodular mutual information parameterized with a different submodular function.

Next, we list several interesting properties of SMIs and CSMIs. All the properties shown below also hold for the mutual information $I(X_{A};X_{B})$ as a function over sets of random variables $A$ and $B$. Two properties which follow directly by definition are: a) symmetry: $I_{f}(A;B)=I_{f}(B;A)$, and b) self-information: $I_{f}(A;A)=f(A)$. The next lemma shows the non-negativity of (conditional) submodular mutual information and provides upper and lower bounds.

When $f$ is submodular, $I_{f}(A;B)\geq 0$ and $I_{f}(A;B|C)\geq 0$. Also: $\min(f(A),f(B))\geq I_{f}(A;B)\geq f(A\cap B)$ and $\min(f(A|C),f(B|C))\geq I_{f}(A;B|C)\geq f(A\cap B|C)$.

Next, we study $I_{f}(A;B)$ (and $I_{f}(A;B|C)$ for a fixed set $B$ (and $C$). We can then view $I_{f}(A;B)$ (or $I_{f}(A;B|C)$) as a function of $A$. The following theorem studies their monotonicity and submodularity.

For a given sets $B$ and $C$, $I_{f}(A;B)$ and $I_{f}(A;B|C)$ are monotone functions in $A$, though in general, they are neither submodular nor supermodular. They are submodular, however, iff the second-order partial derivatives, $f^{(2)}(j,k;A)$ are monotone increasing or equivalently the third-order partial derivatives $f^{(3)}(i,j,k;A)=f^{(2)}(j,k;A\cup i)-f^{(2)}(j,k;A)$ are always non-negative.

Recall that for monotone functions, the first-order partial derivatives $f(j|X)\geq 0$, while for submodularity, we require the second-order partial derivatives $f^{(2)}(j,k;A)\leq 0$. A subclass of submodular functions which additionally have non-negative third-order partial derivatives satisfy the property that the submodular (conditional) mutual information function is submodular. Such functions are also called second order supermodular functions (Korula et al., 2018). In the Appendix A.3, we show that several practically useful functions like set cover, facility location and concave over modular with power and log functions satisfy this property. However we also show that a rather simple function like the uniform matroid rank function (i.e., a truncation of the form $f(A)=\min(|A|,c)$) does not satisfy this, and correspondingly, the (conditional) mutual information parametrized by these functions is not submodular. Also, the standard mutual information is not necessarily submodular in one set given the other (Krause and Guestrin, 2005). Next, we provide simple submodular upper and lower bounds for the submodular mutual information.

For a given set $B$, $I_{f}(A;B)$ can be upper/ lower bounded by two submodular functions: $f(A)-\sum_{j\in A\backslash B}f(j|B)\leq I_{f}(A;B)=f(A)-f(A|B)\leq f(A)-\sum_{j\in A\setminus B}f(j|\Omega\setminus j)\leq f(A)$.

We begin this section by studying the positivity and monotonicity of the $k$-way total correlation.

Given a monotone submodular function, it holds that $C_{f}(A_{1},\cdots,A_{k})\geq 0$. Furthermore, the $k$-way total correlation $C_{f}(A_{1};\cdots;A_{k})$ is monotone in any one of the variables fixing the others. Correspondingly, it is also monotone in all the variables.

While $I_{f}(A;B)$ and the total correlation are always non-negative, the $k$-way mutual information might be negative even for $I_{f}(A;B;C)$ when $k=3$ (similar to what (Yeung, 2008) showed in the entropic case).

The $3$-way submodular mutual information $I_{f}(A;B;C)$, can be both positive or negative. $I_{f}(A;B;C)\geq 0$ if $I_{f}(A;B)$ is submodular in $A$ for a fixed set $B$ (equivalently $A,B,C$ are redundant with respect to each other). Similarly, $I_{f}(A;B;C)\leq 0$ if $I_{f}(A;B)$ is supermodular in $A$ for a fixed set $B$ (i.e. sets $A,B,C$ are synergistic with respect to each other).

In the Appendix A.4, we provide examples of $I_{f}(A;B;C)<0$. Since the three-way mutual information is not necessarily non-negative, we do not expect the $k$-way mutual information to be non-negative in general. The next result discusses the monotonicity of the three-way mutual information.

For a given set $D$ and a function $f$, we have $I_{f}(A\cup D;B\cup D;C\cup D)\geq I_{f}(A;B;C)$ for any three subsets $A,B,C$. On the other hand with fixed sets $B,C$ we do not always have monotonicity in $I_{f}(A;B;C)$ as function of $A$.

Again, contrasting this with the two-set case, $I_{f}(A;B)$ is monotone in $A$ for a given $B$ and vice versa. However, this does not hold for the three-way mutual information. Moreover, for the four-way mutual information does not satisfy the above (i.e. $I_{f}(A\cup E;B\cup E;C\cup E;D\cup E)$ may be smaller or larger compared to $I_{f}(A;B;C;D)$, and hence we do not expect the $k$-way submodular mutual information to be monotone (cf. Appendix A.4). Finally, we provide an upper bound on the mutual Information:

Given a monotone submodular function, the following inequality: $I_{f}(A_{1};A_{2};\cdots;A_{k})\leq\min(f(A_{1}),\cdots,f(A_{k}))$ holds for $k=3$ and $4$. However, it does not hold for $k=5$, and hence does not necessarily hold for $k\geq 5$.

We next show that the submodular information distance measure is a pseudo metric for any general submodular function $f$ and then we state the condition on $f$ for $D_{f}(A;B)$ to be a metric between subsets of $\Omega$.

Given a monotone submodular function $f$, the submodular information metric: $D_{f}(A,B)=f(A\cup B)-I_{f}(A;B)$ is a pseudo metric i.e $D_{f}(A;B)=0\centernot\implies A=B$. Moreover, it is a metric if the submodular function has a curvature $\kappa_{f}>0$ where $\kappa_{f}=1-\min_{j\in\Omega}\frac{f(j|\Omega\backslash j)}{f(j|\emptyset)}$

Curvature defined above is a widely used notion in quantifying approximation bounds for submodular optimization (Conforti and Cornuejols, 1984; Iyer et al., 2013; Vondrák, 2010). Next, we provide upper and lower bounds to this metric in terms of the submodular Hamming metric and its additive version (Gillenwater et al., 2015). The submodular Hamming metric is defined as $D^{SH}_{f}(A,B)=f(A\Delta B)=f(A\backslash B\cup B\backslash A)$ and its additive version as: $D^{SHA}_{f}(A,B)=f(A\backslash B)+f(B\backslash A)$. We define the curvature at a set $A$ as $\kappa_{f}(A)=1-\min_{j\in A}\frac{f(j|A\setminus j)}{f(j|\emptyset)}$. Note that $\kappa_{f}$ defined previously corresponds to this definition via $\kappa_{f}=\kappa_{f}(\Omega)$.

Given a monotone submodular function $f$ and two sets $A,B$, it holds that: $(1-\kappa_{f}(A\cup B))D^{SH}(A,B)\leq(1-\kappa_{f}(A\cup B))D^{SHA}(A,B)\leq D_{f}(A,B)\leq D^{SH}(A,B)\leq D^{SHA}(A,B)$.

Examples of Submodular Information Measures

We instantiate the submodular information measures with modular functions, set-cover, probabilistic set cover, the facility location function, and the graph cut function. We summarize the formulations of the submodular information measures for some representative functions in Tables 1 and 2. The proofs of the results here are in Appendix B.

In this case the function $f$ is modular i.e $f(A)=w(A)=\sum_{a\in A}w(a)$, for some weight vector $w$ over the elements in the ground set $\Omega$.

If $f(A)=w(A)$ is a modular function, then $I_{f}(A;B)=w(A\cap B)$, $f(A|B)=w(A\setminus B)$, and $D_{f}(A,B)=w(A\Delta B)$. Similarly, $I_{f}(A_{1};\dots;A_{k})=w(\cap_{i=1}^{k}A_{i})$. Finally, $A\perp_{f}B$ iff $A$ and $B$ are disjoint, and $A\perp_{f}C\;|\;B$ iff $A\cap C\subseteq B$

Some interesting observations are that the submodular information metric is the weighed hamming distance. Similarly, $I_{f}(A;B)=w(A\cap B)$ is a modular function in one argument given the other.

When $f(A)=w(\gamma(A))$ is the set cover function, $I_{f}(A;B)=w(\gamma(A)\cap\gamma(B))$ and $f(A|B)=w(\gamma(A)\setminus\gamma(B))$ Similarly, $D_{f}(A,B)=w(\gamma(A)\setminus\gamma(B))+w(\gamma(B)\setminus\gamma(A))=w(\gamma(A)\Delta\gamma(B))$. Finally, the multi-set mutual information is $I_{f}(A_{1};\dots;A_{k})=w(\cap_{i=1}^{k}\gamma(A_{i}))$.

Observe that with the set cover, $I_{f}(A;B)$ will be large if $A$ and $B$ cover similar concepts. A similar form is seen with the $k$ way mutual information. Also, the submodular information metric between $A$ and $B$ is the weighted hamming distance between the respective covered sets $\gamma(A)\Delta\gamma(B)$.

Here $f$ is the Probabilistic Set Cover function, $f(A)=\sum_{i\in U}w_{i}(1-\Pi_{a\in A}(1-p_{ia}))$. $p_{ia}$ represents the probability that the element $a\in A$ covers the concept $i\in U$, where $U$ is the set of all concepts. The probabilistic set cover is a soft generalization of Set Cover function and in the case where the probabilities are fixed to be only either or $1$, we recover the formulation for the non-probabilistic counterpart. We denote by $P_{i}(A)=\Pi_{a\in A}(1-p_{ia})$, the probability that none of the elements in $A$ cover the concept $i$. Hence, $1-P_{i}(A)$ denotes that at least one element in $A$ covers the concept $i$. With the above notation, we have the following result:

With $f(A)=\sum_{i\in U}w_{i}(1-P_{i}(A))$ as the Probabilistic Set Cover function, we have that $I_{f}(A;B)=\sum_{i\in U}w_{i}(1-(P_{i}(A)+P_{i}(B)-P_{i}(A\cup B)))$. When $A$ and $B$ are disjoint, $I_{f}(A;B)=\sum_{i\in U}w_{i}(1-P_{i}(A))(1-P_{i}(B))$. Similarly, $f(A|B)=\sum_{i\in U}w_{i}P_{i}(B)(1-P_{i}(A\setminus B))$ and $D_{f}(A,B)=\sum_{i\in U}w_{i}[P_{i}(B)(1-P_{i}(A\setminus B))+P_{i}(A)(1-P_{i}(B\setminus A))]$.

Note that when $A$ and $B$ are disjoint, $I_{f}(A;B)=\sum_{i\in U}w_{i}(1-P_{i}(A))(1-P_{i}(B))$ which essentially is the probability that sets $A$ and $B$ both cover $i\in U$. Similarly with $A_{1},\dots,A_{k}$ being pairwise disjoint we have the multi set mutual information $I_{f}(A_{1},\dots,A_{k})=\sum_{i\in U}w_{i}\Pi_{j=1}^{k}(1-P_{i}(A_{j})$. With $f(A|B)$ we have that for a concept $i$, its term adds to the value only if $A\setminus B$ covers $i$ and at the same time $B$ does not, both with non-zero probability. Consequently the distance metric looks like the symmetric version of the previous observation by the virtue of its definition: $D_{f}(A;B)=f(A|B)+f(B|A)$. Another interesting observation is that when $A$ and $B$ are disjoint, $I_{f}(A;B)$ is submodular in $A$ for a given $B$ can be thought of another instance of the Probabilistic Set Cover function with the weight for each concept $i$ being $w_{i}(1-P_{i}(B))$ instead of just $w_{i}$.

Here $f$ is a facility location function, $f(A)=\sum_{i\in\Omega}\max_{a\in A}s(i,a)$ where $s$ is similarity kernel between the items in $\Omega$ such that the similarity between identical points is highest and equal to 1. In essence the value $f(A)$ models how representative the set $A$ is for the ground set $\Omega$.

With $f(A)=\sum_{i\in\Omega}\max_{a\in A}s_{ia}$, $I_{f}(A;B)=\sum_{i\in\Omega}\min(\max_{a\in A}s_{ia},\max_{b\in B}s_{ib})$. Also, $f(A|B)=\sum_{i\in\Omega}\max(0,\max_{a\in A}s_{ia}-\max_{b\in B}s_{ib})$ and $D_{f}(A,B)=\sum_{i\in\Omega}|\max_{a\in A}s_{ia}-\max_{b\in B}s_{ib}|$. Finally, $I_{f}(A_{1};\dots;A_{k})=\sum_{i\in\Omega}\min(\max_{a_{1}\in A_{1}}s_{ia_{1}},\dots,\max_{a_{k}\in A_{k}}s_{ia_{k}})$.

The mutual information, conditional gain and variation of information metric all have intuitive expressions. In particular, the mutual information is a truncated facility location function (where the truncation depends on how much $B$ represents the items $i\in\Omega$, and hence is submodular), and the distance metric is an absolute difference between the how well sets $A$ and $B$ represent each item $i$.

Here $f$ is the generalized graph cut function, $f(A)=\lambda\sum_{i\in\Omega}\sum_{a\in A}s_{ia}-\sum_{a_{1},a_{2}\in A}s_{a_{1}a_{2}}$ with $\lambda\geq 2$ and $s$ as a similarity kernel. Note that the condition on $\lambda$ is to ensure that $f$ remains a monotone submodular function.

With $f(A)=\lambda\sum_{i\in\Omega}\sum_{a\in A}s_{ia}-\sum_{a_{1},a_{2}\in A}s_{a_{1}a_{2}}$ as the generalized graph cut function, we have $I_{f}(A;B)=f(A\cap B)+2\sum_{a\in A,b\in B}s_{ab}-2\sum_{c\in A\cup B,d\in A\cap B}s_{cd}$. When $A,B$ are disjoint, it follows that $I_{f}(A;B)=2\sum_{a\in A}\sum_{b\in B}s_{ab}$ which is the cross-similarity measure for sets $A,B$. We also have $f(A|B)=f(A\setminus B)-2\sum_{a^{\prime}\in A\setminus B}\sum_{b\in B}s_{a^{\prime}b}$.

The submodular mutual information (in the case of disjoint sets $A$ are $B$) is intuitive since higher the pairwise similarity sum, higher the mutual information. The conditional gain also reduces to $f(A|B)=f(A)-2\sum_{a\in A}\sum_{b\in B}s_{ab}$, which again makes sense – higher the cross similarity between $A$ and $B$, lower is the conditional gain of adding $A$ to $B$.

Optimization Problems and Applications

In this section we study a number of applications of the information theoretic quantities introduced in Section 2, along with a few different optimization problems.

The first problem we consider is the maximization of the submodular information between a subset and its complement under a cardinality constraint, i.e. maximizing $I_{f}(A;\Omega\backslash A)$ in $A$ under cardinality constraints. This generalizes the symmetric mutual information maximization for sensor placement (Guestrin et al., 2005) and maximum graph cut under cardinality constraints. We argue that compared to just optimizing the information $f(A)$, solving $\max_{A\subseteq\Omega,|A|\leq k}I_{f}(A;\Omega\backslash A)$ is less sensitive to outliers since we are also enforcing that the subset $A$ be similar to $\Omega\setminus A$. For a concrete example, consider the set cover function where we have $I_{f}(A;\Omega\setminus A)=w(\gamma(A)\cap\gamma(\Omega\setminus A))$. Consider the case when there are outlier concepts present in the data. Trying to maximize $f$ directly will result in a subset that is likely to also cover the outlier concepts since that will increase the functional value of set $f(A)=w(\gamma(A))$. However with $I_{f}(A;\Omega\setminus A)$ if the subset $A$ covers outliers, it is likely that $\Omega\setminus A$ will not cover the same, leading to a lower functional value due to the intersection between the two and hence, in the process, it will discourage choosing such a subset. Note that $I_{f}(A;\Omega\setminus A)$ is not a monotone submodular function (but it is still submodular) and hence the $(1-\frac{1}{e})$ approximation guarantee by the greedy algorithm (Nemhauser et al., 1978) is not applicable due to non-monotonicity. It is however an instance of cardinality constrained non-monotone submodular maximization and we can achieve a $1/e$ approximation using the randomized greedy algorithm from (Buchbinder et al., 2014).

If we assume that $f(j)\leq 1\;\forall j\in\Omega$, then $g(A)=I_{f}(A;\Omega\setminus A)$ is approximately monotone for a subset $A$ with the factor $\kappa_{f}(A)$, i.e. $g(j|A)\geq-\kappa_{f}(A)\;\forall j\in\Omega,\;A\subseteq\Omega$, where $\kappa_{f}(A)=max_{j\in\Omega\setminus A}\frac{f(j|V\setminus(A\cup j)}{f(j)}$. The greedy algorithm is guaranteed to give us a subset $\hat{A}$ with $k$ elements such that $I_{f}(\hat{A};\Omega\setminus\hat{A})\geq(1-\frac{1}{e})(OPT-k\kappa_{f}(A^{*}))$ where $A^{*}$ is the optimal set.

Next, we consider the problem of maximizing the mutual information with respect to a fixed query set $Q$. An application of this is query based summarization. We consider the following general optimization problem:

where $g(A)$ is another submodular function modeling diversity/representation. This optimization problem (which we call submodular mutual information maximization or SMIMax) tries to trade-off representation/diversity (through $g(A)$) and query closeness (through $I_{f}(A;Q)$). Recall from the properties discussed in Section 2 (specifically, Theorem 3.5), that though $I_{f}(A;B)$ is monotone function in $A$ for a given $B$ it is not necessary submodular.

If $f$ is second order supermodular, i.e. $f$ satisfies $f^{(3)}(i,j,k;A)\geq 0$ and $g$ is monotone submodular, the greedy algorithm achieves a $1-1/e$ approximation for SMIMax. There exists no polynomial time approximation algorithm for SMIMax. Specifically, with $n$ being the size of the problem instance and $\alpha(n)>0$ to be a positive poly-time computable function of $n$, there cannot exist a polynomial time algorithm which is guaranteed to find a subset $\hat{A}$ ($|\hat{A}|\leq k$) such that $I_{f}(\hat{A};B)\geq\alpha(n)OPT$ with $OPT=\max_{A\subseteq\Omega,|A|\leq k}I_{f}(A;B)$.

Several useful submodular functions like facility location and set cover satisfy this. Unlike query based summarization, privacy preserving summarization’s goal is to select a summary $A$ that has low submodular mutual information to a set $P$ which is private information the summary should not represent. Following the above, we can pose this as $\max_{A\subseteq\Omega,|A|\leq k}\lambda g(A)-I_{f}(A;P)=\max_{A\subseteq\Omega,|A|\leq k}\lambda g(A)+f(P|A)$. We call this NSMIMax, since it involves maximizing the negative of submodular mutual information plus a submodular function. Unfortunately, NSMIMax is not tractable (in most cases, as we show below), and hence we modify the objective to maximize the conditional gain $f(A|P)$ instead of maximizing $f(P|A)$. Note that this is a different optimization problem, but it tries to achieve a similar goal, i.e., obtain a set $A$ as different as possible from $P$. The optimization problem is (we call it CGMax): $\max_{A\subseteq\Omega,|A|\leq k}\lambda g(A)+f(A|P)$.

NSMIMax is an instance of (non-monotone) submodular maximization if $f$ is second-order submodular, i.e. $f$ satisfies $f^{(3)}(i,j,k;A)\leq 0$. In the worst case, there exists submodular function $f$ such that NSMIMax is inapproximable. However, CGMax is an instance of monotone submodular maximization if $f$ and $g$ are monotone, and correspondingly the greedy algorithm admits a $1-1/e$ approximation.

For many subclasses of functions, the third-order partial derivatives are non-negative instead of non-positive and hence NSMIMax is typically a non-monotone difference of submodular functions, and hence a much harder problem. However, CGMax is always monotone submodular maximization and for this reason preferred.

Finally, we consider the scenario of simultaneous query based and privacy preserving summarization. We formulate this in two ways. The first is to solve: $\max_{A\subseteq\Omega,|A|\leq k}I_{f}(A;Q)-I_{f}(A;P)+\lambda g(A)$. Unfortunately, this is again a difference of submodular functions and not approximable. The second formulation is

or in other words maximize the conditional submodular mutual information. We call this problem: CSMIMax. This formulation (as we argue in Appendix C), tries to obtain a set $A$ that is similar to $Q$ yet independent of $P$. The following Lemma provides the approximation bound for CSMIMax.

CSMIMax is an instance of monotone submodular maximization if the third-order partial derivatives are not negative, i.e. $f^{(3)}(i,j,k;A)=f^{(2)}(j,k;A\cup i)-f^{(2)}(j,k;A)\geq 0$. As a result, the greedy algorithm (Nemhauser et al., 1978) achievea a $1-1/e$ approximation .

What is also interesting is that CSIMax yields SMIMax and CGMax when considering only query or privacy preserving summarization. In particular, if $Q=V,I_{f}(A;V|P)=f(A|P)$ which is CGMax. Similarly, when $P=\emptyset,I_{f}(A;Q|\emptyset)=I_{f}(A;Q)$ which is SMIMax. Furthermore, when both $P=\emptyset,Q=V,I_{f}(A;V|\emptyset)=f(A)$ (which is query and privacy agnostic summarization).

We end this section by studying the problem of maximizing and minimizing the $k$-way multi-set information measures (multi-set submodular mutual information and multi-set submodular total correlation) such the sets $A_{1},\cdots,A_{k}$ form a partition of $\Omega$ (i.e., for all $i,j$, $A_{i}\cap A_{j}=\emptyset$ and $\cup_{i=1}^{k}A_{i}=\Omega$). An application of the minimization problem is clustering (Narasimhan et al., 2006) while the maximization problem can be applied to diverse partitioning (Wei et al., 2015b). Maximizing and minimizing the submodular total correlation over partitions turn out to be related to two well studied problems.

Minimizing the $k$-way submodular total correlation is equivalent the submodular multi-way partition (Zhao et al., 2005; Chekuri and Ene, 2011) minus a constant. Similarly, maximizing the $k$-way total correlation is the submodular is exactly the submodular welfare problem (Feige and Vondrak, ; Vondrak, 2008) minus a constant.

In Appendix C, we study the multi-set mutual information partitioning problems. In particular, we show that minimizing the multi-set submodular mutual information does not make sense and for clustering, the $k$-way total correlation is better. In the maximization setting though, the $k$-way submodular mutual information is related to robust partitioning (Wei et al., 2015b), while the total correlation is the average partitioning.

Finally we take a look at the centroid finding problem in the context of the submodular information metric in an unconstrained setting. We want to find a subset $A$ over all subsets of $\Omega$ such that it is as similar as possible to a collection $S_{1},S_{2},\dots,S_{m}$ with respect to the submodular information metric:

This problem is related to problem of minimizing the submodular hamming metric (and the additive submodular hamming metric) as shown in Lemma 3.12. We use this to show the following approximation guarantee for Equation (13).

We can approximately solve the problem in equation 13 with the approximation guarantee of $1-\kappa_{f}$, where $\kappa_{f}$ is the worst case curvature of $f$.

The proof of this result is in Appendix C.4.

Conclusion

In conclusion, we study a number of submodular information measures, their properties and instantiations on a number of common submodular functions. We also investigate a number of optimization problems related to these information measures on data summarization. In future work, we would like to study learning problems with these information measures, experimentally validate the proposed algorithms on real and synthetic data, and also apply them to other problems such as data subset selection and feature selection. For future work, we will study applications of the submodular information measures, specifically, the submodular mutual information, submodular conditional gain, submodular multi-set mutual information and submodular total correlation to applications such as summarization, targeted subset selection, clustering, disparate partitioning, and diverse $k$-best MAP inference.

References

Appendix A Proofs of the Results from Section 3 and Additional Results

In this section, we prove the Lemmas introduced in Section 3 and also some results we did not cover in Section 3 due to space limitations.

The first part of the proof follows directly from the subadditivity of $f$, since $f$ is submodular. The second part follows from the very simple observation that $I_{f}(A)\geq f(j),\forall j\in A$ and since $f(j)\geq 0$ (because of non-negativity) and $I_{f}(A)=0$, this implies that $f(j)=0,\forall j\in A$.

We contrast the second with the result of entropy where $H(X)=0$ iff $X$ is a deterministic variable. In the case of combinatorial information functions, it means the variables $j\in A$ have no information. Also note that the proof has only used monotonicity and non-negativity of the information functions.

A.2 Submodular Conditional Gain: Proofs

Finally, if $f$ is submodular, $f(A|B)=f(A\cup B)-f(B)$ will be a submodular function in $A$ as $f(A\cup B)$ is submodular in $A$ for a fixed set $B$ and $f(B)$ is just a constant. Note that however, $f(A|B)=f(A\cup B)-f(B)$ is not submodular in $B$ for a given $A$.

A.2.2 Other Results on Conditional Gain

Similar to the submodular information functions, we study the case when the conditional $f(A|B)=0$.

Given a monotone, non-negative submodular function $f$, it holds that $f(A|B)=0$ iff $f(j|B)=0,\forall j\in A$. In other words, given $B$, every element $j\in A$ has no additional information.

Again, invoking monotonicity, we have $f(B)=f(A\cup B)\geq f(j\cup B),\forall j\in A$. Also, because of monotonicity, we have that $f(j\cup B)\geq f(B)$ which implies that $f(B\cup j)=f(B),\forall j\in A$ which implies that $f(j|B)=0,\forall j\in A$.

Again, contrasting with random variables, note that $H(Y|X)=0$ iff $Y$ is a deterministic function of $X$, or in other words, $Y$ has no extra information on top of the information that $X$ has. In the case of combinatorial information functions, this means that the elements $j\in A$ have no extra information over and above the information contained in set $B$. Also note that the proof has only used monotonicity of the information functions.

Finally, we study properties of the conditional gain that follow directly from definition.

Given a submodular function $g(A)=f_{1}(A)+f_{2}(A)$, $g(A|B)=f_{1}(A|B)+f_{2}(A|B)$. Furthermore, if $f(A)=c$ (a constant), then $f(A|B)=0$, for all sets $A,B\subseteq\Omega$. FInally, if $g(A)=\lambda f(A)$, $g(A|B)=\lambda f(A|B)$.

A.3 Submodular Mutual Information: Proofs

The non-negativity of $I_{f}(A;B)$ follows from the definition of a subadditive function since $I_{f}(A;B)=f(A)+f(B)-f(A\cup B)$ and for a subadditive function we have

Similarly, for the conditional mutual information note that

Note that thanks to the submodularity of $f$, we have that:

The last inequality follows from the monotonicity of $f$. Hence when $f$ is monotone submodular, the conditional mutual information is non-negative.

For the lower bound, we use the submodularity of $f$: $f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\implies I_{f}(A;B)=f(A)+f(B)-f(A\cup B)\geq f(A\cap B)$. For the upper bound, we rewrite the definition as $I_{f}(A;B)=f(A)-f(A|B)=f(B)-f(B|A)$ and since $f(A|B),f(B|A)\geq 0\;\forall A,B\subseteq\Omega$ for a monotone submodular function (from Lemma 3.2) this gives us $I_{f}(A;B)\leq f(A)$ and $I_{f}(A;B)\leq f(B)\implies I_{f}(A;B)\leq\min(f(A),f(B))$.

The upper and lower bounds for conditional mutual information similarly hold, just replacing $f(A)$ and $f(B)$ by $f(A|C)$ and $f(B|C)$ and using Lemma 3.3.

Consider $g(A)=I_{f}(A;B)$ as a function of $A$ with a fixed set $B$. Now we consider the gain of adding an element $j\notin A\cup B$ to $A$ i.e $g(j|A)=f(j|A)-f(j|A\cup B)$. Since $f$ is a submodular function we will have $f(j|A)\geq f(j|A\cup B)\implies g(j|A)\geq 0$ and hence we have monotonicity. We can also see that $I_{f}(A;B)=f(A)-f(A\cup B)+f(B)$ is a difference of submodular functions since both $f(A)$ and $f(A\cup B)$ are submodular functions in $A$ when $B$ is fixed. A similar argument for the other case when set $A$ is fixed and we view $I_{f}(A;B)$ as a function of $B$.

Next, we study the submodularity of $g(A)$. First, we show that non-negativity of the third order partial derivatives $f^{(3)}(i,j,k;A)=f^{(2)}(j,k;A\cup i)-f^{(2)}(j,k;A)$ is the same as monotonicity of the second-order partial derivatives. Note that

Next, recall that $g(j|A)=f(j|A)-f(j|A\cup B)$. Now since $f$ additionally satisfies the monotonicity property for the second-order partial derivatives, we have:

This means that is $C\supseteq A,g(j|C)\leq g(j|A)$ which implies that $g$ is submodular. To prove the converse, assume that $I_{f}(A;B)$ is submodular, but $f^{(2)}(j,k;A)$ is not necessarily monotone. In other words, there exists sets $A,C$, with $A\cap C=\emptyset$ such that $f^{(2)}(j,k;A)\geq f^{(2)}(j,k;A\cup C)$. Define $g(A)=I_{f}(A;C)$. Following the chain of inequalities like above, this implies that $g(j|A\cup k)\geq g(j|A)$ which contradicts the submodularity of $I_{f}(A;C)$ for any fixed set $C$.

Finally, we note that the submodularity of $I_{f}(A;B|C)$ for fixed sets $B,C$ holds from Lemma 3.3. In particular, define $g(A)=f(A|C)$ and observe that $I_{g}(A;B)$ is submodular in $A$ for given $B,C$ if $g^{(3)}(i,j,k;A)\geq 0$. Now since $f^{(3)}(i,j,k;A)\geq 0,\forall A\subseteq\Omega$, it holds that $f^{(3)}(i,j,k;A\cup C)\geq 0,\forall A\subseteq\Omega$ and hence $g^{(3)}(i,j,k;A)\geq 0$.

Next, we study subclasses of submodular functions which satisfy the condition $f^{(2)}(j,k;A)=f(A\cup j\cup k)-f(A\cup i)-f(A\cup j)+f(A)$ is monotonically increasing in $A$, or in other words, $I_{f}(A;B)$ is submodular in $A$ for a fixed $B$.

We first show that the Facility Location satisfies this condition. We start with the $\max$-function.

If $f(A)=\max_{i\in A}w_{i}$, then $f^{(2)}(j,k;A)$ is a monotonically increasing function in $A\subseteq\Omega\backslash\{j,k\}$ for a given $j,k$.

Define $W_{A}=\max_{i\in X}w_{i}$. Notice that $f^{(2)}(j,k;A)=\max(W_{A},w_{j},w_{k})-\max(W_{A},w_{j})-\max(W_{A},w_{k})-w_{A}$. We try to analyze if this function is monotone in $A$. Lets assume first that $w_{A}$ is smaller than both $w_{i},w_{j}$. In this case, $f^{(2)}(j,k;A)$ is either $w_{A}-w_{j}\leq 0$ or $w_{A}-w_{k}\leq 0$ depending on whether $w_{j}\leq w_{k}$ or $w_{j}\geq w_{k}$. Furthermore, if $w_{A}$ is larger than either $w_{j}$ or $w_{k}$, notice that $f^{(2)}(j,k;A)=0$. Hence $f^{(2)}(j,k;A)$ is an increasing function and hence proved.

A simple observation is that if $f_{1}$ and $f_{2}$ both satisfy the property of the non-negativity of the third-order partial derivatives, any convex combination of $f_{1}$ and $f_{2}$ will also satisfy this. Hence, this implies that the Facility Location satisfies this property as well.

If $f(A)$ is the Facility Location Function, then $f^{(2)}(j,k;A)$ is a monotonically increasing function in $A\subseteq\Omega\backslash\{j,k\}$ for a given $j,k$.

Next, we show that the Set Cover and Concave over Modular functions with Power Functions satisfy this.

If $f(A)=w(\gamma(A))$ or $f(A)=[w(A)]^{a},a\in$, then $f^{(2)}(j,k;A)$ is a monotonically increasing function in $A\subseteq\Omega\backslash\{j,k\}$ for a given $j,k$.

Lets start with the Set Cover Function. Note that the set-cover function satisfies $\gamma(A\cup B)=\gamma(A)\cup\gamma(B)$. Plugging this into the definition of the second-order partial derivatives, we get $f^{(2)}(j,k;A)=w(\gamma(A)\cup\gamma(i)\cup\gamma(j))-w(\gamma(A)\cup\gamma(i))-w(\gamma(A)\cup\gamma(j))+w(\gamma(A))=w(\gamma(A)\cap\gamma(i)\cap\gamma(j))$ which is monotonically increasing since the set cover is monotonically increasing.

Next, we look at concave over modular functions: $f(A)=[w(A)]^{a}$. Then, $f^{(2)}(j,k;A)=[w(A)+w(j)+w(k)]^{a}-[w(A)+w(j)]^{a}-[w(A)+w(k)]^{a}+[w(A)]^{a}$. To show that this is monotone, we look at its continious extension: $g(x)=[x+w(j)+w(k)]^{a}-[x+w(j)]^{a}-[x+w(k)]^{a}+[x]^{a}$ at $x=w(A)$. Note that $g^{\prime}(x)=a/[x+w(j)+w(k)]^{1-a}-a/[x+w(j)]^{1-a}-a/[x+w(k)]^{1-a}+a/x^{1-a}$. Finally, we can see that $g^{\prime}(w(A))\geq 0$ since the function $h(A)=a/w(A)^{1-a}$ is a supermodular function in $A$.

A corollary of the above is that sums of power concave over modular functions satisfy the monotone double gain property. We end this section, by showing, somewhat surprisingly that a simple uniform matroid rank function does not satisfy this property (and hence not all concave over modular functions satisfy this).

If $f(A)=\min(|A|,k)$, then $f^{(2)}(j,k;A)$ is not necessarily a monotonically increasing function in $A\subseteq\Omega\backslash\{j,k\}$ for a given $j,k$.

Lets start with $A=\emptyset$. Its easy to see that $f^{(2)}(j;k,A)=0$. Next, set $A$ to be a set of size $k-1$. Now, $f^{(2)}(j;k,A)=k-k-k+(k-1)=-1$. Hence $f^{(2)}(j;k,A)$ is not monotonically increasing in $A$. Similarly, if $A$ is a set of size $k$, again, the value of $f^{(2)}(j;k,A)=0$ and as a result, in this case $f^{(2)}(j;k,A)$ is neither increasing nor decreasing.