線性時間中的貝葉斯優化

Bayesian Optimization in Linear Time

線性時間中的貝葉斯優化

https://arxiv.org/pdf/2605.00237

摘要：

貝葉斯優化是一種用于最小化目標函數的序列方法，此類目標函數評估代價高昂，且關于其幾乎無法做出假設。通過利用所有已收集的數據訓練該函數的高斯過程模型，并自適應地采用全局探索與局部利用的混合策略，該方法已被應用于包括機器學習、汽車工程和強化學習在內的諸多領域的優化問題中。然而，標準方法存在兩個問題：1）其計算復雜度隨訓練集規模呈立方增長，最終導致模型訓練在計算上不可行；2）鑒于最小化過程的局部特性，對目標函數進行全局建模未必是最優選擇。通過對搜索空間進行靈活且遞歸的二分劃分，我們調整了標準貝葉斯優化的建模與采集方面，使其與劃分方案協同工作，從而改善了上述兩個標準缺陷。我們在七個具有挑戰性的測試函數（維度范圍為6至124）上，將本方法與一個常用的貝葉斯優化庫進行了對比，結果表明本方法在所有測試中均取得了更優的優化性能。此外，本方法具有線性的計算復雜度。

關鍵詞：機器學習，全局優化，優化，隨機過程，聚類，

1.引言

許多優化問題涉及不透明且難以評估的目標函數。此類"黑箱"問題出現在機器學習中的超參數調優[26]、汽車懸架部件設計[25]以及強化學習中的策略優化[30]等場景中。為了在函數f的d維定義域上最小化該函數，如果除了函數的定義域之外幾乎無法做出任何假設，那么假設目標函數具有凸性或可微性等性質的標準優化技術可能不適用。此時，優化必須基于對f的性質及其在選定輸入配置處評估值的靈活建模假設來進行。如果f的計算成本此外還很高昂，那么評估的預算就會受到限制，可能僅在幾百次以內。

貝葉斯優化是應對此類挑戰的標準技術[6, 第1章]。通過使用高斯過程對f進行建模，并在選擇下一個觀察f的點x時權衡探索與利用，貝葉斯優化已在各種技術和工程應用中成功最小化了許多此類函數，例如Google的機器學習模型[7]。

盡管取得了成功，標準貝葉斯優化仍存在兩個缺點。首先，如第2節所述，訓練f的模型在收集到的觀測數量上具有立方級復雜度，這最終會在計算上變得難以處理。其次，f的優化既是一項全局任務也是一項局部任務：有必要準確建模f的全局結構，但僅需達到能夠定位最小值參數鄰域的程度即可。在其他區域，精度只需足以排除進一步的最小值即可。為了貝葉斯優化的成功，在對f進行建模和獲取其連續觀測值時，恰當地平衡這些局部和全局優先級是高度可取的。

我們在第3節中通過幾種方法協同解決這些缺點。使用聚類和靈活的二元分類，我們遞歸地劃分f的定義域。作為說明，圖1(a)展示了d=2時的Rastrigin測試函數（d=6將在第4節中考慮），圖1(b)展示了基于收集到的數據進行的劃分。該遞歸過程創建了一個如圖2所示的二叉樹，其節點代表定義域的子區域。每個節點都獲得自己使用從整個數據集中特別選擇的子集創建的f的模型。接下來，我們修改f的建模以及后續觀測值的獲取，使其與搜索空間的劃分協調工作。這些方法共同改善了貝葉斯優化的局部和全局建模方面的平衡，并解決了標準方法的兩個缺點。更新f模型的計算復雜度從立方級降低到常數級，因為用于擬合節點模型的觀測數量有一個硬性上限。此外，整體優化的復雜度從立方級降低到線性級。這導致對于特別苛刻的優化問題，運行時間顯著減少。除了運行更快之外，與標準方法相比，改進的局部-全局建模平衡還提高了優化性能，有時提升幅度很大。

我們在第4節中通過將我們的方法（命名為TreeBO）與標準貝葉斯優化庫DiceOptim[20]在一組多樣化的七個測試函數上進行比較，從而實證驗證這些主張，其中包括一個源自汽車質量最小化問題的高維測試。這些測試的維度范圍從6到124，每個測試都在受控的初始條件下重復多次。結果表明，TreeBO在所有七個測試中都實現了更優的優化性能，同時在最長、維度最高的測試上運行時間大幅減少。與第5節中描述的替代劃分方法相比，TreeBO更簡單且更易于調整，與標準貝葉斯優化相比僅多了一個可調整的超參數。此外，這個額外的超參數無需特殊調整即可實現我們的結果。我們在第6節中總結我們的工作，并討論尚未解決的問題和未來研究的前景。

