Combinatorial Bayesian Optimization using the Graph Cartesian Product

1.摘要

通常來(lái)說(shuō)，在貝葉斯優(yōu)化中的改進(jìn)有三方面：1.代理模型（高斯過(guò)程，神經(jīng)網(wǎng)絡(luò)集） 2.獲取函數(shù) 3.獲取函數(shù)的優(yōu)化（尤其是在離散問(wèn)題中）。
本文的創(chuàng)新的地方在第1步。

本文主要研究了由有序變量或分類變量組成的組合搜索空間上的目標(biāo)的貝葉斯優(yōu)化(BO)。介紹了一種新的使用高斯過(guò)程(GP)的貝葉斯優(yōu)化COMBO。它利用組合圖來(lái)量化組合搜索空間上的目標(biāo)函數(shù)的“平滑性”。組合圖的頂點(diǎn)集由變量的所有可能的組合組成，而邊是使用代表單個(gè)變量的子圖的圖笛卡爾積構(gòu)造的。在這個(gè)組合圖上，提出了一個(gè)ARD擴(kuò)散核，其中GP能夠建模變量之間的高階交互作用，從而獲得更好的性能。此外，利用Horseshoe先驗(yàn)在ARD擴(kuò)散核中的尺度參數(shù)，得到了一個(gè)有效的變量選擇過(guò)程，使組合適用于高維問(wèn)題。
總結(jié)本文的貢獻(xiàn)如下：
1.提出了COMBO,該算法利用組合圖來(lái)衡量待優(yōu)化函數(shù)的光滑性,組合圖的頂點(diǎn)集由所有可能的變量的聯(lián)合賦值組成,而邊是使用代表單個(gè)變量的子圖的圖的笛卡爾積來(lái)構(gòu)造的.
2.基于該圖,提出了ARD擴(kuò)散核函數(shù),這使得GP能夠建模變量之間的高階相互作用
3.時(shí)間復(fù)雜度上,該算法可以通過(guò)Horseshoe prior線性增加,避免時(shí)間指數(shù)增加.

2.介紹

本文主要研究了由有序變量或分類變量組成的組合搜索空間上的目標(biāo)的貝葉斯優(yōu)化(BO)。組合BO有許多應(yīng)用，包括尋找最優(yōu)的芯片組配置，發(fā)現(xiàn)深度神經(jīng)網(wǎng)絡(luò)的最優(yōu)體系結(jié)構(gòu)，或優(yōu)化編譯器，以將軟件最優(yōu)地嵌入到硬件上。所有這些組合BO問(wèn)題可能有用的應(yīng)用程序都具有以下特性。1.不能使用基于梯度的優(yōu)化器的黑盒目標(biāo)函數(shù)2.有昂貴的評(píng)估程序，即不能使用基于進(jìn)化或遺傳的算法3.存在評(píng)估時(shí)有噪聲和高度非線性的目標(biāo)函數(shù)。
有趣的是，文獻(xiàn)中大多數(shù)BO方法關(guān)注的是連續(xù)的，而不是組合搜索空間。其中之一是最成功的BO方法是建立在高斯過(guò)程(GPs)之上的。由于GP依賴于內(nèi)核定義的平滑度來(lái)建模不確定性，它們最初是被提出的，并且主要用于連續(xù)輸入空間。盡管在組合結(jié)構(gòu)上提出了內(nèi)核，迄今為止，圖信號(hào)的平滑度與組合結(jié)構(gòu)上定義的函數(shù)的平滑度之間的關(guān)系一直被忽略，也沒(méi)有被利用于組合結(jié)構(gòu)上的BO。一個(gè)簡(jiǎn)單的解決方案是使用連續(xù)的內(nèi)核并將它們包圍起來(lái)。然而，在下一輪優(yōu)化的時(shí)候，這個(gè)信息不能在下一輪計(jì)算協(xié)方差的時(shí)候使用。
此外，當(dāng)考慮組合搜索空間時(shí)，可能的配置的數(shù)量迅速爆炸：對(duì)于具有k個(gè)類別的M個(gè)分類變量，可能的組合的數(shù)量與$O(k^M)$相當(dāng)。因此，在組合空間上應(yīng)用BO和全科醫(yī)生并不簡(jiǎn)單
我們提出了組合，一種新的組合BO，旨在解決上述在組合結(jié)構(gòu)上缺乏平滑性和計(jì)算復(fù)雜度的問(wèn)題。為了引入組合結(jié)構(gòu)上的函數(shù)的光滑性，我們提出了組合圖。組合圖由每個(gè)分類（或順序）變量一個(gè)的子圖組成，然后由圖笛卡爾積組合。該組合圖包含了所有可能的組合選擇作為頂點(diǎn)。我們使用圖傅里葉變換(GFT)將組合結(jié)構(gòu)上的函數(shù)的平滑性定義為圖信號(hào)的平滑性.
具體來(lái)說(shuō)，我們提出了圖上擴(kuò)散核(BOCS提出)的一種變體，即自動(dòng)相關(guān)性確定(ARD)擴(kuò)散核作為我們的GP核，其計(jì)算GFT是可以通過(guò)特征系統(tǒng)的分解來(lái)計(jì)算處理的。使用圖上的GP，組合解釋了變量之間的任意高階交互作用。此外，在ARD參數(shù)組合上使用稀疏誘導(dǎo)Horseshoe先驗(yàn)[6]進(jìn)行變量選擇并擴(kuò)展到高維。組合允許在組合搜索空間上實(shí)現(xiàn)精確、高效和大規(guī)模的BO。
作者原文創(chuàng)新點(diǎn)介紹：
First, we show how to introduce smoothness on combinatorial search spaces by introducing combinatorial graphs. On top of a combinatorial graph we define a kernel using the GFT. Second, we present an algorithm for Combinatorial BO that is computationally scalable to high dimensional problems. Third, we introduce individual scale parameters for each variable making the diffusion kernel more flexible. When adopting a sparsity inducing Horseshoe prior, COMBO performs variable selection which makes it scalable to high dimensional problems.

3.算法

作者認(rèn)為：為了在組合結(jié)構(gòu)上設(shè)計(jì)一種有效的基于GP的BO算法，需要一個(gè)由GP定義的光滑函數(shù)空間。
算法的總體框架如下：

未完待續(xù)

4.總結(jié)

據(jù)我們所知，COMBO是第一個(gè)使用適合于變量之間高階復(fù)雜的交互問(wèn)題的高斯過(guò)程作為代理模型的貝葉斯優(yōu)化算法。COMBO是一個(gè)統(tǒng)計(jì)和計(jì)算可擴(kuò)展的組合空間貝葉斯優(yōu)化工具，這是一個(gè)尚未被廣泛探索的領(lǐng)域。

返回貝葉斯優(yōu)化優(yōu)秀論文總結(jié)目錄

總結(jié)

以上是生活随笔為你收集整理的利用图笛卡斯积的组合贝叶斯优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。