Skip to main content
main-content

Über dieses Buch

In diesem Buch werden alle Teilgebiete der KI kompakt, leicht verständlich und anwendungsbezogen vorgestellt. Der Autor kennt das Gebiet nicht nur bestens aus Forschung und praktischer Anwendung, sondern engagiert sich auch erfolgreich in der Lehre. Die Themen reichen von der klassischen Logik über das Schließen mit Unsicherheit und maschinelles Lernen bis hin zu Anwendungen wie Diagnosesysteme, lernfähige Roboter oder Kreativität in der KI.

Sie profitieren von dem umfassenden Einblick in dieses faszinierende Teilgebiet der Informatik, wobei, abgesehen von grundlegenden Programmierkenntnissen sowie etwas Mathematik, alle Voraussetzungen für ein gutes Verständnis bereitgestellt werden. Sie gewinnen vertiefte Kenntnisse, z.B. hinsichtlich der wichtigsten Verfahren zur Repräsentation und Verarbeitung von Wissen und in dem immer wichtiger werdenden Gebiet des maschinellen Lernens. Vor allem der Anwendungsbezug steht im Fokus der Darstellung. Viele Übungsaufgaben mit Lösungen sowie eine strukturierte Liste mit Verweisen auf Literatur und Ressourcen im Web ermöglichen ein effektives und kurzweiliges Selbststudium.

Inhaltsverzeichnis

Frontmatter

1. Einführung

Zusammenfassung
Der Begriff Künstliche Intelligenz weckt Emotionen. Zum einen ist da die Faszination der Intelligenz, die offenbar uns Menschen eine besondere Stellung unter den Lebewesen verleiht. Es stellen sich Fragen wie „Was ist Intelligenz?“, „Wie kann man Intelligenz messen?“ oder „Wie funktioniert unser Gehirn?“. All diese Fragen sind von Bedeutung für das Verständnis von künstlicher Intelligenz. Die zentrale Frage für den Ingenieur, speziell für den Informatiker, ist jedoch die Frage nach der intelligenten Maschine, die sich verhält wie ein Mensch, die intelligentes Verhalten zeigt.
Das Attribut künstlich weckt eventuell ganz andere Assoziationen. Da kommen Ängste vor intelligenten Robotermenschen auf. Die KI mit ihren intelligenten Maschinen und Robotern verändert unter anderem die Arbeitswelt und das Verkehrswesen, was in dieser Einführung diskutiert wird.
Wolfgang Ertel

2. Aussagenlogik

Zusammenfassung
In der Aussagenlogik werden, wie der Name schon sagt, Aussagen über logische Operatoren verknüpft. Der Satz „die Straße ist nass“ ist eine Aussage, genauso wie „es regnet“. Diese beiden Aussagen lassen sich nun verknüpfen zu der neuen Aussage
$$\displaystyle\mathit{wenn}\;\mathit{es}\;\mathit{regnet}\;\mathit{ist}\;\mathit{die}\;\textit{Stra{\ss}e}\;\mathit{nass}.$$
Etwas formaler geschrieben ergibt sich
$$\displaystyle\mathit{es}\;\mathit{regnet}\,\Rightarrow\,\mathit{die}\;\textit{Stra{\ss}e}\;\mathit{ist}\;\mathit{nass}.$$
Diese Schreibweise hat unter anderem den Vorteil, dass die elementaren Aussagen in unveränderter Form wieder auftreten. Um im Folgenden ganz exakt mit der Aussagenlogik arbeiten zu können, starten wir mit einer Definition der Menge aller aussagenlogischen Formeln.
Wolfgang Ertel

3. Prädikatenlogik erster Stufe

