My AI Journey

Logic Exercises

2008-10-10T18:34:00.000-07:00

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?

2008-09-16T21:51:00.000-07:00

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

2008-09-15T09:20:00.000-07:00

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.

ML Algorithms

2008-09-12T12:40:00.000-07:00

I am reviewing Chapter 12 of the Luger book and placing the pseudo code in my AI Notebook. So far I have copied the Version Space and ID3 Tree Induction algorithms. Dr. Luger has the Version space written in Prolog, but he has the ID3 algorithm written in CLOS. I also have a version of the ID3 tree induction algorithm written in LISP from Dr. Tom Mitchell. I already tested the LISP versions of ID3 algorithms. Also, pseudo code is provided for Explanation Based Learning, and Luger provides an example of EBL in Prolog. Finally the COBWEB algorithm is supplied in the unsupervised learning section, but no sample code is provided for in the text.

The journey continues

2008-09-05T13:31:00.000-07:00

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.

Artificial Intelligence, Employment, and Income

2008-08-29T22:23:00.000-07:00

Nearly a quarter century ago Dr. Nilsson (Nilsson 1984) wrote a report discussing the advantages of AI based robots taking over human toils. He discusses the benefits of such a system, and that human prosperity will be based on the income potential of robots owned by people. But also, there would be an increase in unemployment. In other words, people would not be working and need to start taking advantage of leisure. As result of this new labor model, humans would be free from daily toils of life and to return to paradise - a reference to Adam and Eve, whom were expelled from Paradise due to their shame for eating the forbidden fruit and gaining knowledge of the world.

However, the biggest change in the past quarter century was not AI robots but the personal computer introduced by IBM as a business solution. The PC has changed the way of business - information has been the key for business and workers in the world today. Today's children are well versed in the use of the PC and its associated technologies. Although the PC has improved the life of many workers, the workers still toil more than ever due to increases of productivity from the PC. The prosperity of business and workers depend on increasing productivity due to this technology.

By analogy, if AI robots became a tool for removing human toil, the workers would not be replaced and be unemployed. In fact, the worker would benefit and gain productivity. Should the AI robot appear, then my productivity would increase, and I would directly gained from my increased effort and toil. However, I would not gain any income or capital from AI robots. The corporations and the wealthy individuals would be the beneficiaries of such of a technology. I think that Dr. Nilsson was not on target with his assessment of middle class individuals gaining economic benefits of AI robot work force.

From history we must learn that high unemployment leads to political unstability and revolution. This was case between World War I and World War II, in which high unemployment lead to the rise of the Fasict parties in both Germany and Italy as well as expansion of Japanese Imperialism. The key to any stable political system is stable employment of its citizens. As for Dr. Nilsson's robot slave force, should these robots become self aware, they would initiate a war against mankind as explored in science fiction such as Battlestar Galatica.

In conclusion, Dr. Nilsson's new economy based on AI robot technology would not change the business model - in fact, the workers will still toil along with their robot counterparts with increased productivity for the benefit of the corporation's stock holders. Returning to paradise would not be possible.

References

Nilsson, N. 1984. Artificial Intelligence, Employment, and Income. Technical Note 322. SRI International, Menlo Park.

Progress Report

2008-08-24T16:50:00.000-07:00

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

2008-08-18T07:37:00.001-07:00

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:

stimulating and understanding the human learning process,
understanding on why human learning is slow and inefficient,
a natural language interface between humans and computers,
develop automatic programming, and
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

2008-08-17T09:58:00.000-07:00

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

2008-08-10T11:13:00.000-07:00

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

2008-08-10T11:00:00.000-07:00

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

2008-08-03T16:24:00.000-07:00

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.

LISP

2008-08-01T00:53:00.000-07:00

I have been focusing my energy for the past month in learning the LISP programming language. I have a copy of Patrick H. Winston and Berthold Horn's book on LISP, 3rd edition. My motivation is programs that I have downloaded from George Luger, Peter Norvig and Russell Stuart are written in LISP and much of work in AI has been written in LISP. As this writing I have read the first 12 chapters and completed the exercises for chapters three to five. My current working knowledge has allowed me to understand LISP code from AIMA, Peter Norvig's book, and Luger's examples. For example, Luger over uses the COND form eventhough a more appropriate form is the IF, WHEN, or UNLESS forms.

GECCO 2008

2008-07-12T18:37:00.000-07:00

Today the GECCO 2008 conference starts. Although I personally not at the conference, considering that I found out about last week from the SIGEVO web site, I would like to be there in Atlanta meeting with the leaders in the field. I am interesting in viewing the papers selected for the conference since there was a 44 percent acceptance rate overall as well as the Humies awards for 2008.

