Künstliche Intelligenz

Zusammenfassung KI (von Marco Piroth)
Definition:
KI ist das Teilgebiet der Informatik, das sich damit beschäftigt, menschliche, intelligente
Verhaltensweisen auf einer Maschine nachzuvollziehen.
Softwaretechnische Methoden: z.B.: OO, Studium von Prototypen, kontinuierliche
Weiterentwicklung (exploratives Programmieren)
Anwendungsgebiete der KI:
Schlussfolgerung
Deduktive Systeme
Sehen
Bildverstehende Systeme
Hören
Spracherkennung
Lesen
Sprachverarbeitung
Bewegen
Robotik
Lehren
Tutorielle Systeme
Sprechen
Sprachgenerierung
Merken
Wissensrepräsentation
Lernen
Wissensakquisition
KI-Methoden:
 Überführung von Eingabedaten in die interne Wissensrepräsentation
 Repräsentation von Wissen
 Such- und Inferenzprozesse über Wissensstrukturen
 Organisationsstrukturen für kognitive Systeme
Turing-Test:
Experte führt abwechselnd Dialog mit einem Menschen und einem KI-System, ohne zu
wissen, welche Leitung wer ist.
Gelingt es dem Experten nicht, das KI-System gegenüber dem Menschen eindeutig zu
identifizieren, hat das KI-System den Turing-Test bestanden.
Chinesisches Zimmer:
Kann man ein System bauen, das nur durch formale Interpretation, ohne ein wirkliches tiefes
Verständnis der realen Welt menschliches intelligentes Verhalten realisiert?
 Nein, da man nicht in unendlich viele Meta-Ebenen gehen kann.
Das MIN-MAX-Verfahren:
Beteiligt: 2 nichtkooperative Aktoren  Suchgraph meist extrem groß (Schach: 35100)
 heuristische Suche nach vollständigem Lösungsweg aussichtslos.
 daher: Bewertung des nächsten Handlungsschrittes (Vorausschau & einige Züge bewerten)
Annahmen bei Min-Max:
der jeweilige Gegenspieler entscheidet sich immer für seinen besten Zug (nach MM)
Nachteile:
- Zahl als Positionsbewertung ist wenig aussagekräftig (wie ist sie entstanden?)
- Hoher Aufwand: alle möglichen Nachfolger erzeugen und Pfade berechnen
Modelle und Verfahren:
Suche in Bäumen: große Komplexität durch kombinatorische Explosion.
TI: Bäume mit exponentieller Komplexität mit polynomiellem Aufwand berechnen.
KI: Verzicht auf die beste Lösung, Faustregeln (Heuristiken)  s. Handelsreisender
allgemein (schwach)
problemspezifisch (stark)
z.B. Bestensuche, Tiefensuche mit Backtracking, Breitensuche, Bergsteigen
konventionelle Informatik: Algorithmus   KI: deklarative Sicht des Problems
konventionelle Problemlösung:
Daten
- Problemanalyse
- Problem beschreiben
- Problem lösen (Algorithm)
- Lösungsweg kodieren
Rechner
Ergebniss
 Programm
Wissensbasierte Problemlösung:
Fakten
- Problem analysieren
- Problem darstellen
- Wissen sammeln
- Wissen darstellen
Schlußfolgerungsmaschine
Problemlösung
Formale Problembeschreibung:
1. Definition eines Zustandsraumes, der alle möglichen Konfigurationen der relevanten
Objekte enthält
2. Festlegung von Anfangszuständen
3. Festlegung von Endzuständen
4. Angabe einer Menge von Regeln, die die verfügbaren Tätigkeiten (Operatoren)
beschreiben. Die Regeln sollen einen Zustand des Raums in einen anderen überführen
Formale Unterschiede:
Datenverarbeitung
Ausgangspunkt: Verarbeitung von Zahlen
Wenige Datentypen, viele Instanzen
Strukturiertes Programmieren
Verarbeitungsablauf ist explizit festgelegt
Nur vollständige Programme können
abgearbeitet werden
C, Pascal...
normale PC’s
Wissensverarbeitung
Ausgangspunkt: Verarbeitung symbolischer
Ausdrücke
Viele Strukturtypen, wenige Instanzen
Exploratives Programmieren
Verarbeitungsablauf durch Anwendung von
Regeln implizit oder gar nicht vorgegeben
Verarbeitung unvollständiger Strukturen ist
möglich
Lisp, Prolog, Smalltalk
hochauflösende BS, Fenster, Maus
Inhaltliche Unterschiede:
Datenverarbeitung
KI
monotone, strukturierte, definierte Prozesse
komplexe Prozesse, diffuses Wissen
Systementwickler schreibt mit Wissen Prog. Wissen transferieren in KI-System
nur Programmierer kann den Prozess erklären KI-System kann Prozess erklären
Verarbeitung homogen strukturierter Massendaten
bei formaler Spezifikation Korrektheitsbew. Heuristiken, diffuses Wissen kein KorBew.
Komplexität: Umfang der Datenmenge
Reichhaltigkeit der Wissens-Strukturen
Probleme bei Suchverfahren:
 Suchrichtung: vorwärts   rückwärts (Verzweigungsfaktor beachten!)
 Topologie des Baumes: Graph, Wiederholungen vermeiden
 Wissensdarstellung in Knoten: Fortschreibung des Wissen von Knoten zu Knoten
 Auswahl der Regel: Konfliktmenge (anwendbare Regeln) wegen Komplexität nicht
