4.8 算法信息论与前沿方向

本节处理三个更专门的方向，它们把前面七节的工具推进到新的位置。算法信息论把信息量从分布推广到单个对象：熵描述随机变量平均携带的信息，柯尔莫哥洛夫复杂度描述一个具体对象的描述长度。这一推广回答了压缩极限之外的另一个问题：一个对象本身包含多少信息，与它来自哪个分布无关。

最小描述长度原则把这一想法变成模型选择准则，为奥卡姆剃刀给出定量形式：模型复杂度以描述长度计价，与数据拟合的编码长度相加后取最小值。差分隐私把 KL 散度的家族用于隐私定义，(ε, δ) 参数与散度的阶参数一一对应。量子信息论把概率分布换成密度矩阵，熵、条件熵与互信息都有对应的形式，并且出现经典情形没有的性质，例如负的条件熵。

本节的性质与前七节不同，三个方向都以概念介绍与最小示例为主，细节留给各自的教材。阅读目标是建立接口：知道这些方向用什么工具、解决什么问题、与前面哪些结论直接相连。

4.8.1 柯尔莫哥洛夫复杂度

描述长度的定义

4.4 节的信源编码定理回答了一个统计问题：给定分布，长序列平均需要多少比特。算法信息论回答一个逐对象的问题：一个具体的二进制串 $x$ 需要多少比特才能被描述出来。定义

$$K_U(x)=min\{|p|:U(p)=x\}$$

其中 $U$ 是通用图灵机，$p$ 是程序，$|p|$ 是程序长度（比特），$K_U(x)$ 称为 $x$ 的柯尔莫哥洛夫复杂度（Kolmogorov complexity）：输出 $x$ 的最短程序长度。程序可以理解为描述 $x$ 的方法，最短描述的长度就是 $x$ 自身携带的信息量。

定义依赖具体的通用图灵机，但依赖程度有限。对两台通用图灵机 $U$ 与 $V$，存在常数 $c$（只依赖 $U$ 与 $V$）使

$$|K_U(x)-K_V(x)|\le c$$

对所有 $x$ 成立。这是因为 $V$ 可以用 $U$ 上的一个模拟程序实现，模拟程序的长度是常数。常数可以任意大但与对象无关，因此 $K(x)$ 在 $O(1)$ 意义下是良定义的。这一不变性是算法信息论能够作为理论基础的原因。

基本性质有两条。上界：把 $x$ 直接打印出来的程序长度为 $|x|+c$，因此 $K(x)\le |x|+c$。不可计算性：$K(x)$ 不是可计算函数，否则可以用穷举来找最短程序，从而判定停机问题。

不可压缩性

多数串不可压缩。计数论证直接给出结论：长度小于 $n-k$ 的程序最多有 $2^{n-k}$ 个（按长度求和），每个程序至多输出一个串，因此长度 $n$ 的串中，满足 $K(x)<n-k$ 的比例不超过

$$\frac{2^{n-k}}{2^n}=2^{-k}$$

取 $k=10$，能被压缩 $10$ 比特以上的串不到千分之一；取 $k=20$，不到百万分之一。随机串几乎全部不可压缩，这一结论不依赖任何概率模型，是纯组合的事实。它同时说明：声称某个工具把任意随机数据压缩到远小于原始长度，可以直接用计数论证排除。

与熵的关系

两个量描述不同的对象，形式上有对应。对可计算分布，期望意义下

$$H(X)=E[K(X)]+O(1)$$

熵是复杂度的期望，复杂度是逐样本的实现值。给定分布时熵给出平均最优码长（4.4 节），不知道分布时 $K(x)$ 给出单个对象的最优描述长度。条件版本对应关系也有：$K(x\mid y)$ 是已知 $y$ 时描述 $x$ 的最短长度，对应的对称化互信息为

$$I_K(x:y)=\frac{1}{2}[K(x)+K(y)-K(x,y)]$$

括号内的量度量两个对象的共同信息。与香农互信息相比，$K(x)-K(x\mid y)$ 不满足对称性，需要对称化，这个差别来自逐对象定义的不可加性。互信息的算法版本在理论上更基础（香农互信息可由它导出），代价是不可计算，因此工程中仍然使用 4.1 节的期望版本。

下列代码用游程编码演示描述长度的直观含义：同一长度的四类串有不同的编码长度；随后用计数论证给出可压缩串的比例上界。

import numpy as np

def rle_bits(bits):
    """游程编码的描述长度（比特）：逐段记录长度，符号由交替决定"""
    runs = []
    cur, count = int(bits[0]), 1
    for b in bits[1:]:
        if int(b) == cur:
            count += 1
        else:
            runs.append(count)
            cur, count = int(b), 1
    runs.append(count)
    return int(sum(np.ceil(np.log2(r + 1)) for r in runs)), len(runs)

