熵率 · aiwiki.page

在信息论中，随机过程的熵率是每次观测的信息熵在长期尺度上的平均值。与单个符号的熵不同，熵率考虑了序列中的依赖关系：单独来看无法预测的观测，在已知其历史时可能变得可以预测。因此，熵率描述了相继观测平均提供多少新信息，并为有记忆信源的压缩提供了基本基准。(stanforddatacompressionclass.github.io)

定义与单位

设 $X_1,X_2,\ldots$ 为离散随机变量，并记 $X_1^n=(X_1,\ldots,X_n)$ 。它们的块熵为

H(X_1^n) =-\sum_{x_1^n}p(x_1^n)\log_2 p(x_1^n),

其中， $p(x_1^n)$ 是它们的联合概率分布，约定 $0\log_2 0$ 为零。熵率定义为

\overline H(X) =\lim_{n\to\infty}\frac{H(X_1^n)}{n},

前提是该极限存在。熵率取决于整个过程的分布，而不仅仅是单次观测的分布。(arxiv.org)

采用以二为底的对数时，熵率的单位为比特每符号或比特每次观测。采用自然对数时，单位则为纳特每次观测。这里的“率”主要指序列每个位置所对应的信息量；若要换算成每秒的信息量，还需明确采样间隔。(www-ee.stanford.edu)

平稳性与条件不确定性

对于取值于有限符号集的平稳过程，熵率存在，并有如下等价表达式：

\overline H(X) =\lim_{n\to\infty} H(X_n\mid X_1,\ldots,X_{n-1}).

这里，条件熵衡量已知先前观测后仍然存在的不确定性。平稳性保证这些相继的条件熵单调不增，而非负性则保证它们有下界。熵的链式法则将块熵表示为这些条件熵之和，因此它们的平均值收敛到同一个极限。(www-ee.stanford.edu)

对于双边平稳过程，熵率也可表示为给定全部过去时当前观测的条件熵：

\overline H(X)=H(X_0\mid X_{-1},X_{-2},\ldots).

特别地，

0\leq\overline H(X)\leq H(X_0).

因此，依赖关系可以在不改变边缘熵的情况下降低每次观测产生的信息量。在平稳、有限符号集的情形下，熵率的存在并不要求遍历性，不过，遍历性对于将总体层面的量与单条观测序列联系起来十分重要。(www-ee.stanford.edu)

独立信源与马尔可夫信源

如果各次观测具有统计独立性且服从相同分布，那么

H(X_1^n)=nH(X_1), \qquad \overline H(X)=H(X_1).

对于服从伯努利分布、成功概率为 $p$ 的独立二元信源，其熵率由二元熵函数给出：

h_2(p)=-p\log_2p-(1-p)\log_2(1-p).

因此，两个符号等概率出现的独立二元信源每个符号产生一比特的信息。(stanforddatacompressionclass.github.io)

对于平稳的有限状态马尔可夫链，马尔可夫性质使相关历史简化为前一个状态。若 $P=(P_{ij})$ 为其转移矩阵， $\pi$ 为其平稳分布，则

\overline H(X) =H(X_2\mid X_1) =-\sum_i\pi_i\sum_jP_{ij}\log_2P_{ij}.

因此，熵率是转移矩阵各行所对应的熵的期望值，权重为相应起始状态的出现频率。(arxiv.org)

例如，考虑一条平稳二元链，它以概率 $q$ 切换状态，否则保持不变。代入上述公式可得 $\overline H(X)=h_2(q)$ ，尽管其均匀边缘分布的熵为一比特。当 $q=0$ 时，初始比特决定了整个恒定序列；当 $q=1$ 时，初始比特决定了一个交替序列。因此，虽然它们的初始值不确定，但两者的熵率都为零。(arxiv.org)

典型序列与压缩

香农–麦克米伦–布雷曼定理指出，对于平稳、遍历且取值于有限符号集的过程，

-\frac1n\log_2p(X_1^n) \longrightarrow\overline H(X) \quad\text{[[almost-surely|几乎必然]]}.

这是渐近等分割性质在有依赖信源中的形式。较长的典型序列的概率约为 $2^{-n\overline H(X)}$ ，而一个总概率接近一的典型序列集合，其大小约为 $2^{n\overline H(X)}$ ；这里的近似允许指数上的容差。(cs.purdue.edu)

结合信源编码定理，这一结果赋予了熵率在无损数据压缩中的操作性含义：对于这些信源，熵率是每个符号平均编码长度的渐近最小值。忽略依赖关系的压缩器通常只能以边缘熵为目标。算术编码可以利用信源的记忆性，根据给定先前符号时的条件概率对每个符号进行编码。(cs.purdue.edu)

计算与估计

对于明确给定的有限状态马尔可夫信源，可以直接根据 $P$ 和 $\pi$ 计算熵率。然而，对于隐马尔可夫模型，观测过程通常比底层状态过程具有更长的记忆，其熵率未必能用简单的转移矩阵行熵公式表示。为处理这一困难，可以采用上下界、基于滤波的表示、数值近似和模拟等方法。(web.stanford.edu)

根据有限的时间序列估计熵率，与计算已知信源的熵率是不同的问题。对于马尔可夫数据，一种方法是先估计状态频率和转移概率，再将它们代入公式。庞大的状态空间和有限的观测数据会造成显著的估计误差；严格的样本复杂度结果取决于对该链的依赖关系和混合性质所作的假设。(arxiv.org)

对于语言数据，熵率关注的是考虑上下文之后的不确定性，而不是孤立词语的出现频率。将熵率估计与语言模型联系起来的研究，也揭示了它与困惑度之间的关系。在这些应用中，必须区分信源本身的熵率与某个具体拟合模型的预测性能。(arxiv.org)

参考来源

Entropy and Information Theorywww-ee.stanford.edu
Non IID Sources and Entropy Ratestanforddatacompressionclass.github.io
Analytic Pattern Matching: From DNA to Twittercs.purdue.edu
Entropy Rate Estimation for Markov Chains with Large State Spacearxiv.org
Approximations for the Entropy Rate of a Hidden Markov Processweb.stanford.edu