這一周的主題是優化算法。
?
1. ?Mini-batch：
上一門課討論的向量化的目的是去掉for循環加速優化計算，X = [x(1) x(2) x(3) ... x(m)]，X的每一個列向量x(i)是一個樣本，m是樣本個數。但當樣本很多時（比如m=500萬），向量化依然不能解決問題。所以提出了mini-batch的概念（Batch是指對整個樣本都操作，mini-batch指只對所有樣本的子集進行操作）。把若干樣本合并成一個mini-batch，比如這里選擇1000，X{1} = [x(1) x(2) ... x(1000)]，X{2}?= [x(1001)?x(1002)?... x(2000)]，等等。則我們一共有5000個mini-batch，此時 X = [X{1} X{2} ... X{5000}]。同樣的，把輸出Y也做這樣的操作，得到 Y = [Y{1} Y{2} ... Y{5000}] 。
Notation：x(i)表示第i個樣本，z[l]表示第l層的z值，X{t}表示第t個mini-batch。
具體算法：
repeat { #不斷重復迭代優化for t = 1, ..., 5000 { #對于普通的batch處理手段，遍歷一次樣本更新一次參數。而在mini-batch的方法中，遍歷一次樣本更新了5000次參數。Forward prop on X{t} #用向量化的手段依次處理每一個mini-batchZ[1] = W[1]X{t} + b[1]A[1] = g[1](Z[1])...A[l] = g[l](Z[l])Compute cost J = 1/1000*(∑L(y_hat(i), y(i))）+ 正則化項Back prop to compute gradients with respect to J{t} (using X{t}, Y{t})W[l] = W[l] - αdW[l], b[l] = b[l] - αdb[l]}
}
對于batch處理方式來說，cost function J隨著優化的進行是越來越小的，單調遞減。而對于mini-batch的處理方式來說，則是震蕩著下降，或者說下降的曲線夾雜了噪音。
一個超參數是mini-batch的大小，size。如果size = m，則意味著就是batch gradient descent，用整個數據集訓練。如果size = 1，則是stochastic gradient descent，每個樣本都是獨立的mini-batch。前者的問題是每次迭代的計算太費時，后者的問題是隨機性太嚴重，效率過于低下，失去了向量化帶來的加速計算效果。mini-batch的大小介于兩者之間，能獲得平衡的效果，一方面有向量化的加速效果，另一方面又不需要計算全部樣本。關于mini-batch的大小，NG的建議：1）如果小數據集（少于2000），直接使用batch方法；2）一般的mini-batch大小是64~512，考慮到CPU/GPU的內存存儲方式，2的冪的大小算得更快。不用擔心mini-batch的大小不能整除樣本數的問題，最后一個樣本就少一點沒事。也有人用1024，但不常見。這是一個超參數，所以NG建議多嘗試幾個不同的2的冪，找個最好的。mini-batch越大，減少了噪音，也減少了正則化效果。
?
def random_mini_batches(X, Y, mini_batch_size = 64, seed = 0):"""Creates a list of random minibatches from (X, Y)Arguments:X -- input data, of shape (input size, number of examples)Y -- true "label" vector (1 for blue dot / 0 for red dot), of shape (1, number of examples)mini_batch_size -- size of the mini-batches, integerReturns:mini_batches -- list of synchronous (mini_batch_X, mini_batch_Y)"""np.random.seed(seed) # To make your "random" minibatches the same as oursm = X.shape[1] # number of training examplesmini_batches = []# Step 1: Shuffle (X, Y)permutation = list(np.random.permutation(m))shuffled_X = X[:, permutation]shuffled_Y = Y[:, permutation].reshape((1,m))# Step 2: Partition (shuffled_X, shuffled_Y). Minus the end case.num_complete_minibatches = math.floor(m/mini_batch_size) # number of mini batches of size mini_batch_size in your partitionningfor k in range(0, num_complete_minibatches):mini_batch_X = shuffled_X[:, k*mini_batch_size : (k+1)*mini_batch_size]mini_batch_Y = shuffled_Y[:, k*mini_batch_size : (k+1)*mini_batch_size]mini_batch = (mini_batch_X, mini_batch_Y)mini_batches.append(mini_batch)# Handling the end case (last mini-batch < mini_batch_size)if m % mini_batch_size != 0:mini_batch_X = shuffled_X[:, (k+1)*mini_batch_size : m-1]mini_batch_Y = shuffled_Y[:, (k+1)*mini_batch_size : m-1]mini_batch = (mini_batch_X, mini_batch_Y)mini_batches.append(mini_batch)return mini_batches
2.?指數加權平均（指數加權移動平均）：
vt = βvt-1 + (1-β)θt 。這個公式可以看成 vt?近似等于 1/(1-β) 個數據的平均值，比如β = 0.9，則近似可以看成是10個數據的平均值。展開來看，vt = (1-β)*θt? + (1-β)*β*θt-1? + (1-β)*β2*θt? + ...(1-β)*βn*θt?，權重指數衰減。（為什么近似等于1/(1-β) 個數據的平均值？NG解釋說，如果β接近1，β1/(1-β)≈1/e=0.37，0.37的權重已經很小了，所以說近似等于 1/(1-β) 個數據的平均值。）
指數加權平均的一大好處是可以迭代計算，占內存很小。相比之下，如果記錄過去n個數值，然后算平均數，顯然耗內存很多。
偏差矯正：偏差產生的原因是頭部缺數據，造成求得的指數加權平均比較小。偏差矯正的公式是 vt?/ (1 -?βt)，注意這里是計算完vt后矯正，而不是在迭代過程中實時矯正。直觀地說，如果β大，比如0.98，則需要平均更多的數據，于是1 -?βt更小，從而把 vt?放大。
?
3. Momentum (Gradient descent with momentum)
這種方法幾乎總是比標準的梯度下降快。基本想法是：用梯度的指數加權平均數來更新權重。如果優化的問題有大的condition number，則優化過程中，會在一個方向劇烈震蕩。這導致我們只能選用小的學習率，降低了優化的速度。如果學習率大，很容易就發散了。我們希望的是在震蕩的方向上迭代步長小一點，而在沒有震蕩的方向上迭代步長大一點。指數加權平均的做法在震蕩方向上把數據正負抵消了，所以得到很小的數，而在沒有震蕩的方向上則持續增加。物理的直觀解釋是想象一個小球從碗的邊沿滾下去，梯度是它的加速度，momentum是它的速度，β是和摩擦力相關的量。相比于標準的梯度下降，當前迭代只與當前梯度相關，而momentum的方法把當前迭代和過往梯度也聯系起來。
具體算法：
vdW = 0,?vdb = 0
對于每一步的迭代：
計算當前mini-batch的梯度dW, db。
vdW =?βvdW + (1-β)dW ?# NG解釋說也有的教材寫成 vdW?=?βvdW?+ dW，他自己不喜歡這種，因為更難調參數，調β的時候，會再需要調α。
vdb =?βvdb + (1-β)db
W = W -?αvdW, b = b-?αvdb
α和β是超參數，不過經驗上看β取0.9是非常不錯的。一般人們不用偏差矯正，因為通過初始階段后就無偏了。
?
4. RMSprop(Root mean square prop): NG說這個方法最開始是Geoffrey Hinton在coursera的課上提出來的。
具體算法：
SdW = 0,?Sdb?= 0
對于每一步的迭代：
計算當前mini-batch的梯度dW, db。
SdW?=?βSdW?+ (1-β)dW2? ?#?dW2是把向量的每個元素各自平方。
Sdb?=?βvdb?+ (1-β)db2
W = W -?αdW/(sqrt(SdW)+ε), b = b-?αdb/(sqrt(Sdb)+ε) # 分母加上ε為了防止除以0的情況，ε可以隨便設一個很小的數，比如e-8
直觀地解釋：對于震蕩的優化方向，S值會比較大，從而更新參數時步長會比較小，從而消除震蕩。
?
5. Adam(Adaptive moment estimation)：將Momentum和RMSprop結合起來。
具體算法：
vdW = 0，SdW = 0,??vdb?= 0，Sdb?= 0
對于每一步的迭代：
計算當前mini-batch的梯度dW, db。
vdW?=?β1vdW?+ (1-β1)dW，vdb?= β1vdb?+ (1-β1)db ?# β1對應Momentum。
SdW?=?β2SdW?+ (1-β2)dW2?， Sdb?= β2vdb?+ (1-β2)db2? #?β2對應RMSprop。
vdW_corrected = vdW / (1 -?β1t)，vdb_corrected?= vdb?/ (1 -?β1t)，
SdW_corrected?= SdW?/ (1 -?β2t)，Sdb_corrected?= Sdb?/ (1 -?β2t)，
W = W -?αvdW_corrected?/ (sqrt(SdW_corrected)+ε),?b = b -?αvdb_corrected?/ (sqrt(Sdb_corrected)+ε)
超參數：α需要調試，β1可以設為0.9，β2可以設為0.999，ε可以設為e-8。一般大家都只調α，另外幾個就按照默認值。
Adam非常非常牛逼，默認選項。
?
6. 學習率衰減(Learning rate decay)：
1 epoch的意思是遍歷一次數據集。
一種典型的decay方法：α = α0?/ (1+decay_rate*epoch_num)，decay_rate是另一個需要調的超參數。
其他decay方法：α = 0.95epoch_numα0；α = k*α0?/ sqrt(epoch_num)；α = k*α0?/ sqrt(t)，t是迭代次數；還有分段離散衰減的。
NG說學習率衰減并不是他優先考慮的東西，他優先還是選一個好一些的固定的α。
?
7. 深度學習中的局部最優：
傳統的理解中，局部最優是要避免的。但是在深度學習優化的問題里（比如有2萬個參數，或者說在2萬維的空間），梯度為0的點往往并不是局部最優，而是鞍點。NG說：我們對低緯度空間的大部分直覺不能應用到高緯度空間中。所以深度學習的優化中，并不擔心陷入局部最優，而是擔心在平穩段（導數在很大的區域都接近0）優化變慢。Momentum、RMSprop、Adam等算法可以加速對平穩段的優化。
?
?
?
?
?
?
?
)
