機(jī)器學(xué)習(xí)中的范數(shù)規(guī)則化之（二）核范數(shù)與規(guī)則項(xiàng)參數(shù)選擇

zouxy09@qq.com

http://blog.csdn.net/zouxy09

?

? ? ? ?上一篇博文，我們聊到了L0，L1和L2范數(shù)，這篇我們絮叨絮叨下核范數(shù)和規(guī)則項(xiàng)參數(shù)選擇。知識有限，以下都是我一些淺顯的看法，如果理解存在錯(cuò)誤，希望大家不吝指正。謝謝。

?

三、核范數(shù)

? ? ? ?核范數(shù)||W||_*是指矩陣奇異值的和，英文稱呼叫Nuclear Norm。這個(gè)相對于上面火熱的L1和L2來說，可能大家就會陌生點(diǎn)。那它是干嘛用的呢？霸氣登場：約束Low-Rank（低秩）。OK，OK，那我們得知道Low-Rank是啥？用來干啥的？

? ? ? ?我們先來回憶下線性代數(shù)里面“秩”到底是啥？舉個(gè)簡單的例子吧：

? ? ? ?對上面的線性方程組，第一個(gè)方程和第二個(gè)方程有不同的解，而第2個(gè)方程和第3個(gè)方程的解完全相同。從這個(gè)意義上說，第3個(gè)方程是“多余”的，因?yàn)樗鼪]有帶來任何的信息量，把它去掉，所得的方程組與原來的方程組同解。為了從方程組中去掉多余的方程，自然就導(dǎo)出了“矩陣的秩”這一概念。

? ? ? ?還記得我們怎么手工求矩陣的秩嗎？為了求矩陣A的秩，我們是通過矩陣初等變換把A化為階梯型矩陣，若該階梯型矩陣有r個(gè)非零行，那A的秩rank(A)就等于r。從物理意義上講，矩陣的秩度量的就是矩陣的行列之間的相關(guān)性。如果矩陣的各行或列是線性無關(guān)的，矩陣就是滿秩的，也就是秩等于行數(shù)?；氐缴厦婢€性方程組來說吧，因?yàn)榫€性方程組可以用矩陣描述嘛。秩就表示了有多少個(gè)有用的方程了。上面的方程組有3個(gè)方程，實(shí)際上只有2個(gè)是有用的，一個(gè)是多余的，所以對應(yīng)的矩陣的秩就是2了。

? ? ? ?OK。既然秩可以度量相關(guān)性，而矩陣的相關(guān)性實(shí)際上有帶有了矩陣的結(jié)構(gòu)信息。如果矩陣之間各行的相關(guān)性很強(qiáng)，那么就表示這個(gè)矩陣實(shí)際可以投影到更低維的線性子空間，也就是用幾個(gè)向量就可以完全表達(dá)了，它就是低秩的。所以我們總結(jié)的一點(diǎn)就是：如果矩陣表達(dá)的是結(jié)構(gòu)性信息，例如圖像、用戶-推薦表等等，那么這個(gè)矩陣各行之間存在這一定的相關(guān)性，那這個(gè)矩陣一般就是低秩的。

? ? ? ?如果X是一個(gè)m行n列的數(shù)值矩陣，rank(X)是X的秩，假如rank (X)遠(yuǎn)小于m和n，則我們稱X是低秩矩陣。低秩矩陣每行或每列都可以用其他的行或列線性表出，可見它包含大量的冗余信息。利用這種冗余信息，可以對缺失數(shù)據(jù)進(jìn)行恢復(fù)，也可以對數(shù)據(jù)進(jìn)行特征提取。

? ? ? ?好了，低秩有了，那約束低秩只是約束rank(w)呀，和我們這節(jié)的核范數(shù)有什么關(guān)系呢？他們的關(guān)系和L0與L1的關(guān)系一樣。因?yàn)閞ank()是非凸的，在優(yōu)化問題里面很難求解，那么就需要尋找它的凸近似來近似它了。對，你沒猜錯(cuò)，rank(w)的凸近似就是核范數(shù)||W||_*。

