• 熱門專題

研究領域總結(二):稀疏矩陣補全

作者:aezero  發布日期:2015-10-08 21:12:48
Tag標簽:研究領域  矩陣  
  • I.定義

      矩陣補全(Matrix Completion)是指如下一個問題: 有一個巨大的矩陣$X\in\mathbb{R}^{m\times n}$,然而人們只能觀測到其中的部分元素。記觀測到的矩陣為矩陣$M\in\mathbb{R}^{m\times n}$(沒觀測到的元素位置以$0$填充),則$P_\Omega(X)=P_\Omega(M)$,其中觀測到的元素下標集合記為$\Omega$,$P_\Omega$表示投影到$\Omega$。

      為了說明它的意義,這里舉一個最常見的情形,即評分預測/推薦系統——協同過濾,如豆瓣之類的網站,會有很多用戶(看作行)對很多電影(看作列)進行打分(矩陣元素的值),每個用戶只會對很少的電影打分,這就導致我們的打分矩陣是一個部分觀測到的矩陣,而往往我們想預測出來用戶對沒有打分的電影的評分,依次來推薦或挖掘等等。同時注意到行數和列數往往非常非常大(>百萬級別),并且矩陣的稀疏度可能很高很高(<0.x%)。

      顯然這個問題是個不適定問題,想要補全整個矩陣,我們需要一些額外的約束,最常見的就是假設這個矩陣是低秩的,一方面這符合我們對自然界的觀測,另一方面可以用“物以類聚,人以群分”的一致性來做直覺解釋。考慮觀測有噪聲的情況,則整個問題可以形式化為:

    \[ \min_{X}\|P_\Omega(X-M)\|_F^2 \quad s.t. rank(X)\leq k. \]

    II.求解:化歸到稀疏問題 

      rank是個很難搞的東西,而且把整個問題變成非凸的了。把$X$的奇異值表示成向量形式$\sigma$,那么根據SVD分解的性質,$rank(X)\leq k$等價于 $\|\sigma\|_0\leq k$。這樣,就化歸到了稀疏問題上來,可以用壓縮感知、稀疏編碼的思路來思考,只不過目標從向量拓展到了矩陣。

       1.松弛到凸問題。

      類似壓縮感知,我們也可以把$\|\sigma\|_0$松弛到$\|\sigma\|_1$,這樣就變成了凸問題。同時,松弛到$\|\sigma\|_1$即矩陣的Nuclear norm  \|X\|_*,問題化為:

    \[ \min_{X}\|P_\Omega(X-M)\|_F^2 +\lambda \|X\|_* \]

      關于這個問題,有很多解法,大部分都是從稀疏里變換過來的,如收縮算子、ADMM等等。

      Candes證明了矩陣補全和壓縮感知一樣,在滿足矩陣size和采樣率(觀測稀疏度)要求下,有exact recovery的bound(事實上,矩陣補全的坑就是Candes挖的)。有興趣的可以讀一下他的paper:  E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math.9 717-772

      2.非凸解法。

      同樣的,雖然松弛到凸問題有最優解,有bound guarantee,但是論起實際效果往往非凸的一些解法更準確更快速。這部分我做的比較多。主要兩類:

  • 類似OMP,可以用貪心方法選基,每次選一個rank one的矩陣,然后更新系數,選k個即能保證矩陣秩小于等于k。注意到一個重要的區別是稀疏里有個字典,也即從一組冗余基里選,而矩陣補全沒有這樣一個字典,可以從無限個數的基里選,可以用top SVD 或者其它子目標問題求解得到。 非凸懲罰項,比如MCP。

    III.協同過濾、去噪      

      工業界的推薦系統最主要的兩個思路就是基于內容和協同過濾兩種。協同過濾更standard的是用矩陣分解來做(個人認為主要還是矩陣分解比補全出來的早,搶占了市場),矩陣分解根據一篇paper的定理(一時忘記出處了),其實是和Nuclear norm約束等價的。期待矩陣補全在實際中的更多應用。此外,矩陣補全也可以用來做圖像去噪。

延伸閱讀:

About IT165 - 廣告服務 - 隱私聲明 - 版權申明 - 免責條款 - 網站地圖 - 網友投稿 - 聯系方式
本站內容來自于互聯網,僅供用于網絡技術學習,學習中請遵循相關法律法規
香港最快开奖现场直播结果