• 延續上篇的內容，b其實可以水平同時計算

線性代數的角度理解

把它延展到$\alpha_{4,4}$

• 之後再對A做softmax(或其他激發函數)得到A’

總圖

• 上圖中只有$W^{q,k,v}$training data訓練

Multi-head self-attention

• 可以把q,k,v產生多個
  

Positional encoding

• 每一個vector出現在sequence的不同位置可能會有不同的意義
• 前述之計算並無考慮到相對位置，大家算法都一樣，也都有全部平等的計算
• 為每一個位置設置一個vector $e^i$，再把這個vector加上$a^i$
• $e^i$可以透過某個function產生，也可能是hand-crafted
• 或也可以是learn by data
• 仍然是尚待研究的主題

Self-attention應用

• Bert（NLP）
• transformer

Truncated self-attention

• 當sequence很大，我們的attention matrix會非常大
• 一次訓練的時候不要看所有sequence，看某一段就好

Self-attention for image

• 相片也可以看作是一個vector set，ex. 給定一個5x10 pixel的彩色圖片
  • 把channel當作一個vector(RGB)
  • 則一張圖片是一個5x10的vector set
• Self-attention GAN
• DETR

Self-attention v.s CNN

• CNN會考慮receptive field
• self-attention則是會考慮整張圖（整個vector set的vector）
  
• self-attention可以說是複雜版、更自由的ＣＮＮ
• receptive field變成可學習、控制的大小(truncated self attention)
  • Ref. CNN章節
    
• 這篇論文用嚴謹的數學證明CNN $\subset$ self-attention
• Ref.一開始的章節，我們知道更flexible的模型需要更多training data
  

Self-attention v.s RNN

• RNN不再講到，因為self-attention大多可取代
• RNN也是處理input是sequence的情況
  • 第一個vector做RNN，輸出丟FC，產生輸出，也加入第二個vector丟入RNN…
    
• RNN不可以平行處理，self-attention可以
• RNN難以考慮全面（左右更好），self-attention則可以（天涯若壁鄰）
• Self-attention加上一些東西以後，其實也能變成RNN(ref.)

Self-attention for graph

• 因為edge，所以我們知道哪兩個節點之間會有關聯性
• Attention matrix可以只計算有相連的部分就好
  
• 這算是一種Graph neural network (GNN)

GNN REF.

影片1

影片2

結論

• Self-attention有很多種變形
• 他的缺點是計算量過大(廣義版CNN…汗)
• self-attention最早用於transformer
  • 有時候叫transformer其實就是指self-attention
• performance跟speed的平衡
• 介紹各式各樣的transformers的變形：Efficient Transformers: A survey
  

• 至今為止，我們network input 都是一個vector
• 那如果輸入是可變動的一排向量（sequence）呢？

Vector set as input

• 長度不一的句子就是一個範例
• 關於word embedding如何得到，可以參考這個影片
• 現在的文字基本上都是被word embedding過，而句子就是一連串了文字向量
• 一段聲音訊號也是一個範例（25 millisecond），一個向量稱為『frame』
• 一個graph也是一連串的向量
  • Drug discovery中一個分子，可以看做一個graph
  • 社群媒體中，人（節點）可以是一個向量，ex.性別、年齡、工作等等

What is the output?

Type 1 (本課專注)

• 每一個vector都會有一個label
• POS tagging（詞性標注），每一個詞彙都要對應一個詞性
• 語音，每一段frame都會有一個Pheonic
• Social network，對每一個人可能會有一種廣告投放方式

Type 2 (hw4)

• 一整個sequence輸出一個label
• Sentiment analysis: 機器去判讀一段句字是正面的還是負面
• 給定一段音訊，分辨它是哪個人說的

Type 3

• 不知道輸出幾個label
• 稱為sequence to sequence(seq2seq)

Sequence labeling

• 對於每個向量，要做一個label

First approach

• 直接用fully connect network
• 問題出現：同樣輸入就會有同樣輸出，但是不能保證兩個vector之間是否有關連
• 需要consider the context

Second approach

• 直接給fully connected network整個window (hw2就是這樣做的)
  
• 問題：如果今天的任務是得要考慮整個sequence怎辦
  • sequence長度有長有短，window大小要變動，而且運算量非常大又導致overfitting

Third approach

• 採用Self-attention技術，先把向量加工再個別丟入全連階層
  
• 黑框框向量表示考慮過前後文的加工向量
• Self-attention可以有很多層
• 經典論文：Attention is all you need
  • Transformer
• Self-attention內部結構如下：
  
