Künstliche Intelligenz
Prof. Dr. Jürgen Cleve
Hochschule Wismar
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
Infos
Lehrveranstaltungen 2 SWS V + 2 SWS Ü
Prüfung
Klausur 120 min
Folien, Übungen etc. in Stud.IP
Literatur
PROLOG
Modul KI
Lämmel/Cleve,
LÜB
KI,
Hanser
2012,
Kapitel
2-5.
[Uwe Lämmel, Jürgen Cleve 2012]
http://www.wi.hs-wismar.de/kibuch
Forbrig/Kerner: Programmierung – Paradigmen und
Konzepte, Fachbuchverlag Leipzig 2005, Kapitel Logik
www.wi.hs-wismar.de/~cleve/prolog/fachbuchKap4.html
in ILIAS, viele Zusatzinfos (Videos, Tests)
WWW-Seiten zu KI www.wi.hs-wismar.de/~cleve/vorl/ki15/infos.html
Einordnung in das Studium
1 Einleitung
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
1 Einleitung
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 1
Einleitung
Einführung
Intelligenz und KI
KI und Informatik
Architekturen
State of the art
Zusammenfassung (Einleitung)
Aufgaben
1 Einleitung
Künstliche Intelligenz
Folie 1-1 (7)
Einleitung
Machines should work; people should think
IBM Pollyanna Principle
Arthur Bloch, Murphy’s Law, 1981
1 Einleitung
Künstliche Intelligenz
1.1 Einführung
Geschichte
I
Künstliche Menschen in der Literatur schon im Mittelalter.
I
Leibniz: Universal-Maschine, die alles ausrechnen kann (also
auch logische Schlüsse)
I
1956 Konferenz in Dartmouth, Begriff „artificial intelligence“
geboren.
Folie 1-2 (8)
1 Einleitung
Künstliche Intelligenz
1.1 Einführung
Folie 1-3 (9)
KI - Warum ?
Computer-Historie:
I
Maschinen, die rechnen können.
I
Maschinen (Programme), die Textverarbeitung beherrschen.
I
Programme, die mit grafischen Darstellungen umgehen können.
I
Nun bringen wir den Computern das Denken bei.
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-4 (10)
Menschliche Intelligenz
Intuition
Handlungsweise eines Börsenmaklers
Allgemeinwissen Beantwortung von Fragen z.B. in Trivial Pursuit
Urteilsvermögen Was ist eine gute/schlechte Lösung?
Kreativität
Innovationsfähigkeit bei der Problemlösung
Plausibles Schließen „Wenn es regnet, nehme ich einen Schirm mit.“
Abstraktionsvermögen Begriffe wie Straßenverkehr, Emotionen . . .
Problemlösungsgeschwindigkeit
KI versucht, dies nachzuahmen.
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-5 (11)
Intelligenz und KI
Wesentliche Kriterien für Intelligenz:
I
Lernfähigkeit
I
Logisches Denkvermögen
I
Abstraktionsvermögen
etc.
Wichtige Beobachtung: Begriff Intelligenz ist dynamisch
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-6 (12)
Intelligenz
Viele Facetten:
I
allgemeine Alltagsintelligenz (Sehen, Hören, . . . )
I
Expertenintelligenz (bestimmte Fachgebiete beherrschen)
I
emotionale Intelligenz
I
soziale Intelligenz
...
Wir konzentrieren uns auf die Expertenintelligenz.
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-7 (13)
Künstliche Intelligenz
Wie kann man KI definieren? 4 Ansätze:
1. Denken wie ein Mensch
2. Handeln wie ein Mensch
3. Vernünftig denken
4. Vernünftig handeln
2 Sichtweisen:
I
Natur nachahmen
I
Rein funktionale Sicht
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-8 (14)
1.2.1 Kontroverse Diskussionen
Kontroverse Diskussionen
Gründe für kontroverse Diskussionen um KI:
I
unglückliche 1-1-Übersetzung des Begriffs Artificial Intelligence
I
überzogene Erwartungen/Versprechungen
I
konservative Standpunkte (Intelligenz als etwas Unscharfes, nur
dem Menschen Gegebenes)
I
emotionale statt sachliche Diskussion
Bessere Begriffe: synthetische Intelligenz oder computational
intelligence.
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
Folie 1-9 (15)
1.2.2 Fazit
Fazit
Ziel der KI: Befähigung der Computer zu Assistenzleistungen für
den Menschen, deren Erbringung durch den Menschen Intelligenz
erfordern würde.
Unwesentlich, ob die gleiche Technik angewandt wird:
I
Flugzeuge und Vögel können fliegen . . .
I
. . . allerdings mit unterschiedlichen Methoden
1 Einleitung
Künstliche Intelligenz
1.2 Intelligenz und KI
1.2.2 Fazit
Andere Intelligenz-Bestimmung
I
Entscheidung, ob intelligent oder nicht, rein subjektiv
I
Beurteilung nur nach der erbrachten Leistung oder Reaktion
I
Turing-Test
I
Test wurde erstmals 2014 von dem russischen Programm
„Eugene Goostmann“ bestanden.
Im folgenden verwenden wir KI als terminus technicus.
Folie 1-10 (16)
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-11 (17)
Typische KI-Probleme
Frühe Arbeiten :
Spielen
(Schach, Dame etc.)
Beweisen
mathematischer Sätze
Typische, aktuelle KI-Anwendungsfelder:
I
Sprachverarbeitung, Bildverarbeitung
I
Robotik
I
Experten-Systeme (Diagnose, Planen, Konfigurieren)
I
Intelligente (Software-)Agenten
I
Data Mining, Wissensmanagement
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-12 (18)
KI und konventionelle Datenverarbeitung
I
KI verarbeitet Wissen.
I
Begriffe:
I
I
I
Daten: Zahlen, Zeichenketten, . . .
Information: Daten, deren Bedeutung wir kennen
Wissen: Information, mit der man arbeiten kann
(Zusammenhänge, Abhängigkeiten, logische Regeln . . . )
I
Wissen wird explizit repräsentiert und verarbeitet.
I
In herkömmlicher DV: Wissen meist direkt im Algorithmus
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-13 (19)
KI-Schwerpunkte
I
Wissensdarstellung (-repräsentation) und
Wissensverarbeitung
I
Mechanisierung des Schließens (z.B. mathematisches
Beweisen: Deduktion/Induktion etc.)
I
Wissensakquisition, Maschinelles Lernen, Data Mining
I
Problemlösungsverfahren, Suchverfahren
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Quellen der KI (u.a.)
I
Psychologie
I
Neurobiologie
I
Informatik
I
Mathematik (z.B. Logik)
Folie 1-14 (20)
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-15 (21)
Bezüge zur klassischen Informatik
I
Programmiersprachen
I
Modellierung
I
Systementwurf
I
Softwaretechnik
I
...
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-16 (22)
Konsequenzen
I
KI und Informatik sehr stark verbunden
I
Verständnis intelligenten Verhaltens erforderlich, allerdings kein
umfassendes Verständnis menschlicher Intelligenz
I
KI: Beitrag zum Verständnis menschlicher Intelligenz
I
KI-Systeme: Computer-Programme mit einer bestimmten
(eingeschränkten) Assistenzfunktion, folglich auch mit
Kompetenzgrenzen.
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-17 (23)
Beobachtung
KI-Techniken in vielen (Informatik)-Produkten/-Systemen:
I
Vererbungstechniken
I
automatische Beweiser
I
Regelsysteme (Aktionsregeln)
I
Bild- und Spracherkenner
I
...
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-18 (24)
Aufbau der Vorlesung
I
Generelle Architektur von KI-Systemen
I
KI-Techniken
I
I
I
I
I
I
Wissensrepräsentation und -verarbeitung
Vages Wissen
Programmiersprache Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme und KI-Anwendungsfelder
1 Einleitung
1.3 KI und Informatik
Künstliche Intelligenz
Folie 1-19 (25)
Ein Beispiel . . .
Beispiel 1.1 (Prolog)
Schulze, Meier und Lehmann wohnen in unserer Straße. Einer ist
Maler, ein anderer Klempner, der dritte Tischler.
Unlängst wollte der Maler seinen Freund, den Tischler, um die
Anfertigung eines Tisches bitten. Man sagte ihm, dass der Tischler
gerade im Haus des Klempners arbeitet. Außerdem ist bekannt, dass
Meier noch nie von Lehmann gehört hat.
Wer übt welchen Beruf aus?
1 Einleitung
1.3 KI und Informatik
Künstliche Intelligenz
Folie 1-20 (26)
Ein Beispiel . . .
% Zu einer Person gehören Name und Beruf.
person(Beruf, Name) :- beruf(Beruf),name(Name).
name(schulze). name(meier). name(lehmann).
beruf(maler). beruf(klempner). beruf(tischler).
% Einige kennen sich:
kennt(maler,X,tischler,Y).
kennt(tischler,X,maler,Y).
kennt(klempner,X,tischler,Y). kennt(tischler,X,klempner,Y).
kennt(maler,X,klempner,Y).
loesung(Schulze,Meier,Lehmann) :person(Schulze,schulze),
% Schulze/Meier haben unterschiedliche Berufe
person(Meier,meier), Meier \= Schulze,
person(Lehmann,lehmann),Lehmann\=Schulze,Lehmann\=Meier,
% Meier kennt Lehmann nicht.
not(kennt(Meier,meier,Lehmann,lehmann)).
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-21 (27)
Wissensverarbeitung
Wissen
Computer
Logisches Denken
Wissensverknüpfung
Lösung
Abb. 1: Wissensverarbeitung
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-22 (28)
Problemlösen mittels Regelverarbeitung
Container−Umschlag
C1
C2
C3
Lager
L1
L2
LKW
??
L1
C2
L2
Waggon
Wenn C auf Lager und C ist oben
Dann setze C auf LKW
Wenn C auf LKW und C ist oben
Dann setze C auf Waggon
...
Abb. 2: Problemlösung durch Regelverarbeitung
1 Einleitung
Künstliche Intelligenz
1.3 KI und Informatik
Folie 1-23 (29)
Neuronale Netze
Abb. 3: Wissensverarbeitung mit Neuronalen Netzen
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Architekturen
Ausgangspunkt: Das angestrebte Verhalten von Computern als
(scheinbar) intelligente Assistenten.
Folie 1-24 (30)
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-25 (31)
1.4.1 KI – Historie
Historie
Die ersten „Computer“ der Welt:
I
Wilhelm Schickard (1623)
I
Blaise Pascal (1642)
I
Gottfried Wilhelm Leibniz (1671 - ca. 1693)
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
1.4.1 KI – Historie
Leibnizsches Programm
I
lingua characteristica
I
calculus ratiocinator
. . . mit den Worten der KI aus heutiger Sicht:
I
eine formale Sprache zur Wissensrepräsentation
I
ein Inferenzmechanismus (Wissensverarbeitung) zum
automatischen Schließen
Folie 1-26 (32)
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-27 (33)
1.4.1 KI – Historie
Geschichte der KI – 1
Erste Schritte 1945-1965
Darthmouth-Konferenz 1956: Artificial
Intelligence aus der Wiege (Minsky, McCarthy,
Newell, Simon u.a.) gehoben.
I Kennzeichnend: Suche nach universellen
Lösungsmustern und deren Anwendung auf
einfache Probleme (z.B. die Klötzchenwelt).
I
Ernüchterung 1965-1975
Universelles Vorgehen ist zu komplex.
I Also Spezialisierung, thematisch und technisch.
I Themen: universelle Methoden für die
Wissensrepräsentation und -verfahren sowie
Suchtechniken.
I
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-28 (34)
1.4.1 KI – Historie
Geschichte der KI – 2
Periode 1975-1990
I
I
I
I
I
Erfahrungen der Jahre zuvor:
problemspezifisches Vorgehen erforderlich.
Leistungskraft einer Problemlösung hängt eher
vom Problemwissen als von den allgemeinen
Problemlösungstechniken ab.
Erste ernstzunehmende Anwendungen wie
Expertensysteme.
Neue Themen: z.B. Fuzzy-Ansätze und Techniken
zur Wissensakquisition.
Ebenso: Orientierung an naturanalogen
Verfahren wie Neuronalen Netzen, Genetischen
Algorithmen, Simulated Annealing etc.
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-29 (35)
1.4.1 KI – Historie
Geschichte der KI – 3
Periode seit 1990
Paradigmenwechsel zu den Intelligenten
Agenten.
I Anwendungsspezifische Spezialisierung geht
weiter.
I Bestimmte KI-Techniken werden neu „erfunden“,
wie die Business Rules (Production Rules) und die
Topic Maps (Semantische Netze).
I KI hält stärker Einzug in betriebswirtschaftliche
Anwendungen.
I
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-30 (36)
1.4.2 Architekturprinzipien
Architekturprinzipien
KI-Systeme: explizite Repräsentation von Wissen.
I
Wissensbasis
I
Inferenzmaschine
Aus Anwendersicht:
I
Benutzerschnittstelle (User Interface)
I
I
Erklärungskomponente
Wissenserwerbskomponente
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-31 (37)
1.4.2 Architekturprinzipien
Architekturprinzipien
Wissensakquisition
User Interface
Erklärungskomponente
Inferenzmaschine
Wissensbasis
Abb. 4: Architektur von KI-Systemen
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-32 (38)
1.4.2 Architekturprinzipien
Architekturprinzipien
In realen KI-Systemen:
I
heterogene und strukturierte Wissensbasis
I
I
I
I
unterschiedliche Wissensarten in unterschiedlichen
Repräsentationen
hierarchische Strukturen
verteilte Wissensbasen (Regeln, Datenbanken etc.)
verschiedene Inferenzmechanismen
1 Einleitung
Künstliche Intelligenz
1.4 Architekturen
Folie 1-33 (39)
1.4.3 Intelligente Agenten
Intelligente Agenten
Wissen H
H
H
j
H
X
XX
Erfahrungen
z
X
:
Ziele *
Beobachtungen
Agent
- Aktionen
Abb. 5: Intelligente Agenten
1 Einleitung
Künstliche Intelligenz
1.5 State of the art
Folie 1-34 (40)
Wie weit ist KI heute?
Wissensbasierte Systeme Diagnose- und Beratungssysteme
Robotik
STANLEY ist ein fahrerloser VW Touareg, der durch die
Mojave-Wüste eine 132-Meilen-Strecke mit einer
Geschwindigkeit von 22 mph schaffte (2006).
Spracherkennung Viele Dialogsysteme verwenden Spracherkennung.
Autonome Planungsagenten Die NASA nutzt intelligente Agenten zur
Steuerung der Raummissionen zu entfernteren
Planeten (MAPGEN 2004, MEXAR2 2007).
Spielstrategien DEEP BLUE schlug als erster Computer einen
Schach-Weltmeister (Kasparow, 1997).
Spamfilter
Lernfähige Spamfilter benutzen KI-Techniken.
Planung in der Logistik 1991 nutzten die USA während der Golf-Krise
das Tool DART (Dynamic Analysis and Replanning Tool)
für eine automatische Planung der Logistik.
1 Einleitung
Künstliche Intelligenz
1.6 Zusammenfassung (Einleitung)
Folie 1-35 (41)
Das sollten Sie wissen . . .
Zusammenfassung 1.1 (Einleitung)
I
Künstliche und natürliche Intelligenz
I
Leibnizsches Programm
I
Historie
I
Architektur von KI-Systemen
1 Einleitung
1.7 Aufgaben
Künstliche Intelligenz
Folie 1-36 (42)
Aufgaben Einleitung
Aufgabe 1.1 (Intelligenz)
Was sind aus Ihrer persönlichen Erfahrung heraus wichtige Kriterien
für Intelligenz?
Aufgabe 1.2 (Wissensdarstellung)
Warum ist es in bestimmten Bereichen sinnvoll, das Wissen explizit
darzustellen, also z.B. in Form einer logischen Regel? Wann sollte
man im Gegensatz dazu das Wissen gleich direkt in einen Algorithmus
codieren?
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 2
Darstellung und Verarbeitung von Wissen
Wissen und seine Darstellung
Kriterien für die Wissensrepräsentation
Wissensarten
Arten der Wissensdarstellung
Prädikatenlogik
Logikbasierte Wissensdarstellung und Regelverarbeitung
Regelbasierte Wissensverarbeitung
Semantische Netze
Frames
Prozedurale Darstellung
Weitere Darstellungsformen
Zusammenfassung (WR/WV)
Aufgaben
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-1 (45)
Darstellung und Verarbeitung von Wissen
If an experiment works, something has gone wrong.
Finagl’s First Law
Arthur Bloch, Murphy’s Law, 1981
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-2 (46)
Darstellung und Verarbeitung von Wissen
I
Repräsentation und Verarbeitung von Wissen – Kernthemen
der KI
I
Wissen – „nützliche, anwendbare“ Information, die für eine
Problemlösung hilfreich ist.
I
geeignete Darstellungen für Wissen: WR
I
passende Verarbeitungsformen: WV
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-3 (47)
Typisches Vorgehen bei Problemlösungen
I
Charakterisierung des Gegenstandsbereichs
I
Symbolische Repräsentation der Objekte
I
Eingabe des Wissens in den Computer
I
Fragen stellen
I
Antworten interpretieren
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-4 (48)
Darstellung und Verarbeitung von Wissen
Grundlegend für KI-Systeme: explizite Repräsentation von
Wissen
Warum? Trennung des Problemwissens von der Verarbeitung .
;
In konventionellen Programmen verschmelzen Problemlösung und
Problemwissen.
; Dies ist nachteilig, falls sich Problembereich ändert.
Kernbereich der KI: Repräsentation von Wissen
WR immer im Zusammenhang mit Wissensverarbeitung
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-5 (49)
Wissensverarbeitung
Abb. 6: KI – Wissensverarbeitung
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-6 (50)
KI und Problemlösung
Folgende Probleme:
1. Wie extrahiert man das Problemwissen?
2. Wie stellt man es auf dem Rechner dar?
3. Wie kann man das Wissen automatisch verarbeiten?
Für den 3. Punkt verwendet man u.a. auch Suchalgorithmen.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
Folie 2-7 (51)
Ansatz der WR/WV
I
Adäquate Wissensdarstellung
I
Passende Wissensverarbeitung (Inferenzregeln)
I
Problemreduktion auf Suche
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.1 Wissen und seine Darstellung
Folie 2-8 (52)
Wissen und seine Darstellung
I
Ebene des Wissen (reale Welt)
I
symbolische Ebene (Repräsentationsebene)
Beispiel 2.1 (Logik)
Wir wissen: alle Menschen sind sterblich, Sokrates ist ein Mensch.
In Prädikatenlogik:
∀X mensch(X ) → sterblich(X )
mensch(sokrates)
Jetzt können wir schließen:
sterblich(sokrates)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.1 Wissen und seine Darstellung
Folie 2-9 (53)
Wissensverarbeitung
Ausgangswissen
in der realen Welt
Resultate der WV
in der realen Welt
6
?
Interne Darstellung
des Wissens
Verarbeitung durch
den Computer
Interne Darstellung
der Resultate
Abb. 7: Wissensverarbeitung – Prinzip
2 Darstellung und Verarbeitung von Wissen
2.2 Kriterien für die Wissensrepräsentation
Künstliche Intelligenz
Folie 2-10 (54)
Kriterien der WR
Wichtige Kriterien für die Qualität der Wissensrepräsentation sind:
1. Adäquatheit (Fähigkeit, das vorhandene Wissen darzustellen)
2. Granularität der Modellierung
3. Leistungskraft der Verarbeitungskomponente
4. Effizienz der Verarbeitungskomponente
5. leichte Erweiterbarkeit
2 Darstellung und Verarbeitung von Wissen
2.3 Wissensarten
Künstliche Intelligenz
Folie 2-11 (55)
Arten von Wissen
I
Relationales Wissen
I
Vererbbares Wissen
I
Prozedurales Wissen
I
Logik-Wissen
I
...
Beispiel 2.2 (Vererbung)
I
Ein Auto hat einen Motor.
I
Ein Audi ist ein Auto.
I
; D.h. der Audi hat einen Motor.
2 Darstellung und Verarbeitung von Wissen
2.3 Wissensarten
Künstliche Intelligenz
Folie 2-12 (56)
Vererbung
Abb. 8: Vererbung von Eigenschaften
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.4 Arten der Wissensdarstellung
Folie 2-13 (57)
Arten der Wissensdarstellung
Natürlichsprachliche Repr. Das Auto ist rot.
Logische Repr.
ist_rot(Auto).
∀X ist_rot(X ) → ist_ferrari(X ).
Regel-basierte Repr./Horn-Logik hat(X,raeder) :- ist_auto(X).
Semantische Netze
Objektorientierte Repräsentation z.B. Frames
Vererbungstechniken
Prozedurale Repräsentation
...
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.4 Arten der Wissensdarstellung
Folie 2-14 (58)
Behandelte WR/WV-Techniken
Wir werden uns mit folgenden Wissensrepräsentationstechniken
befassen:
I
Prädikatenlogik
I
Regelbasierte WR: Logik und Produktionsregeln
I
Vererbung: Semantische Netze und Frames
I
Unsicheres Wissen: Bayessche Formel und Sicherheitsfaktoren
I
Unscharfes Wissen: Fuzzy
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-15 (59)
Prädikatenlogik
I
Logik ist einer der ältesten
Untersuchungsgegenstände der KI.
I
Automatische Beweisen: das Thema der KI
I
Wissensrepräsentation mit Logik:
leistungsstarke Technik
I
PL wird in vielen Anwendungsgebieten der
KI benutzt.
I
Prädikatenlogik ist eine Erweiterung der
Aussagenlogik.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-16 (60)
2.5.1 Syntax
Quantifizierung
Eine Person, die eine andere Person liebt, hasst diese nicht.
I
Aussagenlogik:
liebtXY → ¬hasstXY
für jedes Personenpaar X, Y.
I
I
I
Besser: ∀X ∀Y liebt(X , Y ) → ¬hasst(X , Y )
Die Eigenschaften liebt, hasst nennt man Prädikate.
Quantifizieren nur über Objekte: Prädikatenlogik 1.Stufe (PL1).
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-17 (61)
2.5.1 Syntax
Unterschiede zur Aussagenlogik
I
Ereignisse/Eigenschaften (Prädikate) mit Argumenten
I
Quantifizierung über Objekte
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-18 (62)
2.5.1 Syntax
Prädikatenlogik – Syntax
I
Objekte (werden repräsentiert durch Konstante oder Variablen)
I
Prädikate (Relationen, Eigenschaften)
I
Funktionen
I
Verknüpfungsoperatoren und Quantoren (∧, ∨, ↔, →, ¬, ∀, ∃)
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-19 (63)
2.5.1 Syntax
Prädikatenlogik – Syntax
Prädikatenlogische Formeln können wie folgt aussehen:
I
einfach (atomar): interessant (wirtschaftsinformatik )
I
zusammengesetzt: p(a) ∨ p(b)
I
quantifiziert: ∀X p(X ), ∃X p(X )
Variablen können all- oder existenzquantifiziert sein.
Bemerkung 2.1 (Geschlossene Formeln)
I
Betrachten nur Formeln OHNE freie Variablen.
I
Jede Variable muss also quantifiziert werden.
I
; geschlossene Formeln
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-20 (64)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Syntax - Beispiel
I
Marcus war ein Mensch: mensch(marcus)
I
Marcus war ein Pompejer: pompejer (marcus)
I
Alle Pompejer waren Römer: ∀X pompejer (X ) → roemer (X )
I
I
I
I
I
Der Herrscher war Caesar: herrscher (caesar )
Alle Römer verhielten sich Caesar gegenüber loyal oder hassten
ihn: ∀X roemer (X ) → (loyal (X , caesar ) ∨ hasst (X , caesar ))
Jeder Mensch verhält sich zu irgendjemandem loyal:
∀X mensch(X ) → ∃Y (mensch(Y ) ∧ loyal (X , Y ))
Menschen ermorden nur solche Herrscher, zu denen sie nicht
loyal sind: ∀X ∀Y (mensch(X ) ∧ herrscher (Y ) ∧
∧ mordversuch(X , Y )) → ¬loyal (X , Y )
Marcus hat versucht, Caesar umzubringen:
mordversuch(marcus, caesar )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-21 (65)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Gültigkeitsbereich der Quantoren
In
∀X mensch(X ) → sterblich(X )
bezieht sich der Quantor auf die gesamte Implikation. Also müsste
man eigentlich schreiben:
∀X [mensch(X ) → sterblich(X )]
Dagegen beschränkt sich die Gültigkeit des ersten X in der Formel
∀X p(X ) ∨ ∀X q (X )
nur auf die Aussage p.
Besser: Umbenennung der Variablen ∀X p(X ) ∨ ∀Y q (Y ).
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-22 (66)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Gültigkeitsbereich der Quantoren
Schreiben Sie den Quantor an die Stelle, wo er hingehört. In der
Aussage: „Alle Menschen haben einen Vater.“ brauchen wir einen Allund Existenzquantor:
∀X mensch(X ) → ∃Y mensch(Y ) ∧ vater_von(X , Y )
In ausführlicher Schreibweise mit Klammern sieht die Formel so aus:
∀X ( mensch(X ) → ∃Y (mensch(Y ) ∧ vater_von(X , Y )) )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-23 (67)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzung von Aussagen in die PL
Wie übersetzt man die Aussage
„WI- und MM-Studenten lieben (alle) Informatikthemen.“
korrekt in die Prädikatenlogik?
1. Welche Eigenschaften haben wir? wi_student, mm_student,
informatikthema, liebt
2. Auf wen beziehen sich diese Eigenschaften?
I wi_student ; Person; also einstellig.
I mm_student ; Person; also einstellig.
I informatikthema ; Thema; also einstellig.
I liebt ; Person, Thema; also zweistellig.
3. Ist es eine Alle- oder Existiert-Aussage? ∀X .
4. Die Liebe zu Informatikthemen gilt für WI- und MM-Studenten:
I ∀X ∀Y wi_student(X ) ∧ informatikthema(Y ) → liebt(X , Y )
I ∀X ∀Y mm_student(X ) ∧ informatikthema(Y ) → liebt(X , Y )
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-24 (68)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzung von Aussagen in die PL
Wie übersetzt man die Aussage „Marcus war ein Mensch“ korrekt in
die Prädikatenlogik?
1. mensch(marcus)
2. marcus(mensch)
Variante 1 ist richtig. mensch ist eine Eigenschaft (die Marcus erfüllt),
marcus dagegen ist keine Eigenschaft, sondern ein Objekt.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-25 (69)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzung von Aussagen in die PL
1. Erkennen, welche Eigenschaften (wahr/falsch) und Objekte
enthalten sind
2. Erkennen der atomaren Aussagen (Eigenschaft mit zugehörigen
Objekten);
Einführung von Variablen für variable Objekte
3. Logische Verknüpfungen erkennen
4. Ggf. Quantifizierung erkennen
5. Teil-Aussagen im Satz erkennen und benennen, Aussage
möglichst in Teilaussagen zerlegen
6. Formel aufstellen
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-26 (70)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Implizite und explizite Quantifizierung
In der Umgangssprache verwenden wir häufig implizite
Quantifizierung.
I
I
I
Menschen sind intelligent: ∀X mensch(X ) → intelligent (X )
Da sind Menschen in der Stadt: ∃X mensch(X ) ∧ in_stadt (X )
Jeder Mensch verhält sich zu irgendjemandem loyal:
∀X mensch(X ) → ∃Y (mensch(Y ) ∧ loyal (X , Y ))
Unterschied zwischen All- und Existenz-Quantifizierung. Faustregel:
I
All-Quantifizierung: i.allg. Implikation
I
Existenz-Quantifizierung: i.allg. UND.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-27 (71)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Quantifizierung
Warum wurde Aussage Alle Pompejer waren Römer nicht so
übersetzt?
∀X (pompejer ) roemer (X )
Denn eigentlich nur Aussage über Pompejer.
I
In der Prädikatenlogik nicht möglich.
I
Es ist aber auch nicht nötig.
Die Formel
∀X pompejer (X ) → roemer (X )
drückt das Gleiche aus.
(Implikation ist auch für jedes X wahr, welches nicht Pompejer ist.)
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-28 (72)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Was ist richtig?
Wie drückt man in der Prädikatenlogik aus: Alle Discobesucher sind
jung?
Var 1
Var 2
I
∀X discobesucher (X ) ∧ jung (X )
∀X discobesucher (X ) → jung (X )
∀X meint wirklich alle X , also zB Helmut Schmidt.
I
Besucht Hr. Schmidt eine Disco, und ist er jung? Nein.
I
Also ist Variante 2 richtig.
Falls das gewählte X ein Discobesucher ist, dann ist er/sie zwingend
jung.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-29 (73)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Was ist richtig?
Aussage eines Tatverdächtigen Anton: „Ich war es nicht, ich war nicht
am Tatort, Claus war’s.“
¬taeter (anton) ∧ ¬am_tatort (anton) ∧ taeter (claus)
Was müssen wir tun, wenn wir wissen, dass Anton lügt?
Var 1
Var 2
taeter (anton) ∧ am_tatort (anton) ∧ ¬taeter (claus)
¬(¬taeter (anton) ∧ ¬am_tatort (anton) ∧ taeter (claus))
Welche Variante ist richtig? Variante 2!
Und welche Formel nehmen wir nun in unsere Wissensbasis auf?
I
Die Originalaussage? Nein, die ist ja gelogen.
I
Variante 2!
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-30 (74)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Quantoren
Beispiel 2.3 (Übersetzen von Alltagsaussagen)
I
I
I
I
I
I
I
I
Alle Elefanten sind Säugetiere: ∀X elefant(X ) → saeugetier(X )
Einige Elefanten sind Säugetiere:
∃X elefant(X ) ∧ saeugetier(X )
Einige Elefanten sind keine Säugetiere:
∃X elefant(X ) ∧ ¬saeugetier(X )
Kein Elefant ist ein Säugetier: ∀X elefant(X ) → ¬saeugetier(X )
oder ¬∃X elefant(X ) ∧ saeugetier(X )
Alle Vögel haben Federn: ∀X vogel(X ) → hatfedern(X )
Einige Vögel können fliegen: ∃X vogel(X ) ∧ kannfliegen(X )
Einige Vögel können nicht fliegen:
∃X vogel(X ) ∧ ¬kannfliegen(X )
Kein Vogel ist ein Säugetier: ¬∃X vogel(X ) ∧ saeugetier(X )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-31 (75)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Quantoren
Beispiel 2.4 (Übersetzen von Alltagsaussagen 2)
I
I
I
Anne besucht alle Filme, in denen George Clooney mitspielt.
∀X film(X ) ∧ spielt_mit(X , clooney ) → besucht(anne, X )
Anne besucht nur die Filme, in denen George Clooney mitspielt.
∀X film(X ) ∧ besucht(anne, X ) → spielt_mit(X , clooney )
Das Einzige, was Anne besucht, sind Filme, in denen George
Clooney mitspielt.
∀X besucht(anne, X ) → film(X ) ∧ spielt_mit(X , clooney )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-32 (76)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzen in PL
Jeder fragt sich selbst.
∀X fragt(X , X )
(genauer: ∀X mensch(X ) → fragt(X , X ))
Die Diagonale ist voll.
Jemand fragt sich selbst.
∃X fragt(X , X )
(genauer: ∃X mensch(X ) ∧ fragt(X , X ))
Mindestens ein Diagonalelement ist wahr.
a
b
X c
d
e
Y
a b c d e
x
x
x
x
x
Y
a b c d e
a
b
X c
d
e
x
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-33 (77)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzen in PL
Jeder fragt jeden.
∀X ∀Y fragt(X , Y )
( ∀X ∀Y mensch(X ) ∧ mensch(Y ) → fragt(X , Y ))
Jede Kombination ist wahr.
Jeder fragt jemanden.
∀X ∃Y fragt(X , Y )
( ∀X mensch(X ) → ∃Y mensch(Y ) ∧ fragt(X , Y ))
Keine Zeile ist leer.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
a
b
X c
d
e
a
x
x
x
x
x
b
x
x
x
x
x
Y
c
x
x
x
x
x
d
x
x
x
x
x
e
x
x
x
x
x
Y
a b c d e
a
x
b
x
X c
x
d
x
e x
Künstliche Intelligenz
Folie 2-34 (78)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzen in PL
Jeder wird von jemandem gefragt.
∀Y ∃X fragt(X , Y )
( ∀Y mensch(Y ) → ∃X mensch(X ) ∧ fragt(X , Y ))
Keine Spalte ist leer.
Jemand fragt jeden.
∃X ∀Y fragt(X , Y )
( ∃X mensch(X ) ∧ [∀Y mensch(Y ) → fragt(X , Y )])
Eine Zeile ist voll.
Y
a b c d e
a
x
x
b
X c x
x
d
x
e
Y
a b c d e
a
b x x x x x
X c
d
e
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-35 (79)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Übersetzen in PL
Jemand wird von allen gefragt.
∃Y ∀X fragt(X , Y )
( ∃Y mensch(Y ) ∧ [∀X mensch(X ) → fragt(X , Y )])
Eine Spalte ist komplett besetzt.
Jemand fragt jemanden.
∃X ∃Y fragt(X , Y )
( ∃X ∃Y mensch(X ) ∧ mensch(Y ) ∧ fragt(X , Y ))
Eine Zelle ist wahr.
Y
a b c d e
a
x
b
x
X c
x
d
x
e
x
Y
a b c d e
a
b
X c
d
e
2 Darstellung und Verarbeitung von Wissen
x
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-36 (80)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Quantoren und Mengendiagramme – 1
Betrachten wir die Aussage: Jeder Student lernt.
∀X stud(X ) → lernt(X )
Die Menge der Studenten muss also eine Teilmenge der Menge aller
Lernenden sein.
Abb. 9: All-Aussagen als Mengendiagramm
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-37 (81)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Quantoren und Mengendiagramme – 2
Betrachten wir die Aussage: Es gibt einen Studenten, der lernt.
∃X stud(X ) ∧ lernt(X )
Die Mengen der Studenten und der Lerner müssen also mindestens
ein gemeinsames Element haben.
Abb. 10: Existenz-Aussagen als Mengendiagramm
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-38 (82)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Reihenfolge der Quantoren
I
Reihenfolge der Quantoren i.allg. wichtig.
I
Wenn NUR Existenz- oder Allquantoren, dann i.allg. egal.
∀X ∀Y fragt(X , Y ) äquivalent zu ∀Y ∀X fragt(X , Y ).
Allerdings gilt das nicht, wenn man Existenz- und Allaussagen mischt:
∀X ∃Y fragt(X , Y ) ist NICHT äquivalent zu ∃Y ∀X fragt(X , Y ).
Bei der ersten Aussage gibt es zu jedem X ein Y, so dass fragt(X,Y)
gilt. In der zweiten Aussage gibt es EIN Y, welches von ALLEN gefragt
wird.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-39 (83)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Übersetzen 1
Satz
. . . und . . .
sowohl . . . als auch . . .
aber, jedoch, obwohl
. . . oder . . .
Wenn A dann B, aus A folgt B
A, vorausgesetzt dass B gilt
A, falls/wenn B
A nur dann, wenn B
A genau dann, wenn B
entweder A oder B
weder A noch B
A, es sei denn B
Es stimmt nicht, dass . . .
prädikatenlogisch
A ∧ B
A ∧ B
A ∧ B
A ∨ B
A → B
B → A
B → A
A → B
A ↔ B
(A ∨ B ) ∧ (¬A ∨ ¬B )
¬A ∧ ¬B
(B → ¬A) ∧ (¬B → A)
¬(. . .)
Tabelle 1: Übersetzen von Aussagen 1
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-40 (84)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Übersetzen 2
Satz
Alle . . .
Nicht alle . . .
Wenn jemand . . . , dann . . .
Keiner . . .
Manche/Einige . . .
prädikatenlogisch
∀X . . .
¬∀X . . .
∀X . . . → . . .
¬∃X . . . oder ∀X ¬ . . .
∃X . . .
Tabelle 2: Übersetzen von Aussagen
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-41 (85)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Übersetzen
Sowohl GmbHs als auch AGs sind Kapitalgesellschaften.
sowohl . . . als auch . . . = UND ?
∀X GmbH(X ) ∧ AG(X ) → Kapitalgesellschaft(X )
Nicht korrekt. In der Aussage stecken zwei Aussagen:
I
GmbHs sind Kapitalgesellschaften.
I
Aktiengesellschaften sind Kapitalgesellschaften.
Also eigentlich: Es gelten sowohl die Aussage
I
GmbHs sind Kapitalgesellschaften.
als auch die Aussage
Aktiengesellschaften sind Kapitalgesellschaften.
I ∀X GmbH(X ) → Kapitalgesellschaft(X )
∧
Dies ergibt:
I ∀X AG(X ) → Kapitalgesellschaft(X )
Äquivalent: ∀X GmbH(X ) ∨ AG(X ) → Kapitalgesellschaft(X )
I
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-42 (86)
2.5.2 Übersetzen von Aussagen in die Prädikatenlogik
Prädikatenlogik – Übersetzen
Analog hätten wir verfahren müssen, wenn die Aussage mit einem
UND formuliert wäre:
GmbHs und Aktiengesellschaften sind Kapitalgesellschaften.
Umgangssprachliches Oder ist häufig das Entweder-Oder!
Ich gehe heute abend in’s Kino oder in’s Theater.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-43 (87)
2.5.3 Gültigkeit und Erfüllbarkeit
Gültigkeit und Erfüllbarkeit
In Analogie zur Aussagenlogik gibt es auch hier Formeln, die
I
immer wahr,
I
immer falsch sind
I
wahr oder falsch sein können.
oder
Beispiel 2.5 (Wahre und falsche Aussagen)
I
I
I
∀X p(X ) ∨ ¬p(X ) ist immer wahr.
∀X p(X ) ∧ ¬p(X ) ist immer falsch.
Die Formel ∃X p(X ) kann falsch oder wahr sein.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
2.5.3 Gültigkeit und Erfüllbarkeit
Klassifikation von Formeln
I
Kann man eine Formel φ wahrmachen: φ ist erfüllbar.
I
Geht dies überhaupt nicht: φ ist unerfüllbar (falsch).
I
Ist die Formel immer wahr: φ ist allgemeingültig (Tautologie).
I
Kann man die Formel falsch machen: φ ist falsifizierbar.
Folie 2-44 (88)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-45 (89)
2.5.3 Gültigkeit und Erfüllbarkeit
Allgemeingültigkeit
Für prädikatenlogische Formeln φ gilt der Satz:
Satz 2.2 (Allgemeingültigkeit)
φ ist allgemeingültig, gdw. ¬φ ist unerfüllbar.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-46 (90)
2.5.3 Gültigkeit und Erfüllbarkeit
Zusammenhänge zwischen den Begriffen
I
I
I
I
I
I
φ ist allgemeingültig, gdw. ¬φ ist unerfüllbar.
Die erfüllbaren und die falschen Formeln sind komplementär.
allgemeingültige Formeln ⊂ erfüllbare Formeln
falsche Formeln ⊂ falsifizierbare Formeln
(erfüllbare F. ∩ falsifizierbare F.) ∪ allgemeingültige F.
= erfüllbare Formeln
(erfüllbare F. ∩ falsifizierbare F.) ∪ falsche Formeln
= falsifizierbare F.
Tauto−
logien
sowohl
erfüllbar
als auch
falsifizierbar
falsche
Formeln
Abb. 11: Prädikatenlogische Formeln
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-47 (91)
2.5.4 Folgern
Folgern
Wir schreiben Φ |= φ gdw. φ immer wahr ist, falls Φ wahr ist.
Man sagt: Aus Φ folgt φ.
Es gilt beispielsweise:
I
I
∀X p(X ) |= ∃X p(X )
mensch(a) ∧ ∀X (mensch(X ) → sterblich(X )) |= sterblich(a)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-48 (92)
2.5.5 Wissensverarbeitung mit Prädikatenlogik
Automatische Verarbeitung
Modus ponens (Aussagenlogik)
L → K
L
K
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-49 (93)
2.5.5 Wissensverarbeitung mit Prädikatenlogik
Prädikatenlogik und Modus ponens
In dieser Form ist der Modus ponens auf die Formeln:
mensch(sokrates)
∀X mensch(X ) → sterblich(X )
nicht anwendbar, um ableiten zu können, dass gilt:
sterblich(sokrates)
Dazu braucht man eine Regel, die aus
∀X mensch(X ) → sterblich(X )
ableitet, dass gilt (Instantiierung einer allquantifizierten Variablen):
mensch(sokrates) → sterblich(sokrates)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-50 (94)
2.5.5 Wissensverarbeitung mit Prädikatenlogik
Weitere Inferenzregeln
All-Instantiierung
∀X p(X )
p (a )
a . . . beliebige Konstante
Modus tollens:
L → K
¬K
¬L
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-51 (95)
2.5.5 Wissensverarbeitung mit Prädikatenlogik
Inferenzregeln
In dieser Art kann man verschiedene Schlussregeln formulieren, mit
deren Hilfe man logische Schlüsse automatisch vollziehen kann.
Problem: Sehr großer Suchraum, da:
I
ein und dieselbe Aussage auf unterschiedlichste Art und Weise
darstellbar,
I
eine Inferenzregel auf verschiedene Formeln anwendbar,
I
unterschiedliche Inferenzregeln anwendbar.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
2.5.6 Ableiten und Folgern
Folgern und Ableiten
2 unterschiedliche Begriffe für Zusammenhänge von Formeln:
I
I
Folgern: Φ |= φ (φ folgt zwingend aus Φ)
Ableiten: Φ ` φ (φ ist aus Φ – mittels Inferenzregeln –
berechenbar)
Künstliche Intelligenz
Folie 2-52 (96)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-53 (97)
2.5.7 Resolution
Resolution
Resolution besteht aus 2 Schritten:
1. Herstellung einer einheitlichen Darstellung der Formeln
2. Führen des Widerspruchsbeweises
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-54 (98)
2.5.7 Resolution
Äquivalenzen
Beobachtung: Es gibt äquivalente Formeln.
Aus der Sicht des Beweisens ungünstig.
Definition 2.3 (Äquivalenz)
2 Formeln φ1 , φ2 heißen äquivalent (φ1 ≡ φ2 ), falls φ1 wahr ist, genau
dann wenn auch φ2 wahr ist.
Es gilt: φ1 ≡ φ2 gdw. φ1 ↔ φ2 eine Tautologie ist.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-55 (99)
2.5.7 Resolution
Äquivalenzen – 1
A → B ≡ ¬A ∨ B
Implikation
A ↔ B ≡ (A → B) ∧ (B → A)
Äquivalenz
¬(A ∨ B) ≡ ¬A ∧ ¬B
DeMorgan
¬(A ∧ B) ≡ ¬A ∨ ¬B
DeMorgan
(A ∨ (B ∧ C)) ≡ ((A ∨ B) ∧ (A ∨ C)) Distributivität
(A ∧ (B ∨ C)) ≡ ((A ∧ B) ∨ (A ∧ C)) Distributivität
¬∀X A ≡ ∃X ¬A Negierter All-Quantor
¬∃X A ≡ ∀X ¬A Negierter Existenz-Quantor
Tabelle 3: Prädikatenlogische Äquivalenzen – 1
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-56 (100)
2.5.7 Resolution
Äquivalenzen – 2
A ∨ A ≡ A
A ∧ A ≡ A
A ∨ B ≡ B ∨ A
A ∧ B ≡ B ∧ A
(A ∨ (B ∨ C)) ≡ ((A ∨ B) ∨ C)
(A ∧ (B ∧ C)) ≡ ((A ∧ B) ∧ C)
(A ∨ (A ∧ B)) ≡ A
(A ∧ (A ∨ B)) ≡ A
(A ∧ B) → C ≡ A → (B → C)
(A → B) ∧ (A → ¬B) ≡ ¬A
A → B ≡ ¬B → ¬A
Idempotenz
Idempotenz
Kommutativität
Kommutativität
Assoziativität
Assoziativität
Absorption
Absorption
Absurdität
Kontraposition
Tabelle 4: Prädikatenlogische Äquivalenzen – 2
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-57 (101)
2.5.7 Resolution
Äquivalenzen – 3
(A
(A
(A
(A
∧
∧
∨
∨
B)
B)
B)
B)
≡
≡
≡
≡
A
B
B
A
falls B eine Tautologie
falls B falsch
falls B eine Tautologie
falls B falsch
Tabelle 5: Prädikatenlogische Äquivalenzen – 3
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-58 (102)
2.5.7 Resolution
Klauselnormalform
n
^
i =1
mi
_
j =1
Lij
!!
Lij . . . Literal (elementare Aussage oder deren Negation)
Wmi
I
j =1 Lij . . . Klausel
I
Beispiel 2.6 (Klauselnormalform)
(p(X ) ∨ q (X )) ∧ (s(X , Y ) ∨ ¬t (Y )) ∧ a(X ) ist eine korrekte
konjunktive Normalform, wobei wir im folgenden einfach die Und
weglassen und die Klauseln untereinander schreiben:
p(X ) ∨ q (X )
s(X , Y ) ∨ ¬t (Y )
a(X )
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-59 (103)
2.5.7 Resolution
Transformation auf Klausel-Normalform
Beispiel 2.7 (Transformation auf KNF)
I
mensch(marcus)
I
pompejer (marcus)
I
∀X pompejer (X ) → roemer (X ) ;
∀X (¬pompejer (X ) ∨ roemer (X ))
; ¬pompejer (X ) ∨ roemer (X )
I
herrscher (caesar )
I
∀X roemer (X ) → (loyal (X , caesar ) ∨ hasst (X , caesar ))
; ∀X (¬roemer (X ) ∨ loyal (X , caesar ) ∨ hasst (X , caesar ))
; ¬roemer (X ) ∨ loyal (X , caesar ) ∨ hasst (X , caesar )
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-60 (104)
2.5.7 Resolution
Beispiel – Klausel-Normalform
Beispiel 2.7 cont.
I
∀X mensch(X ) → ∃Y (mensch(Y ) ∧ loyal (X , Y )) ;
∀X (¬mensch(X ) ∨ ∃Y (mensch(Y ) ∧ loyal (X , Y ))) ;
¬mensch(X ) ∨ (mensch(f (X )) ∧ loyal (X , f (X )))
(Zu jedem X gibt es ein Y, also hängt Y von X ab, folglich
Y = f (X ).)
; (¬mensch(X ) ∨ mensch(f (X ))) ∧ (¬mensch(X ) ∨
loyal (X , f (X )))
I
I
∀X ∀Y (mensch(X ) ∧ herrscher (Y ) ∧ mordversuch(X , Y )) →
¬loyal (X , Y )
; ∀X ∀Y (¬mensch(X ) ∨ ¬herrscher (Y ) ∨
¬mordversuch(X , Y ) ∨ ¬loyal (X , Y ))
; ¬mensch(X ) ∨ ¬herrscher (Y ) ∨ ¬mordversuch(X , Y ) ∨
¬loyal (X , Y )
mordversuch(marcus, caesar )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-61 (105)
2.5.7 Resolution
Existenzquantor – Skolemisierung
I
I
I
I
I
∃X (r (X ) ∨ s(X )) ; (r (a) ∨ s(a))
∀X ∃Y (p(X ) ∨ r (Y )) ; ∀X (p(X ) ∨ r (f (X )))
∀X ∃Y ∀Z (p(X ) ∨ r (Y ) ∨ s(Z ))
; ∀X ∀Z (p(X ) ∨ r (g (X )) ∨ s(Z ))
∀X ∀Z ∃Y (p(X ) ∨ r (Y ) ∨ s(Z ))
; ∀X ∀Z (p(X ) ∨ r (h(X , Z )) ∨ s(Z ))
∃Y ∀Z (r (Y ) ∨ s(Z )) ; ∀Z (r (b) ∨ s(Z ))
f , g , h sind neue Funktionssymbole, a, b neue Konstanten. Diese
dürfen nur in der entsprechenden Formel verwendet werden.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-62 (106)
2.5.7 Resolution
Skolemisierung – 2
Und warum müssen wir immer neue Funktionen bzw. Konstanten
erfinden?
I
Der Autodieb – nennen wir ihn Joe – brach 23:45 den Kofferraum
des Autos auf.
I
Der Ladendieb – nennen wir ihn Joe – stürzte ein Regal um,
dann gelang ihm die Flucht.
Hier ist das doppelte Verwenden des Pseudonyms Joe inkorrekt, da
die beiden wohl nicht identisch sind.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-63 (107)
2.5.7 Resolution
Transformation auf KNF
Transformation auf Klausel-NF:
1. Ersetzen der Äquivalenzen und Implikationen
2. Negation bis zu atomaren Formeln verschieben
3. Entfernen der doppelten Negation
4. Standardisierung der Variablen (keine 2 Quantoren mit der
gleichen Variablen)
5. Eliminieren der Existenzquantoren (Skolemisierung)
6. Weglassen aller All-Quantoren
7. „Ausmultiplizieren“ mittels Distributivgesetz
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-64 (108)
2.5.7 Resolution
Achtung !
Bemerkung 2.4 (Korrektes Klammern)
Klammern Sie die Formeln korrekt. Wir betrachten:
∀X mensch(X ) → sterblich(X )
Mit Klammern:
Es entsteht die Klausel:
∀X (mensch(X ) → sterblich(X ))
¬mensch(X ) ∨ sterblich(X )
Bei falscher Klammerung:
entsteht die Formel:
also:
und somit die falsche Klausel:
(∀X mensch(X )) → sterblich(X )
(¬∀X mensch(X )) ∨ sterblich(X )
(∃X ¬mensch(X )) ∨ sterblich(X )
¬mensch(a) ∨ sterblich(X )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-65 (109)
2.5.7 Resolution
Ausmultiplizieren
Bemerkung 2.5 (Ausmultiplizieren)
Geoderte Teilterme kann man meist in Ruhe lassen. Wir betrachten:
a ∨ b ∨ (c ∧ d )
Ersetzen Teilterm (a ∨ b) durch x:
x ∨ (c ∧ d )
Nun wenden wir das Distributivgesetz an (Ausmultiplizieren):
(x ∨ c ) ∧ (x ∨ d )
Jetzt ersetzen wir x wieder durch den Originalterm und erhalten:
(a ∨ b ∨ c ) ∧ (a ∨ b ∨ d )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-66 (110)
2.5.7 Resolution
Widerspruchsbeweis
Der Beweis, dass:
Φ |= φ
ist äquivalent zum Beweis, dass
Φ ∧ ¬φ
widersprüchlich ist.
; Nehmen das Ziel negiert auf.
Negieren Sie das gesamte Ziel!
I
Aus dem Ziel
I
wird negiert
I
und folglich
∃X mensch(X )
¬∃X mensch(X )
∀X ¬mensch(X )
Falsch wäre: Direktes Negieren von mensch(X): ∃X ¬mensch(X )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-67 (111)
2.5.7 Resolution
Widerspruchsbeweis
Möchten wir beweisen, dass Marcus nicht loyal gegenüber Caesar
war, so fügen wir
loyal (marcus, caesar )
zu unserer Wissensbasis hinzu und suchen dann einen Widerspruch.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
2.5.7 Resolution
Resolutionsregel
. . . analog Aussagenlogik
Klausel1 = L1 ∨ L2 ∨ L3 ∨ . . . ∨ Ln
Klausel2 = ¬L1 ∨ K2 ∨ K3 ∨ . . . ∨ Km
Resolvente = L2 ∨ L3 ∨ . . . Ln ∨ K2 ∨ K3 ∨ . . . ∨ Km
Resolutionsregel für Prädikatenlogik
Klausel1 = L1 ∨ L2 ∨ L3 ∨ . . . ∨ Ln
Klausel2 = ¬K1 ∨ K2 ∨ K3 ∨ . . . ∨ Km
L1 und K1 sind unifizierbar mit der Substitution σ
Resolvente = σ(L2 ∨ . . . ∨ Ln ∨ K2 ∨ . . . ∨ Km )
Folie 2-68 (112)
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-69 (113)
2.5.7 Resolution
Unifikation
Unifizieren bedeutet das Suchen nach einer Variablensubstitution, so
dass beide Literale gleich sind.
; most general unifier
Beispiel 2.8 (Unifikation)
Die Unifikation von p(f (a, X )) und p(f (Y , c )) liefert die
Variablensubstitution [X ; c , Y ; a].
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-70 (114)
2.5.7 Resolution
Faktorisierung
I
Klauseln p(X ) ∨ p(a) und ¬p(a) ∨ ¬p(Y ) sind widersprüchlich.
I
Mit Resolutionsregel nicht beweisbar.
I
Man benötigt dazu die sogenannte Faktorisierungsregel:
Klausel1 = L1 ∨ L2 ∨ L3 ∨ . . . ∨ Ln
L1 und L2 sind unifizierbar mit der Substitution σ
Klausel2 = σ(L1 ∨ L3 ∨ . . . Ln )
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-71 (115)
2.5.7 Resolution
Klauseln als Mengen
Man kann Klauseln auch als Mengen schreiben. Die Resolutionsregel
sieht dann wie folgt aus:
Klausel1 = {L1 , L2 , L3 , . . . Ln }
Klausel2 = {¬K1 , K2 , K3 , . . . Km }
L1 und K1 sind unifizierbar mit der Substitution σ
Resolvente = (σ(Klausel1 ) \ {σ(L1 )}) ∪ (σ(Klausel2 ) \ {σ(¬K1 )})
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-72 (116)
2.5.7 Resolution
Caesar-Beispiel
neg. Ziel
7+9
1 + 10
4 + 11
8 + 12
mensch(marcus)
pompejer (marcus)
¬pompejer (X1 ) ∨ roemer (X1 )
herrscher (caesar )
¬roemer (X2 ) ∨ loyal (X2 , caesar ) ∨ hasst (X2 , caesar )
¬mensch(X3 ) ∨ loyal (X3 , f (X3 ))
¬mensch(X4 ) ∨ mensch(f (X4 ))
¬mensch(X5 ) ∨ ¬herrscher (X6 ) ∨
¬mordversuch(X5 , X6 ) ∨ ¬loyal (X5 , X6 )
mordversuch(marcus, caesar )
loyal (marcus, caesar )
¬mensch(marcus) ∨ ¬herrscher (caesar ) ∨
¬mordversuch(marcus, caesar )
¬herrscher (caesar ) ∨ ¬mordversuch(marcus, caesar )
¬mordversuch(marcus, caesar )
2
Tabelle 6: Caesar-Beispiel
1
2
3
4
5
6a
6b
7
8
9
10
11
12
13
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-73 (117)
2.5.7 Resolution
Korrektheit
Wie verhält sich diese Berechnungsregel?
I
Ist sie korrekt? Jede Formel, die man mit Hilfe der
Resolutionsregel berechnen kann, folgt auch aus den Formeln?
Satz 2.6 (Korrektheit)
Resolution ist korrekt.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-74 (118)
2.5.7 Resolution
Vollständigkeit
I
Ist Resolution vollständig? Kann man jede Formel, die logisch
folgt, auch mittels Resolution berechnen?
I
NEIN. Aus
A
und
B
nicht ableitbar, dass dann auch gilt:
A ∨ B
Satz 2.7 (Widerlegungsvollständigkeit)
Ist die Klauselmenge widersprüchlich, so existiert eine endliche Folge
von Resolutionsschritten, die zur leeren Klausel führt.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-75 (119)
2.5.7 Resolution
Beliebter Fehler
Das gleichzeitige Streichen von mehr als 1 Literal ist nicht zulässig!
{p(X ), q (Y )}
{¬p(S ), ¬q (T )}
{}
Dies ist kein korrekter Schritt, da sich die Klauseln nicht
widersprechen!
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-76 (120)
2.5.7 Resolution
Resolution und direkte Beweise
I
Resolution wird i.allg. für Widerspruchsbeweise eingesetzt.
I
Nach dem oben gesagten (Unvollständigkeit) sind eigentlich
direkte Beweise nicht sinnvoll.
I
Aber Resolution ist korrekt , leitet also immer Klauseln ab, die
auch gelten.
I
Wenn man keine Idee hat, was zu beweisen ist, kann man
durchaus mit den gegebenen Klauseln resolvieren.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-77 (121)
2.5.7 Resolution
Resolution und direkte Beweise – 2
Seien diese Formeln gegeben:
¬a → b
b ∧ a → ¬c
(¬c ∨ ¬a) → ¬b
Als Klauseln erhält man:
a ∨ b / ¬b ∨ ¬a ∨ ¬c / c ∨ ¬b / a ∨ ¬b
Durch Resolution (1+4) erhält man: a .
Aber Vorsicht: Das funktioniert nicht immer.
Frage: Wie beweist man mit Resolution, dass a ∧ ¬a immer falsch
ist?
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-78 (122)
2.5.7 Resolution
3 Anwendungsmöglichkeiten der Resolution
Widerspruchsbeweis Ziel wird negiert hinzugenommen. Widerspruch
suchen.
„Falsch“-Beweis Beweis, dass eine gegebene Formel falsch ist. Nichts
negieren. Einfach Widerspruch mittels Resolution
suchen.
Direkter Beweis Man hat kein Ziel. Einfach Resolution anwenden,
eventuell bekommt man was vernünftiges raus.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-79 (123)
2.5.7 Resolution
Problem
Haben wir mit der Resolution das perfekte Beweis-Verfahren?
I
Resolution ist zwar ein universelles Verfahren, allerdings gibt es
I
Komplexitätsprobleme (wenn viele Klauseln), da viele mögliche
Klauseleltern mit komplementären Literalen existieren.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-80 (124)
2.5.8 Resolutionsstrategien
Resolutionsstrategien – 1
Unit preference Klauseln, die nur ein Literal enthalten, werden als
Eltern vorgezogen.
Kurze Eltern Es werden die Elternklauseln gewählt, so dass die
Summe ihrer Längen minimal ist.
Diese Strategien reduzieren den Suchraum nicht, sie strukturieren
ihn nur.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-81 (125)
2.5.8 Resolutionsstrategien
Resolutionsstrategien – 2
P/N-Restriktion Eine Elternklausel darf nur positive/negative Literale
enthalten.
Input Resolution Mindestens ein Elternteil muss aus der
Klausel-Ausgangsmenge sein.
Lineare Resolution Aktuelle Resolvente ist Elternteil des nächsten
Resolutionsschritts.
Set of Support Mindestens ein Elternteil muss aus der Set of Support
(SOS) kommen.
Input-Resolution ist nicht widerlegungsvollständig, alle anderen sind
es.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-82 (126)
2.5.8 Resolutionsstrategien
Die Strategie SOS
I
SOS = Trägermenge = Klauseln, die aus dem negierten Ziel
entstanden sind.
I
Resolutionsschritt muss immer eine Elternklausel aus der SOS
haben.
I
Neue Resolventen werden in SOS aufgenommen.
Die SOS-Strategie ist widerlegungsvollständig.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-83 (127)
2.5.9 Beispiel 1 Resolution
Beispiel Resolution
Inspektor Craig erfährt in einem Unternehmen folgendes:
1. Ein Mitarbeiter ist wahnsinnig, wenn alle seine Untergebenen
ehrgeizig sind.
2. Alle Karrieristen sind ehrgeizig.
3. Ist jemand kein Karrierist, so auch keiner seiner Chefs.
Wir möchten mittels Resolution beweisen, dass alle Karrieristen
wahnsinnig sind.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-84 (128)
2.5.9 Beispiel 1 Resolution
Beispiel Resolution
Gegebene Aussagen in die PL übersetzen:
1. Ein Mitarbeiter ist wahnsinnig, wenn alle seine Untergebenen
ehrgeizig sind.
∀X (∀Y chef(Y , X ) → ehrgeizig(Y )) → wahnsinnig(X )
2. Alle Karrieristen sind ehrgeizig.
∀X karrierist(X ) → ehrgeizig(X )
3. Ist jemand kein Karrierist, so auch keiner seiner Chefs.
∀X ¬karrierist(X ) → ¬∃Y (chef(X , Y ) ∧ karrierist(Y ))
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-85 (129)
2.5.9 Beispiel 1 Resolution
Beispiel Resolution
Jetzt die KNF:
1. ∀X (∀Y chef(Y , X ) → ehrgeizig(Y )) → wahnsinnig(X )
∀X ¬(∀Y ¬chef(Y , X ) ∨ ehrgeizig(Y )) ∨ wahnsinnig(X )
∀X (∃Y [chef(Y , X ) ∧ ¬ehrgeizig(Y )]) ∨ wahnsinnig(X )
∀X (chef(f (X ), X ) ∧ ¬ehrgeizig(f (X ))) ∨ wahnsinnig(X )
(chef(f (X ), X ) ∨ wahnsinnig(X )) ∧
∧ (¬ehrgeizig(f (X )) ∨ wahnsinnig(X ))
2. ∀X karrierist(X ) → ehrgeizig(X )
¬karrierist(X ) ∨ ehrgeizig(X )
3. ∀X ¬karrierist(X ) → ¬∃Y (chef(X , Y ) ∧ karrierist(Y ))
karrierist(X ) ∨ ¬chef(X , Y ) ∨ ¬karrierist(Y )
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
2.5.9 Beispiel 1 Resolution
Beispiel Resolution
Das zu beweisende Ziel ist: Alle Karrieristen sind wahnsinnig:
∀X karrierist(X ) → wahnsinnig(X ).
Negation des Ziels: ¬(∀X karrierist(X ) → wahnsinnig(X ))
KNF: ∃X karrierist(X ) ∧ ¬wahnsinnig(X )
karrierist(a) ∧ ¬wahnsinnig(a)
Künstliche Intelligenz
Folie 2-86 (130)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-87 (131)
2.5.9 Beispiel 1 Resolution
Beispiel Resolution
1. chef(f (X1 ), X1 ) ∨ wahnsinnig(X1 )
2. ¬ehrgeizig(f (X2 )) ∨ wahnsinnig(X2 )
3. ¬karrierist(X3 ) ∨ ehrgeizig(X3 )
4. karrierist(X4 ) ∨ ¬chef(X4 , X5 ) ∨ ¬karrierist(X5 )
5. karrierist(a)
6. ¬wahnsinnig(a)
7 (4+5)
8 (3+7)
9 (1+8)
karrierist(X4 ) ∨ ¬chef(X4 , a)
¬chef(X4 , a) ∨ ehrgeizig(X4 )
wahnsinnig(a) ∨ ehrgeizig(f (a))
10 (2+9)
wahnsinnig(a)
11 (10+6)
Widerspruch
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-88 (132)
2.5.9 Beispiel 1 Resolution
Resolution und Unifikation
Bemerkung 2.8 (Unifikation)
Beachten Sie, dass beim Schritt 4+5 Unifikation erforderlich ist.
I
I
karrierist(X4 ) ∨ ¬chef(X4 , X5 ) ∨ ¬karrierist(X5 )
karrierist(a)
X5 muss zu a werden.
Die Resolvente ist dann folglich
karrierist(X4 ) ∨ ¬chef(X4 , a)
und nicht karrierist(X4 ) ∨ ¬chef(X4 , X5 ). Die Originalklausel 4 bleibt
aber erhalten. X5 wird nur temporär durch a ersetzt.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-89 (133)
2.5.10 Beispiel 2 Resolution
Beispiel Resolution
Wir betrachten die Aussagen:
1. Einige Künstler besuchen die Kunstausstellungen regelmäßig.
2. Kein Künstler besucht eine uninteressante Kunstausstellung.
3. Die Kunstausstellungen von Anne werden von allen Künstlern
regelmäßig besucht.
Wir möchten beweisen, dass keine Kunstausstellung von Anne
uninteressant ist.
Zunächst müssen wir uns überlegen, welche Prädikate wir brauchen.
kunst_ex(X,Y) . . . X ist eine Kunstausstellung, Veranstalter Y.
besucht(X,Y) . . . X besucht Y.
kuenstler(X) . . . X ist ein Künstler.
interessant(X) . . . X ist interessant.
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-90 (134)
2.5.10 Beispiel 2 Resolution
Beispiel Resolution – Formeln
Nun wandeln wir diese Aussagen in prädikatenlogische Formeln um:
1. Einige Künstler besuchen die Kunstausstellungen regelmäßig.
∃X kuenstler (X ) ∧ (∀Y , Z kunst_ex (Y , Z ) → besucht (X , Y ))
2. Kein Künstler besucht eine uninteressante, die uninteressant ist.
¬(∃X ∃Y ∃Z kuenstler (X ) ∧ kunst_ex (Y , Z )
∧ ¬interessant (Y ) ∧ besucht (X , Y ))
3. Die Kunstausstellungen von Anne werden von allen Künstlern
regelmäßig besucht.
∀X , Y kunst_ex (X , anne) ∧ kuenstler (Y ) → besucht (Y , X )
Ziel: Keine Kunstausstellung von Anne ist uninteressant.
¬(∃X kunst_ex (X , anne) ∧ ¬interessant (X ))
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-91 (135)
2.5.10 Beispiel 2 Resolution
Beispiel Resolution – KNF
Jetzt wandeln wir die Formeln in die KNF um:
1. ∃X kuenstler (X ) ∧ (∀Y , Z kunst_ex (Y , Z ) → besucht (X , Y ))
; kuenstler (a) ∧ (¬kunst_ex (Y , Z ) ∨ besucht (a, Y ))
2. ¬(∃X ∃Y ∃Z kuenstler (X ) ∧ kunst_ex (Y , Z )
∧ ¬interessant (Y ) ∧ besucht (X , Y )) ;
¬kuenstler (X ) ∨ ¬kunst_ex (Y , Z ) ∨ interessant (Y ) ∨ ¬besucht (X , Y )
3. ∀X , Y kunst_ex (X , anne) ∧ kuenstler (Y ) → besucht (Y , X ) ;
¬kunst_ex (X , anne) ∨ ¬kuenstler (Y ) ∨ besucht (Y , X )
Negiertes Ziel: ¬¬(∃X kunst_ex (X , anne) ∧ ¬interessant (X )) ;
kunst_ex (b, anne) ∧ ¬interessant (b)
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-92 (136)
2.5.10 Beispiel 2 Resolution
Beispiel Resolution – Klauseln und Resolution
1.1
kuenstler (a)
1.2
¬kunst_ex (X1 , X2 ) ∨ besucht (a, X1 )
2 ¬kuenstler (X3 ) ∨ ¬kunst_ex (X4 , X5 ) ∨ interessant (X4 ) ∨ ¬besucht (X3 , X4 )
3
Z.1
¬kunst_ex (X6 , anne) ∨ ¬kuenstler (X7 ) ∨ besucht (X7 , X6 )
Z.2
kunst_ex (b, anne)
¬interessant (b)
Nun können wir Resolution starten:
4 (Z.2+2)
5 (4+Z.1)
6 (5+1.1)
7 (1.2+Z.1)
8 (6+7)
¬kuenstler (X3 ) ∨ ¬kunst_ex (b, X5 ) ∨ ¬besucht (X3 , b)
¬kuenstler (X3 ) ∨ ¬besucht (X3 , b)
¬besucht (a, b)
besucht (a, b)
Widerspruch
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-93 (137)
2.5.11 Nachteile der Prädikatenlogik
Nachteile der Prädikatenlogik
I
2-Wertigkeit, keine vagen (unscharfen oder unsicheren)
Aussagen möglich
I
keine Informationen für Abarbeitung, z.B. Reihenfolge der
Regelanwendung
2 Darstellung und Verarbeitung von Wissen
2.5 Prädikatenlogik
Künstliche Intelligenz
Folie 2-94 (138)
2.5.11 Nachteile der Prädikatenlogik
Andere Logiken
I
Default-Logik
I
Closed world assumption
I
Sortierte Logik
I
Probabilistische Logik
I
Mehrwertige Logik
I
Modale Logik (Notwendigkeit, Möglichkeit, Wissen, Glauben)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.5 Prädikatenlogik
Folie 2-95 (139)
2.5.11 Nachteile der Prädikatenlogik
Logikbasierte WR und Regelverarbeitung
I
Logik macht strikte Trennung zwischen WR und Verarbeitung
I
Kombination von Logik und Abarbeitung:
z.B. Implikationen als Prozeduren: a ∧ b → c (Um c zu
beweisen, beweise a und dann b.)
I
kann aus Effizienzsicht sehr wichtig sein
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.6 Logikbasierte Wissensdarstellung und Regelverarbeitung
Folie 2-96 (140)
2.6.1 Prozedurale Aspekte der Wissensverarbeitung
Beispiel
Sei gegeben:
I
mensch(anton)
I
∀X kind(X ) → mensch(X )
Frage: ∃X mensch(X )
mensch(berta)
kind(clemens)
In welcher Reihenfolge bekommt man die 3 möglichen Antworten?
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.6 Logikbasierte Wissensdarstellung und Regelverarbeitung
Folie 2-97 (141)
2.6.2 Logische Programmierung und Prolog
Logische Programmierung und Prolog
I
Logische Programmierung basiert auf Horn-Klauseln.
I
Prolog als typischer Vertreter
I
Festgelegte Reihenfolge der Verarbeitung
I
Deklarative/Prozedurale Interpretation
I
Closed world assumption, Negation as failure
Beispiel 2.9 (Logische Programmierung)
sterblich(X) :- mensch(X).
mensch(sokrates).
Die Variable X ist allquantifiziert, d.h. obige Regel steht für:
∀X mensch(X) → sterblich(X)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.6 Logikbasierte Wissensdarstellung und Regelverarbeitung
Folie 2-98 (142)
2.6.2 Logische Programmierung und Prolog
Rückwärtsschließen in Prolog
In Prolog ist die Reihenfolge der Verarbeitung definiert. Sei z.B.
gegeben:
a :- b,c.
;
c :- d.
d.
b.
Klare Reihenfolge in der Abarbeitung.
Fragt man nach ?- a., so wird beginnend am Ziel bewiesen.
; Rückwärtsschließen
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.6 Logikbasierte Wissensdarstellung und Regelverarbeitung
Folie 2-99 (143)
2.6.2 Logische Programmierung und Prolog
Prolog und Prädikatenlogik – Abarbeitung
Seien folgende Regeln gegeben:
1
2
3
4
Prolog
?????-
a.
b,c.
c.
d.
Prolog
Prädikatenlogik
a :- b,c.
c :- d.
d.
b.
a ∨ ¬b ∨ ¬c
c ∨ ¬d
d
b
Regel
Prädikatenlogik
Resolution
1
4
2
3
¬a
¬b ∨ ¬c
¬c
¬d
2
5+1
6+4
7+2
8+3
2 Darstellung und Verarbeitung von Wissen
Nr.
5
6
7
8
9
Künstliche Intelligenz
2.6 Logikbasierte Wissensdarstellung und Regelverarbeitung
Folie 2-100 (144)
2.6.2 Logische Programmierung und Prolog
Ausdrucksstärke von Prolog
I
I
Nicht alle PL1-Formeln sind in Prolog darstellbar, z.B. a ∨ b
Prolog erlaubt sogar das Quantifizieren über Prädikate oder
Funktionen.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-101 (145)
Regelbasierte Wissensverarbeitung
Wissen wird häufig durch Regeln dargestellt. Im Gegensatz zur Logik
sind diese Regeln Zustands- und Aktions-orientiert.
Regeln können folgendes Aussehen haben:
WENN Bedingungen DANN Schlussfolgerung
WENN Bedingungen DANN Aktion
Sind die Bedingungen erfüllt, kann die Aktion ausgeführt bzw. die
Schlussfolgerung gezogen werden.
Man bezeichnet diese Regeln auch als Produktionsregeln.
Beispiel 2.10 (Produktionsregeln)
I
Wenn Kunde X die Reise Y bucht, bekomme ich die Provision Z.
I
Wenn der Tank leer ist, fülle ihn auf.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-102 (146)
Container-Beispiel
In einem Lager müssen Container umgeschlagen werden.
A
B
C
D
E
Lager 1
Lager 2
LKW
Waggon
Abb. 12: Container-Beispiel: Startzustand
Die Container sollen so umgestapelt werden, dass folgende Situation
entsteht:
D
A
C
Lager 1
Lager 2
B
E
LKW
Waggon
Abb. 13: Container-Beispiel: Zielzustand
2 Darstellung und Verarbeitung von Wissen
2.7 Regelbasierte Wissensverarbeitung
Künstliche Intelligenz
Folie 2-103 (147)
Regelbasierte Steuerung
Die Steuerung kann regelbasiert erfolgen. Eine mögliche Regel wäre:
WENN Container steht auf PlatzX UND Container steht oben
DANN Setze Container von PlatzX nach PlatzY.
Dies ist eine Aktionsregel.
2 Darstellung und Verarbeitung von Wissen
2.7 Regelbasierte Wissensverarbeitung
Aufbau von Regelsystemen
Ein Regel-System besteht aus zwei Komponenten:
1. Wissensbasis
2. Verarbeitungskomponente
Die Wissensbasis besteht aus:
1. Regelbasis
2. Fakten/Datenbasis
Künstliche Intelligenz
Folie 2-104 (148)
2 Darstellung und Verarbeitung von Wissen
2.7 Regelbasierte Wissensverarbeitung
Künstliche Intelligenz
Folie 2-105 (149)
Verarbeitung
I
Steuerungsstrategie zur Auswahl einer anwendbaren Regel
I
Regel-Anwender
Es gibt 2 Strategien
1. Vorwärtsverkettung
2. Rückwärtsverkettung
und 2 grundsätzliche Vorgehen
1. unwiderrufliche Strategien
2. versuchsweise Strategien (Backtracking)
2 Darstellung und Verarbeitung von Wissen
2.7 Regelbasierte Wissensverarbeitung
Künstliche Intelligenz
Folie 2-106 (150)
Regeln – Beispiel
Beispiel 2.11 (Geldautomat)
Geld1: WENN
Karte_gültig = ja
Kontostand_ausreichend = ja
PIN_korrekt = ja
Betrag =< Maximum
Versuch =< 3
DANN
Auszahlung = ja
Kartenrückgabe = ja
Ergänzen Sie weitere Regeln.
UND
UND
UND
UND
UND
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-107 (151)
2.7.1 Vorwärtsverkettung
Vorwärtsverkettung
Abb. 14: Vorwärtsverkettung
2 Darstellung und Verarbeitung von Wissen
2.7 Regelbasierte Wissensverarbeitung
Künstliche Intelligenz
Folie 2-108 (152)
2.7.1 Vorwärtsverkettung
Steuerung der Regelverarbeitung
I
Vorwärtsverkettung geht von Fakten aus.
I
Suche nach Regeln, deren Bedingungen komplett erfüllt sind.
Wie wählt man eine geeignete Regel aus?
I
Priorität (vom Benutzer vergebene Priorität)
I
Aktualität (Alter der Regel)
I
Spezifität (der Bedingungen)
Eine Regel R1 heißt spezifischer als eine Regel R2, falls R2 IMMER
anwendbar ist, falls R1 anwendbar ist.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-109 (153)
2.7.2 Rückwärtsverkettung
Rückwärtsverkettung
Vorwärtsverkettung
I
geht relativ ziellos vor,
I
das zu erreichende Ziel wird nicht beachtet.
Bei der Rückwärtsverkettung dagegen
I
geht man vom Ziel aus und
I
sucht nach einer Regel, die als Folgerung gerade die zu
erfüllende Aussage hat.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-110 (154)
2.7.2 Rückwärtsverkettung
Rückwärtsverkettung
FUNCTION GUELTIG(Hypothese)
IF Hypothese in Faktenbasis
OR RueckVerkettung(Hypothese)
THEN Hypothese zu Fakten hinzufuegen;
Return true;
ELSE Return false;
ENDIF;
END
FUNCTION RueckVerkettung(Hypothese)
IF Ex. eine Regel: WENN Bed DANN Hypothese
AND
FORALL B aus Bed: GUELTIG(B)
THEN Return true;
ELSE Return false;
ENDIF;
END
Abb. 15: Rückwärtsschließen
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-111 (155)
2.7.2 Rückwärtsverkettung
Regeln – Beispiel
Beispiel 2.12 (Vorwärts- und Rückwärtsverkettung)
Betrachten wir folgende Wissensbasis:
WENN a UND b UND c DANN f
WENN a
DANN b
WENN b UND f
DANN g
Die Faktenbasis sieht zu Beginn wie folgt aus:
(1)
(2)
(3)
a
c
Vorwärtsverkettung geht wie folgt vor:
Iteration
1
2
3
Anwendbare Regeln
2
1 und 2
1, 2, 3
2 Darstellung und Verarbeitung von Wissen
Neue Faktenbasis
a, c, b
a, c, b, f
a, c, b, f, g
Künstliche Intelligenz
2.7 Regelbasierte Wissensverarbeitung
Folie 2-112 (156)
2.7.2 Rückwärtsverkettung
Regeln – Beispiel
Beispiel 2.12 cont.
WENN a UND b UND c DANN f (1)
DANN b (2)
Wissensbasis: WENN a
WENN b UND f
DANN g (3)
Faktenbasis:
a
c
Wir möchten g beweisen. Rückwärtsverkettung geht wie folgt vor:
Schritt
1
2
3
4
5
6
7
Ziel
g
b
a
f
a
b
c
Anwendbare Regeln
3
2
in Faktenbasis
1
in Faktenbasis
schon beweisen
in Faktenbasis
Noch zu beweisen
b, f
a, f
f
a, b, c
b, c
c
2 Darstellung und Verarbeitung von Wissen
2.8 Semantische Netze
Künstliche Intelligenz
Folie 2-113 (157)
Semantische Netze
I
Wissen wird durch Netze repräsentiert.
I
SN sind eine deklarative Repräsentationsform.
I
SN sind gerichtete Graphen.
I
Die Knoten sind Objekte (bzw. Klassen von Objekten).
I
Die Kanten sind 2-stellige Relationen zwischen den
Objekten/Klassen.
I
SN gehen auf Ross Quillian zurück (60er Jahre).
2 Darstellung und Verarbeitung von Wissen
2.8 Semantische Netze
Semantische Netze
Spezielle Relationen sind:
I
ist_ein . . . entspricht der Teilmengenbeziehung
I
Instanz_von . . . entspricht der Elementbeziehung
Alle anderen Kanten sind „normale“ 2-stellige Relationen (vgl.
Datenbanken).
Künstliche Intelligenz
Folie 2-114 (158)
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.8 Semantische Netze
Folie 2-115 (159)
Semantische Netze
hat−beine
Säugetier
4
Ist_ein
hat−beine
Mensch
2
Ist_ein
liebt
Frau
Musik
Instanz_von
Anne
Größe
162
Abb. 16: Semantisches Netz
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.8 Semantische Netze
Folie 2-116 (160)
Semantische Netze
I
Relationen dürfen nur 2-stellig sein.
I
Gibt es also Probleme, falls eine Relation mehrstellig ist? NEIN!
Aktion
Ist_ein
Instanz_von
Petra
Agent
Buch
Geben
Ereignis17
Instanz_von
Objekt
Empfänger
Anne
Abb. 17: Mehrstellige Prädikate mit SN
Die Firma
2 Darstellung und Verarbeitung von Wissen
2.8 Semantische Netze
Künstliche Intelligenz
Folie 2-117 (161)
Semantische Netze
Abb. 18: Semantisches Netz – Deutsche Unternehmen
2 Darstellung und Verarbeitung von Wissen
2.8 Semantische Netze
Künstliche Intelligenz
Folie 2-118 (162)
Semantische Netze und Ontologien
I
Ontologie . . . explizite Spezifikation einer Konzeptualisierung
(Gruber)
I
SN häufig zur Darstellung von Ontologien genutzt.
I
Beispiele:
I
I
allgemeines Wissen: Wordnet (semantisches Lexikon)
wordnet.princeton.edu
medizinisches Wissen: UMLS (Unified Medical Language System)
www.nlm.nih.gov/research/umls
I
Beschreibungssprachen, z.B. Web Ontology Language (OWL)
als Ontologiesprache
www.w3.org/TR/owl2-overview
I
Ein gutes Buch: [Heiner Stuckenschmidt 2011].
2 Darstellung und Verarbeitung von Wissen
2.8 Semantische Netze
Künstliche Intelligenz
Folie 2-119 (163)
Weitere Anwendungen von Semantischen Netzen
I
Semantische Weiterentwicklungen des WWW
I
Semantic Wiki
I
...
2 Darstellung und Verarbeitung von Wissen
2.9 Frames
Künstliche Intelligenz
Folie 2-120 (164)
Objektorientierte WR und Frames
I
FRAMES wurden 1975 von MINSKY eingeführt.
I
Konzept der Frames: 20er/30er Jahre (Psychologie)
I
Idee: Mensch speichert bestimmte Schemata
I
hierarchisch geordnet
I
Eigenschaften durch die Hierarchie vererbbar
2 Darstellung und Verarbeitung von Wissen
2.9 Frames
Künstliche Intelligenz
Folie 2-121 (165)
Frames
Fortbewegungsmittel
ist-ein
: Gegenstand
Typ
: Wertebereich = (Land,Luft,Wasser)
Auto
ist-ein
: Fortbewegungsmittel
Raeder
: Default = 4
Marke
: Wertebereich=(BMW,Mercedes,Trabant)
Motor
: Wertebereich=(2Takt,4Takt,Diesel)
Karosserie: Wertebereich = (Metall, Plaste)
Typ
: Land
SB-P 5774
Instanz-von : Auto
Marke
: Trabant
Motor
: 2Takt
Karosserie : Plaste
2 Darstellung und Verarbeitung von Wissen
2.9 Frames
Folie 2-122 (166)
Struktur von Frames
I
Frame-Name
I
Oberkonzepte / Unterkonzepte
I
Slotname1 :
I
I
I
I
I
Künstliche Intelligenz
Slotwert
Aspektname1 = Aspektwert1
...
Aspektnamen = Aspektwertn
... Slotnamek ...
2 Darstellung und Verarbeitung von Wissen
2.9 Frames
Künstliche Intelligenz
Folie 2-123 (167)
Beispiel
Frames über Zimmer können wie folgt aussehen.
Zimmer
ist-ein
: Raum
Unterkonzepte : Wohnzimmer, Kinderzimmer, Arbeitszimmer
Wand
: Mauer
Zahl
Default 4, Restriktion > 2
Material Beton, Stein, Holz, Gips
Fussboden
: 1
Ausstattung
: Moebel
Wohnzimmer
ist-ein
: Zimmer
Moebel
: Stuhl, Tisch, Sessel, Couch
Blaues Zimmer
Instanz-von
: Zimmer
Stuhl
: Biedermeier,
Zahl 1
2 Darstellung und Verarbeitung von Wissen
2.9 Frames
Künstliche Intelligenz
Folie 2-124 (168)
Konzept der Frames
I
Klassen und Objekte
I
Hierarchie durch Unterklassen, Instanzen, Unterobjekte
I
Eigenschaften von Objekten (Attribute)
I
Attributen kann man bestimmte Aspekte zuordnen
I
Wert
Default-Wert
Wertebereich-Restriktionen
I
...
I
I
I
Methoden für z.B. Lese-/Schreib-Zugriff
I
Vererbung von Attributen innerhalb der Hierarchie
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.9 Frames
Folie 2-125 (169)
Vererbung – Algorithmus
Um auf einen Wert eines Attributes eines Objektes / einer Klasse
zuzugreifen, wird folgender Algorithmus verwendet:
1. Finde das Objekt O in der Wissensbasis
2. Hat das Attribut von O einen Wert, gib ihn zurück
3. sonst: Prüfe, ob O eine Instanz ist. Falls ja: Gehe zum
übergeordneten Objekt/Klasse und suche dort den Wert
4. sonst: Prüfe, ob O eine Unterklasse ist. Falls ja, gehe zur
Oberklasse und suche dort den Wert
5. sonst: kein Wert vorhanden
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.9 Frames
Folie 2-126 (170)
Vererbung
Tier
kann fliegen
Vogel
Fisch
kann nicht fliegen
Spatz
Strauss
Tweety
Abb. 19: Vererbung
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.9 Frames
Folie 2-127 (171)
Probleme
I
Was passiert, wenn ein Objekt mehrere Oberobjekte/-klassen
hat?
I
Wie löst man Widersprüche in der Vererbung (Karo-Problem)?
Sei Clyde ein Zirkuselefant. Er gehört zu 2 Klassen: Elefant und
Zirkustier. Elefanten sind groß, Zirkustiere jedoch klein.
Mensch
Pazifist
Quäker
kein Pazifist
Republikaner
Nixon
Abb. 20: Vererbung – Probleme
2 Darstellung und Verarbeitung von Wissen
2.10 Prozedurale Darstellung
Künstliche Intelligenz
Folie 2-128 (172)
Prozedurale Darstellung
Wissen wird prozedural dargestellt, z.B. durch eine feste Abfolge von
Aktionen.
Nachteile der prozeduralen Repräsentation:
I
i.allg. kein Trial and Error
I
nur anwendbar, wenn klare Handlungsfolge vorliegt
2 Darstellung und Verarbeitung von Wissen
2.11 Weitere Darstellungsformen
Künstliche Intelligenz
Folie 2-129 (173)
Weitere Darstellungsformen
Weitere WR-Formalismen sind:
I
Analoge Repräsentation (z.B. Landkarten)
I
andere Logiken, z.B. Fuzzy-Logik
2 Darstellung und Verarbeitung von Wissen
2.12 Zusammenfassung (WR/WV)
Künstliche Intelligenz
Folie 2-130 (174)
Das sollten Sie wissen . . .
Zusammenfassung 2.9 (WR/WV)
I
Grundprinzip explizite Repräsentation
I
Problemlösen mit KI
I
Formen der WR und WV
I
PL1 und Resolution
I
Regelverarbeitung (WENN-DANN-Regeln Produktionsregeln)
I
SN / Frames, Vererbung
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.13 Aufgaben
Folie 2-131 (175)
Aufgaben – WRWV
Aufgabe 2.1 (Übersetzen in PL1)
Übersetzen Sie die Aussagen in die prädikatenlogische Sprache:
I
Wenn die Sonne scheint, regnet es nicht und umgekehrt.
I
Peter bucht ein Urlaubsziel nur dann, wenn es dort einen
Swimming Pool gibt.
I
Lutz geht zu den Heimspielen von Hansa, aber nur, wenn nicht
gegen St. Pauli gespielt wird.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.13 Aufgaben
Folie 2-132 (176)
Aufgaben – WRWV
Aufgabe 2.2 (Beweisen)
Beweisen Sie (ohne Resolution),
I
dass Marcus nicht loyal gegenüber Caesar war
I
dass er Caesar hasste,
und
und zwar mittels
I
Rückwärtsschließen (mit dem Ziel beginnend)
I
Vorwärtsschließen (mit dem gegebenen Wissen beginnend)
Wo sehen Sie Vor- bzw. Nachteile beider Strategien? Gehen Sie dabei
von den Originalformeln aus.
2 Darstellung und Verarbeitung von Wissen
Künstliche Intelligenz
2.13 Aufgaben
Folie 2-133 (177)
Aufgaben – WRWV
Aufgabe 2.3 (Resolution)
Wie beweist man die Äquivalenz von 2 Formeln A und B?
I
Welches Ziel muss man formulieren und anschließend beweisen?
I
Prüfen Sie Ihr Konzept anhand des Beweises, dass
∀X (p(X ) ∧ q (X )) und
äquivalent sind?
¬∃X (¬p(X ) ∨ ¬q (X ))
Beweisen Sie Ihre Vermutung nur mittels Resolution, also OHNE die
Negation sofort über den Ex.-Operator zu ziehen.
(Hinweis: Man sieht natürlich sehr schnell, dass beide äquivalent sind.
Hier soll der Beweis jedoch mittels Resolution erfolgen.
Also Ziel aufstellen und mit Resolution beweisen.)
2 Darstellung und Verarbeitung von Wissen
2.13 Aufgaben
Künstliche Intelligenz
Folie 2-134 (178)
Aufgaben – WRWV
Aufgabe 2.4 (Produktionsregeln)
Lösen Sie das Wasser-Problem (vgl. Kapitel Suche) mit Hilfe von
Wenn-Dann-Regeln (Produktionsregeln).
Aufgabe 2.5 (Produktionsregeln und Prolog)
Betrachten Sie PROLOG als Regel-verarbeitendes System (im Sinne
der behandelten WENN-DANN-Aktionsregeln) und erläutern Sie die
Abarbeitung in PROLOG an einem Beispiel!
Aufgabe 2.6 (Semantisches Netz)
Stellen Sie als Semantisches Netz dar, dass Marcus ein Pompejer war
und dass jeder Pompejer auch ein Römer war.
2 Darstellung und Verarbeitung von Wissen
2.13 Aufgaben
Künstliche Intelligenz
Folie 2-135 (179)
Aufgaben – WRWV
Aufgabe 2.7 (Frames)
Stellen Sie in Form von Frames einen Ausschnitt der
Lebewesen-Hierarchie dar, also z.B.
I
dass Vögel und Säugetiere Lebewesen sind,
I
dass Vögel fliegen,
I
dass Säugetiere laufen,
I
dass ein Strauß ein Vogel ist und läuft etc.
Benutzen Sie hier die Vererbung von Eigenschaften von
Oberkonzepten auf Unterkonzepte.
2 Darstellung und Verarbeitung von Wissen
2.13 Aufgaben
Aufgabe 2.8 (PL1)
Erläutern Sie den Unterschied zwischen den Formeln:
∃X (p(X ) ∧ q (X )) und ∃X p(X ) ∧ ∃X q (X )
Aufgabe 2.9 (Semantisches Netz)
Übersetzen Sie das Semantische Netz aus Abb. 16 in die
Prädikatenlogik.
Aufgabe 2.10 (Regelsystem)
Entwickeln Sie ein Regelsystem zur Steuerung einer Ampel.
Künstliche Intelligenz
Folie 2-136 (180)
3 Vages Wissen
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
3 Vages Wissen
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 3
Vages Wissen
Unsicheres Wissen
Unscharfes Wissen und Fuzzy-Mengen
Rechnen mit Fuzzy-Mengen
Fuzzy-Logik
Fuzzy-Logik und Prolog
Fuzzy-Regler
Regelung eines inversen Pendels
Ergänzungen
Zusammenfassung (Fuzzy)
Aufgaben (Fuzzy)
3 Vages Wissen
Künstliche Intelligenz
Folie 3-1 (183)
Vages Wissen
No real problem has a solution.
The Smith’s Law, Murphy’s Law
3 Vages Wissen
Künstliche Intelligenz
Folie 3-2 (184)
Vages Wissen
Häufig: vage Aussagen
I
unscharfe Begriffen (groß, profitabel, teuer, effizient) oder
I
unsichere Aussagen (Morgen regnet es.).
Nicht mit gängigen Methoden modellierbar.
Denn: Nicht eindeutig klar, ob solche Aussagen wahr oder falsch.
3 Vages Wissen
Künstliche Intelligenz
Folie 3-3 (185)
Vages Wissen
I
Ziel: auch mit vagen Begriffen Entscheidungen treffen.
I
Z.B. Autokauf: Kriterien wie billig, familien-, umweltfreundlich.
I
Beim Autokauf müssen wir die Angebote irgendwie bewerten (um
das beste Angebot zu finden).
I
Wahr/falsch geht nicht, da unsere Angebote nicht eindeutig billig
bzw. nicht billig sind.
I
Deshalb lassen wir auch Bewertungen für billig von z.B. 80% zu.
I
Wie verbinden wir z.B. 80% (billig) mit 70% (fam.freundlich)?
3 Vages Wissen
Künstliche Intelligenz
Folie 3-4 (186)
Vages Wissen
I
Ebenso möchten wir ähnlich wie mit Resolution Schlüsse
ziehen.
∀X patient(X ) ∧ hohesfieber(X ) → medikament(X , paracetamol)
Ist 38◦ hohes Fieber? Nicht zu 100%, eher 50%.
I
Wir lösen uns von wahr/falsch, möchten jedoch weiter mit dieser
Regel rechnen.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-5 (187)
Unsicheres Wissen
Es werden unsichere Aussagen wie
I
Es regnet morgen.
I
Der Kurs des Euro wird steigen.
betrachtet.
1. Aussagen können nur wahr oder falsch sein.
2. Zum jetzigen Zeitpunkt: keine Aussage möglich, ob wahr / falsch.
Konsequenzen:
I
Die zweiwertige Logik ist nicht anwendbar.
I
Man muss Wahrheitswerte zwischen 0 und 1 zulassen.
I
Üblicher Ansatz: Verwenden von Wahrscheinlichkeiten.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-6 (188)
Wahrscheinlichkeit
Eine Wahrscheinlichkeit drückt aus, mit welchem Maß man
annehmen kann, dass ein Ereignis eintritt.
Beispiel 3.1 (Wahrscheinlichkeit)
Das Ereignis
Es wird eine ungerade Zahl gewürfelt.
hat eine Wahrscheinlichkeit von 0,5.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-7 (189)
Grundlagen der Wahrscheinlichkeitsrechnung
Man kann Wahrscheinlichkeiten unterschiedlich interpretieren:
1. Maß für eine Häufigkeit von Ereignissen
2. subjektives Maß für das Eintreffen von Ereignissen
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-8 (190)
Grundbegriffe
I
I
I
Sei mit Ω der Ereignisraum bezeichnet.
(Beim Würfeln: Ω = {1, 2, 3, 4, 5, 6})
Elementarereignisse: 1, 2, 3, 4, 5, 6
Jedes Ereignis darstellbar als: A ⊆ Ω.
Beispiel 3.2 (Ereignis)
Das Ereignis: Es wird eine gerade Zahl gewürfelt entspricht:
A = {2, 4, 6}.
Eine Aussage A heißt wahr, falls das tatsächlich eingetretene Ereignis
X in A enthalten ist:
X ∈A
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-9 (191)
Grundbegriffe
I
Menge aller möglichen Aussagen: Menge aller Teilmengen von
Ω: 2Ω .
I
Ω ist das sichere Ereignis (da alle Elementarereignisse in Ω
enthalten sind).
I
0/ ist das unmögliche Ereignis, da die leere Menge kein
Elementarereignis enthält.
I
Ereignisse kann man verknüpfen. Sind X und Y Ereignisse über
dem Ereignisraum Ω, so sind auch:
I X ∩Y
I X ∪ Y und
I
X c (Mengenkomplement)
Ereignisse über Ω.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-10 (192)
Ereignisse und Logik
I
I
I
Das Ereignis X ∩ Y tritt genau dann ein, wenn X eintritt UND
auch Y eintritt. Dies entspricht folglich der Aussage X ∧ Y .
Analog entspricht das Ereignis X ∪ Y der Aussage X ∨ Y .
Die Komplementbildung X c entspricht der Negation ¬X .
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-11 (193)
Erwartungswert
Diesen Ereignissen sollen Zahlen (∈ [0, 1]) zugewiesen werden, die
einen Erwartungswert für deren Eintreffen darstellen, eine
Wahrscheinlichkeit.
Definition 3.1 (Wahrscheinlichkeitsfunktion)
Sei Ω ein endlicher Ereignisraum. Eine Funktion P : 2Ω → [0, 1] heißt
Wahrscheinlichkeitsfunktion, wenn gilt:
I
P (Ω) = 1
I
P (X ∪ Y ) = P (X ) + P (Y ) für X , Y ⊆ Ω, wobei X ∩ Y = 0/
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-12 (194)
Eigenschaften einer Wahrscheinlichkeitsfunktion
Für beliebige X , Y ⊆ Ω gilt:
unmögliches Ereignis
Monotonie
Subtraktivität
Subadditivität
Additivität
Komplement
/ =0
P (0)
X ⊆ Y → P (X ) ≤ P (Y )
X ⊆ Y → P (Y ∩ X c ) = P (Y ) − P (X )
P (X ∪ Y ) ≤ P (X ) + P (Y )
P (X ∪ Y ) = P (X ) + P (Y ) − P (X ∩ Y )
P (X c ) = 1 − P (X )
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-13 (195)
3.1.1 Bedingte Wahrscheinlichkeiten
Bedingte Wahrscheinlichkeiten
Meistens hat man abhängige Aussagen:
Wenn die Telekom eine positive Jahresbilanz meldet, dann steigt die
Telekom-Aktie um 5%.
Was bedeutet ein Wert von 0,8 für diese Aussage?
Betrachtet man diese Aussage als logische Implikation:
A → B
so entspricht dies der Aussage:
¬A ∨ B
Folglich bedeutet der Wert 0,8, dass in 80% der Fälle die Telekom
keine positive Jahresbilanz vermeldet oder die Aktie um 5% steigt.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-14 (196)
3.1.1 Bedingte Wahrscheinlichkeiten
2. Interpretation
Wenn eine positive Bilanz gemeldet wird, dann steigt die Aktie mit
einer Wahrscheinlichkeit von 0,8 um 5%.
Dies bezeichnet man als bedingte Wahrscheinlichkeit.
Unterschied ist signifikant:
1. Betrachten den Fall: 7 x nicht positive Bilanz, 3 x positive Bilanz
2. Aktie steigt in einem von diesen 3 Fällen um 5%.
Resultat:
I
Erste Interpretation: 0,8 erfüllt (log. Implikation erfüllt in 8 von 10
Fällen)
I
Bedingte Wahrscheinlichkeit: 0,8 nicht erfüllt (Aktie stieg nur in 1
von 3 Fällen)
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-15 (197)
3.1.1 Bedingte Wahrscheinlichkeiten
Bedingte Wahrscheinlichkeit
Definition 3.2 (Bedingte Wahrscheinlichkeit)
Sei Y ein Ereignis mit P (Y ) > 0. Dann heißt
P (X |Y ) =
P (X ∩ Y )
P (Y )
bedingte Wahrscheinlichkeit von X unter der Bedingung Y . Falls
P (Y ) = 0, so ist die bedingte Wahrscheinlichkeit nicht definiert.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-16 (198)
3.1.1 Bedingte Wahrscheinlichkeiten
Bedingte Wahrscheinlichkeit
Beispiel 3.3 (Bedingte Wahrscheinlichkeit)
Welchen Wahrscheinlichkeitswert muss diese Aussage bekommen:
Wird eine gerade Zahl gewürfelt, so ist es eine 2.
Die Wahrscheinlichkeit für das Ereignis G = {2, 4, 6} beträgt:
P (G) = 0, 5.
Für das Ereignis Z = {2} gilt: P (Z ) = 16 .
Die bedingte Wahrscheinlichkeit beträgt: P (Z |G) = 13 .
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-17 (199)
3.1.2 Bayessche Formel
Bayessche Formel
Stellt man die Formel für die bedingte Wahrscheinlichkeit um, so erhält
man:
P (X ∩ Y ) = P (Y ) ∗ P (X |Y )
Betrachtet man die bedingte Wahrscheinlichkeit von Y bezüglich X , so
ergibt sich analog:
P (Y ∩ X ) = P (X ) ∗ P (Y |X )
Da der Mengendurchschnitt kommutativ ist, gilt:
P (Y ) ∗ P (X |Y ) = P (X ) ∗ P (Y |X )
Somit erhält man die Bayessche Formel:
P (X |Y ) =
P (Y |X ) ∗ P (X )
3 Vages Wissen
3.1 Unsicheres Wissen
P (Y )
Künstliche Intelligenz
Folie 3-18 (200)
3.1.2 Bayessche Formel
Bayessche Formel
Beispiel 3.4 (Bayessche Formel)
Seien diese Aussagen gegeben:
X: Der Motor braucht einen Ölwechsel: P (X ) = 0, 06.
Y: Der Motor des Autos macht seltsame Geräusche: P (Y ) = 0, 08.
Ein dringend erforderlicher Ölwechsel verursacht in 60% der Fälle
seltsame Geräusche des Motors: P (Y |X ) = 0, 6.
Bayessche Formel zur Berechnung, mit welcher Wahrscheinlichkeit
ein seltsames Motorgeräusch auf einen dringend erforderlichen
Ölwechsel schließen lässt:
P (Y |X )∗P (X )
0,06
P (X |Y ) =
= 0,60∗,08
= 0, 45
P (Y )
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-19 (201)
3.1.2 Bayessche Formel
Problem – 1
Häufig sind die wahrscheinlichkeitstheoretischen Voraussetzungen
nicht erfüllt bzw. prüfbar.
Beispiel 3.5 (Bayessche Formel)
Sei im Auto-Beispiel
P (Y ) = 0, 03
so ergäbe sich als bedingte Wahrscheinlichkeit:
P (X |Y ) = 1, 2
Die Ursache für diesen Fehler liegt in den bereits widersprüchlichen
subjektiven Werten.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
3.1.2 Bayessche Formel
Problem – 2
Betrachtet werden die Ereignisse:
Im ersten Wurf wird eine gerade Zahl gewürfelt.
Im zweiten Wurf wird eine ungerade Zahl gewürfelt.
Beide Ereignisse gleichzeitig ; 0,25 (0, 52 , da unabhängige
Ereignisse)
Betrachtet man dagegen die Ereignisse:
Im ersten Wurf wird eine gerade Zahl gewürfelt.
Im ersten Wurf wird eine ungerade Zahl gewürfelt.
Beide Ereignisse gleichzeitig ; 0 (Ereignisse nicht unabhängig)
Folie 3-20 (202)
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-21 (203)
3.1.2 Bayessche Formel
Bayessche Formel – Beispiel
Beispiel 3.6 (Bayessche Formel)
Marianne möchte sich eine neue Festplatte kaufen.
Marke
A
B
C
W., dass Mar.
Marke kauft
0,4
0,5
0,1
Falls Platte kaputt geht, wie
wahrscheinlich war es A?
W., dass Platte (im 1.
Jahr) kaputt geht
0,05
0,02
0,01
P (A|kaputt) =
P (kaputt|A)×P (A)
P (kaputt)
Die erforderlichen Einzelwahrscheinlichkeiten sehen wie folgt aus:
I
I
P (kaputt|A) = 0, 05
;
P (A) = 0, 4
P (kaputt) = 0, 4 ∗ 0, 05 + 0, 5 ∗ 0, 02 + 0, 1 ∗ 0, 01 = 0, 031
Damit erhalten wir: P (A|kaputt) =
0,05∗0,4
0,031
= 64, 51%
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-22 (204)
3.1.3 Sicherheitsfaktoren
Sicherheitsfaktoren
I
Meist keine Wahrscheinlichkeiten gegeben, sondern subjektive
Maßzahlen.
I
subjektive Maßzahl 6= Wahrscheinlichkeit
I
besser: Glaube oder Sicherheit
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-23 (205)
3.1.3 Sicherheitsfaktoren
Sicherheitsfaktoren
I
Sicherheitsfaktoren (engl. Certainty Factors, CF)
I
Quantitative Bewertung von Aussagen. [−1, 1]. Die Zahl -1
bedeutet falsch, 1 steht für wahr.
I
Die Sicherheitsfaktoren werden mit CF (H |E ) bezeichnet.
I
Bewertung der Sicherheit eines Ereignisses H basiert auf
Erfahrung (Evidenz): E
I
Ein Fakt Es stürmt (CF-Wert 0,8), wird in der Form
CF (Es stürmt|E ) = 0, 8
angegeben.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-24 (206)
3.1.3 Sicherheitsfaktoren
Sicherheitsfaktoren für Regeln
Betrachten wir folgendes Beispiel:
1
2
3
Es regnet.
Es stürmt.
Die Sonne scheint.
→
→
→
Es ist schlechtes Wetter.
Es ist schlechtes Wetter.
Es ist schlechtes Wetter.
0,9
0,7
-0,9
Die folgende Schreibweise ist eine andere Darstellung der Regel 1:
CF (Es ist schlechtes Wetter|Es regnet) = 0, 9
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-25 (207)
3.1.3 Sicherheitsfaktoren
Logische Verknüpfungen mit CF-Werten
I
Wie berechnet man die Verknüpfungen von CF-Werten mittels
Oder / Und / Negation?
I
Wie berechnet sich der CF-Wert für H in einer Implikation
X → H?
I
I
Sequentielle Verknüpfung von 2 Implikationen X → Y und
Y → H?
2 parallele Regeln für eine Hypothese (X → H und Y → H)?
Wir betrachten dazu einige Fälle.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-26 (208)
3.1.3 Sicherheitsfaktoren
Schließen mit Regeln – Fall 1
Weiß man, dass es regnet, kann man mit einer Sicherheit von 0,9
darauf schließen, dass schlechtes Wetter ist.
CF (Es regnet|E ) = 1
CF (Es ist schlechtes Wetter|Es regnet) = 0, 9
Es soll Es ist schlechtes Wetter geschlossen werden. Dies entspricht
im Prinzip dem Modus ponens:
A → B
A
B
CF (Es ist schlechtes Wetter|E ) =
= CF (Es regnet|E ) ∗ CF (Es ist schlechtes Wetter|Es regnet)
= 1 ∗ 0, 9 = 0, 9
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-27 (209)
3.1.3 Sicherheitsfaktoren
Schließen mit Regeln – Fall 2
Was kann man schließen, wenn zusätzlich bekannt ist, dass es
stürmt?
CF (Es stürmt|E ) = 1
Offensichtlich gibt es zwei Argumente, die dafür sprechen, dass
schlechtes Wetter ist. Seien
a = CF (Es ist schlechtes Wetter|Es regnet) = 0, 9
b = CF (Es ist schlechtes Wetter|Es stürmt) = 0, 7
und
dann ist
CF (Es ist schlechtes Wetter|(Es regnet ∧ Es stürmt)) =
a + b − a ∗ b = 0, 97.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
3.1.3 Sicherheitsfaktoren
Schließen mit Regeln – Fall 3
Es stürmt und die Sonne scheint.
I
einfache Addition der CF-Werte sinnvoll ?
I
Kombination des positiven und negativen Argumentes für
schlechtes Wetter
I
Resultat -0,2
Folie 3-28 (210)
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-29 (211)
3.1.3 Sicherheitsfaktoren
Schließen mit Regeln – Fall 4
Es stürmt und regnet, die Sonne scheint.
I
Analog Fall 2: positives Argument für schlechtes Wetter 0,97.
I
Gegenargument ergibt 0,9.
I
Resultat: 0,07, obwohl zwei Regeln dafür sprechen, nur eine
dagegen.
Als Verknüpfung für CF1 und CF2 wählt man deshalb in diesem Fall:
CF =
CF 1 + CF 2
1 − min{|CF 1|, |CF 2|}
Mit dieser Verknüpfung erhält man 0,7.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-30 (212)
3.1.3 Sicherheitsfaktoren
Mögliche Verknüpfungen
Aussagen können folgende Verknüpfungen enthalten:
¬
∧
∨
→
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-31 (213)
3.1.3 Sicherheitsfaktoren
Systematische Betrachtung
Regel 1:
Regel 2:
Regel 3:
X ∧ Y −→ H
M ∨ N −→ H
A −→ H
(0, 9)
(0, 7)
(−0, 9)
Diese CF-Werte seien bekannt:
CF
X
0,7
Y
1
M
-0,2
N
1
A
0,6
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-32 (214)
3.1.3 Sicherheitsfaktoren
Behandlung von ∧ und ∨
CF (a ∧ b|E ) = min(CF (a|E ), CF (b|E ))
CF (a ∨ b|E ) = max(CF (a|E ), CF (b|E ))
Es ergibt sich:
CF (X ∧ Y |E ) = 0, 7
CF (M ∨ N |E ) = 1
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-33 (215)
3.1.3 Sicherheitsfaktoren
Behandlung einer Regel – 1
Betrachtet man die Regel:
Regel: P −→ H (CF )
und sei CF (P |E ) gegeben, so berechnet sich der Sicherheitsfaktor
CF (H |E ) durch:
CF (H |E ) = CF (P |E ) ∗ CF (H |P )
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-34 (216)
3.1.3 Sicherheitsfaktoren
Behandlung einer Regel – 2
Man beachte, dass dies nur dann sinnvoll ist, wenn
CF (P |E ) ≥ 0 gilt. Ist der Wert negativ, so benötigt man eine Regel
der Form:
Regel: ¬P −→ H (CF )
Unter Beachtung der Gleichung:
CF (¬P |E ) = −CF (P |E )
erhält man:
CF (H |E ) = CF (¬P |E ) ∗ CF (H |¬P ) = −CF (P |E ) ∗ CF (H |¬P )
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-35 (217)
3.1.3 Sicherheitsfaktoren
Behandlung einer Regel – 3
Bemerkung 3.3
Der Schluss von P auf H entspricht dem Modus ponens.
Ist jedoch der
I
I
Sicherheitswert CF (P |E ) negativ, und ist
keine Regel für den komplementären Fall gegeben,
so ist die Anwendung des Modus ponens unsinnig. Man sollte den
CF-Wert CF (H |E ) dann auf Null setzen.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-36 (218)
3.1.3 Sicherheitsfaktoren
Unser Beispiel
In obigem Beispiel erhält man mit Regel 1:
CF (H1 |E1 ) = CF (H1 |X ∧ Y ) ∗ CF (X ∧ Y |E ) = 0, 63
Analog ergibt sich mit Regel 2 und 3:
CF (H2 |E2 ) = 0, 7
CF (H3 |E3 ) = −0, 54
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-37 (219)
3.1.3 Sicherheitsfaktoren
Verknüpfung mehrerer Regeln
Seien x = CF (H |E1 ) und y = CF (H |E2 ) die sich aus zwei Regeln
ergebenden Sicherheitsfaktoren. Dann berechnet sich der kombinierte
Sicherheitsfaktor durch:

x +y −x ∗y


 x +y +x ∗y
CF (H |E1 , E2 ) =
undefiniert



x +y
1−min(|x |,|y |)
falls x , y ≥ 0
falls x , y < 0
falls x ∗ y = −1
sonst
Die Verknüpfungsfunktion ist kommutativ und assoziativ, so dass eine
Reihenfolge der Anwendung keine Rolle spielt.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-38 (220)
3.1.3 Sicherheitsfaktoren
Unser Beispiel
CF (H1 |E1 )
CF (H2 |E2 )
CF (H3 |E3 )
CF (H1,2 |E1 , E2 )
CF (H |E1 , E2 , E3 )
= 0, 63
= 0, 7
= −0, 54
= 0, 63 + 0, 7 − 0, 63 ∗ 0, 7 = 0, 889
−0,54
= 0,889
= 0, 759
1−0,54
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-39 (221)
3.1.3 Sicherheitsfaktoren
Systematische Betrachtung
Verknüpfung
Und
Oder
Negation
Regel
2 CFs
CF-Wert
min(CF (a|E ), CF (b|E ))
max(CF (a|E ), CF (b|E ))
−CF (P |E )
CF (P |E ) ∗ CF (H |P )
CF1 + CF2 − CF1 ∗ CF2
CF1 + CF2 + CF1 ∗ CF2
CF1 +CF2
1−min(|CF1 |,|CF2 |)
undefiniert
Bedingung
CF1 , CF2 ≥ 0
CF1 , CF2 < 0
CF1 ∗ CF2 < 0, 6= −1
CF1 ∗ CF2 = −1
Tabelle 7: Verknüpfungen von CF-Werten
3 Vages Wissen
3.1 Unsicheres Wissen
Künstliche Intelligenz
Folie 3-40 (222)
3.1.3 Sicherheitsfaktoren
Measure of Belief
Wie bekommt man die CF-Werte für die Fakten wie Es stürmt oder Es
regnet?
Analog zu CF: Measure of Belief/Disbelief MB/MD
Beide Werte müssen im Intervall [0,1] liegen.
3 Vages Wissen
Künstliche Intelligenz
3.1 Unsicheres Wissen
Folie 3-41 (223)
3.1.3 Sicherheitsfaktoren
Measure of Belief
Beispiel 3.7 (Measure of Belief)
Liegt Rostock an der Ostsee?
Rostock ist eine Hafenstadt. Dies spricht uneingeschränkt dafür:
MB (Rostock liegt an der Ostsee|E ) = 1, 0
Dagegen spricht, dass man vom Stadtzentrum etwa 15 km
zurücklegen muss, um an die Ostsee zu kommen.
MD (Rostock liegt an der Ostsee|E ) = 0, 2
Differenzbildung:
CF (H |E ) = MB (H |E ) − MD (H |E ) = 1, 0 − 0, 2 = 0, 8
3 Vages Wissen
Künstliche Intelligenz
3.2 Unscharfes Wissen und Fuzzy-Mengen
Unscharfes Wissen und Fuzzy-Mengen
Im folgenden: unscharfe Aussagen wie groß, intelligent, reich,
profitabel
Eigenschaften werden normalerweise beschrieben durch
I
Mengen / Teilmengen (z.B. Relationen)
I
Prädikate (Wahrheitswerte)
I
charakteristische Funktionen
Folie 3-42 (224)
3 Vages Wissen
Künstliche Intelligenz
3.2 Unscharfes Wissen und Fuzzy-Mengen
Folie 3-43 (225)
Fuzzy-Mengen
1 6 s
0
0
s
s
s
s
s
5
s
s
s
s 10
Abb. 21: Charakteristische Funktion – gerade natürliche Zahlen
I
Mengen und Prädikate sind ungeeignet, um unscharfe Aussagen
darzustellen.
I
Dazu eignen sich die Fuzzy-Mengen.
I
Man bildet nicht mehr auf {0, 1} ab, sondern auf [0,1].
3 Vages Wissen
Künstliche Intelligenz
3.2 Unscharfes Wissen und Fuzzy-Mengen
Folie 3-44 (226)
Fuzzy-Mengen
Folgendes Bild stellt die Zugehörigkeit von Personen zur Menge groß
dar, und zwar in Abhängigkeit von ihrer Körpergröße.
Abb. 22: Charakteristische Funktion für groß
3 Vages Wissen
Künstliche Intelligenz
3.2 Unscharfes Wissen und Fuzzy-Mengen
Folie 3-45 (227)
Fuzzy-Menge – Definition
Definition 3.4 (Fuzzy-Menge)
Eine Fuzzy-Menge Z über einer Referenzmenge X ist eine Teilmenge
aus X × [0, 1]. Z wird beschrieben durch die Zugehörigkeitsfunktion:
µ Z : X → [ 0, 1]
z = (x , s) ist in der Fuzzy-Menge Z genau dann enthalten, wenn gilt:
µZ (x ) = s
F (X ) ist die Menge aller Fuzzy-Mengen über X.
3 Vages Wissen
Künstliche Intelligenz
3.2 Unscharfes Wissen und Fuzzy-Mengen
Folie 3-46 (228)
Diskrete Funktionen
Man kann sich von der Abbildung auf das Intervall [0, 1] lösen und
wieder endliche Mengen zulassen. Z.B.:
unmöglich < höchst unwahrscheinlich < sehr selten < selten <
unwahrscheinlich < manchmal < Chance ist 50:50 < wahrscheinlich
< oft < meistens < fast immer < fast sicher < sicher
I
Totale Ordnung der Bewertungsgrößen
I
Im folgenden diskrete Funktionen nicht betrachtet
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-47 (229)
Rechnen mit Fuzzy-Mengen
Will man mit Fuzzy-Mengen rechnen, braucht man eine endliche
Repräsentation der Fuzzy-Mengen, z.B.
I
Referenzmenge X ist endlich.
I
Die Funktion µ ist als analytischer Ausdruck (parameterabhängig)
bekannt.
Ein typischer Vertreter sind die stückweise linearen Funktionen.
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-48 (230)
Teilmenge
Wie definiert man typische Beziehungen von Mengen zwischen
Fuzzy-Mengen?
Definition 3.5 (Teilmenge)
Seien µ und µ0 zwei Fuzzy-Mengen von X.
µ heißt Teilmenge von µ0 (⊂)
gdw.
für alle x ∈ X gilt: µ(x ) ≤ µ0 (x ).
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-49 (231)
Teilmenge
Beispiel 3.8 (Fuzzy-Teilmengen)
1
6
AAAA
AAA
AAA
A
0.5
0
0
6
1
1
2
B
AAAB
AAB
BAA
B
0.5
3
Abb. 23: Teilmenge
0
0
und
1
2
3
keine Teilmenge
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-50 (232)
Durchschnitt
Und wie verknüpft man Fuzzy-Mengen?
Berechnen einer Funktion: S : [0, 1] × [0, 1] → [0, 1], so dass gilt:
(µ ∩ µ0 )(x ) = S (µ(x ), µ0 (x ))
Welche Eigenschaften muss S erfüllen?
I
S (a, 1) = a
I
Monotonie: a ≤ b → S (a, c ) ≤ S (b, c )
I
I
Kommutativität S (a, b) = S (b, a)
Assoziativität S (a, S (b, c )) = S (S (a, b), c )
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-51 (233)
Durchschnitt
Folgende Funktionen erfüllen die Forderungen:
Variante 1:
min( a , b )
Variante 2:
max( 0 , a+b-1 )
Variante 3:
a×b
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-52 (234)
Durchschnitt
Abb. 24: Charakteristische Funktion – klein UND groß (Variante 1)
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-53 (235)
Vereinigung
Berechnen einer Funktion V : [0, 1] × [0, 1] → [0, 1], so dass gilt:
(µ ∪ µ0 )(x ) = V (µ(x ), µ0 (x ))
Welche Eigenschaften muss V erfüllen?
I
V (a, 0) = a
I
Monotonie: a ≤ b → V (a, c ) ≤ V (b, c )
I
I
Kommutativität
Assoziativität
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Vereinigung
Folgende Funktionen erfüllen die Forderungen:
Variante 1:
max( a , b )
Variante 2:
min( 1 , a+b )
Variante 3:
a+b−a×b
Folie 3-54 (236)
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-55 (237)
Vereinigung
Abb. 25: Charakteristische Funktion – klein ODER groß (Variante 1)
3 Vages Wissen
Künstliche Intelligenz
3.3 Rechnen mit Fuzzy-Mengen
Folie 3-56 (238)
Komplement einer Fuzzy-Menge
Analog kann man die Komplementbildung definieren als:
µZ c (x ) = 1 − µZ (x )
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-57 (239)
Fuzzy-Logik
Für die Disjunktion, Konjunktion und Negation haben wir bereits
Funktionen kennengelernt:
I
I
I
Konjunktion ∧ : Mengendurchschnitt
Disjunktion ∨ : Mengenvereinigung
Negation ¬ :
Differenz (Mengenkomplement)
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-58 (240)
Achtung !
Welche der Varianten 1/2/3 wir benutzen, ist uns überlassen.
Funktionen für Durchschnitt und Vereinigung sollten zueinander
passen.
Wählt man
I
für den Durchschnitt das Minimum,
I
für die Vereinigung das Maximum,
so gilt auch in der Fuzzy-Logik die Aussage:
A ∨ (A ∧ B ) = A
Denn es gilt:
µA ∨ (A ∧ B) (x ) = max(µA (x ), min(µA (x ), µB (x ))) = µA (x )
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-59 (241)
Implikation
Die Implikation kann man z.B. folgendermaßen definieren:
µA → B (x )
min(1, 1 − µA (x ) + µB (x ))
max(1 − µA (x ), µB (x ))
max(1 − µA (x ), min(µA (x ), µB (x )))
1 − µA (x ) + µA (x ) × µB (x )
Name
Lukasiewicz
Kleene-Dienes
Zadeh
Reichenbach
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-60 (242)
Woher kommen die Implikations-Varianten?
Definitionen für die Implikationen hängen von den Varianten 1/2/3 für
∧ und ∨ sowie von der Darstellung der Implikation ab.
Variante
Lukasiewicz
Kleene-Dienes
Zadeh
Reichenbach
Darstellung
für A → B
¬A ∨ B
Variante
für ∧/∨
2
¬A ∨ B
1
¬A ∨
(A ∧ B )
¬A ∨
(A ∧ B )
1
3
Formel
µA → B (x ) =
= µ¬A ∨ B (x )
= min(1, (1 − µA (x )) + µB (x ))
= µ¬A ∨ B (x )
= max(1 − µA (x ), µB (x ))
= µ¬A ∨ (A ∧ B) (x )
= max(1 − µA (x ), min(µA (x ), µB (x ))
= µ¬A ∨ (A ∧ B) (x )
= (1 − µA (x )) + µA ∧ B (x ) − . . .
−µ¬A ∧ (A ∧ B) (x )
= (1 − µA (x )) + µA ∧ B (x )
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-61 (243)
Ferienplanung mit Fuzzy-Logik
Wir möchten in den Urlaub fahren. Kriterien sind für uns:
I
Der Urlaub soll möglichst in die Ferienzeit 20. Juni - 10. August
fallen.
I
Wir möchten an die See.
Die Reise soll preiswert oder der Urlaubsplatz „sonnensicher“
sein.
Reiseziel
Zeitraum
Preis
Wismar
19.6.-2.7.
1000
Uns liegen drei Angebote vor:
Bordeaux 1.7.-14.7.
2000
Mallorca
30.7.-12.8. 1800
I
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-62 (244)
Fuzzy-Modellierung
Fuzzy-Werte für
I
an der See
und
I
sonnensicher
werden empirisch festgelegt.
1
0
6
@
0
@
@
1000
@
@
@
@
2000
3000
Abb. 26: Charakteristische Funktion – preiswert
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-63 (245)
Ferienzeit
Fuzzywert =
3 Vages Wissen
Tage in Ferienzeit
Gesamtzahl 14 Tage
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-64 (246)
Komplette Übersicht
Für Variante 1 (min/max) ergibt sich für den Urlaubsplatz Wismar:
Sonne ∨ preiswert : max(0, 8; 0, 87) = 0, 87
Zeit ∧ See ∧ (Sonne ∨ preiswert) : min(min(0, 93; 0, 95); 0, 87) = 0, 87
Reiseziel
Wann
Fuzzy Fuzzy Fuzzy Fuzzy Var Var Var
Zeit Preis Sonne See
1
2
3
Wismar
19.6.-2.7.
0,93
0,87
0,8
0,95 0,87 0,88 0,86
Bordeaux 1.7.-14.7.
1
0,2
0,9
0,8
0,8 0,8 0,74
Mallorca 30.7.-12.8. 0,86
0,33
0,95
0,99 0,86 0,85 0,82
3 Vages Wissen
Künstliche Intelligenz
3.4 Fuzzy-Logik
Folie 3-65 (247)
Fuzzy-Resolution
L1 ∨ L2
¬L1 ∨ K2
L2 ∨ K2
, α
, β
, min(α, β)
Gefahr: Bei langen Schlussketten wird Fuzzy-Wert kleiner und kleiner.
3 Vages Wissen
Künstliche Intelligenz
3.5 Fuzzy-Logik und Prolog
Folie 3-66 (248)
Fuzzy-Logik und Prolog
Prolog-Programme bestehen aus Regeln und Fakten:
H ← B1 ∧ . . . ∧ Bn
H←
Man kann Prolog mit Hilfe einer Fuzzy-Resolutionsregel oder eines
Fuzzy-Modus-ponens auf Fuzzy-Ebene verallgemeinern.
L
L→H
H
, α
, β
, α∗β
3 Vages Wissen
Künstliche Intelligenz
3.6 Fuzzy-Regler
Folie 3-67 (249)
Fuzzy-Regler
I
Interessante Fuzzy-Anwendung für Regelungs-Vorgänge
I
Natürlichsprachliche Regeln der Form:
Wenn der Zug dem Ziel nah ist und die Geschwindigkeit hoch ist, dann
ist stark zu bremsen.
I
Offen: Modellierung der unscharfen Begriffe nah, hoch, stark
I
Dies kann man mit Fuzzy-Mengen tun.
3 Vages Wissen
Künstliche Intelligenz
3.6 Fuzzy-Regler
Folie 3-68 (250)
Fuzzy-Regler 2
I
Linke Seite einer Regel: Messgrößen
I
Rechte Seite einer Regel: Einstellgrößen
Wir gehen davon aus, dass wir n Messgrößen x1 ∈ X1 , . . . , xn ∈ Xn und
eine Stellgröße y ∈ Y haben. Regeln haben dann die Form:
Rj : WENN x1 IST a1,j ∧ . . . ∧ xn IST an,j DANN y IST bj
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-69 (251)
Regelung eines inversen Pendels
Ein auf dem Kopf stehendes Pendel soll durch ein Fuzzy-System
geregelt werden. Die Aufgabe besteht darin, die Masse oben zu
halten. Es darf nur das untere Ende des Stabs bewegt werden.
sH Winkelgeschwindigkeit γ0
HH HH
j
H
j
H
Winkel γ v
- Kraft F
Abb. 27: Inverses Pendel
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-70 (252)
Mess- und Stellgrößen
Messgrößen:
I
X1 ... Winkel γ, [−90, 90] Grad
I
X2 ... Winkelgeschwindigkeit γ0 , [−50, 50] Grad/Sekunde
Einstellgröße:
I
X3 ... horizontale Kraft F, [−10, 10] Newton
WENN γ IST positiv klein ∧ γ0 IST etwa Null DANN F IST positiv klein
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-71 (253)
Fuzzy-Modellierung
Modellierung von positiv klein, etwa 0 usw.: mit Dreiecks-Funktionen
1
6
A
A
A A
etwa Null A
A positiv
A klein
A
A
A
A
A
A
- Winkel γ
A
-20
-10
0
10
20
Abb. 28: Winkel – positiv klein, etwa Null
Zuordnung eines Messwerts zu den Fuzzy-Mengen ; Fuzzyfizierung
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-72 (254)
Inverses Pendel
Ist γ etwa null und γ0 positiv mittel, dann ist die anzulegende
horizontale Kraft positiv mittel.
γ
ng
ng
nm
γ0 : nk
en
pk
pm
pg
ng
nm
nk
nm
nm
nk
en
en
ng
nm
nk
en
pk
pm
pg
pk
pm
pg
en
pk
pm
pm
pg
Tabelle 8: Regeln für Inverses Pendel
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-73 (255)
Verarbeitung
Welche Regel ist nun anzuwenden? Meist kommen mehrere Regeln in
Frage.
Hat man konkrete Messwerte,
I
bestimmt man für jede Bedingung jeder Regel den
Zugehörigkeitswert und
I
verknüpft die Werte für die Bedingungen je Regel mit min.
Nun gibt es 2 Varianten:
I
Regel mit dem maximalen Fuzzy-Wert der Bedingungen (max).
I
Man berücksichtigt alle Regeln, deren Bedingungen einen
Fuzzy-Wert 6= 0 liefern.
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-74 (256)
Inverses Pendel
Wir betrachten den Fall γ = 0, γ0 = −3. Der Stab befindet sich zwar im
Gleichgewicht, bewegt sich aber nach links. Definiert man die
Fuzzy-Mengen für γ gemäß
1
6
A
A
A A
etwa Null A
A positiv
A klein
A
A
A
A
A
A
- Winkel γ
A
-20
-10
0
10
20
dann kommen nur Regeln, die den Winkel γ mit etwa Null einstufen, in
Betracht.
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-75 (257)
Inverses Pendel
Die Fuzzy-Mengen für die Winkelgeschwindigkeit γ0 seien wie folgt
definiert.
6
A
A
A A
negativ klein A
A
A etwa Null
A
A
A
A
A
A
- WinkelA
geschwindigkeit
γ0
-5
5
-10
0
10
1
Abb. 29: Winkelgeschwindigkeit – negativ klein, etwa Null
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Inverses Pendel
Es kommen nun nur zwei Regeln in Frage:
WENN γ IST etwa Null ∧ γ0 IST etwa Null
DANN F IST etwa Null
WENN γ IST etwa Null ∧ γ0 IST negativ klein
DANN F IST negativ klein
Folie 3-76 (258)
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-77 (259)
Inverses Pendel
Das Minimum der Zugehörigkeitswerte der Bedingungen ergibt für die
beiden Regeln:
c1 = min(b11 ; b21 ) = min(1; 0, 4) = 0, 4
c2 = min(b12 ; b22 ) = min(1; 0, 6) = 0, 6
Für alle anderen Regeln gilt ci = 0.
Jede Regel liefert eine Fuzzy-Menge, die zur Anwendung kommen
könnte.
Wie wird die anzulegende Kraft F berechnet?
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-78 (260)
Inverses Pendel
Zunächst beschränkt man die Zugehörigkeitsfunktion für F etwa Null
auf den Zugehörigkeitswert c1 = 0, 4.
6
A
A
etwa Null A
A
A
A
A -F
0
-2
2
1
1
6
etwa Null
-2
0
A
A
A -F
2
Abb. 30: Reduzierte Fuzzy-Menge – F etwa Null
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-79 (261)
Inverses Pendel
Analog beschränkt man die Zugehörigkeitsfunktion (für die
anzulegende Kraft) F negativ klein auf den Zugehörigkeitswert
c1 = 0, 6.
6
1
A
A
neg. klein A
A
A
A
A -F
-3
-1
1
neg. klein
1
6
A
A
A
A -F
-3
-1
1
Abb. 31: Reduzierte Fuzzy-Menge – F negativ klein
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-80 (262)
Inverses Pendel
Es wird der Schwerpunkt der aus beiden Flächen entstehenden
gemeinsamen Fläche berechnet.
1
6
neg. klein
etwa Null
A
• A A
••A A
A A
- Kraft F
3
-3
-1
1
Abb. 32: Schwerpunkt beider Fuzzy-Mengen
Der x-Wert unter diesem Schwerpunkt wird als Stellwert genommen.
Hier wird also eine Kraft von etwa -0,57 N angelegt.
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-81 (263)
Schwerpunktmethode
I
Vorgehen wird Schwerpunktmethode genannt.
I
Berechnen eines exakten Wertes aus einer Fuzzy-Menge . . .
Defuzzyfizierung
3 Vages Wissen
Künstliche Intelligenz
3.7 Regelung eines inversen Pendels
Folie 3-82 (264)
Fuzzy-Regler
Messwerte
Prozess
Stellwert
Fuzzy−Regelung
Fuzzyfizierung
Entscheidung
Defuzzyfizierung
Wissensbasis
Abb. 33: Architektur eines Fuzzy-Reglers
3 Vages Wissen
Künstliche Intelligenz
3.8 Ergänzungen
Folie 3-83 (265)
Weiterführende Konzepte
I
Bayessche Netze
I
I
I
I
Abhängigkeiten als Graph
mit Wahrscheinlichkeiten versehen
Wahrscheinlichkeiten pflanzen sich durch den Graphen fort
Dempster-Shafer-Theorie (Vertrauensintervalle)
3 Vages Wissen
Künstliche Intelligenz
3.9 Zusammenfassung (Fuzzy)
Das sollten Sie wissen . . .
Zusammenfassung 3.6 (Fuzzy)
I
Unsicheres / unscharfes Wissen
I
Wahrscheinlichkeits-basierte WR/WV
I
Sicherheitsfaktoren
I
Fuzzy-Logik
I
Fuzzy-Mengen
I
Fuzzy-Regler
Folie 3-84 (266)
3 Vages Wissen
Künstliche Intelligenz
3.10 Aufgaben (Fuzzy)
Folie 3-85 (267)
Aufgaben – Fuzzy
Aufgabe 3.1 (Stückweise lineare Funktionen)
Finden Sie stückweise lineare Funktionen für die Fuzzy-Mengen: groß,
ca. 10 Stück. Wie repräsentiert man stückweise lineare Funktionen?
D.h. wie stellt man sie in einem Computer-Programm dar, damit man
mit der Funktion rechnen kann?
Aufgabe 3.2 (Fuzzy-Mengen)
Berechnen Sie für 2 Fuzzy-Mengen GROß und KLEIN den
Durchschnitt und die Vereinigung nach min/max!
3 Vages Wissen
Künstliche Intelligenz
3.10 Aufgaben (Fuzzy)
Folie 3-86 (268)
Aufgabe 3.3 (Bayessche Formel)
Ist ein Musiker gut, so bekommt er zumeist eine gutes Musikdiplom
(Wahrscheinlichkeit 70%). Ist er nicht gut, so hat er nur noch eine
10%-Chance auf ein gutes Musikdiplom. Absolventen mit einem guten
Musikdiplom bekommen meistens eine Stelle (70%). Schlechte
Absolventen haben dagegen nur noch eine 10%-Chance. 30% der
Musiker sind gut.
I
Wie groß ist die Wahrscheinlichkeit, dass ein Musiker eingestellt
wird?
I
Was kann man aus der Tatsache, dass ein Musiker nicht
eingestellt wird, bezüglich seines Talents (guter/schlechter
Musiker) folgern?
4 Prolog
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
4 Prolog
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 4
Prolog
Allgemeine Hinweise
Grundkonzept von Prolog
Abarbeitung und Bedeutung von PROLOG-Programmen
Datentypen und Arithmetik
Steuerung der Abarbeitung
Beispielprogramme
Zusammenfassung (Prolog)
Aufgaben
4 Prolog
Künstliche Intelligenz
Folie 4-1 (271)
Prolog
When a compiler accepts a program without error on the first run, the
program will not yield the desired output.
Arthur Bloch, Murphy’s Law
4 Prolog
Künstliche Intelligenz
Folie 4-2 (272)
PROLOG – Wozu?
1. Wenn (falls) es regnet, ist es nass: regnet → nass
2. Es regnet: regnet
Nach dem Modus Ponens kann man nun schließen:
nass
Dies kann man (in etwas anderer Notation) in PROLOG ausdrücken:
nass :- regnet.
regnet.
% Es ist nass, FALLS es regnet.
% Es regnet.
Fragt man PROLOG nun, ob nass wahr ist, so antwortet PROLOG
korrekt mit yes (oder true).
Die Regel entpuppt sich als ausführbares Programm.
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-3 (273)
4.1.1 Arbeiten mit PROLOG
Arbeiten mit PROLOG
1. Prolog starten
2. Erstellen/Modifizieren der Wissensbasis (in separater Datei):
Fakten/Regeln eingeben oder modifizieren
3. Datei laden/compilieren
4. Anfragen stellen
5. Gehe zu 2. oder Prolog verlassen.
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-4 (274)
4.1.2 Syntaktische Grundkenntnisse
Syntaktische Grundkenntnisse
I
In PROLOG: Klauseln, d.h. Fakten und Regeln
I
Jede Eingabe in Prolog mit . abschließen.
I
Eingabeprompt ?Bei Eingabe einer Klausel wird dies als Anfrage interpretiert.
I
Laden einer Datei mit Klauseln: Fakten/Regeln als Wissen
gespeichert.
I
Kommentare: mittels /* und */, oder zeilenweise mit %
I
Variablen: beginnen mit einem Großbuchstaben, Konstante mit
einem Kleinbuchstaben.
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-5 (275)
4.1.3 Einordnung von PROLOG
Einordnung von PROLOG
Prolog erlaubt mehrere Sichten:
I
logische Sicht
I
prozedurale Sicht
I
Datenbank-Sicht
Prolog eignet sich exzellent zum rapid prototyping.
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
4.1.3 Einordnung von PROLOG
Prozedurales Programmieren
I
Problemanalyse
I
Spezifikation der Lösung
I
algorithmische Umsetzung
Folie 4-6 (276)
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-7 (277)
4.1.3 Einordnung von PROLOG
Logisches Programmieren
Andere Idee:
I
Beschreibung des Problems in Form von logischen
Zusammenhängen.
I
Problemlösung als Anfrage, ob ein bestimmter Sachverhalt aus
obigen logischen Zusammenhängen folgt.
I
PROLOG-Programm: Menge von Aussagen
I
Berechnung: Beweis, dass eine bestimmte Aussage gilt!
PROLOG als Programmiersprache interpretierbar, in der mit Hilfe
von logischen Zusammenhängen programmiert wird.
;
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-8 (278)
4.1.3 Einordnung von PROLOG
Beispiel 4.1 (Zahlen suchen)
Dreistellige Zahlen gesucht, die
I
durch 5 und 6 teilbar
I
bei Division durch 9: Rest 3
In Pascal
PROGRAM gesuchtezahl;
VAR zahl: INTEGER;
BEGIN
FOR zahl := 100 TO 999
IF
((zahl mod
AND ((zahl mod
AND ((zahl mod
THEN WRITELN(zahl);
END.
DO
5) = 0)
6) = 0)
9) = 3)
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-9 (279)
4.1.3 Einordnung von PROLOG
In PROLOG
In PROLOG
ziffer(Z) :- member(Z,[0,1,2,3,4,5,6,7,8,9]).
gesucht(Zahl) :ziffer(H), H > 0, ziffer(Z), ziffer(E),
Zahl is H*100 + Z*10 + E,
0 is Zahl mod 5,
0 is Zahl mod 6,
3 is Zahl mod 9.
4 Prolog
Künstliche Intelligenz
4.1 Allgemeine Hinweise
Folie 4-10 (280)
4.1.3 Einordnung von PROLOG
Einordnung und Historie
I
Prolog realisiert Ziel-orientiertes Programmieren.
I
Deklarative Programmierung: Spezifizieren, was zu lösen ist,
nicht wie es zu lösen ist.
I
Prolog = PROgramming in LOGic, ca. 1970:
I
I
I
Theorie: Robert Kowalski (Edinburgh)
Experimente: Maarten van Emden (Edinburgh)
Implementierung: Alain Colmerauer (Marseilles)
I
Mitte der 70er Jahre: effiziente Implementierung durch David
Warren (Edinburgh)
I
Erste Implementierungen: nur Interpreter
I
Heute: Interpreter + leistungsstarke Compiler
I
Grundlagen für Prolog:
I
I
Logik (Prädikatenlogik 1. Stufe)
Resolution (Robinson 1965)
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-11 (281)
4.2.1 Fakten
Fakten
frau_von
wolfgang
gerda
vater_von
frau_von
christine renate juergen lutz
kerstin
vater_von
martin
ralf
Abb. 34: Familienwissensbasis
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
4.2.1 Fakten
Fakten
I
vater_von(christine,wolfgang).
I
vater_von(renate,wolfgang).
I
vater_von(juergen,wolfgang).
I
vater_von(lutz,wolfgang).
I
vater_von(martin,lutz).
I
vater_von(ralf,lutz).
I
frau_von(wolfgang,gerda).
I
frau_von(lutz,kerstin).
Folie 4-12 (282)
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-13 (283)
4.2.1 Fakten
Parameter
Bemerkung 4.1 (Parameterreihenfolge)
Was ist richtig?
I
vater_von(kind, vater) oder
I
vater_von(vater, kind)?
Das ist egal.
Ähnlich wie beim Datenbankentwurf müssen wir uns auf eine Variante
festlegen.
4 Prolog
4.2 Grundkonzept von Prolog
4.2.2 Anfragen ohne und mit Variablen
Anfragen ohne und mit Variablen
Anfragen an Prolog:
?- vater_von(juergen,christine).
false
?- vater_von(juergen,wolfgang).
true
?- vater_von(X,wolfgang).
X = christine ;
X = renate ;
X = juergen ;
X = lutz ;
false
Künstliche Intelligenz
Folie 4-14 (284)
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-15 (285)
4.2.2 Anfragen ohne und mit Variablen
Erste Beobachtungen
I
Fakten
I
Anfragen ohne Variablen
I
Anfragen mit Variablen
I
Suche nach weiteren Lösungen
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-16 (286)
4.2.3 Fakten mit Variablen
Fakten mit Variablen
Variablen in Fakten:
Für jede Belegung von X gilt: ...
I
Fakt gefaellt(X,merkel). : Egal wie X belegt ist, gilt ....
I
Die Anfrage gefaellt(jcleve,merkel) liefert also true.
I
Variablen in Fakten: allquantifiziert.
I
;
meistens unsinnig
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-17 (287)
4.2.4 Konjunktive Anfragen und shared variables
Konjunktive Anfragen und shared variables
Anfrage: ?- vater_von(juergen,X),vater_von(lutz,X).
Antwort: X = wolfgang
Gesucht: Variablenbelegung, so dass sowohl
vater_von(juergen,X) als auch vater_von(lutz,X) gilt.
Komma entspricht in PROLOG dem logischen UND.
Als logische Anfrage:
I
Gibt es eine Variablenbelegung, so dass beide Anfragen gelten.
Operational/prozedural:
I
Löse 1. Anfrage, übernimm die Variablenbindung und
I
versuche, 2. Anfrage (mit dieser Variablenbelegung) zu beweisen.
4 Prolog
4.2 Grundkonzept von Prolog
Künstliche Intelligenz
Folie 4-18 (288)
4.2.4 Konjunktive Anfragen und shared variables
Aufgaben
Aufgabe 4.1 (Familie)
Erstellen Sie eine eigene Faktenbasis über Ihre Familie, aufbauend
auf vater_von, frau_von.
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-19 (289)
4.2.5 Regeln
Regeln
Suche nach einem Großvater:
1. ?- vater_von(ralf,X), vater_von(X,Y).
2. Definition des Großvaters als logische Regel unabhängig von der
eigentlichen Familie:
grossvater_von(X,Y) :vater_von(X,Z), vater_von(Z,Y).
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-20 (290)
4.2.5 Regeln
Bemerkungen
I
Regel wird auch als Klausel bezeichnet.
I
Conclusion (grossvater_von(..)) . . . Kopf
I
Bedingungen (vater_von(..), vater_von(..)) . . . Körper
der Klausel
I
Eigenschaften wie vater_von, frau_von . . . Prädikate
I
Struktur: Prädikat(arg1 ,...,argn ) . . . Literal
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-21 (291)
4.2.5 Regeln
Syntax
I
Großgeschriebene Namen sind Variablen.
I
Gleiche Variablennamen bezeichnen gleiche Objekte nur
innerhalb einer Regel (lokales Variablenkonzept).
I
Variablen in Regeln sind allquantifiziert.
I
Variablen in Anfragen sind existenzquantifiziert.
I
Fakten / Regeln / Literale
I
Logisches Und
,
I
Logisches Falls
:-
4 Prolog
4.2 Grundkonzept von Prolog
Künstliche Intelligenz
Folie 4-22 (292)
4.2.5 Regeln
Variablennamen
Häufig sind Variablennamen wie X, Y wenig aussagekräftig. Besser so:
grossvater_von(Kind,Grossvater) :vater_von(Kind,Vater),
vater_von(Vater,Grossvater).
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-23 (293)
4.2.5 Regeln
Aufgaben
Aufgabe 4.2 (Familie)
Erweitern Sie Ihre Familien-Datei.
Aufgabe 4.3 (Familie)
Programmieren Sie das Prädikat mutter_von. Sie müssen dazu
definieren, wann Y die Mutter von X ist, also mutter_von(X,Y) :....
I
Mit mutter_von haben wir die Vater-orientierte Sicht auf die
Familie korrigiert.
I
Nun vater_von und mutter_von wie Fakten verwendbar.
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-24 (294)
4.2.5 Regeln
Regeln
Frage: Wie definiert man den Großvater mütterlicherseits?
I
2. Regel für Großvater
oder
I
Prädikat eltern_von/2 definieren:
eltern_von(Kind,Vater) :- vater_von(Kind,Vater).
eltern_von(Kind,Mutter) :- mutter_von(Kind,Mutter).
grossvater_von(Kind,Grossvater) :eltern_von(Kind,E), vater_von(E,Grossvater).
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-25 (295)
4.2.5 Regeln
Regeln
Um Prädikate wie schwester_von definieren zu können, muss man
das Geschlecht der Personen kennen.
1. Möglichkeit
I
mann(wolfgang).
I
frau(gerda).
mann(juergen).
...
...
2. Möglichkeit
I
mann(...) explizit für jeden nicht verheirateten Mann
I
frau(...) explizit für jede nicht verheiratete Frau
I
mann(X) :- frau_von(X,Y). verheirateter Mann
I
frau(X) :- frau_von(Y,X). verheiratete Frau
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
4.2.5 Regeln
Zusammenfassung
1. Prolog-Programme – Wissensbasen
(Klauseln, Kopf :- Körper, Fakten)
2. :- entspricht der logischen Implikation
3. Anfragen mit freien Variablen
4. Klausel mit Variablen:
logische Regel „Für alle ... gilt : ...“
5. Variablen in Fakten/Regeln sind somit allquantifiziert,
6. Variablen in Anfragen: existenzquantifiziert.
7. Variable in einer Regel doppelt (gemeinsame (shared)
Variablen)
Folie 4-26 (296)
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-27 (297)
4.2.5 Regeln
Aufgaben
Aufgabe 4.4 (Familie)
Programmieren Sie weitere Verwandschaftsrelationen.
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-28 (298)
4.2.6 Rekursive Regeln
Rekursive Regeln
Wann ist eine Person ein Vorfahre einer anderen Person?
vorfahre_von(Person,Vorfahre) :eltern_von(Person,Vorfahre).
vorfahre_von(Person,Vorfahre) :eltern_von(Person,X),
eltern_von(X,Vorfahre).
vorfahre_von(Person,Vorfahre) :eltern_von(Person,X),
eltern_von(X,Y),
eltern_von(Y,Vorfahre).
Nachteil: Vorfahren nur bis zu einer bestimmten Generation erreichbar.
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-29 (299)
4.2.6 Rekursive Regeln
Rekursive Regeln
2. Möglichkeit: rekursive Regeldefinition
vorfahre_von(Person,Vorfahre) :eltern_von(Person,Vorfahre).
vorfahre_von(Person,Vorfahre) :eltern_von(Person,X),
vorfahre_von(X,Vorfahre).
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-30 (300)
4.2.6 Rekursive Regeln
Abarbeitung
?−vorfahre_von(martin,wolfgang).
Regel 1
Regel 2
eltern_von(martin,wolfgang) eltern_von(martin,X),vorfahre_von(X,wolfgang)
fail
ok mit X=lutz
Regel 1
eltern_von(lutz,wolfgang)
ok
Abb. 35: Vorfahre – Trace
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-31 (301)
4.2.6 Rekursive Regeln
Rekursion
Beispiel 4.2 (Rekursion)
Theorie, nach der man in 7 (oder weniger ?) Schritten zu jedem
Menschen auf der Welt eine Beziehung herstellen kann.
Können wir diese Relation beziehung zwischen beliebigen Personen
X und Y in Prolog darstellen?
Der einfachste Fall ist, dass X die Person Y direkt kennt:
beziehung(X,Y) :- kennt(X,Y).
Oder indirekte Verbindung über eine andere Person Z:
beziehung(X,Y) :- kennt(X,Z), beziehung(Z,Y).
Was müssen wir tun, wenn wir zusätzlich die Distanz zwischen X und
Y haben wollen?
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-32 (302)
4.2.6 Rekursive Regeln
Zusammenfassung
1. Prolog-Anfrage aktiviert einen Beweis-Prozess
2. Dabei können Variablen belegt werden.
3. PROLOG – kein Unterschied zwischen formalen und aktuellen
Parametern
4. Backtracking
4 Prolog
Künstliche Intelligenz
4.2 Grundkonzept von Prolog
Folie 4-33 (303)
4.2.6 Rekursive Regeln
Aufgaben
Aufgabe 4.5 (Reicher_als)
Seien Fakten über Personen gegeben, die ausdrücken, wer reicher ist:
reicher(adam,berta). % Adam ist reicher als Berta.
reicher(berta,clemens).
reicher(adam,erwin).
reicher(eva,adam).
Aus den Fakten folgt, dass Eva reicher als Clemens ist. PROLOG
würde uns aber FALSE antworten. Entwickeln Sie Regeln für
reicher_als, die sowohl die reicher-Fakten als auch die transitiven
Beziehungen enthält.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-34 (304)
4.3.1 Backtracking
Abarbeitung und Bedeutung von PROLOG-Programmen
Wie löst PROLOG die folgende Anfrage (vgl. Abb. 34)?
?-vater_von(X,wolfgang), vater_von(ralf,X).
I
Zunächst erste Teilanfrage: gelöst mit X=christine
I
Mit X=christine wird 2. Teilanfrage bearbeitet:
?-vater_von(ralf,christine).
I
Geht nicht. Deshalb Backtracking.
I
Suche nach einer anderen Lösung für 1. Teilanfrage,
. . . wobei Variablenbindung X=christine gelöst wird.
I
PROLOG generiert dann nach und nach X=renate, X=juergen,
X=lutz.
I
Mit X=lutz gelingt auch 2. Teilanfrage.
I
PROLOG findet also die korrekte Antwort X=lutz.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-35 (305)
4.3.1 Backtracking
Abarbeitung und Bedeutung von PROLOG-Programmen
(1) vater_von(stephan,bernd).
(2) mutter_von(stephan,renate). ?−grosseltern_von(stephan,gerda).
(3) vater_von(renate,wolfgang).
Enkel=stephan
(4) mutter_von(renate,gerda).
Klausel 7 G=gerda
(5) eltern_von(Kind,Vater) :−
vater_von(Kind,Vater).
(6) eltern_von(Kind,Mutter) :− eltern_von(stephan,E), eltern_von(E,gerda)
mutter_von(Kind,Mutter).
Klausel 5
Kind=stephan
(7) grosseltern_von(Enkel,G) :−
Kind=stephan
Mutter=E
eltern_von(Enkel,E),
Klausel 6
Vater=E
eltern_von(E,G).
vater_von(stephan,E), eltern_von(E,gerda)
Klausel 1
E=bernd
Klausel 2
true, eltern_von(bernd,gerda)
Klausel 5
Klausel 6
Vater=gerda
Kind=bernd
Kind=bernd
Mutter=gerda
vater_von(bernd,gerda)
fail
mutter_von(stephan,E), eltern_von(E,gerda)
E=renate
true, eltern_von(renate,gerda)
Klausel 6
Klausel 5
Vater=gerda
Mutter=gerda
Kind=renate
Kind=renate
mutter_von(bernd,gerda) vater_von(renate,gerda)
fail
fail
mutter_von(renate,gerda)
ok
Abb. 36: Familien-Wissensbasis – Trace
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-36 (306)
4.3.1 Backtracking
Backtracking
ok
no
?− ziel1,
ok
ziel2 .
fertig (yes / Var.belegung)
fail ? nochmal ?
Abb. 37: Abarbeitung einer Anfrage in Prolog
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-37 (307)
4.3.2 Parameterübergabe mittels Unifikation
Parameterübergabe mittels Unifikation
I
wichtigste Operation für Terme, Parameterübergabe wird in
Prolog mittels Unifikation realisiert.
I
Seien T1 und T2 Terme: Existiert eine Variablensubstitution s, so
dass
s(T1) == s(T2) gilt.
I
In Prolog bezeichnet = die Unifikation, == die Identität.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-38 (308)
4.3.2 Parameterübergabe mittels Unifikation
Das is-Prädikat
X is <ausdruck>
Werte den arithmetischen Ausdruck <ausdruck> aus und unifiziere
das Resultat mit X.
Beispiel 4.3 (Unterschied zwischen is und =)
?- zeit(Min,50)=zeit(Min1,Sek).
Min=Min1,Sek=50
?- 5 is 4 + 1.
true
?- X is 4 + 1.
X = 5
?- 5 = 4 + 1.
false
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-39 (309)
4.3.2 Parameterübergabe mittels Unifikation
Regeln für die Unifikation
Wie löst Prolog die Anfrage ?- S=T ?
1. S und T konstant, dann muss gelten: S==T.
2. S oder T variabel: S wird mit T instantiiert oder umgekehrt.
3. S und T Strukturen, S = f (s1 , s2 , ..., sn ), T = g (t1 , t2 , ..., tm ).
Dann muss gelten: f==g, n==m, si = ti für alle i=1,...,n .
4 Prolog
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Künstliche Intelligenz
Folie 4-40 (310)
4.3.2 Parameterübergabe mittels Unifikation
Unifikation – Beispiel
Definition einer vertikalen bzw. horizontalen Geraden:
vertikal(gerade(punkt(X,_),punkt(X,_))).
horizontal(gerade(punkt(_,Y),punkt(_,Y))).
?- vertikal(gerade(punkt(1,1),punkt(1,2))).
?- horizontal(gerade(punkt(2,2),P)).
?- vertikal(G),horizontal(G).
G=gerade(punkt(X,Y),punkt(X,Y))
true
P=punkt(_,2)
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-41 (311)
4.3.3 Bedeutung von Prologprogrammen
Prologprogramme – Deklarative Interpretation
Sei
I
H :- T1 , T2 , T3 , . . . , Tn
eine Regel (Klausel).
H gilt, falls T1 und T2 und ... und Tn gelten. oder
Aus der Gültigkeit von T1 und T2 und ... und Tn folgt die Gültigkeit
von H.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-42 (312)
4.3.3 Bedeutung von Prologprogrammen
Logische Sicht der Abarbeitung
Abarbeitung: Ein Ziel G ist wahr, wenn
1. Es existiert eine Klausel C, deren Kopf sich mit G unifizieren lässt
(Variablensubstitution sei s).
2. Alle Literale des Körpers von C (unter Beachtung der
Variablensubstitution s) lassen sich beweisen.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-43 (313)
4.3.3 Bedeutung von Prologprogrammen
Prologprogramme – Prozedurale Interpretation
Sei H :- T1 , T2 , T3 , . . . , Tn eine Regel (Klausel).
I
Um H zu lösen, löse T1 , dann T2 , . . . , dann löse Tn .
oder
Wird die Prozedur H aktiviert, so aktiviert diese die Prozeduren
T1 , . . . , Tn in dieser Reihenfolge.
I
Ist der Körper leer, so ist die Prozedur abgearbeitet.
4 Prolog
Künstliche Intelligenz
4.3 Abarbeitung und Bedeutung von PROLOG-Programmen
Folie 4-44 (314)
4.3.3 Bedeutung von Prologprogrammen
Prologprogramme – Prozedurale Interpretation
Wähle nächstes Ziel
ok
Finde Regel Kopf :− Bedingungenfail
mit Kopf = Ziel
fail
yes
Löse Bedingungen
ok
Abb. 38: Prolog – Programmablauf
fail
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-45 (315)
4.4.1 Datenobjekte
Syntax von Prolog – Datenobjekte
I
Atome
I
I
I
beginnend mit Kleinbuchstaben
spezielle Zeichen (z.B. ==, = \ = etc.)
Folge von Zeichen, eingeschlossen in Apostroph (z.B. ’Hallo’)
I
Zahlen
I
Strings
Folge von Zeichen, eingeschlossen in
Anführungsstriche (z.B. ”Hallo”)
I
Variable
I
I
I
integer, float
beginnend mit Großbuchstaben oder Underline (_)
anonyme Variable _
Strukturen: funktor (K1 , K2 , . . . , Kn )
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-46 (316)
4.4.1 Datenobjekte
Syntax von Prolog – Datenobjekte
Datenobjekte (Terme)
einfache Terme
Konstante
Strukturen
Variable
Atome Zahlen Strings
Abb. 39: Datentypen in PROLOG
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-47 (317)
4.4.1 Datenobjekte
Beispiele
Geometrische Strukturen in der Ebene:
punkt(X,Y)
gerade(punkt(X1,Y1),punkt(X2,Y2))
kreis(punkt(X,Y),Radius)
quadrat(punkt(X1,Y1),punkt(X2,Y2))
Auch arithmetische Ausdrücke sind Strukturen: ∗(+(4, 5), −(6, 7))
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-48 (318)
4.4.2 Listen
Listen
Darstellung von Listen:
[anne,niels,juergen,marianne]
Die Restliste wird durch | definiert. Folgende Listendarstellungen sind
äquivalent:
[a,b,c] = [a|[b,c]] = [a,b|[c]] = [a,b,c|[]]
Anfrage 1:
Anfrage 2:
?-[a,b,c,d,e] = [a,b|X].
?-[a,b,[c,d,e]] = [a,b|X].
X=[c,d,e]
X=[[c,d,e]]
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-49 (319)
4.4.2 Listen
Element-Beziehung
Wann ist ein Element in einer Liste enthalten?
el(X,[X|Y]).
% 1. Fall, X ist erstes Element
el(X,[F|Y]) :- el(X,Y). % 2. Fall, X ist in der Restliste
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
4.4.2 Listen
Element-Beziehung – 2
Anfrage mit einer Variablen → überraschende Antworten:
?-el(X,[1,2,3]).
X=1 ;
X=2 ;
X=3 ;
false
Dank Unifikation kann el/2 uns auch Lösungen generieren.
Folie 4-50 (320)
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-51 (321)
4.4.2 Listen
Weitere Listen-Prädikate
app([],L,L).
app([H|T],L,[H|M]):app(T,L,M).
?-app([1,2],[3,4],Z).
Z=[1,2,3,4] ;
false
?-app([1,X],[3,4],[1,2|Y]).
X=2
Y=[3,4] ;
false
del(X,[X|T],T).
del(X,[Y|T],[Y|U]):del(X,T,U).
?-del(X,[1,2,3],Y).
X=1 Y=[2,3] ;
X=2 Y=[1,3] ;
X=3 Y=[1,2] ;
false
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
4.4.2 Listen
app/3 als Hilfsprädikat
el_append(Element,Liste,ListeNeu) :app(Liste,[Element],ListeNeu).
enthalten(Liste,Superliste) :app(L1,L2,Superliste),
app(Liste,L3,L2).
Folie 4-52 (322)
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-53 (323)
4.4.3 Arithmetik
Arithmetik
Natürlich gibt es in PROLOG vordefinierte arithmetische
Operationen.
Operationen: +, −, ∗, /, mod , //
Vergleiche:
<, >, >=, =<, =:=, = \ =
Beispiel 4.4 (Arithmetische Operationen und
Unifikation/Identität)
??????-
X = 5-2-1
1+2 = 2+1
X == Y.
X \== Y.
X \= Y.
15*4 > 50
no
false
false
true
false
true
??????-
X is 5-2-1
1+2 =:= 2+1
X=Y, X == Y.
X=Y, X \== Y.
X=1,Y=2,X\=Y.
15*4 =\= 15*4
4 Prolog
X=2
true
true
false
true
false
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-54 (324)
4.4.3 Arithmetik
Beispiele - Arithmetik
Beispiel 4.5 (Arithmetische Prädikate)
fak(0,1).
fak(N,Fak) :- N1 is N-1, fak(N1,Fak1), Fak is N * Fak1.
l_length([],0).
l_length([_|T],N) :- l_length(T,N1), N is N1 + 1.
max([X],X).
max([First|Rest],Max) :- max(Rest,Max1),
(First > Max1, Max=First ; First =< Max1, Max=Max1).
sumlist([],0).
sumlist([First|Rest],Summe) :- sumlist(Rest,Sum1),
Summe is Sum1 + First.
4 Prolog
Künstliche Intelligenz
4.4 Datentypen und Arithmetik
Folie 4-55 (325)
4.4.3 Arithmetik
Aufgaben
Aufgabe 4.6 (Listen)
Schreiben Sie ein PROLOG-Programm, welches aus einer Liste von
Zahlen alle die Elemente löscht, die kleiner als 0 sind.
Aufgabe 4.7 (Listen)
Schreiben Sie ein PROLOG-Programm, welches eine Liste von Zahlen
bekommt und diejenige Liste zurückliefert, in der alle ursprünglichen
Zahlen halbiert worden sind.
Aufgabe 4.8 (Listen)
Schreiben Sie ein PROLOG-Programm, welches eine Liste von Zahlen
bekommt und das Produkt aller dieser Zahlen zurückliefert.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-56 (326)
4.5.1 Reihenfolge der Klauseln
Reihenfolge der Klauseln
Beispiel 4.6 (Berechnung der Fakultät von n)
n ! = n * (n-1) !
0 ! = 1
fak(N,Fak) :- N1 is N-1,
fak(N1,Fak1), Fak is Fak1 * N.
fak(0,1).
Anfrage: ?-fak(4,F). → Fehlermeldung
Falsche Reihenfolge der Klauseln.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-57 (327)
4.5.2 Reihenfolge der Literale im Körper einer Klausel
Reihenfolge der Bedingungsliterale
Beispiel 4.7 (vorfahre_von-Relation)
(1) vorfahre_von(X,Y) :- eltern_von(X,Y).
(2.1) vorfahre_von(X,Y):(2.2) vorfahre_von(X,Y) :eltern_von(X,Z),
vorfahre_von(Z,Y),
vorfahre_von(Z,Y).
eltern_von(X,Z).
(Var 1)
(Var 2)
Anfrage: ?- vorfahre_von(gerda,gerda).
1. Variante: false
2. Variante: Fehlermeldung
Falsche Reihenfolge der Bedingungsliterale.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-58 (328)
4.5.2 Reihenfolge der Literale im Körper einer Klausel
Schlussfolgerungen
I
Reihenfolge der Klauseln und Literale in den Klauseln wichtig.
I
Grundprinzip für Klauselreihenfolge: Einfache Dinge stets zuerst
versuchen.
I
Es gibt Prolog-Programme, die deklarativ korrekt, aber prozedural
inkorrekt sind.
I
Deklaratives Programmieren verbessert Formulierbarkeit und
Lesbarkeit.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-59 (329)
4.5.3 Der Cut
Kontrolle des Backtracking – Cut
Beispiel 4.8 (Cut)
In Prolog:

 1 ... x ≤ -1
2
f (x ) =
 x ... -1 < x ≤ 2
4 ... x > 2
f(X,1) :- X =< -1.
f(X,Y) :- X > -1 , X =< 2 , Y is X * X.
f(X,4) :- X > 2.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-60 (330)
4.5.3 Der Cut
Der Cut
Was passiert bei der Anfrage:
?- f(-2,X) , X > 4.
false
Das ist korrekt, aber Regeln 2/3 werden (sinnloserweise) auch
versucht.
→ Verhinderung durch Cut: !
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-61 (331)
4.5.3 Der Cut
Der Cut
Wenn X=< -1 galt, so kommt nur 1. Regel in Frage, also schneide
2./3. Regel ab.
f(X,1) :- X =< -1,!.
Wird Regel 2 versucht, so muss bereits X > -1 gelten, die
entsprechende Bedingung kann weggelassen werden:
f(X,Y) :- X =< 2 , ! , Y is X * X.
Kommt die 3. Regel zur Anwendung, so muss X > 2 bereits gelten:
f(X,4).
4 Prolog
4.5 Steuerung der Abarbeitung
Künstliche Intelligenz
Folie 4-62 (332)
4.5.3 Der Cut
Wirkung des Cuts
Sei eine Klausel H :- B1, ..., Bn, !, A1, ..., Am. gegeben.
Sind B1, ..., Bn erfüllt, so werden alle Alternativen (d.h. alle
evtl. noch anwendbaren Regeln zum Beweis) für B1, ..., Bn und
H abgeschnitten.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-63 (333)
4.5.3 Der Cut
Cut – Beispiele
Beispiel 4.9 (Nicht backtrackbare Prädikate)
el(X,[X|_]) :- !.
el(X,[_|Y]) :- el(X,Y).
del(X,[X|T],T) :- !.
del(X,[Y|T],[Y|U]) :- del(X,T,U).
fak(0,1):-!.
l_length([],0):-!.
fak(N,Fak) :l_length([_|T],N) :N1 is N - 1 ,
l_length(T,N1) ,
fak(N1,F1) ,
N is N1 + 1.
Fak is N * F1.
max([X],X):-!.
max([F|Rest],Max) :max(Rest,M1),
(F > M1,!,Max=F
;
Max=M1).
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-64 (334)
4.5.3 Der Cut
Cut
→ Cut kann die Bedeutung eines Programms verändern.
p :- a , b.
p :- c.
p ⇔ (a ∧ b ) ∨ c
p :- a , ! , b.
p :- c.
p ⇔ (a ∧ b) ∨ (¬a ∧ c )
p :- c.
p :- a,!,b.
p ⇔ c ∨ (a ∧ b)
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-65 (335)
4.5.4 Negation as failure
Negation as failure
liebt(_,bayern) :- !,fail.
liebt(juergen,ankerwismar).
liebt(lutz,hansa).
different(X,X) :- !,fail.
different(X,Y).
Führen ein not/1 im folgenden Sinne ein:
not(Goal) liefert true ⇔ Goal liefert fail.
Definition in Prolog:
not(Goal) :- Goal,!,fail.
not(_).
Vorsicht: not/1 liefert nie eine Variablenbelegung und entspricht
damit nicht der Negation in der Logik.
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-66 (336)
4.5.4 Negation as failure
Negation as failure
Beispiel 4.10 (Wirkung der Negation)
r(a).
q(b).
p(X) :- not(r(X)).
?-q(X),p(X).
X=b
?-p(X),q(X).
false
4 Prolog
Künstliche Intelligenz
4.5 Steuerung der Abarbeitung
Folie 4-67 (337)
4.5.4 Negation as failure
Aufgaben
Aufgabe 4.9 (Listen)
Modifizieren Sie das Listen-Prädikat del/3, so dass nur das erste
Vorkommen eines gesuchten Elements gelöscht wird.
?-del1(1,[2,1,3,1,4],M). soll als einzige Lösung M=[2,3,1,4]
liefern.
Aufgabe 4.10 (Listen)
Modifizieren Sie del1/3 zu del2/3, so dass nun auch Unifikation
ausgeschlossen wird.
I
?-del2(3,[2,1,X,1,4],M). soll false liefern,
I
?-del2(X,[2,1,X,1,4,X],M). liefert M=[2,1,1,4,X].
Aufgabe 4.11 (not-Prädikat)
Implementieren Sie das Prädikat hat_keine_kinder/1. Verwenden
Sie dazu das not.
4 Prolog
Künstliche Intelligenz
4.6 Beispielprogramme
4.6.1 Andere Darstellung für Familienwissensbasis
Andere Darstellung für Familienwissensbasis
family(person(klaus,mustermann,[13,08,77]),
person(claudia,mustermann,[07,02,80]),
[person(anne,mustermann,[16,12,86])]).
Unsere neue Wissensdarstellung in Prolog besteht also aus
I
Vater
I
Mutter
I
Liste der Kinder
Folie 4-68 (338)
4 Prolog
Künstliche Intelligenz
4.6 Beispielprogramme
Folie 4-69 (339)
4.6.1 Andere Darstellung für Familienwissensbasis
Hilfsprädikate
vater_von(X,Y) :- family(Y,_,Ch),el(X,Ch).
frau_von(X,Y) :- family(X,Y,_).
fname(person(_,X,_),X).
vorname(person(X,_,_),X).
gebdatum(person(_,_,D),D).
gebtag(person(_,_,[T,_,_]),T).
gebmonat(person(_,_,[_,M,_]),M).
gebjahr(person(_,_,[_,_,J]),J).
4 Prolog
Künstliche Intelligenz
4.6 Beispielprogramme
Folie 4-70 (340)
4.6.1 Andere Darstellung für Familienwissensbasis
Datenabstraktion
I
Für den Nutzer kann nun die interne Darstellung unsichtbar sein.
I
Welche Zugriffsprozeduren haben wir definiert?
I
I
Datenselektoren
Man kann aber auch leicht
I
I
Datenmodifikatoren
Datenkonstruktoren
definieren.
4 Prolog
Künstliche Intelligenz
4.6 Beispielprogramme
Folie 4-71 (341)
4.6.1 Andere Darstellung für Familienwissensbasis
Aufgaben
Aufgabe 4.12 (Datenstrukturen)
Verändern Sie die obige Darstellung, um das Geschlecht einer Person
bestimmen zu können!
Aufgabe 4.13 (Prädikate)
Definieren Sie Prädikate, die
I
die Namen aller Familien mit/ohne Kinder
I
die Namen aller Kinder, die selbst Kinder haben,
I
alle Zwillinge
suchen.
4 Prolog
Künstliche Intelligenz
4.6 Beispielprogramme
Folie 4-72 (342)
4.6.2 Problem der stabilen Paare
Problem der stabilen Paare
I
Es sollen Projekt-Paare zusammengestellt werden.
I
Jeweils 1 Programmierer plus 1 Designer.
I
Designer: Anna, Bruno, Clara, Dagmar.
I
Programmierer: Anton, Bernd, Christine und Dieter.
I
Mitarbeiter kennen sich, haben also Prioritäten.
Gesucht ist ein Programm, welches stabile Teams generiert.
Wann ist eine Teamaufteilung nicht stabil? Wenn
I
X mit Z1 zusammenarbeiten muss,
I
Z2 mit Y zusammenarbeiten muss und
I
X und Y sich gegenseitig (gegenüber Z1/Z2) vorziehen würden.
4 Prolog
4.6 Beispielprogramme
Künstliche Intelligenz
Folie 4-73 (343)
4.6.2 Problem der stabilen Paare
Wissensdarstellung
designer([’Anna’,’Bruno’,’Clara’,’Dagmar’]).
programmierer([’Anton’,’Bernd’,’Christine’,’Dieter’]).
praeferenz(’Anna’,[’Anton’,’Bernd’,’Christine’,’Dieter’]).
praeferenz(’Bruno’,[’Bernd’,’Christine’,’Anton’,’Dieter’]).
praeferenz(’Clara’,[’Anton’,’Dieter’,’Bernd’,’Christine’]).
praeferenz(’Dagmar’,[’Christine’,’Dieter’,’Anton’,’Bernd’]).
praeferenz(’Anton’,[’Bruno’,’Clara’,’Dagmar’,’Anna’]).
praeferenz(’Bernd’,[’Bruno’,’Clara’,’Anna’,’Dagmar’]).
praeferenz(’Christine’,[’Dagmar’,’Anna’,’Bruno’,’Clara’]).
praeferenz(’Dieter’,[’Dagmar’,’Anna’,’Bruno’,’Clara’]).
4 Prolog
4.6 Beispielprogramme
Künstliche Intelligenz
Folie 4-74 (344)
4.6.2 Problem der stabilen Paare
Lösung
Wir können nun in Prolog die Restriktionen an eine Lösung
spezifizieren:
loesung(Teams):designer(Designer),
programmierer(Programmierer),
zuordnung(Designer,Programmierer,Teams), % beliebige Zuordnung
not((element([X,Z1],Teams), % Wir nehmen beliebigen Designer
element([Z2,Y],Teams), % & einen beliebigen Programmierer.
praeferenz(X,XPraef), % Diese Zuordnung ist instabil,
praeferenz(Y,YPraef), % da X und Y sich gegenseitig
steht_vor(XPraef,Y,Z1),% bevorzugen wuerden.
steht_vor(YPraef,X,Z2))).
4 Prolog
4.6 Beispielprogramme
Künstliche Intelligenz
Folie 4-75 (345)
4.6.2 Problem der stabilen Paare
Hilfsprädikate
zuordnung([],[],[]).
zuordnung([A|L1],L2,[[A,B]|Teams]) :delete(B,L2,L2Rest),
zuordnung(L1,L2Rest,Teams).
element(Element,[Element|_]).
element(Element,[_|Rest]) :- element(Element,Rest).
delete(Elem,[Elem|Rest],Rest).
delete(Elem,[Kopf|Alter_Rest],[Kopf|Neuer_Rest]) :delete(Elem,Alter_Rest,Neuer_Rest).
steht_vor(Liste,A,B) :append(_,[A|Rest],Liste),element(B,Rest).
4 Prolog
4.6 Beispielprogramme
Künstliche Intelligenz
Folie 4-76 (346)
4.6.2 Problem der stabilen Paare
Aufgaben
Aufgabe 4.14 (Verallgemeinerte Zuordnung)
Was müssen wir ändern, wenn wir mit beliebig langen Listen arbeiten
wollen? Die Programmierer- und Designerlisten sollen natürlich nach
wie vor gleichlang, aber eben nicht auf 4 beschränkt sein.
4 Prolog
Künstliche Intelligenz
4.7 Zusammenfassung (Prolog)
Folie 4-77 (347)
Das sollten Sie wissen . . .
Zusammenfassung 4.2 (Prolog)
I
Was sind Fakten und Regeln, Anfragen, Variablen?
I
Rekursion
I
Abarbeitung: Tiefensuche im Lösungsbaum, Backtracking, Cut
I
Unifikation
I
Lokales Variablenkonzept
I
Closed-World-Assumption: Wahr kann nur sein, was aus eigener
Wissensbasis folgt.
I
Negation as failure: not(Aussage) ist wahr, falls Aussage nicht
bewiesen werden kann.
I
Datenstrukturen, Listen
4 Prolog
Künstliche Intelligenz
4.8 Aufgaben
Folie 4-78 (348)
Aufgaben PROLOG
Aufgabe 4.15 (Anfragen)
Wie löst Prolog – aufbauend auf der in der Vorlesung behandelten
Familienwissensbasis – folgende Anfragen?
I
?-vater_von(juergen,Vater).
I
?-vater_von(ralf,X),vater_von(X,Y).
I
?-vater_von(X,ralf).
I
?-vater_von(X,wolfgang),vater_von(Y,X).
Begründen Sie Ihre Aussagen.
4 Prolog
Künstliche Intelligenz
4.8 Aufgaben
Folie 4-79 (349)
Aufgaben PROLOG
Aufgabe 4.16 (Pfadsuche)
Sei ein gerichteter Graph durch seine Kanten gegeben. Z.B. werden
durch edge(a,b), edge(b,c) usw. Kanten zwischen a und b, b und c
spezifiziert. Definieren Sie ein 2-stelliges Prädikat connected,
welches true liefert, wenn man vom 1. Knoten zum 2. Knoten (auch
über mehrere Kanten) gelangen kann. Welches Problem tritt hier auf?
4 Prolog
Künstliche Intelligenz
4.8 Aufgaben
Folie 4-80 (350)
Aufgaben PROLOG
Aufgabe 4.17 (Länder, Städte)
Spezifizieren Sie die Zusammenhänge zwischen Kontinenten,
Ländern, Hauptstädten. Stellen Sie anschließend Anfragen, z.B. ob
Rom die Hauptstadt von Italien ist, welche Hauptstadt die USA haben,
welche Hauptstädte in Europa liegen etc.
Aufgabe 4.18 (Unifikation)
Was antwortet Prolog auf folgende Fragen? Begründen Sie Ihre
Antwort.
I
?-punkt(X,Y) = punkt(1,2).
I
?-punkt(X,Y) = punkt(1,2,3).
I
?-plus(1,1) = 2.
4 Prolog
4.8 Aufgaben
Künstliche Intelligenz
Folie 4-81 (351)
Aufgaben PROLOG
Aufgabe 4.19 (Viereck)
Sei viereck(P1,P2,P3,P4) die Darstellung eines Vierecks in der
Ebene. Pi seien Punkte punkt(X,Y). Definieren Sie in Prolog
Prädikate, die testen, ob das Viereck ein Parallelogramm, ein
Rechteck oder ein Quadrat ist!
Aufgabe 4.20 (Listen)
Definieren Sie die Listenprädikate reverse/2, kreuzprodukt/3
(kartesisches Produkt) sowie gerade_laenge/1,
ungerade_laenge/1 !
4 Prolog
4.8 Aufgaben
Künstliche Intelligenz
Folie 4-82 (352)
Aufgaben PROLOG
Aufgabe 4.21 (Listen)
Programmieren Sie in Prolog ein Prädikat, welches eine Liste von
Zahlen als Eingabeparameter bekommt und daraus die Liste der
Quadrate berechnet. Beispielsweise soll die Anfrage
?-quadrate([3,2,12],X). die Lösung X=[9,4,144] liefern.
Aufgabe 4.22 (Listen)
Wie müssen Sie obiges Programm modifizieren, wenn Sie Elemente
(der Eingabeliste), die keine Zahlen sind, einfach ausblenden wollen?
Aufgabe 4.23 (Der Cut)
Was unterscheidet das Prädikat el/2 (für das Finden eines Elements
in einer Liste) mit Cut von dem Prädikat ohne Cut?
5 Problemlösung mittels Suche
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
5 Problemlösung mittels Suche
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 5
Problemlösung mittels Suche
Grundlagen der Suche
Bewertungskriterien für Suchverfahren
Uninformierte Suche
Heuristische Suche
Suchverfahren im Überblick
Problemcharakteristika
Vorwärts- und Rückwärtssuche
Zusammenfassung (Suche)
Aufgaben
5 Problemlösung mittels Suche
Künstliche Intelligenz
Folie 5-1 (355)
Problemlösung mittels Suche
Do not believe in miracles – rely on them
Finagl’s Rules
Arthur Bloch, Murphy’s Law, 1981
5 Problemlösung mittels Suche
Künstliche Intelligenz
Folie 5-2 (356)
Motivation
I
Häufig hat man für ein Problem keinen effizienten,
deterministischen Lösungsalgorithmus.
I
Beispiel: Labyrinth, Tourenplanung, . . .
I
Viele solche Probleme lassen sich auf Suchprobleme
zurückführen.
Auch in den KI-Techniken selbst findet man Suchprobleme:
I
Finden eines Beweises
I
Verarbeitung von Regeln
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-3 (357)
Containerlager
Beispiel 5.1 (Container)
In einem Lager müssen Container umgestapelt werden.
I
Es gibt 3 Stellplätze.
I
Container A und B vom linken auf den rechten Stellplatz
transportieren.
I
Container können nur einzeln transportiert werden.
A
Start:
A
Ziel:
B
B
Abb. 40: Containerlager
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-4 (358)
Containerlager – Zustandsraum
A
Start:
B
B
A
B
A
B
A
A
B
B
A
B
B
A
Ziel:
B
A
B
B
A
B
A
A
Ziel:
B
Abb. 41: Containerlager – Suchraum
A
A
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-5 (359)
Suchen
Wie findet man eine Folge von Aktionen, die zum Ziel führt?
I
Für 2 Container trivial.
I
Was, wenn es 50 Container sind?
Möglichkeit: systematisches Suchen
Wann wenden wir Suche an, wann nicht?
I
Suchen: Containerproblem (kein deterministischer
Lösungsalgorithmus bekannt)
I
Wann nicht suchen? Beispielsweise kgV von 2 natürlichen
Zahlen.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-6 (360)
Problemlösung mittels Suche
Wodurch ist das Containerproblem ausgezeichnet?
1. Es gibt einen definierten Ausgangszustand.
2. Der gewünschte Zielzustand ist vorgegeben.
3. Die möglichen Aktionen zum Übergang von einem Zustand zum
nächsten sind bekannt.
Man kann das Containerproblem folglich als Suchproblem in einem
gerichteten Graphen betrachten.
I
Die Knoten sind die Zustände.
I
Die Wurzel des Graphen ist der Ausgangszustand.
I
Die Kanten sind die Zustandsübergänge.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-7 (361)
Problemlösung mittels Suche
Definition 5.1 (Graph)
Ein Graph besteht aus
I
einer Menge N von Knoten und
I
einer Menge E von Kanten.
G = (N , E ), dabei besteht E aus Paaren von Knoten: E ⊆ N × N.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-8 (362)
Problemlösung mittels Suche
Startknoten
noch nicht
untersuchte
Knoten
untersuchte
Knoten
Zielzustand
Grenzknoten
Abb. 42: Suche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-9 (363)
Suchproblem
Definition 5.2 (Suchproblem)
Ein Suchproblem S = (z1 , N , E , ziel) ist definiert durch:
I
Sei (N , E ) ein Graph.
I
z1 ∈ N
I
ziel : N → {W, F}
Gesucht: Folge von Knoten k0 , k1 , . . . , kn mit den Eigenschaften:
1. z1 = k0
2. (ki , ki +1 ) ∈ E
3. ziel(kn ) = W
für i = 0, . . . , n − 1
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-10 (364)
Andere Definition für Suche
I
Suche ist das Aufzählen einer Menge von potentiellen
Teillösungen
I
Man braucht dazu:
I
I
I
Definition einer partiellen Lösung
Methode zum Generieren der potentiellen Lösungen
Methode zum Testen, ob eine potentielle Lösung eine Lösung ist
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-11 (365)
Darstellung von Zustandsübergängen
Für das Containerbeispiel sieht eine Zustandsfolge zum Zielzustand
wie folgt aus:
[[A, B ], [ ], [ ]] → [[B ], [A], [ ]] → [[ ], [A], [B ]] → [[ ], [ ], [A, B ]]
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-12 (366)
Prinzip 1 für Suche
Meist ist es unsinnig, mehrmals durch den gleichen Zustand zu laufen.
Beispiel 5.2 (Wasserproblem)
I
Wir möchten 2 Liter exakt abfüllen.
I
Wir haben nur 2 kleine Kanister (ohne Skalen): 3 Liter, 4 Liter
Dieses Problem kann man durch Suchen lösen.
I
Der Ausgangszustand: Beide Gefäße sind leer.
I
Der Zielzustand: In mindestens einem Gefäß sind exakt 2 Liter.
I
Es gibt nur 3 mögliche Aktionen, die man ausführen kann:
1. Auffüllen eines Gefäßes
2. Ausschütten eines Gefäßes
3. Umfüllen des Inhaltes eines Gefäßes in das andere
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-13 (367)
Prinzip 1 für Suche
0
4
4
1
3
3
0
0
0
0
4
0
3
3
3
3
0
0
0
3
Zustände kommen mehrfach vor.
4
2
Abb. 43: Wasserbeispiel – Suchraum
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-14 (368)
Prinzip 1 für Suche
Eine andere Darstellung ist folgende:
[0,0]
*
@
I
@
R
@
@
[0,3]
[4,0]
1
@
@
I
@
I
@
6@
R
R
@
@
@
[3,0]
[4,3] [1,3]
@
I
@
6 R
@
@
[3,3]
[1,0]
Y
H
H
j
[4,2]
Abb. 44: Wasserbeispiel – Suchraum (Ausschnitt)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-15 (369)
Doppelte Zustände
Ist es sinnvoll, mehrmals durch den Zustand [0, 3] zu laufen?
[0, 0] → [0, 3] → [4, 3] → [4, 0] → [1, 3] → [1, 0] → [0, 1] → [0, 3]
Man sieht sofort, dass dies nicht sinnvoll ist.
[0, 0] → [0, 3] → [4, 3] → [4, 0] → [1, 3] → [1, 0] → [0, 1] → [0, 3] . . . [4, 2]
Cycle checking
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-16 (370)
Prinzip 2 für Suche
Der Suchraum muss systematisch und vollständig durchsucht werden.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-17 (371)
Praktische (Such-)Probleme
I
Tourenplanung (Suche nach einer günstigen Route),
I
Planungsprobleme wie Produktionsplanung (günstige Folge von
Arbeitsschritten) sowie
I
Diagnoseprobleme, wo in einer großen Zahl von
Kombinationsmöglichkeiten gesucht wird.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-18 (372)
Beispiel – Schach
I
Ausgangszustand
I
Zielzustände (gegnerischer König im Matt, eigener König nicht
bedroht)
I
wohldefinierte Zustandsübergänge (Aktionen)
Der Zustandsraum ist auch hier ein gerichteter Graph.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-19 (373)
Problem beim Schach
I
Wie gewinnt man sicher?
I
Wie wählt man einen sicheren Zug aus?
Diese Aufgabe kan man dem Computer übertragen.
I
Komplettes Durchsuchen aller Möglichkeiten nötig.
I
Problem auf Suche reduziert
Man unterscheidet:
I
Suche ohne Zusatzinfos: uninformierte Suche
I
Zusatzinfos wie Kosten oder Heuristiken: heuristische/informierte
Suche.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-20 (374)
Problem – Komplexität
I
Komplexität beim Schach zu groß.
I
Systematische, uninformierte Suche nicht erfolgreich.
I
Mit informierter Suche z.T. schon erfolgreich.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.1 Grundlagen der Suche
Folie 5-21 (375)
Suche mittels Computer
I
Ziel ist Suche mittels eines Computer-Programms.
I
Wir müssen alle erforderlichen Informationen computergeeignet
darstellen.
Beispiel 5.3 (Wasserproblem)
Startzustand beim Wasser-Problem:
[0,0]
Der Zielzustand muss einem der beiden Muster genügen:
[_,2] oder [2,_]
Auffüllen des linken Gefäßes:
zustandsuebergang([_,Drei],[4,Drei])
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.2 Bewertungskriterien für Suchverfahren
Folie 5-22 (376)
Bewertungskriterien für Suchverfahren
Vollständigkeit Findet das Suchverfahren immer eine Lösung, falls
eine existiert?
Zeitkomplexität Wie lange braucht das Verfahren zum Finden einer
Lösung?
Speicherplatzkomplexität Wieviel Speicherplatz braucht das
Verfahren zum Finden einer Lösung?
Optimalität
Ist die gefundene Lösung optimal (falls ein
Optimalitätskriterium vorliegt)?
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-23 (377)
Uninformierte Suche
Sei
I
Kand . . . die Liste der Kandidaten von Wegen, die zu untersuchen
sind,
I
z1 . . . der Ausgangszustand,
I
z und s . . . Zustände (Knoten des Graphen)
I
p . . . Weg durch den Zustandsraum.
5 Problemlösung mittels Suche
und
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-24 (378)
Uninformierte Suche
FUNCTION Suche
Kand := [z1 ]; Ziel_erreicht := false;
REPEAT
Wähle aus Kand einen Weg aus: p := z1 z2 . . . zm
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Berechne alle Folgezustände von zm : [s1 , . . . , sk ]
Lösche p aus Kand heraus;
Füge z1 . . . zm s1 , z1 . . . zm s2 ,. . .,z1 . . . zm sk in Kand ein;
ENDIF
UNTIL Ziel_erreicht;
RETURN p;
END
Abb. 45: Uninformierte Suche
5 Problemlösung mittels Suche
5.3 Uninformierte Suche
Künstliche Intelligenz
Folie 5-25 (379)
Frage
Bemerkung 5.3 (Zwischenzustände)
Warum merken wir uns die ganzen Zwischenzustände?
I
Inhaltliches Argument: Bei vielen Problemen interessiert uns
nicht nur, ob wir zu einem Zielzustand gelangen, sondern auch
wie (Bspl. Wasserproblem).
I
Technisches Argument: Wir möchten nicht mehrfach durch den
gleichen Zustand laufen (s.o). Wir müssen uns also merken,
welche Zustände wir bereits durchlaufen haben.
5 Problemlösung mittels Suche
5.3 Uninformierte Suche
Künstliche Intelligenz
Folie 5-26 (380)
Freiheitsgrade im Algorithmus
Im folgenden: Nehmen immer erstes Element der Kandidatenliste.
Welche Freiheitsgrade im Algorithmus haben wir?
I
Einfügen der neuen Pfade in die Kandidatenliste
I
Sortieren der Kandidatenliste
2 Varianten:
1. Fügt man die neuen Pfade an den Anfang der Liste der
Kandidaten ein: Tiefensuche,
2. Fügt man sie am Schluss an: Breitensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-27 (381)
5.3.1 Breitensuche
Breitensuche
FUNCTION Breitensuche
Kand := [z1 ]; Ziel_erreicht := false;
REPEAT
Sei Kand = [z1 z2 . . . zm , p2 , . . . , pn ]
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Berechne alle Folgezustände von zm : [s1 , . . . , sk ]
Lösche p = z1 z2 . . . zm aus Kand heraus;
⇒
Kand := [p2 , . . . , pn , z1 . . . zm s1 , . . . , z1 . . . zm sk ];
ENDIF
UNTIL Ziel_erreicht;
RETURN z1 z2 . . . zm ;
END
Abb. 46: Breitensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-28 (382)
5.3.1 Breitensuche
Wasserbeispiel – Breitensuche
0
4
4
0
3
0
1
3
0
0
3
4
3
4
0
3
3
3
0
3
Abb. 47: Wasserbeispiel – Breitensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-29 (383)
5.3.2 Tiefensuche
Tiefensuche
FUNCTION Tiefensuche
Kand := [z1 ]; Ziel_erreicht := false;
REPEAT
Sei Kand = [z1 z2 . . . zm , p2 , . . . , pn ]
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Berechne alle Folgezustände von zm : [s1 , . . . , sk ]
Lösche p = z1 z2 . . . zm aus Kand heraus;
⇒
Kand := [z1 . . . zm s1 , . . . , z1 . . . zm sk , p2 , . . . , pn ];
ENDIF
UNTIL Ziel_erreicht;
RETURN z1 z2 . . . zm ;
END
Abb. 48: Tiefensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-30 (384)
5.3.2 Tiefensuche
Wasserbeispiel – Tiefensuche
0
4
0
3
0
4
0
1
3
3
4
3
3
4
0
0
0
0
0
0
Abb. 49: Wasserbeispiel – Tiefensuche
3
0
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-31 (385)
5.3.2 Tiefensuche
Breiten- und Tiefensuche
I
Der oberste Knoten sei der Ausgangszustand.
I
Wann erreichen die Verfahren die Knoten?
1
1
@
R
3
2
@
R
@
R
5 6
7
4
@
@
R
R
8
9
10
@
R
7
2
@
R
@
R
3
6 8
9
@
@
R
R
5
10
4
Abb. 50: Breiten- und Tiefensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-32 (386)
5.3.2 Tiefensuche
Tiefensuche
Ausgangszustand: Knoten A, Zielzustand: Knoten G
Tiefensuche
akt. Kandidat
A
@
R
B
C
@
R
@
R
D
E F
G
@
@
R
R
J
H
K
A
A-B
A-B-D
A-B-D-H
A-B-D-J
A-B-E
A-C
A-C-F
A-C-G
Kandidatenliste
A
A-B, A-C
A-B-D, A-B-E, A-C
A-B-D-H, A-B-D-J,
A-B-E, A-C
A-B-D-J, A-B-E, A-C
A-B-E, A-C
A-C
A-C-F, A-C-G
A-C-G
Lösung
Abb. 51: Beispiel: Tiefensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-33 (387)
5.3.2 Tiefensuche
Breitensuche
Ausgangszustand: Knoten A, Zielzustand: Knoten G
Breitensuche
akt. Kandidat
A
@
R
A
B
C
A-B
@
R
@
R
D
E F
G
A-C
@
@
R
R
J
H
K
A-B-D
A-B-E
A-C-F
A-C-G
Kandidatenliste
A
A-B, A-C
A-C, A-B-D, A-B-E
A-B-D, A-B-E, A-C-F,
A-C-G
A-B-E, A-C-F, A-C-G,
A-B-D-H, A-B-D-J
A-C-F, A-C-G, A-B-D-H,
A-B-D-J
A-C-G, A-B-D-H, A-B-D-J
Lösung
Abb. 52: Beispiel: Breitensuche
5 Problemlösung mittels Suche
5.3 Uninformierte Suche
5.3.3 Vor- und Nachteile beider Verfahren
Vor- und Nachteile beider Verfahren
I
Tiefensuche kann eine Lösung sehr schnell finden.
I
Tiefensuche muss eine Lösung nicht unbedingt finden.
I
Ist „linker“ Teilbaum unendlich groß und enthält keinen
Zielzustand, so findet Tiefensuche keine Lösung.
I
Tiefensuche ist in diesem Fall also unvollständig.
I
Breitensuche rennt nicht blind in einen Zweig hinein.
I
Breitensuche ist vollständig und fair.
Künstliche Intelligenz
Folie 5-34 (388)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-35 (389)
5.3.4 Komplexität von Tiefen- und Breitensuche
Komplexität von Tiefen- und Breitensuche
Wie hoch ist der Platz- und Zeitbedarf beider Verfahren?
I
Betrachten ungünstigsten Fall.
I
Betrachten gerichteten Baum mit der Tiefe T sowie einer
Verzweigungsrate V .
I
Alle Zielknoten liegen auf der untersten Ebene.
Insgesamt enthält der Baum
1 + V + V 2 + ... + V T = O (V T )
Knoten. Das liegt in der Größenordnung von V T .
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-36 (390)
5.3.4 Komplexität von Tiefen- und Breitensuche
Komplexität – 2
Die Schreibweise O (V T ) bedeutet, dass ein k und ein V0 existieren,
so dass für alle V ≥ V0 gilt:
1 + V + V 2 + ... + V T < k ∗ V T
I
Ungünstigster Fall (Lösung „unten rechts“): beide Verfahren
gleich O (V T )
I
Durchschnittlicher Fall (Lösung liegt irgendwo in der untersten
Ebene):
I Breitensuche: O (V T )
I Tiefensuche: T . . . O (V T )
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.3 Uninformierte Suche
Folie 5-37 (391)
5.3.4 Komplexität von Tiefen- und Breitensuche
Komplexität – 3 : Speicherbedarf
I
Breitensuche – worst case (komplette Ebene T bereits als
Kandidaten): O (V T ) Kandidaten gespeichert
I
Tiefensuche – worst case (erster Knoten in der Ebene T
erreicht): T ∗ (V − 1)
5 Problemlösung mittels Suche
5.3 Uninformierte Suche
Künstliche Intelligenz
Folie 5-38 (392)
5.3.5 Iterative Deepening
Iterative Deepening
I
Existiert Verfahren, welches die Vorteile von
I
I
Tiefensuche (Komplexität) und
Breitensuche (Fairness, Vollständigkeit)
kombiniert?
I
Idee: Tiefensuche mit Beschränkung der Tiefe der Kandidaten
I
Findet man keine Lösung: Lockern der Tiefenbeschränkung.
; Schrittweise Vertiefung (Iterative Deepening).
I
Zeitbedarf: analog Breitensuche (O (V T ))
I
Speicherplatzbedarf: analog Tiefensuche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-39 (393)
Heuristische Suche
I
Tiefen- und Breitensuche scheitern häufig bei größeren
Suchproblemen
I
. . . aufgrund der großen Komplexität.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-40 (394)
Handelsreisender (Travelling salesman problem)
I
Ein Reisender soll n Städte besuchen; jede genau einmal.
I
Gesucht ist die kürzeste Strecke.
I
(n-1)! Möglichkeiten (exakt:
I
Konsequenz: systematische Suche wie Breiten- oder
Tiefensuche nicht ausreichend.
(n−1)!
2
) ; exponentieller Aufwand
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-41 (395)
Zusatzinfos und Heuristiken
I
Folglich zusätzliche Kriterien erforderlich, die den Suchraum
strukturieren oder eingrenzen
I
Strukturieren = Modifikation der Reihenfolge der Abarbeitung der
Kandidaten
I
Eingrenzung des Suchraums = Abschneiden von Zweigen im
Suchraum
I
Bei vielen Problemen: Zusatzinformationen verfügbar wie
Entfernungen, Kosten, Materialverbrauch
I
Diese Informationen werden bei der Breiten- und Tiefensuche
jedoch nicht benutzt.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-42 (396)
Suche und verfügbare Infos
I
Schätzung des Abstands zum Ziel: h
I
Bisherige Kosten: g
Abb. 53: Bewertungsfunktionen
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-43 (397)
Suche – verfügbare Infos
Wozu die Schätzfunktion h?
I
Bisherige Kosten bekannt: einfach summieren
I
Wenn wir noch wüssten, wie weit wir (kostenmäßig) von einer
Lösung entfernt sind . . .
Summe der bisherigen Kosten + noch entstehende Kosten.
I
Wählen besten Kandidaten
I
Entfernung zum Ziel leider unbekannt
I
Meist kann man sie jedoch schätzen.
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Einfache Bewertungsfunktionen
I
g: Bisherige Schritte
I
h: Geschätzte Zahl der noch nötigen Schritte
Künstliche Intelligenz
Folie 5-44 (398)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-45 (399)
Steine-Beispiel
Beispiel 5.4 (Steine-Beispiel)
Auf einem Brett liegen 4 Steine, 2 weiße und 2 schwarze:
W
W
S
S
Zwischen den Steinen ist ein freies Feld.
Es soll folgender Zustand hergestellt werden:
S
S
W
W
Dazu darf man:
I
schieben (Kosten 1)
I
über 1 Stein springen (Kosten 1)
I
über 2 Steine springen (Kosten 2)
Wie findet man eine Zugfolge mit minimalen Aufwand?
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-46 (400)
5.4.1 Nearest Neighbour Heuristik
Nearest Neighbour Heuristik
Eine typische Heuristik ist die nearest neighbour heuristic. Beim
travelling salesman sieht sie so aus:
1. Beliebige Start-Stadt wählen.
2. Wähle aus den noch nicht besuchten Städten die zur aktuellen
Stadt am nächsten gelegene Stadt aus.
3. Falls noch nicht alle Städte besucht sind, gehe zu 2.
Voraussetzung für NNH: Aufwandsmaß g für die Kosten der
Zustandsübergänge
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-47 (401)
5.4.1 Nearest Neighbour Heuristik
Nearest Neighbour Heuristik – Rundreiseproblem
Typisches Verhalten von NNH:
I
Betrachten 6 kreisfreie Städte in MV.
I
Als Startstadt wird Wismar gewählt.
I
Die gefundene Lösung ist nicht optimal.
Stralsund
Rostock
Greifswald
Wismar
Neubrandenburg
Schwerin
Abb. 54: Rundreiseproblem für die 6 kreisfreien Städte mit NNH
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-48 (402)
5.4.1 Nearest Neighbour Heuristik
Nearest Neighbour Heuristik – Algorithmus
FUNCTION NNH
p := z1 ;
Ziel_erreicht := false;
REPEAT
Sei p = z1 z2 . . . zm
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Suche nächstgelegenen Nachbarn von zm : x
p := z1 z2 . . . zm x
ENDIF
UNTIL Ziel_erreicht;
RETURN p;
END
Abb. 55: NNH – Algorithmus
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-49 (403)
5.4.1 Nearest Neighbour Heuristik
Nearest Neighbour Heuristik
I
NNH ist ein typisches Lowest-cost-first-Verfahren.
I
NNH ignoriert das Ziel, konzentriert sich allein auf die lokalen
Kosten.
I
NNH hat kein Backtracking.
Alternativ:
I
Backtracking zulassen
I
Gesamte bisherige Pfadkosten betrachten
I
Mit dem billigsten weiterarbeiten
I
Führt zu einer Art Breitensuche.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-50 (404)
5.4.2 Hill climbing
Hill climbing
I
Voraussetzung: heuristische Funktion h
(Qualität eines Lösungsvorschlags, Abstand zum Ziel)
I
hill climbing: Folgezustand wird nur dann akzeptiert, wenn dieser
„näher“ zum Ziel liegt.
I
wird auch Bergsteiger-Strategie genannt
I
erlaubt Backtracking (in vielen Quellen ohne Backtracking)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-51 (405)
5.4.2 Hill climbing
Hill climbing – Algorithmus
FUNCTION HILL CLIMBING
Kand := [z1 ];
Ziel_erreicht := false;
REPEAT
Wähle aus Kand einen Weg: p := z1 z2 . . . zm ;
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Berechne alle Folgezustände (von zm ) [s1 , . . . , sk ],
für die gilt: h(zm ) ≥ h(si );
Füge für alle si die Wege z1 z2 . . . zm si in Kand ein;
Lösche p aus Kand heraus;
ENDIF
UNTIL Ziel_erreicht;
RETURN p;
END
Abb. 56: Hill Climbing – Algorithmus
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-52 (406)
5.4.3 Bestensuche
Bestensuche
I
Kombination von Tiefen- und Breitensuche
I
verwendet heuristische Funktion h
Idee: Wir nehmen den Kandidaten, dessen Bewertung am besten ist
und suchen auf diesem Pfad weiter.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-53 (407)
5.4.3 Bestensuche
Bestensuche – Algorithmus
FUNCTION BESTENSUCHE
Kand := [z1 ];
Ziel_erreicht := false;
REPEAT
Wähle aus Kand den besten (h) Weg: p := z1 z2 . . . zm ;
Ziel_erreicht := ziel(zm );
IF NOT Ziel_erreicht THEN
Berechne alle Folgezustände (von zm ) [s1 , . . . , sk ];
Füge die Wege z1 z2 . . . zm s1 , . . . , z1 z2 . . . zm sk in Kand ein;
Lösche p aus Kand heraus;
ENDIF
UNTIL Ziel_erreicht;
RETURN p;
END
Abb. 57: Bestensuche – Algorithmus
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
5.4.4 A∗ -Suche
A∗ -Suche
Heuristische Funktionen g , h für:
I
Kosten für bisherigen Pfad: g
I
Abstandsmaß (aktueller Knoten → Zielzustand): h
Die Kandidaten werden durch die Summe beider heuristischer
Funktionen f = g + h bewertet.
Folie 5-54 (408)
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-55 (409)
5.4.4 A∗ -Suche
A∗ -Suche – Motivation
Betrachten das Wasserproblem:
I
I
[0, 0] → [0, 3]
[0, 0] → [4, 0] → [1, 3] → [0, 3]
Beobachtung:
I
Zustand [0, 3] über mehrere Wege erreichbar
I
Wir müssen nur den „besseren“ weiterverfolgen.
I
Multiple path pruning (MPP) / Karo-Effekt
Dies wird im A∗ -Algorithmus ausgenutzt.
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-56 (410)
5.4.4 A∗ -Suche
Implementierung
Der A∗ -Algorithmus wird anders als beispielsweise die Breitensuche
umgesetzt. Man verwaltet zwei Mengen von Zuständen:
I
OPEN: Knoten (bewertet, aber noch nicht expandiert)
I
CLOSED: Knoten (bewertet und expandiert)
Mit Expandieren ist hier das Berechnen aller Nachfolger gemeint.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-57 (411)
5.4.4 A∗ -Suche
A∗ -Suche – Algorithmus
FUNCTION A-STERN
OPEN := [z1 ];
CLOSED := [ ];
Ziel_erreicht := false;
REPEAT
x := bester Knoten (bez. f) aus OPEN;
Ziel_erreicht := ziel(x);
IF NOT Ziel_erreicht THEN
Lösche x in OPEN und füge x in CLOSED ein;
SUCCESSORS := alle Nachfolger von x;
FORALL y∈ SUCCESSORS
IF y∈ OPEN OR y∈ CLOSED THEN
Vergleiche alten/neuen Weg, verwirf schlechteren;
ELSE
Füge y in OPEN ein;
ENDIF
ENDFORALL
ENDIF
UNTIL Ziel_erreicht;
RETURN x;
END
Abb. 58: A∗ -Suche
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-58 (412)
5.4.4 A∗ -Suche
A∗ -Suche – Beispiel
a5
J 3
2
2J
^
? J
b2 c6 d4
J
J
2 3
2
J
J2
J
J
^?
^
e2
f 3
J 3
1
J
1
J
^
g5
h3
J
2
J1
J
^
j 0
i 3
Abb. 59: A-Stern – Beispiel
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-59 (413)
5.4.4 A∗ -Suche
A∗ -Suche – Beispiel
a5
Suchraum:
a5
2 2J 3
?J^
J
b2 c6 d4
3J 2 2 J 2
J^
J^
J?
J
e2
f3
1 J 3 1
J^
J
g5
h3
2 J1
J^
J
j0
i3
a
J
J
^
? J
c
8 d7
b4
a
J
J
^
? J
c
8 d7
b
J
J
J
^
e7
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-60 (414)
5.4.4 A∗ -Suche
A∗ -Suche – Beispiel
a
Suchraum:
a5
2 2J 3
?J^
J
b2 c6 d4
3J 2 2 J 2
J^
J^
J?
J
e2
f3
J
3
1
1
J^
J
g5
h3
2
J1
J^
J
j0
i3
a
a
J
J
J
J
J
J
^
^
^
? J
? J
? J
c8 d
c8 d
c
b
b
b
d
J
J
J
J
J
J
J
J
J
J
J
J
J
J
J
^
^
^
^
^
?
e7
e
e
f 8
f 8
f 8
J
J
J
J
J
J
^
^
10 g
11 g
h11
h10
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-61 (415)
5.4.4 A∗ -Suche
A∗ -Suche – Beispiel
a
a
Suchraum:
a5
2 2J 3
?J^
J
b2 c6 d4
3J 2 2 J 2
J^
J^
J
J?
e2
f3
J
3
1
1
J^
J
g5
h3
2
J1
J^
J
j0
i3
J
J
^
? J
c
b
d
10 g
?
e
J
J
^
? J
c
b
d
J
J
J
^
?
e
f
10 g
h9
h
J
J
J
^
f
J
J
J
^
j 7
11 i
Abb. 60: Beispiel – A-Stern
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-62 (416)
5.4.4 A∗ -Suche
Ablauf der A∗ -Suche
Suchraum:
Expand.
Knoten
a5
J3
2
2
J
?J^
b2 c6 d4
J 2 2 J 2
3
J^
J?
e2
J^
J
1
J3
g5
f3
1
J^
J
h3
2
J1
J^
J
i3
j0
0
1 a
2 b
3 d
4
5
6
7
8
e
c
f
h
j
OPEN
CLOSED
a/5
b/4, c/8, d/7
c/8, d/7, e/7
c/8, e/7, f/8
a
a, b
a, b, d
Bemerkung
Wir hätten auch e
nehmen können.
c/8, f/8, g/11, h/11 a, b, d, e
f/8, g/10, h/10
a, . . . , e auch f möglich
g/10, h/9
a, . . . , f
g/10, i/11, j/9
a, . . . , f, h
g/10, i/11
a, . . . , f, h, j Lösung
Abb. 61: Beispiel – A-Stern
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-63 (417)
5.4.4 A∗ -Suche
Implementierung
I
I
Pointer zwischen den Knoten:
I Knoten → Nachfolger
I Knoten → bester Vorgänger
Findet man einen besseren Vorgänger eines Knotens:
I
I
Pointer auf den besten Vorgänger ersetzen
Weitergeben der neuen (besseren) Bewertung auf alle
Folgezustände (und deren Folgezustände etc.).
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-64 (418)
5.4.4 A∗ -Suche
Optimallösung ?
Satz 5.4 (Optimallösung)
Überschätzt die Funktion h die tatsächlichen Kosten g nicht, so findet
der A∗ -Algorithmus die Optimallösung. Eine solche Funktion h heißt
zulässig.
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-65 (419)
5.4.5 Ein Beispiel
Das Hängebrückenproblem
I
Vier Personen möchten nachts eine Hängebrücke benutzen.
I
Aus Sicherheitsgründen muss dabei eine Taschenlampe benutzt
werden.
I
Die Batterie der Lampe reicht genau für 60 Minuten.
I
Außerdem dürfen höchstens 2 Personen gleichzeitig auf der
Hängebrücke sein.
I
Die Lampe kann nicht zurückgeworfen werden, sie muss
übergeben werden.
I
Die Personen sind unterschiedlich schnell. Sie benötigen für eine
Strecke: Anna: 5 min, Boris: 10 min, Clara: 20 min, Dirk: 25 min.
5 Problemlösung mittels Suche
5.4 Heuristische Suche
5.4.5 Ein Beispiel
Das Hängebrückenproblem
Wir möchten A∗ anwenden. Dazu brauchen wir
1. eine Darstellung für einen Zustand,
2. den Start- und Zielzustand,
3. eine Darstellung für korrekte Zustandsübergänge,
4. eine Kostenfunktion (g) und
5. eine Schätzung für die Entfernung zum Ziel (h).
Künstliche Intelligenz
Folie 5-66 (420)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-67 (421)
5.4.5 Ein Beispiel
Das Hängebrückenproblem – Darstellung eines Zustands
Welche Informationen müssen wir darstellen?
I
Wer ist auf welcher Seite?
I
Wo ist die Lampe?
I
Wieviel Zeit ist verbraucht?
Mögliche Darstellung durch Liste. [[l,a,b],[c,d],20] stellt dar, dass
I
die Lampe, Anna und Boris auf der linken Seite der Brücke sind,
I
die beiden anderen rechts.
I
Verbraucht wurden bisher 20 Minuten.
Startzustand: [[l,a,b,c,d],[],0].
Zielzustand: [[],[l,a,b,c,d],_].
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-68 (422)
5.4.5 Ein Beispiel
Das Hängebrückenproblem – Zustandsübergänge
Korrekter Zustandsübergang:
I
Von links nach rechts: 2 Personen (mit der Lampe)
I
Zurück immer nur 1 Person (mit Lampe).
Wann können X und Y von links nach rechts gehen?
1. Die Lampe ist links.
2. X und Y sind links.
Welche Zeit wird dabei verbraucht? Das Maximum des Zeitbedarfs
von X und Y.
Analog definiert man, dass X von rechts nach links geht.
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-69 (423)
5.4.5 Ein Beispiel
Formale Regeldarstellung
Formal kann man eine Regel (für das Laufen von links nach rechts) in
einer Prolog-Notation wie folgt darstellen:
zustandsuebergang([L,R,T],[L1,[l,X,Y|R],T1]) :del(l,L,La),
% Lampe ist links
del(X,La,L2),
% X ist links
del(Y,L2,L1),
% Y ist links
zeit(X,Time1), zeit(Y,Time2), % Zeit für X & Y
Max is max(Time1,Time2), % davon das Maximum
T1 is T+Max,
% verbrauchte Gesamtzeit
T1 =< 60.
% darf 60 nicht übersteigen
5 Problemlösung mittels Suche
5.4 Heuristische Suche
Künstliche Intelligenz
Folie 5-70 (424)
5.4.5 Ein Beispiel
Das Hängebrückenproblem – Kostenfunktion
Die Kosten (g) ergeben sich durch den Zeitbedarf der Personen.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.4 Heuristische Suche
Folie 5-71 (425)
5.4.5 Ein Beispiel
Das Hängebrückenproblem – Schätzfunktion h
Wie kann man die noch zu erwartenden Kosten schätzen?
Betrachten wir dazu exemplarisch den Zustand
[[l,a,c,d],[b],15].
Zeitbedarf, um a, c, d von links nach rechts zu bringen?
I
Minimal 5 + 25 Minuten (a geht allein, c und d zusammen).
I
Zusätzlich muss Lampe zurückgebracht werden (jedes Mal
mindestens 5 Minuten, falls immer a ginge).
Schätzfunktion, überschätzt tatsächliche Kosten garantiert nicht.
Sie ist also zulässig.
Ergänzung: Unter www.plastelina.net/game7.html findet man eine
Reihe guter Aufgaben, die mit Suchverfahren lösbar sind.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.5 Suchverfahren im Überblick
Folie 5-72 (426)
Suchverfahren im Überblick
Verfahren
Breitensuche
Tiefensuche
Bestensuche
Bergsteiger
nearest
neighbour
A∗
Charakteristika
h
h
Alte Kandidaten zuerst
Neue Kandidaten zuerst
Kandidat mit bestem h-Wert zuerst
Folgezustände dürfen nicht schlechter
(bezüglich h) sein.
g Knoten mit geringsten Kosten (g) wird
genommen.
g+h Bestensuche mit g+h, Mehrfachwege
werden vermieden.
Tabelle 9: Suchverfahren
Backtracking
ja
ja
ja
ja
nein
ja
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.5 Suchverfahren im Überblick
Folie 5-73 (427)
Varianten
Bemerkung 5.5 (Varianten der Suchverfahren)
Breiten-/Tiefensuche MPP möglich
Bestensuche MPP möglich
Bergsteiger
MPP möglich, ebenso Backtrackingverbot (meist
unsinnig).
In vielen Quellen: ohne Backtracking, gierige Suche
(bester Kandidat).
Nearest Neighbour Backtracking bei gleichguten Kandidaten
Dijkstra-Algorithmus Bester Kandidat bezüglich bisherigen g-Kosten.
Backtracking. MPP.
5 Problemlösung mittels Suche
5.5 Suchverfahren im Überblick
Künstliche Intelligenz
Folie 5-74 (428)
Suchverfahren – Aufgaben des Nutzers und des Programm
Der Nutzer muss folgende Infos bereitstellen:
I
Startzustand
I
Zielzustände
I
Korrekte Zustandübergänge
I
g – Kosten für EINEN Zustandsübergang
I
h – geschätzte Entferung zum Ziel
Aufgaben des Suchprogramms:
I
Verwaltung der Kandidaten
I
Auswahl des nächsten Kandidaten
I
Summieren der bisherigen Kosten
I
Berechnung von g+h
I
Cycle checking
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.6 Problemcharakteristika
Folie 5-75 (429)
Problemcharakteristiken
Wie ordnet sich Suche in die allgemeine Problemlösung ein? Ein
typisches Vorgehen bei der Problemlösung ist:
1. Problemdefinition
2. Analyse des Problems
3. Isolieren des für das Problem wichtigen Wissens und Wahl einer
geeigneten Repräsentationsform
4. Auswahl einer passenden Problemlösungstechnik
Gelingt es, das Problem mit Hilfe eines Suchraumes (Ausgangs- und
Zielzustand, Zustandsübergänge) zu definieren, kann im Schritt 4 ein
Suchverfahren eingesetzt werden.
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.6 Problemcharakteristika
Folie 5-76 (430)
Kleine Suchräume durch Problemcharakteristika
I
Ist das Problem zerlegbar? (Container, Zerlegen in Teilprobleme)
I
Kann man Lösungsschritte ignorieren? (beispielsweise Vergleich
mit lokal bester Lösung)
I
Ist die Lösung ein Zustand oder ein Pfad? (Bspl. Wasserproblem:
Pfad oder mehrdeutige Interpretation eines Satzes: Zustand)
5 Problemlösung mittels Suche
5.7 Vorwärts- und Rückwärtssuche
Künstliche Intelligenz
Folie 5-77 (431)
Vorwärts- und Rückwärtssuche
I
Suche beginnt beim Ausgangszustand: Vorwärtssuche
I
Suche beginnt beim Zielzustand: Rückwärtssuche
5 Problemlösung mittels Suche
5.7 Vorwärts- und Rückwärtssuche
Künstliche Intelligenz
Folie 5-78 (432)
Weitere Suchverfahren
I
Simulated Annealing
I
Threshold Accepting
I
Iterative Broadening
I
Constraint-Satisfaction-Verfahren
I
Min-Max- oder α/β-Verfahren
I
Branch-and-bound (Beschränkung durch beste bisher gefundene
Lösung)
5 Problemlösung mittels Suche
5.8 Zusammenfassung (Suche)
Künstliche Intelligenz
Folie 5-79 (433)
Das sollten Sie wissen . . .
Zusammenfassung 5.6 (Suche)
I
Grundprinzip der Problemlösung mittels Suche
I
Wann Suche?
I
Uninformierte / informierte Suche
I
Suchverfahren
I
Suchstrategien
I
Heuristische Funktionen
5 Problemlösung mittels Suche
5.9 Aufgaben
Künstliche Intelligenz
Folie 5-80 (434)
Aufgaben Suche
Aufgabe 5.1 (Suchprobleme)
Finden Sie weitere Problem-Beispiele, die sich als Suchproblem (d.h.
als Zustandsübergangsproblem mit Ausgangs- und Zielzustand)
darstellen lassen! Finden Sie Beispiele, die auf dieses Konzept nicht
passen!
Aufgabe 5.2 (Suchprobleme)
Kennen Sie Beispiele, wo es durchaus sinnvoll ist, das zweimalige
Durchlaufen des gleichen Zustands zuzulassen?
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.9 Aufgaben
Folie 5-81 (435)
Aufgaben Suche
Aufgabe 5.3 (Suchraum)
Folgender Suchraum sei gegeben.
Der Startzustand sei a, der Zielzustand sei h. Wie gelangt der A∗ Algorithmus zur Lösung? In welcher Reihenfolge werden die Kandidaten durchlaufen? Ist die verwendete Schätzfunktion zulässig?
Und wie gehen die anderen Suchstrategien hier vor?
a5
1
J2
J
^
c2
3b
2
2J
J
^
d3
1 J3
J
^
5e
f3
2
J1
J
^
3g
h0
5 Problemlösung mittels Suche
5.9 Aufgaben
Aufgaben Suche
Aufgabe 5.4 (A∗ -Suche)
Wo sehen Sie Vorteile des A∗ -Algorithmus?
Aufgabe 5.5 (Best-First- und Breitensuche)
Erläutern Sie Best-First-Suche und Breitensuche! Wann ist
Best-First-Suche schlechter als Breitensuche?
Künstliche Intelligenz
Folie 5-82 (436)
5 Problemlösung mittels Suche
Künstliche Intelligenz
5.9 Aufgaben
Folie 5-83 (437)
Aufgaben Suche
Aufgabe 5.6 (8 Puzzle)
Betrachten Sie das 8-Puzzle-Problem (Schiebefax) und entwickeln Sie
dafür ein Suchverfahren. (Schiebefax: 3x3-Quadrat mit verschiebbaren
Feldern (1-8), ein Freifeld. Man soll die Felder durch Verschieben in
die richtige Reihenfolge bringen, d.h. 1. Zeile 1-3, 2. Zeile 4-6, 3. Zeile
7-8 u. Freifeld)
Kann man den A∗ -Algorithmus einsetzen? Entwickeln Sie geeignete
heuristische Funktionen. Ist Ihre geschätzte Distanz zum Ziel
zulässig?
Erläutern Sie Ihr Vorgehen am Beispiel des Startzustands:
5 Problemlösung mittels Suche
7
6
1
2
5
3
8
4
Künstliche Intelligenz
5.9 Aufgaben
Folie 5-84 (438)
Aufgaben Suche
Aufgabe 5.7 (Hill climbing)
Wenn Hill climbing ohne Backtracking implementiert wird, welcher
Suchstrategie ähnelt das Verfahren dann am meisten?
Aufgabe 5.8 (Steine)
Finden Sie für das Steine-Beispiel (Beispiel 5.4) eine zulässige
Schätzfunktion h.
6 Neuronale Netze
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
6 Neuronale Netze
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 6
Neuronale Netze
Historie und biologische Aspekte
Funktionsweise
Ein einfaches Neuronenmodell
Verallgemeinertes Modell
Zusammenfassung (Neuronale Netze)
Aufgaben
6 Neuronale Netze
Künstliche Intelligenz
Folie 6-1 (441)
Neuronale Netze
Nothing ever comes out as planned.
Seay’s Law, Murphy’s Law
6 Neuronale Netze
Künstliche Intelligenz
6.1 Historie und biologische Aspekte
Folie 6-2 (442)
Historie und biologische Aspekte
I
Ende 19. Jh.: grundsätzliches Verständnis des Gehirns
I
1913 erstes künstliches NN mit hydraulischen Mitteln (Russel)
I
Beginn der Erforschung künstlicher Neuronaler Netze etwa
1940 (Craik/Rosenbleuth/McCulloch)
I
1949 Hebb: Beginn der Entwicklung von Lernverfahren
I
1957 Rosenblatt: Perceptron
I
1970-1982 Stagnation
I
1982 Hopfield, Aufschwung beginnt
6 Neuronale Netze
Künstliche Intelligenz
6.1 Historie und biologische Aspekte
Folie 6-3 (443)
Aufbau und Wirkungsweise
I
Nervenzellen – Neuronen
I
sind untereinander verbunden, senden elektrische Signale
I
Aussenden von Signalen über Axon (Ausgang)
I
Empfang von Signalen über Dendriten (Eingänge) und
Kopplungsstellen – Synapsen
6 Neuronale Netze
Künstliche Intelligenz
6.1 Historie und biologische Aspekte
Folie 6-4 (444)
Prinzipieller Aufbau und Wirkungsweise
Zellkörper
Endknöpfchen
Synapse
Dendriten
Zellkern
Axon
Abb. 62: Modell eines NN
6 Neuronale Netze
6.2 Funktionsweise
Künstliche Intelligenz
Folie 6-5 (445)
Funktionsweise
I
Neuron arbeitet binär, ist also aktiv oder nicht.
I
Jedes Neuron besitzt einen Schwellwert.
I
Neuron empfängt Eingaben von erregenden Synapsen.
I
Neuron empfängt Eingaben von hemmenden Synapsen.
I
Neuron wird aktiv, wenn die Summe der Eingaben den
Schwellwert übersteigt.
I
Neuron kann max. 200 mal pro Sekunde feuern.
I
Ausbreitung des Signals (über Axon) etwa 100 ms
6 Neuronale Netze
6.2 Funktionsweise
Künstliche Intelligenz
Folie 6-6 (446)
Lernen
Wie lernt das menschliche Gehirn? Nach dem Modell von Donald O.
Hebb funktioniert das Lernen nach folgender Regel:
Sind die prä- und postsynaptischen Neuronen gleichzeitig aktiv,
so wird die Verbindung zwischen den Neuronen verstärkt.
6 Neuronale Netze
Künstliche Intelligenz
6.2 Funktionsweise
Folie 6-7 (447)
Künstliche Neuronale Netze – Forschung
I
Topologien
I
Lernregeln
Man weiß mittlerweile:
I
Modelle für Gehirn-Arbeitsweise sind relativ ungenau.
I
Dennoch funktionieren die künstlichen Neuronalen Netze oft gut.
6 Neuronale Netze
Künstliche Intelligenz
6.2 Funktionsweise
Folie 6-8 (448)
Vergleich – Computer & Gehirn
Eigenschaft
Parallelität
Präzision
Fehlertoleranz
Speicherzugriff
Mustererkennung
fehlerfreies Speichern
Rekonstruktion fehlerhafter Daten
Exaktheit num. Berechnungen
Selbstorganisation
Computer
niedrig
hoch
niedrig
lokal
schlecht
gut
schlecht
gut
bisher kaum
Tabelle 10: Vergleich Computer – Gehirn
Gehirn
hoch
mäßig
hoch
global
gut
schlecht
gut
schlecht
ja
6 Neuronale Netze
Künstliche Intelligenz
6.2 Funktionsweise
Folie 6-9 (449)
Symbolik und Subsymbolik
Symbolik:
I
Explizites Einführen von Begriffen auf der Modellebene
I
Bspl.: Begriff Auto
Subsymbolik:
I
kein explizites Einführen von Begriffen auf der Modellebene
I
Arbeiten mit Mikrostrukturen (z.B. Neuronen), in denen nicht
explizit ein Begriff codiert ist.
I
Bspl.: Mustererkennung mit kNN
6 Neuronale Netze
6.3 Ein einfaches Neuronenmodell
Künstliche Intelligenz
Folie 6-10 (450)
Ein einfaches Neuronenmodell
Seien alle Neuronen fortlaufend durchnumeriert. Jedes Neuron n hat:
I
Eingänge: o1 , . . . , oj mit booleschen Werten 0 oder 1.
I
1 Ausgang: Ausgabewert on (0 oder 1).
I
an den Eingaben liegende Gewichte: w1,n , . . . , wj ,n , wobei ein
positives Gewicht anregend, ein negatives hemmend ist.
I
einen Schwellwert Θn .
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-11 (451)
Wie arbeitet das (künstliche) Neuron?
I
Das Neuron arbeitet in Zeittakten.
I
Zunächst werden die Input-Signale zur Netzeingabe
zusammengefasst (net n heißt Propagierungsfunktion):
net n =
∑ wj ,n ∗ oj
j
I
Nun wird die Aktivität des Neurons (sein neuer Zustand) aus der
Netzeingabe und dem Schwellwert berechnet:
an = fact (net n , Θn )
I
Aus der Aktivität wird die Ausgabe berechnet:
on = fout (an )
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-12 (452)
Aktivierungsfunktion
Eine typische Aktivierungsfunktion ist die Schwellwertfunktion:
fact (x , Θ) = fSchwellwert (x , Θ) =
1, falls x ≥ Θ
0, sonst
Als Ausgabefunktion verwendet man meistens die Identität.
Mit diesen 2 Funktionen erfolgt eine Ausgabe also genau dann, wenn
die Summe der gewichteten Eingaben den Schwellwert erreicht:
on = 1
⇐⇒
∑ wj ,n ∗ oj
j
≥ Θn
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-13 (453)
Neuronales Netz
Ein neuronales Netz
I
besteht aus einer endlichen Anzahl von Knoten (Neuronen),
I
die miteinander verknüpft sein können.
I
I.allg. gibt es nicht nur einen Ausgang von einem Neuron zu
einem anderen, sondern einen Ausgang, der Signale zu
mehreren Neuronen aussendet.
I
Verknüpfungen als Matrix darstellbar.
I
matrix ij . . . Verbindungsgewicht von Neuron i nach j (wi ,j )
I
Ist der Wert 0, besteht keine Verbindung.
I
Die Verbindung ist gerichtet, d.h. von i nach j.
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-14 (454)
kNN für Logisches Oder
Gewicht = 1
Gewicht = 1
Schwellwert = 1
Abb. 63: kNN für Logisches Oder
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-15 (455)
Typische Vertreter
FeedForward-Netze keine Quer- oder Rückwärtsverbindungen
Rekurrente Netze Neuronen haben auch Verbindungen zu sich selbst.
Vollständige Netze Jedes Neuron ist mit jedem verknüpft.
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-16 (456)
XOR-Funktion
Beispiel 6.1 (XOR)






0
0
0
0
0
0
0
0
0
0
1
-1
0
0
0
-1
1
0
0
0
0
0
1
1
0






Schwellwerte jeweils 1.
Abb. 64: kNN für XOR
6 Neuronale Netze
Künstliche Intelligenz
6.3 Ein einfaches Neuronenmodell
Folie 6-17 (457)
Neuronen-Arten
Bemerkung 6.1 (Neuronen)
Die Neuronen kann man unterteilen in:
I
Input-Neuronen: Eingabeschicht
I
Output-Neuronen: Ausgabeschicht
I
hidden Neuronen: die Neuronen der Zwischenschichten
6 Neuronale Netze
Künstliche Intelligenz
6.4 Verallgemeinertes Modell
Folie 6-18 (458)
Verallgemeinertes Modell
I
Unser kNN-Modell arbeitet in Zeittakten.
I
Folglich müssen wir den aktuellen internen Zustand eines
Neurons speichern.
I
Jedes Neuron hat zu jedem Zeitpunkt t einen Aktivierungsgrad
a(t).
Damit müssen wir auch die Aktivierungsregel modifizieren:
an (t + 1) = fact (t , a(t ), net , Θn )
6 Neuronale Netze
6.4 Verallgemeinertes Modell
Künstliche Intelligenz
Folie 6-19 (459)
Gewichte
fact meistens nicht von t abhängig.
fact aber abhängig von der Aktivierung a(t )
Gewichte w zeitabhängig, wenn man über die Gewichte lernt:
1. Erzeugen einer neuen Verbindung
2. Entfernen einer bestehenden Verbindung
3. Modifizieren eines Gewichtes
6 Neuronale Netze
6.5 Zusammenfassung (Neuronale Netze)
Das sollten Sie wissen . . .
Zusammenfassung 6.2 (Neuronale Netze)
I
Grundprinzip
I
Aufbau von NN
I
Einfache Architekturen
I
Einfache Lernregeln
Künstliche Intelligenz
Folie 6-20 (460)
6 Neuronale Netze
Künstliche Intelligenz
6.6 Aufgaben
Folie 6-21 (461)
Aufgaben
Aufgabe 6.1 (NN)
Wie definiert man die logische Äquivalenz mit Hilfe eines NN? Das
neuronale Netz soll also 2 Eingaben bekommen (0 oder 1 für FALSCH
bzw. WAHR). Es soll entsprechend der Definition der logischen
Äquivalenz 0 bzw. 1 liefern.
7 KI-Systeme
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis
Einleitung
Darstellung und Verarbeitung von Wissen
Vages Wissen
Prolog
Problemlösung mittels Suche
Neuronale Netze
KI-Systeme
7 KI-Systeme
Künstliche Intelligenz
19. Februar 2016
Inhaltsverzeichnis – Kapitel 7
KI-Systeme
Planen
Maschinelles Lernen
Bildverarbeitung
Verarbeitung von Sprache
Expertensysteme
Zusammenfassung (KI-Anwendungen)
7 KI-Systeme
Künstliche Intelligenz
Folie 7-1 (464)
KI-Systeme
Wenn man es versteht, dann ist es veraltet.
Bitton’s Theorem über EDV
Arthur Bloch, Murphy’s Law, 1981
7 KI-Systeme
Künstliche Intelligenz
7.1 Planen
Folie 7-2 (465)
Planen
Motivation: Simulieren eines Agenten, der folgende Aufgabenklassen
zu erfüllen hat.
I
Planen von Aktionen (Produktionsplanung)
I
Planen von (räumlichen) Anordnungen
I
Konfigurieren von Produkten
I
...
Kernpunkt ist hier offenbar das Synthetisieren von Lösungen.
7 KI-Systeme
Künstliche Intelligenz
7.1 Planen
Folie 7-3 (466)
Planen
I
Viele KI-Anwendungen: Klassifikationsprobleme
I
z.B. Beratungssysteme, Diagnosesysteme etc.
I
also i.allg. nicht kreativ
I
Planen kreativer Prozess
7 KI-Systeme
Künstliche Intelligenz
7.1 Planen
Folie 7-4 (467)
Planen von Aktionen – Blocksworld
Beispiel 7.1 (Blocksworld)
Auf einer ebenen Fläche sind Quader gelagert, übereinander,
nebeneindander. Aufgabe ist es, die Objekte nach bestimmten
Vorgaben zu platzieren. Z.B. könnte die Aufgabe sein, einen
bestimmten Quader auf einen anderen zu legen, dabei vorher die
entsprechenden Quader leerzuräumen etc. Welche WR-Form würden
Sie wählen?
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
7.2.1 Generalisieren
Generalisieren
I
Induktives Generalisieren
I
deduktives Lernen
Folie 7-5 (468)
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-6 (469)
7.2.2 Discovery Learning
Discovery Learning
I
Bisher: wenig Erfolge, da es um das Erfinden von Konzepten,
Hypothesen etc. geht.
I
Es gibt Programme, die entdeckendes Lernen beinhalten.
Meistens Mathematik.
Beispiele:
1. Entdecken von Eigenschaften/Operationen auf natürlichen
Zahlen (Multiplikation, Primzahlen etc.)
2. Entdecken von geometrischen Hilfskonstrukten bei
geometrischen Beweisen
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
7.2.3 Data Mining
Data Mining
I
Weltweit stetig steigende Datenflut
I
Grobe Schätzungen: Verdoppelung alle 20 Monate
I
Daten über den initialen Zweck hinaus verwenden
I
Data Mining = Schürfen in Daten
I
Suche nach Mustern oder auffälligen Häufungen
I
Suche nach Beurteilungskriterien für vorgegebene Ziele
I
Ausführbar zu Zeiten schwacher Computerauslastung
Folie 7-7 (470)
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-8 (471)
7.2.3 Data Mining
Data Mining
Ziel des DM:
Analyse von großen Datenmengen (strukturiert oder unstrukturiert),
um implizites Wissen, Zusammenhänge zu extrahieren.
Querbezüge zu:
I
Datenbanken
I
Data Warehouses
I
Expertensysteme
I
Maschinelles Lernen
I
Statistik
I
Visualisierung
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-9 (472)
7.2.3 Data Mining
ID3-Algorithmus zur Entscheidungsbaumgenerierung
Nr
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Zielattr.
Risiko
hoch
hoch
mittel
hoch
niedrig
niedrig
hoch
mittel
niedrig
niedrig
hoch
mittel
niedrig
hoch
Kredithistorie
schlecht
unbekannt
unbekannt
unbekannt
unbekannt
unbekannt
schlecht
schlecht
gut
gut
gut
gut
gut
schlecht
Verschuldung
Sicherheiten
Einkommen
hoch
hoch
niedrig
niedrig
niedrig
niedrig
niedrig
niedrig
niedrig
hoch
hoch
hoch
hoch
hoch
keine
keine
keine
keine
keine
angemessen
keine
angemessen
keine
angemessen
keine
keine
keine
keine
0 bis 15
15 bis 35
15 bis 35
0 bis 15
über 35
über 35
0 bis 15
über 35
über 35
über 35
0 bis 15
15 bis 35
über 35
15 bis 35
Tabelle 11: Kreditrisiko
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-10 (473)
7.2.3 Data Mining
Entscheidungsbaum 1
Kreditwürdigkeit ?
unbekannt
Verschuldung ?
niedrig
gut
schlecht
Sicherheit ?
Verschuldung ?
niedrig
angemessen hoch
keine
hoch
niedriges
hohes Risiko
Sicherheit ? Risiko
Sicherheit ?
mittleres Risiko
hohes Risiko
angemessen
keine
keine
angemessen
Einkommen ? niedriges Risiko
Einkommen ? niedriges Risiko
0−15
über 35
15−35
0−15
über 35
15−35 niedriges Risiko
hohes Risiko
mittleres Risiko
mittleres Risiko
hohes Risiko
niedriges Risiko
Abb. 65: Entscheidungsbaum
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-11 (474)
7.2.3 Data Mining
Entscheidungsbaum 2
Einkommen ?
0−15
hohes Risiko
unbekannt
15−35
Kreditwürdigkeit ?
schlecht
gut
über 35
Kreditwürdigkeit ?
unbekannt
gut
niedriges Risiko
niedriges Risiko
hohes Risiko
schlecht
mittleres Risiko
Verschuldung ?
mittleres Risiko
hoch
niedrig
hohes Risiko
mittleres Risiko
Abb. 66: Entscheidungsbaum 2
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-12 (475)
7.2.3 Data Mining
Entscheidungsbaum
Welcher Baum ist für die Klassifikation der unbekannten Datensätze
optimal?
I
Der ID3-Algorithmus unterstellt, dass dies der einfachste Baum
ist.
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-13 (476)
7.2.3 Data Mining
FUNCTION induce_tree(Beispielmenge, Attribute)
IF alle Beispiele gehoeren zur gleichen Klasse
THEN RETURN Blattknoten mit Beschriftung dieser Klasse
ELSE
Waehle ein Attribut P aus Beispielmenge;
Setze P als Wurzel fuer den aktuellen Baum;
Loesche P aus Attribute;
FOREACH Wert V von P
Erstelle Kante im Baum mit Kantenbeschriftung V;
Seien P_V alle Elemente von Beispielmenge,
die als Wert fuer P gerade V haben;
Baumknoten := induce_tree(P_V,Attribute);
END FOREACH;
END IF;
END.
Abb. 67: Algorithmus – ID 3
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-14 (477)
7.2.3 Data Mining
Auswahl eines geeigneten Attributs ?
I
Grundlage: Informationstheorie
I
Wahl des Attributs, das den größten Informationsgewinn liefert.
Der Informationsgehalt eines Attributs E wird gemessen als:
n
I (E ) =
∑ −p(ei ) ∗ log2 (p(ei ))
i =1
I
ei . . . mögliche Werte des Attributs E
I
p . . . Wahrscheinlichkeit für das Eintreffen von ei .
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-15 (478)
7.2.3 Data Mining
Informationsgehalt der Kredit-Tabelle
6
14
3
= 14
I
p(Risiko hoch) =
I
p(Risiko mittel)
I
p(Risiko niedrig) =
5
14
Folglich ist
I (Tabelle) = −
6
14
∗ log2 (
6
14
)−
3
14
∗ log2 (
3
14
)−
5
14
∗ log2 (
5
14
) = 1, 531
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-16 (479)
7.2.3 Data Mining
Welches Attribut?
I
Nun wählt man das Attribut (Eigenschaft) aus,
I
das den maximalen Informationsgewinn erzielt.
I
D.h. man berechnet die Differenz aus I (Tabelle) und der
Information, die sich für die nächste Ebene ergibt.
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-17 (480)
7.2.3 Data Mining
Welches Attribut?
I
Sei eine Beispielmenge C gegeben.
I
Wählt man z.B. das Attribut E mit n Werten aus, so wird C in n
Teilmengen zerlegt: {C1 , . . . , Cn ).
I
I
E als Wurzel des Baums
Zur Baum-Fertigstellung voraussichtlich erforderliche
Informationsmenge:
n
G (E ) =
|Ci |
∑ |C | I (Ci )
i =1
Gewinn an Information: gewinn(E ) = I (C ) − G(E )
Es gilt, „gewinn“ zu maximieren. Man probiert alle Attribute und wählt
jenes mit dem maximalen Gewinn.
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-18 (481)
7.2.3 Data Mining
ID 3 und Informationsgewinn
I
Wählen zunächst Kredithistorie als Attribut.
I
Kredithistorie hat 3 Ausprägungen: unbekannt, schlecht, gut.
I
Für jeden Wert zählen wir, wie oft welches Risiko vorkommt:
Wert
unbekannt
schlecht
gut
hohes Risiko
2
3
1
mittleres Risiko
1
1
1
niedriges Risiko
2
0
3
I (Kreditw_unbek) = − 25 × log2 ( 25 ) − 15 × log2 ( 15 ) − 25 × log2 ( 25 ) = 1, 52
I (Kreditw_schlecht) = − 43 × log2 ( 34 ) − 14 × log2 ( 14 ) = 0, 81
I (Kreditw_gut) = − 15 × log2 ( 15 ) − 15 × log2 ( 51 ) − 35 × log2 ( 35 ) = 1, 37
n
|E |
G(Kredithistorie) = ∑ |Ei| I (Ei ) =
i =1
5
4
× 1, 52 + 14
14
5
× 0, 81 + 14
× 1, 37 = 1, 265
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-19 (482)
7.2.3 Data Mining
ID 3 und Gain-Berechnung
Abb. 68: Gain-Berechnung
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-20 (483)
7.2.3 Data Mining
ID 3 – Beispiel
I
I
I
I
gewinn(kredithistorie) = 1, 531 − 1, 265 = 0, 266
gewinn(einkommen) = 1, 531 − 0, 564 = 0, 967
gewinn(verschuldung) = 1, 531 − 1, 468 = 0, 063
gewinn(sicherheiten) = 1, 531 − 1, 325 = 0, 206
Man wählt nun „einkommen“ als obersten Knoten, da der Gewinn
dort am größten ist, und setzt das Verfahren für jeden Teilbaum
rekursiv fort.
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-21 (484)
7.2.3 Data Mining
Fortsetzung für Zweig einkommen=15-35
I
nur noch die Datensätze, wo einkommen=15-35 gilt
I
Spalte für Einkommen eigentlich nun unnötig
Nr.
2
3
12
14
Zielattr.
Risiko
hoch
mittel
mittel
hoch
Kredithistorie
unbekannt
unbekannt
gut
schlecht
Verschuldung
hoch
niedrig
hoch
hoch
Tabelle 12: Kreditrisiko
Sicherheiten
keine
keine
keine
keine
Einkommen
15 bis 35
15 bis 35
15 bis 35
15 bis 35
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
Folie 7-22 (485)
7.2.3 Data Mining
Informationsgehalt der reduzierten Kredit-Tabelle
2
4
= 24
I
p(Risiko hoch) =
I
p(Risiko mittel)
I
p(Risiko niedrig) =
0
4
Folglich ist I (Risiko) =
2
2
2
2
0
0
I (Tabelle2) = − × log2 ( ) − × log2 ( ) − × log2 ( ) = 1
4
4
4
4
4
4
7 KI-Systeme
Künstliche Intelligenz
7.2 Maschinelles Lernen
7.2.3 Data Mining
Attribut mit maximalem Informationsgewinn
Nun wählt man wieder das Attribut aus, das den maximalen
Informationsgewinn erzielt.
I
I
I
gewinn(kredithistorie) = 1 − 0, 5 = 0, 5
gewinn(verschuldung) = 1 − 0, 6887 = 0, 3113
gewinn(sicherheiten) = 1 − 1 = 0
Man wählt folglich „kredithistorie“ als nächsten Knoten, da der
Gewinn dort am größten ist.
Folie 7-23 (486)
7 KI-Systeme
Künstliche Intelligenz
7.3 Bildverarbeitung
Folie 7-24 (487)
Bildverarbeitung
I
Bisher: Erforderliche Informationen liegen bereits in geeigneter
Form vor.
I
Dies ist jedoch häufig nicht der Fall, z.B. bei Bildern.
I
Zunächst geeignete Information extrahieren.
Bildverarbeitung – Anwendungen:
I
Dokumenterkennung (Schriftzeichenerkennung,
Ausweis-Lesegeräte, Auto-Nummernschilder etc.)
I
Analysieren von räumlichen Anordnungen (Navigationssysteme)
I
Analysieren von medizinischen Aufnahmen (Knochenbrüche)
I
Analysieren von Satellitenbildern (Wettervorhersage)
7 KI-Systeme
Künstliche Intelligenz
7.3 Bildverarbeitung
Folie 7-25 (488)
Bildverarbeitung – Probleme
I
Die Bilder sind häufig verrauscht (unscharfe Kanten).
I
Die Bilder sind meist gestört (Kanten werden durch andere
Gegenstände unterbrochen).
I
Ein Bild enthält i.allg. sehr viele Informationen (Komplexität).
I
Abbildung von 3-dimensionalen Sachverhalten in
2-dimensionalen Bildern → eventuell mehrere
Interpretationsmöglichkeiten
7 KI-Systeme
Künstliche Intelligenz
7.3 Bildverarbeitung
Folie 7-26 (489)
Typisches Vorgehen
1. Digitalisierung des Bildes (z.B. Grauwerte)
2. Low-level-processing
I
I
Rausch-Behandlung (z.B. Glätten von kleinen Bildausschnitten)
Erkennen von low-level-Strukturen (z.B. Kanten)
3. Segmentierung (z.B. Trennen von Kanten, die im Bild
durchgehend sind, aber nicht in der Realität)
4. 3D-Erkennung (z.B. Erkennen von konvexen und konkaven
Kanten)
7 KI-Systeme
7.4 Verarbeitung von Sprache
Künstliche Intelligenz
Folie 7-27 (490)
Verarbeitung von Sprache
1. Bearbeiten der Signale (Umwandeln in Wörter)
2. Syntaktische Analyse (Erkennen der Sätze, Nebensätze, Subjekt,
Prädikat etc.)
3. Semantische Analyse (Inhaltliche Analyse der Sätze,
Ausschließen von Resultaten der syntaktischen Analyse, z.B.
beim Erkennen von Subjekt, Objekt, Doppelbedeutungen von
Wörtern aus dem Kontext)
4. Pragmatische Analyse (Verstehen der Sätze, Zusammenhänge
etc.)
7 KI-Systeme
Künstliche Intelligenz
7.4 Verarbeitung von Sprache
Folie 7-28 (491)
Verarbeitung von Sprache
Ein−/Ausgabedaten
Verarbeitungsstadium
andere verwendete Daten
Spracherkennung
Frequenzspektrogramm
syntaktische Analyse
Grammatik der Sprache
semantische Analyse
Bedeutung der Wörter
Frequenzspektrogramm
Wortsequenz
"Er liebt Hansa Rostock"
Satzstruktur
Er liebt Hansa Rostock
teilweise Bedeutung
Ex x: liebt(x,hansa)
Kontext der Äußerung
Pragmatik
Satzbedeutung
liebt(lutz,hansa)
Abb. 69: Sprachverarbeitung
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-29 (492)
Charakterisierung von Expertensystemen
Expertensysteme sind Computerprogramme mit dem Ziel der
Simulation des Problemlösungsverhaltens von Experten.
Charakteristisch ist, dass in Expertensystemen
I
eine explizite Wissensrepräsentation
erfolgt, und dass
I
eine Verarbeitungskomponente existiert.
Synonym für Expertensysteme (ES): Wissensbasierte Systeme.
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-30 (493)
7.5.1 Expertensysteme im Einsatz
Expertensysteme im Einsatz
DENDRAL
Identifikation von Molekülen mittels
Massenspektrogrammen
MYCIN
Diagnose/Therapie von bakteriellen
Infektionskrankheiten des Blutes
PUFF
Diagnose/Therapie von Lungenkrankheiten
XCON
Konfigurierung von Rechnern (Prozessoren,
Plattengröße, periphere Geräte, . . . )
IXMO
Diagnosesystem für defekte Motoren
...
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
7.5.2 Einsatzgebiete von Expertensystemen
Einsatzgebiete von Expertensystemen
I
Firmengründungsberatung (Rechtsform, Standort, . . . )
I
Investitionsplanung
I
Produktionsplanung und -steuerung
I
Lieferplanung, Logistik
I
Design-/Konstruktionsplanung
I
Technische Analyse- & Diagnose-Systeme
I
Kaufberatung
I
Juristische Beratung
I
Auskunfts- & Buchungssysteme
I
Ausbildung & Training
Folie 7-31 (494)
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-32 (495)
7.5.2 Einsatzgebiete von Expertensystemen
Aufgabe
Aufgabe 7.1 (Wissensbasierte Systeme)
Recherchieren Sie nach aktuellen Expertensystemen
(wissensbasierten Systemen).
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-33 (496)
7.5.3 Klassifizierung der Einsatzgebiete
Klassifizierung der Einsatzgebiete
I
Diagnose – Fehlersuche
I
Überwachung – Vergleich von IST- und SOLL-Werten
I
Design – Konfigurierung von Objekten
I
Planung – Aktionsfolgen-Planung mit einem bestimmten Ziel
I
Vorhersage – Finden von möglichen Konsequenzen aus
gegebener Situation
Also: 3 Typen von Expertensystemen:
I
Diagnostische Expertensysteme
I
Konstruktive Expertensysteme
I
Expertensysteme zur Simulation
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-34 (497)
7.5.4 Anforderungen an ein Expertensystem
Anforderungen an ein Expertensystem
Expertensysteme müssen bestimmte Eigenschaften erfüllen, da sie
z.B. in sicherheitskritischen Bereichen eingesetzt werden.
I
Transparenz – ihre Arbeitsweise muss nachvollziehbar und klar
sein
I
Flexibilität – sie müssen flexibel reagieren können
I
Benutzerfreundlichkeit
I
Kompetenz – sie müssen ihr Fachgebiet „beherrschen“
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-35 (498)
7.5.5 Aufbau von Expertensystemen
Aufbau von Expertensystemen
Expertensysteme genügen der generellen Architektur eines
KI-Systems, d.h es erfolgt eine Trennung von:
I
Wissensbasis
und
I
der Verarbeitungs-/Problemlösungskomponente
Dabei trennt man das Wissen in
I
allgemeines Fachgebietswissen
I
Fall-spezifisches Wissen
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-36 (499)
7.5.5 Aufbau von Expertensystemen
Aufbau von Expertensystemen
Expertensysteme haben also folgenden Aufbau:
I
WR/WV-Komponente
I
Wissensrepräsentationskomponente
I
I
I
I
allgemeines Wissen
Fall-spezifisches Wissen
Problemlösungs-/Verarbeitungskomponente
Benutzerschnittstelle
I
I
Wissenserwerbs-Komponente
Erklärungskomponente
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-37 (500)
7.5.5 Aufbau von Expertensystemen
Aufbau von Expertensystemen
Wissensakquisition
User Interface
Erklärungskomponente
Inferenzmaschine
allgemeines
Fachwissen
Wissensbasis
Fall−spezifisches
Wissen
Abb. 70: Architektur eines Expertensystems
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-38 (501)
7.5.5 Aufbau von Expertensystemen
Expert system shell
Wichtiger Aspekt der Expertensystem-Architektur:
I
Wissensbasis im Prinzip austauschbar
I
Expertensystem ohne Wissensbasis: Expert system shell
I
Beispiel: EMYCIN (ging aus MYCIN hervor)
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-39 (502)
7.5.5 Aufbau von Expertensystemen
Wissenserwerbs-Komponente
Probleme:
I
Experte verfügt i.allg. nicht über (abstrakte) allgemeine Regeln.
I
Klare Strukturierung des Fachgebietes oft erst während der
ES-Entwicklung
I
Während der Wissensgewinnung ist i.allg. Abstraktion
erforderlich.
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-40 (503)
7.5.5 Aufbau von Expertensystemen
Wissenserwerbs-Komponente
Techniken zum Wissenserwerb:
I
Interviews
I
Strukturierter Wissenserwerb
1. Fachbegriffe (z.B. Namen von Krankheiten) klären
2. Begriffsklassen für Problemlösung (z.B. Symptome, Diagnose,
Therapie) definieren
3. Problemlösungsstrategien erkennen und in das System einbauen
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-41 (504)
7.5.5 Aufbau von Expertensystemen
Aufgaben eines Knowledge Engineer
Fachexperte
Dialog
Knowledge Engineer
Transformation
Wissensbasis
Abb. 71: Aufgaben eines Knowledge Engineer
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-42 (505)
7.5.5 Aufbau von Expertensystemen
Benutzerschnittstelle
Anforderungen:
I
Kurze Reaktionszeiten
I
Leichte Handhabbarkeit und Erlernbarkeit
I
Hohe Toleranz bei fehlerhaften Eingaben
Standard-Techniken:
I
Menüs
I
Eingabemasken
I
Kommandosprachen
I
Natürlichsprachliche Eingabe
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-43 (506)
7.5.5 Aufbau von Expertensystemen
Erklärungskomponente
Aufgabe: Transparenz der Problemlösung
Probleme:
I
Ausgabe aller Schritte zur Problemlösung i.allg. zu komplex.
I
Welche Schritte bei der Problemlösung sind „interessant“?
I
Regeln können zu kompakt sein.
Techniken:
I
direkte Erklärung (aus Programmcode der
Problemlösungskomponente)
I
indirekte Erklärung (aus dem Wissen des Experten)
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-44 (507)
7.5.5 Aufbau von Expertensystemen
Wissensbasis/Verarbeitungskomponente
Aufgabe: Darstellung und Verarbeitung von „Wissen“
I
Prädikatenlogik
I
Regelsysteme
I
Frames
I
...
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-45 (508)
7.5.5 Aufbau von Expertensystemen
Wissensbasis/Verarbeitungskomponente
Probleme:
I
Welche Form der Wissensrepräsentation ist adäquat für das
Fachgebietswissen?
I
Ist die gewählte WR-Sprache ausdrucksstark genug?
I
Gibt es für die gewählte WR-Sprache effiziente Verfahren, die
das Wissen verarbeiten können?
I
Wie kann man verschiedene WR-Formen kombinieren?
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-46 (509)
7.5.6 Potential und Grenzen von Expertensystemen
Potential von Expertensystemen
I
Entlastung von Experten
I
Expertenwissen konservierbar & transferierbar
I
Expertenwissen permanent verfügbar
I
Keine (z.B. Stress-bedingte) Fehleranfälligkeit
I
Expertenwissen wird billiger
I
Erfolgreich in gut strukturierten, komplexen, abgegrenzten
Gebieten
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-47 (510)
7.5.6 Potential und Grenzen von Expertensystemen
Potential von Expertensystemen – 2
I
Erkenntnisgewinnung bei der Extraktion des Expertenwissens
I
Hohe Flexibilität (Modifizierbarkeit, Erweiterbarkeit, Einsatz in
anderen Gebieten mit ähnlicher Struktur) durch den modularen
Aufbau
I
Transparenz durch Erklärbarkeit bzw. Wiederholbarkeit von
Problemlösungen
I
Hohe Problemlösungsgeschwindigkeit trotz einer großen
Informationsmenge
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-48 (511)
7.5.6 Potential und Grenzen von Expertensystemen
Grenzen und Defizite von Expertensystemen
I
Expertensystem hat kein „Verständnis“ für Problembereich
I
Expertensystem hat kein Allgemeinwissen, kein
Randgebietswissen
I
Expertensysteme können sich nicht auf neue Situationen
einstellen
I
Aufbereitung der Informationen durch den Benutzer i.allg.
erforderlich.
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-49 (512)
7.5.6 Potential und Grenzen von Expertensystemen
Grenzen und Defizite von Expertensystemen – 2
I
Kaum einsetzbar in schlecht strukturierten Gebieten
I
Expertensysteme sind (bis jetzt) nur sehr beschränkt lernfähig
I
Leistungsstärke hängt von der Problemlösungskomponente ab,
d.h. Expertensysteme sind nur sinnvoll, wenn es für das
Fachgebiet adäquate Problemlösungskomponenten gibt.
I
Benutzerakzeptanz leidet oft unter der Qualität der
I
I
I
Wissenserwerbskomponente,
Erklärungskomponente
und der
Benutzerschnittstelle.
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-50 (513)
7.5.6 Potential und Grenzen von Expertensystemen
Vergleich ES – menschlicher Experte – konv. Programm
Experte
ES
konventionelles
Programm
feste Algorithmen
Nutzt
Daumenre- symbolisches
geln und Heuristi- Schließen
ken
arbeitet in eingegrenzten Problembereichen
Nutzt Allgemeinwis- –
–
sen
Wissen
compiliert Wissen
symbo- Wissen und Kontrolloder als NN
lisch repräsentiert, strukturen in einem
getrennt von Verarbeitung
7 KI-Systeme
Künstliche Intelligenz
7.5 Expertensysteme
Folie 7-51 (514)
7.5.6 Potential und Grenzen von Expertensystemen
Vergleich ES – menschlicher Experte – konv. Programm
Experte
kann Entscheidung
erklären
ES
kann Entscheidung
erklären, aber nur
den Entscheidungsprozess
arbeitet auch mit unvollständigem und
vagem Wissen
kann bei unvollständigem/vagem Wissen
Fehler machen
lernt über die Jahre
I. allg. Lernen durch
neue Fakten/Regeln
konventionelles
Programm
i.allg. keine Erklärung möglich
nur exaktes und vollständiges Wissen
dann i.allg. keine Lösung
Lernen i. allg. nur
durch Codeänderung
7 KI-Systeme
Künstliche Intelligenz
7.6 Zusammenfassung (KI-Anwendungen)
Folie 7-52 (515)
Das sollten Sie wissen . . .
Zusammenfassung 7.1 (KI-Anwendungen)
I
Grober Überblick über Anwendungsklassen
I
Data Mining (insb. Entscheidungsbäume)
I
Expertensysteme / Wiss.bas. Systeme
I
Sprach- und Bildverarbeitung
8 Literatur
Künstliche Intelligenz
Folie 8-53 (516)
Literatur
Uwe Lämmel, Jürgen Cleve.
Künstliche Intelligenz.
Hanser, 2012.
Heiner Stuckenschmidt.
Ontologien.
Springer, 2011.

"Wachstumsschub dank künstlicher Intelligenz"

Künstliche Intelligenz im Gesundheitswesen

response management auf den punkt genau

Alexander von Bülow - Intelligenz System Transfer

Die 7 Intelligenzen nach Howard Gardner

150211 Plakat Treff um 11 Endoprothetik_final.indd

Künstliche Intelligenz und Maschinelles Lernen

ZIF-KONFERENZ Intelligenz: Mensch trifft Technik

PDF-Datei, 4 Seiten - TaT Transferzentrum für angepasste

Suche nach außerirdischer Intelligenz