2 背景

在計算上，使用多種技術來優化 ? 和 α ，包括擬牛頓法（如 L-BFGS-B）和遺傳算法 [20,22]。貝葉斯優化常用的軟件庫選擇是 R 包 DiceOptim [20, 21]。貝葉斯優化作為重復三元組動作的現代起源始于 Jones 等人 [11]。關于貝葉斯優化歷史發展的描述，參見 [6, Ch. 12]。

3 貢獻

3.1 分類器的選擇

4 實證測試

第 1 節的核心主張是，TreeBO 改善了標準貝葉斯優化的計算難處理性（computational intractability），并改進了對 f f 建模的局部 - 全局平衡，與標準方法相比減少了運行時間并提高了性能。為了證明這些主張，我們將 TreeBO 與貝葉斯優化 R 語言庫 DiceOptim [20] 在一組多樣化的 7 個中維和高維測試函數上進行了比較。Ackley、Hartmann、Levy、Michalewicz、Rastrigin 和 Schwefel 函數來自仿真實驗虛擬庫（Virtual Library of Simulation Experiments）[23]，而第七個高維測試源自通用汽車（General Motors）[10] 的一個汽車質量最小化問題。后者通俗地被稱為 MOPTA08 Jones 基準 [9, 10]；我們將其稱為 Automotive（汽車）問題。我們在本節中描述的有利結果并非從更大規模的測試集中刻意挑選出來的。

這些函數為任何優化方法提供了一系列廣泛的挑戰：有些是可加的（Michalewicz, Rastrigin, Schwefel），有些是非可加的（Ackley, Hartmann, Levy），有些是高度振蕩和多模態的（Michalewicz, Rastrigin, Schwefel），有些在其大部分定義域上具有高度誤導性（Ackley），大多數是非常非線性的，且有些函數的特性（Hartmann 和 Automotive）足夠晦澀以至于如同黑盒。

除 Automotive（汽車）問題僅進行了 10 次重復（因其耗時較長）外，所有測試均進行了 100 次重復。在不同起始函數評估集上進行多次重復，確保了我們獲得的有利結果并非源于少量刻意選擇的起始點。每次重復都是配對的，TreeBO 和 DiceOptim 均從相同的 n init ninit 個初始點和隨機種子開始。除 Schwefel 函數外，所有測試均使用冪指數核（power-exponential kernel）；出于數值原因，后者使用了 Matérn 核。計算工作在西蒙弗雷澤大學（Simon Fraser University）的 Cedar 和 Fir 集群以及不列顛哥倫比亞大學（University of British Columbia）的 Sockeye 集群上進行。每種方法、每次重復均使用 1 個 CPU 核心和 4 GB 內存。

由于 DiceOptim 是一個 R 語言包，TreeBO 也使用 R 語言 [21] 編寫。這使我們能夠使用完全相同的方法和設置來為兩種方法擬合 GP 模型，從而促進對比。DiceOptim 使用遺傳優化（結合擬牛頓步）來最大化采集函數 [17]。TreeBO 最初也遵循此做法，但在經過大量測試后，我們發現對采集函數使用粒子群優化（同樣結合擬牛頓步）能改善對目標函數的優化效果 [2]。我們對后者的實現進行了修改，以接受定制的起始點，如第 3 節和算法 4 所述。在將 DiceOptim 與 Python 庫 BoTorch [1] 進行比較后，我們發現后者缺乏競爭力，因此未再進一步探究。

除 Automotive（汽車）問題使用 MATLAB [24] 編寫外，所有測試函數均使用 R 語言 [21] 編寫。為了將 DiceOptim 和 TreeBO 作為 R 程序運行，同時將 Automotive 作為 MATLAB 程序進行評估，我們編寫了一個簡單的系統級接口，用于在 R 與 MATLAB 之間傳遞信息。

盡管將原始的約束型 Automotive 測試轉換為無約束測試，我們仍然記錄了 DiceOptim 和 TreeBO 在觀測到的最小目標函數值處違反約束的數量以及違反量的平方和。對于 DiceOptim，違反約束的數量在 40 到 47 之間，違反量的平方和在 5.91 到 7.98 之間。對于 TreeBO，相應的數值分別為 40 和 47，以及 4.72 和 10.16。

為了在平均值之外進一步證實我們在第 1 節中的主張，我們提供了在優化過程中幾個時間點上所有重復實驗中觀測到的最小目標函數值的并排箱線圖分布證據。這在圖 3 中針對 Ackley 測試展示，在圖 4 中針對 Automotive 測試展示。所有測試的圖表均在補充材料的 E 節中。這些圖表的 x 軸從 0 個后續觀測開始，此時兩種方法在任何重復實驗中都以相同的次評估開始，因此 0 個后續觀測處的箱線圖是相同的。

