xRecurrent.
↑
Networks ← Relational → Learning↓%
Reinforcement
Petar

Veličković

Artificial Intelligence Group
Department of Computer Science and Technology, University of Cambridge, UK
MILA Graph Representation Reading Group Meeting

22 August 2018

Introduction

I In this talk, I will survey the Relational Network architecture,and its recent deployment in recurrent neural networks anddeep reinforcement learning.
I The discussion will span the following papers:

A simple neural network module for relational reasoning(Santoro, Raposo et al., NIPS 2017)
I Relational deep reinforcement learning(Zambaldi, Raposo, Santoro et al., 2018)
I Relational recurrent neural networks(Santoro, Faulkner, Raposo et al., 2018)

I

I Substantial part of DeepMind’s recent “graph networks surge”.

Relational reasoning

I Being able to reason about relations between entities present

in an input is an important aspect of intelligence!
I Consider the simple task of inferring which two points from agiven point set are furthest apart—this requires computing andcomparing all* of their pairwise distances.

I Keep this task in mind—it will be revisited!

Approaches to relational reasoning

I Relations can be naturally expressed within symbolic methods(defined by e.g. the rules of logic)—but these are not robust to
small variations of inputs/tasks.
I Robustness is often achievable with standard neural networkarchitectures (such as MLPs), but it is extremely challenging
for them to capture relations, despite their theoretical potency!
I

This claim is extensively validated throughout the three papers.

=⇒ Seek a model inspired by symbolic AI, while empowered byneural networks (explicitly represent relations in a robust way).

Our task for today

~o♦

♠

♣

♦

~o♣

♥

~o♥

input

~o♠

"How many outlined objects
are above the spade?"
query

"two"
outputOur task for today

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

"two"
outputOur task for today

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

RN

"two"
outputOur task for today

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

RN

"two"
outputThe Relational Network

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

RN

"two"
outputRelational Networks

I Initially, we will assume that the objects are provided as input.
I Consider a set of n objects, O = {~o1 , ~o2 , . . . , ~on }; with eachobject represented by a feature vector ~oi ∈ Rm .
I A Relational Network (RN) summarises the relations between

these objects as follows:X
RN(O) = fφ gθ ~oi , ~oj i,jwhere gθ : Rm × Rm → Rk and fφ : Rk → Rl are functions withparameters θ and φ (usually MLPs).

Properties of RNs

I The central component of RNs is gθ ; the relation function. Itsrole is to infer the nature of relations between objects i and j.
I An RN may be seen as a message-passing neural network

over the complete graph of object nodes.
I RNs have several highly desirable properties:

Relational inference—given the all-pairs nature of thecomputation, the module does not assume upfront knowledge of
which pairs of objects are related, and how.
I Data efficiency—an MLP would need to learn and embed n2(identical) functions to replicate behaviour of RNs.
I Permutation invariance—the summation operation ensuresthat the order of objects does not matter; therefore RNs can beapplied to arbitrary sets.
IDynamic physical systems
MuJoCo-simulated physical mass-spring systems with 10 objects.

Input: ~oi is RGB color and (x, y) coordinates across 16 time steps.
Tasks: (i) infer relations; (ii) count number of systems (harder!).

Results on physical systems

I Relational Networks achieve 93% accuracy in predicting theexistence/absence of relations between objects, and 95%
accuracy in predicting the number of interacting systems.
I MLPs fail to predict better than chance on either task!
I Learnt function transferable to unseen motion capture data!

Conditioning in RNs

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

RN

"two"
outputRN conditioning

I An RN may be seen as a module that “captures” the relations

between objects in a set—this computation may be arbitrarily
conditioned, e.g. to answer a specific relational query.
I Assuming we have a conditioning vector ~q , the RN architecture

may be trivially modified to include it:XRN(O, ~q ) = fφ gθ ~oi , ~oj , ~q i,jThe CLEVR dataset (Johnson et al., 2017)
Question Answering dataset on 3D-rendered objects.
Original Image:Non-relational question:
What is the size ofthe brown sphere?

Relational question:
Are there any rubber
things that have thesame size as the yellow
metallic cylinder?

Input: ~oi is RGB color, (x, y, z) coordinates, shape/material/size.
Queries: count, exist, compare numbers, query attribute,compare attribute.

Results on CLEVR

I The query sentence is encoded into ~q as the last-stage output

of a word-level LSTM (with learned word embeddings).
I Relational Networks achieve an accuracy of 96.4% on CLEVR.

I Human performance is 92.6%! This sounds great!

I ...

Results on CLEVR

I The query sentence is encoded into ~q as the last-stage output

of a word-level LSTM (with learned word embeddings).
I Relational Networks achieve an accuracy of 96.4% on CLEVR.

