Generalized Submodular Information Measures: Theoretical Properties, Examples, Optimization Algorithms, and Applications
Generalized Submodular Information Measures: Theoretical Properties, Examples, Optimization Algorithms, and Applications
复制标题
DOI：
10.1109/tit.2021.3123944
复制
发表时间：
2022-02-01
影响因子：
2.5
通讯作者：
Asnani, Himanshu
中科院分区：
文献类型：
--
作者：
Iyer, Rishabh;Khargonkar, Ninad;Asnani, Himanshu
像熵和互信息这样的信息论量在机器学习中有很多应用。众所周知，由于一组随机变量上的熵是次模的，因此在这些熵量和次模性之间有很强的联系。在本文中，我们研究了组合信息度量，它概括了独立性、（条件）熵、（条件）互信息和在（不一定是随机的）变量集上定义的总相关性。这些度量严格概括了相应的熵度量，因为它们都是通过子模函数参数化的，这些子模函数本身严格概括了熵。重要的是，我们证明了，与一般的熵互信息不同，对于一类三阶偏导数满足非负性的子模函数，子模互信息实际上在一个参数中是子模的，而另一个参数是固定的。这包括许多实际有用的案例，如设施位置和设置覆盖功能。我们研究了这些子模块信息度量的具体实例，以及概率覆盖、图切、对数决定和饱和覆盖函数，并看到它们都具有数学上直观和实用的表达式。最后，我们还研究了数据点子集（熵情况下的随机变量）之间的广义独立性，并将独立性表征与对数次模分布中的独立性联系起来。在应用方面，我们将子模块（条件）互信息的最大化问题与基于互信息、基于查询和隐私保护摘要等问题联系起来，并将多集子模块互信息的优化问题与聚类和鲁棒分区联系起来。我们对各种数据汇总任务进行了真实世界和合成实验。
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, log-determinants, and saturated coverage functions and see that they all have mathematically intuitive and practically useful expressions. Finally, we also study generalized independence between subsets of datapoints (random variables in the entropic case), and connect the independence characterizations to independence in log-submodular distributions. 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. We perform real world as well as synthetic experiments on various data summarization tasks.