Aspekte der universellen Ontologie Elemente der ...ki.informatik.uni-wuerzburg.de/teach/documents/KI/skript/Kap10.4.pdf · 3 Künstliche Intelligenz: 10. Wissensrepräsentation Frank

1

Künstliche Intelligenz: 10. Wissensrepräsentation Frank Puppe 1

Übersicht

I Künstliche IntelligenzII ProblemlösenIII Wissen und Schlussfolgern

7. Logische Agenten8. Prädikatenlogik 1. Stufe9. Schließen in der Prädikatenlogik 1. Stufe10. Wissensrepräsentation

IV Logisch HandelnV Unsicheres Wissen und SchließenVI LernenVII Kommunizieren, Wahrnehmen und Handeln


in den bisherigen Beispielen wurden viele einschränkende Annahmen gemacht:

(1) Ontologie für Schaltkreise: keine Zeit, keine zeitabhängige Propagierung von Signalen, unveränderliche Schaltkreisstruktur, wenig Gatterklassen, keine zufälligen Kapazitäten, ...

(2) Ontologie für WUMPUS-Welt: einfaches Zeitkonzept: nur der Agent handelt, nur je eine Sorte von Fallen und nur ein WUMPUS und ein Agent, ...

Gibt es eine universelle Ontologie, die sich für alle speziellen Zwecke eignet? - Vielleicht!

Universelle Ontologien


• Kategorien, oft organisiert in taxonomische Hierarchien

• Maße

• Zusammengesetzte Objekte

• Substanzen und Objekte

• Zeit, Raum und Änderungen

• Mentale Objekte und Meinungen

Aspekte der universellen Ontologie


Elemente der universellen Ontologie

2


• Repräsentation - mit einstelligen Prädikaten z.B. Tomate (x)- oder durch Objekte (reification): x ∈Tomaten

• Kategorien haben Eigenschaften, - für die Kategorie selbst z.B. Anzahl (Menschen) = 6*109

- für die Instanzen z.B. ∀x x ∈Tomaten ⇒ Rot (x) ∧ Rund (x) • Vererbung von Eigenschaften in Taxonomie und Klassifikation:

- Tomaten ⊂ Gemüse ⊂ Essbare_Dinge- ∀x x ∈Gemüse ∧ Rot (x) ∧ Rund (x) ∧ Klein (x) ⇒ x ∈Tomate

• disjunkte Werte: z.B. Männer und Frauen- erschöpfende Zerlegung: z.B. für Nordamerikaner:

Amerikaner, Kanadier, Mexikaner- Partition: disjunkte erschöpfende Zerlegung,

z.B. für Dinge: eßbar, nicht-eßbar.• Kategorien können durch notwendige und hinreichende

Bedingungen definiert werden.

Repräsentation von Kategorien


Maße: gewöhnlich ausgedrückt mit Zahlen und Einheiten.

→ Arithmetik

aber: Viele Dinge lassen sich schwer messen, z.B. Geschmack, Schönheit, Schwierigkeiten, ...

Alternative: Rangfolgen: A besser als B besser als C.

→ Qualitatives Schließen

Maße


(Taxonomische Hierarchie von Kategorien: Sportwagen ⊂ Auto ⊂ Fahrzeug)

Teilehierarchie (PartOf):Motor ist Teil vom Auto: PartOf (Motor, Auto)Karosserie ist Teil vom Auto: PartOf (Karosserie, Auto)Zündkerzen sind Teil vom Motor: PartOf (Zündkerzen, Motor)

Aus Transitivität von PartOf kann hergeleitet werden:PartOf (Zündkerzen, Auto)

Weitere Herleitungen möglich, z.B.:Das Gewicht des Autos berechnet sich aus der Summe der Gewichte seiner Teile.

Zusammengesetzte Objekte


Bei Substanzen wie z.B. Butter ist jeder Teil der Butter auch Butter, während bei Objekten wie Äpfeln ein Teil des Apfels keinApfel mehr ist (sondern z.B. nur ein halber Apfel).

Linguisten unterscheiden entsprechend zwischen "Zähl-Substantiven" und "Masse-Substantiven".

Wenn man statt Butter "Ein_Pfund_Butter" sagt, dann meint man keine Substanz, sondern ein nichtteilbares Objekt.

Substanzen und Objekte (1)

3


Objekte haben - intrinsische Eigenschaften, die sie an ihre Teile vererben, - extrinsische Eigenschaften, die sie auszeichnen.

Beispiel: Bodensee

