機(jī)器學(xué)習(xí)中的范數(shù)規(guī)則化之（一）L0、L1與L2范數(shù)

zouxy09@qq.com

http://blog.csdn.net/zouxy09

       今天我們聊聊機(jī)器學(xué)習(xí)中出現(xiàn)的非常頻繁的問題：過擬合與規(guī)則化。我們先簡(jiǎn)單的來理解下常用的L0、L1、L2和核范數(shù)規(guī)則化。最后聊下規(guī)則化項(xiàng)參數(shù)的選擇問題。這里因?yàn)槠容^龐大，為了不嚇到大家，我將這個(gè)五個(gè)部分分成兩篇博文。知識(shí)有限，以下都是我一些淺顯的看法，如果理解存在錯(cuò)誤，希望大家不吝指正。謝謝。

       監(jiān)督機(jī)器學(xué)習(xí)問題無非就是“minimizeyour error while regularizing your parameters”，也就是在規(guī)則化參數(shù)的同時(shí)最小化誤差。最小化誤差是為了讓我們的模型擬合我們的訓(xùn)練數(shù)據(jù)，而規(guī)則化參數(shù)是防止我們的模型過分?jǐn)M合我們的訓(xùn)練數(shù)據(jù)。多么簡(jiǎn)約的哲學(xué)??！因?yàn)閰?shù)太多，會(huì)導(dǎo)致我們的模型復(fù)雜度上升，容易過擬合，也就是我們的訓(xùn)練誤差會(huì)很小。但訓(xùn)練誤差小并不是我們的最終目標(biāo)，我們的目標(biāo)是希望模型的測(cè)試誤差小，也就是能準(zhǔn)確的預(yù)測(cè)新的樣本。所以，我們需要保證模型“簡(jiǎn)單”的基礎(chǔ)上最小化訓(xùn)練誤差，這樣得到的參數(shù)才具有好的泛化性能（也就是測(cè)試誤差也?。?，而模型“簡(jiǎn)單”就是通過規(guī)則函數(shù)來實(shí)現(xiàn)的。另外，規(guī)則項(xiàng)的使用還可以約束我們的模型的特性。這樣就可以將人對(duì)這個(gè)模型的先驗(yàn)知識(shí)融入到模型的學(xué)習(xí)當(dāng)中，強(qiáng)行地讓學(xué)習(xí)到的模型具有人想要的特性，例如稀疏、低秩、平滑等等。要知道，有時(shí)候人的先驗(yàn)是非常重要的。前人的經(jīng)驗(yàn)會(huì)讓你少走很多彎路，這就是為什么我們平時(shí)學(xué)習(xí)最好找個(gè)大牛帶帶的原因。一句點(diǎn)撥可以為我們撥開眼前烏云，還我們一片晴空萬里，醍醐灌頂。對(duì)機(jī)器學(xué)習(xí)也是一樣，如果被我們?nèi)松晕Ⅻc(diǎn)撥一下，它肯定能更快的學(xué)習(xí)相應(yīng)的任務(wù)。只是由于人和機(jī)器的交流目前還沒有那么直接的方法，目前這個(gè)媒介只能由規(guī)則項(xiàng)來擔(dān)當(dāng)了。

       還有幾種角度來看待規(guī)則化的。規(guī)則化符合奧卡姆剃刀(Occam's razor)原理。這名字好霸氣，razor！不過它的思想很平易近人：在所有可能選擇的模型中，我們應(yīng)該選擇能夠很好地解釋已知數(shù)據(jù)并且十分簡(jiǎn)單的模型。從貝葉斯估計(jì)的角度來看，規(guī)則化項(xiàng)對(duì)應(yīng)于模型的先驗(yàn)概率。民間還有個(gè)說法就是，規(guī)則化是結(jié)構(gòu)風(fēng)險(xiǎn)最小化策略的實(shí)現(xiàn)，是在經(jīng)驗(yàn)風(fēng)險(xiǎn)上加一個(gè)正則化項(xiàng)(regularizer)或懲罰項(xiàng)(penalty term)。

       一般來說，監(jiān)督學(xué)習(xí)可以看做最小化下面的目標(biāo)函數(shù)：

       其中，第一項(xiàng)L(y_i,f(x_i;w)) 衡量我們的模型（分類或者回歸）對(duì)第i個(gè)樣本的預(yù)測(cè)值f(x_i;w)和真實(shí)的標(biāo)簽y_i之前的誤差。因?yàn)槲覀兊哪Ｐ褪且獢M合我們的訓(xùn)練樣本的嘛，所以我們要求這一項(xiàng)最小，也就是要求我們的模型盡量的擬合我們的訓(xùn)練數(shù)據(jù)。但正如上面說言，我們不僅要保證訓(xùn)練誤差最小，我們更希望我們的模型測(cè)試誤差小，所以我們需要加上第二項(xiàng)，也就是對(duì)參數(shù)w的規(guī)則化函數(shù)Ω(w)去約束我們的模型盡量的簡(jiǎn)單。

        OK，到這里，如果你在機(jī)器學(xué)習(xí)浴血奮戰(zhàn)多年，你會(huì)發(fā)現(xiàn)，哎喲喲，機(jī)器學(xué)習(xí)的大部分帶參模型都和這個(gè)不但形似，而且神似。是的，其實(shí)大部分無非就是變換這兩項(xiàng)而已。對(duì)于第一項(xiàng)Loss函數(shù)，如果是Square loss，那就是最小二乘了；如果是Hinge Loss，那就是著名的SVM了；如果是exp-Loss，那就是牛逼的 Boosting了；如果是log-Loss，那就是Logistic Regression了；還有等等。不同的loss函數(shù)，具有不同的擬合特性，這個(gè)也得就具體問題具體分析的。但這里，我們先不究loss函數(shù)的問題，我們把目光轉(zhuǎn)向“規(guī)則項(xiàng)Ω(w)”。

       規(guī)則化函數(shù)Ω(w)也有很多種選擇，一般是模型復(fù)雜度的單調(diào)遞增函數(shù)，模型越復(fù)雜，規(guī)則化值就越大。比如，規(guī)則化項(xiàng)可以是模型參數(shù)向量的范數(shù)。然而，不同的選擇對(duì)參數(shù)w的約束不同，取得的效果也不同，但我們?cè)谡撐闹谐Ｒ姷亩季奂冢毫惴稊?shù)、一范數(shù)、二范數(shù)、跡范數(shù)、Frobenius范數(shù)和核范數(shù)等等。這么多范數(shù)，到底它們表達(dá)啥意思？具有啥能力？什么時(shí)候才能用？什么時(shí)候需要用呢？不急不急，下面我們挑幾個(gè)常見的娓娓道來。

