[ML] 隨機梯度下降法 Stochastic Gradient Descent

本文介紹主要分成兩部份，分別是梯度下降法，以及它的變形隨機梯度下降法

這邊推薦台大李宏毅教授的 ML Lecture 3: Gradient Descent

有詳細且深入淺出的教學

Part 1 - 梯度下降法 Gradient Descent

公式  新的權重值 = 舊的權重值 - 學習速率 * 偏微分後的梯度值  (梯度值 可以看作斜率)

Adaptive Learning Rate  演算法 Adagrad - 可以隨著訓練的週期調整學習速率(learning rate)參數


 

圖一[1]

補充知識

若把 loss function 用圖二中下方的泰勒級數作簡化

圖二(擷取自上課影片)

我們可以得到圖三中的方程式 L(theta)

但是前提是x足夠靠近x0

也就是圖中的紅色圈足夠靠近點(a,b)
(當然足夠小是多小，只能從實務上的試誤法經驗判斷)

圖三(擷取自上課影片)

那怎樣能夠讓 loss function 最小？

圖四(擷取自上課影片)

讓圖五中的藍色箭頭與黑色箭頭平行，並且剛好與紅圈等長

就能夠讓 loss function 最小

圖五(擷取自上課影片)

因此，今天梯度下降法能夠使用的前提條件是圖五中的紅圈足夠小

這樣泰勒級數才會準確

對應到公式的部份，影響自己算出來的數字有沒有在紅圈中，跟學習速率也有關係

所以學習速率本身也要足夠小，不然乘出來的數字會讓兩個平方項比d平方大

因此，之前遇到學習速率參數過大，造成loss function數值突破天際的原因就在這邊

圖六(擷取自上課影片)

目前真正最困難的是，當今天梯度變化非常小的時候

程式怎麽判斷是不是就是我們要找的global min ?

這些問題都還懸而未決...

圖(擷取自上課影片)

Part 2 - 隨機梯度下降法 Stochastic Gradient Descent

如果不是很熟悉，可以從 31: 15 開始看起

為了加速梯度下降法，我們在loss function這邊作一些改變

原本的loss function計算方式如下，他是把所有的輸出與理論值相減得到誤差值e

e經過平方運後

最後把所有的訓練用資料的e平方項數值全部加總起來得到數值L

圖(擷取自上課影片)

隨機梯度下降法則是改變策略

隨機取一個 example，並進行上述公式運算 loss function值 (n = 1)

我們來針對兩者進行比較:

梯度下降法看完所有的訓練用資料才更新一次

隨機梯度下降法卻是看過一次訓練資料就更新一次

所以有n張訓練用資料，就會更新n次參數

相比之下，隨機梯度下降法比起梯度下降法還要快得到較低的loss值，訓練速度較快

(天下武功，唯快不破 ? )

圖(擷取自上課影片)

[1] 圖片來源: http://www.yaldex.com/game-development/1592730043_ch18lev1sec4.html

[ML] Error 到底從那裡來？

Error 主要來自 bias 以及 variance

透過下圖，就可以知道 bias 和 variance 之間的差別

圖一、bias 和 variance

在不知道真實的公式的情況底下，我們可以透過統計的工具來試圖回推原始的公式長怎樣

簡單的model，variance比較小 ; 複雜的model，variance比較大

簡單的model，比較不受取樣的資料影響

圖二(擷取自上課影片)

什麼是 ovefitting  與 underfitting ？

我們來觀察一下下圖三

簡單的模型就相當於下圖左variance小，但是bias較大的情況

但是這些 model 並沒有包含正確的 model (紅心的部份) 

複雜的模型就相當於下圖右variance大，但是bias較小的情況

這些 model 有包含正確的 model (紅心的部份) 

因此平均之後得到的model(藍色線)，預測的準確性比起簡單的模型更接近正確答案(黑線)

圖二(擷取自上課影片)

我們可以將上圖的情況用另一張圖來表達

藍色線的部份是我們觀察到的總誤差(error)

