[論文筆記]Relational inductive biases, deep learning, and graph network

09-03

來自專欄 NLP相關筆記8 人贊了文章

斷斷續續看了兩周多, 終於看完了, 是為了自己再次看能夠看懂而寫的, 寫的有些羅嗦.

總體而言, 這與其說是論文不如說是教程, 感覺可以單獨放到 deep learning 裡面自成一章, 確實是乾貨.

另外, 本文中包含著強烈的個人意見, 可能缺乏客觀性而造成一定的理解偏差, 還望指出.

0. Abstract

核心思想
反對單純使用人工特徵或者單純使用端到端系統的方法.AI中首要的問題是要解決組合泛化的問題, 而解決這個問題的方法是要解決結構化表徵方法和結構化計算的問題.

個人理解 :

這裡的結構化表徵方法應該針對的是如今的單純數值類型的詞向量輸入, 雖然詞向量有很多維度, 但是知識之間沒有組織結構(當然, 依存關係屬於結構化表徵的一種.)
這裡的結構化計算應該針對的是如今單純的數值運演算法, 雖然存在著 pooling 等等的非連續性計算單元, 但是缺乏邏輯性的本質還是沒有改變, 現1在使用的神經網路雖說是利用數值運算去模擬邏輯運算, 但是由於數值運算的連續性和邏輯運算的離散性的差異(還有什麼其他的原因嘛?), 使得兩者之間存在著一定的距離.
組合泛化
這裡我的理解就是 :
組合泛化指的是, 將不同的關係和實體進行組合可以產生無限的生成能力, 參照自然語言.

任務描述
如何利用關係歸納偏置去 幫助深度模型 去學習實體,關係以及組織他們的方法.

注意 : 核心模型還是深度模型.
關係歸納偏差是:

歸納偏差:詳見2.0.2節
關係歸納偏差
詳見2.0.3節

graph network
這裡去實現該歸納偏差(假設模型)的架構是 graph network.

這是一個基於圖操作的神經網路, 再次之上可以添加各種各樣的方法
難道是在神經網路中嵌入特徵嘛?如果是的話, 那和增加特徵最為輸入有什麼區別呢?如果不是的話當我沒說.
可以操作結構化知識和產生結構化行為
接下來會討論, graph network如何支持關係推理和組合泛化. 這裡的推理系統是複雜的, 可解釋的, 以及靈活的.
可解釋的應該是針對於網路模型的缺點. 靈活的對應的是純邏輯推理, 例如semantic parse的缺點. 複雜的? 大家都很複雜啊

1. Introduction

定義

Combinatorial generalization
組合泛化對應的是語言的可以無限生成的能力, 從有限的辭彙和規則中,通過組合可以生成無限的序列和意義. 準確定義為:
Construct new inferences, predictions, and behaviors from known building blocks.
現在NLP的很多任務都是在做這樣的工作, 例如神經翻譯系統.神經翻譯系統的known building blocks中, 辭彙是已知的, 還會加入依存序列信息, 但是其中的最重要的inference(翻譯)的信息是隱藏在數據中, 然後希望可以通過表現力強大的神經網路去學得這個信息.
個人認為還是要有一些顯式的block, 也就是規則或者邏輯(一階邏輯等等)作為已知信息.
認知機制
對關係的複雜心理結構表徵, 以及基於關係的推理, 構成了人的認知系統, 而認知系統衍生了人類強大的組合泛化能力. 相關論文見論文列表1?.
人可以利用層級結構去高度抽象細粒度的差異, 並且可以找到表徵和行為的一般性行為!!!!
這個應該是很多做NLP都想去做的事情, 每個人或多或少都想過一些, 下面是我的個人理解 :

概念闡述
一個實體或者關係的表徵毫無疑問是具有層級性或者說結構性的, 暫且不論這個結構是怎麼樣的(個人認為是樹狀, wordnet也是樹狀). 這個結構中肯定在較高層次(個人認為是最高層次)的抽象中, 擁有兩個向下分的憑據 - 類型屬性以及認知屬性.

認知屬性決定的是這個事物是如何被人感知的. 是一種可以獨立於其他語義而存在的結構. 它的習得是憑藉人類的原始感知能力, 我感覺大致分為三種, 對時間的感受(時序性), 對空間的感受(空間模型), 以及自身的生理結構的內部感受(體感以及情感等等). 認知屬性的特點是結構複雜, 但是基本要素不多.
類型屬性決定的是, 這個食物在現實世界中由於經常的共同出現而被聯想起來的結構.是完全依存於語義之間的關係的. 結構簡單但是基本要素很多.

