原文： http://www.benfrederickson.com/numerical-optimization/
作者：Ben Frederickson

數(shù)值優(yōu)化是機(jī)器學(xué)習(xí)的核心技術(shù)之一。對于許多問題，很難直接找出最佳解決方案，但設(shè)置一個衡量解決方案效果的損失函數(shù)相對容易 - 然后最小化該函數(shù)的參數(shù)以找到解決方案。

當(dāng)我第一次嘗試學(xué)習(xí)javascript時，我最終寫了一堆數(shù)值優(yōu)化程序。因?yàn)闊o論如何我都有這些代碼，我認(rèn)為提供這些算法如何工作的一些交互式可視化可能會很有趣。

這篇文章很酷的一點(diǎn)是代碼都在瀏覽器中運(yùn)行，這意味著您可以交互式地為每個算法設(shè)置超參數(shù)，更改初始位置，并更改正在調(diào)用的函數(shù)以更好地了解這些算法工作。

如果你想要檢查它，這篇文章的所有代碼都在github上，它既有最小化功能，也有所有可視化。

內(nèi)爾德 - 米德 Nelder-Mead

假裝你不記得任何微積分，甚至任何基本代數(shù)。你有一個功能，并告訴你需要找到最低值。

一個簡單的嘗試就是對相對靠近的兩個點(diǎn)進(jìn)行采樣，然后重復(fù)從最大值開始：

0.png

迭代11/21，損失= 1.30662

這種方法中的明顯問題是使用固定的步長：它不能接近真正的最小值而不是步長，因此它不會收斂。當(dāng)顯然步長應(yīng)該更大時，它也會花費(fèi)太多時間進(jìn)入最小值。

為了克服這些問題，Nelder-Mead方法根據(jù)新點(diǎn)的丟失動態(tài)調(diào)整步長。如果新點(diǎn)比任何先前看到的值更好，它會擴(kuò)展步長以加速到底部。同樣，如果新點(diǎn)更糟，它會收縮步長以收斂最小值。

在通常的設(shè)置是一半時，收縮的步長和雙步長擴(kuò)大時。對于上面的一維情況，這就像一個疾馳的搜索大小加倍，直到它包含最小值，當(dāng)它切換到收縮然后進(jìn)行二分搜索時。

這種方法可以很容易地擴(kuò)展到更高維度的例子中，所需要的只是比維度多一點(diǎn) - 然后反映其余點(diǎn)的最差點(diǎn)以降低步驟。看看這個等高線圖，看看它如何在2個維度中工作：

1.png

單擊此圖中的任意位置以使用新的初始位置重新啟動。此方法將在該點(diǎn)處生成三角形，然后在每次迭代時將觸發(fā)器翻轉(zhuǎn)到最小值，根據(jù)設(shè)置根據(jù)需要進(jìn)行擴(kuò)展或收縮。

雖然這種方法非常簡單，但它實(shí)際上在低維函數(shù)上運(yùn)行得相當(dāng)好。

像這樣的任何直接搜索方法的最大缺點(diǎn)是它們都開始在更高維度函數(shù)上表現(xiàn)得非常糟糕。對于如上所述的1維和2維示例，Nelder-Mead表現(xiàn)良好 - 但機(jī)器學(xué)習(xí)模型可以增長到數(shù)百萬甚至數(shù)十億甚至數(shù)十億的參數(shù)，并且這種方法對于具有十幾個參數(shù)的簡單問題不起作用。

其中一個問題是找出要走的方向：這在二維空間中并不太難，但隨著維數(shù)的增長而呈指數(shù)級變得更加困難。

梯度下降

這導(dǎo)致了最陡峭下降的路徑，看起來有點(diǎn)像一個球從山上滾向當(dāng)?shù)氐淖钚^(qū)域之一：

2.png

這種方法的問題在于設(shè)置學(xué)習(xí)率。如果您將速率設(shè)置得太低， Gradient Descent將永遠(yuǎn)找到解決方案，需要采取許多微小的步驟來解決問題。設(shè)置學(xué)習(xí)率太高，它會在最小值附近瘋狂振蕩而不會收斂。更糟糕的是，最佳學(xué)習(xí)速率會因功能而異，因此沒有一個值可以實(shí)現(xiàn)良好的默認(rèn)值。

