信息论学习笔记（六）

发表于 2025-06-02 分类于计算机

前段时间查文献的时候，偶然看到了一些算法里涉及到了信息论的相关知识。信息论我在几年前通过看书自学过，时间太久有些忘了，正好趁此机会重新复习一下。

参考书籍：机械工业《信息论基础（原书第二版）》（ELEMENTS OF INFORMATION THEORY SECOND EDITION），作者Thomas M. Cover, Joy A. Thomas

博弈与数据压缩

赛马问题中的投资增长率与赔率关系

以赛马问题为例，赛马中的投资增长率与赛马的熵率之间有极强的对偶性（其中，投资增长率与赛马的熵率二者之和为常数）：

两种马票定义

a-for-1: 赛前用1元买票下注，中奖得a元，不中得0元
b-to-1: 赛前用0元买票下注，中奖得b元，不中得-1元（即缴纳1元本金）
注意，若 $b = a - 1$，则两种马票收益等价。

股民的总收益模型

对于一个股民，其初始资金为买马票，我们记：

在第 $i$ 匹马上下注的资金占本金的 $b_i$：

第 $i$ 匹马赢的概率为 $p_i$；
若第 $i$ 匹马赢，收益为 $o_i \cdot b_i$（赔率为 $o_i$ 的一个因子）。

若有 $n$ 场比赛，第 $n$ 场比赛结束后总资产 $S_n = \prod_{i=1}^n S(x_i)$，其中 $S(x) = b(x) \cdot o(x)$ 为相对收益，是当 $X$ 匹马获胜时，股民购买该马所获收益的乘积因子。

定义一场比赛的双倍率（Doubling Rate）为：

$$
W(b, p) = E(\log S(X)) = \sum_{k=1}^m p_k \log (b_k o_k)
$$

其表示在给定的投资策略 $b$ 和比赛结果的概率分布 $p$ 下，资金的长期平均增长率。具体来说，它衡量的是每次比赛中，股民的资金能够以多快的速度增长。

假设比赛结果 $X_1, X_2, \ldots, X_n$ 为服从 $p(x)$ 的 iid 序列，则股民在策略 $b$ 下的相对收益将以指数因子 $W(b, p)$ 呈指数增长：

$$
S_n \dot{=} 2^{n W(b, p)}
$$

最优双倍率策略

目标：如何在所有投资组合策略 $b$ 的集合中寻找使 $W(b, p)$ 最大化的策略。

最优双倍率：如果选择 $b$ 使得双倍率 $W(b, p)$ 达到最大值 $W^*(p)$，那么称该值为最优双倍率。

$$
W^*(p) = \max_{b} W(b, p) = \max_{b_i \geq 0, \sum b_i = 1} \sum_{i=1}^mp_i\text{log}b_io_i
$$

经证明，$b = p$ 是该优化问题的解。

定理 6.1.2：最优双倍率的显式计算

$$
\begin{aligned}
W(b, p) &= \sum p_i \log (b_i o_i) \\
&= \sum p_i \log \left( \frac{b_i}{p_i} \cdot p_i o_i \right) \\
&= \sum p_i \log o_i - H(p) - D(p \| b) \leq \sum p_i \log o_i - H(p)
\end{aligned}
$$

其中，$D(p | b)$ 为相对熵。当且仅当 $b = p$ 时取等号。

因此，最优化的双倍率公式： $W^*=\sum p_i \log o_i - H(p)$ ，并按比例 $b^*=p$ 下注可达到该值。

若仅知道 $\sum \frac{1}{o_i} = 1$，不包含其他信息，则：

$$
W(b, p) = \sum p_i \log \left( b_i o_i \right) = \sum p_i \log \left( \frac{b_i}{p_i} \cdot p_i o_i \right) = D(p | b) - D(p | \frac{1}{o})
$$

即以以 $o_i$ 估计 $p_i$ ，所谓“马民法”估计（如图）。

$\Rightarrow$ 马民法的估计计划是否实施，取决于马民法下该策略到真实分布的距离的差值。

$\Rightarrow$ 只有当股民的估计 $b$ 比马民法的估计更好时，股民才能赚钱。

均匀公平机会下的收益

若马票为 $m$-for-1，则：

$$
W^*(p) = D(p | \frac{1}{m}) = \log m - H(p)
$$

守恒定理：对于均匀的公平机会收益赔率，$W^*(p) + H(p) = \log m$。双倍率与熵率之和为常数。

