點滴- 機器學習中的優化問題

08-31

點滴- 機器學習中的優化問題

本文是李宏毅老師機器學習教學視頻觀看筆記，文中所用材料如無額外標記，都取自李宏毅老師的視頻。

在機器學習，尤其是深度學習問題中，我們有一系列樣本 $(x_1,y_1),(x_2,y_2),..,(x_N,y_N)$ ，其中 $x$ 可以代表樣本的屬性，而 $y$ 則可代表某個與屬性相關的目標值。我們通過這些樣本調整模型參數，使得給定輸入屬性後，其輸出與真實目標值儘可能接近。為此，我們需要定義一個loss function：

$L( heta)=sum_{i=1}^{N}{l(f_{ heta}(x_i),y_i)}spacespace(1)$

這個loss function描述了模型輸出與實際目標的偏差，是關於模型參數的函數，我們需要找到一套使loss function最小的參數： $heta^*={arg}space ext{ min}_ hetaspace L( heta)$ ，這樣模型能最好地反映樣本信息。但要指出的是，能很貼切反映樣本信息的模型並不一定是最好的模型，因為該模型在訓練樣本中表現出色不代表它具有較強的泛化能力。換句話說，單純一味追求loss function在樣本集最小是一個優化問題，它不等價於「學習」，它不關注模型是否過擬合、是否可以遷移到其他未參與訓練樣本。即認為學習是有條件的優化。

現在我們先放下「學習」，專註於「優化」。如果loss function不是一個凸函數，那麼優化loss function的這個過程實際上是在進行非凸優化，這是NP-hard的一個問題。

怎麼優化這個loss function？

為了簡便，我們把用 $f( old{ heta} )$ 表示loss function，藉助泰勒展開，loss function在參數等於 $heta_0$ 的鄰域可以表示為：

$f( old{ heta} )=f( old{ heta^0} )+( heta- heta^0)^Tg+frac{1}{2}( heta- heta^0)H( heta- heta^0)^T+....spacespace(2)$

設 $heta$ 是一個 $n$ 維參數向量，因此上述展開是高維的泰勒展開，對於這個展開式，當展開階數較低時，雖然在 $heta_0$ 處與原函數最接近，但隨著參數（即函數自變數）取值離鄰域越遠，展開式與原函數的偏差會越大，而如果階數無窮延伸的話，展開式就無窮接近原函數了。因為這樣的多項式在求導、運算方面都具有明顯優勢，因此我們以這個多項式為研究優化問題的基礎。在上式中， $g$ 是loss function在 $old{ heta^0}$ 的偏導，可以寫為 $igtriangledown f( heta^0)$ ，同樣是一個向量，其中的某個元素 $g_i=frac {partial{ f({ heta^0}) }} {partial heta_i}$ ，易得 $( heta- heta^0)^Tg$ 是一個標量； $H$ 表示黑塞矩陣（Hessian Matrix），其每個元素 $H_{ij}=frac{partial^2}{partial{ heta_i}partial{ heta_j}}f( heta^0)$ ，顯然我們有 $H_{ij}=H_{ji}$ ，即黑塞矩陣是一個對稱矩陣。此外， $( heta- heta^0)H( heta- heta^0)^T$ 表示向量和矩陣相乘，其結果也是一個標量。

當多項式 $(2)$ 只展開到一階時，即 $f( old{ heta} )=f( old{ heta^0} )+( heta- heta^0)^Tg$ ，它是關於參數的一次函數，即我們在鄰域附近用一條直線（下圖綠線）近似原函數（下圖黑線）（為了簡便，忽略高維的參數空間，用一維代替）：

為了找loss function的最小值，在這個當前參數所在的鄰域中，把原函數的求導近似為多項式求導，並令導數為0，求取極小點，即 $igtriangledown f( heta)approxigtriangledown f( heta^0)+igtriangledown ( heta- heta^0)^Tg=0$ ，其中，右邊第一項為常數，求導為0，即梯度 $g=0$ 。但是因為現在是用一條直線近似原函數，梯度是一個定值，所以不能一步就令梯度為0，而只能用一個學習率來控制參數的調整： $heta = heta^0-eta g$ ，一步步調整參數，這就是我們常見的梯度下降方法。

而如果我們更進一步，將多項式展開至二階，則有 $f( old{ heta} )approx f( old{ heta^0} )+( heta- heta^0)^Tg+frac{1}{2}( heta- heta^0)H( heta- heta^0)^T$ ，顯然它是一個二次函數，也是一個凸函數，如下圖表示（紅線表示展開式，黑線表示原函數）：

我們要找的是loss function的最小值，那麼在這個鄰域中，我們把原函數的求導近似為多項式求導，並令導數0，求取極小點：

$igtriangledown f( heta)approxigtriangledown f( heta^0)+igtriangledown ( heta- heta^0)^Tg+igtriangledown [frac{1}{2}( heta- heta^0)H( heta- heta^0)^T]$

同理，可化簡為：

$igtriangledown f( heta)approx g+ H( heta- heta^0)$

