[Bash] Why are bash tests so picky about whitespace?

寫過bash腳本的就知道，有時候多一個空白，差很多

Why are bash tests so picky about whitespace?

辨認的關鍵在於 Bash 怎麽辨識腳本裡的指令

[演算法] 尋找Minimum Spanning Tree 的演算法- Kruskal & Prim Algorithm

演算法說明與內容如下

Kruskal's Algorithm:

Minimum Spanning Tree：Kruskal's Algorithm

實作法2: minimum-spanning-tree/apm.c  (謝謝沂詰教會我這個巧妙的作法)

Prim's Algorithm:

Minimum Spanning Tree：Prim's Algorithm

[演算法] 深度優先演算法 Depth-First-Search(DFS)

無向圖的DFS - Depth First Search (DFS) Program in C

待回答:  DFS traversal in directed graph in C

速度分析: Which is faster: implement Depth First Search using recursive function calls or using a stack?

利用Google提出的 Kotlin語言 撰寫Depth-first search 演算法
Basic graph algorithms in Kotlin

[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