用於核逼近的 Nystroem 方法
我一直在閱讀有關低秩內核近似的 Nyström 方法。該方法在 scikit-learn [1] 中實現，作為一種將數據樣本投影到內核特徵映射的低秩近似的方法。
據我所知，給定一個訓練集和一個核函數，它生成一個低秩近似核矩陣通過將 SVD 應用於和.
,
但是，我不明白如何使用核矩陣的低秩近似將新樣本投影到近似的核特徵空間。我發現的論文（例如[2]）沒有太大幫助，因為它們幾乎沒有說教性。
另外，我很好奇這種方法在訓練和測試階段的計算複雜性。
[1] http://scikit-learn.org/stable/modules/kernel_approximation.html#nystroem-kernel-approx
[2] http://www.jmlr.org/papers/volume13/kumar12a/kumar12a.pdf
讓我們以一種可以使您的問題答案更清晰的方式推導出 Nyström 近似值。
Nyström 中的關鍵假設是核函數是有秩的. （真的，我們假設它大約是等級，但為簡單起見，讓我們假設它完全是排名現在。）這意味著任何內核矩陣最多將具有秩, 特別是
是等級. 因此有非零特徵值，我們可以寫出特徵分解作為
特徵向量存儲在, 形狀，並且特徵值排列在， 一個對角矩陣。 所以，讓我們選擇元素，通常是隨機均勻的，但可能根據其他方案 - 在這個簡化版本中，重要的是滿級。一旦我們這樣做了，只需重新標記點，以便我們最終得到塊中的內核矩陣：
我們在哪裡評估每個條目（這是） 和()，但不想評估任何條目. 現在，我們也可以根據這個塊結構拆分特徵分解：
在哪裡是和是. 但請注意，現在我們有. 所以我們可以找到和通過特徵分解已知矩陣. 我們也知道. 在這裡，我們知道這個等式中的所有內容，除了，所以我們可以求解這意味著什麼特徵值：將兩邊右乘要得到
現在我們有了需要評估的一切:
在 (*) 中，我們找到了 Nyström 嵌入的一個版本，您可能只是將其視為定義。這告訴我們我們正在為塊估算的有效內核值.
在 (**) 中，我們看到特徵矩陣 ，也就是形狀, 對應於這些估算的內核值。如果我們使用為了點，我們有一組維特徵
我們可以快速驗證對應於正確的核矩陣：
所以，我們需要做的就是訓練我們的常規學習模型維特徵. 這將與學習問題的核化版本完全相同（在我們所做的假設下）.
現在，對於單個數據點, 中的特徵相當於
為了一點在分區 2 中，向量只是相關的行，所以把這些疊加起來給我們- 所以同意分區 2 中的點。它也適用於分區 1：在那裡，向量是一行，所以將它們堆疊起來得到, 再次同意. 所以……對於訓練時看不見的測試點仍然是正確的. 你只需做同樣的事情：
因為我們假設內核是秩， 矩陣也有等級，以及重建仍然與 for 完全相同的邏輯是準確的.
上面，我們假設核矩陣正是排名*. 通常情況並非如此。例如，對於高斯核，總是排名，但後面的特徵值通常會很快下降，所以它會接近一個秩矩陣，以及我們的重建或者將接近*真實值，但不完全相同。它們將是更好的重建，越接近的特徵空間達到總體而言，這就是為什麼選擇正確的點在實踐中很重要。 另請注意，如果有任何零特徵值，你可以用偽逆替換逆，一切仍然有效；你只需更換在重建中.
如果您願意，可以使用 SVD 代替特徵分解；自從是 psd，它們是一樣的，但是 SVD 可能對內核矩陣中的輕微數值誤差等更穩健一些，所以這就是 scikit-learn 所做的。scikit-learn 的實際實現是這樣做的，儘管它使用在逆而不是偽逆。