令上式等於0，可得 $heta = heta^0-H^{-1}g$ ，注意這個前提是 $H$ 可逆。在這裡我們很容易想到，常用的梯度下降： $heta = heta^0-eta g$ ，兩者都是基於現在所處的位置，找下一個位置，使得loss function變小，不同的是，後者是通過學習率控制步幅，一步步試探走下去，而前者是一步到位，即更新一次就找到當前所處位置所在鄰域中使loss function最小的參數，在這裡 $H^{-1}$ 既調整了梯度方向，又調整了更新步幅。

上面這個過程就是Newtons Method。再通過一幅圖加深理解：

如上圖所示，紅線代表原函數在對應參數鄰域的二階泰勒展開，是二次函數。假設剛開始參數是在 $x_0$ 的位置，可以看到展開的多項式在 $x_0$ 處與原函數重合，隨著取值離 $x_0$ 越遠，兩者偏差越大。我們在 $x_0$ 處用展開式近似原函數，通過求取展開式的極（小）值點更新參數位置到 $x_1$ ，接下來在 $x_1$ 處重新進行泰勒展開，再次求取此時展開式的極值點，以此類推，就可以接近原函數的極值點了。

在調整參數的過程中，我們有可能到達原函數的極大值點、極小值點、鞍點，在這三個地方梯度 $g$ 為0，此時我們有：

$f( old{ heta} ) approx f( old{ heta^0} ) +frac{1}{2}( heta- heta^0)H( heta- heta^0)^T$

由上式所示，當取值落在上述的三個地方時，一階展開為0，二階項變成了多項式的關鍵。

如何根據二階項來判斷現在的真實處境呢？

關鍵在於對稱矩陣 $H$ 。在這裡首先明確兩個定義：

若 $H$ 是正定矩陣（positive definite），那麼對於任意 $x$ ，都有 $xHx^T>0$ ，這也意味著 $H$ 的所有特徵值取值為正；
若 $H$ 是半正定矩陣（semi-positive definite），那麼對於任意 $x$ ，都有 $xHx^Tgeq0$ ，這也意味著 $H$ 的所有特徵值取值非負；
若 $H$ 是負定矩陣（negative definite），那麼對於任意 $x$ ，都有 $xHx^T<0$ ，這也意味著 $H$ 的所有特徵值取值為負；
若 $H$ 是半負定矩陣（semi-negative definite），那麼對於任意 $x$ ，都有 $xHx^T leq 0$ ，這也意味著 $H$ 的所有特徵值取值非正。

現在把 $( heta- heta^0)$ 看做是上面的 $x$ ：

若 $H$ 是正定矩陣，則表示二階項大於0恆成立，即 $f( old{ heta^0} ) +frac{1}{2}( heta- heta^0)H( heta- heta^0)^T>f( old{ heta^0} )$ 恆成立，說明 $heta_0$ 是其所在鄰域內的最低點，表示當前到達了局部最小值的位置；
若 $H$ 是負定矩陣，則表示二階項小於0恆成立，即 $f( old{ heta^0} ) +frac{1}{2}( heta- heta^0)H( heta- heta^0)^T<f( old{ heta^0} )$ 恆成立，說明在 $heta_0$ 是其所在鄰域內的最高點，表示當前到達了局部最大值的位置；
若在當前鄰域時既有 $xHx^T >0$ ，也有 $xHx^T <0$ ，那麼說明現在處於鞍點。（一種方法是通過判斷 $H$ 行列式大小，若小於0則表示處於鞍點）。

那麼如果 $( heta- heta^0)H( heta- heta^0)^T=0$ 呢？此時我們就不能簡單判斷了，就如前面所說的一階展開項為0的情況，此時其後面更高階的項是多項式的關鍵，我們需要展開至更高階來分析。

下面再以矩陣特徵向量的視角分析一下。

設 $H$ 的特徵向量為 $v$ ,特徵值為 $lambda$ ，即 $Hv=lambda v$ 。

現在我們可以令： $v^THv=v^T lambda v=v^Tvlambda=||v||^2lambda$ ，可以看到：

當 $( heta- heta^0)$ 與特徵向量方向一致時，參數更新後的loss function的變化值近似為 $frac{1}{2}( heta- heta^0)H( heta- heta^0)^T=frac{1}{2}||v||^2lambda$ 。
若 $( heta- heta^0)$ 與特徵向量方向並不一致，那麼我們可以把 $( heta- heta^0)$ 看做是多個特徵向量的組合：

$( heta- heta^0)=a_1v_1+ a_2v_2...+ a_nv_n$

由於 $H$ 是對稱矩陣，它的所有特徵向量正交（ $v_iv_j^T=0$ ），易推得：

$frac{1}{2}( heta- heta^0)H( heta- heta^0)^T \=frac{1}{2}[ (a_1v_1+ a_2v_2...+ a_nv_n)H(a_1v_1+ a_2v_2...+ a_nv_n)^T]\ =frac{1}{2}(a_1^{2}lambda_1+ a_2^2lambda_2...+ a_n^{2}lambda_n)$

由以上兩種情況我們可以得到結論：當 $H$ 的特徵值都為正時，loss function的變化值必然為正，此時同樣可得： $heta_0$ 是其所在鄰域內的最低點，表示當前到達了局部最小值的位置；當 $H$ 的特徵值都為負時，loss function的變化值必然為負，此時同樣可得： $heta_0$ 是其所在鄰域內的最低高點，表示當前到達了局部最大值的位置；若特徵值取值正負不定時，則表示loss function變化方向不定，表示到達鞍點。