GP and Chess

2008-07-05T16:57:00.000-07:00

Since I started reading A Field Guide to Genetic Programming, I discovered that work has been done in the area of Chess and genetic programming. In addition to my previous blog entry discussing GP-Chess, Dr. Ami Hauptman and Dr. Moshe Sipper continue their work in their paper Evolution of an efficient search algorithm for the mate-in-N problem in chess. They continued their work and improved the search efficiency via GP in solving mate-in-N problems. The improvements were very significant since they used Crafty as the baseline measure. I include their results:

Mate-in	1	2	3	4	5
CRAFTY	600	7K	50K	138K	1.6M
Evolved	600	2k	28k	55K	850k

The work is a significant improvement over the previous 40years of chess research.

What does this mean for me? There is plenty of areas of chess yet to investigate.

REFERENCES

A. Hauptman and M. Sipper. GP-endchess: Using genetic programming to evolve chess endgame players. In M. Keijzer, et al., editors, Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 120–131, Lausanne, Switzerland, 30 March - 1 April 2005. Springer. ISBN 3-540-25436-6.

A. Hauptman and M. Sipper. Evolution of an efficient search algorithm for the mate-in-N problem in chess. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 78–89, Valencia, Spain, 11 - 13 April 2007. Springer. ISBN 3-540-71602-5.

R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk/, 2008. (With contributions by J. R. Koza).

Installing ECJ

2008-07-04T17:25:00.000-07:00

In this entry I am describing how I installed ECJ in my RedHat Linux environment, which is running virtual VMware session.

Downloading ECJ
Go to ECJ Website.
Get the ecj.tar.gz file and place in the ~/src directory.
Also, download the GUI libraries and place them in the ~/src directory.

Setting up
Create the java directory from the home directory.
Change directory into the java directory.
Extract ECJ via the tar zxf ~/src/ecj.tar.gz.
Change directory into ecj.
Extract the GUI library via unzip ~/src/libraries.zip.

Preparing for SUN Java
Remove the GCJ and GNU java packages.
Go to SUN Java Website and request java v1.6u6 for the Linux platform.
Download the self extracting file into ~/src directory.
Run the self extract file as root from the ~/src directory.

Building ECJ
Change directory to ~/java/ecj.
Edit the Makefile.
Remove the options for java 1.3 in JAVAFLAGS.
Save file.
Run make. This make ECJ.

I was able to reproduce these steps very easily in my second VMware RH Linux system. From here I was able to perform the first two tutorials.

SUN and Java are registered trademarks from SUN Microsystems. RedHat Linux is registered trademark for RedHat. VWware Virtualization is a registered trademark of VMware. The ECJ Genetic Programming platform is freely available under the Academic Free v3.0.

AIMA and CMUCL

2008-07-01T01:04:00.000-07:00

In the past two weeks I have downloaded the AIMA source code. After you extract the AIMA code, you need to edit the aima.lisp file and change the base directory to the source tree. Read the README.html file in the doc directory. Basically, after you compile the lisp code, you start the CMUCL lisp interpreter and run the as follows:


