Slides for the book

Copyright © 2009, W. Ertel 1

Slides for the book

Introduction to Artificial Intelligence

Wolfgang Ertel

Springer-Verlag, 2011

www.hs-weingarten.de/~ertel/aibook

www.springer.com

last update: October 31, 2013

Contents

References 3

1 Introduction 13

2 Propositional Logic 39

3 First-order Predicate Logic 76

4 Limitations of Logic 141

5 Logic Programming with PROLOG 161

6 Search, Games and Problem Solving 190

7 Reasoning with Uncertainty 246

8 Machine Learning and Data Mining 348

9 Neural Networks 509

10 Reinforcement Learning 588

Bibliography

The RoboCup Soccer Simulator. http://sserver.sourceforge.net 3

Alpaydin, E.: Introduction to Machine Learning. MIT Press, 2004 8.8, 9.6

Anderson, J./Pellionisz, A./Rosenfeld, E.: Neurocomputing (vol. 2): direc￾tions for research. Cambridge, MA, USA: MIT Press, 1990 9.8

Anderson, J./Rosenfeld, E.: Neurocomputing: Foundations of Research. Cam￾bridge, MA: MIT Press, 1988, Sammlung von Originalarbeiten (document), 1,

9.8

Bartak, R.: Online Guide to Constraint Programming. http://kti.ms.

mff.cuni.cz/\protect\unhbox\voidb@x\penalty\@M\{}bartak/

Copyright © 2011, W. Ertel 4

constraints, 1998 5.8

Barto, A. G./Mahadevan, S.: Recent advances in hierarchical reinforcement

learning. Discrete Event Systems, Special issue on reinforcement learning, 13

2003, 41–77 10.1

Bellman, R.E.: Dynamic Programming. Princeton University Press, 1957 10

Berrondo, M.: Fallgruben fu¨r Kopffu¨ssler. Fischer Taschenbuch Nr. 8703,

1989 2.4

Bibel, W.: Deduktion: Automatisierung der Logik. Volume 6.2, Handbuch der

Informatik. Oldenbourg, 1992 3.5, 3.5, 3.9

Billard, A. et al.: Robot Programming by Demonstration. In Siciliano, B./

Khatib, O., editors: Handbook of Robotics. Springer, 2008, 1371–

1394 10.2

Bl¨asius, K.H./Burckert, H.-J.: ¨ Deduktionssysteme. Oldenbourg, 1992 3.5, 3.9

Copyright © 2009, W. Ertel 5

Bratko, I.: PROLOG: Programmierung fu¨r Ku¨nstliche Intelligenz. Addison￾Wesley, 1986 5, 5.8

Burges, C. J.: A Tutorial on Support Vector Machines for Pattern Recognition.

Data Min. Knowl. Discov. 2 1998, Nr. 2, 121–167 9.6

Chang, C. L./Lee, R. C.: Symbolic Logic and Mechanical Theorem Proving.

Orlando, Florida: Academic Press, 1973 3.9

Clocksin, W. F./Mellish, C. S.: Programming in Prolog. 4th edition. Berlin,

Heidelberg, New York: Springer, 1994 5, 5.8

Dassow, J.: Logik fu¨r Informatiker. Teubner Verlag, 2005 3.9

Diaz, D.: GNU PROLOG. Universit¨at Paris, 2004, Aufl. 1.7, fu¨r GNU Prolog

version 1.2.18, http://gnu-prolog.inria.fr 5.1, 5.8

D.J. Newman, S. Hettich, C.L. Blake/Merz, C.J.: UCI Repository of ma￾chine learning databases. http://www.ics.uci.edu/\protect\unhbox\

voidb@x\penalty\@M\{}mlearn/MLRepository.html, 1998 8.8

Copyright © 2011, W. Ertel 6

Duda, R.O./Hart, P.E.: Pattern Classification and Scene Analysis. Wiley, 1973,

Klassiker zur Bayes-Decision-Theorie (document)

Duda, R.O./Hart, P.E./Stork, D.G.: Pattern Classification. Wiley, 2001,

Neuauflage des Klassikers Duda/Hart 7.6, 8.6, 15, 8.8

Eder, E.: Relative Complexities of First Order Calculi. Vieweg Verlag, 1991 3.3

