這裡讨論的優化問題指的是，給定目标函數f(x)，我們需要找到一組參數x，使得f(x)的值最小。
本文以下内容假設讀者已經了解機器學習基本知識，和梯度下降的原理。
SGD指stochastic gradient descent，即随機梯度下降。是梯度下降的batch版本。
對于訓練資料集，我們首先将其分成n個batch，每個batch包含m個樣本。我們每次更新都利用一個batch的資料，而非整個訓練集。即：
xt+1=xt+Δxt
Δxt=−ηgt
其中，η為學習率，gt為x在t時刻的梯度。
這麼做的好處在于：
當訓練資料太多時，利用整個資料集更新往往時間上不顯示。batch的方法可以減少機器的壓力，并且可以更快地收斂。
當訓練集有很多備援時（類似的樣本出現多次），batch方法收斂更快。以一個極端情況為例，若訓練集前一半和後一半梯度相同。那麼如果前一半作為一個batch，後一半作為另一個batch，那麼在一次周遊訓練集時，batch的方法向最優解前進兩個step，而整體的方法隻前進一個step。
SGD方法的一個缺點是，其更新方向完全依賴于目前的batch，因而其更新十分不穩定。解決這一問題的一個簡單的做法便是引入momentum。
momentum即動量，它模拟的是物體運動時的慣性，即更新的時候在一定程度上保留之前更新的方向，同時利用目前batch的梯度微調最終的更新方向。這樣一來，可以在一定程度上增加穩定性，進而學習地更快，并且還有一定擺脫局部最優的能力：
Δxt=ρxt−1−ηgt
其中，ρ 即momentum，表示要在多大程度上保留原來的更新方向，這個值在0-1之間，在訓練開始時，由于梯度可能會很大，是以初始值一般選為0.5；當梯度不那麼大時，改為0.9。η 是學習率，即目前batch的梯度多大程度上影響最終更新方向，跟普通的SGD含義相同。ρ 與 η 之和不一定為1。
這是對傳統momentum方法的一項改進，由Ilya Sutskever(2012 unpublished)在Nesterov工作的啟發下提出的。
其基本思路如下圖（轉自Hinton的coursera公開課lecture 6a）：
首先，按照原來的更新方向更新一步（棕色線），然後在該位置計算梯度值（紅色線），然後用這個梯度值修正最終的更新方向（綠色線）。上圖中描述了兩步的更新示意圖，其中藍色線是标準momentum更新路徑。
公式描述為：
Δxt=ρxt−1−ηΔf(xt−1+ρxt−1)
上面提到的方法對于所有參數都使用了同一個更新速率。但是同一個更新速率不一定适合所有參數。比如有的參數可能已經到了僅需要微調的階段，但又有些參數由于對應樣本少等原因，還需要較大幅度的調動。
Adagrad就是針對這一問題提出的，自适應地為各個參數配置設定不同學習率的算法。其公式如下：
Δxt=−η∑tτ=1gτ+ϵ−−−−−−−−−−√gt
其中gt 同樣是目前的梯度，連加和開根号都是元素級别的運算。eta 是初始學習率，由于之後會自動調整學習率，是以初始值就不像之前的算法那樣重要了。而ϵ是一個比較小的數，用來保證分母非0。
其含義是，對于每個參數，随着其更新的總距離增多，其學習速率也随之變慢。
Adagrad算法存在三個問題
其學習率是單調遞減的，訓練後期學習率非常小
其需要手工設定一個全局的初始學習率
更新xt時，左右兩邊的機關不同一
Adadelta針對上述三個問題提出了比較漂亮的解決方案。
首先，針對第一個問題，我們可以隻使用adagrad的分母中的累計項離目前時間點比較近的項，如下式：
E[g2]t=ρE[g2]t−1+(1−ρ)g2t
Δxt=−ηE[g2]t+ϵ−−−−−−−−√gt
這裡ρ是衰減系數，通過這個衰減系數，我們令每一個時刻的gt随之時間按照ρ指數衰減，這樣就相當于我們僅使用離目前時刻比較近的gt資訊，進而使得還很長時間之後，參數仍然可以得到更新。
針對第三個問題，其實sgd跟momentum系列的方法也有機關不統一的問題。sgd、momentum系列方法中：
Δx的機關∝g的機關∝∂f∂x∝1x的機關
類似的，adagrad中，用于更新Δx的機關也不是x的機關，二是1。
而對于牛頓疊代法：
Δx=H−1tgt
其中H為Hessian矩陣，由于其計算量巨大，因而實際中不常使用。其機關為：
Δx∝H−1g∝∂f∂x∂2f∂2x∝x的機關
注意，這裡f無機關。因而，牛頓疊代法的機關是正确的。
是以，我們可以模拟牛頓疊代法來得到正确的機關。注意到：
Δx=∂f∂x∂2f∂2x⇒1∂2f∂2x=Δx∂f∂x
這裡，在解決學習率單調遞減的問題的方案中，分母已經是∂f∂x的一個近似了。這裡我們可以構造Δx的近似，來模拟得到H−1的近似，進而得到近似的牛頓疊代法。具體做法如下：
Δxt=−∑t−1τ=1Δxτ−−−−−−−−√E[g2]t+ϵ−−−−−−−−√
可以看到，如此一來adagrad中分子部分需要人工設定的初始學習率也消失了，進而順帶解決了上述的第二個問題。
Karpathy做了一個這幾個方法在MNIST上性能的比較，其結論是：
adagrad相比于sgd和momentum更加穩定，即不需要怎麼調參。而精調的sgd和momentum系列方法無論是收斂速度還是precision都比adagrad要好一些。在精調參數下，一般Nesterov優于momentum優于sgd。而adagrad一方面不用怎麼調參，另一方面其性能穩定優于其他方法。
實驗結果圖如下：
Loss vs. Number of examples seen
Testing Accuracy vs. Number of examples seen
Training Accuracy vs. Number of examples seen
最近看到了一個很棒的總結文章，除了本文的幾個算法，還總結了RMSProp跟ADAM（其中ADAM是目前最好的優化算法，不知道用什麼的話用它就對了）
來源： http://blog.csdn.net/luo123n/article/details/48239963
梯度下降（GD）是最小化風險函數、損失函數的一種常用方法，随機梯度下降和批量梯度下降是兩種疊代求解思路，下面從公式和實作的角度對兩者進行分析，如有哪個方面寫的不對，希望網友糾正。
下面的h(x)是要拟合的函數，J(theta)損失函數，theta是參數，要疊代求解的值，theta求解出來了那最終要拟合的函數h(theta)就出來了。其中m是訓練集的記錄條數，j是參數的個數。
1、批量梯度下降的求解思路如下：
（1）将J(theta)對theta求偏導，得到每個theta對應的的梯度
（2）由于是要最小化風險函數，是以按每個參數theta的梯度負方向，來更新每個theta
（3）從上面公式可以注意到，它得到的是一個全局最優解，但是每疊代一步，都要用到訓練集所有的資料，如果m很大，那麼可想而知這種方法的疊代速度！！是以，這就引入了另外一種方法，随機梯度下降。
2、随機梯度下降的求解思路如下：
（1）上面的風險函數可以寫成如下這種形式，損失函數對應的是訓練集中每個樣本的粒度，而上面批量梯度下降對應的是所有的訓練樣本：
（2）每個樣本的損失函數，對theta求偏導得到對應梯度，來更新theta
（3）随機梯度下降是通過每個樣本來疊代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能隻用其中幾萬條或者幾千條的樣本，就已經将theta疊代到最優解了，對比上面的批量梯度下降，疊代一次需要用到十幾萬訓練樣本，一次疊代不可能最優，如果疊代10次的話就需要周遊訓練樣本10次。但是，SGD伴随的一個問題是噪音較BGD要多，使得SGD并不是每次疊代都向着整體最優化方向。
3、對于上面的linear regression問題，與批量梯度下降對比，随機梯度下降求解的會是最優解嗎？
（1）批量梯度下降---最小化所有訓練樣本的損失函數，使得最終求解的是全局的最優解，即求解的參數是使得風險函數最小。
（2）随機梯度下降---最小化每條樣本的損失函數，雖然不是每次疊代得到的損失函數都向着全局最優方向， 但是大的整體的方向是向全局最優解的，最終的結果往往是在全局最優解附近。
4、梯度下降用來求最優解，哪些問題可以求得全局最優？哪些問題可能局部最優解？
對于上面的linear regression問題，最優化問題對theta的分布是unimodal，即從圖形上面看隻有一個peak，是以梯度下降最終求得的是全局最優解。然而對于multimodal的問題，因為存在多個peak值，很有可能梯度下降的最終結果是局部最優。
5、随機梯度和批量梯度的實作差别
以前一篇博文中NMF實作為例，列出兩者的實作差别（注：其實對應Python的代碼要直覺的多，以後要練習多寫python！）
<b>[java]</b> view plain copy
// 随機梯度下降，更新參數
public void updatePQ_stochastic(double alpha, double beta) {
for (int i = 0; i < M; i++) {
ArrayList<Feature> Ri = this.dataset.getDataAt(i).getAllFeature();
for (Feature Rij : Ri) {
// eij=Rij.weight-PQ for updating P and Q
double PQ = 0;
for (int k = 0; k < K; k++) {
PQ += P[i][k] * Q[k][Rij.dim];
}
double eij = Rij.weight - PQ;
// update Pik and Qkj
double oldPik = P[i][k];
P[i][k] += alpha
* (2 * eij * Q[k][Rij.dim] - beta * P[i][k]);
Q[k][Rij.dim] += alpha
* (2 * eij * oldPik - beta * Q[k][Rij.dim]);
}
}
}
// 批量梯度下降，更新參數
public void updatePQ_batch(double alpha, double beta) {
// Rij.error=Rij.weight-PQ for updating P and Q
Rij.error = Rij.weight - PQ;
// 對參數更新的累積項
double eq_sum = 0;
double ep_sum = 0;
for (int ki = 0; ki < M; ki++) {// 固定k和j之後,對所有i項加和
ArrayList<Feature> tmp = this.dataset.getDataAt(i).getAllFeature();
for (Feature Rj : tmp) {
if (Rj.dim == Rij.dim)
ep_sum += P[ki][k] * Rj.error;
}
}
for (Feature Rj : Ri) {// 固定k和i之後,對多有j項加和
eq_sum += Rj.error * Q[k][Rj.dim];
// 對參數更新
P[i][k] += alpha * (2 * eq_sum - beta * P[i][k]);
Q[k][Rij.dim] += alpha * (2 * ep_sum - beta * Q[k][Rij.dim]);
來源： http://blog.csdn.net/lilyth_lilyth/article/details/8973972
梯度下降法的缺點是：
靠近極小值時速度減慢。
直線搜尋可能會産生一些問題。
可能會'之字型'地下降。
三、随機梯度下降法stochastic gradient descent，也叫增量梯度下降
由于梯度下降法收斂速度慢，而随機梯度下降法會快很多
–根據某個單獨樣例的誤差增量計算權值更新，得到近似的梯度下降搜尋（随機取一個樣例）
–可以看作為每個單獨的訓練樣例定義不同的誤差函數
–在疊代所有訓練樣例時，這些權值更新的序列給出了對于原來誤差函數的梯度下降的一個合理近似
–通過使下降速率的值足夠小，可以使随機梯度下降以任意程度接近于真實梯度下降
•标準梯度下降和随機梯度下降之間的關鍵差別
–标準梯度下降是在權值更新前對所有樣例彙總誤差，而随機梯度下降的權值是通過考查某個訓練樣例來更新的
–在标準梯度下降中，權值更新的每一步對多個樣例求和，需要更多的計算
–标準梯度下降，由于使用真正的梯度，标準梯度下降對于每一次權值更新經常使用比随機梯度下降大的步長
–如果标準誤差曲面有多個局部極小值，随機梯度下降有時可能避免陷入這些局部極小值中
來源： http://www.cnblogs.com/549294286/archive/2012/12/13/2817204.html
在應用機器學習算法時，我們通常采用梯度下降法來對采用的算法進行訓練。其實，常用的梯度下降法還具體包含有三種不同的形式，它們也各自有着不同的優缺點。
下面我們以線性回歸算法來對三種梯度下降法進行比較。
一般線性回歸函數的假設函數為：
$h_{\theta}=\sum_{j=0}^{n}\theta_{j}x_{j}$
對應的能量函數（損失函數）形式為：
$J_{train}(\theta)=1/(2m)\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)})^{2}$
下圖為一個二維參數（$\theta_{0}$和$\theta_{1}$）組對應能量函數的可視化圖：
批量梯度下降法（Batch Gradient Descent，簡稱BGD）是梯度下降法最原始的形式，它的具體思路是在更新每一參數時都使用所有的樣本來進行更新，其數學形式如下：
(1) 對上述的能量函數求偏導：
(2) 由于是最小化風險函數，是以按照每個參數$\theta$的梯度負方向來更新每個$\theta$：
具體的僞代碼形式為：
repeat{
（for every j=0, ... , n）
}
從上面公式可以注意到，它得到的是一個全局最優解，但是每疊代一步，都要用到訓練集所有的資料，如果樣本數目$m$很大，那麼可想而知這種方法的疊代速度！是以，這就引入了另外一種方法，随機梯度下降。
優點：全局最優解；
缺點：當樣本數目很多時，訓練過程會很慢。
從疊代的次數上來看，BGD疊代的次數相對較少。其疊代的收斂曲線示意圖可以表示如下：
由于批量梯度下降法在更新每一個參數時，都需要所有的訓練樣本，是以訓練過程會随着樣本數量的加大而變得異常的緩慢。随機梯度下降法（Stochastic Gradient Descent，簡稱SGD）正是為了解決批量梯度下降法這一弊端而提出的。
将上面的能量函數寫為如下形式：
利用每個樣本的損失函數對$\theta$求偏導得到對應的梯度，來更新$\theta$：
1. Randomly shuffle dataset；
2. repeat {
for i=1, ... , $m${
(for j=0, ... , $n$)
随機梯度下降是通過每個樣本來疊代更新一次，如果樣本量很大的情況（例如幾十萬），那麼可能隻用其中幾萬條或者幾千條的樣本，就已經将theta疊代到最優解了，對比上面的批量梯度下降，疊代一次需要用到十幾萬訓練樣本，一次疊代不可能最優，如果疊代10次的話就需要周遊訓練樣本10次。但是，SGD伴随的一個問題是噪音較BGD要多，使得SGD并不是每次疊代都向着整體最優化方向。
優點：訓練速度快；
缺點：準确度下降，并不是全局最優。
從疊代的次數上來看，SGD疊代的次數較多，在解空間的搜尋過程看起來很盲目。其疊代的收斂曲線示意圖可以表示如下：
有上述的兩種梯度下降法可以看出，其各自均有優缺點，那麼能不能在兩種方法之間取得一個折衷呢？即，算法的訓練過程比較快，而且也要保證最終參數訓練的準确率，而這正是小批量梯度下降法（Mini-batch Gradient Descent，簡稱MBGD）的初衷。
MBGD在每次更新參數時使用b個樣本（b一般為10），其具體的僞代碼形式為：
Sayb=10, m=1000.
Repeat{
for i=1, 11, 21, 31, ... , 991{
(for every j=0, ... , $n$)
Batch gradient descent:Use all examples in each iteration；
Stochastic gradient descent:Use 1 example in each iteration；
Mini-batch gradient descent:Use b examples in each iteration.
來源： http://www.tuicool.com/articles/qmqaIbB
來自為知筆記(Wiz)
歡迎轉載，轉載請保留頁面位址。幫助到你的請點個推薦。