Zusammenfassung
Viele praktisch relevante Problemstellungen lassen sich mit der Sprache der Aussagenlogik nicht oder nur sehr umständlich formulieren, wie man an folgenden Beispielen gut erkennt. Die Aussage
„Roboter 7 befindet sich an xy-Position (35, 79)“
kann zwar direkt als die aussagenlogische Variable
„Roboter_7_befindet_sich_an_xy-Position_(35,79)“
zum Schließen mit Aussagenlogik verwendet werden, aber das Schließen mit derartigen Aussagen wird sehr umständlich. Angenommen 100 dieser Roboter können sich auf einem Gitter mit \(100\times 100\) Punkten aufhalten. Um alle Positionen aller Roboter zu beschreiben, würde man \(100\cdot 100\cdot 100=1.000.000=10^{6}\) verschiedene Variablen benötigen. Erst recht schwierig wird die Definition von Relationen zwischen verschiedenen Objekten (hier Robotern). Die Relation
„Roboter A steht weiter rechts als Roboter B .“
ist semantisch letztlich nichts anderes als eine Menge von Paaren. Von den 10.000 möglichen Paaren aus x-Koordinaten sind \((100\cdot 99)/2=4950\) geordnet. Zusammen mit allen 10.000 Kombinationen möglicher y-Werte beider Roboter ergeben sich zur Definition dieser Relation \(100\cdot 99=9900\) Formeln der Art
Roboter_7_steht_weiter_rechts_als_Roboter_12 \(\,\Leftrightarrow\,\)
Roboter_7_befindet_sich_an_xy_Position_(35,79)
\(\,\wedge\,\) Roboter_12_befindet_sich_an_xy_Position_(10,93) \(\,\vee\,\) \(\ldots\)
mit je \((10^{4})^{2}\cdot 0{,}495=0{,}495\cdot 10^{8}\) Alternativen auf der rechten Seite. In der Prädikatenlogik erster Stufe definiert man hierfür ein Prädikat Position(nummer, xPosition, yPosition). Die obige Relation muss nun nicht mehr als riesige Menge von Paaren aufgezählt werden, sondern wird abstrakt beschrieben durch eine Regel der Formwobei als „für alle “ und als „es gibt “ gelesen wird.
Wolfgang Ertel

4. Grenzen der Logik

Zusammenfassung
Wie schon an verschiedenen Stellen erwähnt, gibt es auf der Suche nach einem Beweis fast immer in jedem Schritt viele (je nach Kalkül eventuell sogar unendlich viele) Möglichkeiten für die Anwendung von Inferenzregeln. Es ergibt sich dadurch das schon erwähnte explosionsartige Wachsen des Suchraums (Abb. 4.1). In Worst-Case müssen zum Finden eines Beweises alle diese Möglichkeiten versucht werden, was in für Menschen zumutbaren Zeiträumen aber meist nicht möglich ist.
Vergleicht man nun automatische Beweiser oder Inferenzsysteme mit Mathematikern oder menschlichen Experten, die Erfahrung im Schließen in speziellen Domänen haben, so macht man interessante Beobachtungen. Zum einen können erfahrene Mathematiker Sätze beweisen, die für alle automatischen Beweiser weit außerhalb deren Reichweite liegen. Andererseits jedoch schaffen automatische Beweise zigtausende Inferenzen pro Sekunde. Ein Mensch hingegen schafft vielleicht eine Inferenz pro Sekunde. Obwohl menschliche Experten also auf der Objektebene (d.h. dem Ausführen der Inferenzen) viel langsamer sind, lösen sie die schwierigen Probleme offenbar viel schneller.
Wolfgang Ertel

5. Logikprogrammierung mit Prolog

