使用 LSTM Autoencoder 進行異常檢測

簡介
上回提到，因為 LSTM 能記住事件的先後次序，所以它特別適合用來處理一些，具有時間順序的數據 (Time Series Data) 。上一期，我們實現了如何使用監督學習 (Supervised Learning) 做未來預測。而這一次，我們會用 LSTM 實現另一種常用的系統：非監督式異常檢測 (Unsupervised Anomaly Detection)。

所謂異常檢測 (Anomaly Detection)，其實是指：當我們訓練系統的時候，我們可以透過提供大量正常數據，繼而讓系統自己找出這些數據的規律。然後，當系統突然收到一些與既定規律相違背的數據，它就能自動把這些數據判別為異常。

這種模型，特別適合用來做入侵偵測系統 (Intrusion Detection System)：因為黑客入侵等事件並不尋常， 而且入侵模式千變萬化。所以，我們只能大約知道正常的網絡流量會是怎樣。相反，對於黑客進行攻擊的情況，我們所知的並不多。故此，系統設計者能只提供正常情況的數據，以及極少量的入侵數據（這種數據，在 ML 世界中，也稱為非平衡數據 (Unbalanced Data)），然後就讓系統自行找出正常情況的規律。

是次實作，我們會用另一個較簡單的例子：心跳規律來做示範。我們只需要提供正常的心跳數據，讓系統自行訓練，持之以恆，它就能辨認出何謂正常的心跳。訓練完成後，只要系統發現一些奇怪的心跳規律， 它就會回報異常。這次的實作，是改自 Curiousily - Time Series Anomaly Detection using LSTM Autoencoders with PyTorch in Python 的範例。我改進了以下兩點：

• 使用 DataLoader 來進行 batch training
• 簡化代碼，使其更易閱讀及改裝

---

實作模型：LSTM Autoencoder
Autoencoder，顧名思義， 就是一種自動編碼 (Encode) 及解碼 (Decode) 的轉碼器。

簡單來講，你可以把它想像成一個有損壓縮 (Lossy Compression) 的工具：首先，它會把收到的訊號，編譯 (Encode) 成一個非常細小的編碼 (Embedding Code，下圖紅色部分，又稱為 Bottleneck Layer)。然後， 當解碼器 (Decoder) 收到這一條小編碼，就會試圖把它解譯成原本的訊號。若果轉譯來回的數據十分相似，就代表它帶來的損失很少，也代表這對 Encoder 和 Decoder 的效能很強。相反，若果它在經過來回轉譯後，輸出與原本大相逕庭，就代表這對 Encoder 和 Decoder 失真的情況嚴重，十分垃圾，並不可靠。

Information Theory 告訴我們，由於數據儲存密度有限，若果壓縮要做到可靠，只有兩個方法：一是加大 Embedding Code，讓它存放更多資料，另一方法，則是按照數據的規律，度身訂造 Encoder 和 Decoder，以達至極致的壓縮比率。 由於我們的系統會固定 Embedding Code 的大小 (Embedding Code 的大小，通常固定在原數據十分之一左右) ，所以系統不能使用第一個方法保存資料。也就正說：系統會被迫用第二個方法達成極致壓縮。

正因如此，隨著訓練時間越長，系統將會越來越依靠訓練數據（也就是正常數據）中的一些固定規律去運作。最後，它會變成一個專為正常數據而設的壓縮器。換句話說，這個壓縮器，能在你放入正常數據的情況下，完美地進行極致壓縮。但如果你放入一些異常數據，這個壓縮器就會突然失控，結果變得強差人意。而我們這次，正正就是利用這一種特性，來判斷數據是否異常。

---

演示代碼

https://github.com/cmcvista/MLHelloWorld/blob/main/LSTMAutoencoder/HeartbeatAutoencoder.ipynb

---

幾個重要變數
是次實作，有幾個變數，需要仔細解釋：

• 一條時間順序的資料 (data_seq_len) 的長度為 140，特徵 (data_n_features) 為 1。
  這是指一個數據長度為 140， 而維度只有 1（ y 座標為 1 ）。
• Embedding code 的長度為 (data_embedding_dim) 為 64，
  也代表它的 Tensor Dimension 是 64*1。
• 整個系統的大小為 [140, 128, 64, 64, 128, 140]
  （格式：[Input, Hidden, Embedding, Embedding, Hidden, Output] ）
• 訓練 100 次對 LSTM 來講，其實並不足夠，但由於只作示範，就懶得執行太久。
  

---

Losses 計算方法
損失 (Losses) 的定義，是指解碼後的結果，跟原數據的差異大小。在這次實作中，為了與原例子一樣，我使用了兩組數據之間的 L1Loss 的總和去定義。不過，其實用其他方法（例如 Mean Square Error (MSE) Loss）也能達至相同效果。

---

Threshold 的定義方法
這次因為懶惰，我只用肉眼判斷 Threshold 的值。這個 Threshold 是指：只要任何數據的 total loss 比它小，就應把它當成正常數據。事實上，隨著訓練次數越多，系統會對正常數據的規律更熟悉，輸出會更接近完美，所以它的 total loss 必定會越來越小。故此，訓練越多，Threshold 其實也應該變得越小，以達至更準確的辨識率。

 ---

