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

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

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

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

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