深度算法預(yù)測(cè)模型的數(shù)據(jù)優(yōu)化*

程勁松

（南京航空航天大學(xué) 南京 211106）

1 引言

長久以來，對(duì)于某一類需要深入研究的計(jì)算問題，比如經(jīng)典的決策問題中的P 與NP 問題，人們總是嘗試開發(fā)更高效的求解算法。隨著研究的不斷深入，這些領(lǐng)域或多或少已經(jīng)積累了大量各式各樣的求解算法。然而，在面對(duì)不同的問題實(shí)例時(shí)，沒有哪一種算法可以始終優(yōu)于其他算法。這種現(xiàn)象被稱為算法性能互補(bǔ)，即不同的算法在不同的問題實(shí)例上都能取得最佳的性能表現(xiàn)。絕大多數(shù)的NP決策問題或優(yōu)化問題上都有算法性能互補(bǔ)［1～4］的身影，其中就包括布爾邏輯可滿足性問（Boolean Satisfiability Problem，SAT），約束滿足問題和旅行商問題等，以及近些年來熱門的機(jī)器學(xué)習(xí)領(lǐng)域。這些類型的問題目前不存在一套完整的可以指導(dǎo)如何選取求解算法的理論，即使存在，它也僅存在于少數(shù)特殊的問題類別中，并不能適用于更為普遍的情況。

在這種環(huán)境下，算法預(yù)測(cè)（Algorithm Selection）［5～6］問題逐漸受到人們的重視。給定一個(gè)計(jì)算問題、一組可能解決該問題的算法以及一個(gè)待解決的特定的問題實(shí)例，如何確定哪些算法可以在該問題實(shí)例上取得足夠優(yōu)秀甚至最佳的性能是算法預(yù)測(cè)的目標(biāo)。自從Rice［5］首次系統(tǒng)地提出這個(gè)問題，單實(shí)例算法預(yù)測(cè)問題以及相關(guān)的算法就一直吸引著人們的目光，現(xiàn)如今已開發(fā)出眾多優(yōu)秀的算法預(yù)測(cè)系統(tǒng)，例如SATzilla［7～8］，CSHC［9］和ALORS［10］等。后來，Loreggia［11］將深度學(xué)習(xí)［12］應(yīng)用在算法預(yù)測(cè)任務(wù)上，首次實(shí)現(xiàn)了數(shù)據(jù)集特征的自動(dòng)提取。盡管如此，目前關(guān)于深度學(xué)習(xí)在算法預(yù)測(cè)問題上的應(yīng)用依然存在著很多的局限性。該方法最大的問題就是深度學(xué)習(xí)根深蒂固的老問題，即數(shù)據(jù)集的數(shù)量與質(zhì)量對(duì)于訓(xùn)練強(qiáng)大的深度模型至關(guān)重要。因此，本文就從數(shù)據(jù)優(yōu)化層面評(píng)估深度模型在算法預(yù)測(cè)任務(wù)上的學(xué)習(xí)能力。

2 背景

本文關(guān)注的問題領(lǐng)域是SAT，它是計(jì)算機(jī)歷史上第一個(gè)被證明為NP-Complete 的決策問題，它的原始結(jié)構(gòu)文本示例如下所示。

在上例中，以字母“c”的一行表明該行為注釋。以“p”開頭的一行作為該問題實(shí)例的一個(gè)簡(jiǎn)單聲明，其中后面的兩位數(shù)字分別聲明了該問題實(shí)例有多少邏輯變量和簡(jiǎn)單析取式，剩余的只包含數(shù)字和負(fù)號(hào)的行都是真正有效的語句（簡(jiǎn)單析取式），其中以空格為間隔的數(shù)字（包括帶符號(hào)的數(shù)字）都是問題邏輯變量的表示，末尾的“0”則是例外，它只是一個(gè)結(jié)尾占位符，沒有任何邏輯意義。從數(shù)學(xué)的角度來看，比如第三行的數(shù)字1和-2分別表示邏輯變量“1”和邏輯變量“2”的逆。每個(gè)邏輯變量都可以取真值或假值，每一行中邏輯變量一起組成了一個(gè)簡(jiǎn)單析取式，而所有的語句組合在一起則構(gòu)成了一個(gè)合取范式。SAT 問題的目標(biāo)就是找出一組所有邏輯變量的具體的真假賦值使得它為真。

