Near-optimal Bayesian Active Learning with Correlated and Noisy Tests

1研究问题

要通过一系列带噪声的测试，确定目标变量 Y 的取值（例如该用哪种治疗）。难点在于测试并不直接依赖 Y，而是依赖一个隐藏的"根因" Θ（例如病人的真实身体状况），Y 是 Θ 的函数。于是给定 Y 时，测试结果之间是相关的。这种情况下，按信息增益或 GBS 贪心都可能任意差。

2模型

• 根因 Θ 有 n 个取值，先验已知；目标 Y = r(Θ) 是确定映射。
• 测试 X_1…X_m 在给定 Θ 时条件独立，噪声是持久的（重复同一测试得到同样结果）。
• 目标：在期望预测误差（MAP 估计出错的概率）不超过 δ 的前提下，最小化最坏情况下的测试次数。
• δ=0 且无噪声时，问题就是 EC² 处理的等价类判定。

3为什么简单推广失败

有噪声时，单个结果不能彻底排除某个根因，边无法"切断"。一个自然想法是按似然更新边权（作者称 EC²-Bayes），每次选能让总边权期望下降最多的测试。作者给了一个三根因的小例子：一个完全随机的测试和一个无噪声的有用测试相比，EC²-Bayes 反而选前者（期望下降 0.18 对 0.112）。直接优化预测误差也不行，因为它不是自适应子模的，测试间的互补性会让贪心任意差。

4ECED 算法

1. 初始边与 EC² 相同：不同目标值的根因两两连边，边权为先验概率之积。
2. 观测到结果 x 后，对每个根因 θ 计算似然比 λ = P(x|θ) / max_x' P(x'|θ)。结果与 θ 最可能的结果一致时 λ=1，不打折；不一致时 λ<1。
3. 测试的价值 = 期望被打掉的边权，再减去一个"偏移项"，使纯噪声测试的价值恰好为 0。
4. 每次选价值最大的测试，观测结果后按似然更新边权，直到 MAP 误差不超过 δ。

5理论保证（定理 1）

在测试结果为二值、各测试噪声率与根因无关的情形下：要让期望误差低于 δ，ECED 运行的步数是"达到更低误差的最优策略的代价"乘以一个对数平方量级的因子，再除以噪声强度 c_ε = min_e (1−2ε_e)²。噪声越大，界越差；c_ε=1（无噪声）时 ECED 退化为 EC²。证明结合了一个信息论辅助函数与自适应子模性。

6实验

两个应用：沿用 EC² 的行为经济学理论区分实验，以及通过成对比较的主动偏好学习。正文报告 ECED 的表现优于常见基线；附录还有一个基于样本池的主动学习应用。没有图或传播的实验。

7代码情况

2026-10-13 在 GitHub 按算法名与作者检索，没有找到作者发布的代码，本页不讲解实现。正文算法 1 已给出完整步骤：初始化跨类边权、按"似然比打折减去偏移项"选测试、观测后按似然更新边权、MAP 误差低于 δ 时停止。每一步要对所有跨类根因对求和，根因数大时需要像 EC² 的 EFFECXTIVE 那样做近似。

8与你的方案（传感器部署 + 有效源集合）的关系

• 传感器读数在"给定源"时是相关的，因为它们共享同一次传播实现。这正是 ECED 的设定：取 Θ = (源, 传播实现)，Y = 源。
• 但在这个取法下，给定 Θ 时传感器读数是确定的而非带独立噪声，ECED 的定理条件（二值、独立噪声）并不对应；Θ 的取值数量也大到无法显式枚举。所以不能直接继承它的保证。
• ECED 和 EC² 都是自适应策略，你的方案是静态部署；目标也不同（它们要求误差 ≤ δ 的点判断，你要求覆盖 ≥ 1−α 的集合尽量小）。
• 可借鉴："按似然比打折、对纯噪声测试设为零价值"的思路，可用来设计静态部署时的边际增益。方案里引用它，主要是说明"相关观测下的观测选择"已有通用理论，你的贡献不能放在这一点上。