Ertel, W./Schumann, J./Suttner, Ch.: Learning Heuristics for a Theorem

Prover using Back Propagation. In Retti, J./Leidlmair, K., editors: 5.

O¨sterreichische Artificial-Intelligence-Tagung. Berlin, Heidelberg: Informatik￾Fachberichte 208, Springer-Verlag, 1989, 87–95 4.1, 4, 8

Fischer, B./Schumann, J.: SETHEO Goes Software Engineering: Application

of ATP to Software Reuse. In Conference on Automated Deduction (CADE

97). Springer, 1997, http://ase.arc.nasa.gov/people/schumann/

publications/papers/cade97-reuse.html, 65–68 3.8

Freuder, E.: In Pursuit of the Holy Grail. Constraints, 2 1997, Nr. 1, 57–61 5.7

Copyright © 2009, W. Ertel 7

G¨orz, G./Rollinger, C.-R./Schneeberger, J., editors: Handbuch der Ku¨n￾stlichen Intelligenz. Oldenbourg Verlag, 2003 3.9

Jensen, F.V.: Bayesian networks and decision graphs. Springer-Verlag, 2001 7.5,

7.5, 7.6, 8.4, 9

Kaelbling, L.P./Littman, M.L./Moore, A.P.: Reinforcement Learn￾ing: A Survey. Journal of Artificial Intelligence Research, 4 1996,

237–285, www-2.cs.cmu.edu/afs/cs/project/jair/pub/volume4/

kaelbling96a.pdf 10.2

Kalman, J.A.: Automated Reasoning with OTTER. Rinton Press, 2001,

www-unix.mcs.anl.gov/AR/otter/index.html 3.6

Lauer, M./Riedmiller, M.: Generalisation in Reinforcement Learning

and the Use of Obse rvation-Based Learning. In Kokai, Gabriella/

Zeidler, Jens, editors: Proceedings of the FGML Workshop 2002.

2002, http://amy.informatik.uos.de/riedmiller/publications/

lauer.riedml.fgml02.ps.gz, 100–107 2

Copyright © 2011, W. Ertel 8

Letz, R. et al.: SETHEO: A High-Performance Theorem Prover. Journal of Auto￾mated Reasoning, 1992, Nr. 8, 183–212, www4.informatik.tu-muenchen.

de/\protect\unhbox\voidb@x\penalty\@M\{}letz/setheo 3.6

Melancon, G./Dutour, I./Bousque-Melou, G.: Random Generation of Dags

for Graph Drawing. Dutch Research Center for Mathematical and Computer

Science (CWI), 2000 (INS-R0005). – Technical report, http://ftp.cwi.nl/

CWIreports/INS/INS-R0005.pdf 10

Minsky, M./Papert, S.: Perceptrons. MIT Press, Cambridge, MA, 1969 3

Mitchell, T.: Machine Learning. McGraw Hill, 1997, www-2.cs.cmu.edu/

\protect\unhbox\voidb@x\penalty\@M\{}tom/mlbook.html 2, 8, 8.8,

10.2

Nipkow, T./Paulson, L.C./Wenzel, M.: Isabelle/HOL — A Proof Assistant

for Higher-Order Logic. Volume 2283, LNCS. Springer, 2002, www.cl.cam.

ac.uk/Research/HVG/Isabelle 3.6, 4.1

Palm, G.: On Associative Memory. Biological Cybernetics, 36 1980, 19–31 2

Copyright © 2009, W. Ertel 9

Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Networks of Plausible

Inference. Morgan Kaufmann, 1988 7.5, 7.6

Rich, E.: Artificial Intelligence. McGraw-Hill, 1983 1.1, 1

Ritter, H./Martinez, T./Schulten, K.: Neuronale Netze. Addison Wesley,

1991 9.8

Rojas, R.: Theorie der neuronalen Netze. Springer, 1993 9.8

Rumelhart, D./McClelland, J.: Parallel Distributed Processing. Volume 1,

MIT Press, 1986 (document), 3, 4, 5

Rumelhart, D.E./Hinton, G.E./R.J., Williams: Learning Internal Represen￾tations by Error Propagation. in Rumelhart/McClelland, 1986 3, 5

Schramm, M.: Indifferenz, Unabh¨angigkeit und maximale Entropie: Eine