一、L0范數(shù)與L1范數(shù)

       L0范數(shù)是指向量中非0的元素的個(gè)數(shù)。如果我們用L0范數(shù)來規(guī)則化一個(gè)參數(shù)矩陣W的話，就是希望W的大部分元素都是0。這太直觀了，太露骨了吧，換句話說，讓參數(shù)W是稀疏的。OK，看到了“稀疏”二字，大家都應(yīng)該從當(dāng)下風(fēng)風(fēng)火火的“壓縮感知”和“稀疏編碼”中醒悟過來，原來用的漫山遍野的“稀疏”就是通過這玩意來實(shí)現(xiàn)的。但你又開始懷疑了，是這樣嗎？看到的papers世界中，稀疏不是都通過L1范數(shù)來實(shí)現(xiàn)嗎？腦海里是不是到處都是||W||₁影子呀！幾乎是抬頭不見低頭見。沒錯(cuò)，這就是這節(jié)的題目把L0和L1放在一起的原因，因?yàn)樗麄冇兄撤N不尋常的關(guān)系。那我們?cè)賮砜纯碙1范數(shù)是什么？它為什么可以實(shí)現(xiàn)稀疏？為什么大家都用L1范數(shù)去實(shí)現(xiàn)稀疏，而不是L0范數(shù)呢？

       L1范數(shù)是指向量中各個(gè)元素絕對(duì)值之和，也有個(gè)美稱叫“稀疏規(guī)則算子”（Lasso regularization）。現(xiàn)在我們來分析下這個(gè)價(jià)值一個(gè)億的問題：為什么L1范數(shù)會(huì)使權(quán)值稀疏？有人可能會(huì)這樣給你回答“它是L0范數(shù)的最優(yōu)凸近似”。實(shí)際上，還存在一個(gè)更美的回答：任何的規(guī)則化算子，如果他在W_i=0的地方不可微，并且可以分解為一個(gè)“求和”的形式，那么這個(gè)規(guī)則化算子就可以實(shí)現(xiàn)稀疏。這說是這么說，W的L1范數(shù)是絕對(duì)值，|w|在w=0處是不可微，但這還是不夠直觀。這里因?yàn)槲覀冃枰蚅2范數(shù)進(jìn)行對(duì)比分析。所以關(guān)于L1范數(shù)的直觀理解，請(qǐng)待會(huì)看看第二節(jié)。

       對(duì)了，上面還有一個(gè)問題：既然L0可以實(shí)現(xiàn)稀疏，為什么不用L0，而要用L1呢？個(gè)人理解一是因?yàn)長(zhǎng)0范數(shù)很難優(yōu)化求解（NP難問題），二是L1范數(shù)是L0范數(shù)的最優(yōu)凸近似，而且它比L0范數(shù)要容易優(yōu)化求解。所以大家才把目光和萬千寵愛轉(zhuǎn)于L1范數(shù)。

       OK，來個(gè)一句話總結(jié)：L1范數(shù)和L0范數(shù)可以實(shí)現(xiàn)稀疏，L1因具有比L0更好的優(yōu)化求解特性而被廣泛應(yīng)用。

       好，到這里，我們大概知道了L1可以實(shí)現(xiàn)稀疏，但我們會(huì)想呀，為什么要稀疏？讓我們的參數(shù)稀疏有什么好處呢？這里扯兩點(diǎn)：