? ? ? ?好了，到這里，我也沒什么好說的了，因?yàn)槲乙彩巧晕⒎戳讼逻@個(gè)東西，所以也還沒有深入去看它。但我發(fā)現(xiàn)了這玩意還有很多很有意思的應(yīng)用，下面我們舉幾個(gè)典型的吧。

1）矩陣填充(Matrix Completion)：

? ? ? ?我們首先說說矩陣填充用在哪。一個(gè)主流的應(yīng)用是在推薦系統(tǒng)里面。我們知道，推薦系統(tǒng)有一種方法是通過分析用戶的歷史記錄來給用戶推薦的。例如我們在看一部電影的時(shí)候，如果喜歡看，就會給它打個(gè)分，例如3顆星。然后系統(tǒng)，例如Netflix等知名網(wǎng)站就會分析這些數(shù)據(jù)，看看到底每部影片的題材到底是怎樣的？針對每個(gè)人，喜歡怎樣的電影，然后會給對應(yīng)的用戶推薦相似題材的電影。但有一個(gè)問題是：我們的網(wǎng)站上面有非常多的用戶，也有非常多的影片，不是所有的用戶都看過說有的電影，不是所有看過某電影的用戶都會給它評分。假設(shè)我們用一個(gè)“用戶-影片”的矩陣來描述這些記錄，例如下圖，可以看到，會有很多空白的地方。如果這些空白的地方存在，我們是很難對這個(gè)矩陣進(jìn)行分析的，所以在分析之前，一般需要先對其進(jìn)行補(bǔ)全。也叫矩陣填充。

? ? ? ?那到底怎么填呢？如何才能無中生有呢？每個(gè)空白的地方的信息是否蘊(yùn)含在其他已有的信息之上了呢？如果有，怎么提取出來呢？Yeah，這就是低秩生效的地方了。這叫低秩矩陣重構(gòu)問題，它可以用如下的模型表述：已知數(shù)據(jù)是一個(gè)給定的m*n矩陣A，如果其中一些元素因?yàn)槟撤N原因丟失了，我們能否根據(jù)其他行和列的元素，將這些元素恢復(fù)？當(dāng)然，如果沒有其他的參考條件，想要確定這些數(shù)據(jù)很困難。但如果我們已知A的秩rank(A)<<m且rank(A)<<n，那么我們可以通過矩陣各行(列)之間的線性相關(guān)將丟失的元素求出。你會問，這種假定我們要恢復(fù)的矩陣是低秩的，合理嗎？實(shí)際上是十分合理的，比如一個(gè)用戶對某電影評分是其他用戶對這部電影評分的線性組合。所以，通過低秩重構(gòu)就可以預(yù)測用戶對其未評價(jià)過的視頻的喜好程度。從而對矩陣進(jìn)行填充。

2）魯棒PCA：

? ? ? ?主成分分析，這種方法可以有效的找出數(shù)據(jù)中最“主要"的元素和結(jié)構(gòu)，去除噪音和冗余，將原有的復(fù)雜數(shù)據(jù)降維，揭示隱藏在復(fù)雜數(shù)據(jù)背后的簡單結(jié)構(gòu)。我們知道，最簡單的主成分分析方法就是PCA了。從線性代數(shù)的角度看，PCA的目標(biāo)就是使用另一組基去重新描述得到的數(shù)據(jù)空間。希望在這組新的基下，能盡量揭示原有的數(shù)據(jù)間的關(guān)系。這個(gè)維度即最重要的“主元"。PCA的目標(biāo)就是找到這樣的“主元”，最大程度的去除冗余和噪音的干擾。