$\Rightarrow$ 熵减小 $1 \text{ bit}$，股民收益翻一番。

$\Rightarrow$ 熵越小，获利越丰厚。

股民的保留本金策略

若股民有选择的保留本金的比例 $b(0)$ 为保留本金的比例，其余 $b(x)$ 为对不同马匹 $x$ 的下注比例，则：

$$
S(x) = b(0) + b(x) \cdot o(x)
$$

若 $\sum\frac{1}{o_i} = 1$， $b(0)$ 不影响收益分析，按比例下注最优。
若 $\sum\frac{1}{o_i} < 1$，机会收益更高，因此按比例下注最优，且不必保留本金。也可以选择dutch book（“荷兰赌”）这一策略，令 $b_i=c\frac{1}{o_i}$ 其中 $c=\frac{1}{\sum{c_i}}$ ，相对收益为 $o_ib_i=c$ ， $S(x)=1/\sum{\frac{1}{o_i}}=c>1$ 。
若 $\sum \frac{1}{o_i} > 1$，机会收益更低，需保留部分本金。

已知历史信息下的下注策略

若在赛马比赛中，马民可提前知道一匹马的历史胜率（记作信息 $Y$），则：

$b(x|y) \geq 0, \sum_x b(x|y) = 1$ 为已知信息 $Y$ 条件下的下注策略。
同样地，$b(x) \geq 0, \sum_x b(x) = 1$ 为无条件下注策略。

双倍率定义

无条件双倍率：
$$
W^*(X) = \max_{b(x)} \sum_x p(x) \log b(x) o(x)
$$
条件双倍率：
$$
W^*(X|Y) = \max_{b(x|y)} \sum_{x,y} p(x,y) \log b(x|y) o(x)
$$

$\Delta W = W^*(X|Y) - W^*(X)$

由于获得某匹马比赛 $X$ 中的信息 $Y$ 而引起的双倍率增量 $\Delta W$ 满足：

$$
\Delta W = I(X; Y)
$$

即，双倍率的增量为 $X$ 和 $Y$ 的互信息。

随机过程下的最优双倍率

若赛马的过程为一个随机过程，下注策略依赖于此前各次比赛的结果：

$$
\begin{aligned}
W^*(X_k | X_{k-1}, X_{k-2}, \ldots, X_1) &= \max_{b(x_k | x_{k-1}, \ldots, x_1)} E[\log S(X_k) | X_{k-1}, \ldots, X_1] \\
&= \log m - H(X_k | X_{k-1}, \ldots, X_1)
\end{aligned}
$$

此时最优双倍率在 $b^*(x_k | x_{k-1}, \ldots, x_1) = p(x_k | x_{k-1}, \ldots, x_1)$ 时达到。

第 $n$ 场比赛结束后，股民的相对收益 $S_n = \prod_{i=1}^n S(x_i)$，且增长率的指数（m-for-1）为：

$$
\begin{aligned}
\frac{1}{n} E[\log S_n] &= \frac{1}{n} \sum_{i=1}^n E[\log S(x_i)] \\
&= \log m - \frac{1}{n} H(X_1, X_2, \ldots, X_n)
\end{aligned}
$$

$\Rightarrow$ 对于平稳过程 $H(X)$，两边取极限，可得：

$$
\lim_{n \to \infty} \frac{1}{n} E[\log S_n] + H(X) = \log m
$$

英文的熵与模型复杂度（马尔科夫链语言模型）

一阶逼近模型：$p(x_i | x_{i-1})$ ，用上一个字母预测下一个字母出现的概率。
二阶逼近模型：$p(x_i | x_{i-1}, x_{i-2})$ ，用前面两个字母预测下一个字母出现的概率。
三阶逼近模型：$p(x_i | x_{i-1}, x_{i-2}, x_{i-3})$ ，用前面三个字母预测下一个字母出现的概率。

$\Rightarrow$ 模型复杂度：一阶 < 二阶 < 三阶 < …

$\Rightarrow$ 复杂度越高，越逼近真实文章。

在语言识别中的应用：三字母模型（二阶马尔可夫单词模型）。

2025年补充：

其实现阶段的大语言模型，不论是GPT还是deepseek，其数学原理就是这样，以前面出现的文本（例如system prompt和用户提示词）去预测后续的文本（即模型给出的回答）。
但是要实现这样的生成任务，上述N阶马尔科夫链语言模型显然力不从心，且模型计算复杂度会很高，因此出现了LSTM、Attention、Transformer等技术提高计算效率和并行能力