如果今天我們的誤差來自variance，我們稱作overfitting

若我們的誤差來自bias，我們稱作underfitting

圖四(擷取自上課影片)

那今天有一個很重要的問題，我怎樣判斷我的模型誤差來自誰？怎麽修正？

bias過大 - underfitting

如果今天我們訓練後得到的 model，連訓練資料預測的結果都不好，那麼就是bias過大

屬於underfitting的情況

variance過大 - ovefitting 

但是今天我們訓練後得到的 model，訓練資料預測的結果還不錯，但是測試資料效果不佳

那麼就是variance過大，屬於ovefitting 

ovefitting 解決方法:  

1. 增加測試資料(collect data) ，非常有效，但可能不實際，例如資料難以取得

2. Regularization，增加lamda項，讓曲線變平滑，但是可能會除去不平滑的正確模型

Model 怎麽選？？？

常常 bias 與 variance 都會面臨 Trade-off，就是當選擇其中一項後，另一項表現會比較差

例如，下面的圖五就非常清楚的告訴我們背後的原因

圖五、總誤差與bias 和 variance的關係

所以，有個技巧就是所謂的N-fold cross validation，也就是將訓練用資料分成幾份(fold)

把其中一份當作validation set，並且在訓練的過程中不使用validation set來訓練

分別針對不同情境下，3個模型進行訓練，個別求出誤差值為多少

並選擇平均誤差值為最小的模型來當作最終的預測模型

圖六(擷取自上課影片)

[C語言] 從錯誤中學習 - 錯誤訊息 Segmentation fault(Core Dump) 到底是什麼？

之前在作業鬼打牆時期的時候，一直遇到編譯器吐出這個錯誤

Segmentation fault(Core Dump)

雖然在作業寫不出來而且死線逐漸逼近的時候，內心十分火大

但是看到這個不熟悉的詞彙

第一個直覺就是利用 Google 搜尋這個關鍵字

於是耐著性子 Google 它

發生原因

首先，找到了成大王紹華同學的 晶心科技實習面試  這篇文章
(先謝謝王同學樂意分享，造福後人，也謝謝幕後推手 Jserv )

提到了發生的原因

當記憶體存取到超出程式可用的範圍時，或是去寫入 read-only 的記憶體區段，就會產生 segmentation fault 的錯誤。像是宣告 100 個 entry 的 array，你卻去讀取第 300 個，就可能超出記憶體範圍或者嘗試去讀取 NULL 的 pointer。

ps. 額外小補充，在 interrupt v.s exception  這段也提到

interrupt 是由硬體或軟體所送出的訊號(signal)，要求 CPU 即時處理該事件，此時 CPU 會儲存當前狀態，並執行 interrupt，執行結束後便返回原本的狀態。 而 exception 也為 interrupt 的一種，但是由軟體產生的中斷，且只在特定情況下才被稱為 exception，像是程式無法掌控的狀況，如 division by zero, invalid memory access，所以 segmentation fault 也為 exception 的一種。 

另一篇則是 stackoverflow 上的文章 What is a segmentation fault?

發生原因寫得相當簡潔:

Segmentation fault is a specific kind of error caused by accessing memory that “does not belong to you.” 

(當存取了不屬於你的記憶體時，就會發生 Segmentation fault )

那為什麼有這個機制存在呢？

It’s a helper mechanism that keeps you from corrupting the memory and introducing hard-to-debug memory bugs.

 (是一個幫助程式開發者把管理記憶體的工作變簡單的機制，避免讓記憶體裡的資料變得一團亂，並且難以除錯。所以其實錯誤訊號是好人，而不是讓大家不能繼續撰寫程式的壞傢伙)

所以當出現了 Segmentation fault 錯誤時，通常是自己撰寫的程式不當的存取記憶體！

常見原因

其中一篇回答提到 常見的發生原因 像是:

1. 用一個尚未初始化、已經釋放記憶體的變數或是指標
2. 試圖寫入只能讀取的記憶體區段
3. scanf() 存某變數資料的數值時，忘記在該變數前加上取址符號＆
4. 使用 I/O的 printf()、scanf() 時，輸入了不正確的 Format specifier (%s, %c etc)


