資訊專欄INFORMATION COLUMN
摘要：一是什么是解無約束非線性規(guī)劃問題最常用的方法，具有收斂速度快內(nèi)存開銷少等優(yōu)點，在機器學習各類算法中常有它的身影。在的一階泰勒展開為二階泰勒展開為去掉最后的余項，得到最速下降法算法的一個前提條件就是在連續(xù)可微，并且在處的導數(shù)不為。
本文由作者林洋港授權網(wǎng)易云社區(qū)發(fā)布。
一、 L-BFGS是什么
L-BFGS是解無約束非線性規(guī)劃問題最常用的方法，具有收斂速度快、內(nèi)存開銷少等優(yōu)點，在機器學習各類算法中常有它的身影。簡單的說，L-BFGS和梯度下降、SGD干的同樣的事情，但大多數(shù)情況下收斂速度更快，這點在大規(guī)模計算中很重要。下圖是深度學習Autoencoder模型不同優(yōu)化方法的比較。
二、 L-BFGS“之前”的那些方法
這里的“之前”并不是說L-BFGS問世之前就已經(jīng)存在的方法，而是指為了更好的理解L-BFGS需要了解的其他方法。無約束問題定義：
我們先從泰勒展開開始，這可以說是本文介紹的所有方法的基礎。f在的一階泰勒展開為
二階泰勒展開為
去掉最后的余項，得到
2.1 最速下降法（Gradient descent）
CD算法的一個前提條件就是f在連續(xù)可微，并且在處的導數(shù)不為0。由公式1可知當?shù)诙?0時f的值將下降。由Cauchy-Schwartz不等式可得
為最速下降方向。因此迭代公式為
滿足
2.2 牛頓法（Newton method）
由于f的極值點就是滿足f的導數(shù)為0，根據(jù)公式2，得到
假設Hesse矩陣可逆，由上式可得牛頓法迭代公式
牛頓法具有二次終止性的特點，即經(jīng)過有限次迭代必達到極小點。例如，對于二次凸函數(shù)
A是對稱正定矩陣，取任意初始點，根據(jù)公式3有
顯然經(jīng)過1次迭代即達到極值點。
但牛頓法要求f二次連續(xù)可微，并且Hesse矩陣滿足可逆和正定兩個條件；同時，牛頓方向不一定每次迭代都是下降方向。
阻尼牛頓法是牛頓法的修正，與牛頓法的區(qū)別是迭代公式增加了牛頓方向上的一維搜索，即
其中
是一維搜索得到的步長，滿足
2.3 擬牛頓法（Quasi-Newton Method）
牛頓法每次迭代都需要計算處的Hesse矩陣的逆，同時Hesse矩陣也不一定是正定的。人們又提出了擬牛頓法，其基本思想是用不包含二階導數(shù)的矩陣來近似Hesse矩陣的逆。將f在處展開成2階泰勒級數(shù)并取近似，即
設Hesse矩陣可逆，可得
設近似矩陣為根據(jù)上述，必須滿足
公式7稱為擬牛頓條件。的不同構造方法，決定了不同的擬牛頓方法。
當時n階對稱正定矩陣時，滿足牛頓條件的也必須是n階對稱正定矩陣。因此的一般構造策略為：取為任意n階對稱正定矩陣（通常為單位矩陣I），然后通過下式求出
稱為校正矩陣。
DFP算法將校正矩陣定義為：
至此，根據(jù)公式4、5、6、7、10、11可以由得出并且不需要每次迭代計算Hesse矩陣。
BFGS算法用矩陣近似公式8中的Hesse矩陣，從而得到
將q與p互換，分別取代由DFP公式可以得到
令，從而得到BFGS公式：
從公式11和公式12可以看出，擬牛頓法每次迭代只需要根據(jù)前次迭代的即可以計算出，不需要求出Hesse矩陣的逆。
2.4 L-BFGS（limited-memory BFGS）
BFGS算法中每次迭代計算需要前次迭代得到的矩陣，該矩陣的存儲空間至少為N(N+1)/2，N為特征維數(shù)，對于高維的應用場景，需要的存儲空間將是非常巨大的。L-BFGS的基本思想就是通過存儲前m次迭代的少量數(shù)據(jù)來替代前一次的矩陣。令y=q，s=p，公式12可以改寫成
公式13展開并取前m項的近似，可得
由于ρ、V、s、y這些變量都最終可以由q、p兩個向量計算得到，因此，我們只需存儲最后m次的q、p向量即可算出加上對角陣H0，總共需要存儲2*m+1個N維向量（實際應用中m一般取4到7之間的值，因此需要存儲的數(shù)據(jù)遠小于Hesse矩陣）。
注：公式4中步長的確定需要使用一維搜索，顧名思義，一維搜索就是沿著直線方向尋找使得目標函數(shù)值最小的參數(shù)值。一維搜索具體又分為精確一維搜索和非精確一維搜索，具體可參看相關文獻。
三、 其他相關方法
由于L-BFGS是建立在目標函數(shù)的2階泰勒展開基礎上的，其前提條件就是函數(shù)的2階導不為0。在機器學習中一般如果用L2正則都是可以滿足這個條件的。如果用的是L1正則，則目標函數(shù)可能出現(xiàn)2階導為0的情況。對于使用L1正則的情況，可以使用OWL-QN方法（Orthant-Wise Limited-memory Quasi-Newton），它是基于L-BFGS修改的。
據(jù)說百度首創(chuàng)了Shooting算法，收斂速度比L-BFGS快得多，目前還不知道怎么做的。
此外，Chih-Jen Lin（LIBSVM作者）提出的信賴域牛頓方法（Trust Region Newton Method），其收斂速度也比L-BGFS快，他開發(fā)的另一個針對大規(guī)模線性分類的軟件LIBLINEAR用的就是這種優(yōu)化方法。
此外，Chih-Jen Lin（LIBSVM作者）提出的信賴域牛頓方法（Trust Region Newton Method），其收斂速度也比L-BGFS快，他開發(fā)的另一個針對大規(guī)模線性分類的軟件LIBLINEAR用的就是這種優(yōu)化方法。
免費領取驗證碼、內(nèi)容安全、短信發(fā)送、直播點播體驗包及云服務器等套餐
更多網(wǎng)易技術、產(chǎn)品、運營經(jīng)驗分享請訪問網(wǎng)易云社區(qū)。
文章來源： 網(wǎng)易云社區(qū)
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/25378.html
摘要：實驗基礎其實實現(xiàn)該功能的主要步驟還是需要計算出網(wǎng)絡的損失函數(shù)以及其偏導數(shù)，具體的公式可以參考前面的博文八。生成均勻分布的偽隨機數(shù)。 前言： 現(xiàn)在來進入sparse autoencoder的一個實例練習，參考Ng的網(wǎng)頁教程：Exercise:Sparse Autoencoder。 這個例子所要實現(xiàn)的內(nèi)容大概如下：從給定的很多張自然圖片中截取出大小為8*8的小patches圖片共10000張...
摘要：下面介紹一些值得注意的部分，有些簡單解釋原理，具體細節(jié)不能面面俱到，請參考專業(yè)文章主要來源實戰(zhàn)那我們直接從拿到一個問題決定用神經(jīng)網(wǎng)絡說起。當你使用時可以適當減小學習率，跑過神經(jīng)網(wǎng)絡的都知道這個影響還蠻大。 神經(jīng)網(wǎng)絡構建好，訓練不出好的效果怎么辦？明明說好的擬合任意函數(shù)(一般連續(xù))(為什么？可以參考http://neuralnetworksanddeeplearning.com/)，說好的足夠...
摘要：現(xiàn)在，人臉識別的克星反人臉識別問世了。多倫多大學教授和研究生的團隊開發(fā)了一種算法，可以動態(tài)地破壞人臉識別系統(tǒng)。因此，成功的攻擊需要同時欺騙所有對象方案。算法對抗生成器訓練給定人臉檢測置信度的對抗成功率。 論文地址：https://joeybose.github.io/assets/adversarial-attacks-face.pdf在一些社交媒體平臺，每次你上傳照片或視頻時，它的人臉識別...
閱讀 2505·2023-04-25 19:31
閱讀 2239·2021-11-04 16:11
閱讀 2805·2021-10-08 10:05
閱讀 1515·2021-09-30 09:48
閱讀 2315·2019-08-30 15:56
閱讀 2406·2019-08-30 15:56
閱讀 2174·2019-08-30 15:53
閱讀 2268·2019-08-30 15:44
