Practical_Artificial_Intelligence_Programming_in_Java.pdf

Practical Artificial Intelligence Programming in Java

Version 1.2, last updated January 1, 2006.

by Mark Watson.

This work is licensed under the Creative Commons Attribution NoDerivs NonCommercial License.

Additional license terms:

 No commercial use without author's permission

 The work is published "AS IS" with no implied or expressed warranty - you accept all risks for the use of both the

Free Web Book and any software program examples that are bundled with the work.

This web book may be distributed freely in an unmodified form. Please report any errors to

markw@markwatson.com and look occasionally at Open Content (Free Web Books) at www.markwatson.com for

newer versions.

Requests from the author

I live in a remote area, the mountains of Northern Arizona and work remotely via the Internet. Although I really enjoy

writing Open Content documents like this Web Book and working on Open Source projects, I earn my living as a

consultant. I specialize in artificial intelligence applications, software design, and development in Java, Common Lisp,

and Ruby. Please keep me in mind for consulting jobs!

Table of Contents

Table of Contents........................................................................................................................................................................................2

Preface........................................................................................................................................................................................................5

Acknowledgements........................................................................................................................................................................................... ......5

Introduction................................................................................................................................................................................................6

Notes for users of UNIX and Linux..................................................................................................................................................................... ..7

Use of the Unified Modeling Language (UML) in this book........................................................................................................ .......................7

Chapter 1. Search.....................................................................................................................................................................................10

1.1 Representation of State Space, Nodes in Search Trees and Search Operators................................................................................10

1.2 Finding paths in mazes................................................................................................................................................................................ ...12

1.3 Finding Paths in Graphs.................................................................................................................................................................. ..............19

1.4 Adding heuristics to Breadth First Search................................................................................................................................................... .26

1.5 Search and Game Playing................................................................................................................................................................... ...........27

1.5.1 Alpha-Beta search................................................................................................................................................................................................................27

1.5.2 A Java Framework for Search and Game Playing................................................................................................................................................................28

1.5.3 TicTacToe using the alpha beta search algorithm................................................................................................................................................................33

1.5.4 Chess using the alpha beta search algorithm........................................................................................................................................................................38

Chapter 2. Natural Language Processing...............................................................................................................................................46

2.1 ATN Parsers........................................................................................................................................................................................ ............47

2.1.1 Lexicon data for defining word types..................................................................................................................................................................................50

2.1.2 Design and implementation of an ATN parser in Java.........................................................................................................................................................51

2.1.3 Testing the Java ATN parse.................................................................................................................................................................................................57

2.2 Using Prolog for NLP........................................................................................................................................................................ .............58

2.2.1 Prolog examples of parsing simple English sentences.........................................................................................................................................................58

2.2.2 Embedding Prolog rules in a Java application.....................................................................................................................................................................61

Chapter 3. Expert Systems........................................................................................................................................................................64

3.1 A tutorial on writing expert systems with Jess....................................................................................................................... ......................64

3.2 Implementing a reasoning system with Jess................................................................................................................................. ................70

3.3 Embedding Jess Expert Systems in Java Programs.................................................................................................................................... .74

Chapter 4. Genetic Algorithms.................................................................................................................................................................78

4.1 Java classes for Genetic Algorithms.................................................................................................................................................... ..........81

4.2 Example System for solving polynomial regression problems..................................................................................................................... 85

Chapter 5. Neural networks.....................................................................................................................................................................89

5.1 Hopfield neural networks............................................................................................................................................................................... 90

5.2 Java classes for Hopfield neural networks.................................................................................................................................................... 91

5.3 Testing the Hopfield neural network example class.......................................................................................................................... ...........93

5.5 Backpropagation neural networks................................................................................................................................................. ...............95

5.6 A Java class library and examples for using back propagation neural networks........................................................................ ..............97

5.7 Solving the XOR Problem...................................................................................................................................................................... ......105

5.8 Notes on using back propagation neural networks.................................................................................................................... ................106

6. Machine Learning using Weka..........................................................................................................................................................108

6.1 Using machine learning to induce a set of production rules.............................................................................................................. ........108

6.2 A sample learning problem....................................................................................................................................................... ...................109

6.3 Running Weka............................................................................................................................................................................................... 110

Chapter 7. Statistical Natural Language Processing............................................................................................................................112

7.1 Hidden Markov Models................................................................................................................................................................................ 112

7.2 Training Hidden Markov Models.................................................................................................................................................. ..............114

7.3 Using the trained Markov model to tag text................................................................................................................................ ...............116

Chapter 8. Bayesian Networks...............................................................................................................................................................117

Bibliography............................................................................................................................................................................................118

Index........................................................................................................................................................................................................120

For my grandson Calvin and granddaughter Emily

Preface

This book was written for both professional programmers and home hobbyists who already know how to program in Java and who

want to learn practical AI programming techniques. I have tried to make this a fun book to work through. In the style of a “cook

book”, the chapters in this book can be studied in any order. Each chapter follows the same pattern: a motivation for learning a

technique, some theory for the technique, and a Java example program that you can experiment with.

Acknowledgements

I would like to thank Kevin Knight for writing a flexible framework for game search algorithms in Common LISP (Rich, Knight

1991) and for giving me permission to reuse his framework, rewritten in Java; the game search Java classes in Chapter 1 were loosely

patterned after this Common LISP framework and allows new games to be written by sub classing three abstract Java classes. I would

like to thank Sieuwert van Otterloo for writing the Prolog in Java program and for giving me permission to use it in this free web

book. I would like to thank Ernest J. Friedman-Hill at Sandia National Laboratory for writing the Jess expert system toolkit. I would

like to thank Christopher Manning and Hinrich Schutze for writing their “Foundations of Statistical Natural Language Processing”

book; it is one of the most useful textbooks that I own. I would like to thank my wife Carol for her support in both writing this book,

and all of my other projects. I would also like to acknowledge the use of the following fine software tools: IntelliJ Java IDE and the

Poseidon UML modeling tool ( www.gentleware.com ).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: