论文浅尝 - ICML2020 | 跨域对齐的图最优运输算法
陳卓，浙江大學在讀博士，主要研究方向為圖神經網絡和知識圖譜表示學習。
論文鏈接：https://arxiv.org/pdf/2006.14744
代碼：https://github.com/LiqunChen0606/Graph-Optimal-Transport
發表會議：ICML 2020
動機
該論文的出發點基于前人工作的局限，認為當前存在的跨域對齊方法主要是采用各種先進的注意力機制來模擬軟對齊，但是傳統的注意力機制是由特定下游任務的loss進行監督和引導的，而沒有明確考慮對齊本身的的訓練信號。并且，往往學習到的注意力矩陣會比較稠密，缺乏可解釋性。所以作者提出了圖最優運輸算法這樣一個新的框架，通過把最優運輸應用在圖匹配上來處理跨域問題。
同時，這個算法與現有的神經網絡模型具有很好的兼容性，可以直接作為drop-in正則化項加入到原來的模型中。通過這樣一個通用的正則化系數，在兩個域對齊程度低的的pair上施加更多的懲罰，這對于機器翻譯，圖像注釋，以及圖像-文本跨模態檢索等需要匹配的場景，效果提升是比較make sense的。
最后，這個論文的很大一個亮點在于通用性，作者在5個task上對于不同的模型做了相關實驗，使用了GOT方法后全部取得了效果提升。后面大部分篇幅也用在實驗上。
背景設定
這里的跨域對齊可能與跨知識圖譜數據庫對齊的不太一樣。因為本文所指的跨域是特指跨模態的。對于兩個不同的domain Dx和Dy， 分別考慮其中的一個數據集如X tilde（和Y tilde，其中每一個entity都可以由一個特征向量表示。n和m代表該domain下數據集中的entity數量。
文中所討論的范圍主要集中于涉及圖像和文本的任務，因此此處的實體可以對應于圖像中的對象或句子中的單詞。圖像可以=表示為一組檢測到的對象，每個對象都與一個特征向量相關聯，而一個句子則可以被一串word embedding表示。在通用場景下，一個深度神經網絡fθ會被設計接收以上的X tilde和Y tilde并用來生成當前語境下的數據表示X和Y。這里的fθ可以是很多模型，θ是模型參數。最后監督信號l將會被用來進行參數θ的學習。訓練目標可以簡化為這個loss函數公式，其中小l是監督信號，特定任務下loss函數的選擇和小l都不同。
然后是動態圖譜構建。文章的設定中，每個域的節點集合需要構建一個圖，其中每一個節點都是entity，由一個特征向量表示，并且通過計算成對節點的相似性來選擇是否添加邊。這里手工定義的超參數t作為一個是否添加邊的相似度閾值。論文中選取的t等于0.1。
動態這個詞在這里體現在圖上邊之間聯系的動態性，因為在模型的訓練過程中節點的向量表示X和Y都是會因為參數的迭代更新不斷變化的，所以邊的有無，或者說圖構建，都是一個持續變化且逐漸趨于穩定的過程。
經過以上步驟把每個domain中的entities表示成一個圖，跨域對齊的任務自然被轉換成了一個graph matching 的問題。
該論文的主要idea來源在于，提出了GOT圖最優運輸算法，將兩種類型的最優傳輸距離應用到graph matching上，使得該通用框架在許多任務上達到了更好的效果。其中采用的兩種最優運輸距離，分別是針對節點匹配的Wasserstein distance以及針對邊匹配的Gromov-Wasserstein distance。后面用WD和GWD進行縮寫描述。
大家可能不太了解這個距離的概念，但是我相信KL散度可能大部分人都有所耳聞。這是衡量兩個分布之間距離的一個指標。上面提到的WD和GWD實際上也是。其中WD就起源于最優運輸問題。也叫推土機距離，這個名字非常形象。
其把概率分布想象成一堆石頭，如何移動一堆石頭，通過最小的累積移動距離把它堆成另外一個目標形狀，這就是最優運輸所關心的問題。先看上圖的下半部分：我們可以把兩個分布之間的距離看作是最小需要的累積移動距離，它形象解釋了如何將離散分布P轉換成離散分布Q的過程。而這個過程中第一步p1移動2個方塊到p2，然后p2移動2個到p3，然后p3移動一個方塊到p4。最后總共的移動數目5就是這兩個分布之間的最優運輸距離。
相對于KL散度等分布評價指標來說，WD具有很明顯的優點，比如可以度量離散分布之間的距離，且滿足對稱性，然后能夠很好地反映概率分布的幾何特性。幾何特性的意思就比如這個p1到p3，并不是直接跳過去，而是必須經過中間的p2。這使得分布之間的空間距離也被考慮進去。
然后我們再來看圖片上方文章中這個最優運輸的公式：其中μ和v是來自不同域中兩個離散的分布，π(μ , v)在這里這里表示的意思是所有的聯合分布γ (x, y )的集合。上面這個公式的含義是對于每一個可能的聯合分布γ，從中采樣x，y屬于γ，要注意這里的x，y屬于兩個不同域。然后計算x y之間的距離。后半截代表對于該次采樣的聯合分布γ下樣本對距離的期望。最后在前面加上下界符號，整個公式的含義也就變成了，所有可能的聯合分布下這個期望值所能取到的最小值，換句話說，就是兩個分布的最短距離，這也就是最終希望得到的WD。
但是上面這種形式難以求解，所以進一步的，公式可以通過一些轉換，化簡成為下面那個形式。其中c（xi，yi）的含義也是兩個向量的距離，x，y分別來自兩個分布，或者說兩個domain。這里把找到最優聯合分布gama的這樣一個問題，轉換成為了找到最優傳輸矩陣T的問題，顯然就相對直觀一些了。矩陣T具有天然normalize特性，根據后面這個限定，可以得出其中所有元素加起來都是1. 在這里，其中任意一個元素Tij，代表向量ui移動到向量vj所需要的最小代價，也就是兩個向量之間的WD。后面實驗部分會有直觀展示。
最終，不僅得到了兩個域總體的距離，還得到了代表了兩個域內entity之間的相關系數的副產物T矩陣。
如果前面的WD理解了，那這里的GWD也就很好理解了。可以看到右圖，我們剛才計算的WD是兩個域之間的距離，計算域內距離的方法是前面提到的相似性度量。作者希望那剩下的每個域之間的節點pair，或者說邊的距離，使用GWD進行度量。和前面的定義形式基本一樣，其中L函數是計算邊距離的cost function。而這里的T則成為了一個對齊不同圖中邊的傳輸方案。
然后作者梳理了WD和GWD分別的優勢，GWD可以捕捉邊的相似性但是無法直接應用到圖對齊，因為只考慮邊的相似性話，boy和girl這樣一個pair的相似性居然和football，basketball pair是一樣的。但他們的語義完全不同，所以就說不通。另一方面來說，WD雖然匹配不同圖中的節點，但是又不能捕捉邊的相似性。這樣不同節點表示的重復entity又會被當做一樣并且忽略其周圍的關系。就比如There is a red book on the blue desk這個句子，并且給定了一個圖，里面不同位置的書有不同的顏色。如果無法理解關系，就無法知道這個句子里面的某本書對應的圖里面的哪本。
所以很自然的，作者提出了下圖這樣一個結合方案。
其中最優傳輸矩陣T是被共享的，因為他同時結合了節點信息和邊的信息。最終GOT的公式如上，很自然的，可以轉換到右邊的cost function。下圖就是計算這樣一個距離的流程。原始特征x tilde和y tilde同時輸入，經過特定的模型主體輸出x y同時計算域內的 cost matrix和跨域的cost matrix。然后計算出通用的傳輸方案T，作用到GWD和WD的計算流程上，最后得到一個GOT的融合距離。這個融合距離，最終會作為一個drop in正則化參數，在反向傳播過程中用來監督各種任務訓練中的跨域對齊程度，并且更新模型參數θ。
該論文的亮點在于通用性，也就是在多個不同的，多模態任務中均有效果，而他主要的修改，就是在原有下游任務的基礎上，增加了一個任務無關的，衡量跨域圖譜對齊程度的正則化項。所以就算是前面的最優傳輸沒有理解也沒關系，不影響后面的閱讀和整體思路理解，因為這兩個數學上距離的概念都不是作者提出來的，他只是將其做了一個融合改進并且作為通用的方法應用到了模型中。
實驗：
首先是視覺語言的多模態任務。其一是圖像-文本跨模態檢索。這個任務定義是，當給定一個模態(比如圖像)的查詢時，它的目標是從數據庫中以另一個模態（比如句子）檢索最相似的樣本。這里的關鍵挑戰是如何通過理解跨模式數據的內容，和度量其語義相似性來匹配跨模式數據。早期的方法采用全局表示來表達整個圖像和句子進行一個匹配卻忽略了局部細節。這些方法在只包含單個對象的簡單場景中工作得好，對于涉及復雜自然場景的真實的情況并不令人滿意。
Scan這個方法通過注意力機制把句子中的詞和 圖像中的不同區域被識別出來的物體映射到一個共同的 embedding space 來預測整張圖和一個句子之間的相似性。GOT在這里用來衡量句子和圖片這兩個域中graph的對齊程度。
然后作者證明單獨使用的情況下WD比GWD能夠取得更好的效果，而結合起來，作為GOT使用，可以達到最好的效果。并且可以看到，最優傳輸方案這個矩陣T，可視化出來之后，具有更強的解釋性和更少的模糊性，就是他每一個對應關系都很清晰不像注意力矩陣那么模糊和密集。
任務2是VQA，使用的是雙線性注意力模型BAN。后面的數字可以看做是生成的注意力圖數量，可以理解為模型的復雜程度。可以看出 ?GOT對于簡單模型的提升效果的程度是好于復雜模型。（個人感覺VQA上跨域對齊的好處有待商討）
然后對于文本生成的任務來說，提到了圖像注釋。
以及機器翻譯任務，效果都是比原有的要好。
最后是段落摘要任務，總之就是在一個或多個方法的baseline基礎上加入GOT，效果都有提升。
文章最后以機器翻譯實驗為基礎進行了消融實驗，探討了T矩陣是否在WD和GWD中共享的影響，證明共享T具有更好的效果。同時也測試了超參數λ 取值的影響，最后發現在λ=0.8的時候效果最好，也就是說WD在這個過程中占了更重要的比例。
總結
該文章的主要出發點是跨域對齊在多模態任務中具有很重要的地位，當然也不局限多模態。從結果可以看出域內和域間的關系在對齊任務上都很重要。同時，作者也提到，這是一個可以廣泛應用到許多跨模態任務的通用框架，作者這篇文章的重要性很大一部分也體現在他的通用性上，核心idea是加了一個基于對齊程度的正則化項這樣一個trick。
最后我們可以看出來，kg里面，特別是小的場景kg中，每一個結點和邊都是非常重要的，都有其存在的道理，提升模型效果可以考慮從加強其中語義區分和語義的捕捉入手。
?
OpenKG
開放知識圖譜（簡稱 OpenKG）旨在促進中文知識圖譜數據的開放與互聯，促進知識圖譜和語義技術的普及和廣泛應用。
點擊閱讀原文，進入 OpenKG 網站。
總結
以上是生活随笔為你收集整理的论文浅尝 - ICML2020 | 跨域对齐的图最优运输算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 论文浅尝 | Data Intellig
- 下一篇： 论文浅尝 | 将文本建模为关系图，用于联