Machine Reasoning

2018.12.27

Chin-Hui Chen, Hsiao-Hua Cheng

MSLab Deep Reasoning Team

​

About

陳晉暉 Chin-Hui Chen (CH)

• 2010 - 2013 NTU IRLab MS (advisor: Pu-Jen Cheng)
• 2012 - 2016 榮光/和沛科技 startup 資料&後端工程師
• 2017 ~ now NTU MSLab RA (advisor: Shou-De Lin)
• CCU Center of Cognitive Science, neuroimage neuron model
• Apply for (Neuroscience-inspired) Machine Reasoning Phd

LinkedIn: https://www.linkedin.com/in/chinhui/

Website: https://brain-and-ai.chyy.app

​

​

​

Today’s slide

• https://tinyurl.com/ycou57kv

Agenda

• Introduction
• what is reasoning
• machine reasoning dataset
• Memory based (Memory-Augmented Network approach (MANN))
• MemNN approach (FAIR)
• MemoryNetwork, …, EntityNetwork (ICLR 2017)
• Bio-inspired approach (DeepMind)
• NTM (DeepMind 2014)
• DNC (nature 2016)
• Relational based (RelationNetwork-Augmented Network approach (RN))
• Relation Network (NIPS 2017)
• Graph Network (Deepmind 2018)
• Working Memory Network (ACL 2018)
• Tensor Product Representation based
• TPR-RNN (NIPS 2018)

Y LeCun, et al. Deep learning. (Nature 2015)

What is reasoning?

「推理」是人們由已知或假定的前提來推求結論，或由已知的答案結果，反求其理由根據。例如由因以求果、由果以溯因、由現象以歸其原理、以原理說明現象，包括抽象、類比、演繹、歸納等等思考活動。�

發展心理學的研究指出，人類思考能力從小時候，便開始透過對具體事物的分類與組合來理解事物間的關係，然後約從七歲開始能夠對這些具體事物進行較細緻的邏輯思考，到了十一歲左右智能發展逐漸成熟，便能逐步進行抽象的形式思考。

​

http://www.atlas-zone.com/science/talk/part_1/science150.htm

Inductive Reasoning (歸納) vs Deductive Reasoning (演繹)

• Inductive Reasoning - Francis Bacon
• bottom-up logic
• Deductive Reasoning - Aristotle, Rene Descartes
• top-down logic

​

https://www.quora.com/Whats-the-difference-between-inductive-deductive-and-abductive-reasoning

http://roodo.iguang.tw/bizcom/archives/5015757.html

Deductive Reasoning (演繹推理)

• Deductive reasoning, also deductive logic, logical deduction is the process of reasoning from one or more statements (premises) to reach a logically certain conclusion
• Modus ponens (肯定前件)
• ​

https://en.wikipedia.org/wiki/Deductive_reasoning

• Modus tollens (否定後件)
• ​

​

​

​

• Law of syllogism (三段論)
• ​

Natural Deduction 自然演繹法 (歸納vs演繹)

Can neural network learn 18 rules of inference(推論規則) explicity or implicitly? (8蘊含規則, 10等值規則)

​

https://zh.wikipedia.org/wiki/%E6%BC%94%E7%BB%8E%E6%8E%A8%E7%90%86

https://www.youtube.com/watch?v=sbCdDItHEOE

http://neuralnetworksanddeeplearning.com/images/tikz10.png

Object1 -is in- Object3

Object1 -picked up- Object4

Object2 -went to- Object5

Where is Object4 ? A: Object3

Good at Inductive (tons of training examples)

Neurally plausible? (SGD...)

​

deep learning (connectionism)

symbolic rules (symbolism)

Intrinsic rules (explicitly or implicitly)

​

​

• Machine Reasoning =

Machine Learning + Reasoning (Knowledge Representation Reasoning)

Machine Reasoning Dataset

• NLR: Natural Language Reasoning
• bAbI (FAIR 2015)
• Theory of Mind bAbI (EMNLP 2018)
• Dialog bAbI (NIPS 2016)
• BabyAI (Bengio 2018)
• VQA: Visual Question Answer
• CLEVR (CVPR 2017)
• Abstract Reasoning (ICML 2018)
• Other
• neural math (ICLR 2018), logical entailment (ICLR 2018)