Zusammenfassung
Im Vergleich zu klassischen Programmiersprachen wie zum Beispiel C oder Pascal bietet die Logik die Möglichkeit, Zusammenhänge elegant, kompakt und deklarativ zu beschreiben. Automatische Theorembeweiser sind sogar in der Lage, zu entscheiden, ob eine Anfrage logisch aus einer Wissensbasis folgt. Hierbei sind der Beweiskalkül und das in der Wissensbasis gespeicherte Wissen streng getrennt. Eine in Klauselnormalform aufgeschriebene Formel kann als Eingabe für jeden Theorembeweiser verwendet werden, unabhängig vom verwendeten Beweiskalkül. Für die Repräsentation von Wissen und das Schließen ist dies von großem Nutzen.
Will man jedoch Algorithmen implementieren, die zwangsläufig (auch) prozedurale Komponenten haben, so genügt die rein deklarative Beschreibung oft nicht. Robert Kowalski, einer der Pioniere in der Logikprogrammierung, hat dies mit der Formel
$$\displaystyle\textbf{Algorithm}\boldsymbol{=}\textbf{Logic}\boldsymbol{+}\textbf{Control}$$
auf den Punkt gebracht. Mit der Sprache Prolog hat sich diese Idee durchgesetzt. Vor allem in der KI und in der Computerlinguistik wird Prolog in vielen Projekten eingesetzt. Wir geben hier eine kurze Einführung in diese Sprache, stellen die wichtigsten Konzepte vor, zeigen die Stärken auf und vergleichen sie mit anderen Programmiersprachen und mit Theorembeweisern. Wer einen kompletten Programmierkurs sucht, wird verwiesen auf Lehrbücher wie Bra86, CM94 und die Handbücher Dia04, Wie04.
Die Syntax der Sprache Prolog kennt nur Hornklauseln. In folgender Tabelle sind die logische Schreibweise und die Prologsyntax nebeneinander gestellt.
Wolfgang Ertel

6. Suchen, Spielen und Probleme lösen

Zusammenfassung
Bei fast allen Inferenzsystemen stellt die Suche nach einer Lösung, bedingt durch die extrem großen Suchbäume, ein Problem dar. Aus dem Startzustand gibt es für den ersten Inferenzschritt viele Möglichkeiten. Für jede dieser Möglichkeiten gibt es im nächsten Schritt wieder viele Möglichkeiten und so weiter. Schon beim Beweis einer ganz einfachen Formel aus Ert93 mit drei Hornklauseln mit maximal drei Literalen hat der Suchbaum für SLD-Resolution folgende Gestalt:
Der Baum wurde bei einer Tiefe von 14 abgeschnitten und besitzt in dem mit * markierten Blattknoten eine Lösung. Nur durch den kleinen Verzweigungsfaktor von maximal zwei und das Abschneiden des Suchbaumes auf Tiefe 14 ist er überhaupt darstellbar. Bei realistischen Problemen können Verzweigungsfaktor und Tiefe der ersten Lösung deutlich größer werden.
Wolfgang Ertel

7. Schließen mit Unsicherheit

Zusammenfassung
Dass eine zweiwertige Logik beim Schließen im Alltag zu Problemen führt, haben wir in Kap. 4 an Hand des Tweety-Problems aufgezeigt. In diesem Beispiel führen die Aussagen Tweety ist ein Pinguin, Alle Vögel können fliegen und Pinguine sind Vögel zu der Folgerung Tweety kann fliegen. Interessant wäre zum Beispiel eine Sprache, in der es möglich ist, die Aussage Fast alle Vögel können fliegen zu formalisieren und darauf dann Inferenzen durchzuführen. Die Wahrscheinlichkeitsrechnung stellt hierfür eine bewährte Methode bereit, denn durch die Angabe eines Wahrscheinlichkeitswertes lässt sich die Unsicherheit über das Fliegen von Vögeln gut modellieren. Wir werden zeigen, dass etwa eine Aussage wie 99 % aller Vögel können fliegen zusammen mit Wahrscheinlichkeitslogik zu korrekten Schlüssen führt.
Wolfgang Ertel

8. Maschinelles Lernen und Data Mining

