二值表示对二值源信息瓶颈总是足够吗？

基数界问的是 U 需要多少符号

信息瓶颈寻找源 X 的一个表示 U，在把 I(U;X) 压在速率约束 R 以下的同时，尽可能多地保留关于目标 Y 的信息。形式上，对 R ≥ 0，最优权衡由 IB 函数 F(R) = max { I(U;Y) : U↔X↔Y, I(U;X) ≤ R } 描述。这篇论文回答的不是如何计算 F(R)，而是要让该最大值被达到，U 的字母表必须有多大。

一个经典论证——来自 Witsenhausen 和 Wyner，也可由支撑引理推出——表明 |U| ≤ |X|+1 个符号总是足够。该界随后被证明在 |X| ≥ 3 时是紧的：对输入均匀的汉明信道，在某个区间 (0, R_c) 内的所有速率上，|X|+1 个符号都是必要的。二值情形 |X| = 2 未被这些结果覆盖，这篇论文补上了这一空缺。

二值源只需两个符号而非三个

定理 2.1 指出，若 X = {0,1} 且 Y 有限，则对任意 R ≥ 0，IB 函数中的最大值都能由某个满足 |U| ≤ 2 的 U 达到。该结果对每个联合分布 P_XY 和每个速率约束都成立，而不只是对称信道。因此一般界 |U| ≤ |X|+1 对二值源永远不紧，早先紧性结果中 |X| ≥ 3 的条件不能去掉。

这是关于 IB 函数 F 本身、而不只是关于 IB 拉格朗日量的陈述。早先工作曾指出，|U| ≤ |X| 的说法混淆了拉格朗日量（对它而言 |X| 个符号确实足够）与 F（其图像可能包含线性段）。因此二值定理强于拉格朗日量层面的基数主张：它覆盖了函数在每个速率上的最优值。

为什么曾认为多一个符号是必要的

|X|+1 界并非分析粗糙的产物。对输入均匀且 |X| ≥ 3 的汉明信道，每个最优 U 在小速率下都需要 |X|+1 个符号，所以该界确实被达到。二值情形之所以能避开这一点，原因在于结构：给出更紧界的证明技巧依赖于源后验是一个标量，而一旦 X 上的概率单纯形维数达到 |X|−1 ≥ 2，这一点就不再成立。

对双重对称二值源，Gerber 夫人引理已经表明二值 U 是最优的，但该论证依赖信道的对称性。这里的贡献在于去掉对称性假设，对 X 为二值的任意联合分布建立二值最优性。

证明把 IB 化为凸包上的最小化

论证把 IB 问题约化为在一条曲线的凸包 K 上最小化 H(Y|U)。候选 U 的每个符号 u 对应 [0,1] 中的一个点 q_u = P(X=1|U=u)，可达对 (H(X|U), H(Y|U)) 恰好是满足 (p,s,t) ∈ K 的点 (s,t)，其中 p = P(X=1)。由于 I(U;X) = h(p) − H(X|U) 且 I(U;Y) = H(Y) − H(Y|U)，在 I(U;X) ≤ R 下最大化 I(U;Y) 等价于在 K 上、约束 s ≥ h(p) − R 下最小化 t。

对 K 与区域 { s ≥ h(p) − R, t < t* } 应用分离超平面定理，得到一个非零向量 (c0, c1, c2)，其中 c2 ≥ 0，以及函数 ψ(q) = c0 q + c1 h(q) + c2 g(q)，这里 h 是 q 的二元熵，g(q) = H(f(q))，f(q) = (1−q)w0 + q w1。最优 U 的每个原子 q*_u 于是都是 ψ 在 [0,1] 上的最小点，且取同一最小值 α。

导数之比的凹性限制了最小点个数

关键一步是二值源特有的曲率计算。把 ψ''(q) = h''(q)(c1 + c2 r(q)) 写成 r(q) = g''(q)/h''(q)，论文证明 r(q) = 1 − Σ_y w0(y)w1(y)/f_y(q)，而由于每个 1/f_y(q) 在 q 上凸且 w0(y)w1(y) ≥ 0，r 在 (0,1) 上凹。又因 h''(q) < 0，集合 { q : ψ''(q) < 0 } 等于凹函数的上水平集 { q : c1 + c2 r(q) > 0 }，因而是一个区间。

正是这一区间性质限制住了最小点的个数。引理 4.1 表明，若 ψ(q) = α 在 [0,1] 中多于两个点上成立，则 ψ 在 [0,1] 上恒等于 α。证明用到：ψ'' < 0 的集合不可能同时与三个有序最小点 q1 < q2 < q3 之间的两个区间相交，因为那将迫使内点最小点处 ψ''(q2) < 0，与 ψ''(q2) ≥ 0 矛盾。剩余情形归结为一个多项式恒等式论证。

两种情形都给出二值最优解

既然每个 q*_u 都最小化 ψ，引理 4.1 只留下两种可能。第一种情形下 q*_u 至多取两个不同值，把 U* 中共享同一 q*_u 的符号合并，得到新表示 Û = σ(U*)，满足 |Û| ≤ 2。合并后的表示保持点 z* = (p, H(X|U*), H(Y|U*)) 不变，因此仍是最优的。

第二种情形下 ψ ≡ α，这迫使 c1 + c2 r(q) ≡ 0，从而 c2 > 0。此时 H(Y|U) 由 H(X|U) 通过 H(Y|U) = (α − c0 p − c1 H(X|U))/c2 确定，所以任何满足 H(X|U) = s* 的 U 都是最优的。这样的二值 U 通过时间共享构造：取 T ~ Bern(θ) 与 X' ~ P_X，二者都与 (X,Y) 独立，令 T = 1 时 U_θ = X，T = 0 时 U_θ = X'。由于 H(X|U_θ) 关于 θ 连续，并在 θ = 1 时取 0、θ = 0 时取 h(p)，介值定理给出某个 θ* 使 H(X|U_θ*) = s*。两种情形下最大值都由某个满足 |U| ≤ 2 的 U 达到。

紧界在源符号数为三处发生分界

把定理 2.1 与早先的汉明信道结果结合，得到紧基数界 M，即使得 |U| ≤ M 对每个 P_XY 都足够的最小 M：|X| = 2 时 M = 2，|X| ≥ 3 时 M = |X|+1。因此二值情形不是一般界的一个小实例，而是一个真正不同的区域。

论文还解释了为何该证明不能推广到 |X| ≥ 3。第 1、2 步仍然成立，但第 3、4 步依赖 q 是标量。对 |X| ≥ 3，二阶导数变成 Hessian c1 ∇²_q H(q) + c2 ∇²_q H(qW)，而它失去半正定性的集合由一个广义特征值问题决定，而不是由单个凹函数的符号决定。排序也失效：维数至少为二的单纯形上，三个最小点之间没有自然的中间点，目标会变成至多 |X| 个最小点而非两个。这些障碍不只是技术性的，因为对汉明信道，相应的 ψ 至少有 |X|+1 个不同最小点。刻画哪些 |X| ≥ 3 的源允许 |X| 个符号仍然是一个开放问题。

本文引用的文献