1 梯度下降法

梯度：如果函數(shù)是一維的變量睦柴，則梯度就是導(dǎo)數(shù)的方向；
如果是大于一維的毡熏，梯度就是在這個點的法向量坦敌，并指向數(shù)值更高的等值線，這就是為什么求最小值的時候要用負(fù)梯度招刹。

梯度下降法的缺點：

• （1）靠近極小值時收斂速度減慢丹弱，如下圖所示；
• （2）直線搜索時可能會產(chǎn)生一些問題铲咨；
• （3）可能會“之字形”地下降躲胳。

1.1 批量梯度下降法（BGD）

1.2 隨機梯度下降（SGD）

隨機梯度下降是通過每個樣本來迭代更新一次司训，如果樣本量很大的情況（例如幾十萬）构捡，那么可能只用其中幾萬條或者幾千條的樣本，就已經(jīng)將theta迭代到最優(yōu)解了壳猜，對比上面的批量梯度下降勾徽，迭代一次需要用到十幾萬訓(xùn)練樣本，一次迭代不可能最優(yōu)统扳，如果迭代10次的話就需要遍歷訓(xùn)練樣本10次喘帚。但是，SGD伴隨的一個問題是噪音較BGD要多咒钟，使得SGD并不是每次迭代都向著整體最優(yōu)化方向吹由。

SGD的問題是噪音比BGD要多，使得SGD不是每次迭代都向著整體最優(yōu)的方向朱嘴，SGD以損失一部分精確度和增加一定的迭代次數(shù)為代價倾鲫，換取了總體的優(yōu)化效率的提升，增加的迭代次數(shù)遠(yuǎn)小于樣本的數(shù)量萍嬉。

#1.3 SGD和BGD的比較

可以看到BGD和SGD是兩個極端乌昔，SGD由于每次參數(shù)更新僅僅需要計算一個樣本的梯度，訓(xùn)練速度很快壤追，即使在樣本量很大的情況下磕道，可能只需要其中一部分樣本就能迭代到最優(yōu)解，由于每次迭代并不是都向著整體最優(yōu)化方向行冰，導(dǎo)致梯度下降的波動非常大捅厂，更容易從一個局部最優(yōu)跳到另一個局部最優(yōu)，準(zhǔn)確度下降资柔。

• BGD：最小化所有訓(xùn)練樣本的損失函數(shù)焙贷，使得最終求解的是全局最優(yōu)解，即使得求解的風(fēng)險函數(shù)最小贿堰，但是對于大規(guī)模樣本效率較低辙芍。
• SGD：最小化每條樣本的損失函數(shù)，雖然不是每次迭代得到的損失函數(shù)都向著全局最優(yōu)的方向，但是大方向是全局最優(yōu)解故硅，最終的結(jié)果往往是在全局最優(yōu)解的附近庶灿，適用于大規(guī)模的訓(xùn)練樣本情況。

2 牛頓法

2.1 牛頓法

牛頓法是一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法吃衅。方法使用函數(shù)f (x)的泰勒級數(shù)的前面幾項來尋找方程f (x) = 0的根往踢。牛頓法最大的特點就在于它的收斂速度很快。

2.2 牛頓法優(yōu)缺點

• 優(yōu)點：二階收斂徘层，收斂速度快峻呕；
• 缺點：牛頓法是一種迭代算法，每一步都需要求解目標(biāo)函數(shù)的Hessian矩陣的逆矩陣趣效，計算比較復(fù)雜瘦癌。

2.3 梯度下降法和牛頓法的比較

從本質(zhì)來說，梯度下降法是一階收斂跷敬，牛頓法是二階收斂讯私，所以牛頓法的收斂速度更快。梯度下降法每次考慮的是當(dāng)前位置的負(fù)梯度下降西傀，而牛頓法不但考慮當(dāng)前位置下降的是否夠快斤寇，還會考慮下一步下降的是否夠大，也就是說牛頓法目標(biāo)更長遠(yuǎn)一點拥褂。牛頓法是用一個二次曲面去擬合你當(dāng)前所處位置的局部曲面娘锁，而梯度下降法使用一個平面去擬合當(dāng)前的局部曲面，通常情況二次曲面擬合會比平面更好肿仑，所以牛頓法的下降路徑會更符合真實的最優(yōu)下降路徑致盟。

3 擬牛頓法（DFP碎税、BFGS）

擬牛頓法的本質(zhì)思想是改善牛頓法每次需要求解復(fù)雜的Hessian矩陣的逆矩陣的缺陷尤慰，它使用正定矩陣來近似Hessian矩陣的逆，從而簡化了運算的復(fù)雜度雷蹂。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標(biāo)函數(shù)的梯度伟端。通過測量梯度的變化，構(gòu)造一個目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性匪煌。這類方法大大優(yōu)于最速下降法责蝠，尤其對于困難的問題。另外萎庭，因為擬牛頓法不需要二階導(dǎo)數(shù)的信息霜医，所以有時比牛頓法更為有效。如今驳规，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束肴敛，約束，和大規(guī)模的優(yōu)化問題。

