Research/Blog
Logic and Reasoning (AGI)
- October 9, 2020
- Posted by: Bhavesh Laddagiri
- Category: Artificial General Intelligence (AGI)
#CellStratAILab #disrupt4.0 #WeCreateAISuperstars #WhereLearningNeverStops
Recently, I presented an extensive session on Logic and Reasoning at the CellStrat AI Lab. This topic comes under the broader area of Artificial General Intelligence or AGI.
This workshop included the following topics :-
- Symbolic AI
- Propositional Logic
- First Order Logic
- Program Synthesis
- Relation Network
Symbolic AI
Although, Deep Learning is dominating the field of AI it isn’t flawless. One of the fundamental issues with deep learning is model interpretability and huge data requirements.
Symbolic AI is one of the oldest forms of artificial intelligence which was famous in the second half of the 20th century. It was at the center stage (similar to how DL is at the center now).
Symbolic AI deals with manipulating “symbols” using pre-written rules and properties of the symbols from a knowledge base. Symbols can be anything from an object like an apple to an action like running.
In a nut shell, it is a generalized form of if-else statements.
Why now ?
Deep learning is natively incapable of using logic and reasoning. We can theoretically train it to learn to reason but it requires hand-written ground-truths.
Symbolic AI is natively designed to support human interpretable logic and reason using rules defined by us.
The hybridization of symbolic AI with neural networks is a promising pathway for research towards artificial general intelligence as symbolic AI can complement the missing logic and reasoning in neural nets.
There are two types of symbolic logic :-
- Propositional Logic (PROLOG)
- First Order Logic (FOL)
One thing to note here is that, symbolic logic deals with Boolean outcomes and is not probabilistic like Bayesian networks or neural networks. So every statement expressed in symbolic logic has a truth value of either true or false.
Propositional Logic (Prolog)
Some basic terminology in symbolic logic –
- Symbols – They are objects/facts in the problem world. Eg: Sleeping, Rain, etc.
- Boolean – A data type which can store a binary value of either 1 or 0.
- Logic Operators – These perform some form of operation on the symbols. Eg: AND (∧), OR (∨), NOT (¬), Implies (⇒) and Equivalent (⇔).
- Proposition – A statement consisting of symbols and logic operators. Ex- E ∨ B
- Knowledge Base – A collection of lots of propositional statements which can be used by the AI to perform inference (i.e. applying logic on the knowledge base to answer questions)
Propositional logic is essentially regular Boolean logic.
Truth Table
A truth table represents all the possibilities of a propositional statement.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Truth-Table-1024x252.png)
AND (∧), OR (∨), NOT (¬), Implies (⇒) and Equivalent (⇔)
Implication
In general, the Implies (⇒) operator can be thought of an if … then … statement.
Let’s say, C means that the weather is cold and J is me wearing a jacket. So the truth table for the proposition (implication in this case) If its cold then wear a jacket i.e. C ⇒ J will be –
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Implication-1024x317.png)
Example
Let’s say we have a security alarm (A) which gets triggered if a burglary occurs (B) or an earthquake occurs (E). We can represent the statement in prolog as –
(E ∨ B) ⇒ A
Now, if an alarm gets triggered we can say it notifies the owners John (J) and Mary (M), we can write it as –
A ⇒ (J ∧ M)
To know whether an earthquake took place or not we have a radio (R) which notifies us with the information, so we can encode this knowledge as –
R ⇔ E
Now that we have all these propositions in the knowledge base we can ask the AI about any variable. For instance, if the alarm (A) was triggered (1) and the Radio (R) notification is False (1) then we can infer that Burglary (B) is True (1).
Types of Sentences
- Valid – One that is true in every possible model.
- Satisfiable – One that is true in some models.
- Unsatisfiable – One that is false for all models.
For example, the sentence P ∨ ¬ P is valid and P ∧ ¬ P is unsatisfiable.
Limitations of Prolog
- Cannot handle uncertainty
- Cannot represent objects, only true or false like facts/events
- Cannot directly talk about relations between objects
- It’s not practical to represent a general situation. For example in a world where a vacuum robot operates, we cannot represent the status of all 100 locations as clean. We have to state every location is clean and cannot say that all locations are clean in propositional logic.
First Order Logic (FOL)
First order logic is an extension of propositional logic which overcomes the limitations of vanilla propositional logic.
Although, both these logic systems use an absolute belief system (True, False, or uncertain) and cannot handle the degree of the uncertainty like probabilistic systems.
FOL can represent complex relationships between objects.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/FOL-1024x203.png)
The FOL Model
In propositional logic, the model was just the value of a symbol. Eg: {P: True, Q: False}.
In First Order Logic, our model is more sophisticated and includes – constants, functions and relations.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/FOL-Model.png)
The Syntax
![](https://www.cellstrat.com/wp-content/uploads/2020/10/FOL-Syntax.png)
For example, we could say
∃x Even(x) ⇒ Color(x) = G
Vacuum Robot example 1 –
Let’s say in a world, there are two locations A and B which can be Dirty or Clean at any given moment and a robot can vacuum it if its dirty.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Vacuum-Robot-Example-1.png)
Vacuum Robot example 2 –
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Vacuum-Robot-Example-2.png)
We can represent “The robot is at location A” in FOL as –
At(R, A)
Vacuum Robot example 3 –
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Vacuum-Robot-Example-3.png)
We can represent “There is no dirt in any of the locations” in FOL as –
∀d ∀l Dirt(d) ∧ Loc(l) ⇒ ¬ At(d, l)
Vacuum Robot example 4 –
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Vacuum-Robot-Example-4.png)
We can represent “Robot is in a location with dirt” in FOL as –
∃l ∃d Dirt(d) ∧ Loc(l) ∧ At(R, l) ∧ At(d, l)
Grocery Store inference example
Let’s say, we have the following rules in a knowledge base of a grocery store –
S ⇒ Between(M, B)
H ⇒ Between(M, B)
Where S, H, M, B which stand for sandwich, hotdog, meat and bread respectively If the store has a 50% discount on the sandwiches, should there be a discount on the hotdogs as well?
As per the rules defined in the knowledge base, Yes!
Applications
Symbolic Logic like this is used for making expert systems which take in a huge knowledge base as input and use logic to answer questions and take decisions. Inference systems are so normal now that most people don’t consider them AI now.
It can be seen for use in –
- Retail Stores
- Banking
- Governments
- Military, etc…
A famous example of expert systems is during the Persian-Gulf war when a superhuman decision by a military expert system about where to place a supply base, saved the US 2 billion dollars.
Program Synthesis
Program Synthesis is the task of a computer to generate a program automatically to perform some defined task or solve a problem.
We can look at it as generating a series of logical steps/instructions for completing a given task with specifications like input-output examples. Its similar to how we write a program in a programming language to complete a given task except that the program is auto-generated.
Program Synthesis is one of the closest ideas to how we humans solve a problem with logic and reasoning.
It also has similarities with supervised learning but instead of a mathematical function with parameters to optimize we have a logical function in a defined programming language which searches through the language grammar to generate a program which fits the I/O examples.
Components
- Domain Specific Language (DSL) – It is a set of functions, relations and operations which can be used in various combinations to perform some task in a specific domain.
- Program – The generated program in a DSL. It is usually represented in the form of an abstract syntax tree.
- Program Specification – The input and output pairs which is used to generate a program.
Some approaches for program synthesis are – Search Heuristics, Genetic Algorithms (aka Genetic Programming), Reinforcement Learning, Neural Networks.
A simple example
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Program-Synthesis-example.png)
Question: Is there a square left of the red circle?
Program:
- circles = filter_shape(circle, objects)
- circle = filter_color(red, circles)
- object = relate(left, circle)
- y = shape(object)
- y == square ⇒ Yes
Answer: Yes
Flash Fill example
Gulvani et al. (2011) developed a program synthesizer called flash fill, which is a feature in Excel, which can learn from a few examples and automate tasks by creating a program.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Flash-Fill-example.png)
Flashmeta / Prose
Gulwani and Polozov (2015) developed a meta tool to synthesis custom programs from our own domain specific language. Given some I/O examples for the desired program’s behavior, a DSL to restrict the search space and a search heuristic, PROSE synthesizes a ranked set of programs that are consistent with the examples.
PROSE SDK is available open source for you to try: https://microsoft.github.io/prose/
Program Synthesis vs Supervised Learning
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Program-Synthesis-vs-Supervised.png)
Relation Networks
Relational reasoning is the ability to relate different objects to answer a question or solve a problem.
Symbolic methods are natively capable of relational reasoning but aren’t scalable and sensitive to input variations and noise. Deep Learning representations have come a long way but relational reasoning is one area where it lags.
Relation Networks by Santoro et al. (2017) at DeepMind combines the two areas by using a neural approach to relation reasoning.
RN is a simple plug-n-play module which is designed explicitly for relational reasoning. Moreover with joint training for visual question answering it can influence and shape upstream CNNs and LSTMs to create object like representations.
CLEVR dataset
CLEVR Dataset is a Visual Question Answering benchmark dataset with a focus on relational reasoning. Prior end-to-end differentiable methods haven’t performed very well on this dataset. Architectures specifically designed for reasoning have out performed in this area.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/CLEVR-dataset.png)
Other Relational Reasoning problems
Apart from CLEVR which is like a benchmark you can apply RN on other datasets as well which require relational reasoning. These datasets include –
- General Visual Question Answering
- bAbI – Text based deduction and logic
- Sort-of-CLEVR – A 2D version of CLEVR
- Dynamic Physical Systems – Physical systems like balls rolling on a table and the task is to predict if a ball is independently moving or part of a system and count the number of systems in the environment.
Basic Form
RNs are inherently built for relational reasoning similar to how CNNs are built to capture spatial relations and RNNs are built for capturing sequential dependencies.
In its simplest form, RN is
![](https://www.cellstrat.com/wp-content/uploads/2020/10/RN-equation-2.png)
Where O is a set of all objects and f and g are functions with parameters ϕ and θ respectively.
The output of g_θ can be considered the relation score.
If you notice, we are calculating the relation of every object to every other object regardless of whether any relation actually exists or not. The RN doesn’t know the actual meaning of any object but will learn its implication as it gets trained.
Although, we could potentially customize this further to allow only some pairs of objects to be inferred for relations.
Model Architecture
RNs operate on individual objects and not direct images or text. So we need to encode the inputs into some object level representation.
Fortunately, RNs can work with unstructured inputs in the form of CNN or LSTM embeddings as well. This is because RNs expect object representations as input but what constitutes as an object is not defined.
During training, RN forces the CNN or LSTM to generate better object-like embeddings.
![](https://www.cellstrat.com/wp-content/uploads/2020/10/RN-model-architecture-1024x468.png)
![](https://www.cellstrat.com/wp-content/uploads/2020/10/RN-model-architecture-2.png)
Here, each cell of the k×d×d vector is an object. Technically, an object representation would include everything in the scene i.e. the background, the object, the texture, etc.
The relations between the objects is dependent on the question being asked so we can condition the relation of objects with the embeddings of the question
![](https://www.cellstrat.com/wp-content/uploads/2020/10/RN-equation-2-1.png)
To get the embeddings of the questions, we can use the final state of an LSTM layer.
Results on CLEVR
![](https://www.cellstrat.com/wp-content/uploads/2020/10/CLEVR-results-1024x350.png)
Potential Applications
- Visual Question Answering
- Scene understanding in RL Agents
- Social Network Modelling
- Abstract Problem Solving
- Can be plugged into existing deep learning architectures to improve performance in tasks which might benefit from relational reasoning
Code Demo
Sort-of CLEVR dataset
Sort-of-CLEVR is a simpler version of the CLEVR dataset and has 2D images instead. 6 colors are assigned to randomly chosen shapes (rectangle and circle) and placed in an image.
It contains 2 types of questions with 3 sub-types in each type i.e. –
- Non-Relational Questions
- Shape – What is the shape of the green object?
- Horizontal position – Is there a red object on the left?
- Vertical Position – Is there a gray object on the top?
- Relational Questions
- Closest shape – What is the closest shape to the red object
- Furthest shape – What is the furthest shape from the green object?
- Count – How many objects of the same shape as the blue object are there?
There a total of 10k images with 20 questions per image (10 non-rel and 10 rel).
![](https://www.cellstrat.com/wp-content/uploads/2020/10/Sort-of-Clevr-Dataset.png)
Summary
- Symbolic AI is essentially rule-based systems which use Boolean logic.
- Propositional Logic is Boolean logic and First Order Logic is an extension of it which includes relations and functions.
- FOL is applied in program synthesis i.e. automatic generation of a program in a DSL, given the input-output examples.
- Relation Network by Deepmind is a module which optimizes itself for relational reasoning between objects.
References and Further Reading
- Artificial Intelligence: A Modern Approach – Peter Norvig
- Program Synthesis Meets Machine Learning Talk – Sriram Rajamani, Microsoft Research
- Collection of papers on deep learning for program synthesis – https://sunblaze-ucb.github.io/program-synthesis/index.html
- A simple neural network module for relational reasoning – https://arxiv.org/abs/1706.01427
- https://github.com/kimhc6028/relational-networks
- https://github.com/mesnico/RelationNetworks-CLEVR
- On the Measure of Intelligence – https://arxiv.org/abs/1911.01547