[學習筆記] 機器學習: 系統設計 (Machine Learning: System Design)

如果要運用 supervised learning 設計 e-mail spam classifier, 用來判斷一封 e-mail 是否是垃圾信, 應該怎麼做呢?

首先, 我們決定哪些 key words 可用來判斷是否是垃圾信, 並且把 e-mail 轉換成 vectors of words.

假設我們選擇了 training set 裡最常出現的 10000 個單字作為 key words, 如此我們有 10000 個 features (n = 10000).

接下來, 我們定義 input (x) 及 output (y).

input (x): features of e-mail.
如果 e-mail 裡的單字 match key words j, assign \(x_j = 1\), 否則 \(x_j = 0\).
output (y): spam (y=1) or not spam (y=0).

如此我們就可以開始 train 演算法的 parameters.

但在提高演算法的準確度的過程中, 我們應該把時間投注在哪個方向呢?

1. 蒐集大量 training data
例如 honeypot project 故意產生很多假的 e-mail address 藉此蒐集許多垃圾信.

但蒐集大量 training data 不一定有幫助.
2. 建構精巧細緻的 features.
例如把 e-mail header 裡關於 routing 的資訊納入 feature set.
3. 開發演算法以不同的方式處理 inputs.
例如辨認 e-mail 中拼錯的字.
我們難以事先預料應該把時間投注在哪個方向, 只有透過系統性的方法從完整的面向進行測試及分析才能夠判斷.

藉由 brainstorm 出各種做法, 增加選項之後, 不要憑著 gut feeling 貿然投入大量的時間在其中一個方向, 否則會白費力氣而徒勞無功.

分析預測誤差 (error analysis)


建構 machine learning model 建議的步驟:

1. 以簡單的演算法作為起點, 快速實作完成, 初期就以 cross validation data 測試演算法的準確度.

2. 繪製 learning curve, 用來判斷提升準確度的方向在於取得更多的 training data 或是納入更多的 features.

3. 檢視演算法對於 cross validation set 裡的 data 的預測誤差, 觀察大部分的誤差的原因是否有某種 trend, 據此設法降低誤差以提升準確度.
舉例來說, 對於 e-mail spam classifier, 如果 cross validation set 裡有 500 封 e-mails, 其中 100 封 e-mail 分類錯誤.

我們觀察分類錯誤的那 100 封是哪一類的垃圾信, 舉例來說, 60% 是和 steal password 有關的垃圾信. 因此我們先設法提高判斷和 steal password 有關的垃圾信的準確度.

我們進一步觀察哪些 features 和 steal password 有關, 舉例來說, 60% 的 steal password 都和 unusual e-mail routing 有關連性, 因此我們把 unusual e-mail routing 這個 feature 納入演算法 model 之內來提升準確度.

數值評估 (numerical evaluation) 的重要性


以 e-mail spam classifier 為例, 應該把 discount/discounts/discounted/discounting 視為相同的字或是不同的字?

需要選定觀察指標 (error metrics), 並透過數值評估, 而不是依據 gut feeling 來做判斷.

舉例來說, 如果透過 Porter Stemming Algorithm 把 discount/discounts/discounted/discounting 視為相同的字, 可以讓 error rate 從 5% 降到 3%, 便可以判斷這樣的作法是有效的. 如果由不區分大小寫改為區分大小寫, error rate 從 3% 提高到 3.2%, 便可以判斷這樣的作法不該採用.

衡量 skewed classes 的指標 (Error metrics for skewed classes) - precision/recall


對於 skewed classes, 在選定 error metrics 要特別留意.

以 cancer classification 為例, 我們有病人的 features, 我們想判斷他們是否有 cancer.

我們 train logistic regression model \(h_{\theta}(x)\).
\(y = 1 \text{ if cancer}\\
y = 0 \text{ otherwise}\)
我們發現對於 test set 有 1% 的誤判 (99% 的病例診斷正確).

準確率似乎很不錯.

但我們同時知道, 只有 0.5% 的病人有 cancer.

考慮到這一點, 1% 的誤判率, 事實上準確度是很差的, 因為即使 always 預測病人沒有得癌症 (y=0), 都只有 0.5% 的誤判率.

這種某一類別的比例特別低的情況, 稱之為 skewed classes.

因此我們知道, 對於 skewed classes, 若僅以 error rate 來衡量, 是會造成誤判的.

一種合適的衡量方式稱為 precision/recall.





