谷歌大腦重磅研究:快速可微分排序算法,速度快出一個數量級

2020-12-05 量子位

魚羊 十三 發自 凹非寺量子位 報導 | 公眾號 QbitAI

快排堆排冒泡排。排序，在計算機中是再常見不過的算法。

在機器學習中，排序也經常用於統計數據、信息檢索等領域。

那麼問題來了，排序算法在函數角度上是分段線性的，也就是說，在幾個分段的「節點」處是不可微的。這樣，就給反向傳播造成了困難。

現在，谷歌大腦針對這一問題，提出了一種快速可微分排序算法，並且，時間複雜度達到了O(nlogn)，空間複雜度達為O(n)。

速度比現有方法快出一個數量級！

代碼的PyTorch、TensorFlow和JAX版本即將開源。

快速可微分排序算法

現代深度學習架構通常是通過組合參數化功能塊來構建，並使用梯度反向傳播進行端到端的訓練。

這也就激發了像LeCun提出的可微分編程(differentiable programming)的概念。

雖然在經驗上取得了較大的成功，但是許多操作仍舊存在不可微分的問題，這就限制了可以計算梯度的體系結構集。

諸如此類的操作就包括排序(sorting)和排名 (ranking)。

從函數角度來看都是分段線性函數，排序的問題在於，它的向量包含許多不可微分的「節點」，而排名的秩要比排序還要麻煩。

首先將排序和排名操作轉換為在排列多面體(permutahedron)上的線性過程，如下圖所示。

△排列多面體說明

在這一過程後，可以發現對於r(θ)，若是θ出現微小「擾動」，就會導致線性程序跳轉到另外一個排序，使得r(θ)不連續。

也就意味著導數要麼為null，要麼就是「未定義」，這就阻礙了梯度反向傳播。

為了解決上述的問題，就需要對排序和排名運算符，進行有效可計算的近似設計。

谷歌大腦團隊提出的方法，就是通過在線性規劃公式中引入強凸正則化來實現這一目標。

這就讓它們轉換成高效可計算的投影算子(projection operator)，可微分，且服從於形式分析(formal analysis)。

在投影到排列多面體之後，可以根據這些投影來定義軟排序(soft sorting)和軟排名(soft ranking)操作符。

△軟排序和軟排名操作符

在此基礎上，要想完成快速計算和微分，一個關鍵步驟就是將投影簡化為保序優化(isotonic optimization)。

接下來是將保序優化進行微分，此處採用的是雅可比矩陣(Jacobian)，因為它簡單的塊級結構，使得導數很容易分析。

而後，結合命題3和引理2，可以描述投影到排列多面體上的雅可比矩陣。

需要強調的是，與保序優化的雅可比矩陣不同，投影的雅可比矩陣不是塊對角的，因為我們需要對它的行和列進行轉置。

最終，可以用O(n)時間和空間中的軟算子雅可比矩陣相乘。

實驗結果

研究人員在CIFAR-10和CIFAR-100數據集上進行了實驗。

實驗使用的CNN，包含4個具有2個最大池化層的Conv2D，RelU激活，2個完全連接層；ADAM優化器的步長恆定為10-4，k=1。

與之比較的是O(Tn2)的OT方法，以及O(n2)的All-pairs方法。

△rQ及rE為新算法

結果表明，在CIFAR-10和CIFAR-100上，新算法都達到了與OT方法相當的精度，並且速度明顯更快。

在CIFAR-100上訓練600個epoch，OT耗費的時間為29小時，rQ為21小時，rE為23小時，All-pairs為16小時。在CIFAR-10上結果差不多。

在驗證輸入尺寸對運行時間的影響時，研究人員使用的是64GB RAM的6核Intel Xeon W-2135，以及GeForce GTX 1080Ti。

禁用反向傳播的情況下，進行1個batch的計算，OT和All-pairs分別在n=2000和n=3000的時候出現內存不足。

啟用反向傳播時，OT和All-pairs分別在n=1000和n=2500的時候出現內存不足。

開啟新的可能性

曾就職於谷歌、NASA的機器學習工程師Brad Neuberg認為，從機器學習的角度來說，快速可微分排序、排名算法看上去十分重要。

而谷歌的這一新排序算法，也在reddit和hacker news等平臺上引起了熱烈的討論。

有網友對其帶來的「新可能性」做出了更為詳細的討論：

我想，可微分排序生成的梯度信息量更大，使得梯度下降的速度更快，從而能夠進一步提升訓練速度。

我認為，這意味著某些基於排名的指標，以後可以用可微分的形式來表示。也就是說，神經網絡可以輕鬆地針對這些結果直接進行優化。對於谷歌而言，這很顯然會應用於網絡搜索，以及諸如標籤分配之類的東西問題。

也有網友指出，雖然該算法並不是第一個解決了排序不可微問題的方法，但它的效率無疑更高。

傳送門

論文：https://arxiv.org/pdf/2002.08871.pdf

