Development

Expert Systems: How to implement a backward chaining resolver in Python

An expert system is a tool capable of reproducing cognitive mechanisms. It can resolve queries from a set of known facts and rules.

Photo by Maël BALLAND / Unsplash

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

Rules

First the system receive a set of rules. Rules are equations that combine facts with connectors. Facts are in this case represented by uppercase letters, and connectors can be one of:

&: AND — All operands must be True.
|: OR — Only one operand need to be True.
^: XOR — One operand must be True and the other False.
=>: IMPLY — If the left side is True then the right side must be True.

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 false or 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 ?XXX notation.

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:

the AtomNode, for example A, B or C.
the ConnectorNode: for AND, XOR, OR and IMPLY

That’s why Python seemed to be the best fit, for its simplicity and object oriented properties.

Data structure

Node class

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 B. If A is true, then we deduct B is true.

All the subclass AtomNode and ConnectorNode inherit from this class.

AtomNode class

ConnectorNode class

The resolver

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 AtomNode instance.

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!