基于低秩矩陣估計(jì)的機(jī)器學(xué)習(xí)算法分析.pdf

1、在例如推薦系統(tǒng)，圖像/視頻分析等許多機(jī)器學(xué)習(xí)問題中，數(shù)據(jù)往往是以矩陣的形式進(jìn)行表達(dá)。在這些問題中，矩陣的低秩性質(zhì)在學(xué)習(xí)原始數(shù)據(jù)隱藏結(jié)構(gòu)的過程中有著非常重要的作用。因此，近來針對低秩矩陣算法成為機(jī)器學(xué)習(xí)和相關(guān)領(lǐng)域的一個(gè)研究熱點(diǎn)。低秩近似算法大致上可以被分為兩類:(1)恢復(fù)數(shù)據(jù)（很可能是不完整的）中的低秩結(jié)構(gòu);(2)利用低秩信息提升其他機(jī)器學(xué)習(xí)模型的學(xué)習(xí)效果。雖然在這兩類算法中目前已經(jīng)有很多相關(guān)工作，但是不管從準(zhǔn)確性還是效率來看，已有的算法

2、都并不能達(dá)到讓人滿意的效果。在本論文中，我們從算法理論分析到具體的應(yīng)用對低秩近似算法進(jìn)行了一個(gè)系統(tǒng)的研究，研究內(nèi)容包括矩陣補(bǔ)全問題，主動(dòng)學(xué)習(xí)和基于低秩矩陣正則化的大規(guī)模圖像分類問題。總的來說，本文的創(chuàng)新點(diǎn)如下:
　　1.為了加速針對大規(guī)模矩陣補(bǔ)全問題的奇異值截?cái)嗍剿惴?Singular Value Thresholding，SVT)，在本論文中我們提出了一種奇異值截?cái)嗍郊铀偎惴?Accelerated Singular Value

3、Thresholding，ASVT)將傳統(tǒng)的SVT算法的收斂速度從O（1/N）提升至O（1/N2），其中N是優(yōu)化過程中的迭代次數(shù)。具體而言，通過理論分析我們證明了原始優(yōu)化問題的最優(yōu)解可以通過其對偶問題的最優(yōu)解直接得到。我們在人工數(shù)據(jù)集，真實(shí)距離矩陣數(shù)據(jù)集和電影推薦數(shù)據(jù)集上進(jìn)行一系列的驗(yàn)證，實(shí)驗(yàn)結(jié)果證明了我們所提出算法的效率和有效性。
　　2.為了更好地解決基于截?cái)嗍胶朔稊?shù)的矩陣補(bǔ)全問題，本論文首先對原始截?cái)嗍胶朔稊?shù)優(yōu)化問題進(jìn)行重構(gòu)

4、。原始優(yōu)化問題中的多個(gè)限制條件會(huì)減緩基于乘子的交替方向理論(Alternating Direction Method of Multipliers，ADMM)的收斂速度，并會(huì)對解的準(zhǔn)確性造成一定的影響。隨后，我們對重構(gòu)后的問題提出了一個(gè)帶自適應(yīng)懲罰項(xiàng)的ADMM算法(Alternating Direction Method of Multipliers with Adaptive Penalty，ADMMAP)。在每一次迭代中，我們根據(jù)一

5、個(gè)迭代機(jī)制調(diào)整目標(biāo)函數(shù)中的懲罰項(xiàng)大小，從而加速算法收斂速度。我們在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)分析證明了，同已有的矩陣補(bǔ)全算法相比，我們提出的算法具有更好的效果。
　　3.為了更好地在數(shù)據(jù)集中選擇最具代表性的樣本（我們稱之為錨點(diǎn)），本論文提出在錨點(diǎn)的選擇過程中充分考慮數(shù)據(jù)的局部信息，并設(shè)計(jì)了一種基于近鄰重建的主動(dòng)學(xué)習(xí)方法(Active Learning via Neighborhood Reconstruction，ALNR)。傳

6、統(tǒng)基于重建的主動(dòng)學(xué)習(xí)理論利用所有的錨點(diǎn)對目標(biāo)數(shù)據(jù)進(jìn)行重建。然而，離目標(biāo)數(shù)據(jù)越近的錨點(diǎn)對數(shù)據(jù)重建的作用越大，而離目標(biāo)數(shù)據(jù)較遠(yuǎn)的點(diǎn)對數(shù)據(jù)重建的作用較小甚至有負(fù)面的作用。因此，在我們提出的ALNR算法中，我們僅僅只使用目標(biāo)數(shù)據(jù)的近鄰錨點(diǎn)對目標(biāo)數(shù)據(jù)進(jìn)行重建。為更好地求解最終的優(yōu)化問題，我們提出了一種高效的兩步迭代機(jī)制。我們在人工和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)效果證明了我們算法比已有的主動(dòng)學(xué)習(xí)算法更加準(zhǔn)確高效。
　　4.為了更好地在圖像分類問題中利用

7、矩陣的低秩信息，本論文考慮當(dāng)分類器系數(shù)空間存在低維結(jié)構(gòu)時(shí)的圖像分類問題。當(dāng)前已有的算法往往利用矩陣的核范數(shù)來刻畫分類器系數(shù)矩陣的低秩結(jié)構(gòu)。然而，考慮核范數(shù)并不能對矩陣秩算子進(jìn)行很好地近似，我們提出了一種基于截?cái)嗍胶朔稊?shù)的大規(guī)模圖像分類算法。為了求解最終非凸非光滑的優(yōu)化問題，我們設(shè)計(jì)了一個(gè)高效的算法將原始問題首先分解為多個(gè)非光滑凸子問題，并進(jìn)行迭代優(yōu)化求解。在每一次迭代中，我們將每一個(gè)子問題轉(zhuǎn)化為一個(gè)無線維空間下的l1范數(shù)正則化問題，并使