? ? ? ?魯棒主成分分析（Robust PCA）考慮的是這樣一個(gè)問題：一般我們的數(shù)據(jù)矩陣X會包含結(jié)構(gòu)信息，也包含噪聲。那么我們可以將這個(gè)矩陣分解為兩個(gè)矩陣相加，一個(gè)是低秩的（由于內(nèi)部有一定的結(jié)構(gòu)信息，造成各行或列間是線性相關(guān)的），另一個(gè)是稀疏的（由于含有噪聲，而噪聲是稀疏的），則魯棒主成分分析可以寫成以下的優(yōu)化問題：

? ? ? ?與經(jīng)典PCA問題一樣，魯棒PCA本質(zhì)上也是尋找數(shù)據(jù)在低維空間上的最佳投影問題。對于低秩數(shù)據(jù)觀測矩陣X，假如X受到隨機(jī)（稀疏）噪聲的影響，則X的低秩性就會破壞，使X變成滿秩的。所以我們就需要將X分解成包含其真實(shí)結(jié)構(gòu)的低秩矩陣和稀疏噪聲矩陣之和。找到了低秩矩陣，實(shí)際上就找到了數(shù)據(jù)的本質(zhì)低維空間。那有了PCA，為什么還有這個(gè)Robust PCA呢？Robust在哪？因?yàn)镻CA假設(shè)我們的數(shù)據(jù)的噪聲是高斯的，對于大的噪聲或者嚴(yán)重的離群點(diǎn)，PCA會被它影響，導(dǎo)致無法正常工作。而Robust PCA則不存在這個(gè)假設(shè)。它只是假設(shè)它的噪聲是稀疏的，而不管噪聲的強(qiáng)弱如何。

? ? ? ?由于rank和L0范數(shù)在優(yōu)化上存在非凸和非光滑特性，所以我們一般將它轉(zhuǎn)換成求解以下一個(gè)松弛的凸優(yōu)化問題：

? ? ? ?說個(gè)應(yīng)用吧。考慮同一副人臉的多幅圖像，如果將每一副人臉圖像看成是一個(gè)行向量，并將這些向量組成一個(gè)矩陣的話，那么可以肯定，理論上，這個(gè)矩陣應(yīng)當(dāng)是低秩的。但是，由于在實(shí)際操作中，每幅圖像會受到一定程度的影響，例如遮擋，噪聲，光照變化，平移等。這些干擾因素的作用可以看做是一個(gè)噪聲矩陣的作用。所以我們可以把我們的同一個(gè)人臉的多個(gè)不同情況下的圖片各自拉長一列，然后擺成一個(gè)矩陣，對這個(gè)矩陣進(jìn)行低秩和稀疏的分解，就可以得到干凈的人臉圖像（低秩矩陣）和噪聲的矩陣了（稀疏矩陣），例如光照，遮擋等等。至于這個(gè)的用途，你懂得。

?

3）背景建模：

? ? ? ?背景建模的最簡單情形是從固定攝相機(jī)拍攝的視頻中分離背景和前景。我們將視頻圖像序列的每一幀圖像像素值拉成一個(gè)列向量，那么多個(gè)幀也就是多個(gè)列向量就組成了一個(gè)觀測矩陣。由于背景比較穩(wěn)定，圖像序列幀與幀之間具有極大的相似性，所以僅由背景像素組成的矩陣具有低秩特性；同時(shí)由于前景是移動的物體，占據(jù)像素比例較低，故前景像素組成的矩陣具有稀疏特性。視頻觀測矩陣就是這兩種特性矩陣的疊加，因此，可以說視頻背景建模實(shí)現(xiàn)的過程就是低秩矩陣恢復(fù)的過程。

?

4）變換不變低秩紋理（TILT）：

? ? ? ?以上章節(jié)所介紹的針對圖像的低秩逼近算法，僅僅考慮圖像樣本之間像素的相似性，卻沒有考慮到圖像作為二維的像素集合，其本身所具有的規(guī)律性。事實(shí)上，對于未加旋轉(zhuǎn)的圖像，由于圖像的對稱性與自相似性，我們可以將其看做是一個(gè)帶噪聲的低秩矩陣。當(dāng)圖像由端正發(fā)生旋轉(zhuǎn)時(shí)，圖像的對稱性和規(guī)律性就會被破壞，也就是說各行像素間的線性相關(guān)性被破壞，因此矩陣的秩就會增加。

