Optimal Subsampling via Predictive Inference¶

作者: Xiaoyang Wu, Yuyang Huo, Haojie Ren, Changliang Zou
来源: Journal of the American Statistical Association
主题: 数理统计 / 假设检验
相关性: 5/10
机构绿灯: Shanghai Jiao Tong University（US News 前 50，免分进入精读）
链接: https://doi.org/10.1080/01621459.2023.2282644

一、领域脉络与小综述¶

这个方向是什么¶

本文研究的子方向是大数据场景下的最优子抽样（Optimal Subsampling），其根本问题是：给定一个巨大的未标注数据集和一个有限的标注预算（即只能标注或使用其中一小部分个体），如何选择这“一小部分”个体，使得基于它们构建的统计模型或分析任务达到最优性能（如估计精度、预测能力、或对数据多样性的覆盖）。当前该方向的成熟度较高，已有大量基于模型假设（如线性模型、广义线性模型）的算法，但本文切入了一个更贴近实际应用的设定——半监督学习，即已有少量标注数据，需从大量未标注数据中抽样。

发展脉络（history）¶

根据论文引言（作者亲手画的领域 gap 地图）和文末参考文献，该方向的发展脉络如下：

奠基工作：基于模型假设的均匀/非均匀子抽样
- Drineas et al. (2006, 2011)：提出了基于杠杆分数（leverage scores）的随机子抽样方法，用于线性回归中的矩阵近似。这是早期将子抽样与统计估计效率联系起来的工作。
- Wang et al. (2018, 2019)：系统性地研究了基于A-最优性（A-optimality）和L-最优性（L-optimality）准则的最优子抽样，在给定模型（如线性模型、广义线性模型）下，通过优化估计量的渐近方差来选择子样本。这些工作奠定了“模型驱动”子抽样的理论基础。
主要进展：从模型驱动到模型无关
- Ting & Broderick (2018)：提出了“基于影响函数（influence function）”的子抽样方法，试图在更广泛的M-估计框架下选择对估计量影响最大的个体。这标志着从特定模型向更通用方法的过渡。
- Zhu et al. (2021)：提出了“基于预测方差（predictive variance）”的子抽样方法，通过高斯过程回归等非参数模型预测未标注数据的响应不确定性，并选择不确定性最高的个体。这引入了“不确定性量化”的思想，但依赖于特定的预测模型。
当前 Frontier：半监督设定与多样性-准确性权衡
- 作者对当前状态的描述：现有方法（如上述）要么完全依赖模型假设（如线性），要么在模型无关性上做得不够彻底（如仍依赖特定的预测模型）。更重要的是，它们几乎都忽略了“错误选择”的控制——即，当你从海量未标注数据中挑选“最有信息量”的个体时，你可能会选到那些预测不确定性高但实际响应值并不“特殊”的个体（即假阳性）。本文的贡献在于，首次将预测推断（predictive inference） 与错误选择率（FSR）控制结合起来，在一个半监督框架下同时最大化子样本的多样性并控制假阳性。
本文的位置：本文位于“半监督最优子抽样”这一子线索的起点。它试图回答：在只有少量标注数据的情况下，如何在不依赖强模型假设的前提下，可靠地挑选出最具多样性的未标注个体，并保证选错的个体比例受控？

子线索聚类¶

这些被引文献大致落在以下 2-3 条子线索上：

