線性回歸短視貝葉斯主動學習風險的近似比

The Approximation Ratio for the Risk of Myopic Bayesian Active Learning for Linear Regression

線性回歸短視貝葉斯主動學習風險的近似比

https://arxiv.org/pdf/2607.06642

摘要：

主動學習研究一個基本問題：我們應該選擇什么數據來觀察？最優實驗設計中的貪心算法是一種常見的啟發式方法，并且也等價于線性回歸的短視貝葉斯主動學習，這是一種用單步最優選擇代替長期規劃的通用框架。在這項工作中，我們證明了貪心算法風險的同類首個近似比，該近似比在相差一個絕對常數的意義下是緊的。該近似比與最大初始杠桿得分（MILS）呈線性關系，MILS是一個新發現的量，對貪心算法的性能至關重要。最后，我們用簡單的數值模擬來說明這些結果。

1 引言

最優實驗設計和主動學習是在預算約束下選擇信息數據的兩種密切相關的范式。兩者都提出了同一個基本問題：在可以從候選輸入池中進行選擇的自由下，我們應該觀察哪些輸入，以最小化模型參數估計誤差或未來預測誤差？在實驗設計中，選擇通常是離線做出的，而在主動學習中，它們是在觀察到新標簽時自適應地做出的。然而，對于本工作所考慮的模型貝葉斯線性回歸，觀測值不會影響估計或預測風險，因此離線和自適應設置是等價的。因此，該任務是一個特定的集合優化函數（A/V-最優設計），其搜索空間大小為，這排除了在任何現實設置中使用暴力方法的可能性。

雖然精確優化是NP難的[Li, 2025]，但已經開發了近似算法。在這項工作中，我們專注于貪心算法。貪心算法從空集開始，并重復添加能產生最大即時風險減少的點，直到選出k個點。貪心算法不僅是離線設置中的實用選擇，而且更重要的是，它解決了自適應設置中的一個基本問題。在自適應設置中，為了避免規劃的難處理性，最常見的貝葉斯主動學習算法[MacKay, 1992, Gal et al., 2017, Smith et al., 2023]依賴于一種短視方法：選擇能最優地減少風險的觀測，就好像它是最后一步一樣。“單步最優”和“多步最優”之間的聯系是文獻中研究很少的一個空白。我們通過分析等價的貪心算法來關注這一聯系。

關于貪心算法與該問題的最優策略相比如何，令人驚訝地知之甚少。現有的保證[Bian et al., 2017, Chamon and Ribeiro, 2017]對估計或預測風險（A/V-最優設計）的減少量給出了界。通過證明風險減少是單調的且近似次模的，這些工作表明貪心算法達到了最優減少量的一個常數比例。然而，對于減少量的常數因子近似因子通常是空洞的。據我們所知，貪心算法是否對風險本身實現了常數因子近似，仍然是一個未解決的問題。

我們通過以下貢獻填補了這一空白：

• 常數因子風險保證。 我們證明了貝葉斯線性回歸的倒數風險（reciprocal risk）在 Das and Kempe [2018] 的意義下是近似次模的（approximately submodular）。將這一點與現有的關于近似次模性下貪心算法的分析相結合，得出了貪心算法所實現風險的首個常數因子近似保證。該常數是依賴于問題的量——最大初始杠桿得分（MILS）。
• 顯示緊性的參數化難例。 我們構造了一族問題，在這些問題上，貪心算法的風險被證明是最優風險的 MILS 倍（即比最優風險大一個 MILS 因子），這與我們的上界相匹配。這表明我們保證中的問題依賴因子是必要的，而非分析的偽影（artifact）。
• 數值模擬。 我們使用數值模擬來說明之前已知的界以及我們的界，并確認在我們構造的例子中貪心算法的糟糕表現。

我們在第 2 節提供了精確的問題陳述，在第 3 節涵蓋了必要的背景和相關工作，在第 4 節和第 5 節提供了我們的上界和下界，然后在第 6 節展示了一個說明性示例。

2 問題陳述

確切地說，我們的問題陳述如下：

2.1貪婪算法

需要注意的是，在出現并列（ties）的情況下存在非確定性。當我們證明貪心算法的某個結果時，我們要求該定理對任何打破并列（tie-breaking）的選擇都成立。

對于離線問題，該算法因其簡單性和計算效率而具有吸引力。貪心算法的運行時間為。在線性回歸的主動學習中，貪心算法等價于短視（myopic）算法，該算法因其免去了規劃的需要而具有吸引力。

3 背景與相關工作

3.1 主動學習

主動學習研究的是存在大量未標記數據和有限標注預算的場景。主動學習算法為了獲得最佳的測試性能，會自適應地選擇接下來要標注哪些點。幾種最近的方法研究了短視貝葉斯（myopic Bayesian）設置 [Gal et al., 2017, Kirsch et al., 2019, Mussmann et al., 2022, Smith et al., 2023]，其中通過最小化期望成本（例如，損失、熵）來選擇下一個點或一批點。鑒于規劃的計算開銷（原文此處寫作 computational planning of planning，疑似筆誤，意指計算成本或復雜性），這些方法僅最小化單步之后的成本，類似于貪心算法。

3.2 貝葉斯線性回歸

值得注意的是，在這種情況下，由于目標函數值不依賴于觀測值，而僅依賴于其被觀測這一事實，因此自適應性不起作用。因此，該設置下的主動學習等價于集合優化，從而消除了算法分析的一個復雜性來源。

3.3 最優實驗設計

3.4子模性、近似子模性和曲率

3.5 次模性與 A/V-最優設計

據我們所知，應用于 A-最優設計的貪心算法現有的唯一近似保證見于 Bian 等人 [2017] 和 Chamon 與 Ribeiro [2017] 的工作中。在這兩種情況下，分析的對象是減少量（reduction）

4 上界

4.1 近似次模性的緊性

在本節中，我們證明我們要關于 γ γ 的界是緊的，且曲率任意接近 1。注意近似次模性和曲率不依賴于預算 k k，因此我們在以下陳述中省略它們。

4.2 引理 1 的證明

5 下界

我們現在構造一個具體的問題，以表明該上界在常數范圍內是緊的。

6 說明性數值示例

7 討論

本工作的結果不僅為常見的貪心啟發式算法提供了首個 A/V-最優性準則的近似比保證（針對的是風險本身而非風險減少量），而且解決了主動學習中的一個更基本的問題。幾乎所有的主動學習算法都通過僅關注當前的數據標注迭代，從而避免了跨越多個數據標注迭代的規劃。據我們所知，目前尚無針對短視算法的測試損失近似比的現有保證。在此，對于貝葉斯邏輯回歸，[結果表明] 短視數據標注幾乎與完全規劃的數據標注相匹配，至少當 MILS（最大初始杠桿得分）較小時是這樣。我們希望這項工作能為未來對其他模型的分析奠定基礎，特別是那些自適應選擇不等價于離線選擇的模型。

原文鏈接： https://arxiv.org/pdf/2607.06642