文章導讀: Why machine learning algorithms are hard to tune and how to fix it
最近朋友傳來一篇 machine learning 的 blog，因為實在寫得太好，但內容橫跨 ML 跟 non-linear programming (主要跟 Lagrange Multiplier 有關)，想說寫一篇導讀，分享學到的東西給大家。
The Basic: Lagrangian Multiplier
雖然唸過一些基本最佳化的人應該對 Lagrangian Multiplier 是很熟悉，但既然是一篇導讀，這邊就分享一下我自己在學 Lagrangian Multiplier 的時候一些小直覺跟思路，但證明一概跳過 (因為我也忘了)。
一般來說，一個最佳化問題大概可以寫成以下形式:
以大一微積分來說，如果沒有 g 的存在，我想要求出最佳 x 應該不是大問題，所以說現在最大的阻礙，就是 g 的存在。那有沒有辦法讓我們不用去管 g ，直接用像一階條件的方式求出 x 呢？這就是 Lagrangian Multiplier 本質上的精神。
有一天數學家們被雷打到之後，忽然想出了這個好用的 function L:
相信我，第一次看到的時候應該都會覺得這是被雷打到才想到的。其中更神奇的是，對這個 L 來說，最佳解的一階條件就是：
看到那令人感動的一階條件了沒! 我這邊沒有仔細講的 slackness、primal-dual gap 等等重要觀念，但第一是我數學很爛，第二是真的講下去等於寫書了，所以可能麻煩自行查資料腦補囉 😛
但到底這個 L 背後的想法是什麼? 為什麼它能幫助我們解出有 g 限制下的最佳 x 是多少呢? 另外對我來說，當面對實際的應用問題時，我是可以寫出相關限制式的數學式是多少，但我老是記不住在 minimize/maximize 的時候，到底那些限制式應該是要 ≥0 還是 ≤0 呢? 一個不小心寫錯，g 就差了個負號。如果你也有一樣的困擾，這邊跟你分享一下我是怎麼記住這些東西的。
前面說到一個根本的想法是能不能這個有限制式的問題變成一個沒有限制式的問題，然後套用。要做到這樣，至少轉換過去的這個 L 的最佳的 x 應該要是轉換前是同一個。這邊，我們考慮以下的 P 函數:
這時我們隨便挑個 x ，那會有兩種狀況 (i) x 是 feasible，也就是說它符合我們的限制式 g；(ii) x 是 infeasible，也就是說它不符合 g。在 (i) 的狀況，因為 g ≤ 0 ，所以要去達到最大值的情況下，lambda 只能是 0；反之，如果 g > 0 ，lambda 就會變成正無線大，也因此 P 的值會是正無限大。換句話說，這個 P(x) 在 feasible 的情況下會等於 f(x)，在 infeasible 的情況下就會變成是正無限大。那如果直接對 P(x) 取最小值，那這時候的 x 會是誰呢? 沒錯，就會是 feasible 的 x 中最小的那個，也就是我們原本最佳化問題的解呢!
所以說，這個 P(x) 巧妙的地方就是，在最小化 f 的問題中，infeasible 的點的函數值會變成無限大，反之在最大化 f 的問題中，infeasible 的點的函數值就要變成負無限大，這樣我們就可以直接透過最佳化 P 去找到我們的解。也就是為什麼在最小化 f 的問題中，g 應該要是 ≤ 0，在最大化 f 的問題中，g 應該要是 ≥ 0 ，都是為了要讓 feasible 的地方 lambda 變成 0，所以我們直接對 P(x) 求解就可以得到我們想要的 x 了。
Regularization: A Non-Linear Programming Perspective
目前大家對 Lagrange 有一點點基本的認識之後，我們回到本篇的主題: 為什麼有時候我們加上各種 regularization loss 並選取我們的 alpha，但無論我們怎麼調整 alpha，訓練出來的模型發生以下狀況:
- alpha 太大，模型直接忽略我們主要的 loss function
- alpha 太小，regularization 發揮不了作用
就是沒有中間的狀況，也就是一個同時考慮了 loss function 跟 regularization 的模型。不失一般性，我們考慮我們的 loss = loss1 + alpha* loss2。原文中給了一個有趣的視覺化結果：
這到底是為什麼呢？原文中考慮了一個有趣的集合，在 (loss1, loss2) 這個平面上，我們所有可以透過 alpha 得到的所有 (loss1, loss2) 的集合，稱之為 Pareto Frontier (上圖中藍色斜影區域，以下簡稱 P)， 是長什麼樣子呢？在理想的狀況中，因為 P 是 convex 的，所以 alpha 得以發揮作用；但反之如果 P 是 concave 的，alpha 就沒辦法發揮作用。如果把 total loss 放在 z 軸，可以看到以下兩種不同的 vector field：
這就是為什麼 alpha 怎麼調都得不到中間的解的理由之一。更不要說在一般的模型訓練中，P 的長相可能是部分 convex 部分 concave ，導致 alpha 能不能發揮效用還跟 initialization 會有關，增加分析的難度。
Regularization: A Non-Linear Programming Perspective
這時候我們當然會想，到底該怎麼解決這樣的問題？要說明這個的話，我們回想一下前面提到的 Lagrangian：
如果從機器學習的角度來看， L 就像是 loss 再加上 regularization g 。或者反過來說，從最佳化理論的角度來說，regularization 就是我們的 constraint。那既然這樣，何不多加個 constraint 讓 regularization 可以發揮效果呢？也就是說我們希望讓 regularization 可以小到一個我們想要的值:
所以說我們的 loss 會變成:
那解上面這個 L 的方法有很多，我擷取幾個我在裡面看到覺得比較有趣的方法: Hard Constraint First Method、Basic Differential Multiplier Method 與 Modified Differential Method of Multipliers
Hard Constraint First Method
這算是一個非常直覺的做法，也就是說，當 l_2 大於 eposilon 的時候，我們優先對 l_2 做 gradient descent 讓它變小，直到它小於 eposilon 的時候我們才繼續優化 l_1。結果會如同下圖：
但是這個方法在優化的過程中，每一步都只考慮 l_1 或 l_2 其中之一個 gradient，而失去了兩者 gradient 之間的 trade-off 關係。因此，原文中有提到一篇 NIPS 1988 的 paper，也就是我下面要介紹的 Basic Differential Multiplier Method (BDMM) 跟 Modified Differential Method of Multipliers (MDMM)，來解決這些問題。
接下來我會按照我自己的想法來介紹我對這兩個方法的看法，考慮到我孱弱的數學能力，可能有些失準的地方，所以有興趣的人最好還是自己看一下 paper 喔。
Basic Differential Multiplier Method
回到之前說的，我們其實是想要解出這樣的 theta：
對應到這樣的 Lagrangian：
跟我們的好朋友 P(theta)：
所以說，我們是對 lambda 方向去增加 L 但對 theta方向是去減少 L，這也就是 BDMM 的基本精神：對 theta 做 gradient descent，對 lambda 做 gradient ascent，寫成微分方程的樣子就是：
這邊其實跟我們在訓練過程中手動調 lambda 有異曲同工之妙：如果 l_2 比 eposilon 大，那麼 constraint 被違反了，也可以看成 regularization 的力道不夠，在這種時候我們往往就是把 lambda 調大，然後再 train；另外對應到上述的微分方程中，代表 lambda 對時間的微分是正的，所以 lambda 會變大。反之，如果 constraint 沒有被違反，那我們會把 lambda 調小，讓優化器去多優化一點主要的 loss ，也就是 lambda 對時間的微分為負。
那 BDMM 在之前看到的 concave Pareto Frontier 上會變成：
OK，看來是有發揮作用了，至少不會往兩端跑，可以停留在 P 上。可以看得出來這些解在 P 上來回震盪，這也是為什麼使用這種最佳化方法配合 early-stop 可以讓我們找到一些我們想要的解的原因之一。至於為什麼會震盪，理由很簡單，就是出現在 lamda 的微分方程式。可以想見， l_2 大於 eposilon 很多時，會把 lamda 變大，那這時 regulariation 的力道會變強，使得 theta 不得不往讓 l_2 變小的地方跑。這時如果忽然 l_2 跑到了比 eposilon 小的地方了，此時 lambda 可能已經在一個很大的值，接者再逐漸變小，這就是震盪發生的主因。那既然這樣，有沒有減少震盪的方法呢？這就是 Modified Differential Method of Multipliers 想解決的問題。
Modified Differential Method of Multipliers
讓我們來直接看看 MDMM 的微分方程：
唯一改變的只有 theta 的部分，但這多出來的一項到底是什麼？又為什麼它可以抑制震盪的現象呢？其實這在原始論文中是一項額外的 penalty 項，也就是說它的 Lagrangian 其實是：
這裡的 c 就會是個自定的常數，原 paper 是稱作 damping，也就是用物理學的角度來分析這些微分方程式，但對我來說比較直觀的還是從最佳化理論的角度來看會比較清楚。套用我們之前說的，這個可以對應到一個最佳化問題就是：
所以說穿了，抑制震盪的方式就是控制 l_2 的變化不能太大，間接地控制了 lambda 的變化，所以就能有效地抑制震盪的問題。
Wow！神奇的數學。當初讀完這些實在太感動了，就想寫這篇 blog 記錄自己的心得與思路，順便證明最近有唸書 XD。那這次就先寫這樣囉，如果我有再想到什麼會在日後補充。