第四章主要研究的是優化問題。我們機器學習的目標常常是使某個目標函數(objective function)或損失函數(cost function)盡量小，即找到一個 x^{*} = argminf(x). 對於有的問題我們可能可以得到解析解，但對於大多數問題，我們可能無法得到解析解，這時候就需要一些數值計算的方法使我們逐漸逼近最優解，這一章裏就主要講了利用一階導數的梯度下降演算法和利用二階導數的牛頓方法，另外還有研究在給定某些限制條件下的條件極值的解法，Ian在這一章有些解釋可能略過了，在這裡我加入了自己的理解使其更易懂。

梯度下降演算法

首先，回顧一下基本概念，對於函數 y=f(x) ，我們通常用 f(x) 或 frac{dy}{dx} 來表示其導數。導數代表了f(x)在x處的斜率，即假如我們將x改變一個小量 varepsilon ，則 f(x+epsilon) approx f(x) + epsilon * f(x)。

而梯度下降演算法(gradient descent)就是我們想要尋找f(x)的最小值，假設我們初始位置是 x ，那我們下一次想要找的新的x的位置為 x = x - alpha f(x) ，其中 alpha > 0 。由此我們可以得到 f(x)-f(x) = -alpha [f(x)]^2 <= 0 f(x)相對於f(x)是變小的，所以我們可以通過這種更新方式逐步逼近f(x)的最小值。比如對於一個簡單的二次函數 f(x)=frac{1}{2} x^2 ，其導數為 f(x)=x , 在x>0時，f(x)也大於零，所以新的位置應往左邊走，使f(x)更小，對於x<0時，f(x)小於零，因此新的位置應往右邊走，最終我們會得到在x=0時有最小值f(x)=0。

我們可以看出無論f(x) 是大於零還是小於零， f(x)-f(x) 都小於零，即我們在逼近更小值。而當f(x)等於零的時候是一個比較有意思的情況，我們發現f(x)與f(x)的值相同，這個點稱作臨界點(critical point)，它可能是局域最大點(local maximum)如果f(x)比其它周圍的值都高，也可能是局域最小點(local minimum)如果f(x)比其他周圍的值都低，也可能是鞍點(saddle point)即既不是局域極大點也不是極小點，如下圖所示：

前面我們提到了局域，我們還定義如果某一點對於我們所研究的域內所有的點都是最小值，則稱其為全局最小點(global minimum)。 通常我們在深度學習模型裏可能找到的是很多局域最小點而很難找到全局最小點，尤其是對於具有很多維度的優化問題，這個時候我們一般就取一個非常小的局域最小點，而不一定非要強求找到全局最小點。

上面我們主要定義了標量的導數，我們也可以將其推廣到相對於矢量的導數，稱作梯度(gradient)。假設我們有函數 f: R^n ightarrow R 我們定義其偏導數(partial derivative) frac{partial}{partial x_i} f(x) 為f(x)在矢量x所在點相對於 x_i 坐標的f(x)的變化率，我們可以用一個矢量來表示相對於所有坐標的導數，標記為 ?_xf(x) 。而梯度下降演算法的公式就可以表示為 x = x - alpha ?_xf(x) ，其中 alpha 是學習率(learning rate)，表示了每次步進的幅度。通常我們將其選為一個較小的常數，但直觀上講，當初始時我們可能離極值點比較遠，我們可以用比較大的學習率，而接近於極值點時我們需要較小的學習率否則f(x)就可能來回波動而收斂很慢，因此後面章節（第八章）會提到一些其他的optimizer例如Adagrad, Adam等不斷更新學習率的方法。

雅可比矩陣，海森矩陣與牛頓逼近法

有的時候我們的映射函數可能輸入和輸出均是矢量，即 f: R^m ightarrow R^n ，這時候為表示所有輸出與輸入各坐標的偏導數，我們就需要雅可比矩陣(Jacobian matrix)， Jin R^{n imes m} ,其中 J_{i,j} = frac{partial}{partial x_j}f(x)_i

