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

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

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

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

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