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.

What is Artificial Intelligence?

What is artificial intelligence (AI)? The phrase Artificial Intelligence was coined in 1956 at a workshop. It is the branch of computer science concerned with the study of automation of intelligent behavior (Luger and Stubblefield 1992). The first successful artificial intelligent robot was Shakey the Robot, invented at the SRI International’s Artificial Intelligence Center in the early 1970s. As an hardware agent, Shakey the Robot could make plans based on the environment around it. The robot receives inputs or percepts and performs actions.

Russell and Norvig takes the concept of the hardware robot into the software realm – in other words, the software robot (or softbot) receives inputs and performs actions. This leads to the generalization of agents – whether, it is a human, robot, or softbot. This leads to the idea of rational agents, which is the combination of agent program running on architecture (also known as computer hardware). Therefore, the AI is the study of rational agents and the components that builds them (Russell and Norvig 1995).

As an engineer, my goal is to understand and implement algorithms and architecture associated with rational agents to various environments and problems. In other words, develop a tools set with a solid mathematical foundations as to implement solutions to complex problems. After understanding the single agent environments, then my next focus will be on Multiple Agent Systems in Distributive Artificial Intelligence environment.

AIMA Book

I have obtained a copy of the Artificial Intelligence: A Modern Approach (first ed) by Russell and Norvig (1995). Their approach is the study and design of agents (whether its a human, robot, or software agent) by unifying all AI topics – knowledge representation, natural langange, automated reasoning, planning, and machine learning. The book has 27 chapters and is divided into sections with the following names:

• Artificial Intelligence
• Problem-solving
• Knowledge and reasoning
• Acting logically
• Uncertain knowledge and reasoning
• Learning
• Communicating, perceiving, and acting
• Conclusions

Yes, I will encounter familiar topics and algorithms from my previous studies.

The journey continues

As I continue my AI journey, I discovered that I need to review my knowledge of probability theory and statistics. For example, I had to look up Bayes Theorem in Wikipedia, then in my college probability and statistics for engineers book. It has been a long while since I looked at probability and statistics. However, articles and works by Dr. Nils Nilsson uses probability theory and statistics and apply it to uncertainty.

Another area of interest has been the Bayesian Network (or Belief Network). There was an article in which a Bayesian Network illustrate probabilities in the leaves of trees. It is the uncertainty factor once again, but at this point I do not understand how it works, but I will sometime soon.

The last research item was the Support Vector Machine, which is a linear classification method. This method uses hyperplanes in geometric hyper space to determine the maximum distance to the hyperplane and data as to determine the maximum linear classification for the data. The current research uses nonlinear regression techniques and kernel methods to determine maximum data classification.

I am still continuing my studies in LISP programming. Like any other programming language that I have studied, you need to understand the basics and apply standard software engineering methods into the work. However, upon researching the job market, the only jobs are with research institutions or in the UK. Even with the newsgroup comp.lang.lisp, the recommendation is for an individual to focus their energy into java, html, java scripting, sql, etc.

Progress Report

I have completed my review of Artificial Intelligence: Structures and Strategies for Complex Problem Solving (2nd ed) by George Luger and William Stubblefield. I ran some of the example LISP based programs such as the Logic Shell and the Expert System Shell from Chapter 14. For each program I had to write a LISP program to load the individual programs and start the shell.

To continue my studies in machine learning, I have a draft copy of Introduction to Machine Learning by Professor Nils J. Nilsson. Professor Nilsson’s material contains a heavy dose of mathematics. I have not looked at partial dervivatives and probablity theory since my university courses in Partial differenital equations and Statistics and Probablity. After the heavy math, Professor Nilsson discusses Neural Networks with a strong emphasis in error correcting. Then later topics such as decision trees and inductive logic programming, Professor Nilsson finds similarities to Neural Nets with these topics. I basically perused the topics yesterday and today.

Then I signed onto Amazon and compared Dr. Nilsson’s book with Dr. Mitchell’s book on Machine Learning. From a topics point of view, both books are very similar.

Afterwards, going to Google and searching for Dr. Nilsson, I found his website and learned that he worked for Stanford Research Institute (known as SRI International today) in the AI Research Lab, and he graduated with his Ph.D. from Stanford University in 1959. In 1980, Dr. Nilsson and Kurt Konolige wrote a paper on Mulitple-Agent Planning Systems, one earliest papers on multi-agents on DAI pubished in the AAAI-80 Proceedings (pp 138-142).

