[論文速速讀]Gradient Based Learning Applied to Document Recognition

〖想觀看更多中文論文導讀，至[論文速速讀]系列文章介紹可以看到目前已發布的所有文章！〗

paper: http://vision.stanford.edu/cs598_spring07/papers/Lecun98.pdf

CNN系列的開山始祖，LeNet(因為作者是Yann LeCun)，被應用在手寫辨識上，簡單的幾層Conv就可以在MNIST dataset上達到90%以上的Acc.。至今已經有兩萬以上的cite數量。

Abstract

Multilayer neural networks trained with the back-propagation algorithm constitute the best example of a successful gradient-based learning technique. Given an appropriate network architecture, gradient-based learning algorithms can be used to synthesize a complex decision surface that can classify high-dimensional patterns, such as handwritten characters, with minimal preprocessing.

基於gradient based learning的多層神經網路可以合成一個複雜的decision surface，使得在高維下也能夠很好地區分不同的pattern，例如手寫辨識，並且相較於傳統的技術，不需要太多的前處理就可以做得很好。

這篇paper的貢獻可以簡述成下列幾項:

傳統的手寫辨識技術需要較多的前處理來提取特徵，透過自動學習來建立一個pattern recognition systems，降低前處理的步驟
提出了基於梯度學習的神經網路，並和當前手寫辨識的各類方法進行了比較
手寫辨識系統不只有辨識的部分，還包含了句子的分段，paper中也提出設計了一個通用化的架構: graph transformer networks (GTN’s)來做這件事。

這篇文章中會聚焦在Deep learning的部分，關於後面的系統架構不會做太多的介紹，畢竟長達46頁看得頭很痛QQ

Introudction

傳統的pattern recognition通常分成兩個部分，因為data的變異性和豐富性使得無法完全透過手工來建立一個精準的辨識系統(要建立的feature太多了)，所以以前的方法會分成兩個部分(手工+自動)，大致上可以分成下圖兩個架構:

在這個架構中:

透過一個人工建立的feature extraction module取得feature，這個module將raw data轉換成低維的feature vector或是symbols，使得這些feature可以
- 很簡單的拿來進行匹配或比較的操作
- 對於不改變input性質的一些transformations和distortions具有不變性(比較robust)
- 這個feature extractor也包含大量的先驗知識(也就是需要大量的domain knowledge)，並且是基於特定任務的(for special case)
透過一個自動化的classifier module來進行分類

One of the main problems with this paper is that the recognition accuracy is larger determined by the ability of the designer to come up with an appropriate set of features .This turns out to be a daunting task which,unfortunately,must be redone for each new problem

一個pattern recognition system的好壞很大一部分取決於前面的feature extractor，很直觀的，因為如果特徵取的不好，那在後面怎麼學也是學不好的。並且這個extractor還是case by case，所以很耗費大量的人力成本

傳統的技術上，特徵萃取的技術都被限制在低維度空間上進行操作才能有比較好的表現，但近幾年來這個限制卻被突破了，作者認為基於下面的原因:

高效的設備成本越來越低，使得大家越來越有能力可以做一些運算量大的計算(例如numerical brute-force，其實就是在講Neural Network)
資料的取得更加容易，所以可以透過大量的real data來減少hand-crafted feature extraction
最重要的是，machine learning technique的興起使得可以處理高維度的資料

Leaning from Data

(看這段的時候好像再重新學習deep learning的基礎xD)

近期(注意這篇paper是1998年喔，大概是我兩歲的時候)一個成功的automatic machine learning技術，叫做”numerical”或”gradient-based learning”，對於第$p$個input pattern $Z^{p}$，給予一組權重$W$，使用機器學習的方式$F(\cdot)$可以學到一個predict $Y^{p}$，公式如下: $Y^{p}=F(Z^{p}, W)$

然後我們可以去計算這個prediction跟ground truth $D^{p}$的差異:

$E^{p}=\mathcal{D}\left(D^{p}, F\left(W, Z^{p}\right)\right) \\ E_{t r a i n}=\frac{1}{P} \sum_{n-1}^{P} E^{p}$

而一種最佳化方法就是找到一組$W$使得minimize $E_{t r a i n}$，這個performance通常會在獨立於training set的另一組data上來評估，也就是testing set。一些研究發現testing error和train error之間的差異(gap)會近似(這一項有點眼熟，好像就是VC bound? h好像就是VC dimension?)
(VC bound的部分推薦林軒田教授的機器學習課程，雖然很數學，不過稱過一次可以很清楚理解，讚讚)

$E_{\text {test}}-E_{\text {train}}=k(h / P)^{\alpha}$

跟在介紹VC bound時一樣，這個公式可以幫助我們理解怎樣對於machine learning是有幫助的:

當traning samples增加的時候這個gap會降低
當訓練複雜度h增加的時候， E_{train}會降低
- 所以這裡會有一個trade-off，在gap和$E_train$之間

如何想辦法降低gap的同時也降低training error，這類研究稱之structural risk minimization

通常會透過加一個regularization function來trade-off模型的複雜度

Gradient Based Learning

更新權重的公式，用到微積分的chain rule

$W_{k}=W_{k-1}-\epsilon \frac{\partial E(W)}{\partial W}$

或用SGD