Artificial Tasks for Artificial Intelligence (ICLR2015)

NLR: bAbI dataset

• Released by FAIR (Facebook) in 2015
• Synthetic tasks for nature language reasoning QA tasks
• Provide 20 tasks for different types of machine learning problem

Jason Weston, et al. Towards AI-Complete Question Answering: A Set of Prerequisite Toy Tasks 2015

Single/Two/Three supporting factors

Two/Three Argument Relations

Some variants

• Dialog bAbI (NIPS 2016)

Black text is spoken by the teacher

Red text denotes responses by the learner

Blue text is provided by an expert student

(+) denotes positive reward external to the dialog

• Theory of Mind bAbI

A Nematzadeh, et al. Evaluating Theory of Mind in Question Answering (EMNLP 2018)

Machine Reasoning Dataset

• NLR: Natural Language Reasoning
• bAbI (FAIR 2015)
• Theory of Mind bAbI (EMNLP 2018)
• Dialog bAbI (NIPS 2016)
• BabyAI (Bengio 2018)
• VQA: Visual Question Answer
• CLEVR (CVPR 2017)
• Abstract Reasoning (ICML 2018)
• Other
• neural math (ICLR 2018), logical entailment (ICLR 2018)

VQA: CLEVR

• CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning (Stanford AI Lab - FeiFei Li)

​

https://www.cs.ubc.ca/~lsigal/532L/PP_ProgramsForVisualReasoning.pdf

VQA: Abstract Reasoning

DGT Barrett, et al. Measuring abstract reasoning in neural networks (ICML 2018)

Machine Reasoning Dataset

• NLR: Natural Language Reasoning
• bAbI (FAIR 2015)
• Theory of Mind bAbI (EMNLP 2018)
• Dialog bAbI (NIPS 2016)
• BabyAI (Bengio 2018)
• VQA: Visual Question Answer
• CLEVR (CVPR 2017)
• Abstract Reasoning (ICML 2018)
• Other
• neural math (ICLR 2018), logical entailment (ICLR 2018)

neural math

F Arabshahi, et al. Combining Symbolic Expressions and Black-box Function Evaluations in Neural Programs (ICLR 2018)

logic entailment

R Evans, et al. Can Neural Networks Understand Logical Entailment? (ICLR 2018)

(A entails B if every model in which A is true is also a model in which B is true)

Agenda

• Introduction
• what is reasoning
• machine reasoning dataset
• Memory based (Memory-Augmented Network approach (MANN))
• MemNN approach (FAIR)
• MemoryNetwork, …, EntityNetwork (ICLR 2017)
• Bio-inspired approach (DeepMind)
• NTM (DeepMind 2014)
• DNC (nature 2016)
• Related Works
• Relational based (RelationNetwork-Augmented Network approach (RN))
• Relation Network (NIPS 2017)
• Graph Network (Deepmind 2018)
• Working Memory Network (ACL 2018)
• Tensor Product Representation based
• TPR-RNN (NIPS 2018)

Single/Two/Three supporting factors

MemNN appraoch (FAIR)

• Memory Network (MemNN) (Weston et al,’14)
• End-to-end Memory Network (MemN2N) (Sukhbaatar et al., ‘15)
• Key-Value Memory Network (Miller et al., ‘16)
• Recurrent Entity Network (EntNet) (Henaff et al., ‘16)

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

Single/Two/Three supporting factors

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

• unable to train end to end

http://www.shuang0420.com/2017/12/04/%E8%AE%BA%E6%96%87%E7%AC%94%E8%AE%B0%20-%20Memory%20Networks/

MemNN appraoch (FAIR)

• Memory Network (MemNN) (Weston et al,’14)
• End-to-end Memory Network (MemN2N) (Sukhbaatar et al., ‘15)
• Key-Value Memory Network (Miller et al., ‘16)
• Recurrent Entity Network (EntNet) (Henaff et al., ‘16)

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://www.shuang0420.com/2017/12/04/%E8%AE%BA%E6%96%87%E7%AC%94%E8%AE%B0%20-%20Memory%20Networks/

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

Compare to MemNN (multi-hop/addressing)

http://www.shuang0420.com/2017/12/04/%E8%AE%BA%E6%96%87%E7%AC%94%E8%AE%B0%20-%20Memory%20Networks/

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

