[DL]深入了解gradient descent

前言

“在深度學習中，你(設計)的(損失)函數是怎麼更新的，他可微嗎?”

最近有聽到有人提了這個問題，一開始聽到這個問題也沒太放在心上，由於deep learning framework(Tensorflow, Pytorch)的便利性，大家可以不用管求導這件事，開開心心寫code。

不過後來想了想這的確是個可以來認真思考的事情，畢竟是走這行的，總不能一直都只依靠工具而不去了解背後的原理。於是努力上網東找西找拼湊了一套我覺得還算合理的說法，不過畢竟我不是數學系背景出生，如果有講錯的地方歡迎提出指教~

How Deep Learning Update?

我們知道，一個Deep learning model的參數量往往很大，在更新過程中是透過我們定義好的loss function(可能是cross-entropy或mse)來做gradient descent，gradient descent會去算每個參數的gradient，搭配learning rate來更新這些參數，使得讓模型越來越好。

不過算gradient這個動作在tensorflow/pytorch都自動幫我們算好了，以pytorch為例，我們可以從他的code來看到他更新的步驟(可以參考我寫的另一篇:Pytorch的zero_grad()和backward()使用技巧)

Why Gradient Descent?

我們知道沿著gradient的方向走可以讓模型越來越好，但為什麼?

首先先來快速了解gradient是什麼，以下介紹引用自wiki:

考慮一座高度在$(x, y)$點是$H(x, y)$的山。$H$這一點的梯度是在該點坡度（或者說斜度）最陡的方向。梯度的大小告訴我們坡度到底有多陡。

也就是說對於一個函數我們可以想像他有個對應的的分布圖(如果函數是高維空間你就畫不出來，可以用個三維空間的例子來想像，如下圖)，在圖上某個點我們可以透過計算梯度來找到在該點最陡的方向，然後沿著該方向繼續往下找最小值。

那接下來思考一個問題，考慮一個損失函數:

$L_{n}(a, W)=\frac{1}{n} \sum_{i=1}^{n} l\left(y_{i}, a^{T} \sigma\left(W^{T} x_{i}\right)\right)$

假設actuvation function是relu，loss function是L2，那請問這個函數是凸函數(convex)還是非凸函數(non-convex)?

先給答案，如果單看每個unit都是凸的

relu是convex
L2是convex

不過當他們混合起來後就不一定了，以這個例子為例其實他就變成了Non-convex。

Convex or Non-convex

“蛤?我知道gradient可以找到最小值就好了，理他凸不凸幹嘛。”

這很重要，因為這會牽涉到你找到的是區域最小值或是全域最小值。

在講這件事情前，聽說中國那邊有些凹凸的定義跟國外相反，所以我們先來定義一下什麼是凸函數好了:

凸函數長的跟下面這個人的眼睛一樣，開口朝上然後有個最小值(眼珠的部分)

好啦不鬧，也可以看一下他的數學定義:

反正就是畫一條線去看就可以判斷了。再來我們看一下非凸函數跟凸函數的圖長怎樣:

可以知道:

如果函數是凸函數，那我們可以很快的找到全域最小值
- 傳統機器學習方法問題大多是凸函數
但如果函數是非凸函數，模型學習到的就很容易是區域最小值而非全域最佳解，這也是我們必須透過training set/ validation set來判斷模型好不好的原因，因為你不知道你現在的位置到底在哪裡。
- 深度學習方法大多是非凸函數(注意這裡用的是大多，而不是全部)

要如何知道一個function是不是non-convex，引用Ian Goodfellow的回答:

There are various ways to test for convexity.

One is to just plot a cross-section of the function and look at it. If it has a non-convex shape, you don’t need to write a proof; you have disproven convexity by counter-example.

If you want to do this with algebra, one way is just to take the second derivatives of a function. If the second derivative of a function in 1-D space is ever negative, the function isn’t convex.

For neural nets, you have millions of parameters, so you need a test that works in high-dimensional space. In high-dimensional space, it turns out we can take the second derivative along one specific direction in space. For a unit vector $d$ giving the direction and a Hessian matrix $H$ of second derivatives, this is given by $d^{T}Hd$.

For most neural nets and most loss functions, it’s very easy to find a point in parameter space and a direction where $d^{T}Hd$ is negative.

也就是說如果能找到一維空間中函數的二階導數始終為負，則該函數不是凸函數。而最後兩段講到，在非常高維度的神經網路中，我們很容易就可以找到一個點他的二階導數是負的，所以大部分的loss function是non-convex。

所以阿，深度學習很容易學到一半模型就學歪了，因為他可能一不小心就在廣大的沙漠中找到了一小片綠洲而停下來，儘管他不是真正的最佳解。

