2010 JMLR

0 摘要

????????使用凸松弛技術(shù)為大規(guī)模矩陣完成問題提供一系列正則化低秩解決方案。

論文算法 SOFT-IMPUTE 迭代地用從軟閾值 SVD 獲得的元素替換缺失的元素。通過熱啟動，這使算法能夠有效地計算正則化參數(shù)值網(wǎng)格上解決方案的整個正則化路徑。

1 introduction

表示觀測矩陣，最早的矩陣補(bǔ)全問題的優(yōu)化目標(biāo)函數(shù)為：

δ表示訓(xùn)練誤差的容忍程度（一個正則項參數(shù)）

?由于rank(Z)非凸，所以后續(xù)文獻(xiàn)對(1)進(jìn)行了一定的修改

?這里||Z||*表示核范數(shù)（是Z的奇異值的和）

用拉格朗日算子表達(dá)（3），有：

?

?????????在本文中，我們?yōu)楹朔稊?shù)正則化最小二乘問題 (3) 提出了一種SOFT-IMPUTE算法 ，該算法可擴(kuò)展到 m,n ≈的大型問題，其中觀察到的條目約為 或更多。 在每次迭代中，SOFT-IMPUTE 將目標(biāo)函數(shù)的值降低.

2 相關(guān)工作

? ? ? ? 最早期矩陣補(bǔ)全問題的目標(biāo)函數(shù)為

?????????也即相當(dāng)于（1）中δ=0。但是這種評判標(biāo)準(zhǔn)太過于嚴(yán)苛，同時會導(dǎo)致一定的過擬合，于是便有了（1）中的目標(biāo)函數(shù)

?????????在本文中，我們提供了一種 SOFT-IMPUTE算法，用于基于熱重啟的方式計算 (3) 的優(yōu)化目標(biāo)函數(shù)。

????????該算法的靈感來自 SVD-IMPUTE迭代算法，它使用“ 完整的”數(shù)據(jù)矩陣，在當(dāng)前 SVD中 補(bǔ)全缺失值。

? ? ? ? 這種迭代算法要求在每次迭代時計算密集矩陣（維度等于矩陣 X 的大小）的 SVD。這是這種迭代算法的瓶頸所在：無法進(jìn)行大規(guī)模計算。

? ? ? ? 本篇論文的算法 SOFT-IMPUTE 也需要在每次迭代時進(jìn)行 SVD 計算，但SOFT-IMPUTE 通過利用問題結(jié)構(gòu)，可以輕松處理非常大維度的矩陣。

????????在每次迭代中，非稀疏矩陣具有以下結(jié)構(gòu)： ? ? ? ?

? ? ? ? ?其中Ysp具有和觀測矩陣X一樣的稀疏結(jié)構(gòu)，有一個遠(yuǎn)小于觀測矩陣X 維度m和n的秩r' （算法收斂時，r'很接近于預(yù)測矩陣Z的秩）

?另一種使用協(xié)同過濾的方法使用矩陣分解，他被稱為MMMF（maximum margin matrix factorization methods）

????????事實證明，（6）與（3）密切相關(guān)。如果Z的秩 r′ = min(m,n)，則 (6) 的解與 (3) 的解一致。2 然而，(6) 在其自變量中不是凸的，而 (3) 是

3?SOFT-IMPUTE

3.1 符號說明

投影函數(shù)	如果有觀測值的地方就是Yij，沒有觀測值的地方就是0? ? ——>可以寫成
互補(bǔ)投影	?（Y有觀測值的部分，Y沒有觀測值的部分）

?3.2 核范數(shù)正則化

我們提出了以下引理，它構(gòu)成了我們算法的基本要素。

假設(shè)矩陣的秩是r，

那么

結(jié)果可以由?得到

?

?

UDV'是W的SVD分解?

d1,....,dr是D的對角元素

t+=max(t,0)

Sλ表示 soft-thresholding

使用3.1的表示，我們可以改寫（8）為

?

?3.3 算法

????????我們現(xiàn)在提出 SOFT-IMPUTE算法?——?用于計算 (10) 的一系列解決方案，用于使用暖啟動的不同 λ 值。

每過一段時間，λ縮小一點，這樣也能越來越精細(xì)

如何理解前面的(5)呢

3.4 和MMMF的關(guān)聯(lián)

論文的附錄部分證明了一個引理

?

?所以

?

4 收斂性分析

暫略?

5 計算復(fù)雜度

暫略

6 從軟閾值到硬閾值

????????我們認(rèn)為，在許多問題中，?1 正則化也可以提供更好的預(yù)測精度。（軟閾值）

???????? 但是，如果觀測模型非常稀疏，則具有均勻收縮的 LASSO范數(shù)（L1正則化） 既會高估模型中非零系數(shù)的數(shù)量，也會過度收縮（偏向）包括向零的系數(shù)

? ? ? ? 所以論文又提出了硬閾值的方法

? ? ? ? 這里表示Z的第j個奇異值

? ? ? ? 我們用矩陣的形式表示，可以寫成

?

? ? ? ? 這里

?和軟閾值時候類似，也可以用一個SVD 來解決上述優(yōu)化問題

對于每個特定的λ，有相應(yīng)的q=q(λ)個奇異值被保留

?

?6.1 硬閾值算法

和軟閾值類似，也是一個迭代算法

?這也就是這里提到的迭代算法

推薦系統(tǒng)筆記：基于SVD的協(xié)同過濾_UQI-LIUWJ的博客-CSDN博客_基于svd的協(xié)同過濾

總結(jié)

以上是生活随笔為你收集整理的论文笔记 Spectral Regularization Algorithms for Learning Large IncompleteMatrices （soft-impute）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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