LeNet
===
> 由於多層類神經網路的架構在高維度資料(手寫辨識)有不錯的效果，而且相較於傳統的辨識方法，不需要有太多的圖片預處理。這篇主要是以我的觀點來敘述，所以會介紹幾個重點: Lenet架構，Graph Transformer Network(GTN)。過去在處理文字辨識分成好幾個部分去進行，其中包括，extarction, segmentation, recognition, language modeling。而GTN是一個基於gradient learning的network，可以將上述的部分同時進行。

## 介紹
LeCun認爲，使用機器學習的技術解決模式識別問題變得越發重要。他寫這篇論文的一個重要目的就是證明識別的系統可以依賴自動學習的技術，而不是手動設計的方法。以字符識別爲例，LeCun證明人工設計特徵抽取的工作可以通過特別設計的機器學習方法替代，並直接應用在原始的像素圖像上。這裏字符識別任務是指從識別圖像上的字符。當然，LeCun這裏想要證明的就是使用神經網絡可以較好地做字符識別任務。

傳統的圖像辨識準確度與如何設計特徵提取有著密不可分的關係，而且常常必須針對不同問題而重新設計特徵提取。


在使用機器學習自動識別字符之前，通常使用人工設計extraction的方式，將圖像的特徵抽取出來，然後使用分類器進行分類，得到字符識別的結果。人工設計的extraction方法通常叫做視覺描述器（Visual Descriptor - Wikipedia），如局部二值模式（Local Binary Patterns）就是用某個像素周圍的8個像素值與之比較，大的是0，小的是1，得到的特徵。如下圖所示：


## Learning From Data
近幾年來，伴隨機器學習的盛行，越來越多方法被提出，其中最受歡迎的就是梯度學習的方法。

透過計算以下的式子($Z^p$為輸入的資料，W可以視為權重，$Y^p$為預測值，$E^p$為誤差值)，可以求得$Y^p$及$E^p$，將所有的$E^p$相加取平均後可以得到訓練資料的誤差值$E_{train}$。

\begin{gather*}Y^p = F(Z^p, W) \end{gather*}
\begin{gather*}E^p = D(D^p, F(W, Z^p))\end{gather*}

在訓練過程中，往往希望找到一組能讓$E_{train}$達到最小的參數。

通常模型的準確度我們還會用另外一組與訓練資料獨立的測試資料集，計算
$E_{test}$來評估，有一些研究表示用$E_{train}$與$E_{test}$來評估模型的好壞。

\begin{gather*}E_{test} - E_{train} = k(h/P)^{α}\end{gather*}

其中 P為訓練資料數量，h為模型的複雜度，α為0.5~1.0的參數，k
為常數。

如果P越大，兩者的誤差就會越小，即資料量越多能學到的特徵也越多，模型也會越準確。如果h越大，模型也越複雜，在$E_{test}$不變情況下$E_{train}$會越小，但兩者差卻越大，所以找出最好的h是非常重要的。

## Gradient-Based Learning
這邊主要介紹梯度下降，相信有學過深度學習的對這名詞並不陌生。以下式子為梯度下降更新權重的方式：
\begin{gather*}W_{k} = W_{k-1} - ϵ \frac{\partial(E)}{\partial(W)}\end{gather*}

其中ϵ為常數，我的理解是可以把它當成是learning rate，也可以用其他方法，例如文章中提到的inverse-Hessian matrix，共軛梯度法求得ϵ(這邊沒特別深入了解)。文章中也提到，隨機梯度下降法(Stochastic Gradient Descent)來最小化loss function，這邊就不多做解釋SGD。

## Gradient Back-Propagation
Gradient-Based Learning過去只限用於線性模型中，但近年有一些發現使得梯度下降有更廣泛的運用:
1. 在非線形模型中，例如Boltzmann machine，發現能將梯度下降法成功運用
2. Hinton 等人發現本來用在控制理論中的 Back-Propagation 演算法結合梯度下降可以有效的訓練多層的神經網路
3. BP應用sigmoidal unit 的多層神經網路可以解決更複雜的學習問題

