PaperlayerView exact revision on arXiv

Source-linked AI summary

Submodular Combinatorial Information Measures with Applications in Machine Learning

Rishabh Iyer, Ninad Khargonkar, Jeff Bilmes, Himanshu Asnani

arXiv:2006.15412v6cs.LGcs.DScs.ITmath.ITmath.OCstat.ML

TL;DR

The paper studies normalized, monotone, submodular set functions over a ground set of data points. The paper parameterizes combinatorial information measures with submodular functions, including conditional variants and objectives for selection and query- or privacy-based summarization. The paper derives intuitive forms for submodular information measures, including facility-location and set-cover instantiations, and connects their optimization to selection and summarization problems.

  • Problem

    The paper studies normalized, monotone, submodular set functions over a ground set of data points.

    Source: §1 · p. 2

  • Method

    The paper parameterizes combinatorial information measures with submodular functions, including conditional variants and objectives for selection and query- or privacy-based summarization.

    Source: §1 · p. 2, §3 · p. 5, §5 · pp. 9–10

  • Results

    The paper derives intuitive forms for submodular information measures, including facility-location and set-cover instantiations, and connects their optimization to selection and summarization problems.

    Source: §4 · pp. 8–9, §5 · pp. 9–10

  • Takeaways & Limitations

    Maximizing SMI between a selected subset and its complement is argued to be less sensitive to outliers than optimizing f(A) alone.

    Source: §5 · p. 9

    The paper assumes f is normalized, monotone, and submodular unless specified otherwise.

    Source: §1 · p. 2

Abstract

from arXiv · show

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, and saturated coverage functions, and see that they all have mathematically intuitive and practically useful expressions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy-preserving summarization -- and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning.

1. Introduction

Submodular functions provide expressive models for combinatorial and information-theoretic properties and support machine-learning applications. The paper extends information measures to general submodular functions and outlines their properties, instantiations, and applications.

Motivation

  • Submodular functions generalize entropy, set cover, facility location, and graph cut, while modeling diversity, coverage, information, attractive potentials, and cooperation.They also arise in applications including sensor placement, structured learning, social networks, summarization, and data subset selection.Source: §1 · pp. 1–2

Contribution

  • The paper generalizes conditional gain, conditional and unconditional mutual information, total correlation, and variation of information to sets that need not be random variables.Unlike entropic quantities, these generalizations have combinatorial implications but do not necessarily have immediate stochastic interpretations.Source: §1 · p. 2
  • The measures are strictly more general than their entropic counterparts because they are parameterized by submodular functions, which themselves strictly generalize entropy.The paper notes that polymatroid functions need not satisfy certain inequalities required of entropy.Source: §1 · pp. 2–3

Related work

  • Prior work studied special cases, including a non-random-ground-set information measure, an SMI objective for batch active semi-supervised learning, and symmetric SMI as a connectivity function.The paper also situates its generalizations alongside work on multi-set total correlation and mutual coverage.Source: §1 · pp. 2–3

Paper scope

  • The paper develops the measures' properties and examples, then studies optimization problems and applications in summarization and data selection.It places proofs and additional properties, examples, and optimization variants in appendices.Source: §1 · p. 3

2. Submodular Information Theoretic Quantities

This section defines combinatorial information measures by parameterizing them with submodular functions. When the function is entropy, the corresponding measures recover entropic quantities.

General construction

  • Monotone non-decreasing submodular functions parameterize the measures and generalize entropy, so the resulting combinatorial measures generalize entropic ones.Polymatroid functions satisfy the Shannon inequalities used to motivate their interpretation as information functions.Source: §2 · p. 3

Conditional gain

  • Conditional gain f(A|B) measures the increase in function value from adding B to A, and becomes conditional entropy when f(A)=H(X_A).The passage defines the conditional gain and states its entropy-function correspondence.Source: §2 · p. 3

Submodular mutual information

  • Submodular mutual information is defined for two sets, while its conditional form is defined given a third set; with entropy, these recover mutual information.The text states that I_f(A;B)=f(A)−f(A|B).Source: §2 · pp. 3–4