算法預(yù)測(cè)問題都有兩個(gè)基礎(chǔ)的預(yù)測(cè)模型，即虛擬最佳求解器（Virtual Best Selector，VBS）和單個(gè)算法預(yù)測(cè)器（Single Best Selector，SBS）。VBS 是一個(gè)虛擬的理想的預(yù)測(cè)器，它總是能為每個(gè)問題實(shí)例選擇當(dāng)前算法組合中最佳的算法，它相當(dāng)于預(yù)測(cè)性能的上限，而SBS 只會(huì)輸出一個(gè)算法，該算法可以在問題實(shí)例集上取得總體最好的性能，也就是說這是單個(gè)算法能夠達(dá)到的全局最佳性能。

最著名的SAT問題的算法預(yù)測(cè)器是SATzilla［7～8］，自從第一次在SAT競(jìng)賽中取得亮眼的成績之后，之后的多年該模型一直在不斷的發(fā)展，并且在實(shí)踐生產(chǎn)中也得到了應(yīng)用。近些年來，其他一些優(yōu)秀的預(yù)測(cè)模型比如CSHC［9］和ALORS［5］漸漸地涌現(xiàn)出來。無論這些模型的性能如何優(yōu)秀，用于構(gòu)建模型的特征一直需要問題專家的精心設(shè)計(jì)，從而生成可以區(qū)別SAT 問題實(shí)例的特征模式。這些用于訓(xùn)練模型的特征不可避免地包含著人類的主觀性和片面性，它的生成成本也是不可忽略的存在。

隨著深度學(xué)習(xí)的崛起，它也被用于SAT算法預(yù)測(cè)器的構(gòu)建［11］，特別是其問題實(shí)例特征的自動(dòng)化。由于原生SAT 問題實(shí)例的表示不能直接適用于深度模型，因此該方法還提出了一個(gè)基于圖像的中間實(shí)例。相比于當(dāng)時(shí)最好的預(yù)測(cè)模型，該模型預(yù)測(cè)性能還是可以達(dá)到不錯(cuò)的性能表型。該預(yù)測(cè)器主要利用了CNN［13～14］架構(gòu)，一般來說，基于監(jiān)督學(xué)習(xí)方式的CNN 模型都非常依賴于數(shù)據(jù)樣本的質(zhì)量和樣本標(biāo)簽的分布。與眾不同的是，算法預(yù)測(cè)領(lǐng)域的數(shù)據(jù)集并不是一成不變的，這就導(dǎo)致深度預(yù)測(cè)模型的性能會(huì)受到影響。因此，本文主要研究深度模型在算法預(yù)測(cè)數(shù)據(jù)集上的學(xué)習(xí)能力。

3 數(shù)據(jù)優(yōu)化

3.1 數(shù)據(jù)集擴(kuò)展

為了能夠使用深度學(xué)習(xí)模型，Loreggia［11］還引入一種問題實(shí)例格式轉(zhuǎn)換，它的主要思想是逐個(gè)字符地將SAT 問題實(shí)例中主要的文本（包括數(shù)字，字母，空格和換行符）轉(zhuǎn)換成ASCII 碼然后下采樣成指定大小的圖像，所有除注釋和聲明行的有效簡(jiǎn)單析取式都參與了這個(gè)的轉(zhuǎn)換過程，一些不重要的SAT 實(shí)例文件內(nèi)容在轉(zhuǎn)換過程中也被移除了，如末尾的占位符號(hào)0。對(duì)于上述原始SAT 問題示例，三行有效的內(nèi)容得到的ASCII 代碼為49，45，50，48，10，49，51，53，48，10，51，45，55，57，48。此外，由于實(shí)例文件中使用的字符個(gè)數(shù)的限制導(dǎo)致生成的像素值都集中在一個(gè)比較小的區(qū)間內(nèi)，于是額外添加了一個(gè)從[10，57] 到[0，255]的簡(jiǎn)單映射來擴(kuò)展像素值。最終生成的圖像對(duì)于人來說，直觀的反映是一個(gè)幾乎沒有規(guī)律的灰度圖像。