1. gehört zur Substanz-Klasse Gewässer mit intrinsischen Eigenschaften wie: „man kann darin schwimmen“, „kann zufrieren“ usw.

2. gehört zur Objekt-Klasse See mit extrinsischenEigenschaften wie Größe usw.

Substanzen und Objekte (2)


Ein einfacher Reflex-Agent ohne Gedächtnis ist zwar möglich, aber hat es schwer in der WUMPUS-Welt, da er z.B. nicht kombinieren kann.

Wenn er seine Wahrnehmungssequenz speichert, kann er daraus zwar prinzipiell alle Informationen extrahieren, aber das dauertmöglicherweise sehr lange.

Eine Variante davon ist der Situationskalkül, indem jede Situation, in der der Agent sich befand, abgespeichert wird. DieSituationen sind durch Aktionen des Agenten miteinander verbunden.

Eleganter ist es, wenn der Agent einen internen Zustand aufbaut, in dem das für ihn relevante leicht zugänglich ist, ohne daß er sich die Historie explizit merken muß.

Repräsentation zeitlicher Änderungen


Beispiel für Situationskalkül


Effekt-Axiome geben an, was sich von einem Zustand zum anderen ändert.

Frame-Axiome geben, was von einem Zustand zum anderen gleich bleibt.

Repräsentationelles Frame-Problem (viele Frame-Axiome)

kann vermieden werden, indem Effekt- und Frame-Axiome zu Nachfolge-Zustand-Axiome kombiniert werden:

Etwas ist genau dann wahr, wenn es durch die Aktion wahr gemacht wird oder es bereits wahr war und durch die Aktion nichtfalsch gemacht wurde. Dabei müssen alle kritischen Aktionen aufgezählt werden.

Beschreibung von Aktionen im Situationskalkül

4


Effekt-Axiome

Frame-Axiome

Nachfolge-Zustand-Axiome

Beispiele für Axiome im Situationskalkül


• Inferentielles Frame-Problem: Viele Inferenzen über Eigenschaften, die sich nicht ändern.

• Qualitifikations-Problem: Es ist aufwendig, alle Bedingungen zu beschreiben, die für eine erfolgreiche Aktion notwendig sind.

• Ramifikations-Problem: Es ist aufwendig, alle impliziten Konsequenzen einer Aktion herzuleiten.

Nur lösbar mit Spezialproblemlösern; Weitere Probleme:

• kontinuierlichen Änderungen (z.B. Wachsen eines Lebewesens) • Aktionen mehrerer Agenten• Umwelt ändert sich ohne Zutun des Agenten

Alternative: Ereigniskalkül

Probleme mit dem Situationskalkül


• Ereignisse haben eine zeitliche und räumliche Dimension• Ereignisse können Unterereignisse haben: Bsp.: „Schlacht von England“ ist

Teil von „2. Weltkrieg“• Lokalisationen kann man als Ereignisse ohne zeitliche Dimension auffassen.• Kategorisierung von Ereignissen: Bsp.: „2. Weltkrieg“ in Kategorie „Krieg“• Aktionen wie (Gehe [1,1], [1,2]) sind Kategorien von Ereignissen• Prozesse sind "zeitliche Substanzen", d.h. Ereignisse, deren Teilintervalle

zum gleichen Ereignis gehören, z.B. "Flug (Otto)" aber nicht "Flug (Otto, A, B)"

Ereigniskalkül


Die Basis sind Zeitintervalle (mit Start- und Endpunkt).Ein Moment ist ein Intervall der Dauer 0.

Die grundlegenden qualitativen Relationen zwischen Intervallen ergeben sich daraus, wie ihre Start- und Endpunkte zueinander liegen,

z.B. ∀ i,j Meet (i,j) ⇔ Time (end (i)) = Time (start (j))

Repräsentation von Zeit

5


Prädikate über Zeitintervallen

Zusätzliche Prädikate im Zeitkalkül von Allen: starts (i,j); ends (i,j):


Problem: Man will im Supermarkt Kerzen kaufen, hat auch einen Plan: dahin gehen, wo die Kerzen sind, sie in den Einkaufswagen legen, und an der Kasse bezahlen; aber weiß nicht, wo die Kerzen sind.

Das Problem kann gelöst werden, indem man jemanden fragt, der den Standort der Kerzen kennt. Dazu muß man ein Modell des Wissens anderer Personen haben (z.B. das Verkäufer eher den Standort der Kerzen kennen als andere Kunden).

Der Agent glaubt oder weiß, daß ein anderer Agent etwas weiß, z.B. wo es Kerzen gibt.

