Graph Embedding for Combinatorial Optimization: A Survey
作者:Yun Peng、Byron Choi、Jianliang Xu
論文鏈接://arxiv.org/pdf/2008.12646.pdf
摘要:在這篇論文中,香港浸會大學的研究者對近來用于解決組合優化(combinatorial optimization, CO)的圖嵌入方法進行了綜述。大多數圖嵌入方法分為兩個階段:圖預處理和 ML 模型學習。所以,本文也從圖預處理任務和 ML 模型兩個角度來分類圖嵌入工作。此外,本文還總結了近來用于探索圖嵌入的圖組合優化方法。
IsoNN 架構。
使用層級粗化圖(coarsened graph)的圖嵌入。
使用圖嵌入的 CO 方法匯總。
知識圖譜是關于實體及其關系的集合,是非常有用資源。然而,由于知識圖通常是不完備的,所以進行知識圖補全或鏈接預測是有用的,即預測一個不在知識圖譜中的關系是否可能是真的。本文綜述了用于知識圖譜完成的實體和關系嵌入模型,總結了在標準基準數據集上最新的實驗結果,并指出了未來可能的研究方向。
近年來,圖神經網絡(GNNs)由于具有建模和從圖結構數據中學習的能力,在機器學習領域得到了迅猛發展。這種能力在數據具有內在關聯的各種領域具有很強的影響,而傳統的神經網絡在這些領域的表現并不好。事實上,正如最近的評論可以證明的那樣,GNN領域的研究已經迅速增長,并導致了各種GNN算法變體的發展,以及在化學、神經學、電子或通信網絡等領域的突破性應用的探索。然而,在目前的研究階段,GNN的有效處理仍然是一個開放的挑戰。除了它們的新穎性之外,由于它們依賴于輸入圖,它們的密集和稀疏操作的組合,或者在某些應用中需要伸縮到巨大的圖,GNN很難計算。在此背景下,本文旨在做出兩大貢獻。一方面,從計算的角度對GNNs領域進行了綜述。這包括一個關于GNN基本原理的簡短教程,在過去十年中該領域發展的概述,以及在不同GNN算法變體的多個階段中執行的操作的總結。另一方面,對現有的軟硬件加速方案進行了深入分析,總結出一種軟硬件結合、圖感知、以通信為中心的GNN加速方案。
盡管它在機器學習中有重要的應用,非凸非凹目標的最小-最大優化仍然是難以實現的。不僅沒有已知的一階方法收斂甚至近似局部最小最大點,而且識別它們的計算復雜度也不為人所知。本文給出了非凸非凹目標和線性約束的約束最小-最優優化問題的計算復雜度,以及一階方法的局限性。
當前的深度學習研究以基準評價為主。如果一種方法在專門的測試集上有良好的經驗表現,那么它就被認為是有利的。這種心態無縫地反映在持續學習的重現領域,在這里研究的是持續到達的基準數據集。核心挑戰是如何保護之前獲得的表示,以免由于迭代參數更新而出現災難性地遺忘的情況。然而,各個方法的比較是與現實應用程序隔離的,通常通過監視累積的測試集性能來判斷。封閉世界的假設仍然占主導地位。假設在部署過程中,一個模型保證會遇到來自與用于訓練的相同分布的數據。這帶來了一個巨大的挑戰,因為眾所周知,神經網絡會對未知的實例提供過于自信的錯誤預測,并在數據損壞的情況下崩潰。在這個工作我們認為值得注意的教訓來自開放數據集識別,識別的統計偏差以外的數據觀測數據集,和相鄰的主動學習領域,數據增量查詢等預期的性能收益最大化,這些常常在深度學習的時代被忽略。基于這些遺忘的教訓,我們提出了一個統一的觀點,以搭建持續學習,主動學習和開放集識別在深度神經網絡的橋梁。我們的結果表明,這不僅有利于每個個體范式,而且突出了在一個共同框架中的自然協同作用。我們從經驗上證明了在減輕災難性遺忘、主動學習中查詢數據、選擇任務順序等方面的改進,同時在以前提出的方法失敗的地方展示了強大的開放世界應用。
//www.zhuanzhi.ai/paper/e5bee7a1e93a93ef97e1c
概述:
隨著實用機器學習系統的不斷成熟,社區發現了對持續學習[1]、[2]的興趣。與廣泛練習的孤立學習不同,在孤立學習中,系統的算法訓練階段被限制在一個基于先前收集的i.i.d數據集的單一階段,持續學習需要利用隨著時間的推移而到來的數據的學習過程。盡管這種范式已經在許多機器學習系統中找到了各種應用,回顧一下最近關于終身機器學習[3]的書,深度學習的出現似乎已經將當前研究的焦點轉向了一種稱為“災難性推理”或“災難性遺忘”的現象[4],[5],正如最近的評論[6],[7],[8],[9]和對深度持續學習[8],[10],[11]的實證調查所表明的那樣。后者是機器學習模型的一個特殊效應,機器學習模型貪婪地根據給定的數據群更新參數,比如神經網絡迭代地更新其權值,使用隨機梯度估計。當包括導致數據分布發生任何變化的不斷到達的數據時,學習到的表示集被單向引導,以接近系統當前公開的數據實例上的任何任務的解決方案。自然的結果是取代以前學到的表征,導致突然忘記以前獲得的信息。
盡管目前的研究主要集中在通過專門機制的設計來緩解持續深度學習中的這種遺忘,但我們認為,一種非常不同形式的災難性遺忘的風險正在增長,即忘記從過去的文獻中吸取教訓的危險。盡管在連續的訓練中保留神經網絡表示的努力值得稱贊,但除了只捕獲災難性遺忘[12]的度量之外,我們還高度關注了實際的需求和權衡,例如包括內存占用、計算成本、數據存儲成本、任務序列長度和訓練迭代次數等。如果在部署[14]、[15]、[16]期間遇到看不見的未知數據或小故障,那么大多數當前系統會立即崩潰,這幾乎可以被視為誤導。封閉世界的假設似乎無所不在,即認為模型始終只會遇到與訓練過程中遇到的數據分布相同的數據,這在真實的開放世界中是非常不現實的,因為在開放世界中,數據可以根據不同的程度變化,而這些變化是不現實的,無法捕獲到訓練集中,或者用戶能夠幾乎任意地向系統輸入預測信息。盡管當神經網絡遇到不可見的、未知的數據實例時,不可避免地會產生完全沒有意義的預測,這是眾所周知的事實,已經被暴露了幾十年了,但是當前的努力是為了通過不斷學習來規避這一挑戰。選擇例外嘗試解決識別不可見的和未知的示例、拒絕荒謬的預測或將它們放在一邊供以后使用的任務,通常總結在開放集識別的傘下。然而,大多數現有的深度連續學習系統仍然是黑盒,不幸的是,對于未知數據的錯誤預測、數據集的異常值或常見的圖像損壞[16],這些系統并沒有表現出理想的魯棒性。
除了目前的基準測試實踐仍然局限于封閉的世界之外,另一個不幸的趨勢是對創建的持續學習數據集的本質缺乏理解。持續生成模型(如[17]的作者的工作,[18],[19],[20],[21],[22]),以及類增量持續學習的大部分工作(如[12]中給出的工作,[23],[24],[25],[26],[27],[28])一般調查sequentialized版本的經過時間考驗的視覺分類基準如MNIST [29], CIFAR[30]或ImageNet[31],單獨的類只是分成分離集和序列所示。為了在基準中保持可比性,關于任務排序的影響或任務之間重疊的影響的問題通常會被忽略。值得注意的是,從鄰近領域的主動機器學習(半監督學習的一種特殊形式)中吸取的經驗教訓,似乎并沒有整合到現代的連續學習實踐中。在主動學習中,目標是學會在讓系統自己查詢接下來要包含哪些數據的挑戰下,逐步地找到與任務解決方案最接近的方法。因此,它可以被視為緩解災難性遺忘的對抗劑。當前的持續學習忙于維護在每個步驟中獲得的信息,而不是無休止地積累所有的數據,而主動學習則關注于識別合適的數據以納入增量訓練系統的補充問題。盡管在主動學習方面的早期開創性工作已經迅速識別出了通過使用啟發式[32]、[33]、[34]所面臨的強大應用的挑戰和陷阱,但后者在深度學習[35]、[36]、[37]、[38]的時代再次占據主導地位,這些挑戰將再次面臨。
在這項工作中,我們第一次努力建立一個原則性和鞏固的深度持續學習、主動學習和在開放的世界中學習的觀點。我們首先單獨回顧每一個主題,然后繼續找出在現代深度學習中似乎較少受到關注的以前學到的教訓。我們將繼續爭論,這些看似獨立的主題不僅從另一個角度受益,而且應該結合起來看待。在這個意義上,我們建議將當前的持續學習實踐擴展到一個更廣泛的視角,將持續學習作為一個總括性術語,自然地包含并建立在先前的主動學習和開放集識別工作之上。本文的主要目的并不是引入新的技術或提倡一種特定的方法作為通用的解決方案,而是對最近提出的神經網絡[39]和[40]中基于變分貝葉斯推理的方法進行了改進和擴展,以說明一種走向全面框架的可能選擇。重要的是,它作為論證的基礎,努力闡明生成建模作為深度學習系統關鍵組成部分的必要性。我們強調了在這篇論文中發展的觀點的重要性,通過實證證明,概述了未來研究的含義和有前景的方向。
題目: A Survey on Graph Neural Networks for Knowledge Graph Completion
摘要:
知識圖譜在諸如回答問題和信息檢索之類的各種下游任務中越來越受歡迎。但是,知識圖譜通常不完整,從而導致性能不佳。結果,人們對知識庫補全任務產生了濃厚的興趣。 最近,圖神經網絡已用于捕獲固有存儲在這些知識圖譜中的結構信息,并已顯示出可在各種數據集中實現SOTA性能。 在這項調查中,了解了所提出方法的各種優點和缺點,并嘗試在該領域中發現需要進一步研究的新的令人興奮的研究問題。
高斯過程(GPs)為核機器的學習提供了一種有原則的、實用的、概率的方法。在過去的十年中,GPs在機器學習社區中得到了越來越多的關注,這本書提供了GPs在機器學習中理論和實踐方面長期需要的系統和統一的處理。該書是全面和獨立的,針對研究人員和學生在機器學習和應用統計學。
這本書處理監督學習問題的回歸和分類,并包括詳細的算法。提出了各種協方差(核)函數,并討論了它們的性質。從貝葉斯和經典的角度討論了模型選擇。討論了許多與其他著名技術的聯系,包括支持向量機、神經網絡、正則化網絡、相關向量機等。討論了包括學習曲線和PAC-Bayesian框架在內的理論問題,并討論了幾種用于大數據集學習的近似方法。這本書包含說明性的例子和練習,和代碼和數據集在網上是可得到的。附錄提供了數學背景和高斯馬爾可夫過程的討論。
CMU大神博士生Brandon Amos,馬上就要畢業了。博士期間,他在可微優化機器學習建模方向,發表了ICLR 一篇,ICML 三篇,NeurIPS 三篇,分析了可微優化機器學習建模的很多問題。近日,他將自己的博士論文也開放了出來,系統的講述了可微優化機器學習建模的方方面面。
博士論文簡介
我們提出了兩種基于優化建模的基本方法:
然后,我們將展示如何使用OptNet方法,1)將無模型和基于模型的強化學習與可微最優控制相結合,2)針對top-k學習問題,我們展示了如何將cvxpy領域特定的語言轉換為可微優化層,從而實現本文方法的快速原型化。
近年來,移動設備得到了越來越大的發展,計算能力越來越強,存儲空間越來越大。一些計算密集型的機器學習和深度學習任務現在可以在移動設備上運行。為了充分利用移動設備上的資源,保護用戶的隱私,提出了移動分布式機器學習的思想。它使用本地硬件資源和本地數據來解決移動設備上的機器學習子問題,只上傳計算結果而不是原始數據來幫助全局模型的優化。該體系結構不僅可以減輕服務器的計算和存儲負擔,而且可以保護用戶的敏感信息。另一個好處是帶寬的減少,因為各種各樣的本地數據現在可以參與培訓過程,而不需要上傳到服務器。本文對移動分布式機器學習的研究現狀進行了綜述。我們調查了一些廣泛使用的移動分布式機器學習方法。我們還就這一領域的挑戰和未來方向進行了深入的討論。我們相信這項調查能夠清晰地展示移動分布式機器學習的概況,并為移動分布式機器學習在實際應用中的應用提供指導。