• 找出relevant vectors in a sequence，關聯度以$\alpha$表示
• 計算$\alpha$比較常見的做法是做內積，兩個向量各自乘一個矩陣($W^q、W^k等$)以後再做內積
  • 之後課程先只用這個方法

How to apply

• $q^1$表示輸入向量$a^1$對$W^q$矩陣相乘的結果
• $k^i$則表示內積的另一個算子，表示$a^i * W^k$以後的結果
• softmax不一定是唯一解，只是常見（用他沒有理由）
• 得出$\alpha’$以後，繼續根據他抽取sequence中重要的資訊
  
• 最後再把$\alpha’$乘上$W^v$，一個向量得到的分數越高，則越可能會dominate抽取出的結果

參考文章

• q:query，就是輸入的vector，用於與k做內積來判斷相似性
• k:key，指序列中的所有詞向量
• v:value，指實際的序列內容
• q,k內積的過程稱為Dot-product Attention
• 兩個vector之間的關聯越大，則 $\alpha$ 越大
• 上面步驟講到的都是encoder

作業題目

可進行的目標

Data augmentation (training)

• 搜尋torchvision.transform，docs

• 有用的文章：Pytorch提供之torchvision data augmentation技巧

• transform.randomRotate , resize等等

• 最後必須要toTensor，model只吃pytorch的tensor不吃PIL library的

Adv. Data augmentation - mixed up (training)

• mixup (把兩個影像混再一起，變成多重label)

• cross entropy loss function需要重寫

Module selection (搜尋torchvision.models)

• AlexNet

• VGG系列

• ResNet

• SqueezeNet

Cross validation

• 每次訓練更換dataset

• ensemble

以下是我對這作業除了Base sample code以外所做的變化，針對上述目標，有做的我才會列出來

First Approach

Note: 因為這次作業放在kaggle上寫&跑，而kaggle設計在結束比賽之前不能公開notebook，所以不能內嵌frame= =，下面只能先直接貼上code代替

Data argumentation