## Learning in Real Handwriting Recognition Systems
這節簡述了手寫辨識的問題，並解釋了手寫文件辨識中一個很重要的問題: Segmentation，除了正確的辨識每個字以外，我們還需要能夠正確的從一串文字中區分每一個字。其中有一個方法叫做Heuristic Over-Segmentation(HOS)，如下圖所示，透過heuristic image processing將圖片中的文字切成一個一個小區塊，通常切完後會用一種圖表示，Directed Acyclic Graph，圖中可以看到4被切成："L", "1"，從兩點之間箭頭可以得知HOS將"3", "L"視為同一個字元，所以字元之間會互相影響，除非像"3", "2"本來就距離比較遠，所以在切時就不會互相影響


## LeNet-5

上圖為LeNet-5的架構，總共有七層。其中C代表Convolution，S代表subsampling，也可以稱為Pooling。簡單介紹一下Convolution及Pooling:Convolution就是在對圖片去做擷取特徵的動作，找出最好的特徵最後再進行分類。Pooling就是選取特徵，保留重要資訊，並降低Overfitting。

其中比較特別的是，S2與C3之間的連接，這兩層並不是完全的連接，如下圖所示，S2的特定幾個feature map只與C3的特定幾個feature map連接，目的是為了讓整個network架構不對稱(我覺得原因是減少參數量吧)


在output layer是Euclidean Radial Basis Funciton(RBF)。
\begin{gather*}y_i = \sum_{j}(x_j - w_{ij})^2 \displaystyle \end{gather*}

F6的output為84是因為當時Lenet希望能用來辨識ASCII的字符，那這些字符適用7X12bitmap表示

Graph Transformer Networks(GTN)
---
在介紹GTN之前要先了解什麼是GNN(Graph Neural Networks)，由於現在比較常用的CNN是針對屬於歐式空間的資料進行處理，然而近年來非歐式空間的應用變多，因此更多人開始研究基於圖的深度學習，即是GNN。
但是GNN有以下缺點:
1. 對於異構圖，由於GNN只用於處理同構圖，因此效果不好。（什麼是異構圖呢？下面這張圖清楚的展示了異構圖：在一個圖中，節點類型數大於1，如author類型，paper類型，venue類型；邊的類型數大於1，如author -paper邊，paper-venue邊；這樣存在不同的節點類型和邊類型的圖就是異構圖）


2. 一種簡單的處理方法就是忽略類型，缺點就是無法獲取到類型信息

3. 手動設計一個meta-path，例如下圖中紅線所示路徑，如果對於每一個問題都需要單獨的手工設計meta-path；並且最終效果受到選擇meta-path的影響；meta-path的選擇需要對應領域知識。


於是GTN就是為了解決此問題出現，它能夠對圖結構進行學習的神經網絡。

1. 提出了一種新的圖變換網絡，識別有用的元路徑和多跳連接來學習圖上的有效節點表示

2. 圖的生成是可解釋的，提供有效路徑連接的解釋

3. 證明了圖變換網絡學習的節點表示的有效性，從而獲得了最佳的性能，而現有的方法在異質圖的所有三種基準節點分類中都使用了領域知識

以下面圖為例：


1. 此圖即表示GT(Graph Transformer) Layer，它先從tensorA (每一片就是一種edge type)中用權重選擇adjacency matrices(即edge type)。權重選擇的方式也可以理解成捲積，卷積後的兩個matrices分別是兩個圖解構，表示為Q1和Q2

2. 選擇matrices的兩個卷積核是用softmax計算得出的(比如圖中例子，一個卷積核說取最前面的matrices，一個卷積核說取最後面那個matrices)，但實際上是帶有權重分配的

3. 然後再將兩個matrices組成新的圖結構

## 參考文獻
[http://yann.lecun.com/exdb/publis/pdf/lecun-01a.pdf](https://)
[https://www.twblogs.net/a/5d0f4dfbbd9eee1e5c81dc38](https://)
[https://medium.com/@z8663z/%E9%96%B1%E8%AE%80%E7%AD%86%E8%A8%98-a-comprehensive-survey-on-graph-neural-networks-%E7%B7%A8%E8%BC%AF%E4%B8%AD-78118deae743](https://)
[https://blog.csdn.net/mirrorssssssss/article/details/103797829](https://)

###### tags: `ML`