Mentale Ereignisse und Objekte


Wir brauchen Prädikate wie:

Believes (Agent x) bzw. Knows (Agent x) bzw.Wants (Agent x)

Problem: In PK1 darf das x kein Satz wie "Platz (Kerzen, 1. Gang)" sein.

Lösung: Betrachte das x als eine Art Funktion.

Problem: wie kann man daraus vernünftige Schlußfolgerungen herleiten, z.B. dass zwei Funktionen dasselbe Objekt meinen ("referentielle Transparenz").

Formalisierung mentaler Ereignisse und Objekte


Mentale Objekte werden als Strings einer Repräsentationssprache (z.B. Prädikatenlogik) repräsentiert.

Für diese Strings wird eine Syntax, Semantik und Beweistheorie mithilfe der Prädikatenlogik 1. Stufe formuliert.

Beispiel:

Funktionen zur Nachbildung der Regeln der Prädikatenlogik wie Modus Ponens:∀ a,p,q LogicalAgent (a) ∧ Believes (a,p) ∧ Believes (a, Concat (p, "⇒", q) ⇒ Believes (a,q)

Lösung: Syntaktische Theorie mentaler Objekte

6


a) Logische Allwissenheit, d.h. unbegrenzte logische Deduktionsfähigkeit (unrealistisch)

b) Explizite Formalisierung, was ein Agent schlussfolgern kann (schwierig)

Formulierung, was ein Agent weiß


Inferenzsysteme für Kategorien

• Kernelement von Wissensrepräsentationssystemen• Zwei Systemfamilien:

– Semantische Netze: Grafische Darstellung + effiziente Algorithmen für Herleitung von Eigenschaften von Objekten basierend auf Kategoriezugehörigkeit (Vererbung)

– Beschreibungslogik: Formale Sprache für Konstruktion und Kombination von Kategorie-Definitionen und effiziente Algorithmen für Teilmengen-Beziehungen zwischen Kategorien


Grafische Wissensnotationen wurden schon Ende des 19. Jahrhun-derts als "Logik der Zukunft" propagiert. Auf semantischer Ebene besteht aber kein grundlegender Unterschied zur PK1

Kernmechanismen:- Vererbung entlang von Kanten mit Default-Werten- Zugeordnete Prozeduren möglich, um die Beschränkungen in der

Ausdrucksstärke zu kompensieren.

Vorteile grafischer Notationen:- bessere Lesbarkeit für Menschen. - durch Vereinfachungen in der Ausdrucksstärke wird Inferenzprozess

effizienter und transparenter (z.B. Verfolgen von Kanten im Netz)

Nachteile:- oft unklare Semantik der Graphen (z.B. bei multipler Vererbung);

Klärung nur im Programmcode.- Effizienzprobleme aufgrund von Nicht-Monotonie wegen Defaults.

Semantische Netze


Umsetzung semantischer Netze in PK1

7


Relationstypen in semantischen Netzen


Bsp.: Relationstypen in semantischen NetzenKästchen deuten Eigenschaften für alle Objekte einer Kategorie an.

Doppelkästchen deuten Beziehungen zwischen allen Objekten von Kategorien an.


Umwandlung n-ärer in binäre Relationen

Beispiel: Fly

(Shankar, NewYork, NewDehli, Yesterday)

Technik: Reifikation von Kanten, d.h. Umwandlung in Objekte

Grenzen der Ausdrucksstärke: Negationen, Diskunktionen, Funktionen, Existenzquantoren


Problem der Mehrfachvererbung

8


Ziel: Definition von Kategorien, so dass aufgrund der Eigenschaften einer Kategorie bzw. eines Objektes dessen Zugehörigkeit zu einer Kategorie ermittelt werden kann (Subsumption bzw. Klassifikation).

Bsp1 (Junggeselle): And (Unverheiratet, Erwachsener, Männlich)

