CODEWITHSUNDEEP
pythonalgorithmexpert-system
Adelov
Adelov

Reputation: 395

Backward and forward chaining algorithm for (expert system) in Python

I'm looking for the algorithm of backward and forward chaining to implement it with Python. I looked on the internet, but I didn't find too much. I looked in Wikipedia too but I just found some rules and I didn't find the algorithms.

Upvotes: 5

Views: 16082

Answers (3)

Innovations Anonymous
Innovations Anonymous

Reputation: 134

After searching the net and finding only walls of text, I relaxed the search parameters to 'forward chaining pseudocode'. This is the best description of the algorithm I could find. And this is the best I can do to get the basic skeleton down in Python. Clearly there are some symbols and concepts I don't know.

#! /usr/bin/env python3

# if I understand correctly,
# we won't be chaining in any direction
# without some sort of FOL unification algo
from unification import unify

def forward_chain(KB, f):
    if f in KB:
        return
    KB.append(f)
    for c in KB:
        if unify(c, f) == ???: # idk what that symbol is
            kb = list(KB)
            kb.remove(c)
            find_and_infer(KB, kb, d, ???)

def first(conditions):
    return conditions[0]
def rest(conditions):
    return conditions[1:]

def find_and_infer(KB, conditions, conclusion, ???):
    if conditions == []:
        forward_chain(KB, subst(???, conclusion))
    else:
        for f in KB:
            if unify(f, subst(???, first(conditions))) = ???2:
                find_and_infer(KB, rest(conditions)), conclusion, COMPOSE(???, ???2))

Upvotes: 0

Anderson Green
Anderson Green

Reputation: 31850

Forward-chaining inference engines can be implemented relatively easily in Python. This is a list of inference rules:

mammal(A) ==> vertebrate(A).
vertebrate(A) ==> animal(A).
vertebrate(A),flying(A) ==> bird(A).
vertebrate("duck").
flying("duck").
mammal("cat").

These rules can be translated into Python:

global facts
global is_changed

is_changed = True
facts = [["vertebrate","duck"],["flying","duck"],["mammal","cat"]]

def assert_fact(fact):
    global facts
    global is_changed
    if not fact in facts:
        facts += [fact]
        is_changed = True

while is_changed:
    is_changed = False
    for A1 in facts:
        if A1[0] == "mammal":
            assert_fact(["vertebrate",A1[1]])
        if A1[0] == "vertebrate":
            assert_fact(["animal",A1[1]])
        if A1[0] == "vertebrate" and ["flying",A1[1]] in facts:
            assert_fact(["bird",A1[1]])

print(facts)

From the initial set of facts, the inference engine generates this list:

[['vertebrate', 'duck'], ['flying', 'duck'], ['mammal', 'cat'], ['animal', 'duck'], ['bird', 'duck'], ['vertebrate', 'cat'], ['animal', 'cat']]

Upvotes: 5

Guy Coder
Guy Coder

Reputation: 24996

I know you originally tagged your earlier question with Python so I will limit this to just Python.

When looking for code examples one good place to look is in the Github repositories. Querying for backward chaining and then limiting the results to Python will yield this query You can do the same for forward chaining.

Note that you will have to find the code samples you like and then thoroughly test it before making using of it. There are great examples there, but more likely attempts at it that are incorrect. Plan to spend a few days with them and create lots of test cases. All of the code there comes with no guarantees.

If you want just the algorithm then find books for Artificial Intelligence such as Artificial Intelligence ... by George F Luger or Artificial Intelligence ... by Russell and Norvig.

Upvotes: 7

Related Questions