[探索] 門外漢的梯度下降變奏曲（上）

更新於 2020/04/06發佈於 2020/04/06閱讀時間約 20 分鐘

在上篇中，我們提到了一個使用一階微分當作前往全域最小值的方向和步長的演算法。這個被稱為梯度下降學習法，雖然提出了一個有效的方法來達到最小值，然而因為梯度本身屬於局部變化，卻也註定了它難逃以下三個陷阱，而未能到達全域最小值（Global Minimum）的命運。他們分別是：

局部最小值，平坦區域和鞍點

如前所述，由於梯度是屬於量度局部變化，這個只有局部視角的量度，讓我們如井底窺天，無法確認目前所到達的最小值是否為損失函數的全域最小值或僅僅是局部最小值。通常，局部最小值不會帶給我們的最佳化演算法麻煩，我們甚至可以假設，由於類神經網路的拓樸結構可藉由任意排列，而擁有許多等價網路。這些等價的網路，使類神經網路難有單一確定性（Model Identifiable）「註ㄧ」，也使許多局部最小值存在於損失函示表面。

但容忍許多等價網路模型所產生局部最小值並不等同於容忍最佳化演算法被困入局部最小值，當滯留的最小值區域並不是全損失函數中的全域最小點。任何損失函示中的平坦區域「註二」都有可能落在這個陷阱中，而造成最佳化演算法停滯不前。其中一個在高維的特徵空間中最常見的為鞍部（Saddle）。

鞍部指的損失函數在三度空間中像馬鞍的形狀，該形狀，從一截面看去，會成為一個開口向上的拋物線平面，也就是局部最小值所在位置。然而從另一截面看去，卻是一個開口向下的拋物線平面，卻是局部最大值所在位置（如下圖）。鞍部中這兩種截然不同的剖面圖形的交點被稱為鞍點（Saddle Point），該點的一階導數或梯度為零，然而卻不是全域最大或最小值。

鞍部在三維空間中。在 xy，yz 和 xz 平面上的等高線圖為鞍部在該平面的投影

鞍點所創造的問題在於圍繞其周圍的平坦區域。該區域和其他的平坦區域相似，都擁有極小的梯度變化，或甚至較小的曲度（Curvature）。

最後鞍點可以由二階偏導數測試偵測。二階偏導數矩陣，又被稱為海森矩陣（Hessian Matrix），在所處的特徵空間，對每一個維度取二次偏微求得。它也可以看作沿著每一維度估算梯度改變的矩陣。我們可以借助二階偏導數矩陣的特徵值（Eigen Value）來協助描述鞍點的特性。

二階偏導數矩陣的特徵值可以看做在不同維度的曲度（Curvature）量測。若該維度的對應特徵值為正，曲度為正，則該點的二次泰勒展開式曲線則略為往上翹。若為負，曲度為負，則該點的二次泰勒展開式曲線則略為往下。所以，若有一點其一階導數矩陣為零，而所有二階偏導數矩陣的特徵值為正，同時也為 Positive Definite 矩陣，則該點有局部最小值。當所有二階偏導數矩陣的特徵值為負，同時也為 Negative Definite 矩陣，則該點有局部最大值。若所有二階偏導數矩陣的特徵值為正也有負，則該點位於鞍部內「註三」。

不相符的局部和全域結構

由於梯度下降的區域性值，梯度下降法是相當依賴初始值選擇的一個演算法。我們可以想像有一個損失曲面，該曲面有一個小山谷屬於局部最小值，而全域最小值所在地在他處。小山谷陡峭的一端恰巧就是最陡梯度下降法的前進方向，正好通往小山谷的底部。小山谷的緩降部份則可以通往全域最小值，倘若一開始初始在陡峭的一邊，便會注定困在小山谷裡，可謂生錯地方的初始值。

