> For the complete documentation index, see [llms.txt](https://sejkai.gitbook.io/academic/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sejkai.gitbook.io/academic/deep-learning/improving-deep-neural-networks/optimization_algorithm.md). # Optimization algorithms ## Mini-Batch Gradient Descent * 當 training set 非常大，例如有 m = 5000000 筆時 * Batch gradient descent 需要跑完所有 m 才能進行一次下降 * Mini-batch gradient descent 從 m 中取出一批一批 training set * 假設每 1000 筆一批 * 那就可以執行 5000 次下降 * 全部 5000 筆執行完一次，稱為 1 epoch * 前 1000 筆用 $$(X^{{1}}, Y^{{1}})$$ 表示， * 最後 1000 筆就是 $$(X^{{5000}}, Y^{{5000}})$$ * 每次執行的 gradient descent 和 batch 時一模一樣 * 執行 5000 次完還可以重複進行，直到 converge * 執行多次 epoch * Batch 和 Mini-Batch 的 cost per iteration 如下 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxoj59CJAvAT05Mdu%2Fbatch_vs_mini_batch.png?generation=1572544671998058\&alt=media) ### Mini-Batch Size * Mini-batch size 也是一個需要經驗的 hyperparameter * 當 size = m 時 * 就是原本的 Batch gradient descent * 當 size = 1 時 * 稱為 **Stochastic gradient descent** * 每讀一筆 training set 就做一次 gradient descent ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxoj7w7u7nPOLP2hW%2Fbatch_size_comparison.png?generation=1572544673817702\&alt=media) * Batch Gradient Descent * 對整個 m 進行一次 gradient descent * 下降幅度較大，很穩定往最小值移動 * 每個 iteration **時間很長，訓練過程很慢** * Stochastic Gradient Descent * 速度很快 * 但完全沒享受到 vectorization 的加速優勢 * 永遠不會 converge，會在最小值周圍移動 * 可以用 learning rate decay 解決 * Mini-Batch * 將兩者優點合併，但需要找出適合的 batch size * 若 m 較小，如 $$m \le 2000$$ 可以考慮直接使用 batch gradient descent * 若 m 較大，通常使用 $$2^6, 2^7, 2^8, 2^9$$ 作為 batch size 較好 * 符合電腦 memory 儲存方式 * 另外，size 一定要定義為 CPU/GPU 裝的下的大小 ## Exponentially Weighted Averages * 在實作一些比 gradient descent 還要棒的 optimization algorithm 前 * 需要先學會使用 **Exponentially Weighted Averages** * 這是一種用於分析**移動平均**的算法、像天氣、股票等一連串資訊 * 要試著減緩短期波動、反映長期趨勢 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxoj9WPhza26gzpRi%2Fewa_1.png?generation=1572544672719019\&alt=media) * 例如上圖是倫敦一整年的溫度變化圖 * 我們想算出他的移動平均 (紅線) * 我們定義 $$v\_i$$ 為前一天算完的平均 ($$v\_0 = 0$$) * 定義 $$\theta\_i$$ 為每一天的溫度 * 我們可以用以下算法算出紅線 $$ \begin{aligned} v\_0 &= 0 \\ v\_1 &= 0.9 v\_0 + 0.1\theta\_1 \\ v\_2 &= 0.9 v\_1 + 0.1\theta\_2 \\ \vdots \\ v\_{365} &= 0.9 v\_{364} + 0.1\theta\_{365} \end{aligned} $$ * 可以將以上循環定義為一個簡單公式 * 把 $$v\_t$$ 想成是 $$\approx \frac{1}{1-\beta}$$ 天的溫度 $$ v\_t = \beta v\_{t-1} + (1-\beta) \theta\_t $$ * 所以 $$\beta$$ 是一個 weight，在上面例子是 0.9 * 代表每次得到的 $$v$$ 是平均前 10 天的溫度 * 若設定 $$\beta = 0.98$$ * 每次得到的 $$v$$ 就是平均前 50 天的溫度 * 設定 $$\beta = 0.5$$ * 得到 $$v$$ 為平均前 2 天的溫度 * 所以 $$\beta$$ 越小，代表平均越少前面天數，就會改變的越激烈 * 所以綠線就是平均前 50 天所產生的線 ($$\beta = 0.98$$) * 黃線則是平均前 2 天 ($$\beta = 0.5$$) * 我們這目標是在不同分析中找到類似紅色的線 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxojBi_RTj0BJjgvb%2Fewa_2.png?generation=1572544671372482\&alt=media) ### Understanding Exponentially Weighted Averages * 我們設定 $$\beta = 0.9$$，可以計算出 $$ \begin{aligned} \vdots& \\ v\_{98} &= 0.9v\_{97} + 0.1\theta\_{98} \\ v\_{99} &= 0.9v\_{98} + 0.1\theta\_{99} \\ v\_{100} &= 0.9v\_{99} + 0.1\theta\_{100} \end{aligned} $$ * 然後把計算到 $$v\_{100}$$ 的值攤開 $$ \begin{aligned} v\_{100} &= 0.1\theta\_{100} + 0.1 \times 0.9\theta\_{99} + 0.9v\_{98} \\ &= 0.1\theta\_{100} + 0.1 \times 0.9\theta\_{99} + 0.1 \times 0.9^2\theta\_{98} + 0.9v\_{97} \ &= \cdots \end{aligned} $$ * 因為每個 $$\theta\_i$$ 代表第 i 天的真實溫度 * 每個 $$\theta\_i$$ 前方的 $$0.1 \times 0.9^{(n-i)}$$ 稱為 Bias correction * 所有的 Bias correction 加總會接近或等於 1 * 而真實溫度會隨著 Bias correction 不斷被降低 (被無視) $$ \lim\_{\beta\rightarrow 0}(1-\beta)^{\frac{1}{\beta}} = \frac{1}{e} \approx 0.368 $$ * 上面這個公式代表當 $$\beta = 0.9$$ 時 * 10 天後的溫度在乘上 bias correction 後，已經下降到原本的 1/3 左右 * 所以越往後的溫度根本等於沒有用一樣 * 最後，在計算 exponentially weighted averages 只需要一行程式碼 * 並且只需要一個儲存 v 的 memory 位置 * 因為不需定義所有的 v，只需對同一個 v 進行運算更新即可 $$ \begin{aligned} \text{Repeat : }&\\ \&v := \beta v + (1-\beta) \theta\_t \end{aligned} $$ * 雖然**不會**比你直接計算前 10 天、50 天的平均還要**精準** * 但他只需要一行代碼、而且佔用非常少 memory、效率極高 ### Bias Correction Adjustment ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxojDSfjWGPxvaekT%2Fewa_3.png?generation=1572544669724974\&alt=media) * 實際上會因為 $$v\_t$$ 從 0 開始 * 所以 $$v\_1 = \beta v\_0 + (1-\beta)\theta\_1$$ * 前項完全被消掉，因此第一個 v 僅為當天溫度的 ($$1-\beta$$) 倍 * 會產生紫色線一樣慢熱的狀況 * 我們可以修改 $$v\_t$$ 為以下公式 $$ v\_t = \frac{\beta v\_{t-1} + (1-\beta)\theta\_t}{1-\beta^t} $$ * 這個修正讓 $$v$$ 在一開始可以正常一點 * 而隨著 $$t$$ 越大，$$\beta^t$$ 將趨近於 0，代表整個修正不再影響結果 ## Gradient Descent with Momentum * Momentum 事實上就是對 gradient 進行 Exponentially weighted averages 的計算 * 並用新產生的 gradient 來更新下降 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxojFHHWS40IyT5u_%2Fmomentum_intuition.png?generation=1572544670649266\&alt=media) * 上面用一個 intuition 解釋 * 藍線為一般的 gradient descent * 有一些不往最小值移動的 oscillation * 紫線為 learning rate $$\alpha$$ 特別大的 gradient descent * oscillation 更大，甚至會 overshoot * 我們的目的就是要減少上下擺動的幅度 * 並且維持甚至增加往最小值移動的幅度 * 紅線的部分 * 所以 gradient descent with momentum 的實作如下 $$ \begin{aligned} \text{On iteration t :}&\\ &\text{Compute } dw, db \text{ on current mini-batch} \\ & v\_{dW} = \beta (v\_{dW}) + (1-\beta) dW \\ & v\_{db} = \beta (v\_{db}) + (1-\beta) db \\ \&W = W - \alpha (v\_{dW}) \\ \&b = b - \alpha (v\_{db}) \end{aligned} $$ * 其中 $$v\_{dW}, v\_{db}$$ 就是計算 exponentially weighted averages 的方法 * 而 $$\beta$$ 跟 $$\alpha$$ 一樣，是一個 hyperparameter * 當 $$\beta = 0$$，就等於一般的 gradient descent * 通常會設置 $$\beta = 0.9$$，會很好的得到紅線的效果 * momentum 不需要修正 bias correction * 因為通常移動十次左右，就已經是不錯的移動平均 ## RMSprop * RMSprop 全名為 Root-Mean-Square Propagation * 我們假設 $$w$$ 和 $$b$$ 是主要影響 oscillation 的 parameters * 而 $$b$$ 是影響上下擺動較嚴重的 parameter ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxojImzn6t11byqb8%2Frmsprop_intuition.png?generation=1572544674026706\&alt=media) * 我們先來計算 RMSprop * 為了跟 momentum 區分，RMSprop 中的 $$\beta$$ 改為 $$\beta\_2$$ $$ \begin{aligned} \text{On iteration t :}&\\ &\text{Compute } dw, db \text{ on current mini-batch} \\ & s\_{dW} = \beta\_2 (s\_{dW}) + (1-\beta\_2) (dW)^2 \\ & s\_{db} = \beta\_2 (s\_{db}) + (1-\beta\_2) (db)^2 \\ \&W = W - \alpha \frac{dw}{\sqrt{s\_{dW} + \epsilon}} \\ \&b = b - \alpha \frac{db}{\sqrt{s\_{db} + \epsilon}} \end{aligned} $$ * 因為 $$W$$ 較小，所以用 $$(dW)^2$$ 計算的 $$s\_{dW}$$ 也會較小 * 那麼更新 $$W$$ 時，$$s\_{dW}$$ 在分母，算出來的 $$dw$$ 就適中 * 而 $$b$$ 較大，所以用 $$(db)^2$$ 計算的 $$s\_{db}$$ 就會較大 * 那麼更新 $$b$$ 時，$$s\_{db}$$ 在分母較大，算出來的 $$db$$ 就會變小 * 就可以抑制上下的 osciilation * 另外在分母加上 $$\epsilon$$，是為了防止分母太小，導致數值不穩定 * $$\epsilon$$ 通常為 10e-8 * 這裡只是舉 $$b$$ 為影響上下擺動嚴重的 parameter * 實際例子可能為 $$w\_1, w\_2, w\_3, \cdots$$ 是影響上下擺動的原因 * 而 $$w\_4, w\_5, \cdots$$ 是不影響的 * $$\beta\_2$$ 也是一個 hyperparameter ## Adam * Adam 的全名為 Adaptive Moment Estimation * Adam 將 momentum 和 RMSprop 融合在一起，得到更好效果 * 以下是 Adam 算法 * 初始化以下參數 $$v\_{dW} = 0, v\_{db} = 0, s\_{dW} = 0, s\_{db} = 0$$ * 在每個 itetation t 進行計算 * 在 momentum 部分的 $$\beta$$ 用 $$\beta\_1$$ 表示 * 在 RMSprop 部分的 $$\beta$$ 用 $$\beta\_2$$ 表示 $$ \begin{aligned} &\text{Compute } dw, db \text{ on current mini-batch} \\ \&v\_{dW} = \beta\_1 (v\_{dW}) + (1-\beta\_1) dW \\ \&v\_{db} = \beta\_1 (v\_{db}) + (1-\beta\_1) db \\ \&s\_{dW} = \beta\_2 (s\_{dW}) + (1-\beta\_2) (dW)^2 \\ \&s\_{db} = \beta\_2 (s\_{db}) + (1-\beta\_2) (db)^2 \end{aligned} $$ * 接著在 Adam，要對這四個參數進行 bias correction adjustment $$ \begin{aligned} v\_{dW}^{\text{corrected}} &= \frac{v\_{dW}}{1-\beta\_1^t} \\ v\_{db}^{\text{corrected}} &= \frac{v\_{db}}{1-\beta\_1^t} \\ s\_{dW}^{\text{corrected}} &= \frac{s\_{dW}}{1-\beta\_2^t} \\ s\_{db}^{\text{corrected}} &= \frac{s\_{db}}{1-\beta\_2^t} \end{aligned} $$ * 最終更新參數 $$w, b$$ $$ \begin{aligned} W &= W - \alpha \frac{v\_{dW}^{\text{corrected}}}{\sqrt{s\_{dW}^{\text{corrected}} + \epsilon}} \\ b &= b - \alpha \frac{v\_{db}^{\text{corrected}}}{\sqrt{s\_{db}^{\text{corrected}} + \epsilon}} \end{aligned} $$ #### Hyperparameter choices * 以上就是整個 Adam 算法 * 在這個算法中出現非常多 hyperparameters * 要怎麼設置以下一一介紹 * $$\alpha$$ : learning rate，需要自己慢慢找到一個合適的 * $$\beta\_1$$ : momentum 使用到的像 exponentially weighted averages 的 weight * 常用的設定為 0.9 * $$\beta\_2$$ : RMSprop 所使用到的 $$\beta$$，一樣是由 exponentially weighted averages 而來 * Adam 作者建議設定為 0.999 * $$\epsilon$$ : 不重要，用預設的 10e-8 即可 * $$\beta\_1, \beta\_2, \epsilon$$ 通常不太需要去修改調整 ## Learning Rate Decay * 若使用固定 $$\alpha$$ 的 mini-batch，那麼 gradient descent 幾乎不會準確 converge * gradient descent 將會在最小值周圍擺動 * 為此我們可以讓 $$\alpha$$ 隨著時間慢慢減少 * 一開始 $$\alpha$$ 較大，幫助我們跨大步伐 * 最終 $$\alpha$$ 變小，幫助我們在最小值收斂 * 最常用的 learning rate decay 公式如下 $$ \alpha = \frac{1}{1 + \text{decay-rate} \times \text{epoch-num}} \times \alpha\_0 $$ * $$\alpha\_0$$ 是初始的 learning rate * `k epoch` 代表所有 mini-batch 全跑過 k 遍 * `decay-rate` 是一個 hyperparameter * 假設我們設計 $$\alpha\_0 = 0.2, \text{decay-rate = 1}$$ * 那 $$\alpha$$ 將會隨著跑過所有 mini-batch 的次數而下降 | Epoch | $$\alpha$$ | | ----- | ---------- | | 1 | 0.1 | | 2 | 0.067 | | 3 | 0.05 | | 4 | 0.04 | | ... | ... | ### Other Learning Rate Decay Formula * Exponentially Decay $$ \alpha = 0.95^{\text{epoch-num}}\times\alpha\_0 $$ * $$ \alpha = \frac{\text{constant}}{\sqrt{\text{epoch-num}}}\times\alpha\_0 $$ * $$ \alpha = \frac{\text{constant}}{\sqrt{\text{mini-batch-num t}}}\times\alpha\_0 $$ * Discrete staircase * Manual decay : Only small num training set ## Problem of Local Optima * 在 machine learning 時，我們對梯度接近 0 的想像都是 local optima * 圖面上很多凹點，然後你隨便掉進一個凹點就出不來 * 但在 deep learning 中，你的維度變的非常大 * 通常會遇到梯度接近 0 的地方是 **saddle point** * 所以在大型的 nn、有著大量參數、較高維度時 * 困在 local optima 的情況是不太可能的 * 所以 deep learning optimization 的問題不是 local optima 而是 **plateaus** * 這個 saddle point 或者 plateaus 會使得 learning 速度變慢 * 所以才會不斷的推出新的 optimization algorithm * Momentum, RMSprop, Adam, ... * 這些算法能夠加速離開這些梯度接近 0 的點 * 甚至找出更棒的 optimization algorithm 是 deep learning 的挑戰之一 ![](https://2991100231-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LhyC30yNfTP1YdCIj83%2F-LsXxlkZOmtOR6BBD8Av%2F-LsXxojRdQW1Hwp8cvpr%2Flocal_optima_saddle_point.png?generation=1572544673523382\&alt=media)