Optimization

內核化 SVM 是否可以使用梯度下降(如果可以,人們為什麼要使用二次規劃)?

  • May 31, 2016

為什麼人們在處理核化 SVM 時使用二次規劃技術(例如 SMO)?梯度下降有什麼問題?是無法與內核一起使用還是太慢了(為什麼?)。

這裡有更多的上下文:為了更好地理解 SVM,我使用梯度下降來使用以下成本函數訓練線性 SVM 分類器:

我正在使用以下符號:

  • 是模型的特徵權重和是它的偏置參數。
  • 是個訓練實例的特徵向量。
  • 是目標類(-1 或 1)實例。
  • 是訓練實例的數量。
  • 是正則化超參數。

我導出了一個(子)梯度向量(關於和)從這個方程,梯度下降工作得很好。

現在我想解決非線性問題。我可以更換所有的點積嗎和在成本函數中,其中是核函數(例如高斯 RBF,),然後使用微積分推導(子)梯度向量並繼續梯度下降?

如果它太慢,那是為什麼呢?成本函數不是凸的嗎?還是因為梯度變化太快(不是 Lipschitz 連續的)所以算法在下降的過程中不斷地跳過山谷,所以收斂的很慢?但即便如此,它怎麼能比二次規劃的時間複雜度差,也就是? 如果這是局部最小值的問題,那麼帶有模擬退火的隨機 GD 不能克服它們嗎?

放以便和, 和, 在哪裡是原始輸入矩陣的映射,. 這允許人們通過原始公式解決 SVM。使用您的符號表示損失:

是一個矩陣,和是一個矩陣。兩者都不是無限的。

實際上,對偶通常更快地解決,但原始也有它的優點,例如近似解(在對偶公式中不能保證)。


現在,為什麼對偶如此突出並不明顯:[1]

過去十年中大多數關於雙重優化的研究的歷史原因尚不清楚。我們認為這是因為 SVM 是在其硬邊距公式中首次引入的 [Boser et al., 1992],因此雙重優化(由於約束)似乎更自然。然而,一般來說,應該首選軟邊距 SVM,即使訓練數據是可分離的:決策邊界更加穩健,因為考慮了更多的訓練點 [Chapelle et al., 2000]


Chapelle (2007) 認為原始優化和對偶優化的時間複雜度是, 最壞的情況是,但他們分析了二次和近似鉸鏈損失,因此不是適當的鉸鏈損失,因為它不能與牛頓法一起使用。


[1] Chapelle, O. (2007)。在原始中訓練支持向量機。神經計算,19(5),1155-1178。

引用自:https://stats.stackexchange.com/questions/215524

comments powered by Disqus