小結
運用 LSTM Autoencoder 做異常偵測，能達至頗高的成功率，而且原理也不難懂。
不過，由於變數不少，LSTM 訓練時間也頗長， 所以部署時，應先考慮其他方法。

總而言之，這次的實驗也算成功，至少加上 batch support 後，仍能達至預期結果。

---

參考：

[1] Time Series Anomaly Detection using LSTM Autoencoders with PyTorch in Python - https://curiousily.com/posts/time-series-anomaly-detection-using-lstm-autoencoder-with-pytorch-in-python/

[2] 【深度學習】一個簡單又神奇的結構：自編碼機 AutoEncoder - https://jason-chen-1992.weebly.com/home/-autoencoder

 

實作：簡易版 BERT Transformers Multi-Label Classification

簡介
由 Huggingface 所開發的 Transformers Library，雖然可以用 BERT 做 NLP Multi-Class Classification（每一組數據擁有一個 class），但卻未有支援 Multi-Label Classification（每一組數據，可以有多於一個 class）。這次實作，我會以 Kaggle Jigsaw Toxic Comments 作為例子，透過小改 Transformers 的 Multi-Class Classification 範例，令它可以進行 Multi-Label 分類。

---

改進原理
Transformers 中的 BertForSequenceClassification，是一個基於 BERT 及 Attention Model，然後再使用 CrossEntropyLoss 微調訓練的模型。事實上，它也支援自動訓練：只要你使用期間提供了 label，它內置的 CrossEntropyLoss 就能自動計算並返回 loss 值。

這種「黑箱全包」的做法，雖然令入門開發者，可以在不了解 Loss Function 等概念的情況下上手，但同時，它也帶來了一些限制：由於它使用了 CrossEntropyLoss，它就只能支援一個類別的分類。舉例來講，它只能計算出「 預計矩陣 [0 0 0 1] 與期望值 3（也就是 [0 0 0 1] ）的距離為 0 」。它並不能輸入多於一個維度的期望值。

所以，這次實作，我只是簡單地改了一下：不用內置於 BertForSequenceClassification 的 CrossEntropyLoss，改為採用 BCEWithLogitsLoss。由於 BCEWithLogitsLoss 本身就是專為 Multi-Label Classification 而設計的 Loss Function，所以我也懶得仔細查究，直接就拿來用。最後，我們就能把 BertForSequenceClassification 改成支援 Multi-Label Classification 的模型。

至於其他，例如 BertTokenizer 等等，則採用 Pretrained 結果，原封不動。

---

重點代碼
這幾行代碼，就是這次改動的大重點：

在訓練過程中：

# use AdamW
optimizer = optim.AdamW(model.parameters(), lr=lr)

# generate prediction
optimizer.zero_grad()
outputs = model(input_ids, attention_mask=attention_mask)
 
# compute gradients and update weights
loss = nn.BCEWithLogitsLoss(outputs.logits, labels)
loss.backward()
optimizer.step()

解說：

• 使用 AdamW 做 Optimizer（其實其他都可以，只是我發現 AdamW 比較快）。
  
• 使用 BertForSequenceClassification model 的過程中，故意不提供 label，
  這樣，Transformers 就不會偷偷地自己計算 Loss 和 Gradients，必須要自己動手。
• 使用 BCEWithLogitsLoss 來計算 Loss，然後手動做 Backward Propagation 和 Stepping。

 在驗證測試過程中：

# generate prediction
outputs = model(input_ids, attention_mask=attention_mask)
prob = outputs.logits.sigmoid()

# record processed data count
total += (labels.size(0)*labels.size(1))

解說：

• 用 model 計算結果後，必須經過一層 sigmoid 計算。
  因為 BCEWithLogitsLoss 入面都有 sigmoid，這樣才會一致。
• 在計算總準繩率時，不能單一以 labels.size(0)（樣本數）做分母，
  相反，要以總標記數 (樣本數 * 每個樣本內的標記數) 做分母。
  因為：假設 Predict = [ 1 0 0 1 ]， Expected = [ 1 0 0 0 ]，
  它應該算做 3/4 正確，而非一個錯誤。

---

演示代碼
https://github.com/cmcvista/BERTClassifier/blob/main/BertMultiLabelClassifier.ipynb

---

小記
感謝 Joseph 提示方向。

---

參考

[1] - https://huggingface.co/transformers/training.html

[2] - https://towardsdatascience.com/transformers-for-multilabel-classification-71a1a0daf5e1

[3] - https://medium.com/huggingface/multi-label-text-classification-using-bert-the-mighty-transformer-69714fa3fb3d

實作：利用 PyTorch LSTM 估計未來氣温

簡介
Long Short Term Memory (LSTM) 是一種對時序有記憶的神經網絡。簡單來講，你可以幻想它是一種有短暫及長期記憶的細胞。只要你不斷按順序地訓練它，日子有功，它就會記住事物的先後次序（例如：你每次都用 A-B-C 的順序去訓練它，以後它只要見到 A，就會想起下一個是 B）。