個人心得:

Objective - 學到了Segmentation fault

Reflective - 寫 c 程式的時候，時常遇到這種錯誤，這次把錯誤發生的原因記錄下來

是為了避免未來又發生一樣的錯誤

雖然死線逐漸逼近的時候，內心十分惱火

但是耐著性子把原因找出來並解掉才是最快解決他的方法

套一句沂詰的話，如果一開始就想好，就不會有這個錯誤發生

既然知道了這個錯誤，請記取教訓，節省並保護自己的寶貴資產-時間

Interpretive - 決習系統別輕易使用貪婪演算法來做出選擇，除非問題十分簡單直觀，不然後續造成的錯誤需要更多時間去填坑

Decisional - 尤其常見原因的第4點，複習過使用文件，再去使用它，可以節省往後更多時間

(千萬不要選擇看似當下省時間，之後卻帶來無窮時間黑洞的方案)

tshark 使用說明

tshark 最好的使用說明文檔，當然就是官方所寫的文檔

按照裡面的說明即可找到所需指令資訊

tshark - Dump and analyze network traffic

D.2. tshark: Terminal-based Wireshark

演算法作業3之痛不欲生

花費了大把的時間( >= 4 天 ) 全職 debug

求 weighted job scheduling  中總價值最大演算法的邏輯是正確的

但是程式卻有兩處錯誤

[錯誤之處]

1. 遞迴

但是遞迴一定要考慮好結束條件，並把結束條件程式碼寫在函數裡面的最上方

這樣就能夠達到條件就跳離遞迴，並且不會執行剩餘的程式

2. 邊界條件

儲存資料的邊界條件請檢查清楚...

想要取用第1001個陣列裡面的值，但是卻沒有宣告第1001個陣列位置

傳回來的數值是什麼我想鬼才知道那是什麽 XD

以上就是這次作業3 的錯誤之處

[個人心得]

一開始就把程式演算法與細節想清楚、設計好

將可以節省後續除蟲的大把時間

[下次目標]

1. 挖掘 C 語言中容易錯誤之處2項

2. C 語言程式規範、省力寫法

3. 學習C 語言 debug 工具

[python] dpkt 處理 pcap 檔函式庫

最近因為需要了解 Tensorflow 在進行分散式學習的過程中，權重更新的頻率，

因此想透過網路封包交換資訊的大小、頻率來摸索出分散式學習的運作機制

藉此來從系統的角度來熟悉 Parameter server 的運作機制

看過了這篇 pcap python library?

依序試過了 pycapfile, pyshark, scapy 這幾個讀pcap檔的工具

pypcapfile 則是因為官方資訊不夠完全，無法讀檔，立刻放棄

pyshark 則是因為還不夠成熟

scapy 在讀pcap檔上，因為一次把資料讀取進來的方式讓讀檔速度過慢，決定放棄

因此最後決定嘗試 dpkt 這款外部函式庫（ 官方 Document 在此 ）

dpkt

恰如它所說的 fast, simple packet creation / parsing, with definitions for the basic TCP/IP protocols

讀檔

讀檔的部份使用的語法是 dpkt.pcap.Reader()

f = open('test.pcap')  # 開檔
pcap = dpkt.pcap.Reader(f) # 讀檔

IPv4 or IPv6

如何知道IPv4 or IPv6 ?

透過下面的loop就可以知道版本號，如果 ip.v 回傳4，就是IPv4，若是6，則是IPv6

for buf in pcap:
     # Unpack the Ethernet frame (mac src/dst, ethertype)
     eth = dpkt.ethernet.Ethernet(buf)
     ip = eth.data
     if( ip.v == 4):
        print 'IPv4'
     elif( ip.v == 6):
        print 'IPv6'

另外，如果只是單純要取得IP資訊，也可以寫成

ip = dpkt.ip.IP(data)
ip = ether.data
ip_addr = socket.inet_ntoa(ip.src|ip.dst)