1）特征選擇(Feature Selection)：

       大家對(duì)稀疏規(guī)則化趨之若鶩的一個(gè)關(guān)鍵原因在于它能實(shí)現(xiàn)特征的自動(dòng)選擇。一般來說，x_i的大部分元素（也就是特征）都是和最終的輸出y_i沒有關(guān)系或者不提供任何信息的，在最小化目標(biāo)函數(shù)的時(shí)候考慮x_i這些額外的特征，雖然可以獲得更小的訓(xùn)練誤差，但在預(yù)測(cè)新的樣本時(shí)，這些沒用的信息反而會(huì)被考慮，從而干擾了對(duì)正確y_i的預(yù)測(cè)。稀疏規(guī)則化算子的引入就是為了完成特征自動(dòng)選擇的光榮使命，它會(huì)學(xué)習(xí)地去掉這些沒有信息的特征，也就是把這些特征對(duì)應(yīng)的權(quán)重置為0。

2）可解釋性(Interpretability)：

       另一個(gè)青睞于稀疏的理由是，模型更容易解釋。例如患某種病的概率是y，然后我們收集到的數(shù)據(jù)x是1000維的，也就是我們需要尋找這1000種因素到底是怎么影響患上這種病的概率的。假設(shè)我們這個(gè)是個(gè)回歸模型：y=w₁*x₁ w₂*x₂ … w₁₀₀₀*x₁₀₀₀ b（當(dāng)然了，為了讓y限定在[0,1]的范圍，一般還得加個(gè)Logistic函數(shù)）。通過學(xué)習(xí)，如果最后學(xué)習(xí)到的w*就只有很少的非零元素，例如只有5個(gè)非零的w_i，那么我們就有理由相信，這些對(duì)應(yīng)的特征在患病分析上面提供的信息是巨大的，決策性的。也就是說，患不患這種病只和這5個(gè)因素有關(guān)，那醫(yī)生就好分析多了。但如果1000個(gè)w_i都非0，醫(yī)生面對(duì)這1000種因素，累覺不愛。

