【新智元導讀】本文介紹了一個名為LIPO的全局優化方法，這個方法沒有參數，而且經驗證比隨機搜索方法好。基於此，作者提出了MaxLIPO和置信域方法混合使用的優化方法，在所有測試中，都取得了最優結果，而且不需要任何參數。你還在手動調參？不如試一下更好的方法。
有一個常見的問題：你想使用某個機器學習算法，但它總有一些難搞的超參數。例如權重衰減大小，高斯核寬度等等。算法不會設置這些參數，而是需要你去決定它們的值。如果不把這些參數設置為「良好」的值，這個算法就不會起作用。那麼你會怎麼做呢？下面我列出了我見過的人們的做法，從最常見到最不常見排序：
猜測和檢查：聽從你的直覺，選擇感覺不錯的數字，看看它們是否工作。一直持續這樣做，直到厭倦。
網格搜索：讓計算機嘗試在一定範圍內均勻分布的一組值。
隨機搜索：讓計算機隨機挑選一組值。
貝葉斯優化：使用像MATLAB的bayesopt之類的工具來自動選擇最佳參數，然後你會發現貝葉斯優化比你的機器學習算法有更多的超參數，你變得沮喪，然後回頭使用猜測和檢查或網格搜索。
在有一個良好的初始猜測的前提下進行局部優化：這就是MITIE的方法，它使用BOBYQA算法，並有一個精心選擇的起始點。由於BOBYQA只尋找最近的局部最優解，所以這個方法是否成功很大程度上取決於是否有一個好的起點。在MITIE的情況下，我們知道一個好的起點，但這不是一個普遍的解決方案，因為通常你不會知道好的起點在哪裡。從好的方面來說，這種方法非常適合尋找局部最優解。稍後我會再討論這一點。
絕大多數人只會用猜測和檢查的方法。但應該有更好的方法。我們都希望像貝葉斯優化這樣的黑盒子優化策略有用，但根據我的經驗，如果你沒有將其超參數設置為正確的值，那麼它還不如專業的猜測和檢查。我認識的每個使用貝葉斯優化的人都有相同的經驗。最終，如果我認為手動調參能做得更好，那麼就手動唄，而且我的大多數同事也這樣想。最終的結果是，我大部分時間都沒有使用自動化的超參數選擇工具。 我很想有一個無參數的全局優化器，可以信任地用它做超參數選擇。
所以當我讀到Cédric Malherbe和Nicolas Vayatis在去年的機器學習國際會議上發表的Global optimization of Lipschitz /span>，即使 f(x)有多個局部極大值。論文中的關鍵思想是保持f(x)的分段線性上界，並用它來決定在每個優化步驟中用於評估的x。因此，如果你已經評估了點x ，x ，...，xt，那麼您可以在 f(x)上定義一個簡單的上界，如下所示：
其中k是f(x)的Lipschitz常數。因此，根據Lipschitz常數的定義， U(x)f(x), x, 是正確的。作者繼而提出一個簡單的算法，稱為LIPO，該算法隨機挑選點，檢查新點的upper bound是否比迄今所見的最佳點好，如果是，則選擇它作為下一個點來評估。例如，下圖顯示了一個簡單的f(x)函數（紅色線），它相關的upper bound U(x)以綠色顯示。在這種情況下， U(x) 由4個點定義，這裡用小黑方塊表示。
很容易看出upper bound如何幫助你選擇好的點來評估。例如，如果你選擇最大上界作為下一次迭代，那麼你已經非常接近全局最大化。作者繼續證明了這種方法的一些不錯的特性。特別是，它們都是用數學方法證明的，並且在經驗上也證明了在許多非平凡的情況下，這種方法比隨機搜索更好。他們還將該方法與貝葉斯優化等其他算法進行比較，並顯示出其競爭力。
但是你可能會想：「等一下，我們不知道Lipschitz常數k的值！」 這不是大問題，因為它很容易估計，例如，在每次迭代之前將k設置為f(x)的最大觀察斜率。這相當於解決下面這個簡單的問題：
Malherbe等人測試了這個k估計方法的變體，並顯示它可以工作。
這方法很棒。我喜歡這篇論文。總結一下，它提出了一個名為LIPO的全局優化方法，這個方法沒有參數，而且經驗證比隨機搜索方法好。而且它也很簡單。所以我打算給dlib加入一些LIPO算法，我在最新的dlib v19.8版本中實踐了。
但是，如果你想在實踐中使用LIPO，還需要解決一些問題。這篇文章接下來的部分討論了這些問題以及dlib實現如何解決這些問題。首先，如果 f(x) 有噪聲或不連續，即使只有一點點，它也不能可靠地工作，因為k會變成無窮大。在現實世界的問題中總是會發生這種情況。其次，並不是所有的超參數都同等重要，有些參數幾乎沒有關係，而另一些參數的一點小變化都會對 f(x)的輸出影響很大。所以如果每個超參數都有自己的k，那會很好。你可以通過定義上界U(x) 來解決這些問題，如下所示：
現在，來自 f(x) 的每個sample 都有自己的噪聲項，大部分時間它的值應該是0，除非非常接近於不連續性或者存在一些隨機性。在這裡，K是一個對角線矩陣，包含「每個超參數一個Lipschitz k項」。通過這個公式，將每個σ設為0，給出與Malherbe等人所提出的相同的U(x)，但是如果採取更一般的值，可以處理上面提到的問題。
像之前那樣，我們可以通過求解一個優化問題來找到U(x)的參數：
σ²上的的penalty使得大多數σ項恰好為0。整個算法的表現對於這裡使用的特定penalty的值是不敏感的，只要它大得合理，那麼大部分時間σ值都是0，同時仍然阻止k變成無限，這是我們想要的。也可以將它重寫為一個大的二次規劃問題，並用雙坐標下降法來解決這個問題。這裡就不再詳細討論。
需要解決的最後一個問題是LIPO在局部最大化方面的收斂問題。所以，雖然LIPO擅長達到f(x)的最高峰值，但一旦到達，它不會非常快地向最優位置（即峰頂）進展。這是許多衍生優化算法都有的問題，包括MATLAB的貝葉斯優化工具。幸運的是，並不是所有的方法都受到這個限制。尤其是，Michael J.D.Powell撰寫了一系列有關如何將經典置信域方法應用於無梯度優化的論文。這些方法在目前所見的最佳點附近擬合一個二次曲面，然後在當前最佳點的某個距離內進行下一次迭代，成為該二次曲面的最大值。所以我們「信任」這個局部二次模型在最佳點附近的一個小區域內是準確的，因此被稱為「置信域」。上面提到的BOBYQA方法是其中之一，它對最接近的局部最優收斂性非常好，很容易只需很少的步驟找到局部最優值。
我們可以結合這兩種方法來解決LIPO的收斂問題，LIPO將探索 f(x)並快速找到最大峰值點。然後一個Powell 置信域方法可以有效地找到該峰值的確切最大化值。把這兩者結合起來最簡單的方法是在它們之間交替，這就是dlib所做的。在偶數次迭代中，我們根據upper bound選取下一個x，而在奇數次迭代中，我們根據置信域模型選擇下一個x。我還用了一個略微不同的LIPO版本，叫做MaxLIPO。回想一下，Malherbe等人建議選擇一個upper bound大於當前最佳目標值的點。不過，我發現在每次迭代中選擇最大 upper bound點更好。這個替代版本MaxLIPO就是dlib使用的。你可以在下面的視頻中看到MaxLIPO和置信域方法混合使用的情況：
在這個視頻中，紅線是要優化的函數，我們要找的是最大值點。每次算法從函數中抽取一個點時，我們就會用一個小框來記錄。求解器的狀態由全局上界U(x)和置信域方法所使用的局部二次模型決定。因此，我們繪製了upper bounding 模型以及當前的局部二次模型，這樣你就可以看到隨著優化的進行，它們是如何演進的。我們還用一條垂直線標註了到目前為止所看到的最佳點的位置。
將MaxLIPO和Powell置信區間綜合方法（MaxLIPO+TR，紅色）與MATLAB貝葉斯優化工具的默認設置（藍色）相比較，貝葉斯優化在±10的-3次方精度趨於停滯，而混合方法很快就降到了±10的-17次方浮點精度。
MaxLIPO+TR與其他方法的比較，在所有測試中，都取得了最優結果，而且不需要任何參數，使用起來非常方便。
原文還附有使用這個優化函數的Python代碼，具體看這裡：http://blog.dlib.net/2017/12/a-global-optimization-algorithm-worth.html
論文：Global optimization of Lipschitz /span>
本文首發於微信公眾號：新智元。文章內容屬作者個人觀點，不代表和訊網立場。投資者據此操作，風險請自擔。
（責任編輯：何一華 HN110）