線性時間中的貝葉斯優(yōu)化

Bayesian Optimization in Linear Time

線性時間中的貝葉斯優(yōu)化

https://arxiv.org/pdf/2605.00237

摘要：

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

關(guān)鍵詞：機(jī)器學(xué)習(xí)，全局優(yōu)化，優(yōu)化，隨機(jī)過程，聚類，

1.引言

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

貝葉斯優(yōu)化是應(yīng)對此類挑戰(zhàn)的標(biāo)準(zhǔn)技術(shù)[6, 第1章]。通過使用高斯過程對f進(jìn)行建模，并在選擇下一個觀察f的點(diǎn)x時權(quán)衡探索與利用，貝葉斯優(yōu)化已在各種技術(shù)和工程應(yīng)用中成功最小化了許多此類函數(shù)，例如Google的機(jī)器學(xué)習(xí)模型[7]。

盡管取得了成功，標(biāo)準(zhǔn)貝葉斯優(yōu)化仍存在兩個缺點(diǎn)。首先，如第2節(jié)所述，訓(xùn)練f的模型在收集到的觀測數(shù)量上具有立方級復(fù)雜度，這最終會在計算上變得難以處理。其次，f的優(yōu)化既是一項全局任務(wù)也是一項局部任務(wù)：有必要準(zhǔn)確建模f的全局結(jié)構(gòu)，但僅需達(dá)到能夠定位最小值參數(shù)鄰域的程度即可。在其他區(qū)域，精度只需足以排除進(jìn)一步的最小值即可。為了貝葉斯優(yōu)化的成功，在對f進(jìn)行建模和獲取其連續(xù)觀測值時，恰當(dāng)?shù)仄胶膺@些局部和全局優(yōu)先級是高度可取的。

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

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

2 背景

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

3 貢獻(xiàn)

3.1 分類器的選擇

4 實(shí)證測試

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

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

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

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

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

盡管將原始的約束型 Automotive 測試轉(zhuǎn)換為無約束測試，我們?nèi)匀挥涗浟?DiceOptim 和 TreeBO 在觀測到的最小目標(biāo)函數(shù)值處違反約束的數(shù)量以及違反量的平方和。對于 DiceOptim，違反約束的數(shù)量在 40 到 47 之間，違反量的平方和在 5.91 到 7.98 之間。對于 TreeBO，相應(yīng)的數(shù)值分別為 40 和 47，以及 4.72 和 10.16。

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

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

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

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

5 相關(guān)工作

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

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

[14] 和 [27] 均未公開其代碼，導(dǎo)致無法進(jìn)行比較。因此，在第 4 節(jié)中，我們在各種設(shè)置下（包括低維和高維）將 TreeBO 與標(biāo)準(zhǔn)貝葉斯優(yōu)化庫 DiceOptim [20] 進(jìn)行了比較。

6 結(jié)論

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

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