基于低秩結(jié)構(gòu)學(xué)習(xí)數(shù)據(jù)表示.pdf

1、隨著計算機硬件及采樣技術(shù)的發(fā)展，海量高維數(shù)據(jù)的獲取也變得越來越容易，例如圖像與視頻數(shù)據(jù)、文本與網(wǎng)頁數(shù)據(jù)等。那些高維數(shù)據(jù)不但會顯著地增加計算和存儲代價，也使得推理、學(xué)習(xí)和識別等任務(wù)無法完成，并對傳統(tǒng)的機器學(xué)習(xí)與統(tǒng)計分析理論提出了嚴峻的挑戰(zhàn)，如維數(shù)災(zāi)難和小樣本問題等。如何獲取高維數(shù)據(jù)的低維表示并探索其內(nèi)在規(guī)律及本質(zhì)結(jié)構(gòu)，已成為機器學(xué)習(xí)、數(shù)據(jù)挖掘、模式識別、計算機視覺及統(tǒng)計分析等領(lǐng)域研究的熱點問題。
　　維數(shù)約簡可在很大程度上避免維數(shù)災(zāi)

2、難，使得學(xué)習(xí)任務(wù)(如分類或聚類等)更加穩(wěn)定和高效。然而很多經(jīng)典的維數(shù)約簡技術(shù)存在著一定的局限性，比如傳統(tǒng)譜聚類算法、低秩矩陣恢復(fù)與填充算法與非參數(shù)核學(xué)習(xí)算法的計算復(fù)雜度非常高，通常是樣本數(shù)n的立方或者O(n6.5)；傳統(tǒng)的非負矩陣分解沒有充分考慮數(shù)據(jù)與特征的幾何結(jié)構(gòu)，以及半監(jiān)督數(shù)據(jù)表示學(xué)習(xí)沒有利用核矩陣固有的低秩結(jié)構(gòu)信息等。因此，本論文以學(xué)習(xí)數(shù)據(jù)的有效表示為主題，通過挖掘數(shù)據(jù)本身固有的結(jié)構(gòu)如幾何結(jié)構(gòu)、稀疏與低秩結(jié)構(gòu)等信息來更有效地學(xué)習(xí)數(shù)

3、據(jù)的表示。另外，再加以利用可獲得的少量監(jiān)督信息如少量標簽數(shù)據(jù)或成對約束等來學(xué)習(xí)數(shù)據(jù)更有效的表示。從利用的信息由少到多，所取得的主要研究成果為：
　　1.提出了一種局部與全局一致性的兩階段譜聚類框架，可充分挖掘利用數(shù)據(jù)分布空間的拓撲幾何與低秩結(jié)構(gòu)來學(xué)習(xí)數(shù)據(jù)的有效表示。該框架主要包括兩個階段：第一階段是利用快速采樣算法獲得少量樣本代表點(簡稱代表點)；第二階段是由正交化的密度加權(quán)Nystrom低秩近似方法來得到全部數(shù)據(jù)的低維數(shù)據(jù)表示。

4、在此框架下，首先定義了局部和全局兩種距離測度方法，可準確地反映數(shù)據(jù)的幾何結(jié)構(gòu)；然后又提出了一種快速兩階段近鄰傳播采樣算法，可得到少量富含信息的代表點，該采樣算法是一種非均勻采樣的方式；最后給出了一種快速密度加權(quán)低秩近似譜聚類算法。該算法不但在聚類質(zhì)量、效率及內(nèi)存需求方面都超過了傳統(tǒng)的譜聚類與近鄰傳播方法，而且可處理較大規(guī)模數(shù)據(jù)的問題，學(xué)習(xí)獲得的數(shù)據(jù)表示可應(yīng)用于后面的章節(jié)。
　　2.提出了一種雙圖正則的非負矩陣分解框架，可充分利用數(shù)

