Inference reasoning using Python
An expert system is a tool capable of reproducing cognitive mechanisms. It can resolve queries from a set of known facts and rules. This deduction system is useful for decision making or when you want to prove things. It is one of the path leading to artificial intelligence systems.
This article will give you the basic concepts of a how a system like this can be solved. At the end, you should be able to implement you own backward resolver 😊.
The expert system
First the system receive a set of rules. Rules are equations that combine
Facts are in this case represented by uppercase letters, and
connectors can be one of:
&: AND — All operands must be
|: OR — Only one operand need to be
^: XOR — One operand must be
Trueand the other
=>: IMPLY — If the left side is
Truethen the right side must be
The inference truth table
This table describes the inference’s logic. For example in
p => q, if the left part is
false, then we can say nothing about the right part, because it can be either
true. If the left part is
true, then the right part must be
true, otherwise this implication is invalid.
Facts and queries
Facts are represented by uppercase letters. We will say that, by default, all facts are
false. A fact can become true if it is in the set of initial facts (using the
=XXX declaration) or by deduction from the rules.
The searched queries are declared using the
Implementing a resolver
Forward and backward chaining
There are 2 ways to solve an expert system:
- Forward chaining: We start from the facts and we deduct the result.
- Backward chaining: We work backward, from the hypothesis to the facts.
This article will focus on the backward resolver only. The solver will use the same structure as the graph of the first image. Each element on the graph is called a
Node. There is 2 sub-types of nodes:
AtomNode, for example A, B or C.
That’s why Python seemed to be the best fit, for its simplicity and object oriented properties.
Nodes are the most important elements of the graph. They handle the logic and save their states. They are interconnected using
children list. If we know the value of the child, we can deduct the value of the parent. For example, for the rule
A => B,
A is child of
=> child of
A is true, then we deduct
B is true.
All the subclass
ConnectorNode inherit from this class.
Step 1 — Create a list of unique atoms
The first step consist in parsing the input and create a unique list of
atoms. It means that the same letter in different rules will always points to the same
Step 2 — Create a RPN representation of all the rules
RPN — Reverse Polish Notation
The reverse polish notation gives a non ambiguous way to write arithmetic formulas without the use of parentheses.
This technique has many advantages:
- It keeps the order of operands
- You read it from left to right
- Operands that precede the operator and the operand disappears to be replaced by the calculated value
Step 3 — Create the relations between nodes
Step 4— Resolve the queries
I hope that I gave you a better idea of how a system like this works. In case you want to access a complete Python implementation, I’ve linked my repository below 😊.
Tired of supporting big corporations every time you shop online? Switch to open.mt, the decentralized marketplace that uses blockchain technology to enable peer-to-peer commerce with no intermediaries. Not only can you get better prices and faster transactions, but you can also support your local merchants and keep your community thriving.
Follow us for updates on our progress, and be the first to join the open.mt community when we launch. I appreciate your support, and we can’t wait to welcome you to our open market!