在訓(xùn)練深度模型時(shí)，人們總是期望可以有更多的數(shù)據(jù)來優(yōu)化的深度預(yù)測(cè)模型。但是，由于算法預(yù)測(cè)中問題域的特殊性，很難收集足夠多的數(shù)據(jù)以生成強(qiáng)大的深度學(xué)習(xí)模型。SAT 問題的本質(zhì)是邏輯變量之間的析取與合取，然而最終的合取范式的取值并不受邏輯變量或者簡(jiǎn)單析取式之間的位置影響［15］。比如簡(jiǎn)單析取式1 ∨2 ∨3 與3 ∨1 ∨2 在邏輯上是等價(jià)的，因此在原始的問題實(shí)例內(nèi)容轉(zhuǎn)換成ASCII 碼時(shí)，邏輯變量的順序信息也被編碼而加入了圖像的信息?？偟貋碚f，邏輯變量之間以及簡(jiǎn)單析取式之間順序的是可交換的，每個(gè)原始SAT問題實(shí)例在理論上都可以任意排列和組合這些關(guān)鍵信息，從而可以生成幾乎無限的圖像格式數(shù)據(jù)。

3.2 算法標(biāo)簽優(yōu)化

對(duì)于NP 問題的算法，必須提前給定一個(gè)運(yùn)行時(shí)間的閾值（截止時(shí)間，cut-off time），所以在截止時(shí)間內(nèi)結(jié)束計(jì)算并得出解的算法就是可用的目標(biāo)算法。因此，截止時(shí)間的預(yù)設(shè)則顯得至關(guān)重要，由截止時(shí)間的設(shè)置引起的算法標(biāo)簽分布的變化會(huì)隱式地影響深度學(xué)習(xí)這類監(jiān)督學(xué)習(xí)的模型。