有的時候我們可能還需要求某一個函數的二階導數，對於 f: R^n ightarrow R ，其對於 x_j 求偏導後再對 x_i 求偏導可以表示為 frac{partial}{partial x_i partial x_j}f ,對於所有的i,j的偏導數的組合，我們可以用海森矩陣(Hessian matrix)H(f)(x)表示，其中 H(f)(x)_{i,j} = frac{partial^2}{partial x_i partial x_j}f(x) ，我們可以將其看做梯度的雅可比矩陣。

那麼二階導數代表了什麼意義呢？它可以看做是曲線斜率隨輸入的變化，是一種對曲線曲率的測量，對於一維情況，假如二階導數為零，那麼該曲線曲率為零，即為一條直線，如果二階導數為正，那麼曲線就是一個下凹函數，如果二階導數為負，則曲線為上凸函數，如下圖所示：

二階導數可以告訴我們梯度下降演算法的效果。我們將函數f(x)對於當前點 x^{(0)} 做二階泰勒展開，可以得到 f(x) approx f(x^{(0)}) + (x-x^{(0)})^T g + frac{1}{2} (x-x^{(0)})^T H(x-x^{(0)}) ，其中g是導數，H為Hessian matrix。假設學習率是 alpha ，則新的點是 x^{(0)}-alpha g ，有 f(x^{(0)}-alpha g) approx f(x^{(0)})-alpha g^T g + frac{1}{2} alpha ^2g^THg ,可以看出右邊的 -alpha g^T g 是我們優化求極小值時的改善項，而最右一項為修正項，如果最右一項過大，那麼我們就會沿著曲線上移，沒有逼近極小點，而是遠離了極小點。當 g^THg 是零或者負值，我們可以看出提高 alpha 總會使f(x)變小，而當 g^THg 是正值時，如果 alpha 選取的不合適，就可能使f(x)上升，如果我們將二級泰勒展開對於 alpha 求導取零，即可得到最合適的學習率為 alpha ^* = frac{g^Tg}{g^THg}

二階導數也可以用來判斷一個臨界點是否是極小值點，極大值點或是鞍點。在臨界點 f(x)=0 ，如果 f(x)>0 ，如果我們向右移動則導數升高，向左移動則導數下降，直觀地講我們無論左移右移都在向曲線上坡方向走，所以該點是極小值點。同理，當 f(x) < 0 ，則是極大值點。當 f(x) = 0 ，則不確定，可能是鞍點，也可能是一個全平的區域。

以上是針對一維空間進行的討論，我們也可以將其延伸到多維空間：當 ?_xf(x) = 0 時，如果Hessian matrix 是正定矩陣（所有本徵值都大於零），則是極小值點，如果是負定矩陣（所有本徵值都小於零），則是極大值點，其餘情況則為鞍點或是全平的區域。

對於多維空間，我們也可以看出一階梯度下降演算法的侷限性，如果不同方向上的曲率不同，則某些方向上導數改變很快，而另一些方向上導數改變很小，由於梯度下降演算法並沒有考慮二階梯度，它並不知道該選取哪個方向才能更快的到達極值點。同樣的，如果不同方向的曲率不同，我們如何選取合適的學習率也成了一個難題，某些方向上曲率大，就會產生在曲線的兩個山坡上來回振動而不能一直趨近山坳的現象，限制了我們只能選取很小的學習率，如下圖所示：

為瞭解決這一缺陷，我們需要利用二階導數，這就是牛頓方法。多維情況下的二階泰勒展開為 f(x) approx f(x^{(0)}) + (x-x^{(0)})^T ?_xf(x^{(0)}) + frac{1}{2} (x-x^{(0)})^T H(f)(x^{(0)})(x-x^{(0)})