小山谷代表的是損失曲面的局部結構，該區域的最陡方向未能指向全域最小值，我們可以稱呼這種情況為不相符的局部和全域結構。理論上，一個良好的最佳化演算法不該太過依賴初始值，在合理的學習率（Learning Rate）範圍下，演算法會保證收斂到一定的誤差值下。然而在大多的情況下，損失曲面通常佈滿了局部最小值等上述陷阱，而使得梯度下降演算法受限於初始值的選擇。

初始值的選取可以影響收斂的值和速率。在 2019 年一篇 “The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks“ 「註六」的論文則指出：若希望在一個過度參數化（Over-parameterized）的網路中找到一個擁有相同驗證誤差的小型網路（Subnet），則需要有些權重幸運地被初始化到適合的初始值，而那機會就像是贏得彩卷一樣，所以被稱為樂透彩卷假說（The Lottery Ticket Hypothesis）。

病態（ill-conditioning）二階導數矩陣

由於損失函式的曲面形狀事先不可知，必須要在餵送資料時估算。但我們還是可以假設一個完美的損失函式曲面形狀，應該是在各個維度等長以抵銷初始值的影響，而成為一個完美的球體。為什麼一個完美的損失函式形狀會需要是球體呢？我們可以由下圖來說明。

圖左是資料未經過標準化後會程的損失函式。圖右則為經過標準化後所繪出的損失函式。原圖來自於參考資料 [1]

這兩圖中，都各自畫上了模型為線性方程「註五」的損失函式。兩軸分別為模型的兩個參數，而損失函式值，則以有顏色的等高線代表之。等高線顏色偏藍，則為低損失函式值，而顏色為紅，則為高損失函式值。中心的紅點，則為全域最小值。箭頭的方向則是最佳化演算法在每一次迭代所估算出的前進方向。

可以看到，左圖損失函式曲面為橢圓形，這意味著，若最佳化演算法初始化於長軸或高曲度的一端，需要耗費比在短軸或低曲度一端，更長的時間才能到達最低點。而右圖的圓形損失函式曲面則沒有如此問題，此曲面形狀在任何維度都為等長，無論從哪一端初始，都會花一樣的時間到達最低點，因而不易受到初始值的影響。

為了能改善這種情況，通常會對訓練資料做標準化（Standarization）「註四」的前置處理，在這個標準化的前置處理中，需要減去這個批次內資料的平均值和除上標準差，才能將資料的數值形塑為一個平均為為零，而標準差為一的高斯分佈。

接著我們用數學來定性解釋橢圓形的損失函式曲面情況，我們稱呼它為病態的二階導數矩陣。

一個病態的二階導數矩陣，若給予特徵小量擾動，便會產生極大的梯度變化。而作為量測一階導數變化的二階導數，若屬於病態則會使梯度產生極大的變化，造成學習如遇到亂流的飛機，大幅度的震盪。

至於病態二階導數矩陣，可以透過計算條件數（condition number）來檢測。條件數計算方式為最大和最小特徵值的比，再取絕對值。最大和最小的特徵值比可以看做函數的最大曲度方向和最小曲度方向的比值，過大的條件數，造成如非圓形的損失函式曲面的情況，而梯度最佳化演算法便會沿著最大曲度來回震盪的前進。

當然，看到這裡，大家心裡可能有個疑問，既然二階導數的資訊如此重要，為什麼不直接使用有考慮二階導數的演算法呢？事實上，也有不少的學者考慮使用二階導數的演算法，如牛頓法（Newton's Method），或使用近似方式二階導函數的一階方法如 Quasi Netwon 。但由於二階導函數的計算費時，難以併入類神經網路等等的理由，而沒有在類神經網路中實現。

所幸，面對這三個考驗，研究最佳化的專家們也有了對策，這些對策可以粗略分為以下形式：

