低秩矩陣分解的正則化方法與應(yīng)用.pdf

1、在許多數(shù)據(jù)處理分析與應(yīng)用領(lǐng)域，比如高維數(shù)據(jù)的線性降維、計算機(jī)視覺領(lǐng)域中的三維場景重建、運動軌跡的分割，以及個性化商品推薦等，其核心問題都?xì)w結(jié)為矩陣低秩逼近問題的求解。在過去的幾年里，針對具體的應(yīng)用，出現(xiàn)了很多低秩矩陣分解模型。由于實際應(yīng)用中數(shù)據(jù)矩陣元素的大量缺損等因素，矩陣低秩逼近呈現(xiàn)很大的不適定性。因而，如何采取正則化來避免實際問題的不適定性并提供有效的數(shù)值算法，這是一個具有挑戰(zhàn)性的課題。此外，為了更好地利用數(shù)據(jù)信息，提高矩陣分解后的

2、應(yīng)用效果，采用合適的、有針對性的正則化方法，也是增強矩陣分解的實用性一個重要的手段。
　　 在協(xié)同過濾問題中，數(shù)據(jù)缺損的矩陣低秩分解模型可以提供很高的預(yù)測精度，并有很強的擴(kuò)展性。這是非常有效的技術(shù)，已經(jīng)受到很多學(xué)者的關(guān)注且取得了很大的應(yīng)用性進(jìn)展。但是該模型的效果以及相應(yīng)的算法性態(tài)嚴(yán)重地依賴低秩分解模型的正則化方式，并存在比較明顯的過度擬合現(xiàn)象。通常過度擬合會導(dǎo)致很差的結(jié)果。在計算機(jī)視覺相關(guān)的應(yīng)用中，數(shù)據(jù)缺損下的矩陣分解基本模型所

3、產(chǎn)生的最優(yōu)解還很有可能缺乏物理意義。在現(xiàn)有的文獻(xiàn)中，大部分的工作主要集中在針對現(xiàn)有的分解模型設(shè)計比較穩(wěn)定有效的算法。然而關(guān)于數(shù)據(jù)缺損下的矩陣低秩逼近的正則化問題討論的很少。雖然不少學(xué)者提出了圖正則化的矩陣分解模型，以保持?jǐn)?shù)據(jù)點之間的鄰近關(guān)系，提高矩陣分解的效果。但現(xiàn)有的圖正則化方式導(dǎo)致矩陣分解模型變成一個不容易求解的優(yōu)化問題，即使不考慮數(shù)據(jù)缺損的情況下也很難找到最優(yōu)解。在實際應(yīng)用中，比如協(xié)同過濾問題，矩陣低秩分解涉及的數(shù)據(jù)矩陣通常來說規(guī)

4、模都很大且極其稀疏。在此情形下，如何同時保證正則化技術(shù)具有有效性和易用性，是一個困難的問題。為了具有實際應(yīng)用價值，正則化方法也需要具有可擴(kuò)展性。
　　 本文比較系統(tǒng)地、完整地綜述了我們在矩陣低秩分解模型正則化及其算法設(shè)計方面的研究進(jìn)展。有效的正則化方式應(yīng)與具體應(yīng)用背景、問題的特點以及數(shù)據(jù)性質(zhì)相適應(yīng)。對于數(shù)據(jù)缺損問題，我們給出了現(xiàn)有基本模型問題的不適定性理論分析，并考慮了中等程度的數(shù)據(jù)缺損和高度元素缺損的矩陣低秩逼近情況。對于社會

5、化數(shù)據(jù)的降維表示問題，我們提出了一個新的圖正則化的矩陣分解模型。本文也同時介紹了相應(yīng)的快速有效的數(shù)值算法。在一些實際的大規(guī)模數(shù)值例子中，這些新的正則化算法均表現(xiàn)出比現(xiàn)有其它方法都好的數(shù)值特性。
　　 本文的主要貢獻(xiàn)如下：
　　 (1)我們分析了數(shù)據(jù)缺損下矩陣分解模型的不適定性(2.2節(jié))，指出：在一定條件下，基本模型可能存在多重最優(yōu)解，且兩個最優(yōu)解之間可以相差任意遠(yuǎn)。并給出兩類存在多個最優(yōu)解充分條件。對于一般情況，我們?yōu)?/p>

6、基本模型的∈-最優(yōu)解做了誤差分析，給出一個誤差下界。
　　 (2)我們提出引導(dǎo)正則項的思想(3.2節(jié))，用于解決極度數(shù)據(jù)缺損的大規(guī)模矩陣分解問題，并給出了兩個引導(dǎo)正則化模型：引導(dǎo)最小二乘算法(IALS)和引導(dǎo)隨機(jī)梯度下降算法(ISGD)。其中，引導(dǎo)最小二乘算法改善了用于原先的正則化模型的交替最小二乘算法的收斂性態(tài)；能夠同時保持對已觀測元素的逼近誤差和對未知元素的逼近誤差的單調(diào)下降性。與用于原先的正則化模型的隨機(jī)梯度下降算法相比，

7、引導(dǎo)隨機(jī)梯度下降算法能夠隨著矩陣秩的增大有效地提高逼近的準(zhǔn)確性。這兩個用于改進(jìn)模型的算法IALS和ISGD都能夠比原來的算法ALS和SGD達(dá)到更高的預(yù)測精度。
　　 (3)我們提出基于元素約束的正則化方法(4.2節(jié))，以解決中等程度的數(shù)據(jù)缺損的矩陣低秩分解問題。這個方法比較適合計算機(jī)視覺相關(guān)的問題，且恢復(fù)精度比較高。元素約束的范圍可以根據(jù)實際的應(yīng)用問題事先確定，或者用已經(jīng)觀測到的數(shù)據(jù)做出一個大致的估計。我們提出了用持續(xù)交替最小二

8、乘迭代算法(SALS)求解這個元素約束的矩陣分解模型，它可以在每步迭代中保持低秩分解因子交替優(yōu)化方法的快速性的同時，提升算法整體的收斂性和有效性。相比基本模型下的交替最小二乘算法和牛頓型算法，SALS算法在最優(yōu)解的準(zhǔn)確性和計算時間上都得到很大改進(jìn)。
　　 (4)提出一個新的圖正則化的矩陣低秩分解模型(5.1節(jié))，它用于處理包含社會化信息的數(shù)據(jù)，該模型存在一個全局最優(yōu)的解析解。依據(jù)矩陣列數(shù)的大小我們分別提出了直接法和用不精確內(nèi)迭代