一個線搜索，并確保梯度充分不上不下，以防止過量服用小步-能在每次迭代這樣既損失總是被降，以防止它從超調(diào)極小修改學(xué)習(xí)率。在此處啟用行搜索會導(dǎo)致迭代次數(shù)減少，每次迭代可能需要對額外功能點(diǎn)進(jìn)行采樣。

即使使用線搜索，Gradient Descent仍然會遇到像Rosenbrocks Function這樣的功能。問題是有時候最好的方向不是沿著漸變，你還需要考慮函數(shù)的曲率。

共軛梯度

共軛梯度方法試圖通過將先前的搜索方向與當(dāng)前梯度包括在一起以提出新的更好的搜索方向來估計被最小化的函數(shù)的曲率。

Jonathan Shewchuk撰寫了一篇名為“沒有痛苦痛苦的共軛梯度方法的介紹”的偉大論文，在那里他深入描述了共軛梯度法的工作原理。唯一的問題是，它比這整篇文章要長得多 - 而且它甚至沒有開始談?wù)摲蔷€性案例，直到第四十二頁（這給了我噩夢，他有什么令人痛苦的痛苦版本一定要學(xué)習(xí)就好了。

您可以在下面看到此方法的進(jìn)度。采用的實(shí)際方向?yàn)榧t色，每次迭代的漸變用黃色箭頭表示。在某些情況下，使用的搜索方向與漸變幾乎相差90度，這解釋了為什么Gradient Descent在此函數(shù)上存在此類問題：

3.png

另一個例子

到目前為止的例子只有1維或2維函數(shù)，這些函數(shù)對于優(yōu)化來說并不是很有趣。他們還沒有研究實(shí)際數(shù)據(jù) - 這是大多數(shù)機(jī)器學(xué)習(xí)問題的正常情況。我認(rèn)為作為最后一個例子，看看這些算法如何對多維縮放問題進(jìn)行處理會很有趣。

這里的挑戰(zhàn)是將一些點(diǎn)之間的距離矩陣轉(zhuǎn)換為最接近所需距離的每個點(diǎn)的坐標(biāo)。這樣做的一種方法是最小化以下功能：

我在這里使用的數(shù)據(jù)是北美主要城市之間的距離，目標(biāo)是使用這些數(shù)據(jù)來建立這些城市的地圖。通過20個城市之間的距離涉及最小化40個參數(shù)的功能：

4.png

這種可視化非常清楚地展示了幾件事：

• Nelder-Mead方法完全失敗了超過10個城市，甚至在此之前與其他方法相比都在掙扎。
• 如果您具有適當(dāng)?shù)膶W(xué)習(xí)率，則梯度下降效果很好，但最佳學(xué)習(xí)率隨城市數(shù)量而變化。將學(xué)習(xí)率設(shè)置得太高會導(dǎo)致這種情況不會收斂，而太低則會導(dǎo)致它永遠(yuǎn)消失。
• 使用具有漸變下降的線搜索會導(dǎo)致鋸齒形圖案，使用“共軛漸變”方法對其進(jìn)行平滑處理。

進(jìn)一步閱讀

如果你已經(jīng)閱讀了這篇文章，你可能已經(jīng)發(fā)現(xiàn)，這篇文章只是一個借口讓我在我誤入歧途的學(xué)習(xí)語言的過程中弄亂了一些javascript代碼。我之前所說的一切都已經(jīng)說過，通常是比我更有說服力的人。

Nocedai和Wright寫了一本關(guān)于數(shù)值優(yōu)化的優(yōu)秀書籍，這是我對大部分內(nèi)容的參考。雖然它是一個很好的資源，但我還是提到了其他一些未涵蓋的技術(shù)。

塞巴斯蒂安·魯?shù)拢⊿ebastian Ruder）寫了一篇關(guān)于梯度下降方法的精彩概述，這些方法 更深入，尤其是在用于訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)的大型稀疏模型上的隨機(jī)梯度下降的情況下。

一種很酷的導(dǎo)數(shù)自由優(yōu)化方法是貝葉斯優(yōu)化。Eric Brochu，Mike Vlad Cora和Nando de Freitas寫了一篇關(guān)于貝葉斯優(yōu)化的精彩介紹。貝葉斯優(yōu)化的一個有趣的應(yīng)用是超參數(shù)調(diào)整 - 甚至有一家公司SigOpt為此目的提供貝葉斯優(yōu)化作為服務(wù)。