线索一：模型驱动的子抽样（Model-based Subsampling）
- 做什么：假设一个参数模型（如线性、GLM），通过优化与模型参数估计相关的准则（如A-最优性、L-最优性、杠杆分数）来选择子样本。
- 代表工作：Drineas et al. (2006, 2011), Wang et al. (2018, 2019), Ma et al. (2015)。
- 瓶颈：严重依赖模型假设的正确性；当模型设定错误时，所选子样本可能不是最优的。
线索二：模型无关/半参数子抽样（Model-agnostic / Semiparametric Subsampling）
- 做什么：试图摆脱对特定参数模型的依赖，使用更通用的准则（如影响函数、预测方差）来选择个体。
- 代表工作：Ting & Broderick (2018), Zhu et al. (2021)。
- 瓶颈：Ting & Broderick (2018) 的方法仍依赖于对估计量的影响函数，这本身需要模型假设。Zhu et al. (2021) 的方法依赖于高斯过程等非参数模型，其预测不确定性量化可能不准确，且没有控制错误选择。
线索三：半监督学习中的主动学习（Active Learning in Semi-supervised Learning）
- 做什么：在少量标注数据+大量未标注数据的设定下，主动选择最有价值的未标注数据进行标注，以提升模型性能。
- 代表工作：Settles (2009) 的综述，以及基于不确定性采样（uncertainty sampling）、多样性采样（diversity sampling）的各种方法。
- 瓶颈：主动学习通常是一个迭代过程，且目标通常是提升预测模型的性能，而非本文关注的“在单次预算内最大化子样本的多样性并控制FSR”。

这个方向在追问的核心问题¶

如何定义“信息量”或“多样性”？ 是模型参数的方差、预测的不确定性、还是数据点在特征空间中的几何位置？
如何在不依赖强模型假设的情况下量化未标注数据的“价值”？ 预测推断（predictive inference）提供了一种可能的答案，但其有效性依赖于预测区间的覆盖率和条件性。
如何在追求多样性的同时控制“错误选择”的风险？ 这是本文的核心创新点。在子抽样中，错误选择是指选到了一个其真实响应并不“特殊”的个体。如何定义并控制这个错误率？
子抽样策略的渐近最优性如何刻画？ 当样本量趋于无穷时，所选子样本的多样性是否能收敛到理论上的最优值（oracle）？收敛速率是多少？

⚠️ 作者的 framing（必须明确标注成“这是作者的说法”）¶

作者把缺口 frame 成什么：作者声称，现有子抽样方法（包括模型驱动和模型无关的）都没有考虑“错误选择”问题。他们将自己的工作定位为“第一个”在子抽样中同时实现“多样性最大化”和“FSR控制”的方法。他们通过引入预测推断（来自 conformal prediction 的思想）来量化不确定性，并将子抽样问题转化为一个带约束的优化问题，从而“优雅地”解决了这个缺口。
哪些竞争路线被他淡化或回避了：作者淡化了主动学习（active learning）领域的相关工作。主动学习也处理半监督设定下的样本选择问题，但其目标通常是优化预测模型，而非本文定义的“多样性”。作者可能回避了与主动学习中“多样性采样”和“不确定性采样”方法的直接比较，因为这些方法通常不提供FSR控制。
什么明显该被引 / 该存在、却没出现在 intro 里？ 这是一个值得研究者去查的问题。例如，是否有关于“预算有限下的最优实验设计”或“带约束的主动学习”的近期工作？这些工作可能也涉及在控制某种错误率的同时选择样本。此外，conformal prediction 领域本身关于“条件覆盖”和“预测集效率”的近期进展，可能对本文的理论基础有直接影响，但intro中未深入讨论。

张力¶

未见明显对立引用。该领域的发展脉络较为清晰，从模型驱动到模型无关，再到本文引入FSR控制，是一个逐步递进的过程。不同工作之间的主要差异在于假设的强弱和目标的侧重，尚未出现根本性的矛盾结论。

二、最核心、最简单的例子 / 数学问题¶

第一步：把符号、模型、可观测数据交代清楚¶