http://slazebni.cs.illinois.edu/spring17/lec27_memory.pdf

MemNN appraoch (FAIR)

• Memory Network (MemNN) (Weston et al,’14)
• End-to-end Memory Network (MemN2N) (Sukhbaatar et al., ‘15)
• Key-Value Memory Network (Miller et al., ‘16)
• Recurrent Entity Network (EntNet) (Henaff et al., ‘16)

http://people.idsia.ch/~rupesh/rnnsymposium2016/slides/weston.pdf

http://people.idsia.ch/~rupesh/rnnsymposium2016/slides/weston.pdf

http://people.idsia.ch/~rupesh/rnnsymposium2016/slides/weston.pdf

Recurrent Entity Network

Input Module

Dynamic Memory

Output Model

M Henaff, et al. Tracking the World State with Recurrent Entity Networks (ICLR 2017)

Agenda

• Introduction
• what is reasoning
• machine reasoning dataset
• Memory based (Memory-Augmented Network approach (MANN))
• MemNN approach (FAIR)
• MemoryNetwork, …, EntityNetwork (ICLR 2017)
• Bio-inspired approach (DeepMind)
• NTM (DeepMind 2014)
• DNC (nature 2016)
• Related Works
• Relational based (RelationNetwork-Augmented Network approach (RN))
• Relation Network (NIPS 2017)
• Graph Network (Deepmind 2018)
• Working Memory Network (ACL 2018)
• Tensor Product Representation based
• TPR-RNN (NIPS 2018)

Bio-inspired approach

• Long short-term memory (LSTM)
• Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory (Neural Computation 1997)
• Neural Turing Machine (NTM)
• Alex Graves, et al. Neural Turing Machines (arXiv 2014)
• Differentiable Neural Computer (DNC)
• Alex Graves, et al. Hybrid computing using a neural network with dynamic external memory. (Nature 2016)

​

Long short-term memory (LSTM)

• LSTM was proposed in 1997 by Sepp Hochreiter and Jürgen Schmidhuber and improved in 2000 by Felix Gers' team.
• RNN: brain-inspired general purpose computers that can learn parallel-sequential programs or algorithms encoded as weight matrices. (RNNsymposium2016)
• Since 2013, LSTM has been the most popular and powerful DL model in speech recognition and natural language processing area.
• An LSTM network contains a (memory) cell. An LSTM cell "remembers" a value for either long or short time periods.

https://en.wikipedia.org/wiki/Long_short-term_memory

LSTM

http://colah.github.io/posts/2015-08-Understanding-LSTMs/

forget gate

input gate

update Cell

output gate

LSTM memory operations

• C as cell unit for “remembering” values over arbitary time intervals.
• Use hidden unit (h) and input (x) to determine forget, input, output gate.

�

• Also use hidden unit (h) and input (x) to determine cell state content.

​

• In ordinary LSTM networks, the functions of sequence control and memory storage are closely intertwined. This contrasts with classic models of human working memory, which separate these two. (Demis Hassabis, 2017)

Bio-inspired approach

• Long short-term memory (LSTM)
• Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory (Neural Computation 1997)
• Neural Turing Machine (NTM)
• Alex Graves, et al. Neural Turing Machines (arXiv 2014)
• Differentiable Neural Computer (DNC)
• Alex Graves, et al. Hybrid computing using a neural network with dynamic external memory. (Nature 2016)

​

Inspired by working memory

• Human intelligence is characterized by a remarkable ability to maintain and manipulate information within an active store, known as working memory, which is thought to be instantiated within the prefrontal cortex(前額葉皮層) and interconnected areas (Goldman-Rakic, 1990).
• Classic cognitive theories suggest that this functionality depends on interactions between a central controller (‘‘executive’’) and separate, domain-specific memory buffers (e.g., visuo-spatial sketchpad) (Baddeley, 2012)

​

Demis Hassabis, et al. Neuroscience-Inspired Artificial Intelligence

(Baddeley, 2012)

https://www.slideshare.net/Frank.van.Harmelen/panel-on-the-future-of-ai-at-the-flamish-royal-society-of-sciences-and-arts

