為了使模型做出正確的預測，需要透過不斷的修正模型的參數。修正過程越穩定，模型的可再現性也就越高。如此尋找最佳解的過程稱之為參數的「最佳化(optimization)」。前半段我會解釋為什麼大家都使用數值法，後半段介紹常見的最佳化手段Adam 及最佳化陷阱：區域最小值以及調速問題。
何不使用解析解一步登天？
解開微分方程組的方法有以下兩種，「解析解(analytical solution)」與「數值解(numerical solution)」。本篇著重於使用數值解尋求最佳解。但在此之前，我想問為什麼不能用解析解一步登天？一言以蔽之就是太貴了，無論是時間上或是資源上都要付出難以想像的代價。構成機器模型的方程式通常是非線性的，也就是說參數有很大的機率彼此相乘。在數學上找出非線性二元二次微分方程組可以是工程數學裡的一個章節，甚至出個五題就足以打發一次期中考。這是我大學時的應用數學課本的目錄，其中偏微分方程式是獨立一個章節，使用很大的篇幅解釋要怎麼排除變數之間的影響。若能夠假設為線性變數的題目都很好解，不能的只能用特殊解法解開、又不好背，因為不同的代數關係有不同的特殊解法。很難想像需要多少時間得到上千萬的參數構成的機器模型的解析解。由於太過困難，解析解鮮少用在更新機器參數上。
慢慢用數值解比較快
只要方程式是非線性的，那麼就很難更新參數。每改變一個參數，另一個參數的輸出就會受到影響，因此在更新的時候必須全盤考慮，不能一次只更新一兩個參數。若要降低非線性項的影響，就必須要降低更新的步伐，一次只改變一點點。舉個例子，令$L$是預測與真實的差距，預測模型具有$x$與$y$兩個參數，$L$在$x_0$的泰勒展開如下式一：
$ L(x,y) = L(x_0,y) + \frac{1}{1!}\frac{d}{dx}L(x,y)\cdot(x – x_0) + \frac{1}{2!}\frac{d^2}{dx^2}L(x,y)\cdot(x – x_0)^2 +… $ (1)
我們想知道如果$x$改變了一點點，對$\frac{dL}{dy}$有多大的影響？所以讓我們令$x = x_0 + \Delta x$，如下式二：
$ L(x_0 + \Delta x,y) = L(x_0,y) +
\frac{1}{1!}\frac{d}{dx}L(x_0 + \Delta x, y)\cdot \Delta x +
\frac{1}{2!}\frac{d^2}{dx^2}L(x_0 + \Delta x, y)\cdot \Delta x^2 + … $ (2)
我們將式二對$y$微分後稍微移項一下，得到式三：
$ \frac{d}{dy}L(x_0 + \Delta x,y) = \frac{d}{dy}L(x_0,y) +
\frac{1}{1!}\frac{d}{dy}\frac{d}{dx}L(x_0 + \Delta x, y)\cdot \Delta x +
\frac{1}{2!}\frac{d}{dy}\frac{d^2}{dx^2}L(x_0 + \Delta x, y)\cdot \Delta x^2 + … $
$ \frac{d}{dy}L(x_0 + \Delta x,y) – \frac{d}{dy}L(x_0,y) =
\frac{1}{1!}\frac{d}{dy}\frac{d}{dx}L(x_0 + \Delta x, y)\cdot \Delta x +
\frac{1}{2!}\frac{d}{dy}\frac{d^2}{dx^2}L(x_0 + \Delta x, y)\cdot \Delta x^2 + … $ (3)
式三就是$x$改變一點點之後，對$\frac{dL}{dy}$造成的影響。因為$\Delta x$總是出現在分子，所以足夠小的話，$x$改變一點點的影響是可以忽略掉的。
歸一化與梯度
在更新機器模型之前，我們要先知道其輸出的意義。因為篇幅有限還有方便起見，今天我們先暫時假設想要知道的是某件事的機率。機器模型本身是一個非線性方程式，其輸出可能有很多項介於無限大到負無限大之間的數，不一定符合機率的定義，我們需要做一些規範使方程式的輸出符合機率的定義。首先是歸一性，使機率總和為一；第二、每一項的值都要不小於零。機器學習領域通常使用Softmax函數，因為它能簡化參數對損失函數的微分。舉個例子，令機器模型如下式四：
$ \vec a = f(x) $
where $ \vec a = (a_1, a_2, …, a_n) $ (4)
令$q_i$為$a_i$套上Softmax歸一化後的值，算法如下式五：
$ q_j
= P_{\theta}(j|x)
= Softmax(a_j)
= \frac{e^{a_{j}}}{\Sigma_i e^{a_{i}}} $ (5)
式五的意思是，給定輸入為$x$，這個機器模型認為j是答案的機率為$q_j$。接著令損失函數為KL divergence，其意思是預測與真實之間令人驚訝程度的差距。由於篇幅的關係，想知道原因的可以看這篇這裡。這是一個用來衡量猜錯的程度的好指標。KL divergence長得像式六：
$ D_{KL}= H(\vec p) – H(\vec p, \vec q) $
where $H(\vec p)$ is entropy, $H(\vec p, \vec q)$ is cross-entropy, $\vec p$ is true value, and $\vec q$ is predict value. (6)
由於$\vec{p}$ 與模型無關，$\vec{p}$ 對模型的任一個參數或輸出微分都是零，我們在計算微分時可以忽略$\vec{p}$ 。我們的目標是算出機器模型參數對損失函數的微分，如式七：
$ \frac{\partial D_{KL}}{\partial \theta}
= – \Sigma_i \frac{\partial H(\vec{p}, \vec{q})}{\partial a_i} \cdot
\frac{\partial a_i}{\partial \theta} $ (7)
其中，$\partial a_i / \partial \theta$ 跟損失函數無關，只跟模型本身的架構有關。它不一定為零，但下面不做推導，我們把重點放在機器模型原輸出$\partial a_i$ 對交叉熵$H(\vec{p}, \vec{q})$的微分：
$ \frac{\partial H(\vec{p},\vec{q})}{\partial a_j}
= -\Sigma_i \frac{\partial H(\vec{p},\vec{q})}{\partial q_i} \cdot \frac{\partial q_i}{\partial a_j} $
$-\frac{\partial H(\vec{p},\vec{q})}{\partial q_i} = -\frac{\partial}{\partial q_i} p_i \cdot log(q_i)
= -\frac{p_i}{q_i} $
Let $q_j = e^{a_j} \cdot S^{-1}$, where $S = \Sigma_i e^{a_i}$
$ \frac{\partial q_i}{\partial a_j} = \frac{\partial}{\partial a_j}(e^{a_i} \cdot S^{-1}) =
e^{a_i}(-S^{-2}\cdot e^{a_j}) =
-q_i \cdot q_j $, if $i \neq j$.
$ \frac{\partial q_i}{\partial a_j} =
\frac{\partial}{\partial a_j}(e^{a_i} \cdot S^{-1}) =
\frac{\partial}{\partial a_i}(e^{a_i} \cdot S^{-1}) $, if $i = j$.
$ \frac{\partial}{\partial a_i}(e^{a_i} \cdot S^{-1}) = e^{a_i}\cdot S^{-1} + (-S^{-2}\cdot e^{2a_j})
= (e^{a_i}\cdot S^{-1})\cdot (1 – S^{-1}\cdot e^{a_i})
= q_i \cdot (1 – q_i)
= q_i – q_i^2 $
$ \implies \frac{\partial D_{KL}}{\partial a_j} = -\Sigma_{i \neq j} p_i \cdot q_j + \Sigma_{i = j} p_i \cdot (1 – q_i)
= p_j -\Sigma_i p_i \cdot q_j
= p_j – q_j $ (8)
由於人類偏好數學上看起來簡單的答案，Softmax與KL divergence也因此經常一起使用。我不知道漂亮的答案對於模型的穩定度有沒有關係，但肯定能讓後面的計算更容易一些，因為只有牽涉到加減一個數，避免多餘的乘法除法以及相對應的例外處理。到這裡還沒結束，因為我們想要的是更新參數用的梯度，把式八的結果套回式七，結果如式九：
$ \frac{\partial D_{KL}}{\partial \theta}
= \Sigma_i \frac{\partial D_{KL}}{\partial a_i} \cdot
\frac{\partial a_i}{\partial \theta}
= \Sigma_i (p_i – q_i) \cdot \frac{\partial a_i}{\partial \theta} $ (9)
式九即為梯度，也是更新模型參數的基礎。以下的最佳化手段也是基於梯度演化而來的。
機器學的是什麼？
目前我們討論過的最佳化手段時僅考慮過機率模型。如果是想要求得兩真實事物的關係、例如房型與房價，那麼就不能用機率來描述輸出了，KL divergence配Softmax那一套也不能使用了。但我們並不是束手無策，用傳統的Mean Square Error（平均方差）來更新方程式。另外、如果是要輸出圖片，因為通常色彩的範圍有限，可以使用Sigmoid輸出函數。很特別的是Sigmoid可以跟KL divergence搭配使用。下面介紹的最佳化策略並沒有要求輸出必須符合機率的定義，在大部分的命題中都是可用的。
有了梯度後，應該走多大步？
有了梯度之後，梯度的方向就是當前最佳化的方向，但控制一次要走多大步是一件困難的事。參數空間在任何一點的梯度都是未知的，除非真的走到那一點並計算梯度。我們希望更新參數的時候可以考慮梯度，令參數為$\theta$，更新的方法寫作下式十：
$ \theta_{t+1} = \theta_{t} – \eta \cdot \frac{dL_{t}}{d\theta_{t}} $ (10)
式十的作法叫做Stochastic Gradient Decent(SGD)，也是最基礎的最佳化方法之一。$t$代表世代，下一個世代的參數$\theta_{t+1}$等於原本的數值$\theta_t$減去梯度乘上一個學習率$\eta$。學習率(learning rate)是用來調整梯度的尺度(scale) 用的，會影響到更新參數的大小。完成上述的計算後後，我們要在新的參數上再測量一次梯度、再一次更新參數等等不斷循環。重複上述的行為無數次，直到模型的輸出非常接近訓練資料。學習率高的話模型更新的速率快，但是比較難接近最佳解，反之亦然。通常我們會希望能夠偶爾調控更新的步伐來達到理想的訓練效果。
Adam：最泛用的最佳化算法
僅僅使用梯度以及學習率的SGD在訓練模型時的穩定度很差，因為某些特殊的參數空間可能會把SGD困住。有兩件事情SGD難以克服，第一點是時不時遇到的局部最小值，容易使模型困在裡頭離不開；第二是學習率太大導致無法接近最佳解，只能在最佳解附近的參數空間繞圈圈。
利用動量跨過局部最小值
在參數空間中，偶爾會發現局部的最小值。舉滑雪場的例子，在起點跟終點之間偶爾會有些地方相對平坦，讓運動員在中間停下來欣賞風景。這點參數空間也是一樣的，偶爾會有相對平坦的參數空間。梯度在平坦的參數空間時只有很小的值，但是我們不希望最佳化的過程因此停下來。只依照當前的梯度更新參數是無法有效離開局度最小值附近的。如果考慮更之前的梯度，就像是物理的動量一樣，就可以克服比較小的局部最小值。更新參數的算法如下式十一：
$ t \leftarrow t+1 $
$ g_t \leftarrow \partial_\theta f_t(\theta_{t-1}) $
$ m_t \leftarrow \beta m_{t-1} – (1-\beta) \cdot g_t $
$ \hat{m_t} \leftarrow m_t/(1 – \beta^t) $
$ \theta_{t} = \theta_{t-1} – \eta \cdot \hat{m_t} $ (11)
請讓我用文字的方式解釋式十一。假設現在我們走在第$t$ 步，思考著要怎麼邁出第$t+1$ 步。首先我們算了所在參數空間的梯度$g_t$ 。然後我們也參考了前幾步的梯度，那些梯度可以幫助我們理解較大範圍內的梯度平均情形。因為這些梯度是以一階的方式相加而成，那些梯度的總和我們稱之為「動量」。我們也相信越久以前的梯度越不重要，所以在計算動量時會乘上衰退係數$\beta$，確保以前的梯度的影響會越來越小。算動量時還要注意一件小事。如果第t次更新參數前的梯度都是零，也就是$t-1$ 的動量為零的話，我們希望第$t$ 次的動量跟梯度一樣。所以動量$m$ 要校正為$\hat{m}$ 。最後，新的參數$\theta$ 等於舊的參數減去動量$\hat{m}$乘上學習率$\eta$。
我們很順利的通過一連串高低起伏，雖然偶有窪地，但是我們很清楚目標不在那裡。我們利用「動量」，也就是大範圍的平均梯度，順利的通過了那些陷阱。現在我們已經很接近終點，也就是最佳解。由於我們定義的預測方程式幾乎*處處可微，所以在最佳解附近的斜率都會很接近0。如果用地形來想像的話，那就是一小段平原，但周圍有數座大山包圍。
- 如果使用ReLU作為activation function的話會有一些點不可微，但是相對於廣褒的參數空間可以忽略。同理可證其他的activation function。
利用動能慢行於過陡的山坡
這下麻煩了，我們沒辦法停在最佳解平原上。因為山坡太陡，所以每更新一次參數，就會從一邊的山坡爬到另一邊。那邊的山坡也差不多陡，所以又一次更新參數之後，又爬上了另一個山坡。我們希望在平原上快跑，但是在山坡上慢行，這樣才不會錯過最佳解。讓我們看看式十二：
$ t \leftarrow t+1 $
$ g_t \leftarrow \partial_\theta f_t(\theta_{t-1}) $
$ v_t \leftarrow \beta_2 v_{t-1} – (1-\beta_2) \cdot g_t^2 $
$ \hat{v_t} \leftarrow v_t/(1 – \beta_2^t) $
$ \theta_{t} = \theta_{t-1} – \eta \cdot \frac{g_t}{\hat{v_t}+\epsilon} $ (12)
這個算法的核心概念是，如果走過的路越長，那麼下一步就越短。讓我們一樣用文字來理解式十二想要表達的事情：假設現在我們走在第$t$ 步，思考著要怎麼邁出第$t+1$ 步。首先我們算了所在參數空間的梯度$g_t$ 。然後我們也希望參考前幾步的梯度，那些梯度可以幫助我們理解最近走了多遠。如果走了很遠，那有可能附近的梯度很大，要走慢一點，反之亦然。因為是以二階的方式相加而成，那些梯度的總和我們稱之為「動能」。我們也相信越久以前的梯度越不重要，所以在計算動能時會乘上衰退係數$\beta_2$ ，確保以前的梯度的影響會越來越小。算動能時還要注意一件小事。如果第t次更新參數前的梯度都是零，也就是$t-1$ 的動能為零的話，我們希望第t次的動能跟梯度一樣。所以動能$v$ 要校正為$\hat{v}$ 。最後，新的參數$\theta$等於舊的參數減去梯度$g_t$ 乘上學習率$\eta$ 除以動能$\hat{v}$ 。看到了除法，記得程式上我們要避免除以零造成的奇點問題，所以我們在分母必須放一個很接近但不是零的數來避免除以零。
在平原快跑、在山坡慢行
以上我提到的是Adam算法的兩大部分，「動量」與「動能」。合在一起看的話如式十三。Adam考慮了「附近的斜率」還有「最近走了多遠」。前者可以幫助我們跨過局部最小值；後者可以提醒我們在山坡上走慢一點，在平地上走快一點。經驗上Adam非常泛用，大部分的深度學習模型都可以透過使用Adam得到性能提升。Adam有三個參數可以微調，$\beta_1$、$\beta_2$與$\epsilon$。實際上這三個參數幾乎不用調整，Adam的原作者提供的數值0.9, 0.999, and $10^{-8}$就已經很好用了，而調整後也通常不會比較好。順帶一提，Adam並不是從天而降的，「動量」與「動能」的概念分別參考自RMSprop與Adagrad。我認為學問從來不是一蹴而就的，那些璀璨的成果，背後都有無數的努力在支撐。如果僅僅以天才來稱讚科學家，那就太瞧不起他們曾經付出的努力了。
$ t \leftarrow t+1 $
$ g_t \leftarrow \partial_\theta f_t(\theta_{t-1}) $
$m_t \leftarrow \beta_1 m_{t-1} – (1-\beta_1) \cdot g_t $, where $\beta_1 = \beta$ in eq(11)
$ \hat{m_t} \leftarrow m_t/(1 – \beta_1^t) $
$ v_t \leftarrow \beta_2 v_{t-1} – (1-\beta_2) \cdot g_t^2 $
$ \hat{v_t} \leftarrow v_t/(1 – \beta_2^t) $
$ \theta_{t} = \theta_{t-1} – \eta \cdot \frac{\hat{m_t}}{\sqrt{\hat{v_t}+\epsilon}} $ (13)
小結
我們介紹了機器模型如何透過數值法尋找最佳解，涵蓋了梯度計算以及常見的最佳化手段。我個人常發生的錯誤是忘記確認方程式的輸出是否符合機率的定義。根據目的不同，有的時候不一定會用機率來描述輸出。最佳化手段相對機器模型是比較成熟的部分，大多數的情況直接使用Adam都不會出錯，跟各種複雜的模型相比，是一種不太需要調整的一種超參數(hyper-parameter)。
備註
我很猶豫要不要寫這個主題，因為Adam在2014年後已成為最佳化方法的主流。現今大多數的開發者在想新算法時，也很少考慮Adam以外的可能性。網路上已經有很多Adam相關的介紹文，我的描述連錦上添花都談不上。但如果我要達到我的目標，也就是強化機器學習相關知識，那麼介紹最佳化手段就是不可逃避的關卡。另一方面，機器學習會用到的最佳化手段很少用在其他目的。也就是說，我應該要預期讀者們可能不熟悉這些最佳化手段。綜上所述，若要使作品完整，介紹最佳化手段是必要的。
參考
[機器學習] Backpropagation with Softmax / Cross Entropy, Hoskiss 2019
Cross Entropy and KL Divergence, Tim Hopper
ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION, Diederik P. Kingma, Jimmy Lei Ba