二、L2范數(shù)

       除了L1范數(shù)，還有一種更受寵幸的規(guī)則化范數(shù)是L2范數(shù): ||W||₂。它也不遜于L1范數(shù)，它有兩個(gè)美稱，在回歸里面，有人把有它的回歸叫“嶺回歸”（Ridge Regression），有人也叫它“權(quán)值衰減weight decay”。這用的很多吧，因?yàn)樗膹?qiáng)大功效是改善機(jī)器學(xué)習(xí)里面一個(gè)非常重要的問題：過擬合。至于過擬合是什么，上面也解釋了，就是模型訓(xùn)練時(shí)候的誤差很小，但在測(cè)試的時(shí)候誤差很大，也就是我們的模型復(fù)雜到可以擬合到我們的所有訓(xùn)練樣本了，但在實(shí)際預(yù)測(cè)新的樣本的時(shí)候，糟糕的一塌糊涂。通俗的講就是應(yīng)試能力很強(qiáng)，實(shí)際應(yīng)用能力很差。擅長(zhǎng)背誦知識(shí)，卻不懂得靈活利用知識(shí)。例如下圖所示（來自Ng的course）：

       上面的圖是線性回歸，下面的圖是Logistic回歸，也可以說是分類的情況。從左到右分別是欠擬合（underfitting，也稱High-bias）、合適的擬合和過擬合（overfitting，也稱High variance）三種情況。可以看到，如果模型復(fù)雜（可以擬合任意的復(fù)雜函數(shù)），它可以讓我們的模型擬合所有的數(shù)據(jù)點(diǎn)，也就是基本上沒有誤差。對(duì)于回歸來說，就是我們的函數(shù)曲線通過了所有的數(shù)據(jù)點(diǎn)，如上圖右。對(duì)分類來說，就是我們的函數(shù)曲線要把所有的數(shù)據(jù)點(diǎn)都分類正確，如下圖右。這兩種情況很明顯過擬合了。

       OK，那現(xiàn)在到我們非常關(guān)鍵的問題了，為什么L2范數(shù)可以防止過擬合？回答這個(gè)問題之前，我們得先看看L2范數(shù)是個(gè)什么東西。

       L2范數(shù)是指向量各元素的平方和然后求平方根。我們讓L2范數(shù)的規(guī)則項(xiàng)||W||₂最小，可以使得W的每個(gè)元素都很小，都接近于0，但與L1范數(shù)不同，它不會(huì)讓它等于0，而是接近于0，這里是有很大的區(qū)別的哦。而越小的參數(shù)說明模型越簡(jiǎn)單，越簡(jiǎn)單的模型則越不容易產(chǎn)生過擬合現(xiàn)象。為什么越小的參數(shù)說明模型越簡(jiǎn)單？我也不懂，我的理解是：限制了參數(shù)很小，實(shí)際上就限制了多項(xiàng)式某些分量的影響很?。瓷厦婢€性回歸的模型的那個(gè)擬合的圖），這樣就相當(dāng)于減少參數(shù)個(gè)數(shù)。其實(shí)我也不太懂，希望大家可以指點(diǎn)下。

       這里也一句話總結(jié)下：通過L2范數(shù)，我們可以實(shí)現(xiàn)了對(duì)模型空間的限制，從而在一定程度上避免了過擬合。

       L2范數(shù)的好處是什么呢？這里也扯上兩點(diǎn)：

1）學(xué)習(xí)理論的角度：

       從學(xué)習(xí)理論的角度來說，L2范數(shù)可以防止過擬合，提升模型的泛化能力。

