Submodular combinatorial information measures with applications in machine learning

Rishabh Iyer, Ninad Khargoankar, Jeff Bilmes, Himanshu Asanani
Proceedings of the 32nd International Conference on Algorithmic Learning Theory, PMLR 132:722-754, 2021.

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 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 (also called second-order supermodular functions). We study specific instantiations of the submodular information measures, 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v132-iyer21a, title = {Submodular combinatorial information measures with applications in machine learning}, author = {Iyer, Rishabh and Khargoankar, Ninad and Bilmes, Jeff and Asanani, Himanshu}, booktitle = {Proceedings of the 32nd International Conference on Algorithmic Learning Theory}, pages = {722--754}, year = {2021}, editor = {Feldman, Vitaly and Ligett, Katrina and Sabato, Sivan}, volume = {132}, series = {Proceedings of Machine Learning Research}, month = {16--19 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v132/iyer21a/iyer21a.pdf}, url = {https://proceedings.mlr.press/v132/iyer21a.html}, 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 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 (also called second-order supermodular functions). We study specific instantiations of the submodular information measures, 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.} }
Endnote
%0 Conference Paper %T Submodular combinatorial information measures with applications in machine learning %A Rishabh Iyer %A Ninad Khargoankar %A Jeff Bilmes %A Himanshu Asanani %B Proceedings of the 32nd International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Vitaly Feldman %E Katrina Ligett %E Sivan Sabato %F pmlr-v132-iyer21a %I PMLR %P 722--754 %U https://proceedings.mlr.press/v132/iyer21a.html %V 132 %X 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 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 (also called second-order supermodular functions). We study specific instantiations of the submodular information measures, 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.
APA
Iyer, R., Khargoankar, N., Bilmes, J. & Asanani, H.. (2021). Submodular combinatorial information measures with applications in machine learning. Proceedings of the 32nd International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 132:722-754 Available from https://proceedings.mlr.press/v132/iyer21a.html.

Related Material