5、據(jù)的流形與低秩結(jié)構(gòu)來學(xué)習(xí)非負數(shù)據(jù)的有效表示。該框架同時考慮了數(shù)據(jù)流形和特征流形的幾何結(jié)構(gòu)，并分別在數(shù)據(jù)空間和特征空間創(chuàng)建兩個近鄰圖來反映它們各自的幾何流形結(jié)構(gòu)。在此框架下，首先給出了一種雙圖正則非負矩陣分解模型，并推導(dǎo)了一種交替迭代更新規(guī)則；作為上述模型的拓展，然后又提出了一種雙圖正則非負矩陣三分解模型，并提供了一種交替迭代更新算法；最后分別提供了兩種算法的收斂性證明。大量的實驗結(jié)果表明提出的兩種算法比相關(guān)算法的聚類性能更好，并能學(xué)習(xí)得

6、到更有效的基于部分的數(shù)據(jù)表示。
　　3.提出了一種魯棒低秩矩陣分解框架，可充分利用數(shù)據(jù)的稀疏與低秩結(jié)構(gòu)恢復(fù)被幅值較大的噪聲或奇異點損壞的數(shù)據(jù)，而且還能填充丟失的數(shù)據(jù)。傳統(tǒng)的核范數(shù)最小化算法每次迭代都需要對較大規(guī)模的矩陣進行奇異值分解，故此它們具有很高的時間復(fù)雜度。為了克服上述算法的局限性，把矩陣分解的思想引入到傳統(tǒng)的核范數(shù)最小化模型中。再根據(jù)給定數(shù)據(jù)分布于單線性子空間或多子空間，分別給出了兩種不同的魯棒低秩矩陣分解模型。提出的兩種

7、優(yōu)化問題分別為核范數(shù)與l1或l2，1范數(shù)最小化的混合問題，又提供了一種基于交替方向法的迭代求解算法。最后再推廣到低秩矩陣填充問題，并給出了一種相應(yīng)的交替迭代求解算法。
　　4.提出了一種基于核矩陣元素分類的數(shù)據(jù)表示學(xué)習(xí)框架，可充分利用數(shù)據(jù)的幾何與低秩結(jié)構(gòu)及給定的少量成對約束信息。該框架以圖Laplacian的譜嵌入作為輔助，再利用成對約束信息去提升它得到新的數(shù)據(jù)表示。為了更準確地刻畫數(shù)據(jù)的幾何結(jié)構(gòu)，首先創(chuàng)建了一種對稱偏好近鄰圖。然

8、后基于平方損失函數(shù)，把學(xué)習(xí)數(shù)據(jù)表示的問題轉(zhuǎn)化為一個半正定二次線性規(guī)劃問題，可由常用的半正定規(guī)劃軟件包如SDPT3進行有效地求解。最后再把學(xué)習(xí)得到數(shù)據(jù)表示應(yīng)用于半監(jiān)督聚類及直推式分類問題。
　　5.提出了一種基于理想核矩陣填充學(xué)習(xí)數(shù)據(jù)表示的框架，可充分利用數(shù)據(jù)的幾何和低秩結(jié)構(gòu)及給定的少量成對約束信息。由于一般給定的成對約束的數(shù)目比精確重構(gòu)低秩核矩陣需要的采樣數(shù)目少很多，因此也考慮把圖Laplacian的譜嵌入作為輔助，進而把整個較大

9、規(guī)模核矩陣的求解轉(zhuǎn)化為一個較小規(guī)模的對稱半正定矩陣求解問題。上述的模型還是一個核范數(shù)正則最小二乘問題。然后又提出了一種特征值迭代閾值算法去有效地求解給出的優(yōu)化問題。最后還提供了該算法收斂于其最優(yōu)解的嚴格理論證明。
　　6.提出了一種基于復(fù)合信息的半監(jiān)督學(xué)習(xí)框架，可充分利用數(shù)據(jù)的幾何和低秩結(jié)構(gòu)及給定的少量數(shù)據(jù)標簽與成對約束信息。該框架不但能利用少量的樣本標簽與給定的成對約束信息，還能利用了大量的無標簽數(shù)據(jù)?；谏鲜龅目蚣?，給出了一種