深度算法預測模型的數據優化*

程勁松

（南京航空航天大學 南京 211106）

1 引言

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

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

2 背景

本文關注的問題領域是SAT，它是計算機歷史上第一個被證明為NP-Complete 的決策問題，它的原始結構文本示例如下所示。

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

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

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

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

3 數據優化

3.1 數據集擴展

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

在訓練深度模型時，人們總是期望可以有更多的數據來優化的深度預測模型。但是，由于算法預測中問題域的特殊性，很難收集足夠多的數據以生成強大的深度學習模型。SAT 問題的本質是邏輯變量之間的析取與合取，然而最終的合取范式的取值并不受邏輯變量或者簡單析取式之間的位置影響［15］。比如簡單析取式1 ∨2 ∨3 與3 ∨1 ∨2 在邏輯上是等價的，因此在原始的問題實例內容轉換成ASCII 碼時，邏輯變量的順序信息也被編碼而加入了圖像的信息。總地來說，邏輯變量之間以及簡單析取式之間順序的是可交換的，每個原始SAT問題實例在理論上都可以任意排列和組合這些關鍵信息，從而可以生成幾乎無限的圖像格式數據。

3.2 算法標簽優化

對于NP 問題的算法，必須提前給定一個運行時間的閾值（截止時間，cut-off time），所以在截止時間內結束計算并得出解的算法就是可用的目標算法。因此，截止時間的預設則顯得至關重要，由截止時間的設置引起的算法標簽分布的變化會隱式地影響深度學習這類監督學習的模型。

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

如果能夠為所有的算法單獨確定一個截止時間，因此生成的問題實例算法標簽的分布則會與原來的標簽分布完全不同。為了研究這種意義上標簽分布，本文提出了另一種標簽選項，即獨立自適應標簽。具體的實現方式利用了層次聚類算法（Agglomerative Hierarchical Clustering）［16～17］，獨立地對每一個算法在訓練問題實例上的性能進行聚類，得到類間距離最遠的兩個簇：一個表示當前算法能夠解決的問題實例，另一個表示余下的“不能被解決”的問題實例。當然，這個“不能被解決”只是表示該問題實例不能在截止時間內被特定的算法解決。這個聚類結果可以導出獨立自適應二元標簽，對于它的連續版本，則需要根據兩個簇之間的邊界或相交點的時間作為各自新的截止時間，然后按照一般連續標簽的計算方法，生成新的獨立自適應連續標簽。

4 具體實驗

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

圖1 CNN模型結構

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

本文的實驗主要測試了同一個CNN 模型在多個不同數據集及其變種上的性能表現，主要由PS和SAAL 測試算法預測器的預測準確性和預測質量，分別記錄在表1和表2中。參與測試的預測模型是在驗證集上表現PAR10 指標表現最好的一個。此外，在關于未增強的圖像集的區域，SAT12INDU數據集沒有相關的實驗結果，這要歸因于SAT12INDU 內部的訓練樣本太少，導致深度模型在此數據集上的預測效果極其不穩定，因此很淡獲得有效的實驗數據，這也反映了將深度學習方法應用于算法預測任務的所面臨的困難。

表1 多個模型多種數據集上的解決率（PS）

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

表2 多個模型多種數據集上的平均的算法預測水平（SAAL）

5 結語

算法預測希望為每個給定的問題實例指定用于求解的最佳候選算法。實踐證明，算法預測是一種的有效的組合方法。但是，構建優秀預測模型需要一定水平的專業領域知識。深度學習依靠其強大表示學習功能可以降低這方面的要求。本章主要關注在布爾可滿足性（SAT）問題上基于深度學習的算法預測的研究，即問題樣本及其算法標簽的變化對最終模型的性能的影響，并且提出一個新的評價指標做橫向對比。從最后的結果可以看出，將深度學習應用于算法預測的瓶頸依然來自于原始問題數據的重新表示。由于圖像已經在下采樣的時候丟失了過多的信息，這使得圖像很難還原初始的問題實例。另外，人類無法理解圖像所表達的含義的缺陷使人們無法進一步探索其學習過程。因此，目前的自動化特征提取亟需找到一種新穎且合理的中間格式來表征復雜的問題實例，從而以較低的代價實現自動化特征的目標。