2）優(yōu)化計(jì)算的角度：

       從優(yōu)化或者數(shù)值計(jì)算的角度來說，L2范數(shù)有助于處理 condition number不好的情況下矩陣求逆很困難的問題。哎，等等，這condition number是啥？我先google一下哈。

       這里我們也故作高雅的來聊聊優(yōu)化問題。優(yōu)化有兩大難題，一是：局部最小值，二是：ill-condition病態(tài)問題。前者俺就不說了，大家都懂吧，我們要找的是全局最小值，如果局部最小值太多，那我們的優(yōu)化算法就很容易陷入局部最小而不能自拔，這很明顯不是觀眾愿意看到的劇情。那下面我們來聊聊ill-condition。ill-condition對(duì)應(yīng)的是well-condition。那他們分別代表什么？假設(shè)我們有個(gè)方程組AX=b，我們需要求解X。如果A或者b稍微的改變，會(huì)使得X的解發(fā)生很大的改變，那么這個(gè)方程組系統(tǒng)就是ill-condition的，反之就是well-condition的。我們具體舉個(gè)例子吧：

       咱們先看左邊的那個(gè)。第一行假設(shè)是我們的AX=b，第二行我們稍微改變下b，得到的x和沒改變前的差別很大，看到吧。第三行我們稍微改變下系數(shù)矩陣A，可以看到結(jié)果的變化也很大。換句話來說，這個(gè)系統(tǒng)的解對(duì)系數(shù)矩陣A或者b太敏感了。又因?yàn)橐话阄覀兊南禂?shù)矩陣A和b是從實(shí)驗(yàn)數(shù)據(jù)里面估計(jì)得到的，所以它是存在誤差的，如果我們的系統(tǒng)對(duì)這個(gè)誤差是可以容忍的就還好，但系統(tǒng)對(duì)這個(gè)誤差太敏感了，以至于我們的解的誤差更大，那這個(gè)解就太不靠譜了。所以這個(gè)方程組系統(tǒng)就是ill-conditioned病態(tài)的，不正常的，不穩(wěn)定的，有問題的，哈哈。這清楚了吧。右邊那個(gè)就叫well-condition的系統(tǒng)了。

       還是再啰嗦一下吧，對(duì)于一個(gè)ill-condition的系統(tǒng)，我的輸入稍微改變下，輸出就發(fā)生很大的改變，這不好啊，這表明我們的系統(tǒng)不能實(shí)用啊。你想想看，例如對(duì)于一個(gè)回歸問題y=f(x)，我們是用訓(xùn)練樣本x去訓(xùn)練模型f，使得y盡量輸出我們期待的值，例如0。那假如我們遇到一個(gè)樣本x’，這個(gè)樣本和訓(xùn)練樣本x差別很小，面對(duì)他，系統(tǒng)本應(yīng)該輸出和上面的y差不多的值的，例如0.00001，最后卻給我輸出了一個(gè)0.9999，這很明顯不對(duì)呀。就好像，你很熟悉的一個(gè)人臉上長(zhǎng)了個(gè)青春痘，你就不認(rèn)識(shí)他了，那你大腦就太差勁了，哈哈。所以如果一個(gè)系統(tǒng)是ill-conditioned病態(tài)的，我們就會(huì)對(duì)它的結(jié)果產(chǎn)生懷疑。那到底要相信它多少呢？我們得找個(gè)標(biāo)準(zhǔn)來衡量吧，因?yàn)橛行┫到y(tǒng)的病沒那么重，它的結(jié)果還是可以相信的，不能一刀切吧。終于回來了，上面的condition number就是拿來衡量ill-condition系統(tǒng)的可信度的。condition number衡量的是輸入發(fā)生微小變化的時(shí)候，輸出會(huì)發(fā)生多大的變化。也就是系統(tǒng)對(duì)微小變化的敏感度。condition number值小的就是well-conditioned的，大的就是ill-conditioned的。

       如果方陣A是非奇異的，那么A的conditionnumber定義為：

       也就是矩陣A的norm乘以它的逆的norm。所以具體的值是多少，就要看你選擇的norm是什么了。如果方陣A是奇異的，那么A的condition number就是正無窮大了。實(shí)際上，每一個(gè)可逆方陣都存在一個(gè)condition number。但如果要計(jì)算它，我們需要先知道這個(gè)方陣的norm（范數(shù)）和Machine Epsilon（機(jī)器的精度）。為什么要范數(shù)？范數(shù)就相當(dāng)于衡量一個(gè)矩陣的大小，我們知道矩陣是沒有大小的，當(dāng)上面不是要衡量一個(gè)矩陣A或者向量b變化的時(shí)候，我們的解x變化的大小嗎？所以肯定得要有一個(gè)東西來度量矩陣和向量的大小吧？對(duì)了，他就是范數(shù)，表示矩陣大小或者向量長(zhǎng)度。OK，經(jīng)過比較簡(jiǎn)單的證明，對(duì)于AX=b，我們可以得到以下的結(jié)論：

       也就是我們的解x的相對(duì)變化和A或者b的相對(duì)變化是有像上面那樣的關(guān)系的，其中k(A)的值就相當(dāng)于倍率，看到了嗎？相當(dāng)于x變化的界。

       對(duì)condition number來個(gè)一句話總結(jié)：conditionnumber是一個(gè)矩陣（或者它所描述的線性系統(tǒng)）的穩(wěn)定性或者敏感度的度量，如果一個(gè)矩陣的condition number在1附近，那么它就是well-conditioned的，如果遠(yuǎn)大于1，那么它就是ill-conditioned的，如果一個(gè)系統(tǒng)是ill-conditioned的，它的輸出結(jié)果就不要太相信了。

       好了，對(duì)這么一個(gè)東西，已經(jīng)說了好多了。對(duì)了，我們?yōu)槭裁戳牡竭@個(gè)的了？回到第一句話：從優(yōu)化或者數(shù)值計(jì)算的角度來說，L2范數(shù)有助于處理 condition number不好的情況下矩陣求逆很困難的問題。因?yàn)槟繕?biāo)函數(shù)如果是二次的，對(duì)于線性回歸來說，那實(shí)際上是有解析解的，求導(dǎo)并令導(dǎo)數(shù)等于零即可得到最優(yōu)解為：

       然而，如果當(dāng)我們的樣本X的數(shù)目比每個(gè)樣本的維度還要小的時(shí)候，矩陣X^TX將會(huì)不是滿秩的，也就是X^TX會(huì)變得不可逆，所以w*就沒辦法直接計(jì)算出來了?；蛘吒_切地說，將會(huì)有無窮多個(gè)解（因?yàn)槲覀兎匠探M的個(gè)數(shù)小于未知數(shù)的個(gè)數(shù)）。也就是說，我們的數(shù)據(jù)不足以確定一個(gè)解，如果我們從所有可行解里隨機(jī)選一個(gè)的話，很可能并不是真正好的解，總而言之，我們過擬合了。

       但如果加上L2規(guī)則項(xiàng)，就變成了下面這種情況，就可以直接求逆了：

       這里面，專業(yè)點(diǎn)的描述是：要得到這個(gè)解，我們通常并不直接求矩陣的逆，而是通過解線性方程組的方式（例如高斯消元法）來計(jì)算?？紤]沒有規(guī)則項(xiàng)的時(shí)候，也就是λ=0的情況，如果矩陣X^TX的 condition number 很大的話，解線性方程組就會(huì)在數(shù)值上相當(dāng)不穩(wěn)定，而這個(gè)規(guī)則項(xiàng)的引入則可以改善condition number。

       另外，如果使用迭代優(yōu)化的算法，condition number 太大仍然會(huì)導(dǎo)致問題：它會(huì)拖慢迭代的收斂速度，而規(guī)則項(xiàng)從優(yōu)化的角度來看，實(shí)際上是將目標(biāo)函數(shù)變成λ-strongly convex（λ強(qiáng)凸）的了。哎喲喲，這里又出現(xiàn)個(gè)λ強(qiáng)凸，啥叫λ強(qiáng)凸呢？

       當(dāng)f滿足：

       時(shí)，我們稱f為λ-stronglyconvex函數(shù)，其中參數(shù)λ>0。當(dāng)λ=0時(shí)退回到普通convex 函數(shù)的定義。

       在直觀的說明強(qiáng)凸之前，我們先看看普通的凸是怎樣的。假設(shè)我們讓f在x的地方做一階泰勒近似（一階泰勒展開忘了嗎？f(x)=f(a) f'(a)(x-a) o(||x-a||).）：

       直觀來講，convex 性質(zhì)是指函數(shù)曲線位于該點(diǎn)處的切線，也就是線性近似之上，而 strongly convex 則進(jìn)一步要求位于該處的一個(gè)二次函數(shù)上方，也就是說要求函數(shù)不要太“平坦”而是可以保證有一定的“向上彎曲”的趨勢(shì)。專業(yè)點(diǎn)說，就是convex 可以保證函數(shù)在任意一點(diǎn)都處于它的一階泰勒函數(shù)之上，而strongly convex可以保證函數(shù)在任意一點(diǎn)都存在一個(gè)非常漂亮的二次下界quadratic lower bound。當(dāng)然這是一個(gè)很強(qiáng)的假設(shè)，但是同時(shí)也是非常重要的假設(shè)?？赡苓€不好理解，那我們畫個(gè)圖來形象的理解下。

       大家一看到上面這個(gè)圖就全明白了吧。不用我啰嗦了吧。還是啰嗦一下吧。我們?nèi)∥覀兊淖顑?yōu)解w*的地方。如果我們的函數(shù)f(w)，見左圖，也就是紅色那個(gè)函數(shù)，都會(huì)位于藍(lán)色虛線的那根二次函數(shù)之上，這樣就算w_t和w*離的比較近的時(shí)候，f(w_t)和f(w*)的值差別還是挺大的，也就是會(huì)保證在我們的最優(yōu)解w*附近的時(shí)候，還存在較大的梯度值，這樣我們才可以在比較少的迭代次數(shù)內(nèi)達(dá)到w*。但對(duì)于右圖，紅色的函數(shù)f(w)只約束在一個(gè)線性的藍(lán)色虛線之上，假設(shè)是如右圖的很不幸的情況（非常平坦），那在w_t還離我們的最優(yōu)點(diǎn)w*很遠(yuǎn)的時(shí)候，我們的近似梯度(f(w_t)-f(w*))/(w_t-w*)就已經(jīng)非常小了，在w_t處的近似梯度?f/?w就更小了，這樣通過梯度下降w_{t 1}=w_t-α*(?f/?w)，我們得到的結(jié)果就是w的變化非常緩慢，像蝸牛一樣，非常緩慢的向我們的最優(yōu)點(diǎn)w*爬動(dòng)，那在有限的迭代時(shí)間內(nèi)，它離我們的最優(yōu)點(diǎn)還是很遠(yuǎn)。

       所以僅僅靠convex 性質(zhì)并不能保證在梯度下降和有限的迭代次數(shù)的情況下得到的點(diǎn)w會(huì)是一個(gè)比較好的全局最小點(diǎn)w*的近似點(diǎn)（插個(gè)話，有地方說，實(shí)際上讓迭代在接近最優(yōu)的地方停止，也是一種規(guī)則化或者提高泛化性能的方法）。正如上面分析的那樣，如果f(w)在全局最小點(diǎn)w*周圍是非常平坦的情況的話，我們有可能會(huì)找到一個(gè)很遠(yuǎn)的點(diǎn)。但如果我們有“強(qiáng)凸”的話，就能對(duì)情況做一些控制，我們就可以得到一個(gè)更好的近似解。至于有多好嘛，這里面有一個(gè)bound，這個(gè) bound 的好壞也要取決于strongly convex性質(zhì)中的常數(shù)α的大小?？吹竭@里，不知道大家學(xué)聰明了沒有。如果要獲得strongly convex怎么做？最簡(jiǎn)單的就是往里面加入一項(xiàng)(α/2)*||w||²。

       呃，講個(gè)strongly convex花了那么多的篇幅。實(shí)際上，在梯度下降中，目標(biāo)函數(shù)收斂速率的上界實(shí)際上是和矩陣X^TX的 condition number有關(guān)，X^TX的 condition number 越小，上界就越小，也就是收斂速度會(huì)越快。

