大規(guī)模機(jī)器學(xué)習(xí)：矩陣低秩近似與在線學(xué)習(xí).pdf

1、在本文我們將探討兩種適合大規(guī)模計(jì)算的框架——矩陣的低秩近似和在線學(xué)習(xí)——來解決機(jī)器學(xué)習(xí)中的兩個重要問題：非監(jiān)督學(xué)習(xí)與監(jiān)督學(xué)習(xí)。對大規(guī)模矩陣進(jìn)行特征值分解是在非監(jiān)督學(xué)習(xí)中最經(jīng)常遇到的問題，例如核主成分分析，譜聚類。但是其三次方的算法復(fù)雜度阻礙了其在大規(guī)模數(shù)據(jù)集上的應(yīng)用。另一方面，支持向量機(jī)是在監(jiān)督學(xué)習(xí)中是最常用的方法。在大規(guī)模數(shù)據(jù)集中，稀疏性規(guī)約通常用來保證模型不會過擬合。然而，稀疏性規(guī)約的加入則使得優(yōu)化算法異常復(fù)雜。
　　Nyst

2、rm方法是一個有效的對大規(guī)模核矩陣進(jìn)行特征值分解的手段。但是，為了保證足夠的的近似精度，Nystr?m方法需要從核矩陣中采樣足夠多的列。而在大數(shù)據(jù)集上，作用在采樣的子矩陣上的SVD算法會很快凸顯出耗時的缺點(diǎn)，以致于嚴(yán)重到影響Nystr?m方法的效率。在這篇文章里，我們通過使用一個近似的奇異值分解算法來對Nystr?m方法進(jìn)行改進(jìn)，使其可以被高效地應(yīng)用在超大規(guī)模的數(shù)據(jù)集上。理論分析表明該改進(jìn)后的算法和標(biāo)準(zhǔn)的Nystr?m方法一樣精確。一系

3、列在大規(guī)模數(shù)據(jù)集上的測試驗(yàn)證了該算法的以上特性。此外，我們還將其從在CPU上運(yùn)行擴(kuò)展到了在GPU上運(yùn)行，從而使得8百萬×8百萬的核矩陣可以在1分鐘之內(nèi)被很好的近似。
　　Nystr?m方法的一個重要應(yīng)用是在譜聚類上。然而，當(dāng)數(shù)據(jù)量足夠大時，譜聚類處理和存儲采樣列的代價仍然非常昂貴。在這篇文章里，我們提出了一個在時間和空間上同時高效的算法，使得譜聚類可以被應(yīng)用在超大規(guī)模數(shù)據(jù)集上。同時被提出的還有一個一般化的正交化方法，該方法用于正交

4、化近似得到的特征向量。我們對大量的規(guī)模從數(shù)萬到數(shù)百萬的數(shù)據(jù)集，進(jìn)行了譜聚類實(shí)驗(yàn)，來測試并驗(yàn)證了該算法的準(zhǔn)確和高效。更進(jìn)一步，我們將其應(yīng)用到圖片分割上。該算法可以在1臺機(jī)器上，于1分鐘之內(nèi)，處理千萬像素的圖片。
　　多樣例學(xué)習(xí)是一個最近提出的監(jiān)督學(xué)習(xí)框架，與傳統(tǒng)的監(jiān)督學(xué)習(xí)相比，前者能處理模糊的標(biāo)號。一般來說，多樣例學(xué)習(xí)被應(yīng)用在離線的學(xué)習(xí)框架下。但是，諸如物體跟蹤等應(yīng)用并不能作用于離線框架下。因此，在基于已有成功應(yīng)用的離線多樣例學(xué)習(xí)算