NeurIPS 2010 · 23: 766–774
Near-Optimal Bayesian Active Learning with Noisy Observations
要用尽量少的昂贵测试，判断真相属于哪一"类"。作者发现常见的贪心准则在有噪声时会很差，于是提出 EC²：把"不同类之间的假设对"连成带权边，每次选能切掉最多边权的测试，并证明它与最优策略只差对数倍。
1研究问题
有一组假设（理论、诊断、模型）和一组可做的测试，每个测试有代价、结果有噪声。目标是自适应地选测试，以最小期望代价确定该采取的决策。最优策略不仅 NP 难，而且难以近似。
2无噪声背景
无噪声时，每个假设对应一组确定的测试结果。经典方法广义二分搜索（GBS）每次选能排除最多先验概率的测试，期望代价与最优只差 ln(1/p_min)+1 倍。这一保证来自自适应子模性：越早做的测试，期望收益越大。
3等价类判定（ECD）与 EC²
把假设分成若干等价类，只需判断真假设落在哪一类。作者给出例子：GBS 在这种问题上可能比最优差 n/2 倍；按"类的熵"贪心选择也会差 Ω(n/log n) 倍，原因是测试之间有互补性。
- 在属于不同类的每对假设之间连一条边，边权为两者先验概率之积。
- 某个测试的结果若与边的一个端点矛盾，就"切掉"这条边。
- 目标函数：已切掉的边权总和。它自适应子模、强自适应单调（命题 2）。
- EC² 每次贪心选择期望切边权与代价之比最大的测试，直到剩下的假设都在同一类。
定理 3：EC² 的期望代价不超过最优策略的 (2 ln(1/p_min) + 1) 倍；测试代价相同时可改进到 O(log n)。
4处理噪声
- 把噪声写成额外的随机变量 Θ：测试结果是 (假设, Θ) 的确定函数。若不同假设永远不会产生同样的结果，就把每个"假设 × 噪声实现"当作新假设，原假设对应一个等价类，直接套用 EC²。
- 一般情况下做完所有测试仍不能确定真假设。作者改为对决策分类：所有导致同一最优决策的结果向量构成一类，于是问题仍是 ECD（定理 4）。
- 噪声取值很多时，等价类会指数级大。作者提出近似算法 EFFECXTIVE：每次选使后验概率平方和期望增加最多的测试，可看作基于二阶 Rényi 熵的信息增益。
5实验
应用是行为经济学实验设计：给被试一对彩票让其选择，用以区分期望值、前景理论、均值–方差–偏度、常相对风险厌恶四种理论。模拟中，不确定性抽样、GBS、决策价值（VoI）表现甚至不如随机选择；EFFECXTIVE 明显优于 Shannon 信息增益，后者又优于随机。作者也在真人被试上运行了该方法。
6局限
- 保证依赖"噪声可约化为等价类判定"，噪声取值多时只能用没有保证的近似 EFFECXTIVE。
- 是自适应（逐个测试、看结果再选）的策略，不是一次放完的静态选择。
- 没有图或传播的实验。
7代码情况
2026-10-13 在 GitHub 按算法名与作者检索，没有找到作者发布的代码，本页不讲解实现。论文给出的 EFFECXTIVE 伪代码（算法 1）只需后验概率与每个测试结果的条件概率，可以直接按式子实现；朴素存储所有跨类边在假设数大时不可行，这是自己实现时的主要成本。
8与你的方案（传感器部署 + 有效源集合）的关系
- 把"传感器"看成测试、"源"看成需要判断的类，EC² 是通用的观测选择框架。若取 Θ = 源与一次完整传播实现，传感器读数就是 Θ 的确定函数，形式上可以套用；但传播实现的数量巨大，显式边集不可存储。
- 它的目标是"确定类"，最终要求后验集中到一类；你的目标是在给定覆盖下让集合尽量小，二者不同。
- 可借鉴：EFFECXTIVE 的"后验平方和"准则可以改写成静态部署的一个打分基线；"测试有互补性导致简单贪心失败"的论述，可用来说明为什么你的方案要做成对交换。