更多程式 API 的細節可以參考這份文檔:  My documentation on dpkt

網路知識補充

什麼是 socket？[4]

Sockets allow communication between two different processes on the same or different machines.

To be more precise, it's a way to talk to other computers using standard Unix file descriptors[5]. 

A file descriptor is just an integer associated with an open file and it can be a network connection, a text file, a terminal, or something else. 

而網路這邊所用的 socket 屬於Stream Sockets，並且遵守 TCP(Transmission Control Protocol) 規範

參考範例

1. dpkt Tutorial #2: Parsing a PCAP File

2. Source code for examples.print_packets

3. TCP/IP

4. What is a Socket?

5. 檔案描述符

[Linux] 利用 shell script 自動餵待測程式測試資料的方法

利用 shell script 自動餵待測程式測試資料的方法

拖了一個禮拜才著手進行撰寫

我想利用 Linux shell 自動測試的這篇文章可以延伸出非常多有趣的主題

經過 培任 的推薦

決定利用資料流控制 <  和 txt 檔來作為自動餵入測試資料的工具

自動餵入測試資料指令方法

bash shell script 程式設計

方法1

有一種方法如下，在 cmd 裡面先輸入要執行的程式的指令

配合輸出資料重新導向的 < 操作符號(output redirection operator)

後面接上要輸入的測試資料檔案，就像下方的程式碼[1]

./程式執行檔  <  測試資料.txt 

(若在檔案資料夾下，可以不加 ./ )

方法2


利用 cat  讀取資料[2][4]，再利用 pipe 指令 |  把 前面指令的 stdout 資料轉到｜後面指令的 stdin裡

cat 測試資料 ｜ ./程式執行檔

(若在檔案資料夾下，可以不加 ./ )

以上兩個指令，程式就會自動把測試資料輸入，並且自動執行，並把輸出結果列印在cmd裡

說明

. / 的意思[3]

這邊的 . 是指現在所在的資料夾路徑位置，兩個點 .. 代表上一層的父目錄

/ 就是指資料夾，兩個合在一起就變成現在這個資料夾底

例如 ./ file1 就是執行目前所在資料夾底下的 file 1

cat 指令

cat 指令是Linxu中相當常用的指令，它含有以下幾個功能

1. 讀檔

純讀檔

在 cmd 中輸入

cat file1

並按下Enter後，就會以全文字模式（all tex mode）印出檔案內容

讀檔並把資料寫入別的檔案

cat file1  file2

將 file 1 的內容讀出來，並寫入file 2

2. 連鎖(同時以字串顯示內容)

同時以全文字方式顯示多個檔案的內容

cat file1 file2 ... filen

當然也可以多個檔案開起來之後寫入同一份檔案中

cat file1 file2 file3 > file4

I/O Redirection 

>  or  >> ？

關於輸出重新導向的操作符號，> 不是一個便當吃不夠不會吃兩個的問題

如果在cmd裡面輸入

ls > ls.txt

是把 ls 的內容覆蓋過去ls.txt 原本的內容並且寫入進去

那如果再加入一個 >

ls >> ls.txt

則是保留原始ls.txt

並把 ls 的內容，寫入到 ls.txt 原始檔案內容之後


個人心得

之前不知道Linux環境下可以用這種方式輸入測試資料

還傻傻的一筆一筆輸入測資

有時候不小心手誤，輸入錯誤還需要暫停程式並且重新輸入 

回頭仔細想來，當下貪圖一時的方便其實並沒有節省多少時間

 反而在未來替自己挖了一個消耗時間的大坑還不自知 

知識就是力量這句格言在今天的情境下完美的體現出來

參考資料 

1.  bash shell script 程式設計

2.  The cat Command

3. What does “./” mean in linux shell?

4. 13 Basic Cat Command Examples in Linux

5. I/O Redirection

6. 輸入/輸出重導向（I/O Redirection）

系統工具- ftrace

ftrace - Function Tracer document

KernelShark - trace-cmd的前端讀取工具