? ? ? ?低秩紋理映射算法(TransformInvariant Low-rank Textures，TILT)是一種用低秩性與噪聲的稀疏性進(jìn)行低秩紋理恢復(fù)的算法。它的思想是通過幾何變換τ把D所代表的圖像區(qū)域校正成正則的區(qū)域，如具有橫平豎直、對稱等特性，這些特性可以通過低秩性來進(jìn)行刻畫。

? ? ? ?低秩的應(yīng)用非常多，大家有興趣的可以去找些資料深入了解下。

?

四、規(guī)則化參數(shù)的選擇

? ? ? ?現(xiàn)在我們回過頭來看看我們的目標(biāo)函數(shù)：

? ? ? ?里面除了loss和規(guī)則項(xiàng)兩塊外，還有一個(gè)參數(shù)λ。它也有個(gè)霸氣的名字，叫hyper-parameters（超參）。你不要看它勢單力薄的，它非常重要。它的取值很大時(shí)候會決定我們的模型的性能，事關(guān)模型生死。它主要是平衡loss和規(guī)則項(xiàng)這兩項(xiàng)的，λ越大，就表示規(guī)則項(xiàng)要比模型訓(xùn)練誤差更重要，也就是相比于要模型擬合我們的數(shù)據(jù)，我們更希望我們的模型能滿足我們約束的Ω(w)的特性。反之亦然。舉個(gè)極端情況，例如λ=0時(shí)，就沒有后面那一項(xiàng)，代價(jià)函數(shù)的最小化全部取決于第一項(xiàng)，也就是集全力使得輸出和期待輸出差別最小，那什么時(shí)候差別最小啊，當(dāng)然是我們的函數(shù)或者曲線可以經(jīng)過所有的點(diǎn)了，這時(shí)候誤差就接近0，也就是過擬合了。它可以復(fù)雜的代表或者記憶所有這些樣本，但對于一個(gè)新來的樣本泛化能力就不行了。畢竟新的樣本會和訓(xùn)練樣本有差別的嘛。

? ? ? ?那我們真正需要什么呢？我們希望我們的模型既可以擬合我們的數(shù)據(jù)，又具有我們約束它的特性。只有它們兩者的完美結(jié)合，才能讓我們的模型在我們的任務(wù)上發(fā)揮強(qiáng)大的性能。所以如何討好它，是非常重要。在這點(diǎn)上，大家可能深有體會。還記得你復(fù)現(xiàn)了很多論文，然后復(fù)現(xiàn)出來的代碼跑出來的準(zhǔn)確率沒有論文說的那么高，甚至還差之萬里。這時(shí)候，你就會懷疑，到底是論文的問題，還是你實(shí)現(xiàn)的問題？實(shí)際上，除了這兩個(gè)問題，我們還需要深入思考另一個(gè)問題：論文提出的模型是否具有hyper-parameters？論文給出了它們的實(shí)驗(yàn)取值了嗎？經(jīng)驗(yàn)取值還是經(jīng)過交叉驗(yàn)證的取值？這個(gè)問題是逃不掉的，因?yàn)閹缀跞魏我粋€(gè)問題或者模型都會具有hyper-parameters，只是有時(shí)候它是隱藏著的，你看不到而已，但一旦你發(fā)現(xiàn)了，證明你倆有緣，那請?jiān)囍バ薷南滤?#xff0c;有可能有“奇跡”發(fā)生哦。