rng = np.random.default_rng(0)
n = 200
cases = {
    "随机（p=0.5）": rng.integers(0, 2, size=n),
    "偏置（p=0.9）": (rng.random(n) < 0.9).astype(int),
    "分块（四段）": np.concatenate([np.zeros(50), np.ones(50), np.zeros(50), np.ones(50)]).astype(int),
    "全零": np.zeros(n, dtype=int),
}
for name, bits in cases.items():
    length, runs = rle_bits(bits)
    print(f"{name:14s}: 游程数 = {runs:3d}, 描述长度 = {length:3d} 比特（原始 {n} 比特）")

# 计数论证：长度 n 的串中，可压缩 k 比特以上的比例不超过 2^(-k)
print()
for k in [10, 20, 40]:
    print(f"长度 40 的串中，可压缩 {k:2d} 比特以上的比例不超过 2^-{k} = {2.0 ** -k:.3e}")
# 随机串的描述长度接近原始长度：p=0.5 时 158 / 200
# 偏置串的游程更少，描述长度 101 比特，接近熵率给出的理论值 200 * H(0.9) ≈ 94 比特
# 结构性串（分块、全零）的描述长度远小于原始长度

输出给出三档对比：随机串的游程编码几乎没有压缩（$158$ 对 $200$ 比特，游程编码对无结构数据接近无效）；偏置串压缩到 $101$ 比特，与熵率给出的理论下限 $94$ 比特接近；分块串压缩到 $24$ 比特。计数部分显示可压缩串的比例随 $k$ 指数下降：压缩 $20$ 比特以上的串不超过百万分之一。第一档与后两档的差别就是复杂度的直观内容：编码能压缩的是结构，随机串没有结构可用。

4.8.2 最小描述长度与奥卡姆剃刀

两段码

模型选择要在拟合精度与模型复杂度之间权衡。最小描述长度（minimum description length，MDL）原则把这一权衡写成编码长度：用模型描述数据的总长度由两部分组成，

$$L(\text{模型})+L(\text{数据}\mid \text{模型})$$

第一项是模型的描述长度，第二项是在给定模型后编码数据的长度。选择总长度最小的模型。以多项式拟合为例，阶数是模型，系数是模型的描述内容，残差是数据在模型下的编码对象：阶数越高，模型描述越长，残差编码越短。

4.4 节的 Kraft 不等式给出编码长度与概率的对应：长度 $L$ 的码字对应概率 $2^{-L}$（比特单位）。把两段码换成概率，$2^{-L(\text{模型})}$ 是模型的先验，$2^{-L(\text{数据}\mid \text{模型})}$ 是似然，总长度最小化等价于最大化

$$p(D\mid M)p(M)$$

这正是贝叶斯模型选择的目标（2.12 节）。两个框架在这里重合：概率大对应码长短，先验概率对应模型复杂度。贝叶斯因子与描述长度之差是同一个量的两种语言。

奥卡姆剃刀的定量形式

复杂度惩罚的必要性可以用计数论证说明。若允许的模型数量随复杂度指数增长，总存在一个复杂模型把训练数据拟合得更好，把噪声也编码进去。惩罚项的作用是抵消这一增长：复杂度每增加一比特，可选模型数量翻一倍，而惩罚也增加一比特，净效应使过拟合模型在描述长度上没有优势。

这一机制在经典准则中有对应的近似。BIC 的形式

$$-2\log \hat{L}+k\log n$$

来自对边际似然的拉普拉斯近似：第一项是数据在最优参数下的编码长度，第二项近似参数的描述长度（每个参数约 $\frac{1}{2}\log n$ 比特）。AIC 用 $2k$ 代替 $k\log n$，对应不同的编码假设。三者的共同点是数据拟合项加复杂度惩罚，差别只在惩罚的具体形式。

与柯尔莫哥洛夫复杂度的关系是近似的：MDL 用可计算、可优化的模型类代替不可计算的 $K(x)$。理想的描述长度是 $K(\text{数据})$，实际使用的最短描述被限制在给定的模型族内，因此 MDL 得到的是该模型族内的最优，模型族本身的选择仍然依赖先验知识。

下列代码在带噪声的三次多项式数据上执行两段码准则。模型码长按参数个数乘以每个参数的固定位数计算，数据码长取高斯残差的负对数似然。

import numpy as np

rng = np.random.default_rng(0)
n = 300
x = np.linspace(-1, 1, n)
y = 0.5 + 1.2 * x - 2.0 * x ** 2 + 1.5 * x ** 3 + rng.normal(0, 0.3, size=n)

