談談神經網路的deep和shallow

05-01

在目前深度學習這麼火熱的時代里，有太多人都認為DL就是一個「black box」，好多非常出色現象背後的理論根據還沒有得到論證，大家就紛紛自然而然認為這樣做肯定是對的，不會錯。

就比如說，在我們設計一個非常toy的model過程中，我們往往的直覺觀念是，如果該model屬於神經網路的類型，那麼該神經網路的深度越深，那麼該model的表現能力就會越出色，對於input進入的feature的學習，肯定是要比shallow的神經網路優秀的。這僅僅是直覺上的感受，並且也有很多人做了相關方面的研究。就拿MNIST手寫辨識來說，發現，確實一個僅僅只有幾十層的網路的分類性能，在其他情況都相同的情況下，是遠遠不如一個幾百層的網路的分類性能更加準確。究其原因，我們知道，如果一個神經網路設計的越深，那麼model中所含有的參數的個數就會越多，對於input的feature的理解能力也要比shallow的網路更加強大。但是，這些好處的背後也會帶來一個非常嚴重的問題，那就是overfitting問題。要想做好這兩個方面的trade-off還是需要多點思考的。

由於自己也是DL的新手，剛剛入門到這個領域，如果寫的過程中，有哪些不對的地方，希望大佬們評論區各種拍磚就行。

關於神經網路的deep和shallow的問題，我會先通過以下3個問題來逐層展開，在展開的過程中，會涉及到近幾年有關這方面研究的paper，希望大家也可以認真讀一讀，仔細體會體會。

Q1：對於一個shallow的網路來說，是不是可以fit任意一個function？
Q2：我們怎麼通過一個deep的網路來fit一個function？
Q3：deep的網路就一定要比shallow的網路要好么？

在解決上述問題之前，我們先來review一些比較基礎的理論：

在上面這個圖中，

我們默認NN的input是一個落在[0,1]之間的標量，把這個NN看做是一個"black box"，也就是說他的內部可以有不管多少個hidden layer都是可以的。
有一個規定就是：activation function必須是ReLU。
然後輸出的output也是一個標量。

再來回到我們問題的本身。

假如我們現在有一個target function，當然target function的形式你可以任意設定，比如說這裡，我們就要求y=x^2

當我們有一個非常shallow的nn的時候，並且這個nn的parameters的非常的少。那麼，不管怎麼樣，我們的這套theories都不能很好的去fit我們所需要的target function。
但是，隨著我們parameters數集的擴大，此時的nn就會不斷具有去fit住我們所需要達到的target function。

我們現在又要進一步的討論下，當我們有一個非常deep的nn的時候，只需要非常small的parameters集合就可以去fit住我們的target function。
那麼，這個時候，我們不得不在去探索下，這種通過非常shallow的並且具有large的parameters的nn，和非常deep的並且具有small的parameters的nn都可以去fit住我們的target function，但是他們兩個之間的差異是什麼？

聲明：在上述的這些討論中，我們只去討論nn能否fit住我們的target function，而不去探討這些optimization和generalization的問題。

Can shallow network fit any function？

在討論這個問題之前，我們回顧下在以前ML的學習中，我們接觸到的一個理論：

對於任意一個連續的函數，我們都是可以通過帶有1個hidden layer的nn來擬合的。

用上面的這個圖來解釋下。

假如我們現在有一個僅僅只含有一層hidden layer的nn，並且activation function我們選擇為:ReLU。
對於任意input進來的x，在經過不同的bias後，在經過ReLU，我們就會得到一個分段的線性函數，如圖中兩個藍色圈圈後的綠色折線，就是通過activation function後得到的結果，之所以形狀不一樣，那是因為其加入的bias是不同的。
然後，我們在將這些neurons輸出的結果進行累加，就會得到最後的那個分段的線性函數。

好了，有了這個前提鋪墊後，我們在來定義一個叫做 L-Lipschitz function的東西，把它定義為 $f^*$ ，那麼，現在的問題就是，我們需要多少個neurons才能去approximate我們這個 $f^*$

在來講講什麼是 L-Lipschitz function吧。

通過上面的定義，我們能夠看出：

對於任意兩個輸入 $x_1,x_2$ 只要輸出的差距小於等於輸入的差距和L的乘積的函數，我們就可以定義為 L-Lipschitz function
上圖中右邊那部分，綠色的線條就可以被看做是一個1-Lipschitz

再繼續回到我們問題的本身:

我們需要多少個neurons才能去approximate我們這個 $f^*$

上圖中的K表示的是neuron的個數，N(K)其實表示的是一個函數空間，那麼此時的target function就是由K個neurons構成的函數空間中的一個function。
在定義一個 $varepsilon$ ,用來衡量 $f(x)和f^*(x)$ 之間的差距
目標就是找到一個整數K，使得 $max |f(x)-f^*(x)|leqvarepsilon$