這種神經網絡，對自然語言處理 (Natural Language Processing) 特別有用：因為它能記住句子的先後順序，繼而找出代名詞原本的意思。 例如「小明去了踩單車，他覺得很開心」這一句中，使用 LSTM，系統就能運用短暫記憶，找出「他」所指的主語，是句子開頭的「小明」。

除了 NLP 之外，LSTM 還特別適合用來預測有規律的時序資料 (time-series data)。例如假設每年天氣都是有四季，而且每年氣温都差不多的話，LSTM 就能找出這個潛在的規律，從而推算出將來某月的氣温大約會是多少。還有，通訊系統的訊號、看似沒有規律的雜訊等等，也非常適合用 LSTM 來找出它的潛在規律。

是次實驗，我會使用新加坡的氣温歷史數據，訓練 LSTM，試試到底它能否有效預測將來的温度。不過，由於新加坡沒有四季，而且氣温有可能隨雨量及雲量影響，所以準繩度理應不會太高。但怎樣也好，姑且一試無妨。  

---

幾個重要的變數
是次實驗，我用了這些變數：

• 原資料的長度為 466 個數據。
• 我把資料切割成 448 份 [x1 x2 x3 ... x16 x17 x18]，然後把期望目標設為 [x19]
  換句話說，我把頭 18 個月的數據進 LSTM，然後期望它會估計到第 19 個月的氣温，
  而這件事會重覆 448 次。
  
•  我把 70% 的資料用作訓練，30% 用作驗證。
• 我使用了 SciKit 的 MinMaxScaler，將所有輸入輸出數據，都以 fit_transform 正規化，
  之後，估算完成後，我再用 inverse_transform 還原。
  

關於 LSTM 的變數，我設定成：

• 資料維度 (input_size / features / input_dimension) 為 1，因為氣温是一維的資料。
• 次序長度 (sequence_len) 為 18，因為我順序放 18 個月的氣温資料。
• 隱藏層大小 (hidden_size) 為 500，因為我估計會有 500 個特徵值得留意。
• 層數 (num_layers) 為 3，所以會同時有三個短暫記憶的空間。
• 我設定了 batch_first=True，所以資料結構是 (batch, sequence, features)，
  也就正乎合 for loop DataLoader 時返回來的資料結構，省回轉來轉去的代碼。
  （RNN 全部都有這種選項，因為它的訓練模式與其他相異，
  x1 和 x2 是放進同一個 cell，而非像 linear regression 那種，是放進兩個不同 cells。）
  

關於訓練的變數：

• 訓練包大小 (batch size) 為 20， 因為本人的電腦記憶體較少 ，不適宜大包大包訓練。 
• 我運行了 500 個 epoch，因為我發現次數再多， loss 也沒再變少。
• 我使用了 Mean Square Error (MSE) 來做 loss function，兩個氣温相差再平方，很直覺。
  

---

演示代碼

https://github.com/cmcvista/MLHelloWorld/blob/main/LSTMPyTorch/LSTMTemperaturePrediction.ipynb

---

預測結果

紅色為預測結果，藍色為實際結果。

由此可見，單純使用 LSTM 並不太準確。
我估計原因是因為，一來新加坡的氣温變化不大，所以難以準確預測，
二來就是訓練次數不足（或者 optimization strategy 太保守），以至它仍未學足 pattern。

但另一方面，雖然方向估錯，但預測結果的形狀，的確有點像實際數據的形狀。
所以，這也算是一個「有意義的發現」。

---

小結
LSTM 與其他傳統的神經網絡不同，它以 RNN 的形式運作，以致可以認出時間次序。
雖然初步來看，用作預測氣温並不可靠，但用來找出數據的規律，看來也還可以。

---

參考：

[1] - https://stackabuse.com/time-series-prediction-using-lstm-with-pytorch-in-python

 

常見的 ML Loss Function: MSE, Hinge 及 Cross Entropy

簡介
在 ML 的領域中，Loss Function 是一種量化「機器預測值 (predicted value)」和「實際期望值 (desired value)」之間差距的一種工具。簡單來講，如果機器預測的結果與實際期望一致，這個模型就「沒有任何資料損失」，也就是說，Loss Function 的輸出會等於 0。相反，如果兩者不一致，損失就應該越大，故此數值輸出應該越高。

以上概念雖然簡單， 但實際上， 不同的 Projects 中均會採用不同的 Loss Function，以便有效反映資料損失的程度。所以，在實際應用中，往往令人覺得很困惑：到底什麼情景，才能用這個 Loss Function 呢？本文會介紹三種十分常見的 Loss Function，並輔以「正常人能理解的文字」，幫助大家更容易明白，以及作出正確選擇。

---

Mean-Squared Error (MSE) 均方差
MSE 是最通用，最易理解的 Loss Function，它的目標是找出兩點的距離。
這種算法不限定期望值的範圍，基本上任何輸出（例如 [-1, 1], [0, 1], [0, inf) 等）都可以用。

首先，我們需用最簡單的方法，計算出兩點距離，也就是 x2 - x1。
不過，它會產生以下問題：

假設 x1 = -4，x2 = 3：