$W_{k}=W_{k-1}-\epsilon \frac{\partial E^{p_{k}}(W)}{\partial W}$

這個都聽到爛掉不想看惹，跳過，有興趣再自己去補。

Gradient Back-Propagation

論文中提到，近年來gradient based learning的興起和下面幾件事情有關:

在高維度中，loss function的local minima並不是實務上的問題
- 在高維度中，其實收斂到鞍點的機率遠大於收斂到局部最小值，有興趣的可以參考梯度下降法的神经网络容易收敛到局部最优，为什么应用广泛？
透過back propagation，可以在多層非線性系統計算gradient
back propagetion搭配神經網路可以學習到複雜的任務

Learning in Real Handwriting Recognition Systems

跟Deep Learning無關，跳過

Global ly Trainable Systems

跳過跳過

Convolutional Neural Network for Isolated Character Recognition

傳統的方式會先透過人工的一些方法萃取出feature然後去訓練，不過如果想要讓模型自己學到這些feature的話該怎麼辦？

論文中提到了幾個困難點:

image size過大，如果一開始就用FC(Fully Connected Layer)會造成參數過多
FC這種沒有結構的網路並不具備平移、縮放等不變性(invariance with respect to translations, or local distortions of the inputs)，也就是說如果圖片有經過一些調整轉換、放大縮小、位移，則FC學到的特徵會完全不同。理論上一個非常大的FC搭配更多的data可以考慮這些狀況(使得所有case都可以被FC學到)，不過這不make sense
- 而CNN具備了平移不變性(shift invariance)，所以很適用在圖片上的相關任務
FC忽略了input的拓墣結構，對於圖片這種二維結構，相鄰的pixel有很大的相關性，不過這在FC中都只是彼此獨立的，甚至順序還可以互相對調而不影響結果。
- 在CNN中則是可以學習到一些local feature

Convolutional Networks

CNN的三個重要概念:

local receptive
shared weights(weight replication)
spatial(temporal) sub-sampling

local receptive

相較於全連接層的感受範圍是整張圖片，一點點圖片的變化就會影響萃取的feature。使用CNN的kernel(或是filter)可以做到局部感受野，使得神經網路能夠提取一些局部特徵(邊緣、角)，並交給下一層合成更高級的特徵。

shared weights

由於圖片可能會位移或是形變，在做convolution時使用了具有相同權重的kernel不只可以降低計算量，也可以想成在不同圖片上使用相同的局部感受野萃取相同的特徵，這樣的話物體在圖片的哪個位置就相對沒那麼重要了。

shared weights和local receptive是CNN對位移和形變robust的原因(shift-invariance)

spatial(temporal) sub-sampling

一但透過convolution得到feature map，特徵的位置就不是那麼重要了，特徵跟特徵之間的相對位置才是我們需要關注的。down-sampling的方式可以降低特徵在圖片中位置的精度，也可以使得CNN更加robust，這使得CNN對於物件在圖片中的什麼位置上影響比較相對較小

LeNet-5

最後來看一下LeNet的架構:

比較特別的地方稍微提一下:

C3的Conv layer

C3的Conv layer不是現在一般的Conv，而是將前一層(S2)的數個output，也就是feature map，做convolution，對應的關係如下表，列代表每一個feature map，行代表這一個convolution使用到了哪幾個feature map

作者認為這樣的好處在於:

降低參數使用量
利用對稱的連接方式學到不同的特徵

不過現在CNN幾乎沒人這樣用了…

F6為啥是84?

其實這也沒啥，神經網路數字想給多少就給多少，只要接得起來就好。不過為啥是84，難道LeCun也會通靈?

F6取84的原因是因為: 對應到ASCII的bitmap，如下圖每一個符號都是7 * 12的bitmap，所以這層的FC output是84

你說阿為啥要讓他等於ASCII的bitmap? 因為在原始LeNet中，output layer的計算方式是用到Euclidean Radial Basis Function ( RBF )來計算每個類別的值:

$y_{i}=\sum_{j}\left(x_{j}-w_{ij}\right)^{2}$

$x$是output layer的輸出(共10個)，$i$是類別(0-9)，$j$是bitmap中的每一個pixel(0-83)，所以RBF的值越接近0代表預測出來的圖片和ASCII該類圖片的bitmap越相近。

loss function

使用MLE(Maximum Likelihood Estimation)，希望訓所有訓練資料預測正確的「正確類別」 RBF 值之平均越小越好。

不過單純這樣設計會有一些問題，所以又補上了Maximum a posteriori(MAP)進去，細節這裡就不講了，因為後續CNN其實也不是用這個方式來設計。不過有興趣的可以參考[ 論文 ] Gradient-Based Learning Applied to Document Recognition或Gradient-Based Learning Applied to Document Recognition這篇，覺得講得非常仔細。

不過後來的model也都是用單純的cross entropy來training…

結論

原本是為了重看所有的CNN系列論文才開始看這篇，結果就發現第一篇居然給我有46頁讓我很無語(雖然最後也沒有全看完)。

重看這篇有總在複習Deep Learning跟CNN的感覺，主要更加了解CNN的三個特性(local receptive, shared weights, spatial sub-sampling)。以這篇為基礎，之後會開始看其他後續的CNN paper。