Bsp2 (Mann mit mindestens drei arbeitslosen und mit einem Doktor verheirateten Söhnen und zwei Töchtern, die Professor in Chemie oder Physik sind):And (Mann, AtLeast (3 Sohn), Atleast (2 Tochter)

(All (Sohn, And (Arbeitslos, Verheiratet, All (Partner Doktor)))(All (Tochter, And (Professor, Fills (Fach, Physik, Chemie))))

Effizienzfrage: Wie aufwendig ist Subsumption in Abhängigkeit der Ausdrucksstärke der Sprache?

Beschreibungslogiken (Terminologische Logiken)


Effizient interpretierbaren Beschreibungslogiken fehlen meist Operatoren für Negation und Disjunktion (z.B. „Or“ oder „Some“; Fills & OneOf erlauben Disjunktion nur für explizit aufgezählte Individuen).

Sprache für Beschreibungslogik in CLASSIC


Schließen mit Default-Informationen• Alle Vögel können fliegen – außer Pinguine, Strauße, …

• Closed World Assumption & Unique Name Assumption– Beispiel: Vorlesungen im Informatik-Grundstudium: 10501,

10503, 10601, 10603, 10605 -- Wie viele Vorlesungen werden angeboten?

• Normale Antwort: 5 • Logikantwort: 1 - ∞

– Wir gehen davon aus, dass die Liste der Vorlesungen vollständig (CWA) und unterschiedlich (UNA) ist.

– CWA macht Datenbank vollständig, d.h. alle Fragen beantwortbar.

– Kann man in Logik nachbilden, ist aber aus Effizienzgründen z.B. in Prolog in Inferenzmechanismus eingebaut

• Negation as Failure: Was man nicht herleiten kann, gilt auch nicht (Verallgemeinerung der CWA)


Bedeutung von Default-Informationen• Erweiterungen von PK1 erforderlich: Nichtmonotone Logiken• Zwei bekannte Ansätze:

– Circumscription: Verbesserung der CWA: • Beispiel: Vogel (x) ∧ ¬Abnorm1 (x) ⇒ KannFliegen (x)• Wenn Vogel (Tweety) gilt und Abnorm1 (Tweety) nicht bewiesen

werden kann, dann ist KannFliegen (Tweety) herleitbar.• Modell-Präferenz-Logik: Sätze die mit Default-Regeln hergeleitet

wurden, sind wahr in allen bevorzugten Modellen der WB – im Gegensatz zu allen Modellen in der klassischen Logik

• Problem: Mehrfachvererbung (s.o. der Pinguin Opus quakt oder spricht): ergibt zwei bevorzugte Modelle, die gewichtet werden können, aber nicht müssen.

– Default Logik• Beispiel: Vogel (x) : KannFliegen (x) / KannFliegen (x) • Aus Vogel (Tweety) ist KannFliegen (Tweety) herleitbar, wenn es

konsistent mit der WB ist.• Default-Regeln implizieren Extensionen der WB, d.h.maximal herleit-

bare Konsequenzen (bei Mehrfachvererbung mehrere Extensionen)• Hauptproblem: Kein Abwägen wie bei Wahrscheinlichkeitstheorie

9


Effiziente Implementierung von Nicht-Monotonem Schließen, z.B. wegen

• Speicherbereinigung (Vergessen)• Änderungen in der Welt• Änderungen bei Default-Annahmen• Korrektur von Fehlinformationen

Problem: Gewährleistung der Konsistenz der Datenbasis, da aus geänderten Aussagen andere Aussagen hergeleitet sein können.

Lösung: Truth-Maintenance-Systeme (TMS)Vier Varianten:1. Backtracking mit kompletter Neuberechnung2. Chronologisches Backtracking:

Ziehe alle Schlussfolgerungen bis zu dem Punkt zurück, wo die geänderte Aussage das erste Mal benutzt wurde.

Belief Revision (1)


2. Justification-Based TMS (JTMS): Speichere zu jeder Schlussfolgerung die direkten Gründe (justifications) für ihre Herleitung. Wenn ein Grund ungültig wird, dann überprüfe, ob für die betroffene Schlußfolgerung noch andere Gründe zutreffen.Wenn nicht, ziehe sie zurück und überprüfe rekursiv die Auswirkungen.

Problem: zirkuläre Gründe. Lösung: Unterscheidung in "sichere" und "unsichere" Gründe.

3. Assumption-Based TMS (ATMS):Speichere zu jeder Schlussfolgerung die Basisannahmen (Assumptions), die zu ihrer Herleitung geführt haben. Wenn sich etwas ändert, überprüfe anhand ihrer Basisannahmen, ob eine Schlussfolgerung immer noch gilt.

Vorteile gegenüber JTMS: Kein Problem mit Zyklen, Behandlung multipler Zustände möglich.Nachteile: Skalierungsproblem, Behandlung von unsicherem Wissen.

Belief Revision (2)

Documents

Aspekte der universellen Ontologie Elemente der ...ki.informatik.uni-wuerzburg.de/teach/documents/KI/skript/Kap10.4.pdf · 3 Künstliche Intelligenz: 10. Wissensrepräsentation Frank