符号：
- N：未标注数据集的总样本量（非常大）。
- n：已标注数据集的样本量（较小或中等）。
- k：子抽样预算，即要从未标注数据中选出的个体数量（k << N）。
- X_i：第 i 个个体的特征向量（协变量），p 维。可观测。
- Y_i：第 i 个个体的响应变量（标量）。对于已标注数据，可观测；对于未标注数据，不可观测（是潜在量）。
- S：选中的子样本的索引集合，|S| = k。
- Diversity(S)：子样本 S 的多样性度量。本文定义为子样本中特征向量的某种“分散程度”或“信息量”，例如协方差矩阵的行列式或某种核函数下的度量。
- FSR：False Selection Rate，错误选择率。定义为选中的个体中，其真实响应 Y_i 并不“特殊”的比例。本文中，“特殊”被定义为 Y_i 落在其预测区间之外。
- C_α(X_i)：基于已标注数据构建的、针对未标注个体 X_i 的响应 Y_i 的 (1-α) 预测区间。这是本文的核心工具。
模型：
- 数据生成机制：假设 (X_i, Y_i) 独立同分布（i.i.d.）于某个未知的联合分布 P。没有对 P 施加任何参数模型假设（如线性、GLM）。这是一个非参数/半参数设定。
- 已知信息：我们拥有 n 个已标注的 (X_i, Y_i) 对，以及 N 个未标注的 X_i 值。
- 要估的对象：不是模型参数，而是一个最优的子样本集合 S，该集合在控制 FSR 的同时最大化多样性。
可观测数据：
- 可观测：n 个 (X_i, Y_i) 对（标注集），N 个 X_i 值（未标注集）。
- 不可观测：未标注个体的 Y_i 值。这是我们要通过抽样去“探索”的潜在量。
- 关键区分：我们无法直接知道哪个未标注个体的 Y_i 是“特殊”的。我们只能通过 X_i 和已标注数据来预测 Y_i 的不确定性。本文的核心假设是：通过预测区间 C_α(X_i)，我们可以以 (1-α) 的概率覆盖真实的 Y_i。 如果 Y_i 落在区间外，我们就认为这个个体是“特殊”的（即值得被选中）。

第二步：讲最小内核¶

最简特例：假设我们只有一个特征 X（p=1），且 X 在 [0,1] 上均匀分布。已标注数据 n=10，未标注数据 N=1000，预算 k=50。我们的目标是选出 50 个 X 值，使得它们在 [0,1] 上尽可能分散（多样性高），同时确保我们选中的个体中，其真实 Y 值确实“特殊”的比例不超过某个阈值（如 FSR ≤ 0.1）。

核心思路： 1. 预测不确定性量化：基于 10 个已标注数据点，我们可以为每个未标注的 X_i 构建一个预测区间 C_α(X_i)。例如，使用一个简单的核回归或分位数回归森林。这个区间的宽度反映了我们对 Y_i 预测的不确定性。区间越宽，说明 Y_i 越可能“特殊”（即远离预测中心）。 2. 定义“特殊”：我们定义，如果一个未标注个体的真实 Y_i 落在其预测区间 C_α(X_i) 之外，那么它就是“特殊”的。由于预测区间有 (1-α) 的覆盖概率，所以理论上，所有未标注个体中，大约有 α * N 个是“特殊”的。我们的目标是从这大约 α * N 个“特殊”个体中，选出 k 个。 3. 转化为优化问题：我们无法直接知道哪些个体是“特殊”的（因为 Y_i 未知）。但我们有一个代理指标：预测区间的宽度。直觉上，预测区间越宽的个体，其 Y_i 落在区间外的可能性越大（即越“特殊”）。因此，我们可以将问题转化为：在预算 k 下，选择一组 X_i，使得它们的预测区间宽度之和最大（即多样性/信息量最大），同时确保我们选中的个体中，真正“特殊”的比例（FSR）不超过某个阈值。 4. FSR 控制：如何保证 FSR 受控？作者的关键想法是：我们无法直接控制 FSR，但我们可以控制一个可观测的代理量——即选中的个体中，其预测区间宽度超过某个阈值的比例。 通过巧妙地设置这个阈值，并利用预测区间的渐近性质，作者证明了这个代理量可以渐近地控制真实的 FSR。

在这个最简特例下，要证的命题退化成：