Dorsolateral Prefrontal cortex (DLPFC) and Supplementary Motor Area (SMA)

https://tinyurl.com/yatrslht

NTM

• Despite its success in modelling complicated data (pattern recognition), modern ML has largely neglected the use of logical flow control and external memory.
• Neural Turing Machine is extend the capabilities of RNN by augmenting external memory resources.
• Inspired by Neuroscience and Cognitive Science, an NTM resembles a working memory(wm) system.
• an NTM can learn to use its wm instead of �deploying a fixed set of procedures over �symbolic data.

Alex Graves et al. Neural Turing Machines 2014

We need external & explicit memory

• How humans deals with mem task?
• Working memory (7±2 “units” in cognitive psychology)
• First store the sequence in working memory, then output it
• Can RNN have some “working memory”?
• The link between RNN and external memory: read & write heads
• Ideas from Turing Machine
• RNN as a “controller”, output transforms to parameters that determine how some read & write heads work

​

Von Neumann architecture scheme

credit from http://cpmarkchang.logdown.com/posts/279710-neural-network-neural-turing-machine

NTM architecture

• High level view

credit from http://cpmarkchang.logdown.com/posts/279710-neural-network-neural-turing-machine

Traditional RNN

RNN

output(raw)

input

output

Parameters of read & write heads

Memory

write heads (make modifications to the memory)

read heads (get data from memory)

read vector

previous states

• previous states also play a role in heads generation

credit from https://docs.google.com/presentation/d/1FqU7q-vWN9uV7sMRt9It9F_el9nIdqzBfMPm91hJ4B0/edit#slide=id.g240572a74a_0_134

y_t = o_tw + b

2)

3)

4)

M_t = M_t-1

x

o

Addressing

http://llcao.net/cu-deeplearning15/presentation/NeuralTuringMachines.pdf

credit from http://cpmarkchang.logdown.com/posts/279710-neural-network-neural-turing-machine

Sharpen

NTM capabilities

• an NTM can infer simple algorithms such as copying, priority sorting, and associative recall from input and output examples.

Copy Task

10

20

30

50

120

train on length=20

LSTM Generalization on copy task

Copy Task

Copy Task

Repeat Copy Task

Associative Recall

Brain analogy

• Attribute theory
• It posits that each time some information is presented to a person, it is neurally encoded in a unique memory trace composed of a combination of its attributes.

Kahana, Michael J. (2012) Foundations of human memory New York: Oxford University Press

Hintzman, D. L. (2003) Robert Hooke’s model of memory Psychonomic Bulletin & Review, 87, 398-410

​

• Summed similarity model

NTM issues

• content-based addressing + location-based addressing (allow the network to iterate through memory locations in order of their indices. For example, location n followed by n + 1 and so on)
• several drawbacks

1. Memory overlap and interfere: no mechanism to ensure that blocks of allocated memory do not overlap and interfere

2. Free memory: no way to free memory; no way to resue memory

3. No way to jump to different parts of memory (limitation of content and location)

Dynamic-NTM (Neural Computation 2018)

Content-based + Dynamic Least Recently Used(LRU) Addressing

Address matrix + Content matrix

Bio-inspired approach

• Long short-term memory (LSTM)
• Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory (Neural Computation 1997)
• Neural Turing Machine (NTM)
• Alex Graves, et al. Neural Turing Machines (arXiv 2014)
• Differentiable Neural Computer (DNC)
• Alex Graves, et al. Hybrid computing using a neural network with dynamic external memory. (Nature 2016)

​

DNC intro

• Differentiable Neural Computer (DNC) is the successor of Neural Turing Machine (NTM)
• A DNC uses differentiable attention mechanism to define dist over N rows, or “locations” (NxW memory)
• Provide 3 types of attention mechanism (memory access)
• There are interesting parallels between the memory mechanisms of a DNC and the functional capabilities of the mammalian hippocampus.

DNC architecture

DNC architecture (cont’)

1. controller network

Selecting locations for reading and writing depends on weightings:

​

​

Reading memory (R readers):

​

​

​

b. reading and writing memory

Writing memory:

: where to write: content-based addressing and dynamic memory allocation

: where to read: content-based addressing and temporal memory linkage

​

​

​

​

c. memory addressing

​

Content-based addressing:

(both for read and write)

