Submodular Combinatorial Information Measures with Applications in Machine Learning

• URL: http://arxiv.org/abs/2006.15412v6
• Date: Tue, 2 Mar 2021 19:58:48 GMT
• Title: Submodular Combinatorial Information Measures with Applications in Machine Learning
• Authors: Rishabh Iyer and Ninad Khargonkar and Jeff Bilmes and Himanshu Asnani
• Abstract summary: Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. We study information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of variables.
• Score: 2.5329739965085785
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Information-Theoretic Measures on Lattices for High-Order Interactions [0.7373617024876725]
  We present a systematic framework that derives higher-order information-theoretic measures using lattice and operator function pairs. We show that many commonly used measures can be derived within this framework, however they are often restricted to sublattices of the partition lattice. To fully characterise all interactions among $d$ variables, we introduce the Streitberg Information, using generalisations of KL divergence as an operator function.
  arXiv  Detail & Related papers  (2024-08-14T13:04:34Z)
• Discovering modular solutions that generalize compositionally [55.46688816816882]
  We show that identification up to linear transformation purely from demonstrations is possible without having to learn an exponential number of module combinations. We further demonstrate empirically that meta-learning from finite data can discover modular policies that generalize compositionally in a number of complex environments.
  arXiv  Detail & Related papers  (2023-12-22T16:33:50Z)
• Uncertainty relations in terms of generalized entropies derived from information diagrams [0.0]
  Inequalities between entropies and the index of coincidence form a long-standing direction of researches in classical information theory. This paper is devoted to entropic uncertainty relations derived from information diagrams.
  arXiv  Detail & Related papers  (2023-05-29T10:41:28Z)
• Modular Deep Learning [120.36599591042908]
  Transfer learning has recently become the dominant paradigm of machine learning. It remains unclear how to develop models that specialise towards multiple tasks without incurring negative interference. Modular deep learning has emerged as a promising solution to these challenges.
  arXiv  Detail & Related papers  (2023-02-22T18:11:25Z)
• Submodularity In Machine Learning and Artificial Intelligence [0.0]
  We offer a plethora of submodular definitions; a full description of example submodular functions and their generalizations. We then turn to how submodularity is useful in machine learning and artificial intelligence.
  arXiv  Detail & Related papers  (2022-01-31T22:41:35Z)
• Learning Aggregation Functions [78.47770735205134]
  We introduce LAF (Learning Aggregation Functions), a learnable aggregator for sets of arbitrary cardinality. We report experiments on semi-synthetic and real data showing that LAF outperforms state-of-the-art sum- (max-) decomposition architectures.
  arXiv  Detail & Related papers  (2020-12-15T18:28:53Z)
• Removing Bias in Multi-modal Classifiers: Regularization by Maximizing Functional Entropies [88.0813215220342]
  Some modalities can more easily contribute to the classification results than others. We develop a method based on the log-Sobolev inequality, which bounds the functional entropy with the functional-Fisher-information. On the two challenging multi-modal datasets VQA-CPv2 and SocialIQ, we obtain state-of-the-art results while more uniformly exploiting the modalities.
  arXiv  Detail & Related papers  (2020-10-21T07:40:33Z)
• Concave Aspects of Submodular Functions [0.0]
  Submodular functions generalize several information-theoretic quantities such as entropy and mutual information. Submodular functions also show signs of concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular using the differentials.
  arXiv  Detail & Related papers  (2020-06-27T17:06:24Z)
• Continuous Submodular Function Maximization [91.17492610120324]
  Continuous submodularity is a class of functions with a wide spectrum of applications. We identify several applications of continuous submodular optimization, ranging from influence, MAP for inferences to inferences to field field.
  arXiv  Detail & Related papers  (2020-06-24T04:37:31Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  Submodular functions have been studied extensively in machine learning and data mining. In this work, we propose a continuous DR-submodular extension for integer submodular functions. We formulate a new probabilistic model which is defined through integer submodular functions.
  arXiv  Detail & Related papers  (2020-06-01T22:20:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.