轉自：http://blog.csdn.net/zouxy09/article/details/24972869
三、核範數
核範數||W||*是指矩陣奇異值的和，英文稱呼叫Nuclear Norm。這個相對于上面火熱的L1和L2來說，可能大家就會陌生點。那它是幹嘛用的呢？霸氣登場：限制Low-Rank（低秩）。OK，OK，那我們得知道Low-Rank是啥？用來幹啥的？
我們先來回憶下線性代數裡面“秩”到底是啥？舉個簡單的例子吧：
對上面的線性方程組，第一個方程和第二個方程有不同的解，而第2個方程和第3個方程的解完全相同。從這個意義上說，第3個方程是“多餘”的，因為它沒有帶來任何的資訊量，把它去掉，所得的方程組與原來的方程組同解。為了從方程組中去掉多餘的方程，自然就導出了“矩陣的秩”這一概念。
還記得我們怎麼手工求矩陣的秩嗎？為了求矩陣A的秩，我們是通過矩陣初等變換把A化為階梯型矩陣，若該階梯型矩陣有r個非零行，那A的秩rank(A)就等于r。從實體意義上講，矩陣的秩度量的就是矩陣的行列之間的相關性。如果矩陣的各行或列是線性無關的，矩陣就是滿秩的，也就是秩等于行數。回到上面線性方程組來說吧，因為線性方程組可以用矩陣描述嘛。秩就表示了有多少個有用的方程了。上面的方程組有3個方程，實際上隻有2個是有用的，一個是多餘的，是以對應的矩陣的秩就是2了。
OK。既然秩可以度量相關性，而矩陣的相關性實際上有帶有了矩陣的結構資訊。如果矩陣之間各行的相關性很強，那麼就表示這個矩陣實際可以投影到更低維的線性子空間，也就是用幾個向量就可以完全表達了，它就是低秩的。是以我們總結的一點就是：如果矩陣表達的是結構性資訊，例如圖像、使用者-推薦表等等，那麼這個矩陣各行之間存在這一定的相關性，那這個矩陣一般就是低秩的。
如果X是一個m行n列的數值矩陣，rank(X)是X的秩，假如rank (X)遠小于m和n，則我們稱X是低秩矩陣。低秩矩陣每行或每列都可以用其他的行或列線性表出，可見它包含大量的備援資訊。利用這種備援資訊，可以對缺失資料進行恢複，也可以對資料進行特征提取。
好了，低秩有了，那限制低秩隻是限制rank(w)呀，和我們這節的核範數有什麼關系呢？他們的關系和L0與L1的關系一樣。因為rank()是非凸的，在優化問題裡面很難求解，那麼就需要尋找它的凸近似來近似它了。對，你沒猜錯，rank(w)的凸近似就是核範數||W||*。
好了，到這裡，我也沒什麼好說的了，因為我也是稍微翻看了下這個東西，是以也還沒有深入去看它。但我發現了這玩意還有很多很有意思的應用，下面我們舉幾個典型的吧。
1）矩陣填充(Matrix Completion)：
我們首先說說矩陣填充用在哪。一個主流的應用是在推薦系統裡面。我們知道，推薦系統有一種方法是通過分析使用者的曆史記錄來給使用者推薦的。例如我們在看一部電影的時候，如果喜歡看，就會給它打個分，例如3顆星。然後系統，例如Netflix等知名網站就會分析這些資料，看看到底每部影片的題材到底是怎樣的？針對每個人，喜歡怎樣的電影，然後會給對應的使用者推薦相似題材的電影。但有一個問題是：我們的網站上面有非常多的使用者，也有非常多的影片，不是所有的使用者都看過說有的電影，不是所有看過某電影的使用者都會給它評分。假設我們用一個“使用者-影片”的矩陣來描述這些記錄，例如下圖，可以看到，會有很多空白的地方。如果這些空白的地方存在，我們是很難對這個矩陣進行分析的，是以在分析之前，一般需要先對其進行補全。也叫矩陣填充。
那到底怎麼填呢？如何才能無中生有呢？每個空白的地方的資訊是否蘊含在其他已有的資訊之上了呢？如果有，怎麼提取出來呢？Yeah，這就是低秩生效的地方了。這叫低秩矩陣重構問題，它可以用如下的模型表述：已知資料是一個給定的m*n矩陣A，如果其中一些元素因為某種原因丢失了，我們能否根據其他行和列的元素，将這些元素恢複？當然，如果沒有其他的參考條件，想要确定這些資料很困難。但如果我們已知A的秩rank(A)<<m且rank(A)<<n，那麼我們可以通過矩陣各行(列)之間的線性相關将丢失的元素求出。你會問，這種假定我們要恢複的矩陣是低秩的，合理嗎？實際上是十分合理的，比如一個使用者對某電影評分是其他使用者對這部電影評分的線性組合。是以，通過低秩重構就可以預測使用者對其未評價過的視訊的喜好程度。進而對矩陣進行填充。
2）魯棒PCA：
主成分分析，這種方法可以有效的找出資料中最“主要"的元素和結構，去除噪音和備援，将原有的複雜資料降維，揭示隐藏在複雜資料背後的簡單結構。我們知道，最簡單的主成分分析方法就是PCA了。從線性代數的角度看，PCA的目标就是使用另一組基去重新描述得到的資料空間。希望在這組新的基下，能盡量揭示原有的資料間的關系。這個次元即最重要的“主元"。PCA的目标就是找到這樣的“主元”，最大程度的去除備援和噪音的幹擾。
魯棒主成分分析（Robust PCA）考慮的是這樣一個問題：一般我們的資料矩陣X會包含結構資訊，也包含噪聲。那麼我們可以将這個矩陣分解為兩個矩陣相加，一個是低秩的（由于内部有一定的結構資訊，造成各行或列間是線性相關的），另一個是稀疏的（由于含有噪聲，而噪聲是稀疏的），則魯棒主成分分析可以寫成以下的優化問題：
與經典PCA問題一樣，魯棒PCA本質上也是尋找資料在低維空間上的最佳投影問題。對于低秩資料觀測矩陣X，假如X受到随機（稀疏）噪聲的影響，則X的低秩性就會破壞，使X變成滿秩的。是以我們就需要将X分解成包含其真實結構的低秩矩陣和稀疏噪聲矩陣之和。找到了低秩矩陣，實際上就找到了資料的本質低維空間。那有了PCA，為什麼還有這個Robust PCA呢？Robust在哪？因為PCA假設我們的資料的噪聲是高斯的，對于大的噪聲或者嚴重的離群點，PCA會被它影響，導緻無法正常工作。而Robust PCA則不存在這個假設。它隻是假設它的噪聲是稀疏的，而不管噪聲的強弱如何。
由于rank和L0範數在優化上存在非凸和非光滑特性，是以我們一般将它轉換成求解以下一個松弛的凸優化問題：
說個應用吧。考慮同一副人臉的多幅圖像，如果将每一副人臉圖像看成是一個行向量，并将這些向量組成一個矩陣的話，那麼可以肯定，理論上，這個矩陣應當是低秩的。但是，由于在實際操作中，每幅圖像會受到一定程度的影響，例如遮擋，噪聲，光照變化，平移等。這些幹擾因素的作用可以看做是一個噪聲矩陣的作用。是以我們可以把我們的同一個人臉的多個不同情況下的圖檔各自拉長一列，然後擺成一個矩陣，對這個矩陣進行低秩和稀疏的分解，就可以得到幹淨的人臉圖像（低秩矩陣）和噪聲的矩陣了（稀疏矩陣），例如光照，遮擋等等。至于這個的用途，你懂得。
3）背景模組化：
背景模組化的最簡單情形是從固定攝相機拍攝的視訊中分離背景和前景。我們将視訊圖像序列的每一幀圖像像素值拉成一個列向量，那麼多個幀也就是多個列向量就組成了一個觀測矩陣。由于背景比較穩定，圖像序列幀與幀之間具有極大的相似性，是以僅由背景像素組成的矩陣具有低秩特性；同時由于前景是移動的物體，占據像素比例較低，故前景像素組成的矩陣具有稀疏特性。視訊觀測矩陣就是這兩種特性矩陣的疊加，是以，可以說視訊背景模組化實作的過程就是低秩矩陣恢複的過程。
4）變換不變低秩紋理（TILT）：
以上章節所介紹的針對圖像的低秩逼近算法，僅僅考慮圖像樣本之間像素的相似性，卻沒有考慮到圖像作為二維的像素集合，其本身所具有的規律性。事實上，對于未加旋轉的圖像，由于圖像的對稱性與自相似性，我們可以将其看做是一個帶噪聲的低秩矩陣。當圖像由端正發生旋轉時，圖像的對稱性和規律性就會被破壞，也就是說各行像素間的線性相關性被破壞，是以矩陣的秩就會增加。
低秩紋理映射算法(TransformInvariant Low-rank Textures，TILT)是一種用低秩性與噪聲的稀疏性進行低秩紋理恢複的算法。它的思想是通過幾何變換τ把D所代表的圖像區域校正成正則的區域，如具有橫平豎直、對稱等特性，這些特性可以通過低秩性來進行刻畫。
低秩的應用非常多，大家有興趣的可以去找些資料深入了解下。
四、規則化參數的選擇
現在我們回過頭來看看我們的目标函數：
裡面除了loss和規則項兩塊外，還有一個參數λ。它也有個霸氣的名字，叫hyper-parameters（超參）。你不要看它勢單力薄的，它非常重要。它的取值很大時候會決定我們的模型的性能，事關模型生死。它主要是平衡loss和規則項這兩項的，λ越大，就表示規則項要比模型訓練誤差更重要，也就是相比于要模型拟合我們的資料，我們更希望我們的模型能滿足我們限制的Ω(w)的特性。反之亦然。舉個極端情況，例如λ=0時，就沒有後面那一項，代價函數的最小化全部取決于第一項，也就是集全力使得輸出和期待輸出差别最小，那什麼時候差别最小啊，當然是我們的函數或者曲線可以經過所有的點了，這時候誤差就接近0，也就是過拟合了。它可以複雜的代表或者記憶所有這些樣本，但對于一個新來的樣本泛化能力就不行了。畢竟新的樣本會和訓練樣本有差别的嘛。
那我們真正需要什麼呢？我們希望我們的模型既可以拟合我們的資料，又具有我們限制它的特性。隻有它們兩者的完美結合，才能讓我們的模型在我們的任務上發揮強大的性能。是以如何讨好它，是非常重要。在這點上，大家可能深有體會。還記得你複現了很多論文，然後複現出來的代碼跑出來的準确率沒有論文說的那麼高，甚至還差之萬裡。這時候，你就會懷疑，到底是論文的問題，還是你實作的問題？實際上，除了這兩個問題，我們還需要深入思考另一個問題：論文提出的模型是否具有hyper-parameters？論文給出了它們的實驗取值了嗎？經驗取值還是經過交叉驗證的取值？這個問題是逃不掉的，因為幾乎任何一個問題或者模型都會具有hyper-parameters，隻是有時候它是隐藏着的，你看不到而已，但一旦你發現了，證明你倆有緣，那請試着去修改下它吧，有可能有“奇迹”發生哦。
OK，回到問題本身。我們選擇參數λ的目标是什麼？我們希望模型的訓練誤差和泛化能力都很強。這時候，你有可能還反映過來，這不是說我們的泛化性能是我們的參數λ的函數嗎？那我們為什麼按優化那一套，選擇能最大化泛化性能的λ呢？Oh，sorry to tell you that，因為泛化性能并不是λ的簡單的函數！它具有很多的局部最大值！而且它的搜尋空間很大。是以大家确定參數的時候，一是嘗試很多的經驗值，這和那些在這個領域摸爬打滾的大師是沒得比的。當然了，對于某些模型，大師們也整理了些調參經驗給我們。例如Hinton大哥的那篇A Practical Guide to Training RestrictedBoltzmann Machines等等。還有一種方法是通過分析我們的模型來選擇。怎麼做呢？就是在訓練之前，我們大概計算下這時候的loss項的值是多少？Ω(w)的值是多少？然後針對他們的比例來确定我們的λ，這種啟發式的方法會縮小我們的搜尋空間。另外一種最常見的方法就是交叉驗證Cross validation了。先把我們的訓練資料庫分成幾份，然後取一部分做訓練集，一部分做測試集，然後選擇不同的λ用這個訓練集來訓練N個模型，然後用這個測試集來測試我們的模型，取N模型裡面的測試誤差最小對應的λ來作為我們最終的λ。如果我們的模型一次訓練時間就很長了，那麼很明顯在有限的時間内，我們隻能測試非常少的λ。例如假設我們的模型需要訓練1天，這在深度學習裡面是家常便飯了，然後我們有一個星期，那我們隻能測試7個不同的λ。這就讓你遇到最好的λ那是上輩子積下來的福氣了。那有什麼方法呢？兩種：一是盡量測試7個比較靠譜的λ，或者說λ的搜尋空間我們盡量廣點，是以一般對λ的搜尋空間的選擇一般就是2的多少次方了，從-10到10啊什麼的。但這種方法還是不大靠譜，最好的方法還是盡量讓我們的模型訓練的時間減少。例如假設我們優化了我們的模型訓練，使得我們的訓練時間減少到2個小時。那麼一個星期我們就可以對模型訓練7*24/2=84次，也就是說，我們可以在84個λ裡面尋找最好的λ。這讓你遇見最好的λ的機率就大多了吧。這就是為什麼我們要選擇優化也就是收斂速度快的算法，為什麼要用GPU、多核、叢集等來進行模型訓練、為什麼具有強大計算機資源的工業界能做很多學術界也做不了的事情（當然了，大資料也是一個原因）的原因了。
努力做個“調參”高手吧！祝願大家都能“調得一手好參”！
五、參考資料
[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