舉例闡述
比如說, "泄漏"這個詞, 會想到兩個用法.

泄漏情報
液體泄漏

例子分析
這同一個辭彙在兩個意思下描述的是不同的事情, 但是兩種存在著一種共性. 這種共性就是認知屬性, 下面是自己的描述:

泄漏的認知意義描述 : 實體E在被動的情況下從空間S1以某種形式移動到了空間S2.
其中, 實體E, 空間S1, 空間S2 都是人可以通過對空間進行感知感受到的東西. 而被動是主格本體和其他本體之間存在的一種關係, 是屬於生理結構的內部感受
泄漏的類型意義描述 : 這裡就可以用於簡單的分類. 信息類別和液體的類別, 這個也許通過wordnet就可以辦到.

實際研究領域相關
大致的分類的話, 個人感覺圖像能夠得出認知屬性中的信息(二維空間以及時間信息(基於視頻)).
plain text 的話, 雖然其中包含的最表層的信息是只基於類型的, 但是由於語言中存在著實體以及關係之外的描述辭彙. 因此可以從中習得認知屬性, 但是相比與直接的感知而言, 挖掘出認知屬性會是相當複雜的過程.
強調
由於這個只是自己在沒有相關認知學基礎上的胡思亂想, 所以還是想給自己的描述加上一些條件.

這裡只是舉出了兩個抽象等級較高的分類標準, 分類的層次不一定是最高, 但是這一個層次內應該只有這兩個分類標準.
第二, 其下面還有很多細粒度的分類標準.

利用知識的層級結構可以進行泛化.
例如上面說的例子, 在得知泄漏這個辭彙可以和情報一起使用後, 我們怎麼對泄漏的使用進行泛化呢?

已知條件: 一些實體和關係的一部分認知屬性和一部分類型屬性, 實例->"泄漏情報"
求解問題: "泄漏"可以搭配的辭彙
方法: 假設已經知道了泄漏擁有一個認知屬性(即上面那個), 但是不知道其相應的搭配, 通過實例之後, 我們不僅知道了泄漏可以和情報搭配使用, 我們還知道了這種認知屬性可以和那種類型屬性一起搭配使用, 因此我們就可以將"泄漏"搭配上其他同屬於"信息"類型的辭彙, 例如-> "泄漏數據"

這種泛化其實是基於一個很強的假設:

實例類的可組合性是抽象類可組合性的充分必要條件.

這個例子裡面, 具體的單詞的某個詞義就是實例, 這個詞義的認知屬性以及類型屬性就是抽象類

其實像很多analogy之類的認為其實都可以認為是這個本質.

The Nature of Explanation
接著論文引用了1943年的一段文字, 用來解釋 "解釋的本質". 是學術界對人去理解解釋世界的模型.
簡單來說, 上面我個人的理解是將抽象和類型完全進行了分離. 這個模型,使用的是範疇中的原型概念(認知語言學相關概念). 一個範疇中的一些原型辭彙的使用方法, 決定了同一個範疇內的其他辭彙和概念的使用方法. 這就使得, 有限的結構化的知識在接受有限的實例後可以擁有了無限表示的能力, 也就是說他將範疇內的原型的組合方法拓展到了其他的同範疇內的其他辭彙.
我們在學習的時候(接受一個正確實例的時候), 可以做兩個事情

將新的知識放入已有的結構化知識框架.
調整框架去適應新的知識.

現在的實現組合泛化的理論
logic, grammars, classic planning, graphical models, causal reasoning, Bayesian nonparametrics, and probabilistic programming
其下面的子領域都明確的以實體和關係為中心進行學習
為什麼結構化的方法如此重要?
這也是本文強調的一個重點, 結構化對應的是這篇論文的主題, 也就是關係歸納偏置. 其對應的是神經網路模型,深度網路模型中的弱歸納偏置, 深度網路的端到端的設計哲學通過最小先驗表示來計算優化和計算的, 並且使用的是簡單結構, 以及儘可能的避免人工特徵, 但是這樣就需要大量的數據和大量的計算時間. 並且其無法解決一下幾種問題:

複雜的語言以及場景的理解
結構化數據的推理
不同訓練條件下的遷移學習
小數據量的任務

關於批評深度模型的論文見論文列表2. ?

弱歸納偏執對應的是數據的低學習效率, 也就意味著需要大量的數據.