4 共軛梯度法（Conjugate Gradient）

共軛梯度法是介于最速下降法與牛頓法之間的一個方法医男，它僅需利用一階導(dǎo)數(shù)信息砸狞，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點镀梭，共軛梯度法不僅是解決大型線性方程組最有用的方法之一刀森，也是解大型非線性最優(yōu)化最有效的算法之一。在各種優(yōu)化算法中报账，共軛梯度法是非常重要的一種研底。其優(yōu)點是所需存儲量小，具有步收斂性笙什，穩(wěn)定性高飘哨，而且不需要任何外來參數(shù)。

5 啟發(fā)式優(yōu)化方法

啟發(fā)式方法是指人在解決優(yōu)化問題時所采取的一種根據(jù)經(jīng)驗規(guī)則進(jìn)行發(fā)現(xiàn)的方法琐凭。其特點是在解決問題時芽隆，利用過去的經(jīng)驗，選擇已經(jīng)行之有效的方法统屈，而不是系統(tǒng)地胚吁、以確定的步驟去尋求答案。啟發(fā)式優(yōu)化方法種類繁多愁憔，包括經(jīng)典的模擬退火方法腕扶，遺傳算法、蟻群算法以及粒子群算法等等吨掌。
還有一種特殊的優(yōu)化算法被稱之多目標(biāo)優(yōu)化算法半抱，它主要針對同時優(yōu)化多個目標(biāo)（兩個及兩個以上）的優(yōu)化問題，這方面比較經(jīng)典的算法有NSGAII算法膜宋、MOEA/D算法以及人工免疫算法等窿侈。

6 EM算法

EM算法是一類算法的總稱。EM算法分為E-step和M-step兩步秋茫。EM算法的應(yīng)用范圍很廣史简，基本機器學(xué)習(xí)需要迭代優(yōu)化參數(shù)的模型在優(yōu)化時都可以使用EM算法。
EM算法的思想和過程
E-step：E的全稱是Exception肛著，即期望的意思圆兵。E-step也是獲取期望的過程。根據(jù)現(xiàn)有的模型枢贿，計算各個觀測數(shù)據(jù)輸入到模型中的結(jié)果殉农。這個過程稱為期望值計算過程，即E過程局荚。
M-step：M的全稱是Maximization超凳，即最大化的意思。M-step也是期望最大化的過程。得到一輪期望值以后聪建，重新計算模型參數(shù)钙畔，以最大化期望值。這個過程為最大化過程金麸，即M過程擎析。
最大化的意思是我們在使用這個模型時希望我們定義的函數(shù)能使得到的結(jié)果最大化，而結(jié)果越大越接近我們希望得到的結(jié)果挥下。我們優(yōu)化的目標(biāo)也就是這些能得到最大值的函數(shù)揍魂。
常見的EM算法有：隱含馬爾科夫模型的訓(xùn)練方法Baum-Welch算法；最大熵模型的訓(xùn)練方法GIS算法等棚瘟。

EM算法結(jié)果
EM算法不一定能保證獲得全局最優(yōu)解现斋，但如果我們優(yōu)化的目標(biāo)函數(shù)是一個凸函數(shù)，那么一定能保證得到全局最優(yōu)解偎蘸。否則可能獲得局部最優(yōu)解庄蹋。因為如果優(yōu)化的目標(biāo)函數(shù)有多個峰值點，則如果優(yōu)化到某個不是最高的峰值點處迷雪，則會無法再繼續(xù)下去限书，這樣獲得的是局部最優(yōu)解。

EM算法總結(jié)
EM算法只需要輸入一些訓(xùn)練數(shù)據(jù)章咧，同時定義一個最大化函數(shù)倦西，接下來經(jīng)過若干次迭代，就可以蓄念出我們需要的模型了赁严。

7 小結(jié)

在機器學(xué)習(xí)中的無約束優(yōu)化算法扰柠，除了梯度下降以外，還有前面提到的最小二乘法疼约，此外還有牛頓法和擬牛頓法卤档。
　　梯度下降法和最小二乘法相比，梯度下降法需要選擇步長忆谓，而最小二乘法不需要裆装。梯度下降法是迭代求解踱承，最小二乘法是計算解析解倡缠。如果樣本量不算很大，且存在解析解茎活，最小二乘法比起梯度下降法要有優(yōu)勢昙沦，計算速度很快。但是如果樣本量很大载荔，用最小二乘法由于需要求一個超級大的逆矩陣盾饮，這時就很難或者很慢才能求解解析解了，使用迭代的梯度下降法比較有優(yōu)勢。
　　梯度下降法和牛頓法/擬牛頓法相比丘损，兩者都是迭代求解普办，不過梯度下降法是梯度求解，而牛頓法/擬牛頓法是用二階的海森矩陣的逆矩陣或偽逆矩陣求解徘钥。相對而言衔蹲，使用牛頓法/擬牛頓法收斂更快。但是每次迭代的時間比梯度下降法長呈础。