Submodular Combinatorial Information Measures with Applications in Machine Learning (2020-06-27T00:00:00.000000Z)

TL;DR

This paper studies combinatorial information measures that generalize independence, (conditional) entropy, (Conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables and shows that, unlike entropic mutual information in general, the submodular mutual information is actually sub modular in one argument, holding the other fixed.

Abstract

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.

Authors

Rishabh K. Iyer

1 papers

Ninad Khargoankar

1 papers

J. Bilmes

3 papers

TL;DR

Abstract

Authors

References72 items

Concave Aspects of Submodular Functions

The Online Submodular Cover Problem

Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Vision

A Framework Towards Domain Specific Video Summarization

Deep Submodular Functions

Submodular Hamming Metrics

Mixed Robust/Average Submodular Partitioning: Fast Algorithms, Guarantees, and Applications

Submodular Optimization and Machine Learning: Theoretical Results, Unifying and Scalable Algorithms, and Applications

Submodularity in Data Subset Selection and Active Learning

Summarization of Multi-Document Topic Hierarchies using Submodular Mixtures

Polyhedral aspects of Submodularity, Convexity and Concavity

Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order

Gaze-enabled egocentric video summarization via constrained submodular maximization

Video summarization by learning submodular mixtures of objectives

Learning Mixtures of Submodular Functions for Image Collection Summarization

From MAP to Marginals: Variational Inference in Bayesian Submodular Models

Submodular Maximization with Cardinality Constraints

Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Submodular feature selection for high-dimensional acoustic score spaces

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications

Active Semi-Supervised Learning using Submodular Functions

Submodularity beyond submodular energies: Coupling edges in graph cuts

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1

A Class of Submodular Functions for Document Summarization

Approximation Algorithms for Submodular Multiway Partition

The Submodular Welfare Problem with Demand Queries

On the Feature Selection Criterion Based on an Approximation of Multidimensional Mutual Information

Causal Markov condition for submodular information measures

Non-monotone submodular maximization under matroid and knapsack constraints

Approximating submodular functions everywhere

Information Theory and Network Coding

Optimal approximation for the submodular welfare problem in the value oracle model

Submodular Approximation: Sampling-based Algorithms and Lower Bounds

Elements of Information Theory

Near-optimal sensor placements in Gaussian processes

Near-optimal Nonmyopic Value of Information in Graphical Models

Submodularity, Supermodularity, and Higher-Order Monotonicities of Pseudo-Boolean Functions

PAC-learning Bounded Tree-width Graphical Models

Maximizing the spread of influence through a social network

Feature selection based on mutual information criteria of max-dependency, max-relevance, and min-redundancy

On characterization of entropy function via information inequalities

A non-Shannon-type conditional inequality of information quantities

Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

Decomposition of submodular functions

An analysis of approximations for maximizing submodular set functions—I

Multivariate information transmission

Causal meets Submodular: Subset Selection with Directed Information

SVitchboard II and fiSVer i: high-quality limited-complexity corpora of conversational English speech

Submodular Function Maximization

Near Optimal algorithms for constrained submodular programs with discounted cooperative costs

Fast Semidierential-b ased Submodular Function Optimization: Extended Version

Mirror Descent-Like Algorithms for Submodular Optimization

Submodularity and Curvature: The Optimal Algorithm

Gaussian Markov triplets approached by block matrices

Submodularity and curvature : the optimal algorithm

Robust Submodular Observation Selection

Two Constructions on Limits of Entropy Functions

A Mathematical Theory of Communication

Greedy splitting algorithms for approximating multiway partition problems

Lectures Notes in Information Theory

Submodular functions and optimization

Submodular functions and convexity

Information Theoretical Analysis of Multivariate Correlation

A * ) − kκ f (A * ))

Here we have the facility location set function, f (A) = i∈[n] max a∈A s(i, a) where s is similarity kernel and Ω =

) (j, k; A) ≤ 0. Next, we will show that NSMIMax is inapproximable. For this, let P = Ω. Then I f (A

approximates D f (A, S i ) upto a factor of 1 − κ f , we get the resulting approximation guarantee

We then combine g(A i ) =⇒ (g(A * ) − kκ f (A * )) − g(A k ) ≤ (1 − 1 k ) k (g(A * ) − kκ

For the Conditional Gain we have f (A|B) == i∈Ω max(max a∈A s(i, a)

A)+f (B)−f (A∪B) = i∈[n] max a∈A s(i, a)+ max b∈B s(i, b) − max c∈A∪B s(i, c) = i∈[n] max a∈A s(i, a) + max b∈B s(i, b) − max(max a∈A s(i, a), max b∈B s(i, b)) = i∈Ω min(max a∈A s(i, a)

Field of Study

Venue Information

Name

Type