I Human performance is 92.6%! This sounds great!

I . . . OK, I lied to you. (Sorry!)

The actual CLEVR dataset (Johnson et al., 2017)
Visual Question Answering dataset on 3D-rendered objects.
Original Image:Non-relational question:
What is the size ofthe brown sphere?

Relational question:
Are there any rubber
things that have thesame size as the yellow
metallic cylinder?

Input: The scene image. The ~oi vectors are not explicitly given!
Queries: count, exist, compare numbers, query attribute,compare attribute.

Object extraction

♠

♣

♦

input

♥

♦

~o♦

♣

~o♣

♥

~o♥

♠

~o♠
objects"How many outlined objects
are above the spade?"
query

RN

"two"
outputObject extraction from images

I In general, we should not assume the ~oi will be given!
I Arguably, obtaining the ~oi from raw input will be the mostvariable pipeline component.
I Often, we can obtain object representations as high-level

outputs of neural networks specialised for such inputs.
I In the case of images (most common!) this will be a

convolutional neural network.

CNN object extraction

I A convolutional architecture generally consists of interleaving

convolutional and pooling layers—progressively building moresophisticated feature maps.
I At any point during a CNN, a feature map f may have theshape n × m × k , where n and m are the height and width of
the feature map, and each pixel is represented by k features.
I Each pixel represents a summary of a certain region of theimage. Without any further assumptions, it is safest to let eachpixel constitute an object!
I Therefore, we will have an object set O = {~o1 , . . . ~on·m } withn · m objects and ~oi ∈ Rk that will correspond to ~fxy .

CNN object extraction

input

Conv.

Pool

Conv.

f

CNN object extraction

input

Conv.

Pool

Conv.

~o1 ~o2~o3 ~o4Overall CLEVR architecture

Final CNN feature maps

RN
Object pairwith question

object

-MLP
-MLP

*

...

...

Conv.

+
Element-wisesum

What size is the cylinderthat is left of the brown
metal thing that is leftof the big sphere?

...
what size is ... sphere
LSTM

End-to-end trainable with gradient descent.

smallActual results on CLEVRFirst approach to achieve superhuman performance on this task!

Actual results on CLEVR

Accuracy

compare numbers
1.0
0.5
0.25
0.0
overall

count

exist

query attribute

Accuracy

Human
CNN+LSTM+RN
CNN+LSTM+SA
CNN+LSTM
LSTM
Q-type baseline

0.75

more
than

less
than

query
color

comparesize

equal
compare attribute

1.0
0.75
0.5
0.25
0.0

query
size

query
shape

query
material

compareshape

comparematerial

comparecolor

Especially excels at compare attribute, the query type which
heavily relies on relational reasoning.

Failure cases on CLEVR

Failure inputs are often occurring under heavy
occlusion—challenging for humans as well!

Results on Sort-of-CLEVR

A simple CLEVR-inspired dataset with clear separation of relational
vs. non-relational queries.

Demonstrates clear advantage of RNs on relational queries.

LSTM object extraction: bAbI (Weston et al., 2015)

A text-based set of 20 question-answering tasks.

Let O = {~o1 , . . . , ~o20 } be the LSTM representations of up to 20
sentences preceding the question. ~q is once again obtained as the
LSTM representation of the question.

Results on bAbI

I RN(O, ~q ) passes (95+% accuracy) 18/20 tasks after joint

training—comparable with other state-of-the-art memory
network architectures.
Memory networks: 14/20
DNC: 18/20
I Sparse DNC: 19/20
I EntNet: 16/20
I
I

I Does not catastrophically fail (91.9% and 83.5% accuracy) on

the remaining two.
I Notably, it succeeds on the basic induction task (97.9%), where

Sparse DNC (46%), DNC (44.9%) and EntNet (47.9%) all fail.

Self-attention

I Thus far, the building block functions of a Relational Network(fφ , gθ ) were simple MLPs.
I For more recent RN architectures, we focus instead on the

self-attention operator.
I A self-attentional operator, Aθ , acts on a set of n entities,

E = {~e1 , ~e2 , . . . , ~en }, producing higher-level representations:
Ee = Aθ (E)where Ee = {~e10 , ~e20 , . . . , ~en0 }, and θ are learnable parameters.

Self-attention, cont’de will be derived by examining all
I Each component of E
components of E (by way of linear combinations):X~ei0 =
αij fψ (~ej )jwhere fψ : Rm → Rk is a learnable transformation.
I Here, the coefficients αij correspond to the importance of thefeatures of entity j to entity i, and are derived by a learnableattention mechanism, aφ : Rm × Rm → R:
αij = aφ (~ei , ~ej )Self-attention
~e0j
Σ

