今天要講Hyperparameters Tuning，也就是俗稱的「調參！」。
一般而言Hyperparamters指的是那些我們在模型開始訓練之前就設定的數值，通常跟Model長相、training過程有關，像是ML裡Random Forest我們常調的就是n_estimators，這會決定我們的RF裡面要有幾棵tree，而同時我們也會調max_depth，這會限制每一顆Tree的最大深度，這邊順便提一下，sklearn目前的tree based pruning都只支援pre pruning，也就是說在tree被建出來之前去限制它的長相，而沒有post pruning。在DL裡面包含batch size、epoch、learning rate都是我們非常常調的數據。
調參數不論是在ML時代還是在DL時代都是非常重要的事情，大部分的baseline建出來後只要認真調參數都還可以再improve 1~2%的accuracy。
調參數之所以重要，最主要是不同的參數通常會影響我們model的capacity，像是在Ridge Regression裡面如果我們把L2 regularization開很強，那我們model相對就不好fit training data，也就是model capacity變低了，反之如果我們把L2 regularization開很小，那我們model就可以隨意亂長，更容易fit training data，但是相對而言也就可能更容易overfitting。
因此一般我們的邏輯是「underfitting時增大model capacity，overfitting時減低model capacity」，而調參數就是一個可以做到這件事的方法。
除此之外像是SVM的kernel，tune了會讓你的model畫出不同形狀的decision boundary，如果我們的data需要non linear classification的話可能使用rbf就會比較好，所以hyperparameter setting也會影響我們model是否適合針對這個data學習。
常見調參數方法
- Manual Hyperparameters Tuning：簡而言之就是手調，手調基本上就是吃一個data scientist對數據的敏感度以及模型的熟悉度，像是Deep Learning裡面我們train一個CNN可能就要2 3小時，這種時候如果你對train CNN極熟悉，可能看一兩次accuracy或做初步的error analysis就可以非常容易的設計出更好的Architecture或是Hyperparaters，像是我們實驗室（孫民老師實驗室）的學長姐很多對如何Tune CV model都非常熟悉。
- Grid Search Hyperparameter Tuning：這也是教科書、一般ML課程最常提到的方法，簡單來講就是我們把各個hyperparameter的可能都設好，然後grid search會自動幫我們把所有可能的組合都試一遍。Ex: 如果今天我們同時要調n_estimators = {100, 200, 300}跟max_depth = {5, 8}，那Grid Search就會自動幫我們把(n_estimators, max_depth)分別等於(100, 5), (100, 8), (200, 5), (200, 8), (300, 5), (300, 8)，這6種組合全部都跑一次實驗，然後挑最好的。
- Random Search Hyperparameter Tuning：類似於Grid Search，我們先把每個hyperparater可能的數值或是range設定好，然後Random Search會幫我們隨機去做組合，也就是不同於Grid Search，Random Search不會保證每一種組合都被訓練到，相對的優勢就是我們可以設定最多的實驗數量，藉此來限制我們的訓練資源、時間
- Coarse-to-Fine Hyperparameter Tuning：是一種迭代的方法，我們先粗略的search的整個hyperparameter space，然後當我們發現哪個區塊表現普遍比較好時，我們再針對這個區塊去做深入（如下圖，我們先用藍色的點概略搜尋整個Hyperparameters Space，發現紅色區塊都比較高之後再用紅色的點細緻的搜尋那個區域。）這個迭代的過程可以重複多遍。
上述4種方法都是在實務中常用的方法，其中像是Grid Search往往是最花時間的，而manual search則是最需要經驗，並且自動化程度最低，Coarse-to-Fine其實就是一種半自動的方法，每一輪跌代都做一個比較粗略的Grid Search或是Random Search然後不斷去縮小我們的搜尋範圍，藉此得到好的結果時也能讓自己不要浪費太多時間在爛的區塊，相對而言過去大家最常做的也是Coarse-to-Fine，但是Coarse-to-Fine其實預設了Hyperparameter對Performance的影響是很smooth的，也就是說類似的區塊會有類似的效果，不會左邊一個點效果很差而右邊反而效果很好，這個假設在某些特別sensitive的Hyperparameter會被打破，使用時要時時注意每個Hyperparameter對performance是否影響劇烈且敏感。
除了上述4種傳統上非常常用的方法以外，近3年還有很紅的Bayesian Hyperparameter Tuning，這是一種auto ML的方法，簡單來講就是用Bayesian Model去直接針對accuracy或是loss function optimize我們的Hyperparameters，這個本身比較複雜，之後有機會再開一篇新的來討論。
Which is Better ? Grid Search or Random Search ?
在台灣普遍的課程或是教科書裡面都會大量介紹Grid Search，包含介紹GridSearchCV這個function，大部分甚至會有一個作業在做這個，反而Random Search很少介紹，這邊我想特別來比較一下兩者，哪個比較好，後續我會用GS簡稱Grid Search、RS簡稱Random Search。
在NeurIPS 2018的tutorial中有一個Automatic Machine Learning的Tutorial，由University of Freiburg的Prof Frank Hutter跟Eindhoven University of Technology的Joaquin Vanschoren共同演講，是一個品質非常高的演講，內容放到現在也都還是適用，很推薦大家去看，兩位教授的slide裡面放了下面這張圖。
這張圖顯現了GS的缺陷，假設我們有兩個Hyperparameters需要tuning（圖中寫作parameter，這邊只是名詞定義上的不同），那我們同時做一個3*3的GS跟一個總量為9的RS，兩者在訓練時間上是完全相同的。
假設今天我們其中一個Hyperparameter比較敏感（也就是圖中的Important parameter），另一個則很不敏感（也就是圖中的Unimportant parameter），那這種時候GS因為搜索的方法過於規矩，在不敏感的Hyperparameter上也會重複搜尋3種可能，這種時候其實搜尋9個點就幾乎等效於搜索3個點而已，因為在不敏感的Hyperparameter這個維度上你怎麼搜效果都差不多。然而RS因為它是隨機在一個range內去挑選9個點，所以不論在敏感還不敏感的維度上都有9個不同的值，因此今天即便有不敏感的Hyperparameter，RS搜尋9個點在敏感的維度上還是具有9個點的效果，因此更容易找到最佳組合。
簡單來說就是：Grid Search浪費時間在搜索不重要的Hyperparameter。而Random Search不會。
所以實際上我自己幾乎沒有在用Grid Search，雖然Random Search也只有在每個model、feature set的初期探索期會大量用，但是依舊比Grid Search好用很多。
Multi-Fidelity Search
前面談那麼久，就是希望幫助建立一個完整的Hyperparameters tuning的觀念，大家現在應該了解，以Hyperparameters tuning而言我們最在意的除了最終結果以外還有「效率」。
實際上如果我們不在意效率，那Grid Search的缺陷就不見了，因為我們有無限的時間可以搜索。
而大家會了不斷得提高效率，推出了我個人非常非常非常常用的技巧稱為Multi-Fidelity Search。
Multi-Fidelity Search的核心假設就是「用不同量的data、feature來做Hyperparameter會有類似的效果。」，通常我們會搭配Coarse-to-fine或Grid Search、Random Search使用，因此我們可以在Tuning早期用比較少的data、feature來做Hyperparameter tuning，找到還不錯的區塊（或是比較好的幾種組合）後，用比較多的data、feature去深入、更細節的搜索這個區塊，再不斷迭代下去。（如下圖）
上面的圖是用SVM train在MNIST上，由左至右使用越來越多data來train，顏色越藍代表performance越好，從圖上我們可以看到用不同量的MNIST data search出來的結果其實都有一致性，在最一開始使用最少data時比較好的區塊（青色），在使用比較多的資料時也是得到最好的結果（深藍色）。
類似的結果也可以很容易被reproduce出來
而這裡還有一個類似的變種，是用不同n_estimators的Random Forest也都是類似的結果（如下圖）
Multi-Fidelity Search讓我們在搜尋的時候可以依據我們的需求減少training時間，並仍然得到robust的結果，因此當我們在Kaggle或實務上面對大量data時就會使用這個trick。
這裡有一個小細節，就是如果要選partial data來做search，那我一般還是會check這個partial data跟我們test data的distribution shift，或是這個partial data是我用心clean、impute過的data，保證這些data的有效性，這樣search出來的Hyperparameters才會有用，很多比賽上只要做好data cleaning就可以有一個明顯的performance improvement。
到這裡大家可能會覺得Multi-Fidelity Search搭配Coarse-to-fine跟Random Search就已經非常強了，但是實際上還是有一個問題，就是我們怎麼分配我們的資源在早期跟晚期的運算上，不同階段應該要用多少data、多少運算資源，這就是Successive Halving出手的地方了！（也就是說前面都是前言XD）
Successive Halving 簡介
一言以蔽之，Successive Halving會自動化幫你分配運算資源來做Multi-Fidelity Search。
這邊直接來看sklearn的實驗圖，實驗可以參考sklearn document。
這邊可以看到圖中有多條線，每一條線其實就代表一個Hyperparameter組合，而這邊最起始的時候其實有35個candidates（35種組合），而每個candidates都train在20筆data上，而越往後期candidates越少（被淘汰掉了），同時使用的data也越來越多，這裡圖上面線沒有那麼多是因為這個資料偏簡單，很多線都疊在一起看不到，如果在比較複雜的dataset上就會看到比較不一樣的結果。
簡單來講，Successive Halving就是讓一群學生進行多個輪次的淘汰賽，第一輪每個學生寫5題的小考卷，其中表現最好的一半留下來，第二輪剩下一半的學生每個學生寫10題的考卷，以此類推到最後剩下3~4個學生寫大考卷。而successive halving會自動幫你決定考卷的題數跟學生的數量。
Successive Halving的Pseudo Code
這邊pseudo code比較難讀懂，因為當初是以Multi-armed bandit problem來說明successive halving，不過這邊就把Budget B當成總共運算量、arms就是candidate的數量、loss就是error，所以successive halving做的事情就是：
- 最一開始假設有N個candidates
- 因為我們總共會處理log(N)輪（這裡log底數都是2），所以把總budget B平分給log(N)輪，所以每一輪可以使用B/log(N)的運算資源，而這個運算資源會再被機器換算成你能使用的data量
- 第一輪我們有N個candidates，所以平均下來每個candidates可以使用(B/log(N)) / N，也就是每一輪的總資源平分給每個candidates
- 接下來把所有的candidates training後的performance算出來，把分數在後一半的candidates全部丟掉，也就是表現比較差的沒有進入下一輪的機會。
- 接下來進入第二輪，我們剩下N/2個candidates
- 每個candidates去評分B/log(N)的總資源，所以平均都有(B/log(N)) / (N/2)，所以這邊可以看到第二輪每個candidates都比第一輪多一倍的資源可以使用，這讓每個candidates隨著時間能夠使用越來越多資料。
- 依據performance再把後一半candidates刷掉，剩下N/4個candidates。
- 進入第三輪．．．以此類推直到剩1~2個candidates。
Successive Halving in Sklearn 0.24.1
這次更新sklearn新增了兩個基於successive halving的function，分別是HalvingGridSearchCV、HalvingRandomSearchCV，顧名思義兩個function最大的差異就是底層我們使用的search方法一個是Grid Search另一個則是Random Search。
Function Parameters：
這邊像是estimator、param_grid這種原本GridSearchCV就有的Parameters就不贅述，大家自行參考其他文章，重要的parameters有下面幾個。
- factor：我們剛剛舉的例子中每次是「刪掉一半的candidates」，也就是說我們的factor是2，實際上也可以是3，就是每次只留1/3的candidates，後2/3都丟掉，而sklearn factor default是3。
- resource：這是你想要隨著時間慢慢增加的資源，預設是n_samples，也就是隨著時間data用量會越來越多，但是也可以填入不同的資訊，像是針對random forest我們可以讓他的n_estimator隨著時間越來越多，或是一些iterative的model可以讓n_iteration越來越多。
其他parameters我都建議可以玩玩看，但是相對而言理解的必要還沒有那麼高。
下面是sklearn給的例子，我加上了中文註解大家可以參考。
from sklearn.datasets import load_iris
from sklearn.ensemble import RandomForestClassifier
from sklearn.experimental import enable_halving_search_cv # noqa
from sklearn.model_selection import HalvingGridSearchCV
X, y = load_iris(return_X_y=True)
clf = RandomForestClassifier(random_state=0)
### 設定要搜索的hyperparameter組合有哪ㄒㄧ
param_grid = {"max_depth": [3, None],
"min_samples_split": [5, 10]}### 創建Successive Halving並開始學習
search=HalvingGridSearchCV(clf, param_grid, resource='n_estimators',
max_resources=10,
random_state=0).fit(X, y)### 最終找到的最佳Hyperparameter組合
search.best_params_
除了剛更新的sklearn以外，我以前有用過dabl的RandomSuccessiveHalving，用法基本上跟sklearn這次的設計一樣，兩者都是可以試試看的function。
其他autoML或是進階的Hyperparameters tuning會再寫幾篇來介紹！
如果有任何遺漏或是錯誤或是想要討論的請大家在留言區提醒我。
如果覺得有幫助記得幫我拍手XD
如果喜歡這篇文章可以幫我多拍手幾次XD，或是對於哪個類型文章有興趣都可以在留言區跟我講~ 後續會以中難度的ML/DS/AI知識為主，以及AI/HCI研究相關知識。Reference：
Jamieson, Kevin, and Ameet Talwalkar. “Non-stochastic best arm identification and hyperparameter optimization.” Artificial Intelligence and Statistics. PMLR, 2016.
NeurIPS 2018 Automatic Machine Learning tutorial https://nips.cc/Conferences/2018/Schedule?showEvent=10979