immer bestimmbar
 Heuristiken: stark   schwach
Allgemeinheuristiken:
1. Tiefensuche
2. Tiefensuche mit Backtracking
3. Breitensuche
in KI unmöglich, da Graphen zu groß sind
4. Bidirektionale Suche  Start- und Zielzustand gleichzeitig (Probleme reduzieren)
5. Erzeugen und Prüfen  Weg erzeugen -> Zielzustand? -> bis Lösung gefunden (Lotto)
6. Problemreduzierung: UND-ODER-Graph
7. Beschränktheitserfüllung  Lösung = Menge von Einschränkungen
8. Auffinden von stabilen Zuständen (ich fahr nach Frankfurt, dann seh’ ich weiter)
9. Blinde Suche  in jedem Zustand: wähle erfolgsversprechensten Weg  Bergsteigen
10. Bestensuche
Strategien der Abbildung der realen Welt in einem Computer:
 closed world assumption (Annahme einer geschlossenen Welt)
 was sich nicht beweisen lässt, ist falsch
 default reasoning (Schließen mangels besseren Wissens)
 wenn PC was nicht weiß, schließt er aus anderen Wissenseinheiten (Pinguin)
 Abhilfe: nicht-monotone Logik
 common sense reasoning (gesunder Menschenverstand, Alltagswissen)
 zusätzliche Infos aus Mitteilungen herleiten
Formen menschlichen Wissens:
statisches Wissen
dynamisches, aktives Wissen
oberflächliches, diffuses Wissen
Spezialwissen
heuristisches Wissen: hierarchische Struktur
prozedurales Wissen: Rezept
deklaratives Wissen: Daten ( = 3,14)
Wissensrepräsentationsformalismen:
1. Natürliche Sprache  große Ausdruckskraft, Redundant, Kontext/ Hintergrundwissen
2. Logik  Terme und Formeln, Rückwärtsverkettung *1
3. Produktionsregeln  mit Vorbedingungen versehene Aktionen, Vorwärtsverkettung
4. semantische Netze  Konzepte (Knoten) die in Beziehung stehen (Kanten)  ISA,
HASA, CD-Graphen
5. Frames
6. analoge Repräsentation  nicht-symbolische Darstellung, keine formale
Interpretierbarkeit
7. Skripts (Drehbücher)  komplexe Aktionen, Sequenz von Ereignissen mit
Zusammenhang
*1:
Resolutionsverfahren:
gegeben: Menge von Aussagen, logisch verknüpft
Ziel: Bewies einer neuen Aussage / Behauptung
1. Überführen in kognitive Normalform
2. Negiere Behauptung
3. Schleife: Beginne mit der negierten Behauptung, kombiniere mit anderen Aussagen
 Resolvente  bis leere Resolvente
KI-Programmiersprachen:
einfache Syntax
Symbole, nicht Zahlen stehen im Vordergrund
keine Datentypen
keine Unterscheidung zwischen Daten und Anweisungen
LISP (List Processing):
Es gibt Atome (Wörter) und Listen, Listen können ausgewertet und so als Funktionsaufrufe
interpretiert werden.
Prolog (Programing with Logic):
Der Benutzer gibt nur Fakten und Regeln ein, der Rechner leitet neues Wissen daraus ab und
versucht eine Problemlösung mithilfe dieses Wissens zu finden.
Smalltalk (objektorientiert):
Programmierung mit Klassen und Objekten.
Senden von Nachrichten über Methoden-Aufrufe.
Anwendungsgebiete der KI-Programmierung:
 Expertensysteme
Büro
 Natürlichsprachliche Systeme
 Bilderkennung
Industrielle Fertigung
 Robotik
Anforderungen an Expertensysteme:
Erkennen fachspezifischer Aufgabenstellungen und Formulierung in Fachsprache
Korrekte und vollständige Problemlösung
Verständliche Formulierung für den Kunden
Erklärung des Losungsweges
Hilfe bei der Anwendung der Lösung
Aufgabengebiete:
Interpretation, Diagnose, Planen, Konstruktion, Beweisen, Tutoring
Architektur eines Expertensystems:
Benutzer
Dialogkomponente
Erklärungskomponente
Problemlösungskomponente
Dialogwissen
Wissensbasis
Problemlösungsmethoden:
 Klassifikation (Diagnose)
 Konstruktion (Beschränktheitserfüllung)
 Simulation
Wissensakquisitionskomponente

Download Report