但是數據是非常昂貴的(在特殊領域確實是這樣, 並且需要應用的任務大部分都是特殊領域內的問題, 比如說上面提到的結構化數據的推理). 因此通過增強歸納偏置來提供一個結構化的方法是非常重要的.

結構化方法和現在深度方法一定是對立的嘛?

早期的結構化方法
這些是早期的連接主義學家面對結構化數據和問題時提出的一些解決方法:

類比決策?(analogy-making)
語言學分析
符號理論
其他見論文列表3?

近期與連接主義的結合
利用這些理論, 出現了一些使用深度模型去利用分散式的連續的向量表示文本, 圖, 幾何和邏輯甚至編程的方法. 詳細見論文列表4?
這些論文提出, 結構化和靈活性並不是對立的!!!!!. 我們應該將兩者的組合泛化作為今後的目標!!!!!並且提出了一些相關的研究. 這些研究都表現出了很好的效果. 詳細見論文列表5?.
這些論文中的方法都有一個很大的特點就是:
performing computation over discrete entities and the relations between them.

這個真的很激動人心!!!!!!!!!!!!!
在之前看有關認知學的書的時候, 就看到過人的思維既擁有連續特性, 又擁有離散特性的特點, 這裡注意到了這個並進行了分析!!!!!!
符號主義(離散)和連接主義(連續)結合的思想
具體可以看論文 : Mitchell, T. M. (1980). The need for biases in learning generalizations
然後, 我們其實很容易就可以想到這一點, 就是學習知識需要離散和連續表徵, 但是到目前的經典方法無法實現這個的原因是, 不知道如何去學習實體和關係的結構表徵, 以及對應的計算的方法表徵(即將其轉換為計算機可理解的形式),而要想解決這些問題, 繼續要事先指定他們
解釋一下上面加黑的一句話:
最後的他們指的是, 實體關係的抽象結構的表示方法, 不是說制定具體的關係和實體有什麼關係, 知道了這些也就沒必要學習直接應用就好了. 這裡需要提前指定的是這些實體, 關係以及方法的抽象表示法.比如說:
我們要想去學習DNA的結構, 就需要提前指出, DNA之間的組成結構是雙螺旋結構.
要想學習化學分子和其間關係的, 就需要提前指出, 化學分子其轉化應滿足的基本原則, 比如物質守恆, 能量守恆, 價守恆等等(化學忘完了, 胡縐的,大概這個意思)
而這種解決方法就需要強關係歸納偏置去約束, 約束的具體形式就是設計一些特殊的結構, 這些結構可以引導對實體表徵和關係表徵的學習.
更多具體方法見論文列表6?

接下來的文章構造介紹

介紹目前的已經出現的一些強關係歸納偏置模型
其實這種思想一直有人在用, 但是都沒有意識到其本質.這裡想到於用例子去解釋.
其實, 筆者認為, CNN, RNN, attention , 甚至DNN等等劃時代模型的背後都有著對應的歸納偏置.(個人看法不一定正確)
CNN是利用到了臨近單元具有某種特殊關係的假設; RNN用到了序列的時序性假設;attention利用的是信息量的信息表達形式的不平衡假設;DNN用到的是知識的多層級性假設.
這些就是一種對知識的結構性描述.
提出一種通用框架去描述基於實體和基於關係的推理, 也就是graph network. 統一併擴展了現在基於圖的處理方法, 並描述了使用graph network作為基本單元處理時的核心設計思想.
其實看到這裡, 大概知道文章想做什麼了.
這篇文章想要把所有的神經網路框架做一個抽象化, 即用一個抽象的方法去表示所有的模型.
比如, 把CNN抽象成一個圖. 或者把RNN抽象出一個圖. 等等.
從中去發掘設計結構化知識思想的本質.

2. Relational inductive bises

2.0 基本概念解釋

2.0.1 relational reasoning

詳見筆記 [知識點筆記]:結構化表徵和結構化計算.

圖模型是機器學習中用來處理關係推理的方法之一. 圖模型可以通過明確隨機變數之間的隨機條件獨立性來表徵複雜的聯合分布. 該模型可以捕捉構成真實世界的生成過程的稀疏結構.

文章還講了幾種圖模型的具體演算法, 自己看吧.

感覺這篇文章應該是用圖模型去抽象化深度模型

2.0.2 Inductive biases

歸納偏差解釋詳見筆記 [知識點筆記]:歸納偏差

2.0.3 關係歸納偏置

深度學習中的各種模型其實就可以看作是由不同的初級building block組成的複雜的深層的層級結構或者圖結構.