這一個(gè)優(yōu)化說了那么多的東西。還是來個(gè)一句話總結(jié)吧：L2范數(shù)不但可以防止過擬合，還可以讓我們的優(yōu)化求解變得穩(wěn)定和快速。

       好了，這里兌現(xiàn)上面的承諾，來直觀的聊聊L1和L2的差別，為什么一個(gè)讓絕對(duì)值最小，一個(gè)讓平方最小，會(huì)有那么大的差別呢？我看到的有兩種幾何上直觀的解析：

1）下降速度：

       我們知道，L1和L2都是規(guī)則化的方式，我們將權(quán)值參數(shù)以L1或者L2的方式放到代價(jià)函數(shù)里面去。然后模型就會(huì)嘗試去最小化這些權(quán)值參數(shù)。而這個(gè)最小化就像一個(gè)下坡的過程，L1和L2的差別就在于這個(gè)“坡”不同，如下圖：L1就是按絕對(duì)值函數(shù)的“坡”下降的，而L2是按二次函數(shù)的“坡”下降。所以實(shí)際上在0附近，L1的下降速度比L2的下降速度要快。所以會(huì)非?？斓媒档?。不過我覺得這里解釋的不太中肯，當(dāng)然了也不知道是不是自己理解的問題。

       L1在江湖上人稱Lasso，L2人稱Ridge。不過這兩個(gè)名字還挺讓人迷糊的，看上面的圖片，Lasso的圖看起來就像ridge，而ridge的圖看起來就像lasso。