到這裡我們知道函數是否convexity在最佳化時的差異。不過再來考慮另一個問題，deep learning都說用gradient descent來做更新，我們假設單一的函數都是convex(如Affine transformations, relu, max…)，那這些function一定可微嗎?

Is convex function differentiable?

答案是convex function不一定要可微，你可以去回顧上面對於凸函數的定義，可不可微並不影響他的性質。

那問題來了，不可微的東西你Pytorch是要怎麼backward算gradient啦!!

我們來舉個例子，大家都用到爛掉的relu:

你知道，我知道，獨眼龍也知道，在0那個點是不可微的(不過relu確實是個convex function唷)，那在0這個點到底該怎麼辦呢?

這時候sub-gradient就跳出來了，先說結論:

由於backward並不是真的去算一遍微分公式，而是會先定義好他的gradient是多少然後去propagation(可參閱autumatic differentiation技術)，所以就不會有計算錯誤的run-time error。
對於relu在0這個點的微分通常會設成0，不過實際上在[0, 1]之間選一個值也可以(我也看過有人用1/2的)

Subgradient???

先上簡單版結論: Subgradient method是可以在非光滑的function(也就是有些地方不可微時)訓練更新的方法，接下來會必較詳細的介紹subgradient

有幾篇文章我覺得講得非常好，所以下面內容我會節錄部分內容來做個簡單的介紹，你可以在reference看到引用的網站:

对于光滑的凸函数而言，我们可以直接采用梯度下降算法求解函数的极值，但是当函数不处处光滑、处处可微的时候，梯度下降就不适合应用了。因此，我们需要计算函数的次梯度。对于次梯度而言，其没有要求函数是否光滑，是否是凸函数，限定条件很少，所以适用范围更广。。官方定义就不抄了，大致就是：
$g$ is a subgradient of $f$ (convex or not) at $x$ if
$f(y) \geq f(x)+g^{T}(y-x), \forall y$
这里主要包含两层意思：

用次梯度对原函数做出的一阶展开估计总是比真实值要小；

次梯度可能不唯一。

也就是說，在函數不可微的地方我們仍然可以透過求subgradient，然後進行更新。

实际上，函数$f(x)$在$x$处的次梯度可以构成一个集合，通常用符号$∂f(x)$表示，这个集合是一个凸集，元素个数可能等于0或者大于0。
對於一個凸函數，一定可以找到一個全域最小值，那也可以想成是說他不存在subgradient:
$f\left(x^{*}\right)=\min _{x} f(x) \leftrightarrow 0 \in \partial f\left(x^{*}\right)$

然後來看gradient descent和subgradient method的差異:

gradient descent是沿著最陡方向去迭代更新，直到收斂
- 更新公式: $x^{(k)}=x^{(k-1)}-\alpha_{k} \nabla f\left(x^{(k-1)}\right)$
Subgradient method並不是下降算法，因為subgradient不一定是最陡的方向，從上面介紹就可以看的出來
- 更新方式跟gradient descent類似，只是換成了subgradient

注意subgradient不一定是最陡的方向，那他真的會收斂嗎? 答案是會的(太神奇了傑克!)，細節可以看文章內的證明。

另外，因为次梯度通常不唯一，而上面并没有提到任何次梯度的选取，因此理论上，任选一个都是可以使坐标不断向最小值点靠近，只是收敛的速率会不一样

了解subgradient是什麼，以及他可以更新不可微的函數後，我們回頭看relu的case:

在x=0時我們可以找到很多條切線通過這個點，這些線的斜率組成了subgradient的集合，所以我們可以任意取一個subgradient來作為relu在x=0該點的微分值。

懂了這個概念後，所有有尖點的函數都可以用subgradient來算了，像是L1, relu…blabla

題外話，L1也是convex，參考According to shape, an l1 norm is not convex. Why do people say it is a convex function?

總結

這篇文章重新回顧了深度學習是如何學習的概念，然後探討了一些問題:

deep learning怎麼使用gradient descent來學習
函數是不是convex對於找最佳解的影響
convex不一定可微
使用gradient descent時如果遇上函數不可微該怎麼辦

所以雖然大家都說deep learning的更新是用gradient descent，不過更仔細來說的話我感覺應該是:

對於函數可微的部分的確是用gradient descent
在函數不可微的地方使用了subgradient method

然後在來迭代更新，值到某個停止條件達成。

所以…下次再被問到”你的這個loss function可微嗎?”，就可以更精確的用比較裝B的方式回答對方:

“就算有不可微的地方依舊可以透過subgradient來autumatic differentiate，所以不影響updating”

前言

How Deep Learning Update?

Why Gradient Descent?

Convex or Non-convex

Is convex function differentiable?

Subgradient???

總結

Reference