對餵送資料所做的變化處理：在這裡將會討論如何用小批次的方法產生亂度較大的梯度估算，同時可用來克服過度擬合的問題。（上）
對損失函示的表示所做的變化處理：在這裡我們會介紹如何使用參數的範數作為損失函數的處罰項，迫使最佳化演算法將參數稀疏化，或部分參數採取零或接近零的值。（上）
對訓練時間長度所做的變化處理：在這裡所指的時間長度不是執行的時間，而是執行的迭代數，我們會在這個小節談到一個簡單地避免過度擬合的方法，Early Stopping。（上）
對估計梯度的方法所做的變化處理：在這裡我們會介紹動量（Momentum），並將動量引入梯度最小演算法，提供新的參數更新的步驟。（下）
對設定學習率所做的變化處理：在這裡主要是介紹如何使學習率變成可學習的參數，同時動量估算也會被引用，幫助學習率根據損失函式的局部狀態取得最佳值。（下）

接下來就來了解我們的小幫手們吧！

對餵送資料所做的變化處理

Mini-batch

在「病態二階導數矩陣」小節中，我們提到了能夠將損失函式曲面經由標準化處理，變為更似球體，比較不易受到初始值影響。然而，多半的時候損失函式曲面較為複雜，存在許多小的山谷和尖峰，就算重新塑造的損失函示曲面移除了初始值的偏好，最終也會莫名的在這些小山谷，或局部最小值中徘徊，找不到出口離開。

我們知道，損失函式的估算來自於我們如何餵送資料，若每一批餵送資料數目為大，則估算該點的損失值的變異小而較為精準，相對的若餵送資料數目為小，則估算損失函度計算的變異大，而較不精準。

然而，變異大的損失值估算不一定是不好的，事實上小批次餵送資料，又稱為 mini-batch，可以給予我們的最佳化演算法探索的能力，而不會侷限於由所有訓練資料所算出的梯度，進而獲得較佳泛化的能力，進而解決了部分過度擬合的問題：與其每次迭代都使用全部的訓練資料，mini-batch 的方式，將全部的資料分為幾個不同的批次，分批遞送。這樣做的好處，在於計算梯度時，可以探索不同的方向，在較為複雜的損失函式，可以找到更佳的最小值。

針對每一批次不同資料大小，可分為使用所有資料的單次餵送的批次梯度下降法（Batch gradient desent，藍），多次餵送的迷你批次梯度下降法（Mini-batch gradient descent）和與訓練資料長度相等的餵送次數，隨機梯度下降法（Stochastic gradient desent）在這個方法中，一次只餵送一個資料。
原圖來自於參考資料[1]

對損失函示的表示所做的變化處理

處罰項

過去我們在討論如何衡量模型的表現時，曾提到解決擬合不足的問題，最簡單的方法就是增加模型的複雜度。而過度擬合的解決方案中，則有增加較多的資料，或可以加入處罰項式（penalty term）到損失函式內，以及利用集合（ensemble）的方法來完成。

增加較多資料是最簡單的選項，但對標註資料不易取得的情況，這通常是最後的選項。至於 ensemble 方法，在統計學習中是非常普遍的方法：著名的 Random Forest 演算法，在訓練時便刻意對特徵和訓練實例任意取樣，而訓練出許多不同的 decision tree 模型。類神經網路們，因為訓練一個類神經網路相當耗時，所以多半在訓練過程中對一或多層的網路結構進行 “drop out” ，裁減網路節點後，再取平均作為輸出結果。我們會在介紹與類神經網路相關的模型調整技巧中，再見到它，

在這裡我們僅討論在線性模型中常用的處罰項式方法。處罰項式為一個增加到原損失函式的新項式，其作用在於處罰那些多餘的參數，防止這些多餘的參數讓新的損失函數上升。藉著處罰這些多餘參數，使其值逼近於零，而達到縮減參數個數的目的，所以處罰項屬於調節（Regularization）模型的方法。同時因為哪些參數會被處罰，都交由最佳化演算法決定，所以算是以自動的方式進行特徵選取（feature selection）。