與其他常用的分類任務(wù)數(shù)據(jù)集相比，算法預(yù)測(cè)任務(wù)的數(shù)據(jù)集普遍存在算法標(biāo)簽不固定的情況（此后的標(biāo)簽就是指算法組合中的算法，不同的實(shí)例有不一樣的可用的標(biāo)簽/算法）。例如，經(jīng)典MNIST 手寫數(shù)字?jǐn)?shù)據(jù)集的每個(gè)圖像有且僅有一個(gè)標(biāo)簽，即每張圖像都與一個(gè)單獨(dú)的數(shù)字相關(guān)聯(lián)。然而，在算法預(yù)測(cè)相關(guān)的數(shù)據(jù)集中，一個(gè)問題實(shí)例往往可以被多個(gè)算法在指定的時(shí)限內(nèi)完成求解，從而導(dǎo)致大多數(shù)問題實(shí)例都會(huì)對(duì)應(yīng)于多個(gè)算法標(biāo)簽。如前文所述，基于CNN 的算法預(yù)測(cè)研究采用的方法就是這樣的分類思想。盡管它也取得了可接受的結(jié)果，從問題解決的角度來看，例如，如果基于CNN 的算法預(yù)測(cè)系統(tǒng)為某個(gè)實(shí)例選擇了排名第五的算法，則至少有五種算法可以解決該問題實(shí)例，則問題解決是成功的。但是，從學(xué)習(xí)算法的角度來看，這樣的預(yù)測(cè)表明該模型并沒有在數(shù)據(jù)集上取得最好的擬合效果，因?yàn)樗c最優(yōu)的算法還是很遠(yuǎn)的距離。因此，算法預(yù)測(cè)任務(wù)在建模時(shí)需要盡可能保留原始數(shù)據(jù)格式里的潛在信息，比如用改變標(biāo)記策略后的新的算法標(biāo)簽分布作為訓(xùn)練集。為了更合理并簡(jiǎn)單地區(qū)分這些標(biāo)簽分布，原始論文中的標(biāo)簽被稱為一般二元標(biāo)簽，其中值1 表示問題實(shí)例可以通過特定算法來解決，即運(yùn)行時(shí)間比預(yù)設(shè)時(shí)限更短，反之則為0。此外，由于原始的運(yùn)行時(shí)間數(shù)據(jù)不太適合直接在神經(jīng)網(wǎng)絡(luò)中操作，同時(shí)為了與一般二元標(biāo)簽對(duì)齊，原來的運(yùn)行時(shí)間可以通過一個(gè)映射g(t，T)=(T-t)/T，被壓縮成[0，1]。其中，T表示預(yù)設(shè)的截止時(shí)間，t是算法的真實(shí)運(yùn)行時(shí)間，1 和0 與二元標(biāo)簽具有相同的意義，但是它們之間的值與1 有著相同的意義，即也可以解決問題實(shí)例，只是它們的性能有所不同。這種標(biāo)簽在文中被稱為一般連續(xù)標(biāo)簽，它本質(zhì)上是標(biāo)準(zhǔn)化后的運(yùn)行時(shí)間。

如果能夠?yàn)樗械乃惴▎为?dú)確定一個(gè)截止時(shí)間，因此生成的問題實(shí)例算法標(biāo)簽的分布則會(huì)與原來的標(biāo)簽分布完全不同。為了研究這種意義上標(biāo)簽分布，本文提出了另一種標(biāo)簽選項(xiàng)，即獨(dú)立自適應(yīng)標(biāo)簽。具體的實(shí)現(xiàn)方式利用了層次聚類算法（Agglomerative Hierarchical Clustering）［16～17］，獨(dú)立地對(duì)每一個(gè)算法在訓(xùn)練問題實(shí)例上的性能進(jìn)行聚類，得到類間距離最遠(yuǎn)的兩個(gè)簇：一個(gè)表示當(dāng)前算法能夠解決的問題實(shí)例，另一個(gè)表示余下的“不能被解決”的問題實(shí)例。當(dāng)然，這個(gè)“不能被解決”只是表示該問題實(shí)例不能在截止時(shí)間內(nèi)被特定的算法解決。這個(gè)聚類結(jié)果可以導(dǎo)出獨(dú)立自適應(yīng)二元標(biāo)簽，對(duì)于它的連續(xù)版本，則需要根據(jù)兩個(gè)簇之間的邊界或相交點(diǎn)的時(shí)間作為各自新的截止時(shí)間，然后按照一般連續(xù)標(biāo)簽的計(jì)算方法，生成新的獨(dú)立自適應(yīng)連續(xù)標(biāo)簽。

4 具體實(shí)驗(yàn)

