從動力學角度看優化算法:SGD ≈ SVM?

2021-12-19 PaperWeekly

收錄於話題 #機器學習 67個內容

©PaperWeekly 原創 · 作者｜蘇劍林

單位｜追一科技

研究方向｜NLP、神經網絡

眾所周知，在深度學習之前，機器學習是 SVM（Support Vector Machine，支持向量機）的天下，曾經的它可謂紅遍機器學習的大江南北，迷倒萬千研究人員，直至今日，「手撕 SVM」仍然是大廠流行的面試題之一。然而，時過境遷，當深度學習流行起來之後，第一個革的就是 SVM 的命，現在只有在某些特別追求效率的場景以及大廠的面試題裡邊，才能看到 SVM 的蹤跡了。

峰迴路轉的是，最近 Arxiv 上的一篇論文 Every Model Learned by Gradient Descent Is Approximately a Kernel Machine 做了一個非常「霸氣」的宣言：任何由梯度下降算法學出來的模型，都是可以近似看成是一個 SVM！

論文標題：

Every Model Learned by Gradient Descent Is Approximately a Kernel Machine

https://arxiv.org/abs/2012.00152這結論真不可謂不「霸氣」，因為它已經不只是針對深度學習了，而且只要你用梯度下降優化的，都不過是一個 SVM（的近似）。筆者看了一下原論文的分析，感覺確實挺有意思也挺合理的，有助於加深我們對很多模型的理解，遂跟大家分享一下。

SVM基礎

其中

SVM 理論不是本文的重點，我們知道它的形式如（1），即可。在這一節中，我們將會推導梯度下降的一個解析解，並且發現這個解跟式（1），具有非常相似的形式，因而我們說梯度下降出來的模型都可以近似看成一個 SVM 模型。

假設我們的模型是

為了使得後面的推導更簡潔，這裡使用了求和的形式，一般情況下是求平均才對，但這不影響最終的結果。在「從動力學角度看優化算法」系列文章中，我們堅持的觀點是梯度下降求解參數

可見，模型

結果分析

經過一番推導，我們的得到了式（7），它是當學習率趨於 0 的梯度下降的理論解。從推導過程可以看到，這個結果只依賴於梯度下降本身，跟模型具體結構沒關係。對於式（7），我們可以從下面的角度理解它。

首先，我們將記

這在形式上就跟 SVM 很像了，區別就在於 SVM 的

拓展思考

那麼，這個結果能給我們帶來什麼思想衝擊呢？原論文在「Discussion」那一節花了相當長的篇幅討論這個事情，這裡我們也來琢磨一下這個事情。

從深度學習的視角來看，這個結果揭示了深層神經網絡模型與傳統的核方法之間的聯繫，藉助核方法的可解釋性來增強神經網絡的可解釋性。比如，通過梯度內積作為相似度度量，我們或許可以從訓練集中檢索出與輸入相近的訓練樣本，以解釋輸出的決策過程。更進一步地，如果該方向能夠得到更為精確的量化，那麼它有可能大大改進增量學習的方法，即對於新來的標註樣本，我們可能只需要想辦法往模型中添加

反過來看，該結果也許能促進核機器、核方法的發展。傳統的核函數依賴於認為定義，而上述梯度內積形式的核函數給我們帶來了新的構建核函數的思路，增強核方法對複雜函數的建模能力。同時，由於梯度下降與核機器的相似性，我們最終或許可以通過梯度下降來訓練核機器，從而克服核機器在大規模數據下的訓練難題，等等。

還有一些別的腦洞可以發散一下，比如我們知道對於凸優化問題有唯一解，並且理論上梯度下降總可以找到這個解，而前面又說梯度下降相當於一個 SVM。所以，這是不是意味著所有凸優化問題的解都相當於一個 SVM？這個腦洞夠不夠大？

總之，揭示梯度下降與核機器之間的聯繫，有助於兩者的進一步借鑑與融合，並且有可能發展出一些新的研究思路。

如何才能讓更多的優質內容以更短路逕到達讀者群體，縮短讀者尋找優質內容的成本呢？答案就是：你不認識的人。

總有一些你不認識的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學者和學術靈感相互碰撞，迸發出更多的可能性。 

PaperWeekly 鼓勵高校實驗室或個人，在我們的平臺上分享各類優質內容，可以是最新論文解讀，也可以是學習心得或技術乾貨。我們的目的只有一個，讓知識真正流動起來。

📝 來稿標準：

• 稿件確係個人原創作品，來稿需註明作者個人信息（姓名+學校/工作單位+學歷/職位+研究方向） 

