Computational Techniques for Investigating Information Theoretic Limits of Information Systems
Computational Techniques for Investigating Information Theoretic Limits of Information Systems
复制标题
DOI：
10.3390/info12020082
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
C. Tian;J. Plank;Brent Hurst;Ruida Zhou
中科院分区：
文献类型：
--
作者：
C. Tian;J. Plank;Brent Hurst;Ruida Zhou
基于熵线性规划框架的计算机辅助方法，已被证明是有效的，在协助信息系统的信息论基本限制的研究。显著影响其计算效率和适用性的一个关键因素是基于特定问题的对称性和依赖关系减少变量。在这项工作中，我们建议使用不相交集的数据结构，以算法识别约简映射，而不是依赖于穷举的等价分类。基于这一约化线性规划，我们考虑了四种研究信息系统基本极限的方法：（1）计算给定信息测度线性组合的外界并给出最优解处的信息测度值：（2）有效地计算两个信息量之间的多面体折衷外界;（3）为计算出的外界提供证明（作为已知信息不等式的加权和）;以及（4）提供最佳值不发生变化的信息量范围，即，敏感性分析一个工具箱，具有高效的JSON格式输入前端，以及Guidance或Cplex作为线性规划求解引擎，并实现和开源。
Computer-aided methods, based on the entropic linear program framework, have been shown to be effective in assisting the study of information theoretic fundamental limits of information systems. One key element that significantly impacts their computation efficiency and applicability is the reduction of variables, based on problem-specific symmetry and dependence relations. In this work, we propose using the disjoint-set data structure to algorithmically identify the reduction mapping, instead of relying on exhaustive enumeration in the equivalence classification. Based on this reduced linear program, we consider four techniques to investigate the fundamental limits of information systems: (1) computing an outer bound for a given linear combination of information measures and providing the values of information measures at the optimal solution; (2) efficiently computing a polytope tradeoff outer bound between two information quantities; (3) producing a proof (as a weighted sum of known information inequalities) for a computed outer bound; and (4) providing the range for information quantities between which the optimal value does not change, i.e., sensitivity analysis. A toolbox, with an efficient JSON format input frontend, and either Gurobi or Cplex as the linear program solving engine, is implemented and open-sourced.