2）模型空間的限制：

       實(shí)際上，對(duì)于L1和L2規(guī)則化的代價(jià)函數(shù)來說，我們可以寫成以下形式：

       也就是說，我們將模型空間限制在w的一個(gè)L1-ball 中。為了便于可視化，我們考慮兩維的情況，在(w1, w2)平面上可以畫出目標(biāo)函數(shù)的等高線，而約束條件則成為平面上半徑為C的一個(gè) norm ball 。等高線與 norm ball 首次相交的地方就是最優(yōu)解：

       可以看到，L1-ball 與L2-ball 的不同就在于L1在和每個(gè)坐標(biāo)軸相交的地方都有“角”出現(xiàn)，而目標(biāo)函數(shù)的測(cè)地線除非位置擺得非常好，大部分時(shí)候都會(huì)在角的地方相交。注意到在角的位置就會(huì)產(chǎn)生稀疏性，例如圖中的相交點(diǎn)就有w1=0，而更高維的時(shí)候（想象一下三維的L1-ball 是什么樣的？）除了角點(diǎn)以外，還有很多邊的輪廓也是既有很大的概率成為第一次相交的地方，又會(huì)產(chǎn)生稀疏性。

       相比之下，L2-ball 就沒有這樣的性質(zhì)，因?yàn)闆]有角，所以第一次相交的地方出現(xiàn)在具有稀疏性的位置的概率就變得非常小了。這就從直觀上來解釋了為什么L1-regularization 能產(chǎn)生稀疏性，而L2-regularization 不行的原因了。

       因此，一句話總結(jié)就是：L1會(huì)趨向于產(chǎn)生少量的特征，而其他的特征都是0，而L2會(huì)選擇更多的特征，這些特征都會(huì)接近于0。Lasso在特征選擇時(shí)候非常有用，而Ridge就只是一種規(guī)則化而已。

       OK，就聊到這里。下一篇博文我們聊聊核范數(shù)和規(guī)則化項(xiàng)參數(shù)選擇的問題。全篇的參考資料也請(qǐng)見下一篇博文，這里不重復(fù)列出。謝謝。