×

×

×

α1,j

αj,j

αn,j
fψ

fψ

aφ

aφ

~e1

...

~ej

fψ

aφ

...

~en

The Transformer architecture
I In particular, the Transformer architecture (Vaswani et al.,2017) is used for Aθ .
I

Here abbreviated as MHDPA (multi-head dot-product attention).

I First, derive queries, keys and values for the attention:~qi = Wq ~ei~ki = Wk ~ei~vi = Wv ~ei

I Now, use the queries and keys to derive coefficients:√ 
exp h~qi , ~kj i/ dk
αij = P√ ~~m exp hqi , km i/ dk
where dk is the dimensionality of the keys.

The Transformer architecture, cont’d

I Now, can use αij to recombine the values at each position:~ei0 =

X

αij ~vjj
I Can be conveniently written in matrix form as:
Ee = softmax

QKT
√
dk


V

I Further optimised by using multi-head attention; replicating

this operation K times (each with independent parameters Wq ,Wk , Wv ) and featurewise-concatenating the results.

Reinforcement learning: Box-World and StarCraft II
Box-World: A grid RL environment meant to stress relational
reasoning while deciding how to act.
StarCraft II: Mini-games (Vinyals et al., 2017).

In both cases, agent receives pixel-structured inputs (minimaps,
screens, etc.).

Relational deep reinforcement learning

I Empowers a standard CNN-based policy network (in an RL

setting) with a relational module based on self-attention.
I

Architectures for both tasks are very similar!

I Extract entities, ~ei , just as before (as separate pixels in ahigh-level feature map).
I Then perform several rounds of the Transformer self-attention

over E (each round followed by a small MLP, fθ , and layer
normalisation to introduce nonlinearity).
I Finally, perform global pooling and a small MLP to derive thepolicy for the RL algorithm (IMPALA (Espeholt et al., 2018)).

The Box-World architecture

ReLU

x4

FC 256

Multi-head dot product attention

Feature-wise
max pooling

query

Relational
module

key
value

Input

...

...

Conv. 2 x 2, stride 1

...

x2

ReLU

Results on Box-World
1.0

Underlying graph
Fraction solved

Branch length = 1

Observation

0.8
0.6
0.4

Relational (1 block)
Relational (2 blocks)
Baseline (3 blocks)
Baseline (6 blocks)

0.2
0.0

0

2

4
6
8
10
Environment steps

Fraction solved

Branch length = 3

1.0

12

14
1e8

7

8
1e8

Relational (2 block)
Relational (4 blocks)

0.8
0.6
0.4
0.2
0.0

0

1

2

3
4
5
6
Environment steps

Visualising the attentional coefficients

Zero-shot experiments in Box-Worlda)Longer solution path lengthsb)Withheld key
Not required
during training

Relational

Baseline

0.8
0.6
0.4
0.2
0.0

1.0
Fraction solved

Fraction solved

1.0

n. 4 6 8 10
ai
Tr
Test

a
Tr

.
in 4 6 8 10
Test

Relational

Baseline

0.8
0.6
0.4
0.2
0.0

a
Tr

.

in

t

s
Te

in

a
Tr

.

st
Te

The non-relational baseline (ResNet CNN) fails to generalise!

Results on StarCraft II

Sets new state-of-the-art, often beating human grandmaster.

Zero-shot experiments in StarCraft
200
Relational
Control

Mean score

150

100

50

0

1 marine

2 marines

3 marines

4 marines

5 marines

10 marines

Exhibits higher—although not fully conclusive—generalisation
ability from 2 marines to higher numbers.

Neural networks for sequential processing

I Finally, we turn our attention to architectures used for generalsequential processing of data.
I In the general setting, we require a stateful system, Sθ , capableof processing incoming inputs ~xt , and updating its internal
state, ~st , appropriately:~st = Sθ (~xt , ~st−1 )I Inference may then be performed by leveraging ~st .

Approaches to sequential processing

I Traditional approaches for modelling Sθ include recurrent

neural networks (e.g. LSTM, GRU, etc.) andmemory-augmented neural networks (e.g. NTM, DNC, etc.)

I Recurrent neural networks generally represent their state as afixed-size vector, ~ct , which gets appropriately updated at eachstage of input processing.
I Memory-augmented networks have a memory matrix,
M ∈ Rn×m , which may be read from/written to by using arecurrent controller.

Analysis of approaches

I Both approaches have shortcomings when explicit relational

reasoning through time is required:
RNNs pack entire representation in a single dense vector,
making it hard to reason about entities (and therefore relations);
I Memory-augmented networks explicitly represent entities (asrows of M), but these cannot easily interact once written to.
I

I Relational recurrent neural networks address both