注釋 : 下面說的 block 就是在2.0.1中提到的 "個體".

初級building block包括, 「fully connected」 , "convolutional layers"等等等等很多.

複雜的結構, 例如 MLP就是由多個「fully connected」組成的. 這個時候, "MLP" 也可以作為一個block.

而CNNs就是由 "convolutional layers" 和 "MLP" 組成的一個新的block.

最重要的是, 不同的block都包含著不同的 "relational inductive biase", 也就是不同的設計指導思想.

下面是幾個例子:

除此之外, 還有還有很多 no-relational inductive biase.

activation non-linearities
weight decay,
dropout ,
batch and layer normalization ,
data augmentation, training curricula
optimization algorithms all impose constraints on the trajectory and outcome of learning.

這些稱為非關係歸納偏置, 與上面的關係歸納偏置進行對比, 我們就可以大概知道:

關係歸納偏置是應用了關係推理的歸納偏置. 是具有生成能力的.

2.0.4 推廣到深度模型

將 relational reasoning 推廣到深度模型的話就是:

entities和relaitions是分布表徵. 也就是不同block的輸出.

rules是 neural network function approximators(神經網路函數逼近器)、也就是各層之間的激活函數.

事實上, 這裡對三者的定義沒有和前面舉的例子完全吻合. 我也搞不清三者的抽象定義到底是什麼.
現在只考慮深度模型中的 entities, relations和rules.
entitis就是模型中的unit, 一般都是框架中的variable變數. 就是模型圖中的小圈圈.
relations是制定那些unit和哪些unit之間有聯繫, 就是模型圖中的連線. 包含weight, bias這些變數, 以及sigmoid函數或者ReLU這些個激活函數.
rules是制定連線之間進行的操作.

每個深度模型的entities, relations 和 rules都是不一樣的, 為了更好的理解他們, 這裡定義了幾個術語.

arguments : 是 rule functions的輸入, 就是entities和relations
reused, shared : 指的是 rule functions 是否被reused或者shared(也就是說不同relation(連線)之間是否使用相同的rules(激活函數,不同權重算不同函數)).
interactions, isolation : 得出的結果是全部entities之間協作的結果的話就是interactions, 否則就是isolation.

2.1 深度模型中的關係歸納偏置

2.1.1 Fully connected

entities : the units in the network
relations : all-to-all
rules : specified by the weights and biase
The argument to the rule is the full input signall, there is no reuse, and there is no isolation of information.
relational inductive bias : very weak, all input units can interact to determine any output unit』s value, independently across output

2.1.2 Convolutional layers

entities : 還是獨立的unit
relations : 是稀疏的, 不再是全部連接.
關係歸納偏置 : locality and translation invariance

locality : 意思是空間相近的實體有聯繫遠的沒有.
translation invariance : 局部單元對於rules(卷積子)的復用,Spatial translation

遠距離單元之間是isolated 的

2.1.3 Recurrent layers

rule : 接受 a step』s inputs 和 hidden state作為arguments.
reused : The rule is reused over each step
relational inductive bias : temporal invariance
全部是Interaction.

2.2 Computations over sets and graphs

2.2.1 具有處理結構性知識的模型是什麼樣的?

一句話總結
這個論文想做的一個是實體和關係的明確表示和抽象化數學定義, 以及利用這種數學定義去表達知識中的結構特性.
我們到目前的關於模型的定義通常採用圖示,以及一些特殊的定義, 並沒有賦予他們在一個廣義框架下的明確的定義方式.
並且我們還有設計一個學習演算法去找到他們的方式, 也就是rules. 也就是合適的參數.
真實世界的物體之間通常是沒有order的, 但是, 他們之間的order是可以通過他們的屬性的關係去決定的.
例如, 詞向量的順序.
順序的不變性, 應該是需要通過深度模型的結構或者組件進行規範和反映的, 這樣的模型結構就具有了 (一定程度的)relational reasoning 的能力.
這裡強調了結構性知識的順序性, 但是結構性知識應該還具有其他特性, 例如兩個知識的離散可操作性?(個人定義), 或者下面提到的知識的相互無關性和成對交互性等等.
相互無關性和成對交互性的例子
這裡以相互無關性為例去給了一個具體的結構性知識的屬性去展示如何通過改變模型結構去"支持"這種屬性.
這裡我對"支持"用了引號. 是因為, 一個結構屬性對於一個模型而言, 不應該是存在不存在的問題(relational inductive bias does not come from the presence)
而應該是缺少不缺少的問題. (but rather from the absence)
存在和缺少是有本質差距的, 下面是我對其的理解.
這裡存在四個實體(認知概念上的實體) - 用滅霸的手套來舉例