關於處罰項式的數學表示，一般使用的 p-範數作為參數的強度（不考慮方向），若有多個參數，則會將各個參數的 p-範數相加起來。為了達到處罰效果，處罰項需要增加原損失函式，所以不能為負值。p 最常見是選擇為 2 和 1。p 為 2 被稱為 L2 範數處罰項，當 p 為 1，則被稱為 L1 範數處罰項。在線性模型中又把 L1 範數處罰項稱為 Lasso ，而 L2 範數處罰項稱為 Ridge。

這兩個範數處罰項的不同可以由下圖來說明：

上圖中，損失函式的數學式 L(x, y, w)，包含了輸入特徵 x, 真正的標記 y 和參數 w 的函式）。而處罰項式 Ω(w)，為參數 w 的函式。新的損失函示則是原來的損失韓式再加上處罰項式，仍舊維持 L(x, y, w) 的表現式。處罰項式可以使用 L1 範數（左）和 L2 範數（右）。W* 為加入範數處罰項後的損失函數最佳解。但無論是用L1 或 L2 範數，都要乘上一個為正浮點數的參數 λ ，作為處罰項的強度調節。
原圖來自於參考資料[2]

上圖中 x 軸的參數對應的是參數 W1，y 軸對應的則是另一個參數 W2 ，而原損失函式則為這兩個參數的函式，將其值繪出後會等於一個等高線圖（橢圓形），愈往外圈移動，原損失函式值愈大。左右兩邊的圖形分別為針對範數處罰項的數學形式畫了相對的幾何圖形。可以看到 L1 範數（左），兩參數為線性關係，再取絕對值後，而造成上下左右對稱，所以對應的圖形是一個菱形。而 L2 範數（右），兩參數都取平方相加，所以對應的圖形是圓形。

其次，我們可以從範數處罰項的圖形了解範數處罰項的特性。我們可以知道屬於菱形的 L1 範數處罰項擁有不可連續微分點。而屬於圓形的 L2 範數處罰項則四處可微。雖然，L1 範數處罰項擁有不可連續微分點，但我們可以從圖中看到，加入範數處罰項後，與原本損失函式相交且總和為最小的情況，意即是最佳參數 W* 所在的位置，在 L1 範數的例子，W1 參數為零的情況可達成。在 L2 範數的例子，則是靠近 W1 為零的地方。

可以看到，加入範數處罰項後，與原本損失函式相交且總和為最小的情況，意即是 W* 所在的位置。在 L1 範數處罰項的例子，W1 參數為零的情況可達成。在 L2 範數處罰項的例子，則是靠近 W1 為零的地方。我們都可以從圖形看到加入了處罰項後，最佳參數值不再是原損失函式的最低點，也就是橢圓中心點，透過處罰項的調節功能，而是在上述位置。

這個簡單的例子告訴我們，範數處罰項如何達到我們所希望的，藉著移至參數為零的位置，來減少參數的數目。然而，從例子中我們更發現，若想要真正達到參數稀疏化，那麼使用 L1 範數作為處罰項，將會令許多參數的值為零，而非使用 L2 範數只能近似零。倘若希望函式能夠四處可微，則該使用 L2 範數。

最後，要注意的是當使用處罰項於參數時，通常不會針對偏移項（bias）做處罰「註五」。這是因為偏移參數數量較少且參數之間多無關聯，若使用處罰項時容易造成過度擬合的情況。

對訓練時間長度所做的變化處理

Early stopping

在多數的時候，過度擬合的問題由資料餵送的方式來解決效果是有限的，因為 mini-batch 本身並不是針對過度擬合所設計的解決方案。而使用處罰項，需要改變原損失函式並且需要重新開始訓練，有沒有什麼預防過度擬合方法是非常簡易可以實現，卻不會大幅更動模型和損失函式呢？