def two_part_bits(degree, bits_per_param=32):
    """两段码长度：模型参数码 + 数据在模型下的负对数似然（比特）"""
    coef = np.polyfit(x, y, degree)
    resid = y - np.polyval(coef, x)
    sigma2 = np.mean(resid ** 2)
    nll_bits = 0.5 * n * np.log2(2 * np.pi * np.e * sigma2)   # 高斯残差的编码长度
    model_bits = (degree + 1) * bits_per_param
    return nll_bits + model_bits, nll_bits, model_bits

print("阶数   模型码长   数据码长    总码长")
best = None
for d in range(0, 9):
    total, nll, model = two_part_bits(d)
    print(f"  {d}    {model:6.0f}     {nll:8.1f}   {total:8.1f}")
    if best is None or total < best[0]:
        best = (total, d)
print(f"最优阶数 = {best[1]}（真实生成模型为三次）")
# 低阶模型的数据码长长（拟合不足），高阶模型的模型码长长（过拟合的收益不足）
# 总码长在真实阶数处取得最小值

输出显示总码长在阶数 $3$ 处最小：$2$ 阶的数据码长比 $3$ 阶多 $103$ 比特（拟合不足的代价），$4$ 阶的模型码长比 $3$ 阶多 $32$ 比特而数据码长只省下 $1$ 比特（过拟合的收益不足）。两条曲线的最小值点给出了复杂度与拟合的平衡位置，这就是奥卡姆剃刀在这一问题上的定量形式。

4.8.3 差分隐私

定义与散度

差分隐私限制统计结果对单条记录的依赖程度。设随机机制 $\mathcal{M}$ 对数据集 $D$ 输出分布 $\mathcal{M}(D)$。若对任意相差一条记录的相邻数据集 $D$ 与 $D^{\prime }$，及任意输出集合 $S$，

$$P(\mathcal{M}(D)\in S)\le e^{\epsilon }P(\mathcal{M}(D^{\prime })\in S)+\delta$$

则称 $\mathcal{M}$ 满足 $(\epsilon ,\delta )$-差分隐私（differential privacy）。$\epsilon$ 控制两个输出分布的接近程度，$\delta$ 允许一个小概率的例外。

信息论给出这一条件的精确形式。$\delta =0$ 时，条件是所有集合上概率比的上确界不超过 $e^{\epsilon }$，等价于最大散度（max-divergence，4.2 节的 Rényi 散度在 $\alpha \to \mathrm{\infty }$ 的极限）满足

$$D_{\mathrm{\infty }}(\mathcal{M}(D)\parallel \mathcal{M}(D^{\prime }))\le \epsilon$$

$\delta >0$ 时条件放宽为散度族中的一组成员，对应于Rényi 差分隐私：对阶参数 $\alpha$，

$$D_{\alpha }(\mathcal{M}(D)\parallel \mathcal{M}(D^{\prime }))\le \epsilon (\alpha )$$

Rényi 散度的引入有两个作用。其一是组合：多次查询的隐私损失按阶参数累积，Rényi 形式给出的组合界比基本组合 $(\epsilon ,\delta )$ 直接相加更紧，这是它在深度学习场景（对同一数据集做大量梯度更新）中被广泛使用的原因。其二是可计算性：高斯机制的隐私损失在高斯分布之间有闭式的 Rényi 散度，而最大散度对高斯分布为无穷（两个高斯分布的支持集重合但密度比无界），直接用 $(\epsilon ,0)$ 定义不可行。这解释了高斯机制为什么必须配合 $(\epsilon ,\delta )$ 或 Rényi 形式使用。

两种机制

拉普拉斯机制：查询函数 $f$ 的敏感度定义为相邻数据集上取值差的上确界 $\mathrm{\Delta }f=\underset{D\sim D^{\prime }}{sup}|f(D)-f(D^{\prime })|$。机制输出 $f(D)+\eta$，其中 $\eta$ 取自尺度为 $\mathrm{\Delta }f/\epsilon$ 的拉普拉斯分布。可以验证两个相邻输入的输出密度比处处不超过 $e^{\epsilon }$，因此满足 $(\epsilon ,0)$-差分隐私。噪声尺度与敏感度成正比、与 $\epsilon$ 成反比：要求越强的隐私（$\epsilon$ 越小），需要的噪声越大。

高斯机制：输出加方差为 ${\sigma }^2$ 的高斯噪声，取 $\sigma \ge \mathrm{\Delta }f\sqrt{2\log (1.25/\delta )}/\epsilon$ 时满足 $(\epsilon ,\delta )$-差分隐私。噪声呈高斯型，适合与梯度下降结合（差分隐私随机梯度下降在每次更新时对梯度加噪），这一形式是差分隐私机器学习的主要工具。

隐私参数与信息量的关系