• 使用 x2 - x1 的公式，我們得出距離為 3-(-4) = 7
  

但當 x1 = 4，x2 = -3 的情況：

• 使用 x2 - x1 的公式，我們將得出距離為 -3-4 = -7

因為 Loss Function 的定義是「數值越細，損失越少」，這個情況下，明明兩個例子的實際距離均是 7，我們卻得到不一樣的結果。為了防止這種情況，最簡單的方法，就是把結果平方，變成以下公式：

• 使用 (x2 - x1) ^2，兩個例子均能得到 (7)^2 = (-7)^2 = 49

這樣就能解決正負問題，而且也能做到「距離越大，損失越多」的感覺。
（例如 2^2 = 4，但 7^2 = 49，原本只差 7-2=5，卻做到了 49/4=12 倍的差別）

附上公式代碼：

def MSE(yHat, y):
    return np.sum((yHat - y)**2) / y.size 

---

Hinge Loss 鉸鏈損失
這種 Loss Function 只適用於期望值是 -1 或 +1 的情況。例如，在 SVM 二元分類器 (binary classifier) 的情況中，只要分類正確，損失值就應該是 0。相反，若果分類錯誤，Loss Function 就應該要懂得表達有多少差距。

這種特性，可以用 Loss = max(0, 1 - desired value * predicted value) 表示。

例如當 predicted value = +1，desired value = +1 （分到同類）時：

• Loss = max(0, 1 - 1*1) = max(0, 0) = 0

當 predicted value = +0.8，desired value = +1 （分到同類，但不夠肯定）時：

• Loss = max(0, 1-0.8) = max(0, 0.2) = 0.2

當 predicted value = -0.8，desired value = +1 （分錯類）時：

•  Loss  = max(0, 1-(-0.8)) = max(0, 1.8) = 1.8

這樣，Loss Function 就能有效表示分錯類，或者分得不夠開的情況。

附上公式代碼：

def Hinge(yHat, y):
    return np.max(0, 1 - yHat * y)

---

Cross Entropy Loss 交叉熵損失
這種 Loss Function 特別適合期望值在 [0, 1] 連續數據範圍的情況，例如概率等等。它與 MSE 有一個相似之處：當預測值與期望值的差距越大，得到的懲罰就會指數性上升。例如當期望值 = 1， 我們可以用下列圖表及公式表示 Cross Entropy：

公式：Loss = - p(x) * log (q(x))，
若 desired value = 1，則 p(x) = 1，q(x) = predicted value；
若 desired value = 0，則 p(x) = 1，q(x) = 1-predicted value。

當 desired value = 1 及 predicted value = 1 時：

• Loss = -1*log(1) = 0

當 desired value = 0 及 predicted value = 0.99 時：

• Loss = -1*log(1-0.99) = -1*log(0.01) = -2

由此可見，當預測值與期望值越背道而馳，損失就越高。

附上公式代碼：

def CrossEntropy(yHat, y):
    if y == 1:
      return -log(yHat)
    else:
      return -log(1 - yHat)

---

參考：

[1] - https://ml-cheatsheet.readthedocs.io/en/latest/loss_functions.html

[2] - https://blog.csdn.net/hustqb/article/details/78347713

Principal Component Analysis (PCA) 初探

簡介
很多時候，當我們得到一大堆數據，要進行數據分析的時候，我們都會先篩選一些比較重要的變數，然後才把它們放進 Machine Learning 的算法當中，以節省電腦的運算時間。不過，當篩選出來的數據仍然很多，有時候就令人頭痛。到底有沒有方法，可以用一個變數去取代數個相似的變數呢？（例如「氣温」和「季節」很相近，可否結合成一個變數，例如「天氣」來代表呢？）

另一種情況，就是當我們得到一大堆數據，希望用 ML 做分辨系統，我們也會問：到底這個 project 的可行性有多高？數據之間是否存在著一些，可用 2D 或 3D 的圖表展示的規律？

面對這兩種情況，降維 (Dimensionality Reduction) 就能幫助我們達到以上的目的 。這裏的「維度 (Dimension / Dimensionality)」是指變數（例如氣温、季節等）。而降低維度，正正就是指把 N 個變數，變成 K 個變數（當中 N >= K）。是次會以 PCA 算法作為例子，簡介一下到底大致原理是什麼，以及有什麼應用。

Principal Component Analysis (PCA) 的目的
顧名思義，這個算法的目的，就是要找出一大堆數據中最有代表性的 Vector（或者叫 Principal Component）。舉例來說，以下的 2D 例子中有五點，當中最有代表性的 vector 就是 (1/sqrt(2), 1/sqrt(2))，也就是藍色的箭頭：

算法的目的，就是從 2D 平面中，找出那條藍色箭頭，然後，以上五點大約的位置 ，就能以投影的方式，在 1D 的線上表示。正如下圖左下方的例子，原本 x(1) 需要以 2D (x2, x1) 的方法表示，但當找到藍色 vector 之後，就能以 1D，也就是 x(1) = m*(z1) 的方法表示（當中 m 代表長度）：

