機器學習中的范數(shù)規(guī)則化之(一)L0、L1與L2范數(shù)
今天我們聊聊機器學習中出現(xiàn)的非常頻繁的問題:過擬合與規(guī)則化。我們先簡單的來理解下常用的L0、L1、L2和核范數(shù)規(guī)則化。最后聊下規(guī)則化項參數(shù)的選擇問題。這里因為篇幅比較龐大,為了不嚇到大家,我將這個五個部分分成兩篇博文。知識有限,以下都是我一些淺顯的看法,如果理解存在錯誤,希望大家不吝指正。謝謝。
監(jiān)督機器學習問題無非就是“minimizeyour error while regularizing your parameters”,也就是在規(guī)則化參數(shù)的同時最小化誤差。最小化誤差是為了讓我們的模型擬合我們的訓練數(shù)據(jù),而規(guī)則化參數(shù)是防止我們的模型過分擬合我們的訓練數(shù)據(jù)。多么簡約的哲學啊!因為參數(shù)太多,會導致我們的模型復雜度上升,容易過擬合,也就是我們的訓練誤差會很小。但訓練誤差小并不是我們的最終目標,我們的目標是希望模型的測試誤差小,也就是能準確的預測新的樣本。所以,我們需要保證模型“簡單”的基礎上最小化訓練誤差,這樣得到的參數(shù)才具有好的泛化性能(也就是測試誤差也?。?,而模型“簡單”就是通過規(guī)則函數(shù)來實現(xiàn)的。另外,規(guī)則項的使用還可以約束我們的模型的特性。這樣就可以將人對這個模型的先驗知識融入到模型的學習當中,強行地讓學習到的模型具有人想要的特性,例如稀疏、低秩、平滑等等。要知道,有時候人的先驗是非常重要的。前人的經(jīng)驗會讓你少走很多彎路,這就是為什么我們平時學習最好找個大牛帶帶的原因。一句點撥可以為我們撥開眼前烏云,還我們一片晴空萬里,醍醐灌頂。對機器學習也是一樣,如果被我們?nèi)松晕Ⅻc撥一下,它肯定能更快的學習相應的任務。只是由于人和機器的交流目前還沒有那么直接的方法,目前這個媒介只能由規(guī)則項來擔當了。 還有幾種角度來看待規(guī)則化的。規(guī)則化符合奧卡姆剃刀(Occam's razor)原理。這名字好霸氣,razor!不過它的思想很平易近人:在所有可能選擇的模型中,我們應該選擇能夠很好地解釋已知數(shù)據(jù)并且十分簡單的模型。從貝葉斯估計的角度來看,規(guī)則化項對應于模型的先驗概率。民間還有個說法就是,規(guī)則化是結(jié)構(gòu)風險最小化策略的實現(xiàn),是在經(jīng)驗風險上加一個正則化項(regularizer)或懲罰項(penalty term)。 一般來說,監(jiān)督學習可以看做最小化下面的目標函數(shù):
其中,第一項L(yi,f(xi;w)) 衡量我們的模型(分類或者回歸)對第i個樣本的預測值f(xi;w)和真實的標簽yi之前的誤差。因為我們的模型是要擬合我們的訓練樣本的嘛,所以我們要求這一項最小,也就是要求我們的模型盡量的擬合我們的訓練數(shù)據(jù)。但正如上面說言,我們不僅要保證訓練誤差最小,我們更希望我們的模型測試誤差小,所以我們需要加上第二項,也就是對參數(shù)w的規(guī)則化函數(shù)Ω(w)去約束我們的模型盡量的簡單。 OK,到這里,如果你在機器學習浴血奮戰(zhàn)多年,你會發(fā)現(xiàn),哎喲喲,機器學習的大部分帶參模型都和這個不但形似,而且神似。是的,其實大部分無非就是變換這兩項而已。對于第一項Loss函數(shù),如果是Square loss,那就是最小二乘了;如果是Hinge Loss,那就是著名的SVM了;如果是exp-Loss,那就是牛逼的 Boosting了;如果是log-Loss,那就是Logistic Regression了;還有等等。不同的loss函數(shù),具有不同的擬合特性,這個也得就具體問題具體分析的。但這里,我們先不究loss函數(shù)的問題,我們把目光轉(zhuǎn)向“規(guī)則項Ω(w)”。 規(guī)則化函數(shù)Ω(w)也有很多種選擇,一般是模型復雜度的單調(diào)遞增函數(shù),模型越復雜,規(guī)則化值就越大。比如,規(guī)則化項可以是模型參數(shù)向量的范數(shù)。然而,不同的選擇對參數(shù)w的約束不同,取得的效果也不同,但我們在論文中常見的都聚集在:零范數(shù)、一范數(shù)、二范數(shù)、跡范數(shù)、Frobenius范數(shù)和核范數(shù)等等。這么多范數(shù),到底它們表達啥意思?具有啥能力?什么時候才能用?什么時候需要用呢?不急不急,下面我們挑幾個常見的娓娓道來。
一、L0范數(shù)與L1范數(shù) L0范數(shù)是指向量中非0的元素的個數(shù)。如果我們用L0范數(shù)來規(guī)則化一個參數(shù)矩陣W的話,就是希望W的大部分元素都是0。這太直觀了,太露骨了吧,換句話說,讓參數(shù)W是稀疏的。OK,看到了“稀疏”二字,大家都應該從當下風風火火的“壓縮感知”和“稀疏編碼”中醒悟過來,原來用的漫山遍野的“稀疏”就是通過這玩意來實現(xiàn)的。但你又開始懷疑了,是這樣嗎?看到的papers世界中,稀疏不是都通過L1范數(shù)來實現(xiàn)嗎?腦海里是不是到處都是||W||1影子呀!幾乎是抬頭不見低頭見。沒錯,這就是這節(jié)的題目把L0和L1放在一起的原因,因為他們有著某種不尋常的關(guān)系。那我們再來看看L1范數(shù)是什么?它為什么可以實現(xiàn)稀疏?為什么大家都用L1范數(shù)去實現(xiàn)稀疏,而不是L0范數(shù)呢? L1范數(shù)是指向量中各個元素絕對值之和,也有個美稱叫“稀疏規(guī)則算子”(Lasso regularization)?,F(xiàn)在我們來分析下這個價值一個億的問題:為什么L1范數(shù)會使權(quán)值稀疏?有人可能會這樣給你回答“它是L0范數(shù)的最優(yōu)凸近似”。實際上,還存在一個更美的回答:任何的規(guī)則化算子,如果他在Wi=0的地方不可微,并且可以分解為一個“求和”的形式,那么這個規(guī)則化算子就可以實現(xiàn)稀疏。這說是這么說,W的L1范數(shù)是絕對值,|w|在w=0處是不可微,但這還是不夠直觀。這里因為我們需要和L2范數(shù)進行對比分析。所以關(guān)于L1范數(shù)的直觀理解,請待會看看第二節(jié)。 對了,上面還有一個問題:既然L0可以實現(xiàn)稀疏,為什么不用L0,而要用L1呢?個人理解一是因為L0范數(shù)很難優(yōu)化求解(NP難問題),二是L1范數(shù)是L0范數(shù)的最優(yōu)凸近似,而且它比L0范數(shù)要容易優(yōu)化求解。所以大家才把目光和萬千寵愛轉(zhuǎn)于L1范數(shù)。
OK,來個一句話總結(jié):L1范數(shù)和L0范數(shù)可以實現(xiàn)稀疏,L1因具有比L0更好的優(yōu)化求解特性而被廣泛應用。 好,到這里,我們大概知道了L1可以實現(xiàn)稀疏,但我們會想呀,為什么要稀疏?讓我們的參數(shù)稀疏有什么好處呢?這里扯兩點: 1)特征選擇(Feature Selection): 大家對稀疏規(guī)則化趨之若鶩的一個關(guān)鍵原因在于它能實現(xiàn)特征的自動選擇。一般來說,xi的大部分元素(也就是特征)都是和最終的輸出yi沒有關(guān)系或者不提供任何信息的,在最小化目標函數(shù)的時候考慮xi這些額外的特征,雖然可以獲得更小的訓練誤差,但在預測新的樣本時,這些沒用的信息反而會被考慮,從而干擾了對正確yi的預測。稀疏規(guī)則化算子的引入就是為了完成特征自動選擇的光榮使命,它會學習地去掉這些沒有信息的特征,也就是把這些特征對應的權(quán)重置為0。 2)可解釋性(Interpretability): 另一個青睞于稀疏的理由是,模型更容易解釋。例如患某種病的概率是y,然后我們收集到的數(shù)據(jù)x是1000維的,也就是我們需要尋找這1000種因素到底是怎么影響患上這種病的概率的。假設我們這個是個回歸模型:y=w1*x1 w2*x2 … w1000*x1000 b(當然了,為了讓y限定在[0,1]的范圍,一般還得加個Logistic函數(shù))。通過學習,如果最后學習到的w*就只有很少的非零元素,例如只有5個非零的wi,那么我們就有理由相信,這些對應的特征在患病分析上面提供的信息是巨大的,決策性的。也就是說,患不患這種病只和這5個因素有關(guān),那醫(yī)生就好分析多了。但如果1000個wi都非0,醫(yī)生面對這1000種因素,累覺不愛。
二、L2范數(shù) 除了L1范數(shù),還有一種更受寵幸的規(guī)則化范數(shù)是L2范數(shù): ||W||2。它也不遜于L1范數(shù),它有兩個美稱,在回歸里面,有人把有它的回歸叫“嶺回歸”(Ridge Regression),有人也叫它“權(quán)值衰減weight decay”。這用的很多吧,因為它的強大功效是改善機器學習里面一個非常重要的問題:過擬合。至于過擬合是什么,上面也解釋了,就是模型訓練時候的誤差很小,但在測試的時候誤差很大,也就是我們的模型復雜到可以擬合到我們的所有訓練樣本了,但在實際預測新的樣本的時候,糟糕的一塌糊涂。通俗的講就是應試能力很強,實際應用能力很差。擅長背誦知識,卻不懂得靈活利用知識。例如下圖所示(來自Ng的course):
上面的圖是線性回歸,下面的圖是Logistic回歸,也可以說是分類的情況。從左到右分別是欠擬合(underfitting,也稱High-bias)、合適的擬合和過擬合(overfitting,也稱High variance)三種情況??梢钥吹?,如果模型復雜(可以擬合任意的復雜函數(shù)),它可以讓我們的模型擬合所有的數(shù)據(jù)點,也就是基本上沒有誤差。對于回歸來說,就是我們的函數(shù)曲線通過了所有的數(shù)據(jù)點,如上圖右。對分類來說,就是我們的函數(shù)曲線要把所有的數(shù)據(jù)點都分類正確,如下圖右。這兩種情況很明顯過擬合了。
OK,那現(xiàn)在到我們非常關(guān)鍵的問題了,為什么L2范數(shù)可以防止過擬合?回答這個問題之前,我們得先看看L2范數(shù)是個什么東西。 L2范數(shù)是指向量各元素的平方和然后求平方根。我們讓L2范數(shù)的規(guī)則項||W||2最小,可以使得W的每個元素都很小,都接近于0,但與L1范數(shù)不同,它不會讓它等于0,而是接近于0,這里是有很大的區(qū)別的哦。而越小的參數(shù)說明模型越簡單,越簡單的模型則越不容易產(chǎn)生過擬合現(xiàn)象。為什么越小的參數(shù)說明模型越簡單?我也不懂,我的理解是:限制了參數(shù)很小,實際上就限制了多項式某些分量的影響很?。瓷厦婢€性回歸的模型的那個擬合的圖),這樣就相當于減少參數(shù)個數(shù)。其實我也不太懂,希望大家可以指點下。 這里也一句話總結(jié)下:通過L2范數(shù),我們可以實現(xiàn)了對模型空間的限制,從而在一定程度上避免了過擬合。 L2范數(shù)的好處是什么呢?這里也扯上兩點: 1)學習理論的角度: 從學習理論的角度來說,L2范數(shù)可以防止過擬合,提升模型的泛化能力。 2)優(yōu)化計算的角度: 從優(yōu)化或者數(shù)值計算的角度來說,L2范數(shù)有助于處理 condition number不好的情況下矩陣求逆很困難的問題。哎,等等,這condition number是啥?我先google一下哈。 這里我們也故作高雅的來聊聊優(yōu)化問題。優(yōu)化有兩大難題,一是:局部最小值,二是:ill-condition病態(tài)問題。前者俺就不說了,大家都懂吧,我們要找的是全局最小值,如果局部最小值太多,那我們的優(yōu)化算法就很容易陷入局部最小而不能自拔,這很明顯不是觀眾愿意看到的劇情。那下面我們來聊聊ill-condition。ill-condition對應的是well-condition。那他們分別代表什么?假設我們有個方程組AX=b,我們需要求解X。如果A或者b稍微的改變,會使得X的解發(fā)生很大的改變,那么這個方程組系統(tǒng)就是ill-condition的,反之就是well-condition的。我們具體舉個例子吧:
咱們先看左邊的那個。第一行假設是我們的AX=b,第二行我們稍微改變下b,得到的x和沒改變前的差別很大,看到吧。第三行我們稍微改變下系數(shù)矩陣A,可以看到結(jié)果的變化也很大。換句話來說,這個系統(tǒng)的解對系數(shù)矩陣A或者b太敏感了。又因為一般我們的系數(shù)矩陣A和b是從實驗數(shù)據(jù)里面估計得到的,所以它是存在誤差的,如果我們的系統(tǒng)對這個誤差是可以容忍的就還好,但系統(tǒng)對這個誤差太敏感了,以至于我們的解的誤差更大,那這個解就太不靠譜了。所以這個方程組系統(tǒng)就是ill-conditioned病態(tài)的,不正常的,不穩(wěn)定的,有問題的,哈哈。這清楚了吧。右邊那個就叫well-condition的系統(tǒng)了。 還是再啰嗦一下吧,對于一個ill-condition的系統(tǒng),我的輸入稍微改變下,輸出就發(fā)生很大的改變,這不好啊,這表明我們的系統(tǒng)不能實用啊。你想想看,例如對于一個回歸問題y=f(x),我們是用訓練樣本x去訓練模型f,使得y盡量輸出我們期待的值,例如0。那假如我們遇到一個樣本x’,這個樣本和訓練樣本x差別很小,面對他,系統(tǒng)本應該輸出和上面的y差不多的值的,例如0.00001,最后卻給我輸出了一個0.9999,這很明顯不對呀。就好像,你很熟悉的一個人臉上長了個青春痘,你就不認識他了,那你大腦就太差勁了,哈哈。所以如果一個系統(tǒng)是ill-conditioned病態(tài)的,我們就會對它的結(jié)果產(chǎn)生懷疑。那到底要相信它多少呢?我們得找個標準來衡量吧,因為有些系統(tǒng)的病沒那么重,它的結(jié)果還是可以相信的,不能一刀切吧。終于回來了,上面的condition number就是拿來衡量ill-condition系統(tǒng)的可信度的。condition number衡量的是輸入發(fā)生微小變化的時候,輸出會發(fā)生多大的變化。也就是系統(tǒng)對微小變化的敏感度。condition number值小的就是well-conditioned的,大的就是ill-conditioned的。 如果方陣A是非奇異的,那么A的conditionnumber定義為:
也就是矩陣A的norm乘以它的逆的norm。所以具體的值是多少,就要看你選擇的norm是什么了。如果方陣A是奇異的,那么A的condition number就是正無窮大了。實際上,每一個可逆方陣都存在一個condition number。但如果要計算它,我們需要先知道這個方陣的norm(范數(shù))和Machine Epsilon(機器的精度)。為什么要范數(shù)?范數(shù)就相當于衡量一個矩陣的大小,我們知道矩陣是沒有大小的,當上面不是要衡量一個矩陣A或者向量b變化的時候,我們的解x變化的大小嗎?所以肯定得要有一個東西來度量矩陣和向量的大小吧?對了,他就是范數(shù),表示矩陣大小或者向量長度。OK,經(jīng)過比較簡單的證明,對于AX=b,我們可以得到以下的結(jié)論:
也就是我們的解x的相對變化和A或者b的相對變化是有像上面那樣的關(guān)系的,其中k(A)的值就相當于倍率,看到了嗎?相當于x變化的界。 對condition number來個一句話總結(jié):conditionnumber是一個矩陣(或者它所描述的線性系統(tǒng))的穩(wěn)定性或者敏感度的度量,如果一個矩陣的condition number在1附近,那么它就是well-conditioned的,如果遠大于1,那么它就是ill-conditioned的,如果一個系統(tǒng)是ill-conditioned的,它的輸出結(jié)果就不要太相信了。 好了,對這么一個東西,已經(jīng)說了好多了。對了,我們?yōu)槭裁戳牡竭@個的了?回到第一句話:從優(yōu)化或者數(shù)值計算的角度來說,L2范數(shù)有助于處理 condition number不好的情況下矩陣求逆很困難的問題。因為目標函數(shù)如果是二次的,對于線性回歸來說,那實際上是有解析解的,求導并令導數(shù)等于零即可得到最優(yōu)解為:
然而,如果當我們的樣本X的數(shù)目比每個樣本的維度還要小的時候,矩陣XTX將會不是滿秩的,也就是XTX會變得不可逆,所以w*就沒辦法直接計算出來了?;蛘吒_切地說,將會有無窮多個解(因為我們方程組的個數(shù)小于未知數(shù)的個數(shù))。也就是說,我們的數(shù)據(jù)不足以確定一個解,如果我們從所有可行解里隨機選一個的話,很可能并不是真正好的解,總而言之,我們過擬合了。 但如果加上L2規(guī)則項,就變成了下面這種情況,就可以直接求逆了:
這里面,專業(yè)點的描述是:要得到這個解,我們通常并不直接求矩陣的逆,而是通過解線性方程組的方式(例如高斯消元法)來計算??紤]沒有規(guī)則項的時候,也就是λ=0的情況,如果矩陣XTX的 condition number 很大的話,解線性方程組就會在數(shù)值上相當不穩(wěn)定,而這個規(guī)則項的引入則可以改善condition number。 另外,如果使用迭代優(yōu)化的算法,condition number 太大仍然會導致問題:它會拖慢迭代的收斂速度,而規(guī)則項從優(yōu)化的角度來看,實際上是將目標函數(shù)變成λ-strongly convex(λ強凸)的了。哎喲喲,這里又出現(xiàn)個λ強凸,啥叫λ強凸呢? 當f滿足:
時,我們稱f為λ-stronglyconvex函數(shù),其中參數(shù)λ>0。當λ=0時退回到普通convex 函數(shù)的定義。 在直觀的說明強凸之前,我們先看看普通的凸是怎樣的。假設我們讓f在x的地方做一階泰勒近似(一階泰勒展開忘了嗎?f(x)=f(a) f'(a)(x-a) o(||x-a||).):
直觀來講,convex 性質(zhì)是指函數(shù)曲線位于該點處的切線,也就是線性近似之上,而 strongly convex 則進一步要求位于該處的一個二次函數(shù)上方,也就是說要求函數(shù)不要太“平坦”而是可以保證有一定的“向上彎曲”的趨勢。專業(yè)點說,就是convex 可以保證函數(shù)在任意一點都處于它的一階泰勒函數(shù)之上,而strongly convex可以保證函數(shù)在任意一點都存在一個非常漂亮的二次下界quadratic lower bound。當然這是一個很強的假設,但是同時也是非常重要的假設。可能還不好理解,那我們畫個圖來形象的理解下。
大家一看到上面這個圖就全明白了吧。不用我啰嗦了吧。還是啰嗦一下吧。我們?nèi)∥覀兊淖顑?yōu)解w*的地方。如果我們的函數(shù)f(w),見左圖,也就是紅色那個函數(shù),都會位于藍色虛線的那根二次函數(shù)之上,這樣就算wt和w*離的比較近的時候,f(wt)和f(w*)的值差別還是挺大的,也就是會保證在我們的最優(yōu)解w*附近的時候,還存在較大的梯度值,這樣我們才可以在比較少的迭代次數(shù)內(nèi)達到w*。但對于右圖,紅色的函數(shù)f(w)只約束在一個線性的藍色虛線之上,假設是如右圖的很不幸的情況(非常平坦),那在wt還離我們的最優(yōu)點w*很遠的時候,我們的近似梯度(f(wt)-f(w*))/(wt-w*)就已經(jīng)非常小了,在wt處的近似梯度?f/?w就更小了,這樣通過梯度下降wt 1=wt-α*(?f/?w),我們得到的結(jié)果就是w的變化非常緩慢,像蝸牛一樣,非常緩慢的向我們的最優(yōu)點w*爬動,那在有限的迭代時間內(nèi),它離我們的最優(yōu)點還是很遠。 所以僅僅靠convex 性質(zhì)并不能保證在梯度下降和有限的迭代次數(shù)的情況下得到的點w會是一個比較好的全局最小點w*的近似點(插個話,有地方說,實際上讓迭代在接近最優(yōu)的地方停止,也是一種規(guī)則化或者提高泛化性能的方法)。正如上面分析的那樣,如果f(w)在全局最小點w*周圍是非常平坦的情況的話,我們有可能會找到一個很遠的點。但如果我們有“強凸”的話,就能對情況做一些控制,我們就可以得到一個更好的近似解。至于有多好嘛,這里面有一個bound,這個 bound 的好壞也要取決于strongly convex性質(zhì)中的常數(shù)α的大小??吹竭@里,不知道大家學聰明了沒有。如果要獲得strongly convex怎么做?最簡單的就是往里面加入一項(α/2)*||w||2。 呃,講個strongly convex花了那么多的篇幅。實際上,在梯度下降中,目標函數(shù)收斂速率的上界實際上是和矩陣XTX的 condition number有關(guān),XTX的 condition number 越小,上界就越小,也就是收斂速度會越快。 這一個優(yōu)化說了那么多的東西。還是來個一句話總結(jié)吧:L2范數(shù)不但可以防止過擬合,還可以讓我們的優(yōu)化求解變得穩(wěn)定和快速。 好了,這里兌現(xiàn)上面的承諾,來直觀的聊聊L1和L2的差別,為什么一個讓絕對值最小,一個讓平方最小,會有那么大的差別呢?我看到的有兩種幾何上直觀的解析: 1)下降速度: 我們知道,L1和L2都是規(guī)則化的方式,我們將權(quán)值參數(shù)以L1或者L2的方式放到代價函數(shù)里面去。然后模型就會嘗試去最小化這些權(quán)值參數(shù)。而這個最小化就像一個下坡的過程,L1和L2的差別就在于這個“坡”不同,如下圖:L1就是按絕對值函數(shù)的“坡”下降的,而L2是按二次函數(shù)的“坡”下降。所以實際上在0附近,L1的下降速度比L2的下降速度要快。所以會非??斓媒档?。不過我覺得這里解釋的不太中肯,當然了也不知道是不是自己理解的問題。
L1在江湖上人稱Lasso,L2人稱Ridge。不過這兩個名字還挺讓人迷糊的,看上面的圖片,Lasso的圖看起來就像ridge,而ridge的圖看起來就像lasso。 2)模型空間的限制: 實際上,對于L1和L2規(guī)則化的代價函數(shù)來說,我們可以寫成以下形式:
也就是說,我們將模型空間限制在w的一個L1-ball 中。為了便于可視化,我們考慮兩維的情況,在(w1, w2)平面上可以畫出目標函數(shù)的等高線,而約束條件則成為平面上半徑為C的一個 norm ball 。等高線與 norm ball 首次相交的地方就是最優(yōu)解:
可以看到,L1-ball 與L2-ball 的不同就在于L1在和每個坐標軸相交的地方都有“角”出現(xiàn),而目標函數(shù)的測地線除非位置擺得非常好,大部分時候都會在角的地方相交。注意到在角的位置就會產(chǎn)生稀疏性,例如圖中的相交點就有w1=0,而更高維的時候(想象一下三維的L1-ball 是什么樣的?)除了角點以外,還有很多邊的輪廓也是既有很大的概率成為第一次相交的地方,又會產(chǎn)生稀疏性。 相比之下,L2-ball 就沒有這樣的性質(zhì),因為沒有角,所以第一次相交的地方出現(xiàn)在具有稀疏性的位置的概率就變得非常小了。這就從直觀上來解釋了為什么L1-regularization 能產(chǎn)生稀疏性,而L2-regularization 不行的原因了。 因此,一句話總結(jié)就是:L1會趨向于產(chǎn)生少量的特征,而其他的特征都是0,而L2會選擇更多的特征,這些特征都會接近于0。Lasso在特征選擇時候非常有用,而Ridge就只是一種規(guī)則化而已。 OK,就聊到這里。下一篇博文我們聊聊核范數(shù)和規(guī)則化項參數(shù)選擇的問題。全篇的參考資料也請見下一篇博文,這里不重復列出。謝謝。 |
|
來自: 昵稱31750011 > 《深度學習》