SMART Systems (Vorlesung: KI & XPS)
Beim vorigen Mal: Einführung, Grundprobleme, Fokussierung
Inhalt heute: Einfache symbolische Repräsentationsansätze
Lernziele: Entwicklungsgrundlage von heute vieldiskutierten
Repräsentationstechniken kennenlernen Einschätzen der Möglichkeiten und Grenzen
Ralf Möller, Univ. of Applied Sciences, FH-Wedel
Wiederholung: Regelbasiertes VorgehenRegelbasis (rule base)
Regeln konjunktiv verknüpfte Vorbedingungen (auch: Antezedenzen) Nachbedingungen (auch: Konklusionen, Konsequenzen) Vorbedindungen ggf. negierbar (Konklusionen nicht negierbar)
Arbeitsspeicher (working memory) Elemente: (<Objekt> <Attribut> <Wert>)-Tripel Regelanwendung (Feuern einer Regel) auf Elemente,
die zu Vorbedingungen passen (match) und im Arbeitsspeicher sind oder "gerade" nicht im Arbeitsspeicher sind (bei Negation)
Hinzufügung der Nachbedingungen zum Arbeitsspeicher
… z.B. wenn ein Auto nicht anspringt
Regel 1Wenn(Anlasser Zustand normal)dann (Batterie Zustand OK)Regel 2Wenn (Batterie Zustand OK)Und (Tankuhr Wert > 0)Und (Benzinfilter Zustand sauber)Dann (Problem Ort Zündanlage)Regel 3Wenn (Batterie Zustand OK)Und (Tankuhr Wert > 0)Und (nicht (Benzinfilter Zustand sauber))Dann (Problem Ort Benzinzuleitung)Regel 4Wenn (nicht (Scheibenw. Zustand OK))Und (nicht (Licht Zustand OK))Dann (Defekt Wert Batterie_leer)Regel 5Wenn (nicht Wert Tankuhr > 0)Dann (Defekt Wert Tank_leer)Regel 6Wenn (Problem Ort Zündanlage)Und (Verteilerdose Zustand OK)Dann (Defekt Wert Zündspule)
(Anlasser Zustand normal)
(Scheibenw. Zustand OK)
(Licht Zustand OK)
(Tankuhr Wert > 0)
(Benzinfilter Zustand sauber)
(Verteilerdose Zustand OK)
Inferenz- kompo-nente
(Batterie Zustand OK)
Regelbasiertes Vorgehen: Beispiel
© Bernd Neumann
ArbeitsspeicherRegelmenge
Hinzufügung
Regelbasiertes Vorgehen: Probleme
Operationale Semantik, MehrdeutigkeitenNegation nicht wohlverstandenDatenrepräsentation mit Tripeln skaliert nicht
für große Anwendungen Betrachtung aller Attribute eines Objekts erschwert Keine Strukturierung der Objekte in Kategorien Wertebereiche von Attributen nicht festlegbar Keine indefiniten Angaben über Werte
(siehe ">0" im Diagnosebeispiel)
Deduktion vs. Reaktion
Deduktion: Nur Hinzufügung von durch Nachbedingungen
beschriebene Elemente zum Arbeitspeicher Regelverkettung (vorwärts und rückwärts)
Reaktion: Auch Löschen von Elementen des Arbeitspeichers,
die durch Nachbedingungen beschrieben werden Zustandsmodellierung Vorwärtsverkettung Kommt später im Kontext von Planungsaufgaben
Symbolische Datenrepräsentation
(<Objekt> <Attribut> <Wert>)-Tripel gehen auf philosophische Arbeiten zurück Leibniz: ca. 1690 Frege: Begriffsschrift (concept notation), 1879 Anwendungsorientierte Sichtweisen in der KI (ab ca. 1967)
Statt Tripelsichtweise auf Daten: Netzwerksichtweise ("Semantische Netze", Quillian, 1967) Objekte sind Knoten, Attribute definieren Kanten Ausgezeichnetes Attribut ISA zur Kategorisierung Problem: Einige Knoten sind Objekte, einige Knoten
repräsentieren Kategorien Konventionen: z.B. Objekte mit Nummern und klein
Regeln mit Variablen
Schema: Wenn (?x ISA Batterie)
Dann (?x ISA Elektrisches-Bauteil)Anwendung im Diagnosebeispiel:
Wenn (?x ISA Elektrisches-Bauteil) Und (tankuhr-1 Wert >0) Dann (problem-1 Ort ?x)
Im Arbeitspeicher: (batterie-1 ISA Batterie) (tankuhr-1 Wert >0)
Weitere Arbeiten
Bisheriger Fokus: Daten: Objekte (im Sinne von atomaren Symbolen)
Neuer Fokus: Kategorien ("Frames", Minsky 1975) Beschreibung von Attributen von Objekten
und ihren Wertebereichen Der Wert eines Attributs kann eine Menge von
Objekten sein, die durch Frame beschrieben werdenBevorzugte Anwendung:
Ereignisbeschreibung (z.B. Restaurantbesuch)
Frames (Rahmen)
Objekte spielen bei Ereignissen eine best. RolleEreignisattribute heißen "Rollen" oder auch
"Slots" Beispiel: Agens, Thematisches-Objekt, Instrument, ...
"Robbie hit the ball with a bat"Wertebereichsangaben für SlotsVererbungsprinzip:
Angaben von "Ober-" bzw. "Unterframes" Idee: Wertebereichsangaben für Slots auf
Unterframe(s) übertragen
Frame-Systeme: ein Beispiel
Define-frame Husband ISA: Person Married-to: Person
Define-frame Parent Has-child: Person
Define-frame ralf-1 ISA: Husband AND Parent Married-to: silvia-1 Has-child: marcus-1
Hinreichende odernur notwendige
Definitionen?
Frame-Systeme: weitere Schwierigkeiten
Datenbeschreibung (Frames) und Daten (Objekte) immer noch vermischt
Kann ein Objekt zu mehreren Frames in einer ISA-Beziehung stehen?
Kann ein Objekt zu mehreren Frames in einer Oberframe/Unterframe-Beziehung stehen?
Sind Frames mit verschiedenen Namen disjunkt? Kann indefinites Wissen repräsentiert werden?
ralf-1 ISA Mercedes-Fahrer OR BMW-Fahrer Was ist mit Negation? "ralf-1 ISA Not Rolls-Royce-
Fahrer"
Ausprägungen ab ca. 1979 (ggf. mehr Möglichkeiten)
Erweiterte Entity-Relationship-Modellierung + Relationale Sicht: <Attribut> (<Objekt>, <Wert>) + n-stellige Relationen + Kardinalitätsangaben
UML (Unified Modeling Language) + Verhaltensbeschreibung von Objekten
XML (eXtensible Markup Language) + Verteilung
RDF (Resource Description Framework) + Definition von Beschreibungssprachen
XML: eXtensible Markup Language
Ursprung: strukturierter Text (HTML4.0 XML SGML)
Web-Standard (W3C) zum Datenaustausch: Ein- und Ausgabedaten von Anwendungen können mittels
XML beschrieben werden Industrie muß sich nur noch auf standardisierte Beschreibung
einigen Komplementärsprache zu HTML:
HTML beschreibt die Präsentation XML beschreibt den Inhalt
Datenbank-Sichtweise: XML als Datenmodell für semistrukturierte Daten
© Steffen Staab
Dokumenttyp vs. Dokument
Parser
XML DTD
Dokument Parse-Baum
Parse-Baum=
Datenstruktur
XML-Modell als linearer Text
<Bib id=“o1”><paper id=“o12”>
<title> Foundations of Databases </title><author>
<firstname> Serge </firstname><lastname> Abiteboul </lastname>
</author> <year> 1997 </year>
<publisher> Addison Wesley </publisher></paper>...
</Bib>
© Steffen Staab
XML-Modell als Graph (oder auch Netz)
&o1
&o12 &o24 &o29
Serge AbiteboulVictor Vianu 122 133
1997
paper book paper
author year authorpage
firstname lastnamefirstname lastname first last
Bib
Objektidentifikator als Attribut im Knoten vermerktKnoten sind markiert
Text im Knoten vermerkt© Steffen Staab
Schemata in XML (optional)
DTD – Document Type Definitions: Einfache Grammatik für ein XML-Dokument
Deklaration von Elementen, Attributen, u.a. Beschränkt die beliebige Verschachtelung von Elementen und Attributen
Ist Teil des XML-Standards Erbe von SGML
XML-Schema: Komplexere Datendefinitionssprache:
Viele standardisierte Basistypen, z.B. float, double, decimal, boolean Typen und typisierte Objektreferenzen Klassenhierarchien / Vererbung Konsistenzbedingungen
Standard in Ergänzung zu XML (noch nicht verabschiedet!) Abwärtskompatibel zu DTD
© Steffen Staab
XML-Schemata I: DTD
Eine DTD definiert eine kontextfreie Grammatik für ein XML-Dokument
Zuvor beliebige Elemente und Attribute werden auf eine definierte Auswahl und Struktur eingeschränkt
<bib><paper id=“o12”>
<title> Foundations of Databases </title><author>
<firstname> Serge </firstname><lastname> Abiteboul </lastname>
</author> <year> 1997 </year><publisher> Addison Wesley </publisher>
</paper>...
</bib> XML
<!DOCTYPE bib [<!ELEMENT bib (paper*)><!ELEMENT paper (author+, year, publisher?)><!ATTLIST paper id ID #REQUIRED><!ELEMENT author (firstname*, lastname)><!ATTLIST author age CDATA #IMPLIED><!ELEMENT firstname (#PCDATA)><!ELEMENT lastname (#PCDATA)><!ELEMENT year (#PCDATA)>
<!ELEMENT publisher (#PCDATA)>...
]> DTD© Steffen Staab
DTD – Deklaration von Elementen
Beschreibt die Einschränkungen des Inhalts eines Elements Syntax:
<!ELEMENT Name (Definition)> Einziger atomarer Typ: #PCDATA
(Parsed Character DATA) (a,b,c): Liste von Unterelementen (a|b|c): Alternativen Kardinalitäten:
* keinmal oder beliebig oft + einmal oder beliebig oft ? kein- oder einmal (optional) (ohne Angabe): genau einmal
EMPTY : Erzwingen von leerem Element
<!DOCTYPE bib [<!ELEMENT bib (paper*)><!ELEMENT paper (author+, year, publisher?)><!ATTLIST paper id ID #REQUIRED><!ELEMENT author (firstname*, lastname)><!ATTLIST author age CDATA #IMPLIED><!ELEMENT firstname (#PCDATA)><!ELEMENT lastname (#PCDATA)><!ELEMENT year (#PCDATA)>
<!ELEMENT publisher (#PCDATA)>...
]> DTD
© Steffen Staab
Syntax ist nicht ausreichend
<Bestellung><Anzahl>500</Anzahl><Objekt>Schekel</Objekt>.....
</Bestellung>
?
Hintergrundwissen/Kontext:Die israelische Währung ist der Schekel (Mehrzahl: Schekelim), offiziell NeuerIsraelischer Schekel (NIS). Er setzt sich aus 100 Agorot (Einzahl: Agora ) zusammen
© Steffen Staab
Hinter XML steckt noch mehr...
Moduln/NamensräumeXLink, XPoint: Einbetten von Links und
Verzweigungen (zum Aufbau von Graphstrukturen)
XML-Stylesheets CSS, Cascading Style Sheets (z.B. für HTML) XML-Transformationen (XSLT) Knotentests (mit Prädikaten)
XPATH: Adressierung von Elementen im GraphXML-QL: Anfragesprache
XML: ein Blick zurück
Sind mit XML die Probleme von Frame-Sprachen beseitigt worden?
Mengenwertige Attribute UND- oder ODER-Semantik? Anzahlbegrenzung? <!ELEMENT author (firstname*, lastname)> firstname
firstname
firstname
lastname
author-1
XML vs. Frame-Systeme
+ Datenbeschreibung vs. Daten - Kategorien vs. Objekte- Indefinites Wissen
Mercedes-Fahrer OR BMW-Fahrer- Negation
Not Rolls-Royce-Fahrer"
RDF: Resource Description Format
Nicht alle Daten symbolisch beschreibar (z.B. AV-Daten)
Idee: Beschreibung von "Daten" durch Zusatzangaben (Meta-Daten)
Verfügbare "Daten" werden als Ressource aufgafaßt Ressourcen sind durch URI's gekennzeichnet
URI: Unified Resource Identifier, Ressourcenbeschreibungen Ressourcen haben Eigenschaften (Properties)
Beziehungen zu anderen Ressourcenoder atomare Werte
Aussagen über Ressourcen (Statements) "Ressource x hat Eigenschaft y mit Wert z"
Kategorien: RDF(S)
RDF: Resource Description Format(Schemata) Beschreibung von Kategorien (Klassen)
Idee: Festlegung von Ober- und Unterkategoriebeziehungen Damit Maschinen die Bedeutung von Metadaten
erfassen können, sind Standard-Schemata nötig PICS (Platform for Internet Content Selection):
Schema zur Beurteilung von Internet-InhaltenWorld Wide Web Consortium: PICS Rating Vocabularies in XML/RDF, W3C NOTE
DC (Dublin Core): Schema zur Beschreibung von InhaltenDublin Core Metadata Initiative. (http://purl.org/dc)
Ausdrucksstärke stark eingeschränkt
Kategorien: XMLS, XML-Schema
Beschreibung einer Menge (Klasse) von "Dokumenten"
Kernideen: Spezifikation des Typs von Elementen Spezifikation der Min/Max-Anzahl von Elementen
Details: http://www.w3.org/TR/xmlschema-0/
XML-Schema: Typen Typdefinition durch
Erweiterung (engl. extension) oder Restriktion (engl. restriction) einer bestehenden Typdefinition
Alle Typen in XML-Schema sind entweder Atomare Typen (z.B. string, int) oder Erweiterung bzw. Restriktion bestehender Typen
Alle Typen bilden eine Typhierarchie Baum mit Wurzel: Typ Zeichenkette Keine Mehrfachvererbung
Typen sind entlang der Typhierarchie abwärtskompatibel: Für Typinstanzen gilt das Substituierbarkeitsprinzip Elemente eines bestimmten Typs akzeptieren auch Daten einer
Erweiterung oder Restriktion des geforderten Typs
XML-Schema
Es soll viel mehr "Semantik in einem Schema eingefangen werden" als mit DTDs
Für viele Anwendungen reicht die Modellierungskraft nicht (siehe die Kritik an Frame-Systemen)
Was heißt "Semantik in einem Schema einfangen" ?
XML-Schema noch kein W3C-Standard
Web-Kontext: Viele, meist unbekannte Partner
© Rudi Studer
RDF(S) und XML-Schema: Probleme
Verarbeitung von Informationen an einem Knoten nur möglich, wenn Repräsentationsschema bekannt
Verwendung unterschiedlicher Schemata an unterschiedlichen Knoten
Leicht: netzwerkweiter Zugriff auf SchemataHart: Berücksichtigung der Bedeutung der in
einem Schema repräsentierten Begriffe bei der Verarbeitung
Bedeutung ist relativ zu verstehen!
Ontologie
Ursprünglich eine philosophische Disziplin zur Untersuchung und Beschreibung der Realität Wissenschaft vom Seienden vgl. Aristoteles
„Metaphysik“In der Informatik wird der Begriff Ontologie
häufig folgendermaßen definiert: "An ontology is an explicit, formal specification
of a shared conceptualisation." [Gruber 95] Symbolische Art und Weise, eine Welt zu
modellieren
© Steffen Staab
Gemeinsame Konzeptualisierung
Verständnis eines Anwendungsbereichs getragen von einer Gruppe von Menschen, z. B.
einer Abteilung intensionale Charakterisierung der relevanten
Konzepteund Beziehungen eines Anwendungsbereiche
Gekennzeichnet wohldefiniertes Vokabular an Lexemen (lexical entries)
einheitliches Verständnis welche Begriffe (concepts) und Beziehungen (relations) durch die Lexeme referenziert werden
© Steffen Staab
Syntax, Semantik, Pragmatik
Syntax: Menge von Zeichen (Symbolen, Lexemen), Zeichen tragen Bedeutung für Menschen, nicht für
eine MaschineSemantik: Beziehungen zwischen den Zeichen
und der realen (oder einer fiktiven) Welt Pragmatik: Welche Zeichen werden zu
welchem Zweck wie gebraucht?
Semiotisches Dreieck
© Steffen Staab
Abbildung von Symbolen auf Dinge der Welt
© Steffen Staab
Gemeinsames Verständnis bei der Kommunikation
© Steffen Staab
Ontologien
Menge von Annahmen, die dazu dienen die Abbildung von Symbolen auf Dinge der Welt weniger mehrdeutig zu machen
Kommunikation kann nur stattfinden, wenn bezüglich der Annahmen Konsenz herrscht
© Rudi Studer
Die Idee des Semantic Web
Bei Interpretation (z.B. zur Recherche) von Web-Daten auf Bedeutung Bezug nehmen
Nicht nur oberflächennahe, syntaktische Operationen anbieten
Zusammenfassung, Kernpunkte
Abriß der Historie von Repräsentationssprachen Von Frames und Semantischen Netzen zu
XML und RDF Neuerdings: Wildwuchs an
Standardisierungsvorschlägen Primär "Vererbung" als Inferenzschema Ausdrucksstärke (z.B. XML/RDF(S)) zu schwach Syntax und Tools im Vordergrund, nicht Semantik
Die Idee des Semantic Web Semantik im Vorderung, nicht Syntax oder Präsentation
Was kommt beim nächsten Mal?
Beschreibungslogiken als Grundlage für formale Repräsentations- und Inferenzsysteme
Grundlage von Ontologien