Why Should Machines Learn?

In the article Why Should Machines Learn? (Simon 1983), I found his thesis compelling and his recommendations for further research are as follows:

1. stimulating and understanding the human learning process,
2. understanding on why human learning is slow and inefficient,
3. a natural language interface between humans and computers,
4. develop automatic programming, and
5. using the computer for discovery of new ideas.

The only areas based on my current knowledge that has made progress in the past 25 years are automatic programming and cognitive science. In the field of cognitive and brain sciences, cognitive scientists are applying mathematical models from machine learning to human learning.  In the paper Bayesian Modeling of Human Concept Learning (Tenenbaum 1999), Josh Tenenbaum applies Bayesian Modeling from machine learning techniques to human concept learning.  He proposes “a principled Bayesian model based on the assumption that the examples are a random sample from the concept to be learned. The model gives precise fits to human behavior on this simple task and provides qualitative insights into more complex, realistic cases of concept learning.”

In the speech recognition arena, machines are able to recognize human speech due to new mathematical approaches.

The discovery of new ideas has been achieved with evolutionary computing and genetic programming arenas. With the introduction of the humies award, a number of old ideas and engineering designs have been revisited and improved. Still there is plenty to do based on Simon’s recommendations.

Logic Theorist

Reading Chapter 11 of the Luger book, I originally skimmed over the topic of the Logic Theorist (LT) and the refutation resolution. The chapter was devoted to automated reasoning and theorem proving. Logic Theorist was a symbolic pattern matching algorithm with basic theorem proving capability.  I was curious about the LT and found it in Wikipedia. It gave a brief overview of the program, the inventors of the software (Newell, Shaw, and Simon), and a hyper link containing the original technical report by the inventors of the program dating over 50 years ago. After reading the report, it was very interesting that the creators of LT written a production system for solving mathematical theorems based on five axioms. The work was ahead of its time since the only programming language available was IBM assembly language.

So, can the LT be recreated using modern day techniques and programming languages? Yes, since it is basically production system with symbolic pattern matching.

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.

Knight’s Tour

As part of my earlier studies into Artificial Intelligence, I was challenged to write a prolog program to solve the knight’s tour for an 8×8 board. I had early success using UNSW4 prolog interperter on SCO Unix machine, and the program resolved a path in 45 minutes in early 1995. Later that year, using the same prolog program and prolog interperter, the program resolved the knight’s tour on Sparc Center 2000 in 25 minutes. In my opinion I accomplished quite a feat. My code was influenced by Clocksin and Mellish book Programming in Prolog, which had an example of depth first search algorithm.

Here is the original prolog code for UNSW prolog interperter.

% The knight's tour puzzle for an 8x8 board.
% Written by Robert Borrell
%
% To find solution,
%        type knight_tour([1,8], X)? on interpreter line.
%
% The following clauses are from Programming in Prolog by Clocksin
% and Mellish:
%
%   membership,
%   rev, and
%   append
%
% Verify clause
verify(X,Y) :- X > 0 , X < 9, Y > 0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Classical membership test
%
member(X,[X|T]).member(X,[H|T]) :- member(X,T).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(Place,T,R,L) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R,L1),
        L is L1 + 1.go0(X,T,[X|T], 1).
%
% Classical rev clause
%
rev([],[]).
rev([H|T],L) :- rev(T,Z), append(Z,[H],L).
%
% Classical append clause
%
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R, Len),
        Len == 64,
        rev(R, Solution),
        !.

Recently I have ported the UNSW prolog interperter to a RHEL 4.5 in VMWare environment on a PC running 3.0 GHz Intel processor. The result was the program resolved a path in 35 seconds.

However, I modified the same code above and ported to GNU Prolog, the result is simpler:

%
% Verify clause
%
verify(X,Y) :- X > 0 , X < 9, Y > 0 , Y < 9.
%
% Knight move rules
%
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C + 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C + 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 2 , Y is C - 1 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R - 1 , Y is C - 2 , verify(X,Y).
knight_move([R,C],[X,Y]) :- X is R + 1 , Y is C - 2 , verify(X,Y).
%
% Depth Search Algorithm dervived from Programming in Prolog
%
go0(X,T,[X|T]).
go0(Place,T,R) :-
        knight_move(Place,Next),
        not(member(Next,T)),
        go0(Next,[Place|T],R).
%
% knight_tour clause
%
knight_tour(Start, Solution) :-
        go0(Start, [], R),
        length(R, Len),
        Len == 64,
        reverse(R, Solution).

The irony is that Luger in Artificial Intelligence: Structures and Strategies for Complex Problem Solving treats the knight’s tour problem as a simple student exercise, in which he not only challenges the student to resolve in Prolog, but also in LISP, the premier AI programming language for which I have little experience with.

Logic Exercises

Although I have finished reading the Luger book, I am working on the exercises for each chapter starting with chapter 2. The propositional and predicate calculus exercises are interesting. I completed all the exercises except for the unify function. Otherwise I have been very busy.

I recently acquired the book Experiments in Induction by Hunt, Marin, and Stone (1966). Basically, this book is an accumulation of effort in the Concept Learning using the program called Concept Learning System (CLS) from 1961 to 1965. The rational for acquiring this book is due to many authors referencing this book. In the book the authors focus on the subject of conceptual learning, which leads to three different areas – pattern recongition, data classification, and induction. The book covers a number of experiments and enumerates a list of potential applications. Although LISP was in its infancy, the programs listed are written in IPL and the last one CLS-9 was in Algol programming language.

In addition I found an online version at Questia website of Hunt’s book (1962) Concept Learning: An Information Processing Problem. I was able to read the first eleven pages before the site informed me to join site. The subscription rate is $9.95 per month for one subject area or $19.95 for unlimited access. The subject of conceptual learning is ongoing effort back in the 1950s and 1960s since the cognitive and computer scientists alike were studying on how a person develops concepts, then implement into a computerize algorithm. This effort was a collaboration between Hunt and Hovland.

This activity was triggered because I am still reading Machine Learning: An Artificial Intelligence Approach edited by Michalski, Carbonell, and Mitchell (1983) with Chapter 3 reading the survey written by Dietterich and Michalski called A Comparative Review of Selected Methods for Learning from Examples.

Logic Exercises

Although I have finished reading the Luger book, I am working on the exercises for each chapter starting with chapter 2. The propositional and predicate calculus exercises are interesting. I completed all the exercises except for the unify function. Otherwise I have been very busy.

I recently acquired the book Experiments in Induction by Hunt, Marin, and Stone (1966). Basically, this book is an accumulation of effort in the Concept Learning using the program called Concept Learning System (CLS) from 1961 to 1965. The rational for acquiring this book is due to many authors referencing this book. In the book the authors focus on the subject of conceptual learning, which leads to three different areas – pattern recongition, data classification, and induction. The book covers a number of experiments and enumerates a list of potential applications. Although LISP was in its infancy, the programs listed are written in IPL and the last one CLS-9 was in Algol programming language.

In addition I found an online version at Questia website of Hunt’s book (1962) Concept Learning: An Information Processing Problem. I was able to read the first eleven pages before the site informed me to join site. The subscription rate is $9.95 per month for one subject area or $19.95 for unlimited access. The subject of conceptual learning is ongoing effort back in the 1950s and 1960s since the cognitive and computer scientists alike were studying on how a person develops concepts, then implement into a computerize algorithm. This effort was a collaboration between Hunt and Hovland.

This activity was triggered because I am still reading Machine Learning: An Artificial Intelligence Approach edited by Michalski, Carbonell, and Mitchell (1983) with Chapter 3 reading the survey written by Dietterich and Michalski called A Comparative Review of Selected Methods for Learning from Examples.