一個模型(大框架) - 對應著滅霸的無限手套
一個待處理的任務 - 對應者 - 要消滅一般的生物
多個模型中處理結構性知識的能力 - 對應者 - 需要控制時間, 力量,心靈, 吧啦吧啦
任務(知識)所擁有的結構性屬性 - 對應著- 時間寶石, 力量寶石, 心靈寶石

這樣我們就大概明白了, 當一個模型沒有處理一種結構知識屬性的話, 他就像手套上少一塊寶石, 有一個空洞!!!!

上一個黑點我們說了知識的順序性, 但是這個也是相對於具體任務的, 對於某些任務是不需要使用順序性的.例如利用已經知道的星系中的行星位置重量體積等信息去計算這個星系的中心位置. 這個問題中, 我們就不需要使用知識的順序性, 反之這個裡面擁有知識的相互無關性, 也可以理解為對稱性. 其相應的結構叫做 Deep Sets model .

文章中還舉出了當求解的是各個行星在一段時間之後的位置的時候, 需要利用到新的特性 - 成對交互性(全部成對交互), 這裡就不細說了.

一些其他的結構
這裡以上面的 相互無關性 和 成對交互性(全部) 作為兩個極端, 提出了一些中間結構 成對交互性(部分):

我的思考:

這個裡面其實只用到了一個二元關係去表達實體(unit) 之間的關係(relation), 即關係是 0或者1.

如果將 rules 考慮在內的話, 就可以表示多元關係. 上面說, 將會設計學習演算法去學習 rules. 拭目以待吧.

3. Graph networks

本章組成, 首先簡介過往有關 graph nerual network 任務. 其次, 提出自己的 graph network framwork.

3.1 Background

第一段, 首先介紹了很多利用網路模型做的任務, 很多很多, 裡面提到了幾個感興趣的研究,記在論文列表6.

第二段, 介紹了一些利用個網路模型去解決需要對離散的實體和關係進行推理的任務, 例如組合優化問題, boolean satisfiability(布爾可滿足性問題), 以及 performing inference in graphical models等等,還有一個很有趣的方向是 building generative models of graph, 對這四個方向感興趣的論文列表7.

最後一段, 更多的有關graph neural networks的論文, 見論文列表8.

這一節非常非常重要, 介紹了很多很有趣的方向.

3.2 Graph network (GN) block

3.2.0 Introduction

一句話總結
GN框架基於圖結構表徵(表示), 定義了一組用來進行關係推理的函數.
defines a class of functions for relational reasoning over graph-structured representations
功能
最重要的功能是,
supports constructing complex architectures from simple building blocks
就是從一些基本的 building blocks 去構建複雜的結構.(並且後續會發布新的框架.)
組成

GN框架的基本單元是 GN block.
輸入是graph. (表現在網路中就是unit, 結合任務比如說神經翻譯,就可以是詞向量, 字元向量等等)
輸出是graph
執行的是基於結構的計算, 也就是最最開始說的 structural computation.
graph 的 node 是實體(entities), edges 是關係(relations)

具體的見 3.2.1 節.

3.2.1 Definition of 「graph」

graph 的定義

node ? $v_i$ : 擁有屬性 attribute, 抽象含義是一個node, 具體值是 attribute ? $v_i$ .
? $V = { v}_{i =1: N_v}$ , 是所有nodes的集合
edge ? $e_k$ : 擁有屬性, 抽象含義是一個edge, 具體值是 attribute ? $e_k$
? $E = { ( e_k ,r_k ,s_k ) }_{k =1: N_e}$ , 是所有edges的集合. 其中 $r_k$ ?,? $e_k$ 是輸入的子圖或者node的indice
全局屬性 $u$ ? : 圖的全局屬性.

上面是三個基本組成元素.

"sender" node $v_{s_k}$ ? : edge $e_k$ ? 的發射端node
"receiver" node ? $v_{r_k}$ : edge $e_k$ ? 的接受端node

3.2.2 Internal structure of a GN block

GN Block 的構造

三個更新函數
三個更新函數中含有三個聚合函數

對每一個邊的狀態進行的更新:

圖示(藍色為輸出, 黑色為輸入):

對每一個節點的狀態進行的更新:

其中,

他是一個聚合函數, 其接受參數為一個邊的集合. 然後利用集合中所有邊的信息去調整一個node的狀態.

圖示:

對全局狀態進行跟新.

