機器學習基石系列(11) — 正規化
這裡的正規化(regularization)講的是針對模型的，是指在一票可以解決同一個問題的模型中找到最佳解。前面在介紹過度配適、非線性轉換時提到使用高次多項式，將資料投射到更高的維度可能可以解決問題，但隨之而來的模型複雜度有可能造成過度配適。因此挑選適合的模型避免過低/過度配適適達到預測目的的必要手段。
從高次多項式走回低次多項式
嚴格限制
以線性回歸為例，將資料x投射到Q維的空間。根據非線性轉換，會得到一個轉換矩陣
為方便，本來轉換之後的權重w要長一條蚯蚓在上面以便和原始權重區隔，但這邊就不讓它長了。一樣，用十次多項式和二次多項式比較：
- 十次多項式為
共11個權重。
2. 二次多項式為
3個權重。
也可以說，二次多項式是十次多項式的限制版。什麼意思？如果十次多項式裡三次項到十次項的係數w都是0，那十次多項式就長得像二次多項式了。所以從高次多項式走回低次多項式，就是在係數加以限制。
原本的十次多項式有11個係數，在這之中尋找最好的組合。如果把它限制成二次多項式，那就是11個係數中限制三次到十次的八個係數必為0，然後在剩下的3個係數中尋找最佳解。
彈性限制
現在把限制放寬一點：還是限制8個係數要為0，但是不限制三次到十次項，而是11項係數中至少8個為0。把它寫成一個看起來很複雜的式子：
翻譯一下就是「統計十次多項式中係數非0的項加總，不得超過3的情況下，追求最小的E_in」。用最多三個係數描述模型，這個hypothesis set給它一個名字叫H’_2，以和原本的限制嚴格的3–10次項係數必為0所組成的hypothesis set，H_2，有所區別。比較一下彈性限制版的任三項係數不為0(H’_2)，和嚴格限制的3–10次項係數必為0(H_2)，還有十次多項式(H_10)，可以得到的關係為
彈性越大，變化越多。我們把H’_2稱作離散假設(sparse hypothesis)，雖然有彈性，但因為可為0的係數不固定，不好算。
換一個方法維持彈性
不再看每一項係數是不是0，而是直接看值。值越小的，平方後也會很小；反之就會很大。依據這個原則列出新的限制：
把係數全部平方加總。C為一定值，可設定。對應的H就變成看係數的平方和，也就是範數(norm)的平方：
利用這個新的H(C)可以把H’_2包含在其中，但不完全相等。C是一個實數，所以H(C)變成一個連續的，從0到無限大(C)的hypothesis set。此外，hypothesis set彼此之間互相包含。最大的H(∞)放開全部係數的限制，也就是H_10。如果把這個H之間的關係用包含的方式列出來，就是
在這個狀況下可以綿密的，細緻的調整想要的限制，而且又能包含前面我們設想的限制狀況，C也可以透過norm的平方調整，是個理想的限制方式。我們把H(C)稱做regularized hypothesis set，在這個限制下找到的最適合投射矩陣就叫w_{REG}。
求最佳化
剛剛提到w的平方和。w*w之前我們就做過了，在線性回歸的時候：
現在只是換成w^Tw而已。想像一個球，球心為圓點，半徑為√C，包含所有的H。目標是其中E_in最低的。
藍色橢圓表示梯度的範圍，就是在羅吉斯回歸裡面提過的。藍色箭頭是梯度的反方向，也就是下降的方向。在沒有正規化之前，我們使用隨機梯度下降，在選擇方向上沒有任何限制；正規化之後梯度下降的方向和範圍被限制在紅色的球裡面。
從圖直觀看，如果要能盡量下降梯度，那w的位置在球的邊緣能下降最大梯度的機率比較高。假如w已經位在邊緣，要如何判斷是不是最佳解了？那就要看看是不是在這個位置還有沒有梯度可以繼續往下。
但首先，w是有方向限制的，因為還是要在球上面，所以紅色箭頭的方向是絕對不能走的。這個方向垂直於w所在點的切面(C是一顆球)，故為w的法向量。球體C是w^Tw，所以法向量就是w向量本身。
相對的，可以走的方向就是法向量的垂直方向。如果有一個梯度的反方向，如藍色箭頭，他可以分解成法向量及切面方向的向量(綠色箭頭)。則如果沿著切面方向繼續走，就可能再下降一些梯度，而保持在紅色球體的限制之內。
所以最佳解出現在什麼時候？就是綠色箭頭消失的時候，找不到在限制範圍內還可以下降的梯度了。此時梯度向量和法向量平行，即
接著要引入一個概念：拉格朗日乘數(Lagrange multiplier)。先看看維基百科裡面關於它的介紹：
在數學中的最佳化問題中，拉格朗日乘數法（以數學家約瑟夫·拉格朗日命名）是一種尋找多元函數在其變數受到一個或多個條件的限制時的極值的方法。這種方法可以將一個有n個變數與k個限制條件的最佳化問題轉換為一個解有n + k個變數的方程式組的解的問題。這種方法中引入了一個或一組新的未知數，即拉格朗日乘數
尋找一個多元函數在其變數受到一個或多個條件限制時的極值的方法。嗯，彷彿完美為我們現在的狀況設計的一樣。其實我也不清楚到目前為止的推論是不是為了接著引用這個概念所以如此推導，或者是推導到這個地方剛好可以運用拉格朗日乘數來解決問題。總之，將拉格朗日乘數帶入之後得到的式子為
把式1的概念轉換成一個n+k個變數的方程組。然後根據線性回歸，可以再把式子改寫為
可以看本系列(6)，式3的地方。這樣一來，式子變成w_REG的線性方程式。
在λ>0時，方程式為
移項並把2/N除去，最後得到
I是單元矩陣。由於z^Tz為半正定矩陣，而λ>0，λI>0，故兩者相加之後變成正定矩陣，必有反矩陣存在，則w_REG必有解。這個解過程稱為ridge regression，是線性回歸的一種變化。
從多項式的角度
回到式1，可以看到方程式的左邊項
是一個微分的概念。梯度本來就是微分的概念。他趨近於0，表示E_in接近最小值。同理，式1也可以從微分的觀點看，既然要求
為0，那就表示要求他的積分
的最小值了。這個式子由E_in加上一項所組成，後面這一項
稱做正規項(regularizer)，幫助正規化的；整個式2則可以用一個
代稱，叫做augmented error，把誤差放大的。那為什麼要把式1等價成式2呢？在式1的時候，梯度受到法向量的限制，在一個球裡面，求梯度。式2把限制放在regularizer裡面，不用再受到法向量的限制，可以看成像前面一樣梯度下降的方式處理。最佳解就是E_aug的最小值，已知也從C換成λ。
λ基本上不會是負值，因為他和法向量以及梯度向量有關。只要λ>0，上面說的都成立。那麼，如果λ=0怎麼辦？λ=0時regularizer消失，變成原本的E_in，就是最容易overfitting那個十次多項式啦。
下面這張圖可以很好的看到λ的變化對於模型預測的影響：
λ的些微變化可以造成很大的影響。從
知道λ大的時候，w越大會讓誤差放大，所以到最後w就會變小。w變小之後，C是由w的長度為半徑畫的圓，所以也會變小。這個利用λ逼使w變小的做法稱做weight decay regularization，也是機器學習和深度學習裡面很常出現的專有名詞。
這裡舉線性回歸和多項式回歸為例，但weight decay的做法也可以用在其他的狀況，例如羅吉斯回歸。有些時候方成式之間各項的向量不一定垂直，這會導致正規化的時候對於每一項的要求不一致。而且如果某些項目初始係數較小需要放大，但λ又要降低w，就會形成矛盾。因此有一種做法是用座標轉換先將項量都調整成彼此垂直，然後再進行正規化。這種作法產生的多項式叫做legendre polynomials。
和VC dimension的關聯性
現在整理一下正規化的式子。首先是一開始的「限制版」：將多項式中各項的係數，其範數相加限制為一個常數C：
想像下降的梯度最大範圍在一個半徑為√C的球體裡。同時，根據VC theory，我們設定的E_out和E_in的關係為
其中Ω是一個限制(懲罰，penalty)，來自於hypothesis set被常數C限制的狀況。
接著是「無限制版」：利用積分，變成
把C換成λ，沒有法向量的限制，可以向前面一樣任意做梯度下降。
對照上面兩個式子，就可以發現：在無限制版本中，追求E_aug，設定一個λ，他有一個對應的C。然後就間接地完成了VC theory。在無限制的版本中，我們某方面來說是考慮了所有的w，但因為penalty的限制，使我們最終能選擇的w很有限，只有一小部分，這一小部分剛好和半徑為√C的球體內的範圍重合。可是，這樣我們就可以很放心的把所有w都納進來，反正有penalty幫忙過濾。重新看看這兩個式子：
Regularizer (w^Tw)可以想像成單一hypothesis的複雜度，因為它就是多項式的係數構成的向量相乘。如果在比較高次有係數，多項式就會比較複雜。
Ω(H)則是表示整個hypothesis set的複雜度，也就是有多少hypothesis set可以選擇。所以error augmented和VC有點不一樣，但他們共通的是都在計算複雜性。如果把Ω視為評估複雜度的符號，我們把w^Tw代換成Ω(w)，以表是單一hypothesis的複雜度。
這兩者有沒有關聯呢?可能有一點。如果單一hypothesis的複雜度高，某種程度上表示hypothesis set的複雜度也很高，因為這個hypothesis只是裡面的一種選擇嘛。所以，E_aug可能接近VC theory中不等式的右邊。從這裡推論，有可能E_aug可以比單純的E_in更好的找到小的E_out。所以E_aug可以不受限制的搜尋w，但又比E_in更好的能尋找E_out。
從VC dimension的角度
E_aug的VC dimension，也就是模型複雜度是
因為它沒有真正限制整個hypothesis set哪個不能選。但實際上，因為λ對應的C，我們知道它有「偏好」的，即為H(C)。所以我們可以用一個「等效」(effective) VC dimension的方式表達：
A就是演算法，在這裡表示最小的E_aug對應的hypothesis。如此一來，我們同時兼顧搜尋整個hypothesis set，同時又利用penalty過濾的方式篩選多項式，可以比較有效率的找到小的E_out。可以說，正規化限縮VC dimension到等效的範圍，讓泛化更好進行。
尋找更好的regularizer
除了weight decay，有沒有其他的regularizer呢?在尋找時有沒有什麼條件?
最好的方法就是知道target function，不過這也是不可能的。然而，根據資料對象，可以從domain knowledge去排除依些不適合使用的函數，這樣至少可以限縮一些範圍。
另外就是選用可以讓函數變比較平滑的：因為stochastic和deterministic noise的關係，函數常常很崎嶇。接下來要提到的L1 regularizer就是屬於這種。
還有一種是好最佳化的，可微分的。weight decay就是屬於這種。
那如果regularizer越選越爛怎麼辦?那就把λ設為0，不使用regularizer。這樣至少不會讓狀況更糟。
結論就是：有說服力的，容易評估的，容易最佳化的，適合作regularizer。
以下分別介紹L1和L2 regularizer。首先是L1。
絕對值，凸函數，但轉角處無法微分，是尖銳的。
因為是絕對值，所以是一個正方形(體)，而非圓形(球)。在邊界時，如果不是在端點上，該邊界的法向量全部相同。如果剛好和法向量不平行，那它就可以一直被拉著跑，直到端點為止，此時w有幾項可能為0。
缺點是非全可微分，但優點是較離散，可能好幾項是0，因此比較有效率。
再來是L2 regularizer。
好，其實就是weight decay，換個名字而已(被毆)。全段可微分，凸函數。容易最佳化。
λ的選擇
先看考慮stochastic noise的情況下，不同強度(σ²)對於λ的影響。
節點處為該情況時E_out最小值，畫垂線下來對應的就是最好的λ。再來是考慮不同deterministic noise的情況。這裡Q_f表示模型複雜度(多項式次數)
看起來不管是哪一種noise，只要noise越高，要取的小的E_out就要越大的λ。但因為實際上很難知道noise的確切量，所以還是只能從選擇λ入手。該如何選擇，請待下回分曉。
本篇介紹正規化，從多項式開始，講到限制，以及取代限制的方法，和VC的關聯性，以及如何選擇regularizer。運用到前面提過的一些觀念，是比較需要反覆思考的一個單元。
