信息论（信息熵、KL散度、交叉熵以及互信息）

信息论作为一门主要学科, 使用数理统计方法探讨信息度量. 传输及转换规律.
它主要研究通讯与控制系统中通用的信息传递规律及其优化解决方案的基础理论.
看似与概率论及机器学习的研究领域不同. 但二者间存在紧密联系.
为了简化数据表示. 需将较短码字分配给高概率事件/位串.
常见短语/高频词汇通常具有较短编码长度.
这种情况下需建立模型以区分可能发生的数据类型.

信息熵

遵循概率分布p的随机变量X的熵（记作H(X)），用于衡量其不确定性的重要指标。
对于具有 K 个状态的离散型随机变量而言，
其数学表达式如下：

H(X) = - \sum_{k=1}^{K}p(X = k)\log_{2}p(X=k)
一般采用基于2的对数值。
当离散型随机变量呈均匀分布时 其信息熵达到最大值。
由此可知 在具有K个状态的离散型随机变量中 如果每个状态的概率p(x=k)=1/K" 则该系统的不确定性最高 最大信息熵等于\log_2 K 。
反过来讲 在这种情况下 信息熵即为零 即系统完全没有不确定性。

遵循伯努利分布的随机变量X \in \{0, 1\}等价地表示为概率分别为p(X=1) = \theta和p(X=0) = 1 - \theta。由此可得信息熵可被定义为：

H(X) = -[p(X = 1)\log_{2}p(X=1) + p(X = 0)\log_{2}p(X=0)] = -[\theta\log_{2}\theta + (1-\theta)\log_{2}(1-\theta)]

当\theta=0.5 时，也就是随机变量符合均匀分布，此时有最大的信息熵为1。

KL散度

衡量两个概率分布p与q之间的差异程度可用KL散度这一指标；也可称为相对熵

KL(p||q) = \sum_{k}p_{k}\log \frac{p_{k}}{q_{k}} = \sum_{k}p_{k}\log p_{k} - \sum_{k}p_{k}\log q_{k} = -H(p) + H(p, q)

KL散度不是距离，因为它不是对称的，KL散度的对称版本是JS散度，定义为：

JS(p_1, P_2) = 0.5KL(p_1 || q) + 0.5KL(p_2 || q), \ q = 0.5p_1 + 0.5p_2

The cross-entropy between distributions p and q is defined as the summation over k of p_k multiplied by the logarithm of q_k.
Cross-entropy represents the average number of bits required to encode data from distribution p using distribution q.

KL散度用于衡量数据从一个概率分布转换到另一个所需的信息量。
显然地，

KL(p||q) \geq 0

并且仅在两个分布相等时其值才会为零

数据编码

在特定条件下采用最优编码方案以呈现原始信息

压缩就是说识别出文件中各个组成部分的概率分布情况，并通过将高概率的部分替换成较短的形式来实现数据量的缩减。这意味着，在内容重复度较高的文件中进行压缩时所需的空间会减少。

当内容完全不重复时, 就会难以进行压缩. 最糟糕的情况就是, 在面对那些随机且均匀分布的随机字符串时, 通常情况下无法压缩任何字符.

可以说压缩就是通过消除冗余来实现的这一过程。另一方面，在数据处理过程中存在一个关键的度量标准即信息熵它被用作衡量数据可压缩性的重要指标。

通常情况下，在文件中每个字符出现的概率均为p。这样，在此位置上最多可容纳 1/p 种不同的信息。因此，在此位置上所需的信息量可用二进制位数表示为 log_{2}\frac{1}{p}。

假设某个文件被划分为n个部分，并且每个子部分出现的概率分别为p_{i}；那么至少需要多少比特来压缩该文件：

log_{2}(\frac{1}{p_{1}}) + log_{2}(\frac{1}{p_{2}}) + ... + log_{2}(\frac{1}{p_{n}}) = \sum log_{2}(\frac{1}{p_{i}})

则平均每个部分所占用的比特数为，即：

p_{1} * log_{2}(\frac{1}{p_{1}}) + p_{2} * log_{2}(\frac{1}{p_{2}}) + ... + p_{n} * log_{2}(\frac{1}{p_{n}}) = \sum p_{i} * log_{2}(\frac{1}{p_{i}}) = E(log_{2}(\frac{1}{p}))

霍夫曼编码主要基于高频事件分配短码的思想，在理论上其编码方案具有最优性。它采用了变长码对文件中的字符进行表示，在具体实现中是根据某种评估方法确定字符对应的码长。对于频率高的字符赋予较短的码字表示，在减少总位数的同时有效降低了整体信息量的需求。

互信息

假设我们有两个随机变量X和Y，并且我们想了解其中一个变量如何能提供关于另一个变量的信息。然而，在这种情况下，默认情况下仅适用于实值随机变量的情况，并且在衡量相关性方面的能力较为有限。
一种更为普遍的方法是评估联合概率分布p(X,Y)与边缘分布p(X)p(Y)之间的相似程度，并将其称为互信息（Mutual Information）。其定义为：

I(X;Y) = \sum_{x,y} p(x,y)\log\frac{p(x,y)}{p(x)p(y)}

I(X; Y) = KL(p(X, Y) || p(X)p(Y)) = \sum_{x}\sum_{y}p(x, y)\log \frac{p(x, y)}{p(x)p(y)}

该值非负，并且当且仅当p(X,Y)=p(X)p(Y)时取得等号，表明当随机变量相互独立时互信息等于零。

为了深入理解互信息的含义，可以用联合熵和条件熵来重新表达互信息：

I(X; Y) = H(X) - H(X| Y) = H(Y) - H(Y|X)

根据其定义可知，

H(Y|X) = \sum_{x} p(x) H(Y | X = x)

这一性质表明，
在给定随机变量 X=x_0 的情况下，
随机变量 Y 的不确定性（即其熵）也随之降低。
换言之，
当得知随机变量 Y=y_0
时，
我们对随机变量 X=x_0
的可能性也有了进一步的认识。
换句话说，
当观测到随机变量 Y=y_0
时，
我们对随机变量 X=x_0
的可能性也有所了解。