$\epsilon$ 是每条记录对输出的最大影响。$\epsilon$ 很小对应强隐私，也对应输出几乎不依赖任何单条记录，可用信息量相应减少。组合定理（$k$ 次查询的隐私损失相加）与 4.6 节的误差指数构成同一权衡的两端：更强的隐私意味着更大的噪声、更慢的收敛，实验报告通常同时给出 $\epsilon$、$\delta$ 与模型精度。

下列代码演示拉普拉斯机制的噪声尺度，并数值验证相邻输入的密度比条件。

import numpy as np

rng = np.random.default_rng(0)
print("敏感度为 1 的计数查询，拉普拉斯机制的噪声：")
for eps in [0.1, 1.0, 10.0]:
    noise = rng.laplace(0, 1 / eps, size=200000)
    print(f"  eps = {eps:5.1f}: 噪声尺度 = {1 / eps:6.3f}, 标准差 = {np.sqrt(2) / eps:.3f}, "
          f"90% 分位 = {np.quantile(np.abs(noise), 0.9):.3f}")

def lap_pdf(z, mu, b):
    return np.exp(-np.abs(z - mu) / b) / (2 * b)

eps = 1.0
b = 1 / eps
z = np.linspace(-10, 10, 8001)
ratio = lap_pdf(z, 1.0, b) / lap_pdf(z, 0.0, b)     # 相邻数据集：均值相差 1
print(f"\n最大密度比 = {ratio.max():.6f}，e^eps = {np.exp(eps):.6f}，"
      f"不超过 e^eps：{ratio.max() <= np.exp(eps) + 1e-9}")
# 密度比在所有输出处不超过 e^eps，这正是 (eps, 0)-差分隐私的等价条件

输出显示噪声随 $\epsilon$ 急剧变化：$\epsilon =0.1$ 时噪声标准差为 $14.1$，$\epsilon =10$ 时降到 $0.14$。密度比的最大值恰为 $e^{\epsilon }=2.718$，与理论一致：拉普拉斯机制以取等号的方式满足隐私条件。

4.8.4 量子信息论初步

密度矩阵与冯·诺依曼熵

经典信息论的对象是概率分布，量子信息论的对象是密度矩阵（density matrix）：半正定、迹为 $1$ 的矩阵 $\rho$。对角元给出测量结果的概率，非对角元编码不同基态之间的相干性。纯态 $|\psi ⟩$ 对应 $\rho =|\psi ⟩⟨\psi |$（秩一），混合态是多个纯态的概率混合。

熵的定义直接推广：把概率换成密度矩阵的特征值，或把 $-\log \rho$ 的期望写成矩阵形式，

$$S(\rho )=-\mathrm{tr}(\rho \log \rho )$$

称为冯·诺依曼熵（von Neumann entropy）。对数取 2 为底时单位为量子比特。三条基本性质：纯态的熵为零（特征值只有一个不为零，等于 $1$）；维数为 $d$ 的系统上熵的最大值为 $\log d$，在完全混合态 $\rho =I/d$ 处取到；酉变换不改变熵。

复合系统由张量积描述，求部分系统的状态需要偏迹（partial trace）：对另一部分取迹。偏迹是量子信息论中概念变化的来源：两体纯态的整体熵为零，而各部分可以是混合态。量子互信息定义为

$$I(A:B)=S({\rho }_A)+S({\rho }_B)-S({\rho }_{AB})$$

它与经典互信息同形。量子相对熵定义为 $D(\rho \parallel \sigma )=\mathrm{tr}(\rho (\log \rho -\log \sigma ))$，满足非负性（Klein 不等式）与数据处理不等式，这两条性质使 4.1 与 4.2 节的许多结论在量子情形保持形式。

与经典的差别

负的条件熵是量子情形独有的现象。定义 $S(A\mid B)=S({\rho }_{AB})-S({\rho }_B)$，在经典情形它等于条件熵因而非负；在量子情形它可以为负，因为当 $A$ 与 $B$ 处于最大纠缠时，整体处在纯态（熵为零），而各部分为完全混合（熵为一比特）。纠缠是这一现象的来源：部分的不确定性大于整体的不确定性，因为两部分的信息完全相关。

量子信道是完全正、迹保持的线性映射，作用于密度矩阵。量子信道容量分两个层次：传递经典信息的容量由 Holevo 容量给出上界

$$\chi =S(\sum _i{p}_i{\rho }_i)-\sum _i{p}_{i}S({\rho }_i)\le \log d$$

它不小于经典容量，两者之间的差（Holevo 界是否可达）依赖信道类型；传递量子态本身的容量由相干信息刻画（Lloyd-Shor-Devetak 定理）。两个容量的表达式都以前面的熵与互信息为基础，量子信息论的结构与经典理论平行，计算与可达性的细节更为复杂。

下列代码构造几个典型量子态并计算冯·诺依曼熵，展示纯态、混合态与 Bell 态的区别，并数值检查量子相对熵的非负性。

import numpy as np

