㈠ 贝叶斯网专题1：信息论基础
目录
[toc]
贝叶斯网是一种将概率统计应用于复杂领域，进行不确定性推理和数据分析的工具，其在机器学习和人工智能领域具有重要的基础性地位。从技术层面讲，贝叶斯网可系统地描述随机变量之间关系，构造贝叶斯网的主要目的是进行概率推理。
理论上，进行概率推理只需要一个联合概率分布即可，但联合概率分布的复杂度与随机变量规模呈指数级关系，在解决实际问题时不可行。贝叶斯网为解决该问题提供了方法，通过贝叶斯网可将复杂的联合概率分布分解为一系列规模较小的子模块，从而降低训练和推理的复杂度。
本人将主要依据香港科大张连文教授的《贝叶斯网引论》，对其中重要内容进行精炼，并通过接下来的几篇博客对贝叶斯网展开专题介绍，分三大部分进行：
信息论是基于概率论的一门研究信息传输和处理的数学理论。它不仅是信息技术的基础，也在统计力学、机器学习等领域发挥重要作用。在构建贝叶斯网的过程中，可以用信息论来进行分析。
Jesen不等式源于函数的凹凸性。在数学中，称一个函数为凹函数是指向上凹，凸函数是指向下凸，如下图所示。
证明
用归纳法证明，当 时，式(1)恒等。假设式(1)在 时成立，证明它在 时也成立，即：
命题得证。
Jensen不等式是与函数凹凸性有关的基本性质，在信息论中常会用到，比如用于计算信息熵的对数函数就满足凹函数的Jensen不等式，这在后文证明信息熵的性质时会用到。
一个离散随机变量 的熵 的定义为：
其中，约定 .上式的对数若以2为底，则熵的单位是比特，若以e为底，则单位是奈特，后文将都以比特为单位。
熵在热力学中表示系统的混乱程度，在概率论中表示随机变量的不确定程度，在信息论中表示对信源的期望编码长度。
先来解释下信息论中期望编码长度：假设有一个信源，可产生A、B、C三种不同的信息，产生的概率分别为1/2、1/4和1/4，我们要设计一套编码系统来记录这个信源所产生的信息，所用的比特位数越少越好。显然，我们应该为出现概率大的信息分配码长较短的编码，其长度可通过 来确定，比如我们为A分配码长为1的编码，为B和C分配码长为2的编码，通过霍夫曼编码算法，可将A编码为0，将B和C编码为10和11.此时，该信源的编码平均码长则为
由此我们可知，熵代表了对信源进行最优编码时的期望编码长度。反过来看，如果将这个信源用一个随机变量来表示，若该随机变量的不确定性越高（产生的信息种类越多、各种类出现的概率越平均），则需要用来编码该信源的期望编码长度也会越大，反之则越短。因而，熵又可以表示随机变量的不确定程度。
例如，一个取值为0或1的随机变量 ，计 ，根据熵的定义，有：
随着p的变化， 的变化曲线如下图：
证明：
(1)根据熵的定义， 显然成立。
(2)log为上凹函数，根据Jensen不等式有：
命题得证。
联合熵是基于联合概率分布对熵的推广。两个离散随机变量X和Y的联合熵定义为：
条件熵是基于条件概率分布对熵的推广。随机变量X的熵时用它的概率分布P(X)来定义的。如果知道另一个随机变量Y的取值为y，那么X的条件分布即为P(X|Y=y)。利用此条件分布可定义给定Y=y时X的条件熵：
熵H(X)度量的是随机变量X的不确定性，条件熵H(X|Y=y)度量的则是已知Y=y后，X的不确定性。
上式(3)中，当y变化时，H(X|Y=y)也会发生改变，当知道Y的概率分布后，可以计算X关于Y的条件熵的期望值：
H(X|Y)称为给定Y时X的条件熵。
注意：H(X|Y)和H(X|Y=y)不一样，后者是已知Y取某一特定值时X的条件熵，即已知Y=y后，X剩余的不确定性。而前者时在未知Y的取值时，对观测到Y的取值后X剩余的不确定性的期望值。尤其值得注意的是，H(X|Y=y)可能比H(X)大，即知道Y的某个具体取值后，有可能增大对X的不确定性。而H(X|Y)永远不会比H(X)大，即平均来说，知道Y不会增加X的不确定性。下面给出一个具体的例子加以比较：
设已知联合分布P(X,Y)及其边缘分布P(X)和P(Y)如下表所示：
从而可得出：
可以看到：观测到 后，可使X的熵减小；观测到 后，反而使X的熵增大；但平均而言，对Y的观测使X的熵减小。
由此，我们定义互信息量为：
称为Y关于X的信息，表示Y中包含多少关于X的信息。很容易证明 ，因此又称之为X和Y之间的互信息。
证明：
同理可得：
因此， 得证。
证明：
同理可证
证明：
等式左边：
等式右边：
从而等式成立。
联合熵、条件熵和互信息之间的关系，可用如下文氏图来表示它们之间的关系：
在1.1.2节介绍熵的概念时，介绍了熵的期望编码长度的意义。交叉熵的概念也可以从期望编码长度的意义出发进行理解。
若信源X的理论概率分布为Q(X)，但其实际概率分布为P(X)，则使用理论概率分布构建的霍夫曼编码在实际概率分布下的期望编码长度即为交叉熵，定义为：
相对熵则定义为交叉熵与熵之差，即按照信源的理论概率分布Q设计的最优编码的期望码长会比按照实际概率分布P设计的最优编码的期望码长多几个比特。其定义如下：
其中约定： ； .
KL(P,Q)又称为P(X)和Q(X)之间的Kullback-Leibler距离，或KL散度。但严格来讲，它并不是一个真正意义的距离，因为其不满足对称性。
证明：
信息不等式得证。
利用KL散度可以度量两个概率分布之间的差异。
从1.1.3节给出的联合熵、条件熵与互信息之间关系的文氏图可以看出：对于随机变量X和Y，当互信息I(X,Y)=0时，X和Y相互独立；且 ，等号也在X和Y独立时成立。我们也可以给出严格证明。
证明：
由KL散度大于等于0可得： ，当且仅当P(X,Y)=P(X)P(Y)时等号成立，即X与Y相互独立。
由于 ，所以 ，等号在X与Y相互独立时成立。
从信息论的角度，我们可以看出：两个随机变量相互独立等价于它们之间的互信息为0.
该结论还可以进一步推广到三个随机变量的情况。
对于随机变量X,Y,Z，条件熵H(X|Z)是给定Z时X剩余的不确定性，如果再进一步给定Y，X剩余的不确定性变为H(X|Z,Y)。这两者之差即为给定Z时观测Y的取值会带来的关于X的信息量，即给定Z时X和Y之间的条件互信息，定义如下：
类似上文证明 ，我们也容易证明：
类似上文证明 和 ，我们也容易证明：
其中等号仅在X与Y在给定Z时互相独立的情况下成立，记作 .
从信息论的角度，我们可以看出：给定Z时，两个随机变量X和Y相互条件独立等价于它们的条件互信息为0，即Y关于X的信息已全部包含在Z中，从而观测到Z后，再对Y进行观测不会带来关于X更多的信息。另一方面，如果X和Y在给定Z时相互不独立，则 ，即在已知Z的基础上对Y的进一步观测将会带来关于X的新信息，从而降低X的不确定性。