Bayesian Optimization in Linear Time

線(xiàn)性時(shí)間中的貝葉斯優(yōu)化

https://arxiv.org/pdf/2605.00237

摘要：

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

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

1.引言

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

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

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

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

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

2 背景

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

3 貢獻(xiàn)

3.1 分類(lèi)器的選擇

4 實(shí)證測(cè)試

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

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

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

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

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

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

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

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

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

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

5 相關(guān)工作

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

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

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

6 結(jié)論

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

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