Multi-set measures and distance

  • The framework defines k-set mutual information and total correlation, with the multi-set forms coinciding at k=2 but differing for k>2.It also defines a submodular variation-of-information distance, which the text says is a pseudometric for monotone submodular f.Source: §2 · p. 4

3. Properties of the Submodular Information Measures

The section establishes properties of submodular information measures, including conditions for submodularity and limits on higher-order behavior. It also gives bounds and metric results under stated assumptions.

Submodular information functions

  • For monotone non-negative submodular f, the information of a union equals the multi-set information and is bounded by the sum of the individual information values.The information of A is zero exactly when every element of A is a dummy variable with no information.Source: §3 · p. 5

Conditional gain

  • Conditional gain is non-negative for monotone f, bounded above by f(A) when f is also subadditive, and submodular in A for fixed B when f is submodular.Source: §3 · p. 5

Submodular mutual information

  • Conditional SMI equals SMI for the conditional function g(A)=f(A|C), so SMI results also apply to conditional SMI through this reparameterization.The identity is stated for normalized, monotone, non-negative submodular f.Source: §3 · p. 5
  • For submodular f, SMI and conditional SMI are non-negative and bounded above by the smaller of their respective set values.Their lower bounds are f(A∩B) and f(A∩B|C), respectively.Source: §3 · p. 5
  • SMI and conditional SMI are monotone in one set, but are submodular in that set iff the third-order partial derivatives of f are non-negative.The paper identifies set cover, facility location, and certain concave-over-modular functions as satisfying this condition, while uniform matroid rank does not.Source: §3 · pp. 5–6

Multi-set measures

  • For monotone submodular f, k-way total correlation is non-negative and monotone in each set, while three-way SMI can be positive or negative.Three-way SMI is non-negative when two-set SMI is submodular in one argument and non-positive when it is supermodular there.Source: §3 · p. 6
  • Adding a shared set to all three arguments cannot decrease three-way SMI, but it is not always monotone in one argument with the others fixed.The analogous shared addition to four-way SMI may increase or decrease it; the stated upper bound by the smallest set value holds for k=3,4 but not k=5 or necessarily higher.Source: §3 · p. 6

Submodular information metric

  • The submodular information distance is a pseudometric for monotone submodular f and is a metric when f has positive curvature.Its bounds relate it to the submodular Hamming distance and its additive version.Source: §3 · p. 7

4. Examples of Submodular Information Measures

The section instantiates submodular information measures with several common functions, yielding concrete overlap, coverage, and representation interpretations. These forms make the measures’ behavior depend on what sets cover or represent.

Modular Function

  • For a modular function, mutual information is the weight of the intersection, conditional gain is the weight of the set difference, and the information metric is weighted symmetric difference.Mutual information is modular in either argument when the other is fixed.Source: §4 · pp. 7–8

Weighted Set Cover

  • For set cover, mutual information is the weight of concepts covered by both sets, and the information metric is the weighted Hamming distance between their covered concept sets.Mutual information is large when A and B cover similar concepts.Source: §4 · p. 8

Probabilistic Set Cover

  • For probabilistic set cover, mutual information between disjoint sets sums the weighted probabilities that both sets cover each concept.The disjoint-set expression uses each set’s coverage probability for the concept.Source: §4 · p. 8

Facility Location

  • Facility-location mutual information is a truncated facility-location function, while its distance measures per-item differences in how well two sets represent the ground set.The truncation depends on how much B represents each item.Source: §4 · pp. 8–9

Generalized Graph Cut

  • For disjoint sets, generalized graph-cut mutual information is twice their cross-similarity sum, so greater cross-similarity means greater mutual information.Conditional gain decreases with cross-similarity between A and B.Source: §4 · p. 9

5. Optimization Problems and Applications

The section connects submodular information objectives to selection, summarization, and partitioning problems. It gives approximation guarantees under stated conditions and distinguishes tractable conditional-gain formulations from harder objectives.