本文中所使用的基本CNN模型來自Loreggia［11］在其論文中使用的深度模型，如圖1 所示。由于原始數(shù)據(jù)集沒有公開，所以直接采用了一個(gè)開源的ASLib［18］數(shù)據(jù)庫，其中包含大量的各式各樣的數(shù)據(jù)集。本文選取了其中的三個(gè)數(shù)據(jù)集SAT12ALL，SAT12INDU 和SAT0316INDU［19］，它們?cè)嫉臉颖緮?shù)量分別為1614、1167、2000。此外，SAT12ALL 與SAT12INDU 都有包含31 個(gè)算法的算法組合，截止時(shí)間都為$1200$，而SAT0316INDU只有10個(gè)算法，算法的截止時(shí)間為5000。為了消除實(shí)驗(yàn)中的隨機(jī)性，每個(gè)實(shí)驗(yàn)都會(huì)重復(fù)運(yùn)行3次，并且使用5折交叉驗(yàn)證，其中訓(xùn)練集、驗(yàn)證集和測(cè)試集的比例為3∶1∶1。實(shí)驗(yàn)中，對(duì)三個(gè)數(shù)據(jù)集進(jìn)行增強(qiáng)并獲得數(shù)據(jù)量都彼此接近的問題樣本，大約12000 個(gè)圖像樣本，即分別對(duì)SAT0316INDU、SAT12INDU 和SAT12ALL擴(kuò)展6、11、8 倍。在正式訓(xùn)練之前，對(duì)所有的圖像執(zhí)行像素值標(biāo)準(zhǔn)化，即讓圖像的像素值分布擁有零均值和單位一方差。模型優(yōu)化的目標(biāo)是交叉熵，優(yōu)化的方式是隨機(jī)梯度下降［20］。

圖1 CNN模型結(jié)構(gòu)

評(píng)估完成訓(xùn)練的深度模型是該模型走向應(yīng)用必不可少的一步，然而由于算法預(yù)測(cè)的問題不唯一的標(biāo)簽的特性，目前主流的算法預(yù)測(cè)的性能評(píng)估都不能公平直觀地反映出預(yù)測(cè)算法的質(zhì)量。例如，輸入一個(gè)問題實(shí)例，輸出排名第一的算法的預(yù)測(cè)器性能肯定強(qiáng)于輸出為排名第三的算法預(yù)測(cè)器。可以說錯(cuò)誤分類損失在一定程度上就是用來衡量算法預(yù)測(cè)器的預(yù)測(cè)質(zhì)量，但是不同的問題實(shí)例之間的復(fù)雜度可能是完全不同的，直接基于時(shí)間的對(duì)比就顯得不夠公平，而且也不能反映出預(yù)測(cè)器的真實(shí)能力。因此，為了更公平且方便地比較算法預(yù)測(cè)器的預(yù)測(cè)質(zhì)量，我們提出了新的評(píng)價(jià)方法：可解的平均預(yù)測(cè)算法水平（Solvable Average Algorithm Level，SAAL），見式（1）。SAAL 嘗試預(yù)測(cè)算法a*在當(dāng)前問題x下實(shí)際可行的算法序列Ax中的排名，index函數(shù)輸出算法a*在其根據(jù)算法性能排序的算法列表Ax中的排名，它的取值范圍為[0，| |Ax-1]，其中“0”表示預(yù)測(cè)的算法是算法集中最佳的一個(gè)，其他所有不能解的算法的排名輸出都是 |Ax|。除此之外，實(shí)驗(yàn)中采用的另外一個(gè)評(píng)估方法是解決率（Percentage Solved，PS），即衡量算法預(yù)測(cè)器的決策能夠解決多少問題實(shí)例。在驗(yàn)證模型時(shí)，采用的評(píng)估方法是帶懲罰的平均運(yùn)行時(shí)間（Penalized Average Runtime Score，PAR10），它能表明所有輸入實(shí)例的期望運(yùn)行時(shí)間。如果預(yù)測(cè)方法能夠解決問題實(shí)例，計(jì)算時(shí)取它的真實(shí)值，否則取10 倍的該數(shù)據(jù)集截止時(shí)間。