: where to write: content-based addressing and dynamic memory allocation

: where to read: content-based addressing and temporal memory linkage

​

​

​

​

c. memory addressing

Dynamic memory allocation: (write) allow controller to free and allocate memory as needed

memory retention vector: represents by how much each location will not be freed by the free gates. (1 -> retention t-1 read weighting)

​

memory usage vector:

free list: sorting the indices of the memory locations in asc order of usage. is the index of the least used location.(least)

allocation weighting: provide new locations for writing.

​

​

​

: where to write: content-based addressing and dynamic memory allocation

: where to read: content-based addressing and temporal memory linkage

​

​

​

​

c. memory addressing

write weighting: controller can 1. write to newly allocated locations, or 2. to locations addressed by content, or 3. not to write at all.

: where to write: content-based addressing and dynamic memory allocation

: where to read: content-based addressing and temporal memory linkage

​

​

​

​

c. memory addressing

Temporal memory linkage:

​

precedence weighting: represents the degree to which location i was the last one written to.

a temporal link matrix: to keep track of consecutively modified memory location.

​

​

​

represents the degree to which location i was the location written to after location j. The rows and columns represent the weights of temporal links going into and out from particular memory slots.

​

​

​

​

: where to write: content-based addressing and dynamic memory allocation

: where to read: content-based addressing and temporal memory linkage

​

​

​

​

c. memory addressing

read weighting:

​

DNC capabilities

• Facebook bAbI task
• Interpret and answer questions about graphs
• Started with explicit graphs, but ultimately interested in implicit graphs: relations in natural language, scene parsing, agent’s surroundings…

http://people.idsia.ch/~rupesh/rnnsymposium2016/slides/graves.pdf

Experiment (copy)

Synthetic question answering experiments (bAbI)

the story “John is in the playground. John picked up the football.” followed by the question “Where is the football?” with answer “playground”

Graph experiments

• encode (start node, end node, edge) to vector (bAbI can be encoded too)
• 3 phase: graph definition phase, query phase, (planning phase), answer phase
• training with random graph and generalizing to Underground and family tree graph.

Graph experiments

random seven-step traversal: 98.8%

four-step shortest path: 55.3%

four-step inference: 81.8%

Brain analogy

• Temporal Context Model (TCM)
• The idea is that when a human subject memorizes a sequence, the sequence itself determines context. In this model, context drives both memory storage and recovery.
• Serial recall
• The two prevailing theories are chaining and positional coding. If you are familiar with computer science, chaining basically says memory is a linked list and positional coding says memory is a regular list.

​

Kahana, Michael J. (2012) Foundations of human memory New York: Oxford University Press

• Associative chaining coding������
• Positional coding

• Search of Associative Memory (SAM)
• SAM was proposed by (Atkinson 1968) to explain human free recall studies such as (Raaijmakers 1980), (Murdock 1962) and (Kahana 2008). As a dual-store model, it divides human memory into Short Term Storage (STS) and Long Term Storage (LTS).

​

credit from https://greydanus.github.io/2017/02/27/differentiable-memory-and-the-brain/

Comparison

Brain like direction?

https://www.atlasobscura.com/articles/the-birdlike-soviet-flying-machine-that-never-quite-took-off

https://www.mpoweruk.com/flight_theory.htm

Fundamentals of nature intelligence?

MANN for Neural Machine Translation

Mingxuan Wang, et al. Memory-enhanced Decoder for Neural Machine Translation. EMNLP 2016

MANN for One-Shot/Meta Learning

Adam Santoro, et al. Meta-Learning with Memory-Augmented Neural Networks, ICML, 2016

​

MANN for Stack Emulation

​

​

Learning Operations on a Stack with Neural Turing Machines (NIPS 2016 workshop)

MANN for Neural Programming

​

​

Jacob Devlin, et al. Neural Program Meta-Induction NIPS 2017

​

MANN for Reinforcement Learning (Neural Episodic Control)

Alexander Pritzel, et al. Neural Episodic Control. Deepmind 2017

Neural Episodic Control - DND (differentiable neural dictionary)

​

• For each action a ∈ A, NEC has a simple memory module Ma = (Ka, Va)
• DND maps a key h to an output value o =>

​

​

​

​