如此類推的話，即使原本變數有非常多個（例如 1600 個），只要使用 PCA 不斷投射，我們就可以將變數縮成數個（例如 2 個），然後用圖表去表示數據分布，如下圖所示，PCA 能找出一大堆國家，在 2D 平面下的分布情況：

PCA 的算法
既然 PCA 這麼實用，我們當然想了解它的原理與算法。不過由於它涉及到找出 eigenvectors 等等一大堆 linear algebra 的概念，以及一大堆數學證明，以下部分，只提到基本概念和步驟。詳細證明方法可以參考 CSDN 的文章。

基本概念：

PCA 的目的，在於找出所有投影平面／線中，可以產生最小總距離的兩支 vectors（正負）。
如下圖所示，世界中有超多的 vector，但我只想要 y=x 的那一支：

基本步驟（取自 Coursera）：

1. 計算 covariance matrix，sigma = (1/m)*(x(i))*(x(i))^T
   
2. 用 SVD 計算 eigenvector of matrix sigma，得出 [U, S, V]
   
3. 抽取 U matrix 中的首 K 行，成為 U_reduced
4. 得出 Z = U_reduced^T * x(i)

PCA 程式演示
由於 Python 中的 scikit 一早已經寫好了 PCA 的算法，我們可以直接使用，參見以下例子：
https://github.com/cmcvista/MLHelloWorld/blob/main/PCADimensionalityReduction.ipynb

---

參考：

[1] - Andrew Ng - Machine Learning Course in Coursera - https://www.coursera.org/learn/machine-learning/lecture/ZYIPa/principal-component-analysis-algorithm

[2] - https://zhuanlan.zhihu.com/p/37777074

[3] - https://medium.com/ai%E5%8F%8D%E6%96%97%E5%9F%8E/preprocessing-data-%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90-pca-%E5%8E%9F%E7%90%86%E8%A9%B3%E8%A7%A3-afe1fd044d4f

 

kNN，DBSCAN 及 LOF 初探

簡介
機器學習其中一個最實用的功能，就是分門別類 (Classification / Clustering)。用家只需將數據放入模型當中，算法就能告訴你該數據所屬的類型、或者是所屬的群組。這種算法十分受歡迎，因為它除了可以用來分類垃圾郵件、了解用戶類型、更能幫助找出一堆亂數中的潛在規律。

分類算法，大致上來講，包含了以下兩大類：

• Supervised Clustering: 訓練數據中不但包含數據本身，也包含了數據的標註 (Labels)。這種算法的目標，是找出輸入數據與標註之間的關係，從而判斷未來數據的標註。 例子包括運用 CNN 作 MNIST 數字辯認等等。
  
• Unsupervised Clustering: 訓練數據中，並不包含標註。這種情況，用家並不清楚數據中的特徵，並希望透過算法，找出其特徵，然後將數據自動分類。 例子包括用 SOM / SVM 找出數據之間的邊界等。
  

由於近年機器學習成為熱潮，分類算法自 2000 年起，幾乎每天都有新的變種。 即使傳統算法，也多得不可細數（SOM, SVM, OCSVM, kNN, DBSCAN, OPTICS, LOF, CBLOF ...）。這篇文章本來只打算講其中一種 Unsupervised Clustering 算法（也就是 LOF），但筆者發現，原來 LOF 與 kNN 及 DBSCAN 又有很大關係。所以今天會簡單筆錄一下這三種常見，關係卻十分密切的算法。

kNN (K Nearest Neighbor) ：「K 個最近鄰居」
顧名思義，這種算法的目的，是找出鄰近 K 點所屬的類別，從而決定自己屬於那一類別。

以下會用這個例子示範：

假設 k=3 的話，並已知 a, b 均為甲組，c, d 為乙組。

如果有一個新點 d = (2, 0)，它的最近 3 個鄰居為 a, c, d。
當中因大多數屬乙組，所以 d 點也屬於乙組。

如果有一個新點 e = (1, 1)，它的最近 3 個鄰居為 a, b, c。
當中因大多數屬甲組，所以 e 點會算作甲組。

Python 應用可參考此頁。

DBSCAN (Density-based spatial clustering of applications with noise)：「聚類分析」
聚類分析屬於 Unsupervised Learning，它並不需要任何 Labels 或類別。
它只需要兩個變數，距離值 (ε epsilon) 和最低點數 (minSample)，就能把數據分類。

以維基百科的圖片作例子：eps = r，minSample = 4:

在這個例子中，假設以 A 點出發，
A 點在它的 r 圓周範圍內找到 4 點（包括自己），所以該四點與 A 為同一類別；
然後該四點會開始以 nested loop 方式，用同一方法再算。

隨機先選 A 點左邊的一點，它的圓周範圍內找到 5 點，所以該五點也屬 A 類；
然後該五點會開始以 nested loop 方式，用同一方法再算。

隨機先選五點中最左一點，該點的圓周內找到 4 點，所以該四點也屬 A 類；
然後該四點會開始以 nested loop 方式，用同一方法再算。

再向左出發，B 點的圓周範圍內只找到 2 點，
所以它屬非核心點 (non-core point)，但仍屬 A 類。