wahrscheinlichkeitstheoretische Semantik fu¨r Nicht-Monotones Schließen.

Mu¨nchen: CS-Press, 1996, Dissertationen zur Informatik 4 5

Copyright © 2011, W. Ertel 10

Schulz, S.: E – A Brainiac Theorem Prover. Journal of AI Communications, 15

2002, Nr. 2/3, 111–126, www4.informatik.tu-muenchen.de/\protect\

unhbox\voidb@x\penalty\@M\{}schulz/WORK/eprover.html 3.6, 3.7

Schumann, J.: Automated Theorem Proving in Software Engineering. Springer

Verlag, 2001 3.8

Sch¨olkopf, S./Smola, A.: Learning with Kernels: Support Vector Machines,

Regularization, Optimization, and Beyond. MIT Press, 2002 9.6

Sejnowski, T.J./Rosenberg, C.R.: NETtalk: a parallel network that learns

to read aloud. The John Hopkins University Electrical Engineering and Com￾puter Science Technical Report, 1986 (JHU/EECS-86/01). – Technical report,

Wiederabdruck in Anderson/Rosenfeld S. 661-672 7

Siekmann, J./Benzmuller, Ch.: ¨ Omega: Computer Supported Mathemat￾ics. In KI 2004: Advances in Artificial Intelligence. Springer Verlag, 2004,

LNAI 3238, www.ags.uni-sb.de/\protect\unhbox\voidb@x\penalty\

@M\{}omega, 3–28 4.1

Copyright © 2009, W. Ertel 11

Stone, P./Sutton, R.S./Kuhlmann, G.: Reinforcement Learning for

RoboCup-Soccer Keepaway. Adaptive Behavior, 2005, To appear.,

www.cs.utexas.edu/\protect\unhbox\voidb@x\penalty\@M\

{}pstone/Papers/bib2html-links/AB05.pdf 3

Suttner, Ch./Ertel, W.: Automatic Acquisition of Search Guiding Heuristics. In

10th Int. Conf. on Automated Deduction. Springer-Verlag, LNAI 449, 1990,

470–484 4.1, 4, 9

Sutton, R./Barto, A.: Reinforcement Learning. MIT Press, 1998,

www.cs.ualberta.ca/\protect\unhbox\voidb@x\penalty\@M\

{}sutton/book/the-book.html 10.1, 1, 10.2

Turing, A.M.: Computing Machinery and Intelligence. Mind, 59 1950, 433–

460, Deutsche U¨bersetzung mit dem Titel Kann eine Maschine denken in

Zimmerli/Wolf 11

Whittaker, J.: Graphical models in applied multivariate statistics. Wiley, 1996 7.6

Copyright © 2011, W. Ertel 12

Wiedemann, U.: PhilLex, Lexikon der Philosophie. www.phillex.de/

paradoxa.htm 2

Wielemaker, J.: SWI-Prolog 5.4. Universit¨at Amsterdam, 2004, www.

swi-prolog.org 5.8

Witten, I./Frank, E.: Data Mining. Hanser Verlag Mu¨nchen, 2001, Von

den Autoren in Java entwickelte DataMining Programmbibliothek WEKA:

(www.cs.waikato.ac.nz/\protect\unhbox\voidb@x\penalty\@M\

{}ml/weka) 8, 16

Zdziarski, J.: Ending Spam. No Starch Press, 2005 12

Zell, A.: Simulation Neuronaler Netze. Addison Wesley, 1994, Im

Buch beschriebener Simulator SNNS, bzw. JNNS: www-ra.informatik.

uni-tuebingen.de/SNNS 6, 9.8

Zimmerli, W.C./Wolf, S., editors: Ku¨nstliche Intelligenz – Philosophische

Probleme. Stuttgart: Philipp Reclam, 1994 (document)

Chapter 1

Introduction

Copyright © 2011, W. Ertel 14

What is Artificial Intelligence (AI)

• What is intelligence?

• How can intelligence be measured?

• How does our brain work?

• Intelligent machine?

• Science fiction?

• Rebuild human mind?

• Philosophy, e.g. mind-body dualism?

Copyright © 2009, W. Ertel 15

John McCarthy (1955):

The aim of AI is to develop machines that behave as if they were intelligent.

Two simple Braitenberg-vehicles and their reaction to a light source.