线性回归中近视贝叶斯主动学习风险的近似比

# 近视贝叶斯主动学习用于线性回归的风险近似比 来源：https://arxiv.org/html/2607.06642

###### 摘要

主动学习研究一个基本问题：我们应该选择哪些数据进行观测？最优实验设计中的贪心算法是一种常见的启发式方法，同时等价于用于线性回归的*近视*贝叶斯主动学习，这是一种常见的框架，其中长期规划被单步最优选择所取代。在本文中，我们首次证明了贪心算法风险的近似比，该近似比精确到绝对常数。近似比与*最大初始杠杆得分*（MILS）呈线性关系，这是新发现的、对贪心算法性能至关重要的量。最后，我们通过简单的数值模拟来展示结果。

## 1 引言

最优实验设计和主动学习是在预算约束下选择信息性数据的两种密切相关范式。两者都问同一个基本问题：给定从候选输入池中选择的自由，我们应该观测哪些输入以最小化模型参数估计误差或未来预测误差？在实验设计中，选择通常是离线进行的，而在主动学习中，选择是随着新标签的观测而自适应进行的。然而，对于本文考虑的高斯线性回归模型，观测值不影响估计或预测风险，因此离线和自适应设置是等价的。因此，任务是一个特定的集合优化函数（A/V 最优设计），其搜索空间大小为\(\binom{n}{k}\)，在现实场景中无法枚举。虽然精确优化是 NP 困难的（Li,2025 (https://arxiv.org/html/2607.06642#bib.bib9)），但已经开发了近似算法。在本文中，我们专注于贪心算法。

贪心算法从空集开始，反复添加能带来最大即时风险减少的点，直到选择了\(k\)个点。贪心算法不仅在离线设置中是一种实用的选择，更重要的是，它解决了自适应设置中的一个基本问题。在自适应设置中，为了避免规划的计算困难，最常见的贝叶斯主动学习算法（MacKay,1992 (https://arxiv.org/html/2607.06642#bib.bib7)；Gal 等,2017 (https://arxiv.org/html/2607.06642#bib.bib14)；Smith 等,2023 (https://arxiv.org/html/2607.06642#bib.bib15)）依赖于一种近视方法：选择能够最优降低风险的那次观测，就好像这是最后一步一样。“单步最优”与“多步最优”之间的联系是文献中研究很少的一个空白。我们通过分析等价的贪心算法来关注这一联系。令人惊讶的是，关于贪心算法与这个问题的最优策略相比如何，人们知之甚少。

现有的保证（Bian 等,2017 (https://arxiv.org/html/2607.06642#bib.bib18)；Chamon and Ribeiro,2017 (https://arxiv.org/html/2607.06642#bib.bib19)）限定了估计或预测风险的*减少量*（A/V 最优设计）。通过证明风险减少是单调且近似子模的，这些工作表明贪心算法达到了最优*减少量*的恒定比例。然而，对于*减少量*的常数因子近似往往是没有意义的。据我们所知，贪心算法是否对风险本身实现了常数因子近似仍然是个开放问题。

我们通过以下贡献填补了这一空白：
- •常数因子风险保证。我们证明，对于贝叶斯线性回归，倒数风险在 Das and Kempe (2018 (https://arxiv.org/html/2607.06642#bib.bib20)) 的意义上是近似子模的。将此与近似子模下贪心算法的现有分析相结合，得到了贪心算法所实现风险的第一个常数因子近似保证。该常数是依赖于问题的量*最大初始杠杆得分*（MILS）。
- •参数化的困难实例展示了紧性。我们构造了一族问题，在这些问题上，贪心算法的风险被证明比最优风险大一个 MILS 因子，这与我们的上界相匹配。这表明我们保证中的问题相关因子是必要的，而非分析产物。
- •数值模拟。我们使用数值模拟来说明先前已知的界和我们的界，并确认贪心算法在我们的构造中表现不佳。

我们在第2节 (https://arxiv.org/html/2607.06642#S2) 中提供精确的问题陈述，在第3节 (https://arxiv.org/html/2607.06642#S3) 中介绍必要的背景和相关工作，在第4节 (https://arxiv.org/html/2607.06642#S4) 和第5节 (https://arxiv.org/html/2607.06642#S5) 中给出我们的上界和下界，然后在第6节 (https://arxiv.org/html/2607.06642#S6) 中展示一个说明性示例。

## 2 问题陈述

具体来说，我们的问题陈述如下：

###### 问题陈述 1. 给定一组 n 个向量 \(V = \{v_i\}_{i=1}^n \subset \mathbb{R}^d\)，一个正定矩阵 \(\Lambda \in \mathbb{R}^{d \times d}\)，以及一个预算 \(k\)，选择一个大小为 \(|S| = k\) 的集合 \(S \subset [n]\) 来最小化
\[ f(S) := \mathrm{tr}\left( \left( \Lambda + \sum_{i \in S} v_i v_i^\top \right)^{-1} \right) \quad (1) \]

问题参数是整数 \(n\)、\(k\) 和 \(d\)。在我们的分析中，我们展示了另一个依赖于问题的参数的重要性，我们将其称为*最大初始杠杆得分*（MILS），
\[ h_{\text{max}} = \max_{i \in [n]} v_i^\top \Lambda^{-1} v_i. \quad (2) \]
对于由 \(V\)、\(\Lambda\) 和 \(k\) 定义的给定问题，我们将最优解记为
\[ S^\star = \arg\max_{S \subset [n]: |S| = k} f(S) \quad (3) \]

### 2.1 贪心算法

在本文中，我们分析贪心算法，该算法给定一个问题，返回一个集合 \(S_{\text{greedy}}\)。贪心算法从一个初始集合 \(S_0 = \emptyset\) 开始，然后在 \(k\) 次迭代中，选择在添加时能使 \(f\) 最小的元素。参见算法1。

算法1 贪心算法
0: 输入：向量 \(V \in \mathbb{R}^{n \times d}\)，矩阵 \(\Lambda \in \mathbb{R}^{d \times d}\)，预算 \(k \in \mathbb{N}\)
0: 输出：大小为 \(k\) 的选定集合 \(S \subset [n]\)
1: \(S_0 = \emptyset\)
2: 对于迭代 \(t \leftarrow 1\) 到 \(k\) 执行
3:   计算 \(i_t \in \arg\min_{i \notin S_{t-1}} f(S_{t-1} \cup \{i\})\)
4:   设置 \(S_t = S_{t-1} \cup \{i_t\}\)
5: 结束循环
6: 返回 \(S_{\text{greedy}} = S_k\)

注意，在出现平局时存在非确定性。当我们证明贪心算法的结果时，我们要求该定理适用于任何打破平局的选择。对于离线问题，该算法因其简单性和计算效率而具有吸引力。贪心算法的时间复杂度为 \(\mathcal{O}(nk)\)。在线性回归的主动学习中，贪心算法等价于近视算法，因其消除了规划的需要而具有吸引力。

## 3 背景与相关工作

### 3.1 主动学习

主动学习研究存在大量未标记数据和有限标记预算的场景。主动学习算法自适应地选择接下来要标记的点，以获得最佳的测试性能。最近的一些方法研究近视贝叶斯设置（Gal 等,2017 (https://arxiv.org/html/2607.06642#bib.bib14)；Kirsch 等,2019 (https://arxiv.org/html/2607.06642#bib.bib13)；Mussmann 等,2022 (https://arxiv.org/html/2607.06642#bib.bib16)；Smith 等,2023 (https://arxiv.org/html/2607.06642#bib.bib15)），其中下一个点或批量点是通过最小化期望成本（例如损失、熵）来选择的。考虑到规划的计算复杂性，这些方法仅考虑单步后的成本最小化，类似于贪心算法。

### 3.2 贝叶斯线性回归

我们对该设置的动机主要来自贝叶斯线性回归（Bishop,2006 (https://arxiv.org/html/2607.06642#bib.bib5)；Murphy,2023 (https://arxiv.org/html/2607.06642#bib.bib3)）。该模型由先验协方差 \(\Sigma_0\)、观测噪声 \(\sigma^2\) 以及一组固定点 \(X = \{x_i\}_{i=1}^n \subset \mathbb{R}^d\) 定义。那么，模型为
\[ \theta \sim \mathcal{N}(0, \Sigma_0) \quad (4) \]
\[ \epsilon_i \sim \mathcal{N}(0, \sigma^2) \quad (5) \]
\[ y_i = x_i^\top \theta + \epsilon_i \quad (6) \]

一个标准结果是参数后验为 \(\theta | \{(x_i, y_i)\}_{i \in S} \sim \mathcal{N}(\mu_S, \Sigma_S)\)，其中
\[ \Sigma_S = \left( \Sigma_0^{-1} + \sigma^{-2} \sum_{i \in S} x_i x_i^\top \right)^{-1} \quad (7) \]
\[ \mu_S = \sigma^{-2} \Sigma_S \sum_{i \in S} y_i x_i \quad (8) \]

选择 \(S\) 的两个自然准则是：最小化参数 \(\theta\) 的后验方差，或最小化测试点 \(\{\bar{x}_i\}_{i=1}^m\) 上预测的平均方差（Chaloner and Verdinelli,1995 (https://arxiv.org/html/2607.06642#bib.bib1)）。在第一种情况下，
\[ \mathbb{E}_{\theta|S} \left[ \| \theta - \mathbb{E}_{\theta|S} [\theta] \|^2 \right] = \mathrm{tr}(\Sigma_S) \quad (9) \]
在第二种情况下，
\[ \frac{1}{m} \sum_{i=1}^m \mathrm{Var}_{\theta|S} [\theta \cdot \bar{x}_i] = \mathrm{tr} \left( \Sigma_S \frac{1}{m} \sum_{i=1}^m \bar{x}_i \bar{x}_i^\top \right) \quad (10) \]
在这两种情况下，我们都可以将优化准则写成问题陈述1 (https://arxiv.org/html/2607.06642#Thmproblem1) 的形式。对于第一个准则，设 \(\Lambda = \Sigma_0\) 且 \(v_i = \sigma^{-1} x_i\)，那么 \(f(S) = \mathrm{tr}(\sigma_S)\)。对于第二个准则，如果 \(\Sigma_{\bar{X}} = \frac{1}{m} \sum_{i=1}^m \bar{x}_i \bar{x}_i^\top\) 是满秩的，那么设 \(\Lambda = \Sigma_{\bar{X}}^{-1/2} \Sigma_0 \Sigma_{\bar{X}}^{-1/2}\) 且 \(v_i = \sigma^{-1} \Sigma_{\bar{X}}^{-1/2} x_i\)，则 \(f(S) = \mathrm{tr}(\Sigma_S \Sigma_{\bar{X}})\)。值得注意的是，在这种情况下，由于目标值不依赖于观测值 \(y_i\)，而仅取决于是否观测到它，因此自适应性不起作用。因此，该设置中的主动学习等价于集合优化，去除了算法分析的一个复杂性来源。

### 3.3 最优实验设计

最优实验设计是一个经典的统计问题，旨在选择在哪些输入点观测响应，以便最准确地估计参数或进行预测（Kiefer,1959 (https://arxiv.org/html/2607.06642#bib.bib8)；Fedorov,2013 (https://arxiv.org/html/2607.06642#bib.bib4)；Atkinson 等,2007 (https://arxiv.org/html/2607.06642#bib.bib6)）。我们的目标是从候选池 \(X = \{x_1, \dots, x_n\}\) 中选择一组设计