至於 N 點，由於它的 r 圓周範圍內一點也找不到，它就變成另一個類別。

故此，只要每一點都順序運算最少一次，理應就能找到所有點所屬的類別。

Python 應用可參考此頁。

LOF (Local Outlier Factor) 「本地異常值」
LOF 是三種算法之中，最複雜的一種算法。與 DBSCAN 相似的是，它同樣屬於 Unsupervised Learning 的算法。但與 kNN 也相似的是，它在計算過程中，需要輸入 K 個鄰居值。

簡單來講，它混合了 kNN、LRD 等一大堆運算。只要你給出一個新點，經過計算，就會得出一個相對應的 LOF 值。若果它少於或等於 1，該點很大機會屬於模型中的某一類別，反之，該點則很大機會是異類 (outlier / anomaly)。以下圖片來自維基百科，可見當 LOF 越大，它就越不屬於大類別中的成員：

計算方法：

假設新點為 a，首先計算 LRD (Local Reachability Density)：

LRD = k / (sum of reachabilityDistances to from a to all points)

當中 reachabilityDistance(a,b) = max({distanceToKthNearestNeighbor(b), manhattanDistance(a,b)}，而 manhattanDisance 可以轉換成 Euclidean Distance。

最後，計算 LOF (Local Outlier Factor)：

LOF(a) = [(sum of LRD of all points) * (sum of reachabilityDistance of all points)] / k^2

（不必認真理解，當黑盒使用即可。如果想理解，建議看原論文，或博客解釋）

Python 應用可參考此頁。

小結
是次介紹的三個算法，因為比較相關，而且頭兩個比較容易理解，所以在機器學習界的應用也甚廣。不過，這個世界實在有太多 clustering 的算法，而每個算法都有其好壞，所以有時間的話，不妨多試幾個，再決定是否適合自己的應用場景（反正 Python 實例太多，操作上也不難）。

---

參考：

[1] - https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm

[2] - https://en.wikipedia.org/wiki/DBSCAN

[3] - https://medium.com/@doedotdev/local-outlier-factor-example-by-hand-b57cedb10bd1

[4] - https://en.wikipedia.org/wiki/Local_outlier_factor

[5] - https://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf

[6] - https://pyod.readthedocs.io/en/latest/

LSTM 初探

簡介
傳統機器學習只找出每點數據中的規律，並不考慮時間相關性。例如，今天的天氣，其實很大機會會與明天的天氣相關（假設天氣突變並不常見）。又例如，在一句句子當中，若我們得到前面的句子，我們很容易會猜到下一句的內容（例如 Mary is a _，因為看到 Mary，我們能夠很快估計出，空格應該是 Girl 或者 Lady 等名詞）。而 LSTM (Long Short Term Memory)，正正利用了不同的函數，幫助我們找出這些數據的前後之間的關聯性。

LSTM 極簡（忽略數學公式）解說
LSTM 由以下不同部分組成，使它同時擁有「短暫記憶」及「長期記憶」：

• Input Gate：也就是新數據的入口，大約就是正常的記憶入口
• Forget Gate：大約制定忘記多少上一個記憶
• Output Gate：大約制定殘餘去 hidden state 的數據量，並輸出 output state

由此可見，每一粒 LSTM Cell 都會有自己的長期記憶（儲存在 W），而且它也會輸出一些殘餘記憶去 Hidden State，供下一個 cycle 輸入，以至不會完全「忘記」掉。而隨著時間，這些殘餘記憶將會慢慢因為有更多新數據而被「溝淡」。詳細數學公式解釋，可參考此頁。

（有一個動畫演示 LSTM 的網站也十分值得看一下）

實例：股票預測例子
假設今天的股票波幅與將來相若的話，LSTM 就可以用來推算將來的價格。

以下用 TensorFlow 演示：
https://github.com/cmcvista/MLHelloWorld/blob/main/LSTMExample.ipynb

解說：

• 因為我們假定今天的股價會與明天相若，所以，資料排序的時候，採取了這種排法：
  輸入 x1, x11, x21 ... x91，得出 x2, x12, x22 ... x92
• 輸入的數據組為 [x1, x11, x21 ... x91]，[x2, x12, x22 ... x92]，[x3, x13, x23 ... x93] ⋯
  故此，同一 LSTM Cell 將會先輸入 x1，然後下一個 cycle 輸入 x2，
  這樣才能運用 LSTM 表達數據間的關係。
• TensorFlow 輸入數據中，可以做到一個 batch 入面，數據有時間關係。
  假設數據組為 [x1, x2 ... x10]，[x11, x12 ... x20]，你也可以設定 time step 為 10，
  但是次例子中，我們並沒有用到這個功能，所以設置了 time step 為 1。
  這個就是

  train_X_reshaped = np.reshape(train_X, (len(train_X), 1, len(train_X[0])))

  的原因。
  

筆者暫時仍未掌握得很好。但總括而言，用法大致如此。
其實 MATLAB 的做法更加直觀，詳情參見此頁。

參考

[1] - https://www.datacamp.com/community/tutorials/lstm-python-stock-market

[2] - https://www.analyticsvidhya.com/blog/2017/12/fundamentals-of-deep-learning-introduction-to-lstm/

[3] - https://www.tensorflow.org/guide/keras/rnn

[4] - https://www.mathworks.com/help/deeplearning/ug/long-short-term-memory-networks.html

[5] - https://towardsdatascience.com/animated-rnn-lstm-and-gru-ef124d06cf45

Q-Learning 初探

簡介
強化學習 (Reinforcement Learning) 是一種透過嘗試做不同決策，然後根據所獲取的奬勵 (Rewards) 或懲罰 (Punishment)，找出最佳解 (Optimized Solution) 的算法。由於它採用分數奬勵的形式訓練，所以它特別適合玩迷宮、小遊戲、甚至訓練機器人走路這類「未必有絕對答案，只需完成目的」的應用。

強化學習與監督學習 (Supervised Learning) 有所不同的是：監督學習需要集齊不同迷宮的最佳解，然後讓系統在訓練模式中找出 hidden pattern。相反，強化學習並不需要有最佳解的數據庫：系統只需透過選擇性地嘗試，然後採取最低風險（最高回報）的做法，最後就能找出接近最佳解。

以下會利用 Q-Learning 作為例子，講解算式，最後會用一個程式例子演示。

使用「類 Markov Matrix」表示奬勵積分
以下內容，節錄自 A Painless Q-Learning Tutorial [1]。

假設有五間房，我需要設計一個使用 Q-Learning 離開房間的程式的話，我可以假設每一間房為一個 state （state 0 - 4 共五個 state），而「房間外」則為「State 5」 ，所以一共有六個 state：

然後，為了鼓勵人離開房間，每當離開所有房間（也就是去到 State 5），我都會奬勵它 100 分，其餘行動則獲得 0 分：

最後，我們可以用矩陣去表達這個 Markov Decision Chain，當中不存在的事件，我們之後會忽略掉不計。為了整齊，這裏暫時會用 -1 代表：

例子：
如果我在 State 1，想跳去 State 5，將會得到 100 分奬勵。
如果我在 State 2，想跳去 State 3，將會獲得 0 分奬勵。
如果我在 State 4，想跳去 State 1，我們會忽略這個情況，因為並不合法。

簡化版 Q-Learning 算式
定好了 Reward Table，就可以開始 Q-Table 演算。Q-Table 是一個儲存經驗值的矩陣，經過一輪運算，這個 Table 中的數值，將會幫助系統找出最佳解。

以下例子，會用簡化版 (learning rate = 1) 去講解：
（正常版的數式在 Wikipedia 中有提及，但由於比較複雜，所以不在此詳述）

 

運算步驟：

• 首先選一個起點（例子：State 2）和一個終點（離開房間 = State 5）
• 重覆以下步驟，直至到達終點為止：
• 用 Q-Table Equation 更新 Q-Table:
• 任意取下一點 S，獲取奬勵 R，
• 基於 S 點，找出 Q-Table 中最大數值的點（若同樣則任意選一點）
• 將 S 變成現時點，繼續重覆上一步
  

例子（假設 gamma 為 0.8）：

初始值 Q-Table 全為零。

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，但 Q-Table 中去三點 (Q(5,1), Q(5,4), Q(5,5)) 均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 3，然後從 S=(1,2,4) 中任意選一點，S=1，
基於 S=1，可以去 (3,5) 兩點，而 Q-Table 中 Q(1,3)=0, Q(1,5)=100，因選最大，所以選 5。
然後更新 Q Table 值：Q(3,1) = R(3,1) + 0.8*100 = 0+80 = 80
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

選取起點 State 0，然後從 S=(4) 中任意選一點，S=4，
基於 S=4，可以去 (3,5) 兩點，而 Q-Table 中 Q(4,3) 和 Q(4,5) 均為零，
所以任意選 3，並更新 Q Table 值： Q(0,4) = R(0,4) + 0.8*0 = 0，
最後，將 S=4 變成現時點，繼續運算：

選取起點 State 4，然後從 S=(3,5) 中任意選一點，S=3，
基於 S=3，可以去 (1,2,4) 三點，而 Q-Table (Q(3,1), Q(3,2), Q(3,4)) 中，
因 Q(3,1)=80 為最大，所以選 1，並更新 Q-Table 值：Q(4,3) = R(4,3) + 0.8*80 = 64，
最後，將 S=1 變成現時點，繼續運算：

選取起點 State 1，然後從 S=(3,5) 中任意選一點， S=5，
基於 S=5，可以去 (1,4,5) 三點，而 Q-Table (Q(5,1), Q(5,4), Q(5,5)) 中，三點均為零，
所以任意選 5，並更新 Q Table 值：Q(1,5) = R(1,5) + 0.8*0 = 100
最後，將 S=5 變成現時點，但由於現時點＝終點，所以計算結束。

經過以上幾輪計算，得出以下 Q-Table 值：
Q(1,5) = 100 / Q(3,1) = 80 / Q(0,4) = 0 / Q(4,3) = 64

若果經過更多輪計算，不同數值將會繼續更新，
但最後，均會大約在以下結果中，開始收歛 (convergence)：

所以，將它換成 Markov Chain 表示的話，將會變成：

如是者，就可以判斷出以下結果：

• 由 2 出發，去 3 可獲得最高奬勵，
• 到 3 之後，任意選 1 或 4 均可得相同奬勵，
• 假設選 1 之後，去 5 可獲得最高奬勵。
• 故此，由 2 出發，到 5 的次序為 [2,3,1,5]
  

程式演示

https://gist.github.com/cmcvista/d5067fe96f66a72824127f1ea44d2820

（由於比較繁複，日後有需要，會再加以解釋。）

---

參考：

[1] - A Painless Q-Learning Tutorial - http://mnemstudio.org/path-finding-q-learning-tutorial.htm

[2] - https://www.learndatasci.com/tutorials/reinforcement-q-learning-scratch-python-openai-gym/

[3] - https://gist.github.com/kastnerkyle/d127197dcfdd8fb888c2

PyTorch 入門：使用 ResNet9 辨識鳥類品種

前言
機器學習（Machine Learning，下稱 ML）在近年越來越備受關注，因為它透過模仿神經細胞的結構，能在一大堆數據中，找出資料和結果之間的線性 (linear relationship) 和非線性關係 (non-linear relationship)。例如，假設有極大量不同的動物圖片，它能透過這些圖片，找出不同動物的特性（例如顏色、眼晴等），從而「學會」判斷不同動物。

筆者大約在六七年前，仍在大學二年級左右，已經開始見到有人在 Kaggle 中運用 ML 玩簡單的推算遊戲，以及用來訓練股票系統。當年，筆者只接觸過關於 linear regression 和 multi-layer perceptron 這些基本的機器學習概念。但由於 ML 涉及的數學太多、效率也不太高，所以筆者也放棄深究下去。直至 2015 年，DeepMind 運用 deep neural network 學習圍棋玩法，並挑贏了世界冠軍，ML 就開始變成熱門話題。時至今日，ML 發展速度越來越快，幾乎每天都有新的 training model 和 neural network 誕生。

有見及此，筆者為了 catch up 一下科技進步，參加了 Deep Learning with PyTorch 的網上課程。以下的內容，正正就是 course project 的一部分。

簡介
本次實作基於一個鳥類資料庫。資料庫中有 200 種不同鳥類，每種鳥類 5 張彩色圖片，總共 1000 張圖片。目的是建立一個可以認到 200 種鳥類的神經網絡 (Neural Network)。

使用到的技術
卷積神經網絡 Convolutional Neural Network： 這裏是指由原本 224*224*3（224 像素的正方形圖片，三原色 RGB），演變成長闊數值少，但深度變深（512*20*20，512 層，每層 20*20 px）的一種深度神經網絡。背後概念主要是，透過將層數變多，就能使每一層反映的意義更加精準。例如：原本彩色圖片只有 3 層，代表三種顏色。但當變成 64 層，就可以用第一層表示輪廓、第二層表示黑白比例、第三層表示眼晴數目等等。而同時，當像素變少，物件辨識的演算法就能夠更歸納化，不會因為物件向左右移動了些少，就認不到內容。

Residual Connection 殘差連接：這裏是指在 CNN 的結果中，加回輸入值的做法。由於 ML 的重點是降低 loss function 的數值 (loss function's results minimization)，透過加回輸入值，loss function 就更能反映出輸入與輸出的關係（減去了因為輸入值大少的影響）。具體邏輯可以看成品中的解說。

Data Augmentation 數據增強：原本是指將現有的圖片改一下，然後放入 training set 去增加取樣率。但這個 project 中運用的，作用並不是增加取樣率，而是由於數據有限，我們不希望神經網絡記錯一些過於特殊的細節，反而沒有找到同品種鳥類的共通點。例如它可能記了綠色背景，卻沒有記住鳥的形狀（也就是擬合過度 overfitting）。這種過程，也稱作歸納化 (generalization)。

Adam Optimizer：由於 ML 的重點在於 loss function's results minimization，如果只用傳統的 Stochastic Gradient Descent，只看斜率變化，就有機會找不到 global maxima，或者會出現跳動。運用這個 optimizer 就可以預測跳動，從而調節 learning rate。具體來講十分複雜，算是 ML 的專業學術範疇，所以不在此詳述。

CUDA 硬體加速：由於顯示卡計算 matrix 加減乘法比普通的處理器快 (general purpose CPU)，所以本次使用了 NVIDIA 的加速功能去計算 tensors 的斜率變化。

成品
筆者由於不太熟習 PyTorch，故此只基於 Lecture 5 作出以下小改：

• 將資料改成鳥類
• 將 training set, validation set 和 testing set 分開
• 取消了 data normalization（因考慮到鳥類的顏色比例很重要，而且很麻煩）
• 加減了一些不必要的 code blocks 和 comments

結果如下：


準確率
由完全隨機開始訓練，結果能去到大約 87% 準確率，有點意想不到呢。
如果有時間的話，筆者會再 post 一下使用 pre-trained model 的結果，我相信應該更好。

參考
https://jovian.ml/forum/t/lecture-5-data-augmentation-regularization-and-resnets/1546