使f(x)相對於x的導數為零，可得更新公式 x^* = x^{(0)}-H(f)(x^{(0)})^{-1}?_xf(x^{(0)}) ，牛頓方法會比梯度下降演算法更快的到達極值點。

條件極值與KKT演算法

有的時候，我們不僅僅是要在全域裏求某個函數的極值點，而且是要在給定限制條件的集合中求條件極值。這時候我們可以利用KKT(全稱是Karush-Kuhn-Tucker)演算法將有限制條件的極值問題轉化為無限制條件的極值問題，然後我們就可以用之前處理無限制條件的極值問題的方法來解決這個問題。KKT演算法可以看做是是拉格朗日乘子法的一種推廣形式。

假設我們要求f(x)的極值，其限制條件為 S=left{ x|forall i, g^{(i)}(x)=0, forall j, h^{(j)}(x)leq0 ight} ，其中 g^{(i)}(x) 為等式限制條件， h^{(j)}(x) 為不等式限制條件。對於每一個限制條件，我們可以引入新的KKT乘子 lambda _i 和 alpha _j ，來定義一個新的拉格朗日式子

L(x,lambda,alpha) = f(x) + sum_{i}{lambda _i g^{(i)}(x)} + sum_{j}{alpha _j h^{(j)}(x)}

我們可以將有限制條件的極小值問題轉化為對拉格朗日式子的無條件的極小值問題，即求出

則其得到的極值點與目標是

的相同。

可以如此轉化的原因是如果所有的限制條件都滿足，即 forall i, g^{(i)}(x)=0, forall j, h^{(j)}(x)leq0 則拉格朗日式子第二項 sum_{i}{lambda _i g^{(i)}(x)}=0 ，而由於 h^{(j)}(x)leq0 ，第三項 sum_{j}{alpha _j h^{(j)}(x)} 最大值為零，得到

而假如有任意限制條件不滿足，比如，某一 g^{(i)}(x) e 0 ，則我們可以選取與 g^{(i)}(x) 符號相同的無限大的 lambda ，使得 L(x,lambda,alpha) = infty ，對於某一 h^{(j)}(x)>0 ,我們則可以選取無限大的 alpha ,使得 L(x,lambda,alpha) = infty ，所以可以總結為如果任意限制條件不滿足，則

由此我們也可以得出拉格朗日式子取極值的必要條件：

  • L(x,lambda,alpha) 的梯度得零。
  • forall i, g^{(i)}(x)=0
  • forall j, alpha _{j}*h^{(j)}(x)=0

一個應用KKT的實例是對於線性最小二乘問題(linear least square),我們想要求在限制條件為 x^T x leq 1 時f(x)=frac{1}{2}||Ax-b||^2 的極小值。

我們可以將其轉化為拉格朗日式子

L(x,lambda)=f(x)+lambda (x^T x -1)

而轉化為解決 min_x max_{lambda , lambdageq 0}L(x, lambda) 的問題。

我們想使 L(x, lambda) 相對於x最小化，則可以對拉格朗日式子求x的導數並另其得零而得到

A^T Ax-A^T b + 2lambda x = 0

所以最優解 x^* = （A^TA+ 2lambda I)^{-1}A^T b

那我們如何選取 lambda 可以使 L(x, lambda) 相對於 lambda 最大化呢, 我們可以將 L(x, lambda) 對 lambda 求偏導，得

frac{partial}{partial lambda}L(x,lambda)=x^Tx - 1

可以發現當 x^Tx > 1 即x的範數大於1時，偏導大於零，所以我們應該增大 lambda 使 L(x, lambda) 增大，由於 lambda 增大，我們可以看到x的最優解會相應的減小，即x需要有更小的範數。在機器學習中，我們常常要為防止過擬合而限制某些範數過大的項，就是利用這個方法，而lambda 又稱作正則項(regularization)係數。

至此，花書第四章數值計算總結完畢，這章中的梯度下降演算法和KKT演算法後面會常常用到。


推薦閱讀：
相關文章