對于圖 3 中的 Ackley 測試，從 0 到 75 個后續觀測，TreeBO 的性能與 DiceOptim 相當。然而，在 100 個后續觀測（總共 160 個觀測）之后，與 DiceOptim 相比，TreeBO 的中位數和第 75 百分位數已顯著下降，而到 140 個后續觀測（總共 200 個觀測）時，TreeBO 的箱線圖在 0 附近壓縮得如此緊密，以至于幾乎不可見。相比之下，DiceOptim 的第 75 百分位數約為 8。我們將這一改進歸因于 TreeBO 的二元劃分在搜索原點附近快速下降區域時促進了探索與利用之間更好的平衡。（關于 Ackley 函數的曲面圖，參見 https://www.sfu.ca/~ssurjano/ackley.html。）Ackley 函數在其大部分定義域上相對平坦，因此 DiceOptim 的單一全局 GP 模型和采集函數優化可能難以定位原點附近的有希望區域。相比之下，TreeBO 為定義域的不同子區域擬合獨立的 GP 模型，因此可能通過不同的 GP 模型獲得對定義域的多個視角，從而增加找到全局最小值的機會。

對于高維的 Automotive（汽車）測試，作為一個黑盒，我們無法推測 DiceOptim 和 TreeBO 在方法上有何不同。然而，我們再次看到，在隨后的 300 次觀測（總共 425 次觀測）中，TreeBO 的表現比 DiceOptim 差，在此之后 TreeBO 相對有所改進，以至于在隨后的 475 次觀測（總共 600 次觀測）后，TreeBO 的第 75 百分位數低于 DiceOptim 的第 25 百分位數。

Michalewicz、Rastrigin 和 Hartmann 測試的圖表顯示出類似的趨勢：TreeBO 最初的表現不如 DiceOptim，但最終會超越后者。作為我們在第 6 節討論 TreeBO 潛在缺點的一部分，我們將討論這一現象對 TreeBO 可能產生的影響。

5 相關工作

其次，Li 等人 [14] 在每次迭代時從頭開始重構他們的樹，并根據優化過程的近期表現調整深度。如果觀測到的 f f的最小值近期一直在下降，則降低樹深度以促進探索。反之，如果它沒有下降，則增加樹深度以促進利用。這需要一個關于最大樹深度的參數。我們的方法從不重建二叉樹，從而避免了額外的參數。

第三，為了選擇節點，[14] 和 [27] 都使用置信上界（UCB）技術，這些技術源自多臂老虎機，并且需要一個參數來控制探索與利用的權衡。Li 等人 [14] 將其作為輸入來計算每個葉節點的“劃分得分”，這需要將一個依賴于參數的 softmax 函數應用于 UCB 得分。相比之下，TreeBO 在節點選擇上不需要額外的參數，僅優化每個節點的采集函數，然后選擇具有最高該值的節點。

[14] 和 [27] 均未公開其代碼，導致無法進行比較。因此，在第 4 節中，我們在各種設置下（包括低維和高維）將 TreeBO 與標準貝葉斯優化庫 DiceOptim [20] 進行了比較。

6 結論

標準形式的貝葉斯優化是一種有效且廣泛使用的技術，用于最小化那些知之甚少且評估代價高昂的目標函數 f 。其計算局限性在于，更新 f 的 GP（高斯過程）模型在收集到的觀測數量上具有立方級復雜度，這最終導致該方法變得難以處理。此外，貝葉斯優化需要在建模 f 時平衡局部和全局的優先級，而其擬合單一全局模型的方法未必是最優的。TreeBO 通過對 f 的定義域進行靈活、遞歸的二元劃分來解決這些缺點，創建了一個二叉樹，其葉節點代表了用于獲取下一次觀測的候選子區域。由于任何葉節點中的觀測數量都有限制，擬合 f 模型所需的計算量最終變為常數，這改善了標準貝葉斯優化的第一個缺點。此外，每個葉節點都有自己的模型，這提供了對目標函數的多個視角，并改善了建模 f 時的局部 - 全局平衡，從而改善了第二個缺點。這些優勢通過在七個具有不同特征的困難測試（包括一個高維、黑盒的汽車質量最小化問題）上進行的數百次運行中，TreeBO 與 DiceOptim 的配對比較得到了證明，在所有這些測試中 TreeBO 均優于 DiceOptim。

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