• h_i is the ith element of the array Ka, k(x, y) is a kernel

https://docs.google.com/presentation/d/1rjb7EcHPApf313W-JL40I6tz5NhDel4n53Qbulcb6YA/edit#slide=id.g274915602e_0_2

Experiment

Agenda

• Introduction
• what is reasoning
• machine reasoning dataset
• Memory based (Memory-Augmented Network approach (MANN))
• MemNN approach (FAIR)
• MemoryNetwork, …, EntityNetwork (ICLR 2017)
• Bio-inspired approach (DeepMind)
• NTM (DeepMind 2014)
• DNC (nature 2016)
• Related Works
• Relational based (RelationNetwork-Augmented Network approach (RN))
• Relation Network (NIPS 2017)
• Graph Network (Deepmind 2018)
• Working Memory Network (ACL 2018)
• Tensor Product Representation based
• TPR-RNN (NIPS 2018)

Relation Networks (RN)

Hsiao-Hua Cheng

​

​

A simple neural network module for relational reasoning (NIPS 2017) https://arxiv.org/abs/1706.01427

​

​

​

Relational Reasoning & Relation Networks

• Relational Reasoning: Learn to understand relations between different objects
• Easy for human but difficult for computers
• Relation Networks: Teach the neural network capable of perform complicated relational reasoning with unstructured data

RN-augmented network

• Able to take an unstructured input (an image or a series of sentences) and implicitly reason about the relations of objects contained within it.
• Figure out what counts as an object in the scene from the unstructured stream of pixels by itself (CNN or LSTM)
• Learn the relations between 2 objects as it compares each possible pair. (RN module)
• Combine those relations
• By adding up all these relations

RN-augmented network for CLEVR

• CNN: Extract features of that image in k filters
• The ‘object’ for the relational network is a vector of features of each point in the grid.
• e.g. one ‘object’ is the yellow vector.

RN-augmented network for bAbi

RN module

​

​

​

• RN operate on “objects”,
• fφ and gθ are MLPs
• gθ: calculates relations between a pair of objects
• fɸ: takes in the sum of all gθ, and calculates the final output of the model

CLEVR Dataset

• Visual question answering task designed to explicitly explore a model’s ability to perform different types of reasoning

​

​

​

​

​

Ref: https://arxiv.org/abs/1612.06890

CLEVR Dataset - Question type

​

• count
• How many small spheres are the same color as the big rubber cube? (count)
• exist
• Is there another green rubber cube that has the same size as the green matte cube? (exist)
• compare numbers
• Are there fewer small yellow things to the left of the large yellow matte ball than large brown objects? (less_than)
• query attributes
• What shape is the cyan shiny thing that is the same size as the read matte object? (query_shape)
• compare attribute
• Is the tiny ball make of the same material as the large purple ball (equal_material)

Experiment - CLEVR

​

• Accuracy
• Pre-state-of-art: 68.5%
• Human: 92.5%
• CLEVR: 95.5% (> Human!)

• In particular, it solved “compare attribute” questions, which trouble all other models because they heavily depend on relational reasoning.

Experiment - CLEVR

​

​

​

​

​

• ​

• SA: Stacked Attention

​

​

​

​

​

​

Ref: https://arxiv.org/pdf/1511.02274.pdf

​

bAbI Dataset

• A series of of text-based question answering tasks

​

​

​

​

​

Ref: https://research.fb.com/downloads/babi/

​

Experiment - bAbI

• Succeeded on 18/20 tasks.
• Similar to existing state-of-the-art models
• Notably, it succeeded on the basic induction task (2.1% total error), which proved difficult for the Sparse DNC (54%), DNC (55.1%), and EntNet (52.1%).
• Did not catastrophically fail in any of the tasks
• For the 2 tasks that it failed (the “two supporting facts”, and “three supporting facts” tasks), it missed the 95% threshold by 3.1% and 11.5%, respectively.

Conclusion

• Relational Networks are extremely adept at learning relations.
• They are also flexible and can be used as a drop in solution when using CNN’s, LSTMs, or both.
• “We speculate that the RN provided a more powerful mechanism for flexible relational reasoning, and freed up the CNN to focus more exclusively on processing local spatial structure. This distinction between processing and reasoning is important.”

​

Why does RN work?