• 改動trains transform，新增兩個處理，一個是讓照片有0.6的可能水平翻轉，另一個則是把它做normalization
  • 針對個別batch算出mean,std做normalization的方法我沒找到，目前直接套網路上常用的3 channel RGB圖之平均值當參數 (mean = [0.5,0.5,0.5] std = [0.1, 0.1, 0.1])
       - 這樣做觸犯1個問題，我的normalization是單一標準對所有data做，還是對每個batch單獨這樣做？在這個case沒差，不過這是因為數字寫死，normalization做的實在有夠醜= =
       - 觸犯另一個問題是，我的layer之間有沒有再進行一次normalization呢？有待釐清

    1 2 3 4 5 6 7 8 9 10 11 12 13

    mean = [0.5, 0.5, 0.5] std = [0.1, 0.1, 0.1] train_tfm = transforms.Compose([ # Resize the image into a fixed shape (height = width = 128) transforms.Resize((128, 128)), # You may add some transforms here. transforms.RandomHorizontalFlip(p=0.6), # ToTensor() should be the last one of the transforms. transforms.ToTensor(), transforms.Normalize(mean,std), ])

Module selection

• 這裡我直接選用VGG11取代原本的自訂模型Classifier

Result

• 跑了至少100 epoch，結果training acc達到0.97，validate acc卻只有0.1x而且不再有更好結果，明顯的overfitting = =
• 可能要考慮加入cross validation
• 可能是data augmentation太弱？
• 可能是VGG11模型太強(彈性過高)
• 我耍笨不小心把訓練的過程輸出洗掉了，沒有圖片QQ

Second Approach

Module Selection

• 單純的把VGG11模型改回Classification

Result

• 看起來好像沒什麼變化，看來不是VGG模型導致overfitting
• 可能是normalization的部分出問題了，接下來嘗試把normalization改掉，用VGG train看看
  • 如果這樣成功的話，只能說應該是normalization把數字改成詭異的形狀了，算是一種人為mismatch吧
    

Third Approach

Transform

• 移除normalization

Result

• acc爆增回正常範圍了，看來真的是normalization的鍋qwq
  

• 上面這是最高紀錄，valid acc 有70%，位於epoch 32，我後來一直跑到epoch 52都沒看到更好的分數，就先卡掉了(看起來進medium概率近乎於零= =)
  

• 不過雖然70%比起之前的acc是大躍進，距離medium仍有一段距離，training acc也到達瓶頸，看起來是需要提高data augmentation的時候了

Forth Approach

• 偷偷參考了一下學長的筆記，發現新招數「AutoAugmentation」，適用在Transform內
• 這招的原理來自於這篇論文，可以從data裡面學到如何排Transform Augment
• 同時也從學長的筆記學到，因為code裡面有用BatchNorm2d (batch Normalization)，所以batchSize大一點會比較有利
  • 這好像就是元兇嗎orz，多做一次norm
       - 不過我只有在助教寫的Classification有看到norm，因為用的是VGG11，所以不確定是否仍然有用norm(沒看源碼XD)

Transform

• 新增transforms.AutoAugment()
• 新增transforms.RandomRotation(degrees = 32) //rotate+-32度

BatchSize

• 修改為96

Result

• 這次讓他跑了一整晚，充分認識到kaggel save&run的重要性= =
• 直接掛網頁按run all如果網頁停止回應或是閒置過久就沒了
• 這次訓練時間大約10hr，仍然沒有得到最終結果->網頁爆了
  
• 練到了291 epoch，感覺valid的acc就上不去了… 只能止步medium嗎

Fifth Approach

• 最後又重跑了一次training = =，沒有作任何更動，GPU quota還有18 hr 希望夠用…

Result (Finale)

= =凸

• 最終在epoch 389的時候終止了，最好的epoch在252，其實已經很接近當初的150 patience了
• 好在best model parameters有保存下來，接下來就是load model之後直接predict了

最終成果

Notebook連結

心得

這次作業是CNN的範例題，這次的圖像辨識題真的讓人思考到了如何去優化他，助教提供的sample code省去了start from scratch的痛苦，讓我們能專注在實作理論的部分

其實很多的技術(Batch normalization、crossEntropy+softmax、data Batch等等)都已經被函數包進去一次做好了，正常的時候是不會發現到他們的存在，這或許也間接印證了他們是十分有效提高命中率的方法吧。而真的需要實作的part其實不多，比較難的是要去翻出他們的document一一認識他們的結構並理解功能，這才是最難的部分

助教的sample code寫得蠻精美的，甚至有看出在自訂結構其實有保留空間讓學生自行切分training set跟valid set(可能是用於做cross validation用的)，考量到讓學生改進而保留空間，真的厲害！除了實作理論與閱讀結構以外，最重要的估計就是看懂這個訓練過程的資料結構了吧~

• network架構的其中一種變形:CNN
• 此講專注在CNN專門用在影像上的講解(目前也普遍用在影像)

Image classification - Version 1

• 我們需要假設圖片輸入的大小都是固定的
  • 如果大小不一，就得要rescale
• 是classification問題，所以輸出one-hot vector (向量的長度代表你能分出多少種類別)

如何把影像當作輸入

• 一張圖片其實是一個3維的Tensor (RGB)
  • Tensor(長跟寬)，並有3個Channel
• 我們把3維的Tensor拉直，成為一個向量 (這也是為何影像大小需要相同)

Train with fully connected network？

• 如果我們依然使用fully connected network來訓練，又假設neuron取1000個，則一個100x100的圖片輸入，會產生$1001003(彩色)1000 = 310^7$個weight，是一個巨大的數字，大幅增加了overfitting的風險 (彈性過大)
  
• 不採用全連接層，以下透過一些觀察來嘗試簡化這個網路

Observation 1

• 對於圖片辨識，我們要做的是針對圖片裡面找到一些關鍵的部位 (ex. 鳥嘴、眼睛、翅膀)
• 每個neuron並不需要看過整張圖片(即，不用fully connected)
• 我們可以讓每個neuron只看特定的區塊就好

Simplification 1 - typical settig

• CNN會設定一個『Receptive Field』，每個neuron讀取一個他負責的區塊
  

• Receptive Field可以重疊

• Different neuron是可以有不同的receptive field的

• 上述案例裡面，就是3x3的kernel size

• 通常會有一排(64、128等)個neuron去守備他

• 不同的receptive field之間的距離差距稱為『stride』

• 通常receptive field都會高度重疊

• 如果一個receptive field關注的範圍超出圖片範圍，就需要把外面的值補值(補0、補平均等)，稱為『padding』

• Receptive fields cover the whole image

Observation 2

• 當一個特殊部位落在不同的receptive field內怎麼處理?

Simplification 2 -typical setting

• 我們可以讓一些neuron採用共用參數(Parameter sharing)，讓他們的參數都一模一樣
• 因為輸入(receptive field)不一樣，所以各自的輸出也不會相同
• 可能rf1的第一個neuron跟rf2的第一個neuron共用參數，rf1的第二個跟rf2的第二個neuron共參… etc
• 這些共用的參數稱為『Filter』
  

Benefit of Convolutional layer

• 根據上述的觀察，我們成功讓CNN network針對相片輸入的訓練更加簡化
  
• Convolutional layer的model bias會比較大，但CNN是專門為影像設計的network
  PS. 這邊為何CNN bias會比較大，以及為何這樣不好，可以再google一下

另一個說明CNN的版本

Convolutional layer

• 所謂Convolutional Layer，裡面有很多的Filter，裡面都有一個3x3xchannel維的tensor

• 每一個filter都是要抓取某個pattern

• 以下假設是channel = 1(黑白照片)

• 我們把各個rf跟filter做內積，得出各值
  

• 接下來把所有pattern對各filter一樣的計算

• 這內積出來的一群數字稱為『Feature map』，再這個例子中，我們有64個filter，則我們的feature map會有64組(channels)數字，每組有4x4個數字

• 接下來進到第二層的convolution，我們的filter必須變成3x3x64，因為上一層輸出了64個channel，相對於第一層只有一個channel，第二層會出現64個channel

Note:

• 隨著捲積層的深入，我們觀察的圖片pattern會越來越大
• 繼續上面的例子，如果我們的filter之rf一樣是看3x3大小的話，因為我們的feature map中的3x3大小實際上是對應到圖片裡面的5x5大小(跟stride有關)，所以其實層數越高，我們一次考慮的範圍會越大！
  

Comparison of 2 version

• 第一個版本的共用參數，就是第二版本的filter(本slide忽略bias)
• 把一個filter掃過一張圖片，稱作『convolves over』
  • 例句(?)： each filter convolves over the input image
    

Observation 3

• 如果我們把一張大圖片縮小、拿掉odd columns，圖片還是不會有所影響(看起來差不多)，稱為subsampling -> pooling
• Pooling 本身沒有參數，沒有任何東西要learn，有些人稱他為一種激發函數
• pooling就是把圖片像素分組，然後從裡面只選一個像素留下，簡化圖片像素大小
• 下圖為示意圖
  
• 過度pooling仍會傷害訓練效益

The whole CNN

• 做完卷積層以後要做flatten
• flatten就是把矩陣數值拉直
• flatten完以後扔進fully connected layer訓練完，配個softmax(分類)，就是一個經典的CNN network

Application: GO

• 我們用一個19x19的向量來描述一個棋盤，把它扔進network以後輸出next move應該在的位置

• 下圍棋可以是一個類別分類問題

• 這個問題也可以用fully-connected network解決

• 但用CNN效果更好-> 棋盤可以看做一個19x19來描述

• 每個棋盤格的channel有48個(這格可能被叫吃等等)

• 這意味著圍棋與影像有許多相似特性

  • 可以只看小區塊(alpha go: 5x5)
       - Same pattern appear in different regions (雙叫吃等等)

• 棋盤可否用pooling ? 因為每格都很重要(精細度高) -> Alpha Go有沒有用呢?  

• 李宏毅教你畫重點XD：學著幫論文畫重點，抓critical terms
  

• alpha go 正文沒有提到神經網路結構，這是在附件找到的

  1. 視為19x19x48的image
  2. zero pads(padding補0至23x23)
  3. 有k個filter(競賽用的go，filter = 192)
  4. filter的kernel size = 5x5
  5. stride = 1
  6. 用到rectifier nonlinearity(ReLU)
  7. 2~12層都有做zero padding至21x21，filter數同，kernel size = 3x3，stride = 1
  8. 最後apply softmax function
     

• alpha go 沒有用pooling!!

Hen重要的Notes:

• 語音上、文字處理上，文獻上的方法要仔細看，CNN的receptive field設計會特別為他們特化，這裡講的單純是影像的
• CNN並不能處理影像放大縮小(Scaling)旋轉(Rotation)的問題… (向量問題)
  • 為此我們需要data augmentation
• 其實有Network架構(Spatial Transformer Layer)可以解決這個問題，請Ref.這個影片

• 簡短介紹Batch Normalization的技術
• 另一種直接改變error surface的技術(相對於動態lr，一種改善訓練的方法)

• 考慮以下模型，當$x_1$輸出很小、$x_2$輸出很大的時候，就會產生error surface橢圓的問題
• 因為$x_1$小，就算$w_1$變化很大，y的變化量也不會很大(因為相乘);$x_2$則相反
• 考慮可以把$x_1、x_2$相同的數值範圍
  

Feature Normalization

其中一種normalization做法

• 對多筆feature vector的同一dimention做標準化
  
• 標準化以後，該dim的平均值=0，$\sigma$ = 1
• 像這樣就可以製造比較平衡的error surface，方便optimization作業

Case：In deep learning

• 因為深度學習有多個層，雖然在一開始我們把x做了標準化，但是在經過一層layer計算以後，數值又失去了標準化，故我們需要進行多次的標準化
• 標準化要放在激發函數前後的影響並不大
  
• 以上圖為例，我們需要對z再度進行標準化，公式如下(feature=3的case)
  
  則可以得到
  $$\tilde{z}^i = \frac{z^i-\mu}{\sigma}$$
  後續層也依此類推
• 這個feature標準化的過程使得所有feature之間有了關聯性 -> 這是一個network
  

Case：training in batch approach?

• 這樣的標準化流程會跟著batch(一組batch內部做標準化)跑，不是所有feature納進來標準化
• 這樣的作法稱作batch normalization
  • 問題來了，我們會需要足夠大的batch size才能做一個好的標準化(誤差會比較小)
    
• $\beta、\gamma$是模型的另外兩個參數，透過學習得到
• 為啥需要這兩個參數?
  • 因為標準化會保證$\tilde{z}$之平均值 = 0，這樣的結果有可能會對模型產生一些負面影響，所以我們需要$\beta、\gamma$兩個參數來讓數值變成比較貼合模型需求
  • 問題：這樣不就又破壞掉標準化平衡了嗎?
    • 我們初始設定$\gamma = 1 , \beta = 0$，讓他們初始為真的標準化
    • 讓模型來決定值該怎麼分步

Batch normalization - testing data

• 剛剛講的都是training的情況下
• testing又稱inference
• 當真的是線上模型時，我們必須每一筆資料進來就進行預測，不能用batch
• 當數據只有一筆，怎麼做normalization($\mu=? , \sigma=?$)
• 實作上的解法(pytorch)：
  • 在training若有用這個技術，每次batch算出來的$\mu_i , \sigma_i$就會記錄下來再做以下處理  
    

在實際test時，就代入
$$\tilde{z} = \frac{z-\bar{u}}{\bar{\sigma}}
$$

• Batch normalization的實際測試結果，連結
  
• 紅色線是有做batch normalization
• 粉色線，使用sigmoid function
• 其他線，就是lr乘上$x$倍
• 黑色沒有用BN，用inception
• 收斂速度更快，但結果差不多

How does Batch Normalization help optimization?

• 下面這篇論文的作者發明這個詞”Internal covariate shift”

• 根據這篇論文所認為有以下可能
  

• 我們做參數update，將A變成A’，B變成B’，但是B的變動是根據之前算出來的a作為input，當整體更新了以後，B’要面對的input卻不再是a，而是經過A’算出來的a’，故導致仍舊失準

  • 而Batch normalization的作法，是讓a跟a’有相似的分布(similar statistics)，故誤差會比較接近

• 但是Experimental result並不支持這個緣故(打臉)

  • 打臉者認為實驗下來，a跟a’的分布都差不多，而且不管分布是不是差很多，影響都不大，於是這個假說是錯的(不是batch normalization的關鍵)
  • 不過實驗跟理論依然證明，Batch normalization依然會改變error surface的地貌
    
  • 此人認為batch normalization的發現可能是偶然(意料之外)的，但無論如何這是有用的方法
      - normalization有一堆方法，參考如下
    

• 這是如何分類的短版本，長版本連結如下:
  連結1
  連結2
• 這裡直接講分類是怎麼做的

Classification as Regression?

Regression長這樣

• 那classification怎麼看得像regression呢？
• 我們讓輸出的y(原本是一種類別)變成編號，跟$\hat{y}$比對
• 但這樣會有問題，class 1 跟 class 2 也不同類(loss = 1)，但他們的loss會小於class 1 跟 class 3的錯誤預測(loss = 2)
• 常見的做法是把class用one-hot vector來表示
• 當然，這樣我們就會希望output的y是一個向量而非純量 $\rightarrow$ 我們可以用多組的weight去做多次輸出，如下圖
  
• 我們通常會算出一個y以後，先做一個softmax(y)得到y’才去比較

Softmax activate function

公式如下
$$
y_i’ = \frac{exp(y_i)}{\sum_{j}exp(y_i)}
$$
圖例

softmax有兩個特徵：
$$
1>y_i>0 \\\
\sum_iy_i’ = 1
$$

• 其實就是把$y_i$的各自機率算出來，若y<0則機率~0

why add softmax at last layer in classification?

• 可以參考原版錄影，因為解釋較長
• 騙小孩的說法是，因為機率是0到1之間，所以我們可以把y做softmax讓他normalize

Note :

• Sigmoid就是2 class版的softmax(Ref.深度學習的數學地圖)

分類模型的loss function

• 我們仍然可以採用MSE來計算
• 但更常用的作法是用cross entropy

cross entropy loss function

公式如下
$$
e = - \sum_i\hat{y}_ilny_i’
$$

• 最小值就是當$y = \hat{y}$
• minimize cross entropy = maximize likelihood
• 基本上softmax是被跟cross entropy綁在一起的，因為向性很高
• 所以如果用cross entropy當loss，那模型最後一層自動就會補上softmax當激發函數(pytorch)

用optimizer的角度來證實cross entropy優於MSE

• 用數學證明的方式說明請參考過去影片
• 以下用舉例的方式說明
• 已知一個模型如下圖
  
  則MSE跟cross entropy的表現如下

• 用MSE的前提下，因為點就卡在高loss了，周圍很平坦，很難用梯度下降找到更好的點

• 這是一個透過改變loss function來改變整個error surface的例子

• loss function的定義是有可能影響訓練難度的

• Critical point 不一定是在訓練模型時會碰到的最大問題

Adaptive Learning Rate

• 我們都認為training loss卡住了之後，是因為parameters卡在critical point
• 其實有可能是loss function在兩個谷間碰撞，可能是兩組parameters之間剛好loss差不多
• 考慮一個情境，高爾夫球一直在球洞兩邊滾來滾去，就是滾不到終點
  
• 多數training其實還沒走到critical point就已經停止 (所以真正要注意的點不是critical point)

非卡在critical point的Example

• 給定一個convex error surface，如下圖
  

• 當learning rate太大，會容易在等高線密集的地方邁步過大，如下圖
  

• 或是當learning rate太小，容易卡在低谷幾乎動不了(要挪到X需要好幾百萬次更新)，如下圖
  

$\rightarrow$ 單一learning rate通常不能貫徹模型訓練的整個過程

如何設定learning rate? - Adagrad Approach

• 從上個例子可知，當某方向上等高線密集時，我們需要learning rate 小，反之則要大

• 為了讓$\eta$能自動變動，要調整公式

• 下圖為梯度下降法的原始公式
  

• 方便起見，這裡只用一個參數

• 更動以後的算式如下

$$
\theta^{t+1}_i \leftarrow \theta^t_i - \frac{\eta}{\sigma^t_i} g^t_i
$$

• 我們讓$\sigma^t_i$加入等式，這樣就可以讓learning rate變成一個parameter dependent的hyper parameter

如何計算sigma?

$$
\theta^{1}_i \leftarrow \theta^0_i - \frac{\eta}{\sigma^0_i} g^0_i
$$
其中$\sigma^0_i = \sqrt{(g^0_i)^2} = \vert g^0_i \vert$
接下來
$$
\theta^{2}_i \leftarrow \theta^1_i - \frac{\eta}{\sigma^0_i} g^1_i
$$
其中$\sigma^1_i = \sqrt{\frac{1}{2}[(g^0_i)^2+(g^1_i)^2]}$

…
一路推廣，可以得到

$$
\theta^{t+1}_i \leftarrow \theta^t_i - \frac{\eta}{\sigma^t_i} g^t_i
$$

其中

$$
\sigma^t_i = \sqrt{\frac{1}{t+1}\sum_{j=0}^{t}(g_i^j)^2}
$$

• 目前這個技巧應用在Adagrad

原理

• 當gradient小(平坦)，算出來的$\sigma$就小，learning rate大
• 當gradient大(陡峭)，算出來的$\sigma$就大，learning rate小
  

這樣會有甚麼問題

• 剛才的假設是同一個參數，他的gradient大小就固定一個值(?)
• 就算是同一個參數，他需要的learning rate也會隨時間而改變
• 我們期待就算是同一個參數在同一個方向，learning rate也會有所改變
  舉例，我們討論橫軸

如何設定learning rate? - RMSProp Approach

• 一個沒有論文的方法orz
• 方法如下圖
  
• 主要改變了紅圈圈起來的部分，捨棄了用前面所有的gradient求MSE決定$\sigma$的方法，RMSProp只採計上一個$\sigma$值以及這次的gradient之MSE和
• 多了一個hyper parameter $alpha$，調整對上一個$\sigma$的學習率高低
• 其實上一個$\sigma$就包含了前面所有的gradient之MSE，只是權重會隨著疊代越來越小

learning rate變動範例圖

回到一開始的範例

• [回到這個範例](# 非卡在critical point的Example)，我們來看看各approach的效果

Adaptive learning rate

• 為啥爆炸了?
  • 根據公式，我們把前面幾次的gradient都列入計算，因為在橫線的部分步伐很大，所以當走到步伐該縮小的時候，會爆衝
       - 但也因為公式，爆衝一陣子以後learning rate會逐漸縮小，然後回歸正軌，等待一陣子以後learning rate上升再度爆炸

解法：learning rate decay

• 隨著訓練的進行，我們一定越來越接近終點
• 可以隨著時間降低learning rate，開始微調

解法2：Warm up

• 算是一種黑科技
• 先變大learning rate，再縮小(?)
• 在訓練bert的時候常常用到，但他在很久以前就出現在論文過了
• 在transformer中也出現過，見下圖
  
• 一種可能的解釋是，因為$\sigma$是統計的數據，在訓練初期的時候容易失準，故初期讓learning rate小，等到$\sigma$精準一點以後，再讓learning rate變高
• 相關paper : RAdam

Summary of Optimization

• 雖然Momentum跟$\sigma$都使用過去的資料，但不會因此抵銷
  • Momentum是把所有gradient加起來，故有考慮方向與正負號
  • $\sigma$只考慮MSE

下次預告

• 當訓練過程遭遇大山，要如何闢路繞過去？
• 有沒有可能直接炸掉大山，改變error surface呢?
  $\rightarrow$ Batch normalization
  PS. 課程跳到2-6哦

Note

• 現今最常見的Optimizer:Adam其實就是RMSProp + Momentum

• Adam的細節自行參考

• arxiv論文年代看法

  • https://arxiv.org/abs/1512.03385為例
       - 15代表2015年出版
       - 12代表12月

前言

• 之前課程(Ref. 2021版1-1)說到，在實際train data時我們不是實際把所有Data算出來對L微分求loss，而是把Data先分組切成batch，而所有batch看過一遍，才叫1 epoch
• 我們可以設定shuffle，就是每個不同的epoch，data都會重新分組

Batch size對模型之影響

• 首先比較兩個case：
  
• 左邊沒有用batch，而右邊batch size = 1
• 左邊表示每次必須看完所有data，參數才能更新一次；右邊則相反，每看完一個data就更新一次參數
• 一個是重攻擊長CD，一個是輕攻擊短CD (?)

大batch優缺

優點

• 威力大(更新幅度大)且每步都很穩

缺點

• 超級慢
  (小batch優缺則顛倒)

small batch or big batch?

• 兩邊看似各自相對，但我們還沒考慮平行運算
• 若考慮多核心，其實大batch不會比較慢
• 以下圖為例，用tesla V100 GPU，batch size到1000都很合適(梯度法)
  
• 因為高batch不一定更花時間，所以其實在平行運算下，大batch的每epoch速度甚至還比小epoch還快
• 不過，就算是平行運算下，大batch一定比較好嗎?
  • 與直覺相反的是，noisy大有時候反而可以促進訓練能力(如下圖)

• 相同model(同bias)下，smaller batch size有更高的performance
• 問題來源於optimizer fails(Ref. 2021版2-2關於如何判定問題是哪種)

為何small batch size可以有更好的結果？

• 一說是Noisy update is better for training
  見下圖

small batch下，或許$L^1$卡住了，但是因為$L^2$跟$L^1$有不小的差距，所以剛好可以讓參數更新然後把參數撞開critical point

small batch still better for testing data?

• 我們知道了small batch在training set表現更好，那testing data是否也是如此呢?
• 根據這篇論文，可以知道small batch在測試資料也有好表現

• 就算能把big batch model的準確率練到跟small batch model差不多(調hyper parameter)，在測試時也會有差距顯現 $\rightarrow$ big batch有overfitting問題
  目前普遍認為的原因如下：
  • 就算是卡在local minima，也有分好壞
  • 周圍平坦的local minima較好
  • 而論文認為大batch size傾向會讓我們走向尖銳的minima point
    • 一種說法是，小batch size更動頻繁走向豐富，容易走出周圍很高的minima point(對於逃離critical point能力較高)，而停在平坦的minima point (Ref. 2021版2-2 鞍點)

  • 因為testing 跟 training的loss function，肯定會有所小偏差，如下圖
    

Summary：Batch comparasion

• 因此，batch size最終成為了一個hyper parameter

魚與熊掌兼得的辦法?

• 看ref啃論文 = =

另一個對抗saddle point或minima的技術 : momentum

• 當small gradient的時候，我們走到一個鞍點或局部最小點之後就會停下來
• 但我們可以用物理式來思考，球由高處滾下來到最低點碰到上坡，不一定會停下來，因為有動能

Review : 原本的梯度下降

梯度下降+momentum

• 簡單來說，就是加入慣性，額外參考上一次的移動軌跡

• 多了一個hyper parameter $\lambda$
  

• 這裡只討論optimazion失靈的時候，如何把梯度下降做得更好

  為何opti會失敗（grad）？

  • gradient decent=0，使參數無法再更新
  • 點卡在local minima or saddle point(稱為卡在critical point)

  分辨critical point是saddle point or local minima

  • 雖然我們無法知道loss function長怎樣，但可以用泰勒展開式逼近
  • 給定一組參數$\theta’$
  • 則使用tayler series approximation
    原式為
    $$
    f(x) = f(a) + \frac{f’(a)}{1!}(x-a) + \frac{f’’(a)}{2!}(x-a)^2 + ….
    $$
    我們取到2次微分，代入$x = \theta及a = \theta’$得到
    $$
    L(\theta) \sim L(\theta’)^Tg + \frac{1}{2}(\theta - \theta’)^TH(\theta - \theta’)
    ,其中 g = \nabla L(\theta’)(請參考上週)
    $$

• 其實g就是$L(\theta’)$對$\theta_i$的一階微分，Hessian是$L(\theta’)$對$\theta_{ij}$做二次微分

• 因為critical point的時候g = 0，所以我們要考慮H(也就是2次微分的部分)來分辨是哪種問題，2次微分可以看出地貌
  把Hessian部分拉出來討論
  
  要如何確認滿足哪個原因呢?

  • 線性代數：正定、負定、均非 (看H的eigen value)

  範例說明

• 給定一個模型$y = w_1w_2x$，資料僅有一筆，$f(1)$時其label = 1，且w1w2之間不具有任何激發函數，loss function採用MSE

• 則x=1時透過爆搜我們可以得出下面的error surface(偷偷看正解圖)
  

• 其中鞍點的四周都是高牆，無法離開

• 局部最小點則是在範圍內找不到更低的點

• 但假設我們不知道這個error surface，我們可以應用上面的方法來測定他是哪個問題，根據MSE公式我們得出
  $$
  L = (\hat{y}-w_1w_2x)^2 = (1-w_1w_2)^2
  $$
  對他們做微分可以得到(注意chain rule)
  $$
  g = \frac{\partial L}{\partial w_1} = 2(1-w_1w_2)(-w_2)
  $$
  $$
  g = \frac{\partial L}{\partial w_2} = 2(1-w_1w_2)(-w_1)
  $$
  代入g=0，可以發現當$w_1 = w_2 = 0$，有critical point
  接下來要確認他們是哪個問題，就繼續再做微分:
  
  代入剛剛的$w_1 = w_2 = 0$得到
  $$
  H =  
  \left[
  \begin{matrix}
      0 && -2 \\\ -2 && 0
  \end{matrix}
  \right] \tag{3}
  $$
  抓H的eigen values來知道他是哪個point

case: saddle point

• 我們可以藉由H來得到參數該移動的方向
  令$\lambda$是H的一個eigen value, u為$\lambda$的其中一個eigen vector
  則
  $$
  v^THv = u^THu = u^T(\lambda u) = \lambda \vert \vert u \vert \vert^2
  $$
  若今天$\lambda < 0$則必定$u^THu<0$，回顧剛剛的式子
  $$
  L(\theta) \sim L(\theta’)^Tg + \frac{1}{2}(\theta - \theta’)^TH(\theta - \theta’)
  $$
  可以知道$L(\theta)必定>L(\theta’)$
  
  我們只要將$\theta’沿著u的方向更新u得到\theta$，就可以再次降低loss

範例說明

• 延續剛剛的例子，我們知道$H的\lambda_1 = 2, \lambda_2 =-2$，屬於saddle point(非正定與負定)
• 取$\lambda_2 = -2 , u = (1,1)$，則把$\theta = (0,0)+(1,1)$，就可以逃出saddle point
• 實務上不易使用，因為要做出2次微分且還需要用到找出該矩陣的eigen value，計算量過大 (還有別招可以用)

Saddle point vs. Local Minima

• 在三維的密閉石棺中，在更高維度未必是密閉的
• 在低維度的local minima中，是否只是高維中的saddle point?
• 當參數超級多，是否極度有可能local minima其實只是saddle point? (假說)
• 在實作中，絕大多數的模型，critical point所在點中，幾乎找不到所有eigen value均>0的範例，表示我們幾乎不可能找到完全的local minima
• 定義一個數值”Minimum ratio = $\frac{正\lambda數}{\lambda數}$”，表示你的critical point有多像local minima
• 所以我們可以知道，通常一個模型train到loss卡住，極高可能是卡在一個saddle point