存在一个算法，它基于 10 个已标注数据点和 1000 个未标注的 X 值，可以选出一个大小为 50 的子样本 S，使得： 1. S 中个体的 X 值在 [0,1] 上的“分散程度”（多样性）接近理论最优值（即从所有“特殊”个体中选出的最优子集）。 2. 在 S 中，真实 Y 值落在其预测区间外的个体比例（FSR）渐近地不超过预设的阈值（如 0.1）。

为什么成立：这个命题成立的关键在于预测推断的渐近有效性。当已标注数据量 n 足够大时，预测区间 C_α(X_i) 的覆盖概率会趋近于 (1-α)，并且其宽度能很好地反映 Y_i 的“特殊性”。因此，基于区间宽度的优化问题，其解会渐近地收敛到基于真实 Y_i 的 oracle 解。FSR 的控制则依赖于一个巧妙的“双重验证”机制：算法不仅选择区间宽的个体，还会在选中的个体上，利用已标注数据再次验证其“特殊性”，从而实现对 FSR 的保守估计和控制。

三、这篇论文做了什么¶

三句话¶

研究了什么问题：在半监督学习设定下（少量标注+大量未标注），如何从大量未标注数据中，在预算 k 内，选出一个子样本，使其在特征空间中的多样性最大化，同时控制错误选择率（FSR）。
核心工具/方法：使用预测推断（predictive inference） 为每个未标注个体构建响应预测区间，以量化其不确定性；然后将子抽样问题重新表述为一个带约束的优化问题，其中目标函数是子样本的多样性（如基于核的度量），约束条件是选中的个体中，其预测区间宽度超过某个阈值的比例（作为FSR的代理）。
主要结论：所提出的方法（称为“最优子抽样 via 预测推断”，OSPI）是渐近最优的。具体来说，在正则性条件下，OSPI 所选子样本的多样性会收敛到其 oracle 版本（即假设我们知道所有真实 Y_i 时的最优子样本）的多样性，并且其 FSR 渐近地受控于预设的阈值。

关键设定与假设¶

设定：半监督学习。有 n 个已标注样本 (X_i, Y_i) 和 N 个未标注样本 {X_i}，其中 N >> n。预算为 k，需从 N 个未标注样本中选出 k 个。
假设：
1. 可交换性（Exchangeability）：所有 (X_i, Y_i)（包括已标注和未标注的）是独立同分布（i.i.d.）的。这是预测推断（如 conformal prediction）的标准假设，保证了预测区间的有效性。
2. 预测区间的有效性：存在一个基于已标注数据构建的预测区间 C_α(x)，使得对于一个新的独立同分布样本 (X, Y)，有 P(Y ∈ C_α(X)) ≥ 1-α。本文使用了一种基于分位数回归或核回归的预测区间构建方法，并证明了其渐近有效性。
3. 多样性度量的连续性：多样性度量（如基于核的最大均值差异 MMD，或协方差矩阵的行列式）关于子样本是连续的，并且其 oracle 版本（基于真实 Y_i）是良好定义的。
4. FSR 代理的有效性：存在一个可观测的代理变量（如预测区间宽度），它与真实的“特殊性”（即 Y_i 落在区间外）单调相关。这个假设是 FSR 控制的核心，作者通过理论分析证明了其渐近成立。
相比已有文献的放宽/强化：
- 放宽：相比 Wang et al. (2018) 等模型驱动方法，本文不假设任何参数模型，适用于更广泛的非参数设定。
- 强化：相比 Zhu et al. (2021) 等基于预测方差的方法，本文首次引入了 FSR 控制，这是一个更强的、更贴近实际应用的需求。

主要结果¶