首先，我們必須了解一個迭代型最佳化演算法，通常其訓練誤差會隨著迭代數目減小，直到該演算法收斂為止。所以，我們可以如此假設，當訓練時間長度增長時，尤其對類神經網路，這樣經常過度參數化的模型，訓練誤差一定會隨著訓練時間的長度增長而減小，然而這個訓練時期良好表現，卻造成模型應用到新的資料上的困難，也就是我們一直強調的無法洽當泛化而造成「過度擬合」的問題。

針對驗證集的表現來調整訓練時間長度，就可以直接針對過度擬合來解決，這個方法被稱為 Early Stopping。

藍線是訓練誤差，綠線為驗證誤差。
圖片來源：參考資料 [4]

如圖所示，我們可以設定一個門檻值，當驗證集誤差超出門檻值後，雖然訓練集誤差仍舊下降，但是我們已經可以提早停止演算法。這個門檻值是由使用者選取，但是一個良好的門檻，其數值不能過小，而將隨機震盪且步向收斂的驗證集誤差被誤認為逐漸攀升，且不能過大，而將逐漸攀升的驗證集誤差誤認為是隨機震盪且步向收斂，繼續訓練而傷害模型的泛化能力，以致於過度擬合。

使用 Early Stopping 的方式有以下好處：

如前所述 Early Stopping 不會改變模型和以最無干擾的方式改變訓練演算法。Early Stopping 甚至可以併入處罰項或其他預防過度擬合的調節方法。
可以快速進行可調參數校調（Hyper-parameter Tuning）亦可簡單達成平行計算：多個不同參數可以利用 Early Stopping 的方式快速篩選那些驗證集誤差過高的可調參數值。同時，Early Stopping 方法可以使用不同可調參數來建構多個獨立模型模型，並平行計算。

Early Stopping 亦可以看做一個對訓練迭代數目參數的調整演算法，所以如果訓練發生問題時，上述兩點包含多個調節技巧或更動多個可調參數的訓練方式，難以分辨責任歸屬會造成難以除錯的問題。

應用 Early Stopping 於深度學習，也因近期『兩次下降』（Double Descent）的「註六」發現，而面臨挑戰。在傳統的機械學習概念中，模型的複雜度和訓練實例的關係是用 Bias-Variance Trade-off 來解釋。整體而言，在傳統機械學習的法則下，模型複雜度和驗證損失關係是一個 U 型，也就是只有經歷『一次下降』（Single Descent）後即上升的圖形。然而，最近深度學習的研究者卻提報另一個下降被觀察到，當模型的複雜度成長到穿越了某一個「重要區域」後，驗證誤差又開始下降了！

Early Stopping 雖然只能應用於傳統的一次下降（Single Descent）範圍，而非兩次下降（Double Descent）。但，兩次下降還是一個相對年輕的發現，只要還在傳統機械學習的領土內，都可以安全使用 Early Stopping。

註釋：

[註一] 模型的非『單一確定性』（model identiﬁability）除了可以從權重的對稱空間（weight space symmetry）中，藉由任意排列權重證明，也可以由任意乘或除上一個相對數值，而消減線性或非線性啟動函示對輸入增大或縮小的效果。上述效果也同樣可以在偏移量證明出類神經網路的模型非單一確定性。如前所述，這些因為模型的非單一確定性產生的局部最小值，不會對最佳化造成影響。

[註二] 關於最佳化演算法終止在平坦區域（flat minimum）或是狹長區域（sharp minimum），研究者們有一些爭議。最初由 Hochreiter & Schmidhuber 在 1997 年所發表的一篇論文，”Flat minimum”，中提到，若最佳化演算法終止在平坦區域上的最小值，會比在狹長區域上的最小值有較佳的能力學習未曾看過的例子，或稱為泛化（Generalization）能力。Hochreiter & Schmidhuber 相信，在平坦區域，有較廣的參數變化，其損失值都相似，因次較不易受到雜訊影響。然而，這個說法在 2017 年獲得廣泛檢視，其中一篇由 Yoshua Bengio 實驗室所發表的文章 “Sharp Minima Can Generalize For Deep Nets”，則對這個說法提出反駁。在這篇文章中，他們藉由理論推導提出平坦區域最小值可以透過「註一」所說的非單一確定性，成為一個狹長區域最小值，反之亦然。因為平坦區域最小值非模型的特定性質，自然無法決定其泛化能力。