def von_neumann(rho):
    """冯·诺依曼熵（比特）：对密度矩阵的特征值计算香农熵"""
    vals = np.linalg.eigvalsh(rho)
    vals = vals[vals > 1e-12]
    return float(-np.sum(vals * np.log2(vals)))

def partial_trace_b(rho):
    """对两量子比特系统的第二个子系统求偏迹"""
    return rho.reshape(2, 2, 2, 2).trace(axis1=1, axis2=3)

psi = np.array([1, 0], dtype=complex)
print("纯态 |0>：S =", von_neumann(np.outer(psi, psi.conj())), "比特")
print("完全混合态 I/2：S =", von_neumann(np.eye(2) / 2), "比特")

bell = np.zeros(4, dtype=complex)
bell[0] = bell[3] = 1 / np.sqrt(2)          # (|00> + |11>) / sqrt(2)
rho_ab = np.outer(bell, bell.conj())
rho_a = partial_trace_b(rho_ab)
print("\nBell 态 (|00> + |11>) / sqrt(2)：")
print("  S(AB) =", von_neumann(rho_ab), "比特")
print("  S(A) = S(B) =", von_neumann(rho_a), "比特")
print("  量子互信息 I(A:B) =", 2 * von_neumann(rho_a) - von_neumann(rho_ab), "比特")
print("  条件熵 S(A|B) =", von_neumann(rho_ab) - von_neumann(rho_a), "比特（负值）")

def quantum_kl(rho, sigma):
    """量子相对熵 D(rho||sigma)（自然对数）"""
    w_r, v_r = np.linalg.eigh(rho)
    log_r = v_r @ np.diag(np.log(np.maximum(w_r, 1e-12))) @ v_r.conj().T
    w_s, v_s = np.linalg.eigh(sigma)
    log_s = v_s @ np.diag(np.log(np.maximum(w_s, 1e-12))) @ v_s.conj().T
    return float(np.real(np.trace(rho @ (log_r - log_s))))

rho = np.array([[0.7, 0.2], [0.2, 0.3]])
sigma = np.array([[0.5, 0.05], [0.05, 0.5]])
print("\n量子相对熵 D(rho||sigma) =", round(quantum_kl(rho, sigma), 4), "（非负）")
print("反向 D(sigma||rho) =", round(quantum_kl(sigma, rho), 4), "（两个方向不相等）")
# 纯态熵为 0，完全混合态熵为 1 比特
# Bell 态整体熵为 0，各部分熵为 1 比特，条件熵为 -1 比特

输出显示四组数值：纯态熵为 $0$，完全混合态为 $1$ 比特，Bell 态整体的熵为 $0$ 而各部分各为 $1$ 比特，条件熵为 $-1$ 比特。量子互信息为 $2$ 比特，是经典情形下两比特系统能达到的上限（各部分各一比特的完全相关）。量子相对熵的两点数值为非负且不对称，与经典 KL 散度的行为一致。

4.8.5 本节小结

单个对象、模型选择与两个前沿

本节介绍三个方向。算法信息论用最短程序长度定义单个对象的复杂度 $K(x)$，它是逐对象、与分布无关的量；不变性定理保证定义在常数意义下唯一，计数论证给出不可压缩性：长度 $n$ 的串中能被压缩 $k$ 比特以上的比例不超过 $2^{-k}$。对可计算分布，复杂度的期望等于熵，条件版本给出互信息的算法形式。最小描述长度把复杂度变成模型选择准则：总码长等于模型码长加数据码长，最小化它等价于最大化后验概率；复杂度惩罚抵消模型数量的指数增长，为奥卡姆剃刀提供定量形式，BIC 与 AIC 是它的近似版本。差分隐私用最大散度与 Rényi 散度刻画隐私强度：$(\epsilon ,0)$ 条件等价于最大散度不超过 $\epsilon$，$(\epsilon ,\delta )$ 与 Rényi 形式用于高斯机制与组合分析；拉普拉斯机制与高斯机制的噪声尺度都由敏感度与 $\epsilon$ 决定。量子信息论把分布换成密度矩阵，熵换成冯·诺依曼熵，偏迹带来部分系统的不确定性，纠缠使条件熵可以为负；量子互信息、量子相对熵与信道容量的形式与经典理论平行。

三个方向的共同线索仍然是熵与散度：$K(x)$ 是熵的逐对象版本，MDL 是编码长度与概率对应的直接应用，差分隐私是散度族的应用，量子熵是香农熵在矩阵上的推广。第四章的工具在这里没有改变，改变的是作用的对象。

