信息熵应用随笔1：利用条件熵筛选数据维度
一，背景和任务目标
假设有一个n维数据集，包含k个样本，可以视为n*k矩阵。每个数据维度我们可以视为一个随机变量，此n维数据集则可以视为由n个随机变量构成的系统。我们的目标是从集合数据集中选取一个最具数据代表性的数据维度。怎么算是最具代表性的数据维度呢？一个可行方案是，采用信息论的方法，选择对系统不确定性贡献最大的随机变量X。
关于信息熵，联合熵，条件熵的概念和定义，可以参考：
二， 基于联合熵与条件熵的随机变量选择算法
显然，仅仅计算每个随机变量各自的不确定性（信息熵），并不能确定哪个变量对整个系统的不确定性贡献最大，因为这些随机变量之间很可能存在很大的信息重叠。因此，我们使用考察了信息重叠的联合熵和条件熵来解决问题。具体的解法如下所示：
算法一：先计算整个变量系统的联合熵H(X1, ... , Xn)。然后去掉一个变量X1，再计算一下剩余其他变量的联合熵H(X2, ... , Xn)。然后计算差值D(X1) = H(X1, ... , Xn) - H(X2, ... , Xn) 。以此类推可计算每个随机变量的差值D(Xi)。差值D(Xi)越大，说明Xi对系统的不确定性贡献就越大。这种算法使用联合熵的差值来估计变量Xi对于整个系统的独立信息，而不仅仅是每个随机变量各自的熵，可以涵盖变量间存在很大的信息重叠的情况。
算法二：在算法一的基础上，改计算联合熵差值D(Xi)为信息增益IG(Xi)。每次选择一个变量Xi，系统的剩余不确定性等可以用条件熵表达，即
。而选择变量Xi后系统减少的不确定性被称为信息增益（infomation gain），即系统交叉熵和选择Xi条件熵的差值，信息增益用公式表达如下：
IG(Xi) = 
-
最终，IG(Xi) 最大的变量，对整个系统提供的不确定性越高。这种算法相对第一种更为精确。由于一组变量的联合熵量化了不确定性的总量，条件熵量化了变量系统中部分变量已知时整个变量系统的剩余不确定性。因此，从信息理论的角度，确定单个变量对整个系统的不确定性的贡献的问题，就成为计算其距离场之间信息重叠的任务。
Hazarika, S., et al 等人的论文中，就采用了这种方法来量化等值线的的重要性。
如上图(c)所示，一共有10个等值线，你可以将其理解为10个变量组成的变量系统。然后按照上文算法2,计算每个等值线对应的信息增益。为了便于为了便于在信息引导下探索各个变量（数据维度），使用了如图(a)所示的信息增益曲线，让用户交互地选择变量并可视化其信息增益。在图(a)中，纵轴表示信息增益，横轴表示10个变量。图上的每个点对应一个数据维度，按其信息增益的降序从左到右排列。我们选择其中信息增益最大的5个变量，也就是图(a)从左到右前5个点，它们累积的信息增益如图(a)中部的垂直黑线表示的那样，是4.42，而全部10个变量的信息量只有4.91。也就是说，目前选中的5个变量包含了系统总信息量的90%。这5个选中的变量对应的等值线如图(b)所示。对比图(b)和(c)，可以看到这五个等值线传递的不确定性信息几乎与所有等值线所示的相同。这对于具有大量变量的系统尤其有用，因为它有助于识别与不确定性分析相关的最重要变量。
不得不说这种方法有点像主成分分析（PCA），目的近似，手段不同，最终结果和应用场景也有区别。
三.问题的关键——如何计算多个变量的联合熵
然而多个变量的联合熵计算并不是一个容易的事。首先我们看一下多变量联合熵的计算公式：
(1)
其中p(x1, ... , xn)是随机变量X1, ... , Xn的联合概率分布。而计算联合概率分布的难度是指数型增长的。假设随机变量X1, ... , Xn都是离散型随机变量，均有k种可能取值。那么计算联合概率分布就需要计算n^k次。显然直接计算联合概率分布是有难度的。
但是，如果我们能更巧妙地知道联合概率分布函数，那么计算联合熵就有办法了。那么如何计算联合概率分布函数？一个直接的办法，是计算多变量的联合直方图（joint histogram）。对此，我们需要一整节的内容介绍什么是直方图，再用一整节的内容介绍什么是联合直方图以及如何存储联合直方图，最后再用一节介绍已知联合直方图的情况下怎么计算联合熵和条件熵。
参考文献：Hazarika, S., et al., Information Guided Exploration of Scalar Values and Isocontours in Ensemble Datasets. Entropy, 2018. 20(7): p. 540.