其中包含兩個聚合函數,

第一個, 其接受參數為一個邊的集合. 然後利用集合中所有邊的信息去調整全局狀態.
第二個, 其接受參數為一個點的集合. 然後利用集合中所有點的信息去調整全局狀態.

圖示:

聚合函數需要具有的特點

對於參數的順序不敏感
可以接受不定數的變數
舉例 : elementwise summation, mean, maximum

個人總結
可以注意到, 這個GN Block並沒有指定具體的node數和edge數, 其定義的只是點之間, 邊之間, 點和邊之間, 以及點, 邊, 圖之間的關係. 相當於生成語法中定義了終端子, 非終端子, 文法等等這樣的感覺, 剩下的就只是如何去組合.

3.2.3 Computational steps within a GN block

演算法:

這裡的先對哪部分函數進行更新並不是一個定值, 而是可以選擇的.

3.2.4 Relational inductive biases in graph networks

這個地方又重新開始精彩了!!!!!

在第三章之前我們一直在強歸納偏置的重要性, 那麼在這裡將要介紹這個架構如何去實現強歸納偏置!!!1

graph本身可以根據實體和關係去設計!!!!
在之前的網路結構中, 我們通常是對node沒有進行關於輸入的分別, 而是一視同仁, 即任何辭彙都可以instantiated到每個node. 但是, 其實(為了準確, 放上原文):
graphs can express arbitrary relationships among entities, which means the GN』s input determines how representations interact and are isolated, rather than those choices being determined by the fixed architecture.
個人理解是, graph的node之間的關係是可以根據對node的輸入來定的, 這樣的話, 網路架構就會變成一個動態的架構!!!
圖關於entities和他們之間的relations是的表徵是基於set的. 也就是說, 對於參數位置的交換是沒有反應的. GN block對於參數的順序不敏感, 這個就支持了對於很多對順序不敏感的模型的支持.
每個node和每個edge都是可以被複用的, 這個就支持了組合泛化. 這個是相當重要的. 在決定了GN block後可以根據實例改變size以及shape.

4. Design principles for graph network architectures

上面說的是最廣義的GN block. 下面針對的是對於深度模型的 graph network 設計規則. 使得GN block 成為一個可學習的 graph-to-graph function approximator.

4.1 Flexible representations

靈活性體現在兩點:

屬性值表徵的靈活性
圖的結構本身的靈活性

4.1.1 Attributes

這裡的屬性值代表的是 edges, nodes, globel 的值.

屬性值的形式
屬性的具體數值形式是依據任務的不同而不同的. 在深度模型中, 通常是採用real value vector or tensor 的形式.
輸出的單元
根據任務的不同, 輸出的東西也是可以不同的. 有三種基本類型的輸出.

edge-focused GN : 採取邊作為輸出, 例如下面的研究:

Neural relational inference for interacting systems (必讀)
這個研究是利用變分自動編碼器去模擬物理動力學系統的研究, 也就是說研究的是物體和物體的之間的聯合計算函數. 這個就是很典型的, edge-focused GN 的應用.
Relational inductive bias for physical construction in humans and machine

node-focused GN : 採取點作為輸出. 這個應該就是我們一般的研究.
graph-focused GN : 採取global作為輸出. 例如 predict the potential energy of a physical system.

還可以有三種的混合形式:

Relational inductive bias for physical construction in humans and machine:

這個研究同時利用edge和global去預測一個(人和機器)基於動作的策略.

4.1.2 Graph structure

圖的結構有兩個極端, 一個是實體顯式地決定其之間的關係結構. 一個是, 關係結構必須被推斷或假定. 也可以採取兩者的混合.

第一個方式的例子:
知識圖譜以及句法樹以及社會網路問題, 這樣的問題中, edge是根據其相連實體來確定的.也就是說, ? 是基於一個知識圖譜或者句法樹等等.
這裡的很典型的例子是 graph LSTM (用於遠距離關係抽取). 在這個研究中, 辭彙和辭彙之間不僅具有臨接關係還具有依存句法關係, 用不同的LSTM關聯起擁有不同依存關係的兩個辭彙, 使用方法是,在LSTM中根據依存標籤來設計參數. 這裡就很能說明這裡的方法了, 因為這裡的 edge 同時滿足了

relation(認知上的定義) - 是兩個實體之間存在的關係.
edge(graph上的定義) - 是連接兩個點之間的線
rules(邏輯上的定義) - 是用來處理兩個entities之間的函數.

graph LSTM與一般LSTM的計算不同如下:

第二個方式的例子:
例如, visual scenes, 自然語料庫等等. 這樣的初始的情況下我們不知道實體之間的任何關係.
具體的例子就是, 將句子中的每一個辭彙視為一個node.
有很多方法去通過非結構性數據去進行推斷.比如說利用attention的機器翻譯.
對於這種沒有關係的數據, 我們可以針對每一個數據實例化一個關係.
或是全部使用同一歸納偏置極其弱的關係? 例如 LSTM.?
但是現在也出來了一些利用非結構性數據推斷出稀疏結構的方法, 如下面的論文:
Neural relational inference for interacting systems (必讀)
發現和上面提到的必讀文章是一致的, 果然這個文章很重要!!!!!!!

4.2 Configurable within-block structure

先放上幾個重要論文, 見論文列表9?

這一節講述了通過定製 GN block 中的函數改變模型功能的案例. 體現了 GN 的靈活性.在上面的3.2.2 節, 我們已經介紹了更新各個變數的基本公式.裡面介紹的是下面幾個網路模型的 GN block結構.

Full GN Block

Independent recurrent block

這裡使用的 $phi$ ? 是RNN

例如 tree Lstms, 但是這裡有關問題是, 不論是什麼模型, 邊和點肯定要進行處理的啊, 這裡的邊和點卻是相互獨立的, 不知道是怎麼更新的.

Message-passing neural network

這個可以用物理動力學系統模擬的那篇文章去理解, 用邊去更新點, 點去更新邊.

Non-local neural network
見4.2.2
只預測節點
Relation network

只預測全局屬性的.

Deep set

沒有邊的信息, 只有點和全局屬性, 這是一個無序,無結構的模型. 比如最開始提到的, 星系中心點預測系統.

4.2.1 Message-passing neural network (MPNN)

不說

4.2.2 Non-local neural networks (NLNN)

這個模型很重要, 這個是基於加權圖模型.

NLNN 使用了various 「intra-/self-/vertex-/graph-attention」方法
attention 是更新node的方法
每個節點的更新是依靠其鄰接點的加權和. 節點i和節點j之間的權重是通過兩者屬性值的a scalar pairwise function 來進行計算的.
NLNN中沒有explictly使用edge embedding的方法, 因為, 這裡只是利用了兩者之間是否互相連接的信息.

這個模型有很多變種, 包括 vertex attention interaction network, 還有 graph attention network.

整個的計算過程如下:

其中這個就是attenton模型的最抽象的結構
我們一開始可以假設輸入(例如句子)中的辭彙之間構成了一個全連接圖. 每個單詞是一個key
然後一整個句子的詞向量是一個query, 這個query的獲取就是 $phi^{e o v}$ ?,
那麼這個全連接圖裡面, 一個key與query 之間的attention的計算就包含在

之中.

4.2.3 Other graph network variants

介紹了很多其他的模型.

反正就是很多很多種模型了...

Interaction Networks ,
Neural Physics Engine
a full GN but for the absence of the global
CommNet
structure2vec
ated Graph Sequence Neural Networks
Relation Networks
Deep Sets

其實看到這裡, 之前的熱情已經消退, 本身以為這篇論文可以教給我們怎麼去挖掘信息中的特殊結構, 但是他只是給了我們一個抽象的理解深度模型方法的框架,但是還是很重要, 感覺看完之後加深了對很多模型的理解

4.3 Composable multi-block architectures

可組合的多block結構.

一句話總結
一個GN block的輸入和輸出都是 graph, 那麼一個Block的輸出就可以當成另外一個BLock的輸入.即:

下面介紹三個組合方式.

Composition of GN blocks

這個裡面, 一個很直觀的例子就是另外一篇論文筆記中提到的物理動力學系統, 這個系統中每個 GN block 可以視為對一個 ? $vartriangle t$ 後系統中 object 的預測, 組合 M 個這樣的 Block就可以視為是預測 ? $M*vartriangle t$ 後object的狀態.

Encode-process-decode

即encoder使用了一個 Block, decoder使用了一個Block, 還有一個處理中間狀態的 Block.

還是物理動力學系統模型的例子, 在這個例子中一整個模型就是一個 Encode-process-decode.

Recurrent GN arch tecture

這個可以用來預測時序的圖結構數據.例如物理動力學系統中隨著時間而不停變化的圖的狀態.

這裡也可以使用LSTM或者GRU.

4.4 Implementing graph networks in code

可設計為並行運行的結構等等.

4.5 Summary