信息论一章到此结束。回顾全章：4.1 与 4.2 建立熵、互信息与各类散度的语言；4.3 把它们放到统计流形上，得到信息几何；4.4 与 4.5 给出压缩与传输的两个极限；4.6 把散度连接到统计推断的误差指数与大偏差；4.7 把工具用到机器学习的目标、表示与泛化分析；4.8 处理单个对象的复杂度、模型选择与两个前沿方向。四章的布局到此完整：线性代数提供结构，概率论与统计推断提供不确定性，最优化提供求解方法，信息论提供度量不确定性与信息的统一尺度，四者共同构成后续课程中深度学习、强化学习与概率图模型的基础。

练习题

第 1 题 概念推导

证明柯尔莫哥洛夫复杂度的两条性质：其一，对长度 $n$ 的串 $x$，$K(x)\le n+c$，其中常数与 $x$ 无关；其二，长度 $n$ 的串中，满足 $K(x)<n-k$ 的比例不超过 $2^{-k}$。说明第二条结论与 4.4 节压缩极限的关系：为什么它不依赖任何概率分布，也不与信源编码定理矛盾。

参考答案

上界：设通用图灵机 $U$，构造程序 $p$：把 $x$ 的全部比特作为常数写在程序中，程序的行为是输出该常数。程序长度为 $|x|$ 比特加上固定的输出指令开销，后者与 $x$ 无关，因此 $K(x)\le n+c$。

比例上界：长度小于 $n-k$ 的程序的总数为

$$\sum _{i=0}^{n-k-1}{2}^i<2^{n-k}$$

每个程序至多输出一个串，因此可被这些程序输出的串不超过 $2^{n-k}$ 个。长度 $n$ 的串共 $2^n$ 个，比例为

$$\frac{2^{n-k}}{2^n}=2^{-k}$$

与压缩极限的关系：信源编码定理是统计结论，前提是先知道分布（或用模型估计分布），结论是最优平均码长等于熵。上面的计数结论是组合事实，不涉及分布，它对每一个串给出最坏情形下的描述长度下界。两者不矛盾，因为对象不同：计数结论说的是存在不可压缩的串，编码定理说的是对给定的分布存在最优的平均性能。一个信源可以同时满足两条：分布集中在少数简单串上（熵小，平均可压缩），而该分布下概率极小的串仍然不可压缩。实践中压缩工具在随机数据上失效、在结构化数据上有效，对应的就是这两类对象。

第 2 题 计算推理

某团队有两组候选模型：模型 A 的参数量为 $10$，模型 B 的参数量为 $100$。用两段码准则比较：若每个参数用 $32$ 比特编码，模型 B 相对模型 A 需要多少额外的模型码长？在 $n=10000$ 个样本上，模型 B 平均每个样本的负对数似然需要比模型 A 低多少比特，才能抵消这一额外开销？若模型 B 的实际改进为每样本 $0.001$ 比特，应该选择哪个模型？把结论与 BIC 的惩罚项比较。

参考答案

模型码长之差：

$$\mathrm{\Delta }L(\text{模型})=(100-10)\times 32=2880\text{ 比特}$$

需要的数据码长改进：总码长之差为 $\mathrm{\Delta }L(\text{模型})+\mathrm{\Delta }L(\text{数据})$。要在总码长上打平，需要

$$\mathrm{\Delta }L(\text{数据})\le -2880\text{ 比特}⟹\text{每样本改进}\ge \frac{2880}{10000}=0.288\text{ 比特}$$

若实际改进为每样本 $0.001$ 比特：数据码长共省下 $10$ 比特，远小于 $2880$ 比特的模型开销，总码长增加，选择模型 A。

与 BIC 的比较：BIC 的惩罚为 $k{\log }_{2}n$ 比特（换算到比特单位），对 $n={10}^4$ 每个参数约 ${\log }_2{10}^4=13.3$ 比特，比固定 $32$ 比特的编码更宽松。用 BIC 的惩罚，模型 B 的额外开销为 $90\times 13.3=1194$ 比特，需要的每样本改进为 $0.119$ 比特，结论仍然是选择 A。两个准则的差别在于每个参数的编码成本假设：固定位数假设参数取值范围大（例如浮点表示），BIC 的 $\frac{1}{2}\log n$ 来自对参数做积分（拉普拉斯近似），允许参数数量较大时成本更低。准则的选择取决于参数空间的先验知识，两者给出的方向一致时结论最可靠；出现分歧时通常是因为参数的真实取值范围与假设不符。

第 3 题 代码验证

用 4.8.3 节的拉普拉斯机制代码验证差分隐私的两条性质：其一，噪声尺度与 $\epsilon$ 成反比，验证比例关系；其二，改变敏感度 $\mathrm{\Delta }f$（把相邻数据集的均值差从 $1$ 改为 $2$，并相应调整噪声尺度），观察密度比的最大值如何变化，验证机制满足的隐私条件仍是 $(\epsilon ,0)$。再补充一个检查：把噪声换成高斯分布（尺度取 $1/\epsilon$），观察密度比的最大值是否仍然有界，并解释高斯机制为什么需要 $(\epsilon ,\delta )$ 形式。

