Advice Language

Back in 1990, since my goal back then was to develop a chess playing computer algorithm using prolog, as part of my research, I stumbled into Max Bramer’s book Computer Game Playing: Theory and Practice.  In that book there was a chapter by Ivan Bratko called Knowledge-based problem-solving in AL3, which according to the book the article appeared in Machine Intelligence 10.  In summary the AL3 system was basically a production system for chess problem using the Donald Michie Advice Language concept and utilizing Bratko’s IF condition THEN action rule concept.  At that moment of time, many of the concepts presented in the paper were foreign to me, and unbeknownst to me, many of the ideas are presented in Bratko’s AI book (1990).

Unification

Recently reviewing a blog on knowledge representation and predicate calculus, I noticed the blog writer handled poorly the topic of unification and resolution theorem proving.  The writer stated that unification had to with matching Prolog data structures – that is true for the Prolog programming language since unification and resolution are built into the language.  At first I thought and understood unification algorithm provided by Luger (1993).  Nevertheless, upon reviewing the Unification section, I realized that I missed some the critical points and updated my OneNote Notebook by adding a new page discussing the Unification topic and extracting the important concepts.  In addition, I added details to the Unification algorithm.

Before we can be begin the the Unification topic, please review the recommended websites in Wikipedea for the subjects of propositional calculus and predicate calculus.  The links are excellent.

Unification and resolution principle was developed and published in 1965 by John Alan Robinson when he was visiting researcher at the Argonne National Laboratory’s Mathematics Division.  His paper A machine-oriented logic based on the resolution principle is the basis for all theorem provers and eventually lead to the development of the Prolog programming language.

Basically unification is ability of an inference system to match two expressions.  In propositional calculus this task is very trival.  However, in predicate calculus, the task is more involved since a number of issues require resolution.  Basically, the existential variables require to be set to constants in the logical database.  Next, the universal quantifier variables can be computed, if possible.  The next issue is if variable is itself in a function, which could lead to infinite assignment – thus the occurs check is required to test this condition.  Once a variable is bound, then that assignment must consistent, otherwise, it leads to less generality.  Also, there is the issue of composition of variables.  Finally, the concept of the most general unifier (mgu).

At last the introduction to the unification algorithm pseudo code.  Basically the unify functions requires the two expression be in the form of s-expressions.  For example,

p(X) becomes (p X), p(a, f(b, c)) becomes (p a (f b c)).

The above format makes it easier to work with a functional language such as LISP.  I enclosed my version of the unify pseudo code:

function unify(s1, s2) returns either { fail, {}, {Unification} }
begin
     he1 <- first element of s1
     he2 <- first element of s2
     if both he1 and he2 are constants and if he1 = he2,
               then return {} else return fail.
     if he1 is a variable and is present in he2,
               then return fail else return {he2/he1}
     if he2 is a variable and is repsent in he1,
               then return fail else return {he1/he2}
     result1 <- unify(he1, he2)
     if result1 is fail, then return fail.
     apply substitutions from result to rest of s1 and to rest of s2
     result2 <- unify(rest s1, rest s2)
     return compose result1 result2
end

I have presented the pseudo code for a version of the unify function, which is a generalized symbolic matching algorithm, and have seen various versions of the unify function in the Internet, in Luger(1993), and in Winston and Horn (1989).  Finally, much research has been done to make the unification algorithm as linear as possible.

Decision Trees

I have been reading about decision trees, which induces concepts from examples. According to Luger (1993), the earliest is the ID3 tree induction algorithm, which was developed and experimented by Ross Quinlan back in the late 1970s and early 1980s. After the development of ID3 algorithm, Paul Utgoff (1989) developed the ID5 algorithm.

Ross Quinlan (1983) describes how the ID3 algorithm was used to identify positions, using the white king and white rook versus the black king and knight endgame as the domain set, that lead to a loss for black in n-ply moves after processing a training set. Therefore, by using a tree structure, the idea is to classify the training set and induce a rule set. In the experiments, the larger the training set, the more accurate the induction rules became in classifying and identifying a position more accurately. The problem was back then was computing resources were limited compared to today’s PCs. So, if the training set was modified, then entire training set was processed in a batch and the new tree induction was created.

Ross Quinlan (1992) continued his work with tree induction algorithms and developed the RC4.5 algorithm. His work continued until he developed RC5.0 algorithm, a closed propriety algorithm used for commercial data mining applications.

Utgoff (1989) developed the ID5 tree induction algorithm. The purpose of the ID5 tree induction algorithm was to modify the induction tree if a second training set was added to the existing training set. Instead of batching the entire training set, ID5 algorithm modified the existing tree because the cost of rebuilding tree was expensive. In addition, the ID5 algorithm had yield the same tree as the ID3 algorithm. Utgoff (1997) continue his work in this field and developed the Incremental Tree Induction algorithm.

Much of the above research was found in the Internet by using Goole to search various topics as the references below. The idea for decision trees is to take a training set from a domain set, develop a decision tree, generate a rule set, and validate against a test set. I forsee this effort in the development knowledge bases for expert systems and other rule based systems.

The above is not a theoretical discussion about the ID3, RC4.5, RC5, ID5, and ITI algorithms. For specifics and details, read the references in the reference page.  The authors may have sample code available – typically in LISP (Luger and Mitchell). Quinlan and Utgoff have restrictions for the use of their code base.