• 如果文章並非首發，請在投稿時提醒並附上所有已發布連結 

• PaperWeekly 默認每篇文章都是首發，均會添加「原創」標誌

📬 投稿郵箱：

• 投稿郵箱：hr@paperweekly.site 

• 所有文章配圖，請單獨在附件中發送 

• 請留下即時聯繫方式（微信或手機），以便我們在編輯發布時和作者溝通

🔍

現在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關注」訂閱我們的專欄吧

關於PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報導人工智慧前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公眾號後臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群裡。

相關焦點

  • 從動力學角度看優化算法:為什麼SimSiam不退化?
    筆者認為，像 SimSiam、GAN 等模型的成功，很重要的原因是使用了基於梯度的優化器（而非其他更強或者更弱的優化器），所以不結合優化動力學的答案都是不完整的。在這裡，筆者嘗試結合動力學來分析 SimSiam 不會退化的原因。
  • 【典型算法】SVM算法
    小編說：機器學習算法眾多，全部掌握，一則不可能，二則沒必要。如何靈活掌握和應用機器學習算法呢？
  • 關於支持向量機(SVM)的原理,你了解多少?(萬字長文 速收)
    臺灣的林智仁教授寫了一個封裝SVM算法的libsvm庫，大家可以看看，此外這裡還有一份libsvm的注釋文檔。    除了在這篇論文《fast training of support vector machines using sequential minimal optimization》中platt給出了SMO算法的邏輯代碼之外，這裡也有一份SMO的實現代碼，大家可以看下。
  • 如何學習SVM(支持向量機)以及改進實現SVM算法程序?
    有了這個核函數緩存，你的 svm 求解程序能瞬間快幾十倍。但是還有很多時候樣本是密集向量，比如一共 200 個特徵，大部分樣本都有 100個以上的非零特徵，用稀疏向量存儲的話就非常低效了，opencv 的 svm 實現就是非稀疏向量。非稀疏向量直接是用數組保存樣本每個特診的值，在工程方面就有很多優化方式了，比如用的最多的求核函數的時候，直接上 SIMD 指令或者 CUDA，就能獲得更好的計算性能。
  • 如何學習SVM?怎麼改進實現SVM算法程序?答案來了
    SVM 算法，以及如何利用 matlab 編程實現 SVM 算法，同時在理解原有的程序包以及在原有的程序包基礎上進行改進有什麼好的方法？有了這個核函數緩存，你的 svm 求解程序能瞬間快幾十倍。但是還有很多時候樣本是密集向量，比如一共 200 個特徵，大部分樣本都有 100個以上的非零特徵，用稀疏向量存儲的話就非常低效了，opencv 的 svm 實現就是非稀疏向量。非稀疏向量直接是用數組保存樣本每個特診的值，在工程方面就有很多優化方式了，比如用的最多的求核函數的時候，直接上 SIMD 指令或者 CUDA，就能獲得更好的計算性能。
  • 支持向量機(SVM)算法總結
    但很多算法工程師以外的人對這一算法了解不多。今天我們就聊一聊支持向量機算法。要理解svm我們需要先理解什麼是間隔最大化，首先從簡單的線性二分類開始開始說起。要想對不用的樣本空間分開來，如下如所示，需要找出一條線將不同分類的樣本隔離開。
  • 機器學習算法筆記-SVM支持向量機簡介及JAVA小實現
    前言最近開始學習一些機器學習裡的主要算法，SVM支持向量機是我目前產品裡用到的核心算法，想在這裡把我學到的一些東西記錄下來。
  • SVM 支持向量機算法-實戰篇
    1，SVM 的實現SVM 算法即可以處理分類問題，也可以處理回歸問題。sklearn 庫的 svm 包中實現了下面四種 SVM 算法：LinearSVC：用於處理線性分類問題。SVC：用於處理非線性分類問題。
  • SVM算法
    其中一個很大的原因是，不知道寫什麼好-_-，最近一段時間看了看關於SVM(Support Vector Machine)的文章，覺得SVM是一個非常有趣，而且自成一派的方向，所以今天準備寫一篇關於關於SVM的文章。關於SVM的論文、書籍都非常的多，引用強哥的話「SVM是讓應用數學家真正得到應用的一種算法」。
  • 深度學習優化算法總結(SGD,AdaGrad,Adam等)
    點擊文末「閱讀原文」立刻申請入群~作者 |劉浪原文 | https://zhuanlan.zhihu.com/p/61955391動量（Momentum）算法帶動量的 SGD引入動量（Momentum）方法一方面是為了解決「峽谷」和「鞍點」
  • 通俗易懂講解SVM算法| 算法基礎(15)
    關注：九三智能控，每天學點AI算法作者：劍曇說編譯&出處：CSDN支持向量機（SVM)算法通俗的理解在二維上，就是找一分割線把兩類分開，問題是如下圖三條顏色都可以把點和星劃開，但哪條線是最優的呢，這就是我們要考慮的問題
  • MATLAB中的機械臂算法——動力學
    Robotics System Toolbox(RST)中的動力學算法前面，我們講了機械臂的運動學(kinematics)：正向運動學和反向運動學。正向運動學指的是在已知機械臂各個關節角度的情況下，推算end-effector(機械臂終端)的位置和方向(合稱pose)。
  • 從SGD到NadaMax,十種優化算法原理及實現
    無論是什麼優化算法，最後都可以用一個簡單的公式抽象： 是參數，而  是參數的增量，而各種優化算法的主要區別在於對  的計算不同，本文總結了下面十個優化算法的公式，以及簡單的Python實現：SGDMomentumNesterov MomentumAdaGradRMSPropAdaDelta
  • 零基礎也教你玩轉SVM
    SVM的學習算法就是求解凸二次規劃的最優化算法。    關於SVM學習，推薦兩本書：統計學習方法（李航）和機器學習實戰，二者結合，可以幫助我們理解SVM算法。這就要用到核函數，核函數的功能就是將低維的特徵空間映射到高維的特徵空間，而在高維的特徵空間中，這些樣本進過轉化後，變成了線性可分的情況，這樣，在高維空間中，我們就能夠利用線性模型來解決數據集分類問題   如果想要透徹理解SVM建議還是要看看上面的書和博客文章，篇幅有限，我這裡的中心在於凸二次規劃的優化算法--SMO(序列最小最優化算法)（
  • 6種機器學習中的優化算法:SGD,牛頓法,SGD-M,AdaGrad,AdaDelta,Adam
    正文共：1710 字 8 圖預計閱讀時間： 10 分鐘本文一共介紹6種機器學習中的優化算法：
  • SVM機器學習算法和OpenCV實現貓咪圖片識別器
    SVM（支持向量機）是一種常用的機器學習分類算法。
  • 動手寫機器學習算法:SVM支持向量機(附代碼)
    我們在學習過程中最容易犯的一個錯誤就是：看的多動手的少，其中：線性可分的,指定核函數為linear：'''data1——線性分類'''data1 = spio.loadmat('data1.mat')X = data1['X']y = data1['y']y = np.ravel(y)plot_data(X,y)model = svm.SVC
  • 【乾貨】深度學習必備:隨機梯度下降(SGD)優化算法及可視化
    來源：CSDN 授權轉載作者：Sebastian Ruder譯者：一隻鳥的天空【新智元導讀】梯度下降算法是機器學習中使用非常廣泛的優化算法，也是眾多機器學習算法中最常用的優化方法。一般而言每次更新隨機選擇[50,256]個樣本進行學習，但是也要根據具體問題而選擇，實踐中可以進行多次試驗，選擇一個更新速度與更次次數都較適合的樣本數。mini-batch梯度下降可以保證收斂性，常用於神經網絡中。
  • SVM大解密(連載四)
    可以看到是線性可分的吧，如果還看不清把視角換個角度（右視圖）： 基於此，那麼對於上節的SMO算法，如果拿來求解非線性數據的話，我們只需要將其中對應的內積部分改成核函數的形式即可。當今學者已經有非常多的人研究SVM算法，同時開發了許多開源的程序，這些程序都是經過不斷優化的，性能比起我們這裡自己編的來說要好得多，所以在實際應用中通常都是用他們無私貢獻的軟體包。一個典型的軟體包就是臺灣一個教授團隊的LIBSVM軟體包，那麼你是否想一窺其用法，看看它的性能如何呢？請看下節matlab下LIBSVM的簡單使用。
  • 拳打Adam,腳踢SGD:北大提出全新優化算法AdaBound
    聽起來 Adam 好像高級了很多，但在 Reddi 等人的 ICLR 2018 最佳論文中，他們表示 Adam 等算法在經驗上常會收斂得比帶動量的 SGD 方法差，他們證明了導致該問題的一個原因是這些算法使用了指數滑動平均（exponential moving average）操作。這也是去年的研究重點，很多研究者嘗試改良 Adam 以解決收斂差這個問題。