從三個角度講了GNN的設計原則. 是從底到上的順序

4.1 最底層, 從 GN 的屬性設置和graph 邊的設計方法闡釋了 GNN 的靈活性

4.2 從GN 的多種變種闡述了 GNN 的靈活性

4.3 從GN 的組合來闡述靈活性.

5. Discussion

5.0 概述

在上面講了graph network的基本結構, 靈活的使用方法, 這一節講最核心的, 如何使用graph network 去設計複雜的結構去包含強歸納偏執到模型中.

5.1 Combinatorial generalization in graph networks

這一節介紹了證明 graph network 具有組合泛化能力的論文. 見論文列表10?

被設計用來預測One-step的模型可以用來預測上千步.
在object的數量發生變化時也可以保持高正確率.
GN-based決策模型, 在agents數發生變化時也能很好的應對.
還可以生成一些之前沒有的useful node embedding.
等等特性.

這些特性都證明了 graph network 具有 "從有限中生成無限" 的能力, 即組合泛化能力.

5.2 Limitations of graph network

不能解決的一些問題:

非同構圖的判別的問題(不懂)
一些無法用圖表示的結構的問題, recursion(遞歸), control flow(控制流), and conditional iteration(if-then-這些). 這些「computer-like」 processing 是圖無法處理的結構, 但是這些對於人的認知判斷是極為重要的, 也就是說, graph network 雖然很強大, 但是想相比於人的認知能力還是差很多必要因素.
(什麼樣的模型可以整合進這些結構呢?見論文列表11?

5.3 Open questions

這一節的中心點在於, 認為在相比於某一個框架下進行調整(即在某一個模型上添添補補), 更加重要的是認識到 graph network 的全部潛力.

這裡的問題就是圍繞這"潛力"來的.

graph network 操作的 graph 是怎麼得來的?
這個其實是一個最根本的問題. 也就是如何把原始感官數據轉化為有結構的數據, 如今的wordnet, dependency parsing 其實都是在做這個工作.
一個方法就是使用全連接圖, 就是上面提到的attention思想的 Non-local neural networks.
但是實際的結構應該是更為稀疏的. 有一些研究是做推導出稀疏結構的, 因為這部分很重要因此列在這裡.(重要!!)

Visual interaction networks: Learning a physics simulator from video.
Relational neural expectation maximization: Unsupervised discovery of objects and their interactions
Learning deep generative models of graphs.
Neural relational inference for interacting systems.(見論文筆記)

如何在計算的過程中動態的改變 graph 的結構?
比如, 在一個物體分成幾個部分之後, 這個entity的node也應該分為幾個node.
演算法應該具有在計算過程中對edge進行增加和取消的能力.
有兩個研究是基於這個的.(重要!!)

Learning deep generative models of graphs.
Neural relational inference for interacting systems.

5.4 Integrative approaches for learning and structure

強調本文主要在graph network計算部分, 而在設計思路上只給出了以下的幾個方向

(重要!!)

linguistic trees
partial tree traversals in a state-action graph
hierarchical action policies
capsules
programs
模仿計算機的軟硬體結構的方法(難道是可以解決上面提到的graph無法操作的內容?)

詳細論文, 論文中有名稱(懶得寫了)

####5.5 Conclusion

強調了組合優化的重要性.

作者在肯定 graph network的同時, 也承認了他的不足, 並且提供了幾個作者認為有意思的有前途的但是不是很熱門的方向.比較重要, 列在這裡:

Ritchie, D., Horsfall, P., and Goodman, N. D. (2016). Deep amortized inference for probabilistic programs
Andreas, J., Rohrbach, M., Darrell, T., and Klein, D. (2016). Neural module networks.
Gaunt, A. L., Brockschmidt, M., Kushman, N., and Tarlow, D. (2016). Differentiable programs with neural libraries.
Evans, R. and Grefenstette, E. (2018). Learning explanatory rules from noisy data.
Evans, R., Saxton, D., Amos, D., Kohli, P., and Grefenstette, E. (2018). Can neural networks understand logical entailment?

還有一些強調抽象模型方法的論文: (重要!!)

Schema networks: Zero-shot transfer with a generative causal model of intuitive physics.
From skills to symbols: Learning symbolic representations for abstract high-level planning.
Composable planning with attributes.
Behavior is everything–towards representing concepts with sensorimotor contingencies.

元學習相關研究: (重要!!)

Learning to reinforcement learn.
Prefrontal cortex as a meta-reinforcement learning system.
Model-agnostic meta-learning for fast adaptation of deep networks.