Submodular Mutual Information Based Selection

  • Maximizing mutual information between a subset and its complement can discourage selecting outlier concepts, but the objective is non-monotone and admits a 1/e randomized-greedy approximation.For set cover, the objective rewards concepts covered by both the subset and its complement.Source: §5 · p. 9

Query Based and Privacy Preserving Summarization

  • For query summarization, SMIMax trades off query closeness and diversity, and greedy achieves a 1−1/e approximation when f has non-negative third-order partial derivatives and g is monotone submodular.Several useful functions, including facility location and set cover, satisfy the derivative condition.Source: §5 · p. 10
  • Privacy-preserving summarization replaces the often-intractable negative-mutual-information objective with CGMax, while CSMIMax seeks a set similar to Q yet independent of P.Under the non-negative third-order derivative condition, CSMIMax is monotone submodular and greedy achieves a 1−1/e approximation.Source: §5 · pp. 10–11

Clustering and Partitioning using Multi-Set Information Measures

  • For partitioning, minimizing multi-set total correlation corresponds to submodular multi-way partitioning, while maximizing it corresponds to submodular welfare; minimizing multi-set mutual information is not suitable for clustering.Maximizing multi-set mutual information is related to robust partitioning, whereas total correlation corresponds to average partitioning.Source: §5 · p. 11

Minimization of the Submodular Information Metric

  • The centroid-finding problem for the submodular information metric has an approximation guarantee of 1−κ_f, where κ_f is the worst-case curvature of f.The problem is related to minimizing the submodular Hamming metric and its additive version.Source: §5 · p. 11

6. Conclusion

The conclusion surveys the paper’s information measures, their properties, function-specific instantiations, and optimization applications. The supplied appendix passages prove selected results, including facts about zero information and conditional gain.

6. Conclusion

  • The paper studies submodular information measures, their properties and instantiations, and optimization problems involving data summarization.Future work includes experimental validation on real and synthetic data and applications such as subset selection and feature selection.Source: §6 · p. 12

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

  • Appendix A proves lemmas introduced in Section 3 and presents additional results omitted there for space.Source: Appendix A · p. 15

A.1. Submodular Information Functions: Proofs

  • For submodular information functions, a set has zero information only when each of its elements has zero function value.The proof uses monotonicity and non-negativity.Source: §A.1 · p. 15

A.2.1. PROOF OF LEMMA 2 (PROPERTIES OF CONDITIONAL GAIN)

  • Conditional gain f(A|B) is submodular in A for fixed B, but is not submodular in B for fixed A.Source: §A.2.1 · p. 16

A.2.2. OTHER RESULTS ON CONDITIONAL GAIN

The appendix establishes properties and examples for conditional gain and submodular information, including bounds, conditions for submodularity, and limitations on higher-order information measures.

A.2.2. OTHER RESULTS ON CONDITIONAL GAIN

  • For monotone, non-negative submodular f, f(A|B)=0 exactly when every element of A has zero gain given B.In that case, each element in A adds no information beyond B.Source: §A.2.2 · p. 16

A.3.1. PROOF OF LEMMA 4 (NON-NEGATIVITY AND BOUNDS OF If(A; B))

  • When f is monotone submodular, conditional mutual information is non-negative, and its upper and lower bounds extend by replacing f(A) and f(B) with conditional gains.Source: §A.3.1 · p. 17

A.3.2. PROOF OF THEOREM 5 (MONOTONICITY AND SUBMODULARITY OF If(A; B))

  • For fixed B, submodular mutual information is monotone in A; it is submodular in A when the second-order partial derivatives are monotone increasing.The second-order condition identifies the function class for which this additional submodularity holds.Source: §A.3.2 · p. 17, §A.3.3 · p. 18

A.3.3. EXAMPLES OF WHEN IS If(A; B) SUBMODULAR

  • Facility location, set cover, and power concave-over-modular functions satisfy the condition for submodular mutual information, but uniform matroid rank need not.For uniform matroid rank, mutual information can be neither submodular nor supermodular in A for fixed B.Source: §A.3.3 · pp. 18–19