参考答案

import numpy as np

rng = np.random.default_rng(0)

# 性质一：噪声尺度与 eps 成反比
print("eps    噪声尺度   经验标准差   理论标准差")
for eps in [0.5, 1.0, 2.0, 4.0]:
    noise = rng.laplace(0, 1 / eps, size=200000)
    print(f"  {eps:.1f}    {1 / eps:.3f}     {noise.std():.4f}      {np.sqrt(2) / eps:.4f}")

# 性质二：敏感度为 2 时，噪声尺度取 2/eps，密度比的最大值仍为 e^eps
def lap_pdf(z, mu, b):
    return np.exp(-np.abs(z - mu) / b) / (2 * b)

eps = 1.0
print()
for sens in [1.0, 2.0]:
    b = sens / eps
    z = np.linspace(-20, 20, 16001)
    ratio = lap_pdf(z, sens, b) / lap_pdf(z, 0.0, b)
    print(f"敏感度 = {sens:.0f}：噪声尺度 = {b:.2f}，最大密度比 = {ratio.max():.6f}，e^eps = {np.exp(eps):.6f}")

# 高斯噪声：密度比无界
def gauss_pdf(z, mu, s):
    return np.exp(-(z - mu) ** 2 / (2 * s ** 2)) / (s * np.sqrt(2 * np.pi))

z = np.linspace(-20, 20, 40001)
ratio_g = gauss_pdf(z, 1.0, 1 / eps) / gauss_pdf(z, 0.0, 1 / eps)
print(f"\n高斯噪声：位置 z = 20 处的密度比 = {ratio_g[-1]:.3e}（随 |z| 增大而无界）")
print(f"e^(1/(2 s^2)) 形式：最大值随 z -> +inf 发散，无法用 (eps, 0) 形式约束")

输出（节选）：

eps    噪声尺度   经验标准差   理论标准差
  0.5    2.000     2.8270      2.8284
  1.0    1.000     1.4184      1.4142
  2.0    0.500     0.7085      0.7071
  4.0    0.250     0.3551      0.3536

敏感度 = 1：噪声尺度 = 1.00，最大密度比 = 2.718282，e^eps = 2.718282
敏感度 = 2：噪声尺度 = 2.00，最大密度比 = 2.718282，e^eps = 2.718282

高斯噪声：位置 z = 20 处的密度比 = 2.943e+08（随 |z| 增大而无界）

结论：噪声尺度与 $\epsilon$ 成反比，经验标准差与理论值 $\sqrt{2}/\epsilon$ 一致。敏感度提高时把噪声尺度按比例放大，密度比的最大值不变，仍等于 $e^{\epsilon }$，说明隐私条件与敏感度无关，敏感度只影响所需噪声的大小。高斯噪声的密度比在尾部随 $|z|$ 增大而无界（$z=20$ 处已达 ${10}^8$ 量级，且按 $\exp (z/s^2)$ 继续增长），任何有限的 $\epsilon$ 都无法约束它，因此 $(\epsilon ,0)$ 形式的差分隐私对高斯机制不可满足，必须引入 $\delta$ 允许小概率例外，或用 Rényi 散度在有限阶参数下刻画损失（高斯分布之间的 Rényi 散度有闭式，不涉及无界的密度比）。

第 4 题 综合应用

某团队要把模型训练改造成差分隐私版本（差分隐私随机梯度下降）。他们给出三种候选方案：方案一，对每次梯度更新加拉普拉斯噪声，隐私预算 $\epsilon =1$，训练 $10000$ 步；方案二，加高斯噪声，用 Rényi 差分隐私做组合分析，$(8,{10}^{-5})$-Rényi 参数对应最终 $(\epsilon ,\delta )$ 为 $(3,{10}^{-5})$；方案三，不训练模型，用均匀随机输出。请评价三种方案；用 4.8.3 节的组合关系估算方案一在基本组合下的隐私损失；说明为什么方案二在相同噪声水平下能得到更好的隐私与精度权衡；并解释方案三在隐私与精度两个维度上的位置。

参考答案

方案评价：

方案一的问题在组合：基本组合定理把 $k$ 次查询的隐私损失相加，$10000$ 次更新后隐私损失为 $k\epsilon =10000$（在基本组合下），远超可用范围。要达到总的 $\epsilon =1$，每次更新的预算只有 ${10}^{-4}$，相应的噪声尺度巨大，模型无法收敛。基本组合的悲观是它假设最坏情形的隐私损失线性累积。