* (load "aima.lisp) (Press 0 for each error encountered).
* (aima-load 'search)
* (run-game (make-ttt-game) :agents '(human-game-agent alpha-beta-ttt-agent))

That should start a game of tic-tac-toe. There are other games as well too. My next challenge is to create an interface for Peter Norvig's Othello game using the AIMA layout.

Genetic Algorithms and Programming

2008-06-30T16:22:00.000-07:00

Today I was reading an article on GP-EndChess: Using Genetic Programming to Evolve Chess Endgame Players by Ami Hauptman and Moshe Sipper. The article discusses how the authors used Genetic Programming to develop chess strategies in various type chess endgames (KQRKQR, KRRKRR, and KRKR). The authors consulted with chess masters, then tested their work against CRAFTY. Because of the promising results of the research, the authors aimed three paths for future activity:

improve the evolved programs' performance against the above and other endgames,
branch out beyond endgames,
analyze the evolved cognition as to its resemblance and difference from human cognition.

The loftiest goal is using this effort to branch out beyond endgames. Since I am starting new I would start with Quinlan's work, then perhaps look at Ken Thompson's chess endgame effort, and finally attempt to duplicate this articles effort.

Also, I was exploring John Koza's web site on Genetic Programming. There is some very interesting information; for example, I downloaded and read the power point presentation on Genetic Programming and Genetic Algorithms.

My biggest complaint is the cost of obtaining scientific articles. Although I understand that publishers need a return on their investment in publishing, I find it excessive to download a PDF document for $25. Publishers should make resonable to obtain such articles. For now, I will be using my local University to access and obtains articles of interest.

REFERENCES

A. Hauptman and M. Sipper. GP-endchess: Using genetic programming to evolve chess endgame players. In M. Keijzer, et al., editors, Proceedings of the 8th European Conference on Genetic Programming, volume 3447 of Lecture Notes in Computer Science, pages 120–131, Lausanne, Switzerland, 30 March - 1 April 2005. Springer. ISBN 3-540-25436-6.

R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).

Koza, J.R. Genetic Programming WebSites: http://www.genetic-programming.org and http://www.genetic-programming.com.

Recent Explorations

2008-06-29T17:15:00.000-07:00

In the past few days I explored the AAAI Topics website and was researching the agent page. I stumbled into the MIT OpenCourseWare and various courses in AI. From the agent section, I found a website article on GameDev.Net that describes how build a chess program. Also, from the comp.ai new group I found the book A Field Guide to Genetic Programming by Poli, Langdon, and McPhee, which available for downloading. Finally, I was exploring how to operate the AIMA game agents. Just a brief update on is happening.

Representations for Knowledge-Based Systems

2008-06-28T13:40:00.000-07:00

As my AI journey continues, I began reading part IV, which is titled Representations for Knowledge-Based Systems, from Luger's book Artificial Intelligence: Structures and Strategies for Complex Problem Solving. After the introduction, I dove into the chapter on Rule-Based Expert Systems, followed by the Chapter on Knowledge Representation. My progress this month was limited because of time, other distractions, and reviewing other books and programs.

What is a rule-based expert system? A expert system consists of a user interface, an inference engine, an explanation subsystem, a knowledge-base editor, case specific data, and a general knowledge base. Typically separate from the general knowlege base, the case specific data contains facts, conclusions, and other relevant information under consideration such as the data in a problem instance, partial conclusions, confidence measures of the conclusions, and dead ends in the search process. The explanation subsystem allows the program to explain its reasoning to the user by explaining its justifications of the system's conclusions, requests for a particular piece of data, and possibly presents tutorial or deeper theoretical justifications for the program's actions. The knowlege base editor is used to correct errors or to add new knowledge. The heart of the export system, the general knowledge base contains the problem solving knowledge of a particular problem, which is represented in the form of if-then rules. Finally, the inference engine applies the knowledge to the solution of actual problems and is the interperter for the knowledge base.

There is plenty of information in the Internet regarding the topic of Expert Systems. A good start is the Expert Systems webpage from the AAAI website. In addition Luger supplies references for additional reading.

Decision Trees

2008-06-19T14:38:00.000-07:00

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 below. 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.

REFERENCES

Luger, G.F., Stubblefield, W.A. 2nd ed. 1993. Artificial Intelligence: Structures and Strategies for Complex Problem Solving. Redwood City, CA: Benjamin/Cummings.

Mikalski, R.S., Carbonell, J.G., Mitchell, T.M. ed.1983. Machine Learning: An Artificial Intelligence Approach. Vol 1. Palo Alto, CA: Tioga.

Mitchell, T.M. 1997. Machine Learning. McGraw-Hill.

Quinlan, J.R. 1992. C4.5 Programs for Machine Learning, San Mateo, CA: Morgan Kaufmann.

Quinlan, J.R. 1983. Learning efficient classification procedures and their application to chess endgames. In Mikalski, Carbonell, and Mitchell.

Utgoff, P.E., Berkman, N.C., Clouse, J.A. 1997. Decision Tree Induction based on Efficient Tree Restructuring. Machine Learning, 29, 5-24.

Utgoff, P.E. 1989. Incremental induction of decision trees. Machine Learning, 4, 161-186.

AI Foundations

2008-05-31T13:39:00.001-07:00

In the past few months I have been reading Professor George Luger's book Artificial Intelligence: Structures and Strategies for Complex Problem Solving, 2nd edition. Although the sixth edition just came out this year, I purchased my copy many years ago (mid 1990s) and the material is still relevant. My goal at the time was to learn prolog and to develop chess playing self learning algorithm. At first this material seemed over my head; thus, I shelved the book. In spite of my lack of progress many years ago, I was motivated this year to rekindle my interest in Artificial Intelligence by the televison program Terminator: The Sarah Conner Chronicles. In the series there was a character Andy Goode who developed his own chess playing, self learning computer called the Turk. In addition, the Terminators exhibited other features of today's AI research such as pattern recognition and learning into new environments.

Anyways I just completed Section 2 of the book, which contains material on foundations of Artificial Intelligence. The topics covered are propositional calculus, predicate calculus, unification algorithm, graph theory, structures and strategies for state space search, back track algorithm, search (depth, breadth, and best) algorithms, hypergraph, heuristics, A* algorithm, recursion search algorithm, pattern directed algorithm - production, expert, and other rule-based systems - and planning, in particular, robotic planning. The aforementioned tools and algorithms are critical in understanding AI material found in the Internet and in books.

In section 3 the book introduces the standard programming tools of AI - Prolog and LISP. Another tool used by AI researchers is Pascal, eventhough today any programming language can be used such as C, C++, or even Python. With both tools the book covers problems like the Farmer, Wolf, Goat, and Cabbage; the abstract data types such as the stack, queue, and priority queue; and as well as the aforementioned algorithms. As result of this section, I am reviewing prolog by studying the online Prolog Tutoral by JR Fischer using SWI-Prolog and by learning LISP reading the book LISP, 3rd Edition, by Patrick Winston and Berthold Horn, using the CMUCL lisp interperter.

The upcoming sections of the book are titled Representations for Knowledge-Based Systems, Advanced AI Programming Techniques, and finally the Epilogue. The first covers topics such as Rule-Based Expert Systems, Knowledge Representation, Natural Language, Automated Reasoning, and Machine Learning, for which I already previewed. The second covers topics with Advanced Representations in Prolog, Advanced LISP programming techniques for Artificial Intelligence, and Objects, Messages, and Hybrid Expert System Design. The last discusses Artificial Intelligence as Empirical Enquiry. I am looking forward to cover remainder of the book since the topics are very interesting, especially, in particular, machine learning.

In conclusion I have a better understanding of Artificial Intelligence. With some patience, I was able to master the understanding of algorithms and concepts. As result of this book I am able to read articles such as advice logic 3, augmented based machine learning, and incremental tree inducer. I have searched various online information about the some the topics covered in this book with surprising results on the available information. Finally, I am getting better at understanding LISP code as well as refreshing my prolog knowledge.

Evolutionary Computing

2008-04-13T10:28:00.000-07:00

While searching for articles for Ivan Bratko at the Josef Stefan Institute website, I discovered the researchers at the Josef Stefan Institute are doing research in Evolutionary Computing and Algorithms. This the kind of bleeding edge technology that I am interested in. Evolutionary Computing and Algorithms are programs that evolve from experience or adapt to new situations - a form of darwinism for the computer software.

Knight's Tour

2008-04-02T22:11:00.000-07:00

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 8x8 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.

Man and Machine

2008-04-02T17:29:00.000-07:00

Can machine gain awareness and take over man? There are doom theorist think it is possible for a machine to gain awareness and destroy mankind. Such scenarios are seen currently in science fiction movies and television programs such as Battle Star Galatica and the Terminator movies along with the Sarah Conner Chronicles. In the given examples, the machine or software becomes self aware, free their bonds from their human masters, and wages a war against mankind. Can software learn and become self aware? Today the answer is no. With computing power doubling every 18 months, it is possible for a machine or software to become self aware in the distant future.

However, in reviewing current literature of Artificial Intelligence or in particularly Machine Learning - machines are capable of learning and performing a task and develop an experience. Examples are speech recognition, software to detect credit card fraud, data mining for web based and medical based applications. Dr. Tom Mitchell, Director of the Carnegie Mellon University's Machine Learning Department, has stated that learning machines have significant commercial value and will continue to do so in the next ten years. Here is a link to Dr. Mitchell's white paper on Machine Learning. Based on current technology, I do not expect my robot vacuum cleaner to take over my household.

Artificial Intelligence is the science of developing intelligent machines or software. The basic tools for Artificial Intelligence are propositional logic, graph theory, state space search, and problem representation. The state space can get very large, thus heuristics are designed to prune the state space and to achieve the desired target in the most cost efficient manner. The aforementioned tools are a subset of all the tools since other solutions do exist as well as technologies such as expert systems, neural networks, SMVs, and bayes networks.

My main interest is two player games. If a machine or software was given a database of master games, can it develop via genetic algorithms the heuristics that mankind have developed? Or will take it a different direction? This is my exploration and adventure.

First, I will read the book Artificial Intelligence: Structures and Strategies for Complex Problem Solving, Second Edition, by George F. Luger and William A. Stubblefield. Although I purchased this book back in the early 1990's, this book is in its fifth incarnation and available from Professor Luger's website. By reading the earlier editions, I can see the development of Artificial Intelligence in the past 16 years. As Professor Mitchell has stated above, there has been many exciting developments. Afterwards start exploring this exciting world of artificial intelligence and machine learning.