A.3.4. PROOF OF LEMMA 6 (MODULAR UPPER/LOWER BOUNDS OF If(A : B))

  • The modular upper and lower bounds for conditional gain also yield corresponding bounds for submodular conditional mutual information.Source: §A.3.4 · p. 20

A.4.1. PROOF OF LEMMA 7 (MONOTONICITY AND POSITIVITY OF MULTI-SET TOTAL CORRELATION)

  • Multi-set total correlation is non-negative and monotone in each argument under the stated monotone submodular assumptions.Source: §A.4.1 · p. 20

A.4.2. PROOF OF LEMMA 8 AND NEGATIVITY OF THE k-SET SUBMODULAR MUTUAL INFORMATION

  • Three-set submodular mutual information can be negative, so k-set submodular mutual information is not necessarily non-negative.Source: §A.4.2 · p. 20

A.4.3. PROOF OF LEMMA 9 AND MONOTONICITY OF THE k-SET SUBMODULAR MUTUAL INFORMATION

The appendix establishes monotonicity properties and upper bounds for multi-set submodular mutual information, while identifying cases where those properties fail. In particular, the upper bound by the smallest set value does not hold generally from five sets onward.

A.4.3. PROOF OF LEMMA 9 AND MONOTONICITY OF THE k-SET SUBMODULAR MUTUAL INFORMATION

  • Adding a shared set D to all three arguments cannot decrease three-way submodular mutual information, but fixing B and C does not guarantee monotonicity in A.The fixed-argument failure is demonstrated using a uniform matroid function.Source: §A.4.3 · p. 21
  • For four or more arguments, multi-set submodular mutual information need not be monotone, even when the same elements are added to every argument.The four-way case has a counterexample with disjoint sets under a uniform matroid function.Source: §A.4.3 · p. 21

A.4.4. PROOF OF LEMMA 10 AND UPPER BOUNDS FOR THE k-SET SUBMODULAR MUTUAL INFORMATION

  • Three-way mutual information is bounded above by the minimum of its three set values, and the same upper bound holds for four-way mutual information.The four-way bound follows from monotonicity of the three-way measure when a shared set is added.Source: §A.4.4 · pp. 21–22
  • The minimum-set upper bound fails for five arguments and is therefore not guaranteed for k ≥ 5.The example gives five-way information equal to 3 while the minimum set value is 1.Source: §A.4.4 · p. 22
  • For any number of sets, the minimum-set upper bound holds when the conditional multi-set information is non-negative; this applies to special cases of facility location and set cover.The proof uses the decomposition of multi-set information into the preceding measure minus conditional information.Source: §A.4.4 · p. 22

A.5.1. PROOF OF LEMMA 11 (VARIATION OF INFORMATION IS A PSUEDOMETRIC)

These appendix proofs characterize variation of information and derive information-measure expressions for several submodular functions. They also give bounds relating variation of information to the submodular Hamming metric.

A.5.1. PROOF OF LEMMA 11 (VARIATION OF INFORMATION IS A PSUEDOMETRIC)

  • Variation of information is a pseudometric, but distinct sets can have zero distance when the function is a uniform matroid rank function.If the function has positive curvature, zero distance implies the sets are equal.Source: §A.5.1 · pp. 22–23

A.5.2. PROOF OF LEMMA 12 (UPPER AND LOWER BOUNDS WITH THE SUBMODULAR HAMMING METRIC)

  • Variation of information is bounded above by the submodular Hamming distance and by a tighter bound using the symmetric difference.It is bounded below by (1 − κ_f(A ∪ B)) times the submodular Hamming distance.Source: §A.5.2 · p. 23

B.1. Proof of Lemma 13 (Modular Function)

  • For a modular function, pairwise submodular mutual information is the weight of the intersection, conditional gain is the weight of the set difference, and variation of information is the weight of the symmetric difference.The multi-set expression is also given by inclusion-exclusion.Source: §B.1 · p. 23