方案二的做法是正确方向的两个改动：其一，用 Rényi 散度做组合，隐私损失按阶参数 $\alpha$ 累积，$\alpha$ 较大时单步损失相近但组合界更紧；其二，用高斯机制使单步损失在高斯分布之间有闭式，便于精确累积。$(3,{10}^{-5})$ 的最终参数在训练万步的规模下属于合理范围，这也是差分隐私深度学习文献中的常见配置。

方案三满足最严格的隐私：输出与数据完全独立，任何 $\epsilon$ 都满足。代价是模型完全无用，精度等于随机基线。

方案一的组合估算：基本组合给出 ${\epsilon }_{\text{total}}=k\epsilon =10000\times 1=10000$（忽略 $\delta$ 的累积），对应每条记录几乎完全暴露。要在基本组合下把总量控制在 $1$ 以内，需要单步 $\epsilon \le {10}^{-4}$，拉普拉斯噪声尺度为 ${10}^4$ 倍的敏感度，梯度被噪声完全淹没。

方案二的优势：Rényi 组合利用损失分布在高阶矩下的行为，把 $k$ 步的总损失按阶参数累加后再转换回 $(\epsilon ,\delta )$，转换中的折扣使最终隐私损失随步数的增长明显慢于线性（高级组合定理给出的总量近似按 $\sqrt{k}$ 而不是 $k$ 增长）。高斯机制的单步损失在高斯分布之间有闭式的 Rényi 散度，转换可以做得精确。因此在同一噪声水平下，方案二允许更多的训练步数与更小的最终 $\epsilon$，精度损失小得多。

方案三的位置：在隐私维度上最优（完全不依赖数据），在精度维度上最差（无信息）。三个方案在隐私与精度的平面上构成一条边界上的点，实际选择取决于应用对两个维度的要求。差分隐私的形式化含义正是把这条权衡曲线写清楚：任何声称同时接近两个极端的方案都需要检查其隐私账本（每次查询的 $\epsilon$ 与组合方式）。

常见错误

错误 1 · 把柯尔莫哥洛夫复杂度当作可计算的量并用于实际压缩

原因：$K(x)$ 不可计算，没有算法能在有限时间内给出任意串的最短程序长度。实际工具（游程编码、通用压缩格式）给出的是特定模型族内的描述长度，与 $K(x)$ 之间可以相差很多。

解决：把 $K(x)$ 当作理论基准使用。评估压缩工具时，用已知分布的熵率或可构造的最优编码作为参照；解释工具的压缩比时说明所用的模型族，避免把它当作复杂度的近似值。需要数值演示不可压缩性时，用计数论证（比例上界 $2^{-k}$）而不是计算 $K(x)$。

错误 2 · 把 MDL 的模型码长当作参数的物理存储长度

原因：两段码中的模型码长是编码假设下的抽象长度，取决于参数表示的约定。同一模型用固定位数、浮点格式或拉普拉斯近似的 $\frac{1}{2}\log n$ 编码，得到的码长不同，模型选择的结果也可能不同。

解决：报告中给出编码约定，并说明结论对该约定是否稳健。做法是同时用两种约定（例如固定位数与 BIC 形式）比较排序是否一致；若不一致，说明数据量不足以区分这些模型，需要更多样本或更强的先验。这与 4.6 节的教训一致：界与准则的数值依赖假设，比较时必须固定约定。

错误 3 · 用最大散度描述高斯机制的隐私

原因：两个均值不同、方差相同的高斯分布之间，密度比在尾部无界，最大散度为无穷，因此高斯机制不满足任何 $(\epsilon ,0)$-差分隐私。看到高斯机制在文献中被广泛使用，就以为可以用最大散度或纯 $\epsilon$ 形式描述，会导致隐私账本错误。

解决：高斯机制用 $(\epsilon ,\delta )$ 或 Rényi 形式描述，$\delta$ 正是为了容纳尾部的小概率例外。报告隐私参数时给出三项：机制类型、$(\epsilon ,\delta )$ 的具体数值与组合方式（基本组合或 Rényi 组合）。用 Rényi 形式时同时给出阶参数 $\alpha$，因为损失值依赖它。

错误 4 · 把量子熵直接类比经典熵而不检查前提

原因：量子条件熵可以为负，量子互信息可以超过两部分各自的熵（Bell 态中为 $2$ 比特），这些现象在经典情形不会出现。用经典直觉判断量子表达式的大小（例如默认条件熵非负、由此推出矛盾），会得到错误的结论。

解决：使用量子量时回到定义：$S(A\mid B)=S({\rho }_{AB})-S({\rho }_B)$ 只是一个差分，不保证非负；判断非负性的经典依据（条件化减少不确定性）在纠缠存在时不成立。分析具体系统时先写出密度矩阵与偏迹，再计算熵，避免用经典不等式直接推断。经典直觉仍然可用的范围是确定的：纯态（无纠缠）的系统、以及对纠缠方向做测量后的条件分布。