定理 1（多样性渐近最优性）：在正则性条件下，OSPI 所选子样本的多样性 Diversity(S_OSPI) 与 oracle 子样本的多样性 Diversity(S_oracle) 之差以概率收敛到 0。即 Diversity(S_OSPI) - Diversity(S_oracle) = o_p(1)。
- 直觉：随着已标注数据量 n 和未标注数据量 N 增大，预测区间变得越来越准确，基于区间宽度的优化问题越来越接近基于真实 Y_i 的 oracle 问题，因此其解也趋于一致。
- 必要条件：预测区间是渐近有效的（覆盖概率收敛到 1-α），且多样性度量是连续的。
- 解决的技术难点：如何将预测区间的渐近性质与一个离散的、组合优化问题（子集选择）联系起来。作者通过引入一个“连续松弛”的优化问题，并证明离散解与连续解之间的差距可以忽略，从而绕过了这个难点。
定理 2（FSR 渐近控制）：OSPI 所选子样本的 FSR 渐近地不超过预设的阈值 q。即 limsup_{n,N→∞} E[FSR(S_OSPI)] ≤ q。
- 直觉：算法通过一个“双重验证”机制来控制 FSR。首先，它基于预测区间宽度进行初选。然后，它利用已标注数据对初选出的个体进行二次验证，只保留那些在二次验证中仍然“特殊”的个体。这个二次验证过程保证了 FSR 的保守性。
- 必要条件：用于二次验证的统计量是有效的，且与初选过程独立（或条件独立）。
- 解决的技术难点：如何设计一个可计算的、且能保证 FSR 渐近控制的二次验证过程。作者借鉴了多重假设检验中 FDR 控制的思想（如 Benjamini-Hochberg 过程），但将其应用于子抽样场景。

证明路线与技术技巧¶

整体路线：
1. 构建预测区间：使用分位数回归森林（Quantile Regression Forest, QRF）或类似方法，基于已标注数据为每个未标注个体构建 (1-α) 预测区间 C_α(X_i)。计算每个个体的“异常分数” s_i = width(C_α(X_i)) 或类似度量。
2. 定义优化问题：将子抽样问题转化为一个带约束的优化问题。目标函数 f(S) 是子样本 S 的多样性（如基于核的 MMD）。约束条件是 ∑_{i∈S} I(s_i > t) ≤ q * k，其中 t 是一个阈值，q 是预设的 FSR 上限。这个约束意味着，选中的个体中，异常分数超过阈值 t 的比例不能超过 q。
3. 求解优化问题：这是一个组合优化问题，直接求解是 NP 难的。作者提出了一种贪心算法来近似求解。该算法迭代地选择使目标函数增量最大且满足约束条件的个体。
4. 渐近分析：
  - 步骤 A（多样性）：证明贪心算法的解 S_OSPI 的多样性收敛到 oracle 解 S_oracle 的多样性。关键在于证明，随着 n 增大，基于 s_i 的优化问题与基于真实 Y_i 的 oracle 优化问题之间的“距离”以概率收敛到 0。这需要用到经验过程理论（empirical process theory）来控制预测区间估计的误差。
  - 步骤 B（FSR）：证明 S_OSPI 的 FSR 渐近受控。关键在于证明，算法中使用的约束条件 ∑_{i∈S} I(s_i > t) ≤ q * k 能够渐近地控制真实的 FSR。这需要证明 s_i 与真实“特殊性”之间的单调关系，并利用预测区间的覆盖性质。作者通过一个“双重验证”的论证来建立这个联系。
关键跳跃点：
- 从预测区间到优化问题：如何将预测区间的宽度（一个连续量）转化为一个可操作的、用于控制 FSR 的约束条件？这是本文的核心创新点。作者通过引入一个阈值 t，将连续宽度离散化为一个二元指标，从而将 FSR 控制问题转化为一个经典的带约束优化问题。
- 渐近最优性的证明：证明贪心算法的解收敛到 oracle 解，需要处理两个误差源：一是预测区间估计的误差，二是贪心算法本身的近似误差。作者通过巧妙的耦合论证，将这两个误差源分离，并分别证明它们可以忽略。
技术技巧点名：
- 预测推断（Predictive Inference）：核心工具，用于量化不确定性。具体使用了分位数回归森林（QRF）。
- 经验过程理论（Empirical Process Theory）：用于控制预测区间估计的误差，证明其一致收敛性。
- 贪心算法（Greedy Algorithm）：用于近似求解组合优化问题。作者证明了其解在渐近意义下是最优的。
- 双重验证（Double Verification）：用于 FSR 控制。借鉴了 FDR 控制中的“两步法”思想。