討論：https://news.ycombinator.com/item?id=22393790https://www.reddit.com/r/MachineLearning/comments/f85yp4/r_fast_differentiable_sorting_and_ranking/

— 完 —

相關焦點

  • ...nlogn)時間、O(n)空間複雜度可微分排序算法,速度快出一個數量級
    在機器學習中，排序也經常用於統計數據、信息檢索等領域。那麼問題來了，排序算法在函數角度上是分段線性的，也就是說，在幾個分段的「節點」處是不可微的。這樣，就給反向傳播造成了困難。現在，谷歌大腦針對這一問題，提出了一種快速可微分排序算法，並且，時間複雜度達到了O(nlogn)，空間複雜度達為O(n)。
  • 機器學習新突破:谷歌研究人員利用AI自動重構大腦神經元
    >近日，谷歌與馬克斯·普朗克神經生物學研究所合作，在《Nature Methods》上發表了一篇重磅論文，使用一種循環神經網絡算法對神經元連接組進行自動重構，不僅可以對連接組進行高解析度的可視化成像，而且準確度提高了一個數量級，為連接組學的研究帶來了新的突破。
  • 谷歌為何要養蘋果的親兒子Swift?原來意在可微分編程
    近日，Tryolabs 的研究工程師 Joaquín Alori 發布了一篇長文，從 Python 的缺點一路談到了谷歌在 Swift 機器學習方面的大計劃，並且文中還給出了相當多一些具體的代碼實例。可微分編程真如 Yann LeCun 所言的那樣會成為新一代的程序開發範式嗎？Swift 又將在其中扮演怎樣的角色？也許你能在這篇文章中找到答案。
  • JavaScript實現排序算法
    一、大O表示法大O表示法：在計算機中採用粗略的度量來描述計算機算法的效率，這種方法被稱為「大O」表示法在數據項個數發生改變時，算法的效率也會跟著改變。所以說算法A比算法B快兩倍，這樣的比較是沒有意義的。因此我們通常使用算法的速度隨著數據量的變化會如何變化的方式來表示算法的效率，大O表示法就是方式之一。
  • 谷歌DeepMind 的可微分神經計算機 DNC 怎麼樣?看 Facebook AI...
    研究科學家，主要負責前沿AI 平臺的開發以及前沿的深度學習研究。史丹福大學心智、大腦和計算中心主任 Jay McClelland 稱，這項研究將成為人工智慧領域「有趣且重要的裡程碑」。那麼我們究竟該如何看待谷歌 Deepmind 團隊最新發布的可微分神經計算機 DNC 呢？果然，已經有人在知乎上提出這個問題。編者註：該知乎提問中「谷歌deeplearning團隊」實際上應該指的是「谷歌Deepmind團隊」。
  • 用NumPy寫深度模型,用Julia可微分編程寫函數,這是WAIC開發者日
    但隨著 AlexNet 的提出，錯誤率瞬間就降到了 15%，而且重要的是，這種方法有很大的潛力，之後的研究使 ImageNet 的錯誤率一直在降低，甚至低於「人類」識別錯誤率 5%。深度學習利用強大的擬合能力大大擴展了算法潛力，現在算法問題已經解決了，那麼算力問題呢，我們該怎樣利用計算系統提升訓練速度？
  • 一種快速運動規劃晶片,讓無人車決策速度提升三個數量級
    Realtime Robotics的運動規劃晶片可幫助自動駕駛汽車做出更好的決策。他們最初在桌面手臂機器人上做實驗，基於FPGA開發出了一種可快速進行機器人運動規劃的定製處理器，使運動規劃流程的速度提升了三個數量級，而使用的電量僅為之前的二十分之一。現在，他們把這種晶片成功運用在無人車上。
  • 重磅| 谷歌大腦養成記:從識別貓到突破性機器翻譯
    谷歌公司的人工智慧研究機構谷歌大腦（Google Brain）成立於五年前。成立原則是：通過試錯熟悉周圍世界的人工「神經網絡」或許會發展出類似人類的靈活能力。這個概念不是新東西。不過，其大部分歷史，在絕大多數計算機科學家看來，有些狼藉甚至神秘。儘管如此，2011 年以來，谷歌大腦已經證實深度學習方法可以解決傳統手段無法解決的難題。
  • 比可微架構搜索DARTS快10倍,第四範式提出優化NAS算法
    由於新的目標是難以解決的，我們進一步提出了一種高效的算法，由近端啟發法進行優化。 通過這種方式，NASP 不僅比現有的可微分的搜索方法速度快，而且還可以找到更好的體系結構並平衡模型複雜度。最終，通過不同任務的大量實驗表明，NASP 在測試精度和計算效率上均能獲得更好的性能，在發現更好的模型結構的同時，速度比 DARTS 等現有技術快 10 倍以上。
  • 谷歌大腦提出AutoML-Zero,只會數學運算就能找到AI算法|開源
    接著谷歌又推出了AlphaGo Zero，只讓AI知道圍棋規則，從零開始學下棋，結果再次登上棋藝頂峰。AI既然能從零學習圍棋，是否可以從零開始摸索機器學習算法？當然可以，谷歌大腦團隊最新的研究成果已經做到了。谷歌將這種技術稱之為AutoML-Zero，意為「從零開始的自動機器學習」，已經在GitHub開源，並在Arxiv上提交了論文。
  • Python,Numpy,Pandas……數據科學家必備排序技巧
    有許多不同的基本排序算法。有些比其他執行速度更快、佔用內存更小。有些適合處理大數據，還有些可以更好地對特定序列數據進行排排序。可參見下表了解許多常用算法的時間和空間複雜性。圖片來自 http://bigocheatsheet.com/了解基礎的算法並不能解決大多數數據科學問題。事實上，過早的優化處理說不定什麼時候就會被視為錯誤源泉。
  • 怎麼樣更好地理解排序算法
    這個問題糾纏了我好久，總想怎樣才能把各種算法可視化，更容易理解和記憶。排序是一個經典的問題，它以一定的順序對一個數組或列表中的元素進行重新排序。而排序算法也是各有千秋，每個都有自身的優點和局限性。雖然這些算法平常根本就不用自己去編寫，但作為一個有追求的程式設計師，還是要了解它們從不同角度解決排序問題的思想。
  • 谷歌和OpenAI新研究:如何使用達爾文進化論輔助設計人工智慧算法?
    但是自然界也有其他好想法：現在計算機科學家正再次踏入生物進化這一研究領域，希望通過在人工智慧中植入生物進化元素的方式開發出更智能更有效的算法，恰如數十億年來生物進化塑造了人類大腦一樣。但是，首先讓我們回到中學的生物課本上。
  • 谷歌大腦提出「洗髮水」二階優化算法,Transformer訓練時間減少40%
    無論是SGD還是Adam，此類優化算法在都是計算損失函數的一階導數——梯度，然後按照某種規定的方式讓權重隨梯度下滑方向迭代。其實二階梯度會有更好的特性，因為它是計算梯度的導數，能夠更快地找到最合適的下降方向和速度。然而出於計算量和存儲成本的考慮，二階優化算法很少用到。
  • 計算機入門必備算法——快速排序法
    準備停止學習一周，等把項目這一關過了，再繼續深入學習分享算法。後來吧今天遇到的事情都比較鬱悶，也無心情繼續開發項目。便想轉移一下注意力，繼續學習快速排序算法的內容。昨天了解了遞歸的使用原理。今天可以使用這個新技能來解決一個新的問題————快速排序。快速排序是一種排序算法，這個算法比前天學習的選擇排序要快得多，實屬優雅代碼的典範。
  • 速度提升、準確率更勝一籌,周志華等人提出可微XGBoost算法sGBM
    2018 年，周志華和馮霽等人發表的一篇 NeurIPS 論文提出了一種用於表徵學習的多層梯度提升決策樹（mGBDT），這項研究開創性地融合了上述兩個研究方向的優勢。具體來說，mGBDT 具有和可微分編程模型一樣的分層表徵能力，同時又具備非可微分模型的一些優良特性，因此能以更好的方式處理表格式數據。
  • 用反向傳播算法解釋大腦學習過程?Hinton 等人新研究登上 Nature...
    機器之心報導魔王、Jamin、杜偉反向傳播可以解釋大腦學習嗎？近日 Hinton 等人的研究認為，儘管大腦可能未實現字面形式的反向傳播，但是反向傳播的部分特徵與理解大腦中的學習具備很強的關聯性。該研究將之前的相關研究置於「NGRAD」框架下，NGRAD 算法利用活動狀態的差異驅動突觸更新，這與反向傳播類似。
  • 谷歌大腦48名成員:斯坦福博士最多,還有一名輟學90後
    另外，谷歌首席科學家Vincent Vanhoucke也在谷歌大腦團隊中。 那麼這些天才的工程師都在研究什麼？ 20大研究領域 如上圖所示，谷歌大腦成員的研究範圍，主要包括在20大領域。涉及算法和理論、分布式系統和並行計算、機器智能、機器感知等等。
  • 首枚光子神經形態晶片問世 運算速度快3個數量級
    信息技術 | 首枚光子神經形態晶片問世 運算速度快3個數量級 　　據《麻省理工技術評論》雜誌網站近日報導，美國普林斯頓大學的科研團隊日前研製出全球首枚光子神經形態晶片，並證明其能以超快速度計算。　　普林斯頓大學亞力山大·泰特團隊的新成果是利用光子解決了神經網絡電路速度受限這一難題。
  • MIT 重磅研究成果:已開發出大腦神經迴路計算模型
    AI科技評論消息，MIT CSAIL 於今日發布了一個重磅研究成果：他們已經開發出一個大腦神經迴路的計算模型，它揭示了抑制神經元的生物意義。這個模型是由一組輸入神經元陣列與同等數量的輸出神經元組成，採用「競爭學習規則」（winner-take-all）來操作。也就是說，網絡的輸出神經元之間相互競爭以求被激活，但在每一時刻只有一個輸出神經元被激活。