Zusammenfassung
Definiert man den Begriff der KI wie im Buch von Elaine Rich Ric83
Artificial Intelligence is the study of how to make computers do things at which, at the moment, people are better.
und bedenkt, dass die Computer uns Menschen insbesondere bezüglich der Lernfähigkeit weit unterlegen sind, dann folgt daraus, dass die Erforschung der Mechanismen des Lernens und die Entwicklung maschineller Lernverfahren eines der wichtigsten Teilgebiete der KI darstellt.
Die Forderung nach maschinellen Lernverfahren ergibt sich aber auch aus dem Blickwinkel des Software-Entwicklers, der zum Beispiel das Verhalten eines autonomen Roboters programmieren soll. Die Struktur des intelligenten Verhaltens kann hierbei so komplex werden, dass es auch mit modernen Hochsprachen wie Prolog oder Python sehr schwierig oder sogar unmöglich wird, dieses annähernd optimal zu programmieren. Ähnlich wie wir Menschen lernen, werden auch heute schon bei der Programmierung von Robotern maschinelle Lernverfahren eingesetzt (siehe Kap. 10 bzw. RGH + 06), oft auch in einer hybriden Mischung aus programmiertem und gelerntem Verhalten.
Wolfgang Ertel

9. Neuronale Netze

Zusammenfassung
Neuronale Netze sind Netzwerke aus Nervenzellen im Gehirn von Menschen und Tieren. Etwa 10 bis 100 Milliarden Nervenzellen besitzt das menschliche Gehirn. Der komplexen Verschaltung und der Adaptivität verdanken wir Menschen unsere Intelligenz und unsere Fähigkeit, verschiedenste motorische und intellektuelle Fähigkeiten zu lernen und uns an variable Umweltbedingungen anzupassen. Schon seit vielen Jahrhunderten versuchen Biologen, Psychologen und Mediziner die Funktionsweise von Gehirnen zu verstehen. Um das Jahr 1900 wuchs die revolutionäre Erkenntnis, dass eben diese winzigen physikalischen Bausteine des Gehirns, die Nervenzellen und deren komplexe Verschaltung, für Wahrnehmung, Assoziationen, Gedanken, Bewusstsein und die Lernfähigkeit verantwortlich sind.
Den großen Schritt hin zu einer KI der neuronalen Netze wagten dann 1943 McCulloch und Pitts in einem Artikel mit dem Titel „A logical calculus of the ideas immanent in nervous activity“ AR88. Sie waren die ersten, die ein mathematisches Modell des Neurons als grundlegendes Schaltelement für Gehirne vorstellten. Dieser Artikel legte die Basis für den Bau von künstlichen neuronalen Netzen und damit für dieses ganz wichtige Teilgebiet der KI.
Wolfgang Ertel

10. Lernen durch Verstärkung (Reinforcement Learning)

Zusammenfassung
Alle bisher beschriebenen Lernverfahren arbeiten mit Lehrer. Sie gehören also zur Klasse des Supervised Learning. Beim Lernen mit Lehrer soll der Agent anhand von Trainingsdaten eine Abbildung der Eingabevariablen auf die Ausgabevariablen lernen. Wichtig ist hierbei, dass für jedes einzelne Trainingsbeispiel sowohl alle Werte der Eingabevariablen als auch alle Werte der Ausgabevariablen vorgegeben sind. Man braucht eben einen Lehrer, beziehungsweise eine Datenbank, in der die zu lernende Abbildung für genügend viele Eingabewerte näherungsweise definiert ist. Einzige Aufgabe des maschinellen Lernverfahrens ist es, das Rauschen aus den Daten herauszufiltern und eine Funktion zu finden, die auch zwischen den gegebenen Datenpunkten die gesuchte Abbildung gut approximiert.
Beim Lernen durch Verstärkung (engl. reinforcement learning) ist die Situation eine andere, ungleich schwierigere, denn hier sind keine Trainingsdaten verfügbar. Wir starten mit einem ganz einfachen anschaulichen Beispiel aus der Robotik, das dann zur Illustration der verschiedenen Verfahren dient.
Wolfgang Ertel

11. Lösungen zu den Übungen

Zusammenfassung
Aufgabe 1.3
Eine Maschine kann sehr wohl intelligent sein, auch wenn ihr Verhalten sich stark von dem eines Menschen unterscheidet.
Wolfgang Ertel

Backmatter

Weitere Informationen