shortcomings simultaneously, explicitly allowing rows of M tointeract using self-attention!

Relational memory

I Assume we have a memory matrix M = {m
~ 1, m~ 2, . . . , m~ n }.
I Applying (Transformer) self-attention to it, we obtain a new
f = {m~ 10 , m~ 20 , . . . , m~ n0 }, explicitly taking intomemory state M~ i:account the relations between memory rows mTQK
f = softmax √
V
M
dk

where
Q = MWq
just as before.

K = MWk

V = MWv

Incorporating new inputs

I The interactions thus far are self-contained to what’s already inthe memory; however, we’d like the memory to adapt toincoming inputs, ~x , appropriately.
I Simple extension: let the memory locations attend over ~x too!

f = softmax
M

Q[KkWk ~x ]T√dk

where k denotes row-concatenation.

[VkWv ~x ]The LSTM controllerf
I We do not wish to fully overwrite M by M—cancontrol thisprocess with an LSTM:


~ii,t = σ Wi ~xt + Ui ~hi,t−1 + ~bi~fi,t = σ Wf ~xt + Uf ~hi,t−1 + ~bf~oi,t = σ Wo ~xt + Uo~hi,t−1 + ~bo
0~ i,t = gψ (m~ i,t~ i,t−1m) ~ii,t + m~hi,t = tanh m
~ i,t
~oi,t

~fi,t

where gψ is a learnable function (2-layer MLP with layer
normalisation in the paper).

The Relational RNN
Output

MULTI-HEAD DOT PRODUCT ATTENTION

CORE

MLP

Residual

Residual*
Apply gating

Input

value

Next
Memory Input***computation of gates not depicted

(b)

(a)
Compute attention weights
Queries

UpdatedMemorykey

Memory

+

A

+

Prev.
Memory

query

Keys

Normalize weights with row-wise softmax Compute weighted average of values Return updated memory

Weights

Normalized Weights

Weights

Values.
.
(c)

Updated Memory

Tasks under consideration
A suite of supervised and reinforcement learning tasks demanding
explicit sequential relational reasoning.

Nth farthest

Lock

Key

What is the Nth farthest from vector m?

Super Mario Land is a 1989 side
scrolling platform video _____

x = 339for [19]:x += 597
for[94]:x += 875x if 428 < 778 else 652
print(x)It had 24 step programming
abilities, which meant it was highly _____

Program Evaluation

Language Modeling

Loose KeyA gold dollar had been proposed several
times in the 1830s and 1840s , but was
not initially _____

Gem

Supervised Learning

Viewport

Agent

BoxWorld

Mini-Pacman

Reinforcement Learning

I N-th farthest vector from a given vector;
I Program evaluation from characters (Learning to Execute);
I Language modelling;
I Mini-PacMan and Box-World with viewport!

Results on N-th farthest: LSTM/DNC

LSTM

DNC

Failing to surpass 30% batch accuracy!

Results on N-th farthest: RRNN

pu

time

attention weights

inattending from

attending totAttention weight visualisation

Input Vector Id(a) Reference vector is the last in a sequence, e.g. "Choose the 5th furthest vector from vector 7"(b) Reference vector is the ﬁrst in a sequence, e.g. "Choose the 3rd furthest vector from vector 4"(c) Reference vector comes in the middle of a sequence, e.g. "Choose the 6th furthest vector from vector 6"

Results on LTE

The RRNN is again highly competitive, especially in scenarios
where strong relational reasoning may be required (full programs).

Results on LTE

Results on Language Modelling

The RRNN obtains competitive perplexity levels, compared toseveral strong baselines.

Perplexity

Results on Language Modelling: WikiText-103

60
55
50
45
40
35
30

RMC
LSTM

0

1

2

3

4

5

Steps (B)678Results on Mini-PacMan

With viewport

Without Viewport

The RRNN outperforms an LSTM when used as a policy network(for IMPALA). Specifically, when the entire map is observed, it
doubles the LSTM performance!

Concluding remarks
I Empowering neural networks with various kinds of relational

reasoning modules will likely be a necessary step towards
strong and robust intelligent systems.
I

This claim is clearly supported by several “failure modes” ofbaseline architectures we considered today.

I One limitation going forward lies in the all-pairs interactions,which will limit scalability to larger object sets, especially if
self-attention is used.
I

The NRI (Kipf, Fetaya et al., 2018) offers one possible direction
to address this, but probably not the ultimate solution. . .

I In my opinion, particularly important avenue for future work aregraph-structured memories; where we are not restricted to amatrix, and relations between slots are not all-pairs.

Thank you!

Questions?
petar.velickovic@cst.cam.ac.uk
http://www.cst.cam.ac.uk/∼pv273/