• Graph structure is essential for relational reasoning (Inductive biases).
• Entity -> Node
• Relation -> Edge
• Rule -> Node Edge mapping
• Current DL components are lack of graph structure.

PW Battaglia, et al. Relational inductive biases, deep learning, and graph networks (Deepmind, MIT, 2018)

​

Graph Network (GN)

​

Graph Network (GN)

RN = GN

Working Memory Network

J Pavez et al. Working Memory Networks: Augmenting Memory Networks with a Relational Reasoning Module (ACL 2018)

Agenda

• Introduction
• what is reasoning
• machine reasoning dataset
• Memory based (Memory-Augmented Network approach (MANN))
• MemNN approach (FAIR)
• MemoryNetwork, …, EntityNetwork (ICLR 2017)
• Bio-inspired approach (DeepMind)
• NTM (DeepMind 2014)
• DNC (nature 2016)
• Related Works
• Relational based (RelationNetwork-Augmented Network approach (RN))
• Relation Network (NIPS 2017)
• Graph Network (Deepmind 2018)
• Working Memory Network (ACL 2018)
• Tensor Product Representation based
• TPR-RNN (NIPS 2018)

Tensor Product Representation based

• Inspired by Cognitive Science, Tensor Product Representation (TPR) is one of the general method for embedding symbolic structures in a vector space. (sub-symbolic/neural-symbolic)
• illustration by an example,
• Jay saw Kay = Kay saw Jay = J+K+s
• To avoid this confusion, analyse Jay saw Kay as the set
• choose vector space: :
• choose vector space: :
• TPR:

http://www.aclweb.org/anthology/N18-1114

filler

role

• in vector space embedding,

binding = tensor (out) product

Jay saw Kay != Kay saw Jay

• unbinding = inner product ・

​

TPR-RNN

​

​

​

Input Module:

I Schlag, et al. Learning to Reason with Third-Order Tensor Products (NIPS 2018)

Update Module:

write, move, backlink memory operation

Inference Module:

LN=layer normalization

Some Conclusions

• We present four types of machine reasoning model. (Some are inspired from Cognitive Science or Neuroscience. E.g. working memory, tensor product representation)
• There are still many materials (dataset, models) not convered in the lecture.
• Toy problem and still many unresolved problems remain. E.g. data hungry (how to use 1k instead of 10k training dataset?), computation hungry (DNC complexity), combinatorial generalization (how to generalize to novel entity?), knowledge/rule extraction.
• To arrive the Holly Grial of artificial general intelligence, we shall move from pattern recognition to high level cognition. Reasoning capability is crucial in the future AI agents.

Y LeCun, et al. Deep learning. (Nature 2015)

Thanks

linkedin.com/in/chinhui

​

fb.me/dongochen

​

​

If you have any questions

Related Works

MANN

Graves, Alex, Greg Wayne, and Ivo Danihelka. “Neural turing machines.” arXiv (2014).

Graves, Alex, et al. “Hybrid computing using a neural network with dynamic external memory.” Nature (2016)

Caglar Gulcehre, Sarath Chandar, Kyunghyun Cho, and Yoshua Bengio. “Dynamic Neural Turing Machine with Soft and Hard Addressing Schemes” arXiv (2016).

Caglar Gulcehre, Sarath Chandar, and Yoshua Bengio. “Memory Augmented Neural Networks with Wormhole Connections.” arXiv (2017).

Shiv Shankar, Sunita Sarawagi “Label Organized Memory Augmented Neural Network” NIPS (2017)

Grefenstette, Edward, et al. “Learning to transduce with unbounded memory.” NIPS 2015.

MANN for Language Understanding

Weston, Jason, Sumit Chopra, and Antoine Bordes. “Memory networks.” ICLR (2015).

Sainbayar Sukhbaatar, et al. “End-To-End Memory Networks” NIPS (2015)

Kumar, Ankit, et al. “Ask me anything: Dynamic memory networks for natural language processing.” JMLR (2015).

Zhang, Jiani, et al. “Dynamic Key-Value Memory Network for Knowledge Tracing.” arXiv (2016).

Caiming Xiong, Stephen Merity, Richard Socher. “Dynamic Memory Networks for Visual and Textual Question Answering.” ICML (2016).