? ? ? ?OK，回到問題本身。我們選擇參數(shù)λ的目標(biāo)是什么？我們希望模型的訓(xùn)練誤差和泛化能力都很強(qiáng)。這時(shí)候，你有可能還反映過來，這不是說我們的泛化性能是我們的參數(shù)λ的函數(shù)嗎？那我們?yōu)槭裁窗磧?yōu)化那一套，選擇能最大化泛化性能的λ呢？Oh，sorry to tell you that，因?yàn)榉夯阅懿⒉皇铅说暮唵蔚暮瘮?shù)！它具有很多的局部最大值！而且它的搜索空間很大。所以大家確定參數(shù)的時(shí)候，一是嘗試很多的經(jīng)驗(yàn)值，這和那些在這個(gè)領(lǐng)域摸爬打滾的大師是沒得比的。當(dāng)然了，對于某些模型，大師們也整理了些調(diào)參經(jīng)驗(yàn)給我們。例如Hinton大哥的那篇A Practical Guide to Training RestrictedBoltzmann Machines等等。還有一種方法是通過分析我們的模型來選擇。怎么做呢？就是在訓(xùn)練之前，我們大概計(jì)算下這時(shí)候的loss項(xiàng)的值是多少？Ω(w)的值是多少？然后針對他們的比例來確定我們的λ，這種啟發(fā)式的方法會縮小我們的搜索空間。另外一種最常見的方法就是交叉驗(yàn)證Cross validation了。先把我們的訓(xùn)練數(shù)據(jù)庫分成幾份，然后取一部分做訓(xùn)練集，一部分做測試集，然后選擇不同的λ用這個(gè)訓(xùn)練集來訓(xùn)練N個(gè)模型，然后用這個(gè)測試集來測試我們的模型，取N模型里面的測試誤差最小對應(yīng)的λ來作為我們最終的λ。如果我們的模型一次訓(xùn)練時(shí)間就很長了，那么很明顯在有限的時(shí)間內(nèi)，我們只能測試非常少的λ。例如假設(shè)我們的模型需要訓(xùn)練1天，這在深度學(xué)習(xí)里面是家常便飯了，然后我們有一個(gè)星期，那我們只能測試7個(gè)不同的λ。這就讓你遇到最好的λ那是上輩子積下來的福氣了。那有什么方法呢？兩種：一是盡量測試7個(gè)比較靠譜的λ，或者說λ的搜索空間我們盡量廣點(diǎn)，所以一般對λ的搜索空間的選擇一般就是2的多少次方了，從-10到10啊什么的。但這種方法還是不大靠譜，最好的方法還是盡量讓我們的模型訓(xùn)練的時(shí)間減少。例如假設(shè)我們優(yōu)化了我們的模型訓(xùn)練，使得我們的訓(xùn)練時(shí)間減少到2個(gè)小時(shí)。那么一個(gè)星期我們就可以對模型訓(xùn)練7*24/2=84次，也就是說，我們可以在84個(gè)λ里面尋找最好的λ。這讓你遇見最好的λ的概率就大多了吧。這就是為什么我們要選擇優(yōu)化也就是收斂速度快的算法，為什么要用GPU、多核、集群等來進(jìn)行模型訓(xùn)練、為什么具有強(qiáng)大計(jì)算機(jī)資源的工業(yè)界能做很多學(xué)術(shù)界也做不了的事情（當(dāng)然了，大數(shù)據(jù)也是一個(gè)原因）的原因了。

? ? ? ?努力做個(gè)“調(diào)參”高手吧！祝愿大家都能“調(diào)得一手好參”！

?

五、參考資料

[1]?http://fastml.com/large-scale-l1-feature-selection-with-vowpal-wabbit/

[2]?http://www.stat.purdue.edu/~vishy/introml/notes/Optimization.pdf

[3]?http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

[4]?GradientDescent, Wolfe's Condition and Logistic Regression

[5]?http://nm.mathforcollege.com/mws/gen/04sle/mws_gen_sle_spe_adequacy.pdf

總結(jié)

以上是生活随笔為你收集整理的机器学习中的范数规则化之（二）核范数与规则项参数选择的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。