本文的實(shí)驗(yàn)主要測(cè)試了同一個(gè)CNN 模型在多個(gè)不同數(shù)據(jù)集及其變種上的性能表現(xiàn)，主要由PS和SAAL 測(cè)試算法預(yù)測(cè)器的預(yù)測(cè)準(zhǔn)確性和預(yù)測(cè)質(zhì)量，分別記錄在表1和表2中。參與測(cè)試的預(yù)測(cè)模型是在驗(yàn)證集上表現(xiàn)PAR10 指標(biāo)表現(xiàn)最好的一個(gè)。此外，在關(guān)于未增強(qiáng)的圖像集的區(qū)域，SAT12INDU數(shù)據(jù)集沒有相關(guān)的實(shí)驗(yàn)結(jié)果，這要?dú)w因于SAT12INDU 內(nèi)部的訓(xùn)練樣本太少，導(dǎo)致深度模型在此數(shù)據(jù)集上的預(yù)測(cè)效果極其不穩(wěn)定，因此很淡獲得有效的實(shí)驗(yàn)數(shù)據(jù)，這也反映了將深度學(xué)習(xí)方法應(yīng)用于算法預(yù)測(cè)任務(wù)的所面臨的困難。

表1 多個(gè)模型多種數(shù)據(jù)集上的解決率（PS）

從準(zhǔn)確性的角度來看，在SAT12ALL 和SAT0-316 INDU 數(shù)據(jù)集上的增強(qiáng)圖像數(shù)據(jù)集操作可以顯著增加預(yù)測(cè)模型的解決率，即該操作可以解決更多的問題實(shí)例，也可以讓無法參于模型訓(xùn)練的數(shù)據(jù)集能夠訓(xùn)練，比如SAT12INDU。在算法標(biāo)簽的選擇上，一般二元標(biāo)簽總能夠帶來最好的預(yù)測(cè)準(zhǔn)確率，但是這并不意味著其它的算法標(biāo)簽沒有意義。如表2 所示，以在一般二元標(biāo)簽和增強(qiáng)圖像數(shù)據(jù)集上訓(xùn)練的模型為基礎(chǔ)，算法標(biāo)簽優(yōu)化在一定程度上可以帶來更優(yōu)秀的算法決策，雖然在準(zhǔn)確性方面稍微有所下降，但是相對(duì)于初始的訓(xùn)練條件，即未增強(qiáng)的圖像數(shù)據(jù)集和一般二元標(biāo)簽，這些優(yōu)化依然能夠帶來不同程度的決策質(zhì)量提升，尤其在SAT0316-INDU 和SAT12INDU 數(shù)據(jù)集上，模型預(yù)測(cè)的方法更加偏向于當(dāng)前問題實(shí)例的最優(yōu)算法。

表2 多個(gè)模型多種數(shù)據(jù)集上的平均的算法預(yù)測(cè)水平（SAAL）

5 結(jié)語

算法預(yù)測(cè)希望為每個(gè)給定的問題實(shí)例指定用于求解的最佳候選算法。實(shí)踐證明，算法預(yù)測(cè)是一種的有效的組合方法。但是，構(gòu)建優(yōu)秀預(yù)測(cè)模型需要一定水平的專業(yè)領(lǐng)域知識(shí)。深度學(xué)習(xí)依靠其強(qiáng)大表示學(xué)習(xí)功能可以降低這方面的要求。本章主要關(guān)注在布爾可滿足性（SAT）問題上基于深度學(xué)習(xí)的算法預(yù)測(cè)的研究，即問題樣本及其算法標(biāo)簽的變化對(duì)最終模型的性能的影響，并且提出一個(gè)新的評(píng)價(jià)指標(biāo)做橫向?qū)Ρ取淖詈蟮慕Y(jié)果可以看出，將深度學(xué)習(xí)應(yīng)用于算法預(yù)測(cè)的瓶頸依然來自于原始問題數(shù)據(jù)的重新表示。由于圖像已經(jīng)在下采樣的時(shí)候丟失了過多的信息，這使得圖像很難還原初始的問題實(shí)例。另外，人類無法理解圖像所表達(dá)的含義的缺陷使人們無法進(jìn)一步探索其學(xué)習(xí)過程。因此，目前的自動(dòng)化特征提取亟需找到一種新穎且合理的中間格式來表征復(fù)雜的問題實(shí)例，從而以較低的代價(jià)實(shí)現(xiàn)自動(dòng)化特征的目標(biāo)。