[註三] 另外一個和使用二階偏導數矩陣的特徵值有異曲同工之妙的是計算二階導數矩陣的行列式來檢測鞍點。若該行列式計算結果為負，則該點為鞍點。若該行列式計算結果為正，則該點非鞍點。

[註四] 在許多文件中 normalization 和 standardization 似乎交替使用。

[註五] 一個線性方程有一個係數項參數和偏移項參數所構成，如：y=Wx+b，x 為輸入特徵，y 為輸出，W 是係數項參數，通稱權重參數（Weight），而 b 為偏移項（Bias）參數。

[註六] 關於 Double Descent 和 The Lottery Ticket 請見《深度學習的第一個十年》2019 一文

參考資料：

[1] Gradient Descent Algorithm and Its Variants （英）
[2] What is Regularization in Machine Learning? （英）
[3]線代啟示錄（繁中）：引用實例來介紹病態系統，並有關於如何證明條件數的公式。（繁中）
[4] Deep Learning - Regularization for Deep Learning (Ch 7) （英）

為什麼會看到廣告

Rene Wang的沙龍翻滾吧！駭客女孩！

Rene Wang的沙龍

71會員

35內容數

<p>專為年輕的女孩設計的科學／資訊科技寫作計畫，希望讓每位女孩在體脂肪、青春痘與暗戀對象之外，還能找到新的生活樂趣。</p>

留言0

查看全部

發表第一個留言支持創作者！

Rene Wang的沙龍的其他內容

挺身而進

臉書的營運長，雪柔‧桑德伯格，在 2013 年《挺身而進》一書中，指出女性在職場中的困境，而有些困境是來自於對自己的限制，如缺乏自信和兼顧一切。在這系列的文章中，駭客女孩側寫許多挺身而進的女性工程師或創業者，甚至年輕的城市教育家，他們如何突破固有性別的限制，以創意的方式來教導，鼓勵女性參與工程領域。

#程式教育 #薪資性別差異 #featured

[探索] 門外漢的類神經網路導覽

這篇文章從類神經網路的起源，也就是單神經元的感知器。簡單的感知器迭代演算法使單神經元可以學習，但卻無法學習超過非線性，如 XOR 的資料分布。另外，本文還介紹了 Logistic regression，藉由透過非線性轉換來使線性輸出近似於機率分佈。最後則以一場大師賭局結束(SVM vs NN)。

#類神經網路 #SVM #YannLeCun

[觀點] 人工智慧的回顧與展望 2019

在 2018 年，筆者介紹了普華永道（PwC）關於人工智慧的十項預測。我們將要藉由這篇文章，先來回顧在過去的一年中，電腦視覺和自然語言領域有什麼新的發展。在本文的最後，則提及 PwC 在今年提出的六項建議，主要使已投資 AI 的公司能成功商轉，以及關於自動化資料處理和機械學習的現況。

#人工智慧 #自動化機械學習 #電腦視覺

[探索] 門外漢的類神經物體偵測導覽

本文提到如何以類神經網路為主的深度學習方法，來進行物體偵測。文中包括基礎的物體偵測簡介：如影像問題分類，影像處理和傳統非類神經網路為主的物體偵測方法。這些傳統方法，仍可以在類神經網路的方法中找到其應用。最後簡略敘述當前使用深度卷積網路作為物體偵測的主要研究方向，並對學術界常用的訓練資料集做分析介紹。

#深度學習 #物體偵測 #卷積網路