在開始正文之前，咱首先得說明一下，這篇東西偏向於理論，各位看官可以自行跳過某些部分。這方面的工作奠基人同樣也是compressive sensing的大牛之一E.J Candes（Donoho的得意門生），以及Candes的學生Ben Recht，前者剛從caltech被挖到stanford，後者目前剛到wisconsin做AP。Candes大牛，stanford統計系出生，師從Donoho。Candes原來的主要工作集中在小波分析上（實際上C牛非常多產），比如著名的curvelets以及ridgelets，04年左右開始和Tao合作從事compressive sensing的理論工作，這裡有他的簡要介紹。繼續嘮叨，上回說到借著collaborative filtering的東風，矩陣的稀疏表示受到了廣泛的關注。說到矩陣的稀疏性，大部分看官可能有所誤解。這個矩陣稀疏表示嚴格而言可以分為兩種：1. 矩陣元素的稀疏性，即矩陣非0元個數相對較少。參照向量的範數，同樣可以定義矩陣的0範數，並將其鬆弛到矩陣的1範數的優化問題。2. 矩陣奇異值的稀疏性，即矩陣奇異值中非0元的個數（即矩陣的秩）相對較少。仿照向量情況下0範數與1範數的關係，同樣可以將其鬆弛的到跡範數（trace norm）的優化問題。咱下面會分別聊聊這兩個問題。首先，咱的出發點是machine learning中的collaborative filtering，這個概念並不是啥新東西了，最早大約可以追朔到1992的某篇同名文章。這玩意是做啥的呢，通俗的說，每次你在淘寶上閑逛的時候，下面都會有一行推薦商品。這些個網路服務商（淘寶，Amazon, Ebay）就在想了，如果這個推薦系統做的足夠好，那麼消費者（比如你我）的購物慾望就會得到刺激，這個銷量也就上去了。實際上，這和超市裡玲琅滿目的貨架是一個道理。這裡就得提提Netflix Prize這件事了，話說netflix是家在線dvd租賃公司，這公司就抱了同樣的想法。不過這家公司想了個主意：該公司提供數據，出資100萬美刀，獎勵研發這個推薦系統演算法的小組，並要求這些演算法發表在學術會議或期刊之上。這可以算是現實版的百萬富翁了（學術和money兩不誤），於是collaborative filtering著實火了一把（比如SIGKDD上的不少文章）。最終歷時兩年，由AT&T實驗室成員組成的BellKor』s Pragmatic Chaos贏得了這100萬刀。順到一提，國內也有不少傢伙參與了這個Prize，比如排名第二的Ensemble組裡就能看到中科院某所學生的身影。這個推薦系統咋做呢？我們先從簡單的模型開始。以netflix為例，netflix有個影評系統，在你租完DVD以後會讓你打分（1-5分）。當然不是所有人都會認真去打，實際上只有少數傢伙會給打分（這世界上懶人何其之多）。同樣，對每個用戶而言，他也只可能給部分看過的DVD打分。假設現在有
個用戶和
部電影，如果把所有評分列成一張大表，可以得到矩陣
。其中，每一行對應一個用戶的評分，每一列對應一部電影的用戶評價。可以想像，這個矩陣中只有少部分元素是已知的（圖1）。
從現有的用戶數據，來預測未知的用戶數據，這就是collaborative filtering了。那麼這個東西怎麼實現呢？解釋起來難，做起來容易，這個模型放在在topic model里叫做Probabilistic latent semantic analysis （PLSA），放在代數里叫做矩陣分解（Matrix Fatorization）或者矩陣填充（Matrix Completion），這裡就只能形象的解釋下。雖然用戶千奇百怪、電影成千上萬，但總可以歸結為若干類型：比如有腐女向、宅男向電影之分，再比如有悲劇也有喜劇。如果把這些latent factor畫成一個空間，那麼不同的用戶群體應當位於這個latent factor空間的不同位置，體現了不同用戶的喜好。如果可以把用戶喜好連同潛在的latent factor一同計算出來，預測也自然水到渠成了。從某種角度來看，奇異值分解過程也就是上述的剝離latent factor和用戶喜好的過程，這其中的philosophy可以參見這篇文章。咱首先要談的是矩陣奇異值的稀疏性，為此先來回憶下奇異值分解
。1. 奇異值非負，即
2. 奇異值非0元的個數即為矩陣
的秩（rank）如果把奇異值寫成對角矩陣
的形式（比如SVD分解的標準形式），其對角元為
。進一步，矩陣
的跡範數（trace norm）
定義為矩陣奇異值之和，即有
現在我們可以把collaborative filtering的基本問題回顧一下，給定一張推薦數據表
，已知其下標子集
中的元素（也就是有評分的部分），如何恢復這個矩陣？這就是matrix completion的問題了…乍眼一看，這基本就是mission impossible了，即使只有一個元素未知，這個矩陣也不可能唯一。但是如果我們加一些限制條件，這個問題就變得有趣起來了。Candes考慮的是這麼一個問題：
其中
表示在子集
上的投影（即只取子集上的對應元素）。實際上，同樣的問題可以有不同的表達形式，如果把這個優化問題稍作調整，可以得到相對容易解釋的模型：
其中Frobenius範數也就是矩陣的2範數。從這個式子來看，我們希望找到這麼一個矩陣
，使得其在已有的數據上和用戶評分
儘可能的一致（2範數意義下），同時具有比較低的秩（受到上限
的約束）。這裡對於秩的約束，很多時候是為了降低模型自身的複雜度（比如collaborative filtering，multiple instance learning）。當然，這裡也可以看成是一個fidelity term + regulariztion term的經典形式。實際上矩陣的rank是一個不那麼友好的函數，rank自身是非凸、不連續的，最後的結果就是對於rank的優化問題是NP難的。類比0範數與1範數的關係，矩陣
的秩（rank）相當於這個對角陣的0範數；矩陣
的跡範數（trace norm）
相當於這個對角矩陣的1範數。為此，如果這個對角矩陣足夠稀疏，即矩陣
的秩
，那麼可參照向量的稀疏表示，利用矩陣的跡範數(trace norm)代替矩陣的秩（rank）。
同樣，由於跡範數(trace norm)是凸的，上式是一個凸優化問題，故而必有唯一的最優解。如果這種近似是可以接受的，那麼這個問題自然也就解決了。這種近似靠譜么？這就是Candes和Recht回答的關鍵問題。Candes從random orthogonal model出發，證明了在此假設下從某個秩為
的真實矩陣
中均勻抽取
個元素，且滿足(這裡不妨設
，反之只需要轉置即可)
則凸優化問題的唯一最優解
至少以概率
逼近原始矩陣
，即有
其中
均為某常數。更進一步，如果矩陣的秩
足夠小，對於元素數量
的要求會進一步降低。咱來聊聊這個結果，這說明在random orthogonal model假設成立的條件下，如果
相對於
比較小，那麼只需要知道這個矩陣中約
個元素，就可以很高的概率恢復出這個矩陣。舉例而言，如果我們有一個
秩為10的矩陣，那我們大致只需要從中隨機抽取約270萬個元素就可以（以很高概率）恢復出原始矩陣了(當然270萬貌似也是一個很大的數，但原始矩陣約含有1700萬個元素…）。實際上，這是一個相對保守的界，Recht在此基礎上還進行了一系列的理論工作。自從出現了這個之後，under mild condition，大家都把rank直接放成trace norm了…從實用的角度來說，Candes告訴我們用凸優化去近似一個NP問題，可能得到很好的解。從實驗結果來看（代碼見此），這種近似有時候效果一流，但有時候也根本不work（違背了假設條件），故而具體問題還得具體對待。雖然早在04年NIPS上，就有人提出了類似的優化方法（MMMF），用trace norm代替rank，並且ML領域中也確實有不少類似的工作。但是，Candes的工作解決了根本的理論問題，並為一系列的rank minimization的問題指了一條出路。這裡有一個比較有意思的地方是，MMMF是從構造最大間隔線性分類器的角度出發來考慮matrix factorization的問題，並且用的是low norm，但和matrix completion的模型本質上是差不多的，兩者關係大家可以自行推導下。咱接著要討論的是矩陣元素的稀疏性，這個工作也和Candes有著很大的關係。咱先把上面的公式照著copy一遍：
如果咱已知矩陣
的全部元素，這個東西類似很常見的PCA了：
這樣問題就變成了去噪+降維。進一步把F範數（2範數）改寫為0範數：
為啥是0範數呢，這是基於這麼一種假設：誤差相對於總體樣本而言總是稀疏的。於是，我們可以引入輔助變數表示誤差
，並把上式稍作改寫：
這裡的
用於平衡矩陣的秩和誤差的稀疏性。同樣，rank和0範數什麼的都是相當討厭的東西，於是咱鬆弛一下，就有
這就是Robust Principle Component Analysis (RPCA) 或者Principle Component Pursuit 的核心模型了。這幅圖很好的說明了RPCA和PCA的區別（轉自Yi Ma主頁）。
PCARPCA說起RPCA，這裡岔開兩句，這個東西原來是Yi Ma的學生John Wright發在NIPS09上的一篇文章。結果接收之後，被Candes指出了一個bug（審稿人沒看出來），於是Candes對這個問題進行了考慮，從而就有了一篇叫做《Robust Principal Component Analysis?》的文章（preprint）。Candes證明了在同matrix completion基本相同的假設下，這種近似以很高的概率恢復精確結果（詳細結果可見RPCA的論文）。特別的，此時可以簡單選擇參數
。Matrix Completion（MC）和 RPCA在Yi Ma的主頁上有一個簡單的介紹，上面列舉了相關文獻與代碼的鏈接。MC和RPCA在computer vision上有啥用呢？John Wright在NIPS的文章里做了兩個實驗：背景建模，人臉陰影去除。大家有興趣可以查查cvpr 10的paper, 有用MC來做video denoising的，有用RPCA來做人臉對齊的…還有那篇best paper也是緊密相關。咱本來還想聊聊這些模型的優化演算法，鑒於篇幅所限，就只能留到（下）篇去了。最後，下期預告：優化方法，模型變種，張量推廣…其實最關鍵的老天保佑咱有時間寫….
推薦閱讀：