如上圖所示，只需要最大差距小於 $varepsilon$ 就可以了。

其實，如果有的人不喜歡通過用max來衡量這種關係，換成用積分加開根號的格式也是可以搞定的

那我們繼續接著問題的討論，

我們知道，通過僅僅只有一個hidden layer並且具有K個neurons的nn，我們只能得到一個分段的線性函數，而對於任意一個function而言，這樣做肯定是不夠的。

上圖中的綠色點，然後通過將所有的綠色點連接起來得到的分段線性函數就是f。

$l$ 表示的就是這兩個輸入 $x_1和x_2$ 之間的距離。
$L$ 表示的就是我們定義的L-Lipschitz function中的 $L$ 。
我們可以看到，error其實是 $[x_1,x_2]$ 上的最大誤差了，通過前面的定義，我們知道 $max |f(x)-f^*(x)|leqvarepsilon$ 這個式子是必須要滿足的，那麼最大的error都滿足小於等於 $varepsilon$ ，將其在區間內移動到 $x_1和x_2$ 這兩個位置所得到的error肯定還是小於等於 $varepsilon$ 的。
通過簡單的推導，我們就能得到 $l leq frac{varepsilon}{L}$

有了 $l leq frac{varepsilon}{L}$ 這個關係式後，我們只需要將等號關係成立。

$l = frac{varepsilon}{L}$ ，那麼就可以得到需要 $frac{L}{varepsilon}$ 個區間。

那麼，上圖中的綠色折線我們該怎麼得到呢？其實不難。

任意兩個帶有ReLU的activation function就可以組成一個藍色的折線。然後我們將這些藍色的折線都相加起來，然後在加上bias，就得到了最終的綠色折線圖。

那麼接下來的問題就是，為什麼任意兩個帶有ReLU的neurons就可以完美的組成一個藍色的折線呢？

通過上面的過程，大家應該不能看出來了吧。就拿左上角的這個藍色折線圖來說，他其實是通過右邊的1和2兩個藍色折線通過相加得到的。
下面的這個圖其實就是上述兩個圖的分解過程。
那麼上圖中的那個綠色的曲線是通過3個折線圖+1個bias組成的，也就是3*2個帶ReLU的neurons組成的。
那麼，我們就能總結出如下的一般性結論：

如果我們要擬合一個具有 $frac{L}{varepsilon}$ 的綠色折線圖，那麼我們就需要 $frac{2L}{varepsilon}$ 個neurons

如果想要得到非常小的 error，那麼當 $varepsilon ightarrow0$ 的時候，那麼neurons的個數就趨於無窮大，這就和我們最開始說的，如果想要得到一個表達能力非常nice的shallow的nn的話，我們就需要非常多的parameters。

Why we need deep?

通過上面一個部分的推導，我們知道了，其實可以通過使用shallow的網路+一定數量的parameters去fit我們需要的任意function。那麼既然shallow的網路已經可以做這件事了，我們為什麼還需要研究deep的網路呢？

很簡單，就是因為如果我們用更deep的nn結構，就會得到更高效率的問題解決方法。可能有很多初學者並不能充分理解其中所蘊含的道理。我們接下來通過幾個analoy來對比著理解理解shallow和deep的關係。

就拿我們一般寫程序來說：

比如說，你的老闆給了你一個任務，讓你將大象放進冰箱里。
那麼，你其實可以通過三行程序搞定

第一行：打開冰箱門
第二行：把大象放進去
第三行：關上冰箱門

至於其中的每一步，我們並不知道它的具體實現細節，能不能做到，這都是個迷。所以，從這件任務能否完成的角度來講，都是低效率的。
再比如說，我們在ML的學習過程中學到的SVM with Kernel方法。

我們通過更多的計算步驟，就能得到更加精確的計算結果和完成效率
所以說，越deep的網路，就相當於我們在解決問題的過程中採用越多的step，step越多，那麼最終完成任務的效率也就越高。

再比如對於學EE的同學，我們可以通過數字電路中的門邏輯來類比：

我們繼續回到我們的問題本身：Why we need deep ？

對於一個比較shallow並且wide的網路（就是我們前面說的一個比較shallow但是具有很多parameters的nn）
和一個比較deep並且比較narrow的網路。
如果兩者具有的parameters的數量相同，那麼這兩個網路所能fit到的target function的能力是不同的。
shallow網路僅僅只由幾個線段分段組成，而deep的網路確是由很多個線段分段組成的

還是從分段線性函數來講，我們來找找分段線性函數的upper bound是什麼