B.2. Proof of Lemma 14 (Set Cover Function)

  • For set cover, multi-set mutual information is the weight of the concepts covered by every set.This follows from the inclusion-exclusion expression for the set-cover function.Source: §B.2 · p. 24

B.3. Proof of Lemma 15 (Probabilistic Set Cover Function)

  • For probabilistic set cover, independence under the submodular measure holds exactly when no concept is covered with certainty by both sets.The passage defines P_i(A) as the probability that no element in A covers concept i and gives the independence condition in terms of these probabilities.Source: §B.3 · pp. 24–25
  • The probabilistic set-cover proofs also express conditional gain and variation of information using the probabilities that concepts remain uncovered.For disjoint sets, the pairwise mutual-information expression uses the product of their non-coverage probabilities.Source: §B.3 · pp. 24–25

B.4. Proof of Lemma 16 (Facility Location)

For facility location, the appendix derives expressions for pairwise and multi-set submodular mutual information. The multi-set measure is a sum of minima of the sets’ maximum weights.

B.4. Proof of Lemma 16 (Facility Location)

  • With s(i, i) = 1 as the maximum kernel similarity, pairwise mutual information reduces to counting shared elements.The passage’s decomposition treats the shared-element terms separately from the remaining similarity terms.Source: §B.4 · p. 25
  • When B is the complement of A, the facility-location mutual-information expression becomes a symmetric comparison of the sets’ maximum similarities.The resulting expression sums the positive differences between A’s and B’s best similarities for each ground-set element.Source: §B.4 · p. 25
  • Facility-location multi-set mutual information is the sum, over ground-set elements, of the minimum maximum-similarity value across the sets.For each element, the maximum similarity is taken over each set before the minimum across sets.Source: §B.4 · p. 26

B.5. Proof of Lemma 17 (Generalized Graph Cut)

The appendix derives a cross-similarity expression for generalized graph-cut information and proves a curvature-dependent greedy guarantee for submodular mutual-information-based selection. It also frames query-based and privacy-preserving summarization in terms of approximation guarantees and hardness.

B.5. Proof of Lemma 17 (Generalized Graph Cut)

  • For generalized graph cut, pairwise submodular mutual information reduces to cross-similarities between A and B, and disjoint sets are independent exactly when all cross-similarities vanish.The passage also derives a conditional-gain expression for disjoint sets.Source: §B.5 · p. 26

C.1. Proof of Lemma 18 (Submodular Mutual Information Based Selection)

  • The selection objective g(A) = I_f(A; Ω \ A) can have negative marginal gains, bounded below by −κ_f(A) when each singleton value is at most 1.This motivates the proof’s use of approximate monotonicity.Source: §C.1 · p. 26
  • For the greedy sequence, starting from A0=∅ with value zero and setting Â=Ak, the stated bound for g(Â) contains a (1−1/k)^k factor and the curvature-adjusted term g(A*)−kκf(A*).Source: §C.1 · p. 27

C.2. Query Based and Privacy Preserving Summarization

  • The appendix studies approximation guarantees and hardness for query-based and privacy-preserving summarization formulations.Source: §C.2 · p. 27

C.2.1. QUERY BASED SUMMARIZATION: PROOF OF THEOREM 19

The section establishes when query-based submodular mutual information maximization has a greedy guarantee and presents a constrained alternative that gives explicit control over query similarity.

C.2.1. QUERY BASED SUMMARIZATION: PROOF OF THEOREM 19

  • When f has non-negative third-order partial derivatives and g is monotone submodular, SMIMax is monotone submodular and the greedy algorithm has a 1 −1/e approximation guarantee.The proof also gives a worst-case approximation lower bound using indistinguishable submodular instances.Source: §C.2.1 · pp. 27–28
  • With no query constraint, SMIMax reduces to the original summarization objective f(A).Source: §C.2.1 · p. 28