\( \text{Accuracy} = \frac{\text{# of true positives + # of true negatives}}{\text{# of total examples}} \)

\( \text{Precision} = \frac{\text{# of true positives}}{\text{# of predicted positives}} = \frac{\text{# of true positives}}{\text{# of true positives + # of false positives}} \)
舉例來說, precision 是衡量在所有預測為有癌症的人之中, 多少比例的人真的有癌症.

Precision 越高越好.
\( \text{Recall} = \frac{\text{# of true positives}}{\text{# of actual positives}} = \frac{\text{# of true positives}}{\text{# of true positives + # of false negatives}} \)
舉例來說, recall 是衡量在所有真的有癌症的人之中, 多少比例的人被預測為有癌症.

Recall 也是越高越好.
By convention, positive 通常設定為 \(y = 1\), 且設定為發生機率較低的情況.

同時看 precision 及 recall, 能夠避免 classifier 以簡單的方式來預測, 但實際上有很大的誤差. 舉例如果 always predict \(y=0\), recall 會是 0.

如果一個演算法同時有高 precision 及高 high, 我們有信心這個演算法準確度是高的.

Precision 和 recall 之間的取捨


Logistic regression: \( 0 \leq h_{\theta}(x) \leq 1 \)

Predict \(y=1\) if \( h_{\theta}(x) \geq 0.5 \)

Predict \(y=0\) if \( h_{\theta}(x) \lt 0.5 \)

假設我們希望只有在很有信心的情況下預測 \(y=1\), 我們把 threshold 調高:
舉例來說, 病人沒有癌症卻判斷他有癌症, 病人會遭受很大的打擊, 且需要進行療程, 對病人影響重大, 因此希望只有在很有信心的情況下, 才判斷為癌症.

Predict \(y=1\) if \( h_{\theta}(x) \geq 0.7 \)

Predict \(y=0\) if \( h_{\theta}(x) \lt 0.7 \)

原本有 50% 的把握, 我們就會判斷病人有癌症, 調整 threshold 後, 有 70% 的把握, 我們才會判斷病人有癌症.

在這樣的情況下, 演算法會有較高的 precision, 但會有較低的 recall. 下圖是一個可能的例子.


假設我們希望有些可能性就預測 \(y=1\), 我們把 threshold 調低:
舉例來說, 病人有癌症但卻沒有預測到, 這會讓病人延誤治療時機.

Predict \(y=1\) if \( h_{\theta}(x) \geq 0.3 \)

Predict \(y=0\) if \( h_{\theta}(x) \lt 0.3 \)

原本有 50% 的把握, 我們就會判斷病人有癌症, 調整 threshold 後, 有 30% 的把握, 我們就會判斷病人有癌症.

在這樣的情況下, 演算法會有較高的 recall, 但會有較低的 precision. 下圖是一個可能的例子.


根據上述例子進行歸納, 我們把 threshold 視為一個變數, 對於同一個演算法, 隨著不同的 threshold, precision 和 recall 的變化如下圖所示.

Predict \(y=1\) if \( h_{\theta}(x) \geq \text{threshold} \)



要如何找出最佳的 threshold 呢? 或者不同的演算法, 有不同的 Precision (P) 及 Recall (R), 要如何比較呢?

採用 \( \text{Average} = \frac{P + R}{2} \) 並不恰當.
舉例來說, 如果

Algorithm 1: P = 0.4, R = 0.5 → Average = 0.45

Algorithm 2: P = 0.01, R = 1.0 (例如 always predict y = 1) → Average = 0.505

以 Average 來判斷, 會誤以為 Algorithm 2 比較好.
可以採用 \(F_1\) Score (F score) 來進行比較.

\( F_1 \text{Score} = 2 \frac{P * R}{P + R} \)
如果 P ~= 0 或 R ~= 0, F score ~= 0

如果 P ~= 1 或 R ~= 1, F score ~= 1

Training data 數量的考量


有時候, 演算法的準確度會隨著 training data 的數量而大幅提升.



上圖是 4 種不同的演算法, 用來進行 confusable words 的分類, 有些演算法在 training data 少的時候準確度輸給其他演算法, 但在 training data 量大時, 卻勝過其他演算法.

因此 machine learning 界流傳一句話: "It's not who has the best algorithm that wins. It's who has the most data."

但取得大量的 training data 並不總是有幫助, 如果沒有先釐清是否真的有幫助, 就著手設法取得大量的 training data, 會白費力氣而徒勞無功. 在什麼情況下, 取得大量的 training data 真的有幫助呢?

在下列情況下, 取得大量的 training data 對於提升演算法的準確度可能是有幫助的:

1. Features \(x \in \mathbb{R}^{n+1} \) 有足夠的資訊來準確地預測 y.
舉例來說, 判斷 confusable words 時, 如果把前後文的單字作為 feature set, 預期是有足夠的資訊來準確地預測 y.

相反地, 預測房價時, 如果只以房屋坪數作為 feature, 沒有其他的 feature (如地點, 屋齡, 房間數...), 預期沒有足夠的資訊來準確地預測 y.

測試是否符合這個情況的方法: 給定 input x, 看專家 (人類) 是否能夠預測 y?
2. 採用具有許多 parameters 的 learning algorithm.
具有許多 parameters (e.g. logistic regression/linear regression with many features; neural network with many hidden units) 有助於降低演算法的 bias.

大量的 training data 有助於降低演算法的 variance.

因此具有許多 parameters 的演算法搭配大量的 training data, 可以同時降低演算法的 bias 及 variance.

延伸閱讀


[Coursera] Machine Learning: Machine Learning System Design, by Andrew Ng, Stanford University