Recent Readings

I received a copy of Machine Learning: Artificial Intelligence Approach, Volume 1 (1983) edited by Michalski, Carbonell, and Mitchell. My main interest was to read the J.R. Quinlan article Learning Efficient Classification Procedures and Their Application to Chess End Games. But also I found rest of the tome interesting. I read Herbert Simon’s article Why Should Machines Learn? 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. 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.

My AI progress

As I continue to read Luger’s book, I recently completed reading the chapters on Natural Language, Automated Reasoning, and Machine Learning. After reading the Natural Language chapter, I did not realize how complex our communication systems are. Before langauges were standardized by the printing press or the written hand, men (and, of course, women) communicated based on locality. Therefore, a communication takes place when the knowledge domain is understood as well as the context sensitivity of the language. No doubt researchers in this arena have many interesting challenges. Luger illustrates some algorithms for language parsing and illustrates language in state space via the augumented transition network (ATN), which is common tool in the natural language sphere of AI research.

The Automated Reasoning chapter touched the early research of Newell, Shaw, and Simon with the Logic Theorist and the General Problem Solver (GPS). As Luger stated these systems were the precursor to the production systems and expert systems. Back then when the computing resources were limited, their work was an achievement. After the brief introduction, then Luger discusses the Refutation Resolution theorem proving process. The rest of the chapter was devoted to illustrate examples and explains how it works.

Finally, I revisited the chapter on Machine Learning. Based on my preview and reading the introduction, the chapter covers subjects on classification (version space and ID3 algorithm), learning from examples, learining bias, explanation based learning, unsupervised learning, Parallel Distributive Processing using neural networks, and genetic algorithms. In my opinion this was the most interesting chapter read so far.

After this point in Luger’s book, the next part called Advanced AI Programming Techniques. The next three chapters are Advanced Representation in Prolog, Advanced LISP Programming techniques for Artificial Intelligence, and lastly; Objects, Messages, and Hybrid Expert System Design. I have previewed this section before. Luger illustrates various implementations of the previous topics in either Prolog or LISP programming languages. I will take the time to review this section and study the examples that I downloaded from Luger’s website.

The final part is the Epilog containing one chapter called Artificial Intelligence As Empirical Enquiry. Basically, this is summation of the book and some final thoughts about Artificial Intelligence.

From here after completing the Luger book, my next step is to get a copy of the Russell Stuart and Peter Norvig’s book Artificial Intelligence: Modern Approach. The authors take another approach and has become the most popular AI book.

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 Theorem proving in which the Logic Theorist was. 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 a head of its time and the precursor to ideas such as expert systems.

So, can the LT be recreated using modern day techniques and programming languages? Yes, since it is basically production system; the best language is Prolog since it is a natural for theorem proving. The axioms will be the facts, and new theorems can be added to the database using the assert clause. Then I will setup some rules for the substitution, replacement, and interfences using modus ponens (as known as decomposition by the LT authors). I will explore this and publish my results.

IJCAI

Recently, I found the web site for the International Joint Conferences on Artificial Intelligence (IJCAI). The site is a treasure trove of information containing its proceedings dating back to first conference in 1969. I was reviewed a few articles such as the FDS by Ross Quinlan and the earliest evolutionary computing papers. The work back 40 years ago was very basic since computing resources was limited and expensive. The language of choice was Fortran (and possibly LISP) before modern day languages such as Pascal, Prolog, C++, and Java came into existence.

I added the web site as new hyper link under AI Web Sites. Many of the articles that I read make references to papers published with IJCAI. Therefore, I will be saving a trip or two the local university.

Programming Tools

So far in my AI journey, the author of various books utilized either Prolog or LISP or both. Both languages have their purpose depending on the problem type. For example, Prolog is typically used in problem involved in backward chaining and theorem provers. An example is Advice Logic 3 (AL3). The LISP programming language has been used in expert systems (though Prolog based expert system is available).

However, I have encounter other solutions that the use of java and python such as ECJ and Orange, respectively. ECJ uses java for creating GP based system, eventhough the original work with Genetic Programming by Dr. John Koza was done in LISP. On the other hand, using Python as the language of choice, Orange is a data mining tools used to classify and to develop IF-THEN rules from data. This useful in developing knowledge based and expert systems.

Therefore, the problem defines the solution; the solution depends on the tool.