C.2.2. QUERY BASED SUMMARIZATION: FORMULATION AS A CONSTRAINED PROBLEM

  • Unlike SMIMax, the constrained formulation has a bounded approximation guarantee whenever f and g are monotone submodular.It is framed as submodular maximization with multiple submodular knapsack constraints.Source: §C.2.2 · p. 28
  • The constrained formulation separates query similarity into a submodular constraint, making query control explicit through ε rather than the indirect trade-off parameter λ.When Q = V, the constraint disappears and the problem reduces to cardinality-constrained submodular maximization.Source: §C.2.2 · pp. 28–29

C.2.3. PRIVACY PRESERVING SUMMARIZATION: PROOF OF LEMMA 20 AND COMPARING NSMIMAX AND CGMAX

The section contrasts privacy-preserving objectives based on mutual information with conditional-gain formulations, then gives a constrained alternative for directly controlling privacy.

C.2.3. PRIVACY PRESERVING SUMMARIZATION: PROOF OF LEMMA 20 AND COMPARING NSMIMAX AND CGMAX

  • NSMIMax is non-monotone submodular maximization when f has non-positive third-order partial derivatives, but can be inapproximable in the worst case.The proof reduces the case P = V to maximizing a difference of submodular functions.Source: §C.2.3 · p. 29
  • CGMax maximizes conditional gain f(A|P), recovering f(A) when P is empty and achieving a 1 −1/e guarantee when f has the stated monotonicity, normalization, non-negativity, and submodularity properties.Source: §C.2.3 · p. 29

C.2.4. PRIVACY PRESERVING SUMMARIZATION: FORMULATION AS A CONSTRAINED

  • The constrained privacy formulation adds privacy as an explicit constraint, but its approximation factor may be unbounded when f lacks negative third-order partial derivatives; CGMax is preferred in that case.The constraint-based problem is tractable when the privacy mutual information is submodular, as it is for many functions including facility location and set cover.Source: §C.2.4 · p. 30

C.2.5. PRIVACY PRESERVING AND QUERY BASED SUMMARIZATION: ANALYSIS OF CSIMAX AND PROOF OF LEMMA 21

The section develops joint query-and-privacy objectives and constraints, then connects multi-set information optimization to partitioning, clustering, and robust partitioning.

C.2.5. PRIVACY PRESERVING AND QUERY BASED SUMMARIZATION: ANALYSIS OF CSIMAX AND PROOF OF LEMMA 21

  • CSMIMax combines query relevance with privacy by maximizing conditional submodular mutual information, seeking a set similar to Q yet independent of P.It recovers CGMax when Q = V and SMIMax when P = ∅; under non-negative third-order partial derivatives, greedy achieves a 1 −1/e approximation.Source: §C.2.5 · pp. 30–31

C.2.6. PRIVACY PRESERVING AND QUERY BASED SUMMARIZATION: CONSTRAINED FORMULATION

  • The joint constrained formulation uses separate thresholds to control query similarity and privacy, and is an instance of SCSK when its objective and constraint are monotone submodular.The privacy constraint requires non-negative third-order partial derivatives; the section also introduces a modified problem when that condition fails.Source: §C.2.6 · p. 31

C.3.1. CLUSTERING OR MINIMIZING MULTI-SET MUTUAL INFORMATION

  • Minimizing total correlation over a partition is equivalent to a known submodular partitioning problem, while minimizing k-way mutual information can yield an undesirable set-cover partition.The example permits a trivial solution in which several sets cover similar items and one set covers very different concepts.Source: §C.3.1 · pp. 31–32

C.3.2. DIVERSE PARTITIONING OR MAXIMIZING MULTI-SET MUTUAL INFORMATION

  • Maximizing multi-set mutual information is related to robust partitioning because it maximizes a minimum across functions, and it can be viewed as maximizing a lower bound on the robust objective.The corresponding total-correlation partitioning problem is equivalent to submodular welfare up to a constant objective offset.Source: §C.3.2 · p. 32
  • The multi-set mutual information objective has expressions for facility location and set cover that relate it to worst-case partitioning.Source: §C.3.2 · p. 32
Loading 2006.15412v6…