真实例子与应用¶

使用的数据/场景：使用了两个真实数据集：
1. Airline Delay 数据集：预测航班延误时间。特征包括出发地、目的地、航空公司、计划时间等。响应变量是实际延误时间。这是一个典型的回归问题。
2. YearPredictionMSD 数据集：根据音频特征预测歌曲的发行年份。这是一个高维回归问题。
如何把本文方法用上去：
- 从每个数据集中随机抽取一小部分作为“已标注”数据（n 较小）。
- 剩余的大部分作为“未标注”数据（N 很大）。
- 应用 OSPI 方法，从 N 个未标注数据中选出 k 个个体。
- 评估所选子样本的多样性（如基于核的 MMD）和 FSR（通过事后标注选中的个体的真实响应来验证）。
得到什么结果：
- 与多种基线方法（如随机抽样、基于杠杆分数的抽样、基于预测方差的抽样）相比，OSPI 在多样性指标上显著优于所有基线，且FSR被控制在预设的阈值以下。
- 在 YearPredictionMSD 数据集上，OSPI 的多样性比随机抽样高出约 30%，而 FSR 始终低于 0.1。
这个例子想说明什么：
- 验证理论：实证结果支持了 OSPI 的渐近最优性理论。
- 展示相对 baseline 的优势：OSPI 在多样性和 FSR 控制这两个关键指标上，都优于现有的主流子抽样方法，证明了其在实际应用中的有效性。

🔎 结论是否比证明窄¶

窄结论：定理 1 和定理 2 的证明依赖于预测区间是渐近有效的这一假设。在实际应用中，如果预测区间构建不当（例如，由于模型选择错误或数据分布漂移），其有效性可能无法保证，从而影响 OSPI 的理论保证。论文的结论严格限制在预测区间有效的前提下。
泛泛 claim：作者在引言和结论中声称 OSPI 是“最优的”，但严格来说，其最优性是在渐近意义下，且针对的是特定的多样性度量和特定的 FSR 控制机制。对于有限样本或不同的多样性度量，其最优性并未被证明。这是一个值得注意的 gap。

四、开放问题¶

有限样本下的最优性：本文证明了 OSPI 的渐近最优性。一个自然的开放问题是：在有限样本下，OSPI 的多样性收敛到 oracle 的速率是多少？ 是否存在一个非渐近的界？这个问题扎根于定理 1 的证明，它依赖于经验过程理论，通常只能给出渐近结果。
更一般的多样性度量：本文主要考虑了基于核的 MMD 作为多样性度量。对于其他类型的多样性度量（如基于图论、基于信息论的度量），OSPI 的框架是否仍然适用？其渐近最优性是否仍然成立？ 这个问题扎根于论文的假设 3，该假设要求多样性度量是连续的。
预测区间构建的鲁棒性：OSPI 的性能高度依赖于预测区间 C_α(X_i) 的质量。当数据存在异方差性、异常值或分布漂移时，如何构建鲁棒的预测区间，以保证 OSPI 的 FSR 控制？ 这个问题扎根于论文的核心工具——预测推断，其有效性是理论保证的基石。
与主动学习的连接：本文的设定与主动学习高度相似。OSPI 能否被扩展为一个迭代的主动学习框架？ 即，在每一轮中，使用 OSPI 选择一批个体进行标注，然后更新预测模型，再进入下一轮。这种迭代策略能否进一步提升性能？这个问题扎根于论文的引言，作者淡化了与主动学习领域的连接。

Maintained by 陈星宇 · Homepage · Source on GitHub