蟻群演算法ppt

① XGBoost與GBDT(一)-幾種最優化方法對比

發現了作者的一個ppt GBDT演算法原理與系統設計簡介 ,從頭復習了一波相關的內容,寫兩篇記錄下來.
從根本上來說, GBDT 與XGBoost最大的區別在於二者用的優化方法不一樣,所以從先從最優化方法開始復習.

最優化問題通常分為兩個大類:

在機器學習中,典型的做法就是選擇一個合適的模型 ,對該模型的損失函數 ,通過最優化的方法最小化損失函數,從而求解模型的參數.
最常見的幾種優化方法包括[2]:

可以看出,雖然牛頓法收斂速度較快,但是每次迭代過程,計算海塞矩陣的逆過程相當繁瑣,特別是當該矩陣維度較大時.因此就有了逆牛頓法,他使用正定矩陣來近似求海塞矩陣的逆.
擬牛頓法和梯度下降法一樣只要求每一步迭代時知道目標函數的梯度,另外，因為擬牛頓法不需要二階導數的信息，所以有時比牛頓法更為有效。常用的擬牛頓法有DFP演算法和BFGS演算法.此處不再贅述.
下面補充擬牛頓法的思路(摘自[3]):

共軛梯度法是一種用於解決無約束凸二次規劃問題的方法.

啟發式方法指人在解決問題時所採取的一種根據經驗規則進行發現的方法。其特點是在解決問題時,利用過去的經驗,選擇已經行之有效的方法，而不是系統地、以確定的步驟去尋求答案。啟發式優化方法種類繁多，包括經典的模擬退火方法、遺傳演算法、蟻群演算法以及粒子群演算法等等。

上面前三種演算法,解決的問題都僅限於無約束的凸優化, 而拉格朗日乘數法則解決含有約束條件的優化問題,例如svm演算法的解法推導.約束優化問題的一般形式是:

這個問題可以轉化成函數 的無條件極值問題.
對於約束條件為不等式的問題,有科學家拓展了拉格朗日乘數法.增加了kkt條件以求解.沒學過最優化,這塊就沒法細談了.有機會一定要補上.

[1]Poll的筆記.常見的幾種最優化方法[EB/OL]. https://www.cnblogs.com/maybe2030/p/4751804.html,2015-08-23 .
[2]超神冉.最優化演算法——常見優化演算法分類及總結[EB/OL]. https://blog.csdn.net/qq997843911/article/details/83445318,2018-10-27 .
[3]李航.統計學習方法[M].清華大學出版社:北京,2012:220.
[4]Ja1r0.共軛梯度法[EB/OL]. https://zhuanlan.hu.com/p/28623599,2018-05-28 .