如果你還不了解什麼是ReLU，那麼就得在好好去讀讀相關的paper了。其實通過ReLU的函數形狀，我們就能看出，一個帶有ReLU作為activation function的neuron將會具有兩種狀態。一種狀態就是x,另外一種狀態就是0。因為其函數形式是 $max(0,x)$ 。那麼，通過簡單的乘法原理，我們就能夠得到：一個具有N個neuron的網路，就會具有 $2^N$ 種不同的activation patterns，那麼就會得到 $2^N$ 個分段線性函數，那麼分段線性函數的upper bound就找到了。

一定要記住，upper bound只是理論上的計算最大值，實際中，是很難通過將一系列的分段線性函數組成達到其upper bound。

接下來，我們在引入一個Abs Activation Function幫助我們來進一步理解Why we need deep?

關於Abs Activation Function的構造其實很簡單，只需要將ReLU的結構進行修改，比如這裡，我們通過將 $max(0,x) 與 min(0,-x)$ 進行組合，就得到了Abs Activation Function

有了Abs的概念後，我們將兩個Abs通過串聯的方式堆疊起來，我們就得到了如上圖所示的結構：x->a1->a2。

關於下面的折線圖的解釋：

當x從 $0 ightarrow frac{1}{4}$ 的s時候， $a_1$ 從 $1 ightarrow frac{1}{2}$ ， $a_2$ 就從 $1 ightarrow 0$
通過上面的這個步驟，我們分別分析x在[0，1]上進行取值，就能得到最後類似「W」的圖像了
當我們再加入一個Abs function後，就得到了 $a_3$ 輸出

我們發現了一個規律，只要額外加入一個node，那麼在output那裡，我們最終output所組成的區域就會變成原來的兩倍。

發現了這個重要的結論後，對於shallow網路和deep的網路的認識，我們就能再進一個高度了

結合上圖和第一部分的分析，我們知道，要想多增加一條line的表達能力，shallow網路需要多2個neurons才能表達
但是對於deep網路來說，我每次增加一個neuron，我就能多2條line的表達能力
比如我現在要表示一個具有100條lines的分段線性函數：

如果採用shallow的網路，我們需要200個neurons才能表達出這個function
如果採用deep的網路，我們僅僅需要7個neurons就能表達出這個function $(2^6<100<2^7)$

通過這樣的比較，我們就能夠得出deep的網路比shallow的網路更加高效的原因了吧

分析完了分段線性函數的upper bound，那麼，接下來我們來分析下分段線性函數的lower bound

如果用k表示神經網路的寬度，h表示神經網路的深度，那麼我們就能得到最終的lines的下界為 $k^h$

如果有讀者對這方面的內容非常感興趣，可以去閱讀下面的paper

接下來，通過一系列的實驗來說明一些有趣的現象：

左邊這個圖的實驗是說：

我們通過對第一層的layer到第7層的layer分別添加一個noise，layer1表示是最靠近輸入層的那個layer，layer7表示的是距離輸入層最遠的那個layer。
通過實驗結果，我們可以發現，越靠近input layer的參數對於整個網路的影響性能是最大的，越遠離input layer的參數對於網路的影響性能是越來越小的。

右圖的這個實驗是說：

當我們僅僅對nn的某一層的參數進行train，而其他層的參數都random的賦值後，得到的表現程度的變化
兩個圖的顏色是相互對應的，可以發現，越靠近input layer的參數，更大程度上決定了網路的性能好壞。

Deep v.s. Shallow

通過上面的實驗結果，我們能夠看出來，當Deep和shallow的網路達到了相同的效果的時候，Deep需要的neuron的個數僅僅是Shallow需要的neurons的個數的log值。但是，這個時候的shallow網路並不是理想意義最optim的，也就是說，有可能這個shallow網路並沒有竭盡全力去和deep網路比較，說不定在它最optim情況下就能勝過deep的網路，也有可能這個shallow網路本來就是最optim的，但是它就是比不過deep網路的。

Is Deep better than shallow ?

在對deep的網路和shallow的網路進行對比之前，我們先來看看shallow有什麼好處？

通過前面的分析，我們知道，具有relu的網路是一個分段的線性函數
如果希望表現性能好，那麼我們需要使用最少的分段線性函數來fit住我們的target function

假如我們目前的target function是 $y=x^2$
那麼error的計算公式就可以通過圖中的這個積分來計算
我們為了找到一組parameter，a和b使得error最小，
通過求解，得到最小的error為 $frac{l^5}{180 }$ ，關於具體的數學推導，這裡就不展開了。

接下來的問題就是，如果你現在有n個線段，我們安排這n個線段的最好方法是什麼呢？

通過貪心方法的思想，我們不難證明，只要每個線段的長度都分配相同，那麼最終得到的error就是最小的。

通過讓shallow表現到最optim的狀態，我們發現，在其他條件都相同的情況下，shallow還是不如deep的網路好。

更多理論相關的內容，可以閱讀近幾年COLT,ICML,NIPS上面有關神經網路deep和shallow的paper。