Upload
ursula-brodbeck
View
215
Download
0
Embed Size (px)
Citation preview
SMART Systems (Vorlesung: KI & XPS)
Systems based on Symbol-Manipulating Automated Reasoning Techniques
Voraussetzungen: Algorithmen und Datenstrukturen (z.B. Suche, Sortieren) Grundlagen der Programmierung
Vorteilhaft: XML, RDF, Verteilte Systeme, Datenbanken
Ralf Möller, Univ. of Applied Sciences, FH-Wedel
SMART Systems (Vorlesung: KI & XPS)
Lernziele der Vorlesung allgemein: Fundamente: Überblicke, Grundprinzipien Techniken: Modellierung, Schlußverfahren Anwendungen im Verteilte-Systeme-Kontext
Lernziele heute: Einführung in das Gebiet "Künstliche Intelligenz"
(KI) Grundidee und Probleme von "Expertensystemen" Prinzipien "einfacher" Verfahren Ausrichtung und Fokus dieser Vorlesung:
Frühzeitig "ran" an die praxisorientierten Themen
Ziele der KI als Teilgebiet der Informatik
KI hat ingenieurwissenschaftliche und kognitionswissenschaftliche
Ziele
Ingenieurwissenschaftliche Ziele:Intelligente Systeme konstruieren
Verbindungen zu den Gebieten- Formale Logik- Statistik / Stochastik- Signalverarbeitung- Regelungstechnik
Kognitionswissenschaftliche Ziele:Menschliche Intelligenz "erklären"
Verbindungen zu- Biowissenschaften- Psychologie- Linguistik- Philosophie © Bernd Neumann
Sichten auf das Gebiet KI
Untersuchungen zur menschlichen Kognition... sind notwendig für Systeme in denen eine
"quasi-natürliche" Interaktion angestrebt wird Übersetzung natürlicher Sprache Generierung von Graphiken (z.B. in Handbüchern)
... sind ein interessantes ForschungsgebietAber: In dieser Vorlesung nicht im Fokus Hier: Konstruktion Intelligenter Systeme (IS)
KI/IS - Die Urzeit
Problemlösen durch Suche in einem Zustandsraum Beispiel: Missionare und Kannibalen, Wasserkrug-Problem
Suche und Optimierung Beispiel: 16-er Puzzle, Fahrplanauskunft Systematische Suche der besten Lösung: A*-Algorithmus Stochastische Suche: z.B. "Genetische" Algorithmen
2-Personen-Nullsummenspiele Beispiel: Tic-Tac-Toe, Dame, Schach Basisverfahren: Minimax-Algorithmus, -Beschneidung
Wasserkrugproblem
© Uwe Schmidt
Wasserkrugproblem (2)Zustand:
Zustandsübergänge:
© Uwe Schmidt
Wasserkrugproblem (3)
© Uwe Schmidt
Suchgraph ohne Zyklenerkennung
Suchgraph mitZyklenerkennungSuchstrategien:
Tiefensuche Breitensuche
Wasserkrugproblem (4)
© Uwe Schmidt
Kosten und Finden eines "besten Weges"Annahme: das "Überschreiten" einer Kante zwischen
Knoten ni und nj im Suchraum verursacht bestimmte Kosten c(ni, nj)
Kosten g(n) für einen Knoten n: Summe der Kantenkosten bis zum Startknoten
Tiefensuche vs. BreitensucheBest-First-Traversierung des SuchraumsA*-Algorithmus (später detaillierter)
Betrachte nicht nur g(n), sondern auch Abschätzung h(n) zum Ziel: Knotenkosten f(n) = g(n) + h(n)
KI/IS - Die Frühzeit: Expertensysteme
Problemlösung durch Anwendung von Wissen: Ersetzung/Replizierung eines menschlichen Experten Zustandsraum nicht ausreichend: "Wissen"
notwendigWissensakquisition beim/mit dem "Experten"Wissensrepräsentation
Relationale Modellierungsstrukturen Regelsysteme zur Manipulation der Strukturen Logische Programmierung (z.B. Prolog)
Statistik/Stochastik/Wahrscheinlichkeitstheorie Neuronale Netze
XPS klassischer Ausprägung
Softwaresysteme mit speziellem Aufgabenbereich: Medizinische/technische Diagnose Konstruktion technischer Geräte/Systeme Beratungssysteme ...
Motivation der Problemlösungsstrategie durch "Nachahmung" des Vorgehens eines "Experten"
… 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: z.B. Diagnose
© Bernd Neumann
ArbeitsspeicherRegelmenge
Hinzufügung
Regelverkettungsstrategien
Vorwärtsverkettung: Gegeben: Symptome Frage: Kann durch Regelanwendung als Konsequenz
eine Diagnose abgeleitet werden?Rückwärtsverkettung:
Gegeben: Diagnose, die bestätigt werden soll Frage: Ist es möglich, die gesuchte Diagnose aus den
Vorbedingungen von Regeln abzuleiten?Mixed-mode ggf. unter Benutzerbefragung
Nicht alles muß direkt im Arbeitsspeicher stehen
XPS und Regelsysteme - Probleme? Mehrdeutigkeiten:
Struktur und Bedeutung der manipulierten Einheiten unklar Kontrollstrategie: Was passiert, wenn mehrere Regeln in einer
bestimmten Situation anwendbar sind? (Negation!) Nur operationale Semantik, kein Korrektheitsbegriff Modellbildungsaufwand, Wiederverwendbarkeit Reihenfolge der möglichen Fragen an Benutzer
willkürlichan maschineller Kontrollstrategie orientiert
Kopplung mit Software-Infrastruktur aufwendig Wissensakquisitionsgedanke oft boykottiert Vorgehen des Menschen nicht immer optimal
Später: Assistenzsysteme (1)
Einbettung von Techniken zur Unterstützung des Menschen in Standard-Softwaresystemen
Anwendungen: Hilfesysteme
Später: Assistenzsysteme (2)
Einbettung von Techniken zur Unterstützung des Menschen in Standard-Softwaresystemen
Anwendungen: Übersetzungssysteme
Später: Assistenzsysteme (3)
Einbettung von Techniken zur Unterstützung des Menschen in Standard-Softwaresystemen
Anwendungen: Layout
IS - Warum keine Simulation des Menschen?
Nachahmung hoffnungslosIn der Anwendung werden
(Teil-)Funktionalitäten benötigt, die kein Vorbild haben
Beherrschbarkeit von InformatiksystemenSoftware-Engineering-Prinzipien notwendig
Siehe auch die Vorlesung "Software-Engineering"Modularisierung notwendig
Neue Generation von XPS-Techniken
KorrektheitsbegriffErklärungsfähigkeitVerwendung von (deklarativen) ModellenSpezielle Modellierungstechniken
z.B. modellbasierte Diagnose z.B. Konfigurierungssysteme
Grundprinzip:
• Konsistenzbasierte Diagnosesystematisches Zurückziehen von Korrektheitsannahmen, die mit den Beobachtungen nicht konsistent sind
• Verhaltensbasierte Diagnosesystematisches Suchen von Verhaltensmodellen, die Übereinstimmung mit Beobachtungen ergeben
Meßwert-vorschläge
vorhergesagtes Verhalten
Fehler-annahmen
beobachtetes Verhalten
Physikalisches System
Computer-internes ModellAbweichungen
Modellbasierte Diagnose
© Bernd Neumann
Kabinenlayout für Passagierflugzeuge
Plazierung der Kabineneinrichtung (Sitze, Küchen, Toiletten, etc.) unter Berücksichtigung von:• Kundenwünschen• Technischen Möglichkeiten• Legalen Beschränkungen• Optimalitätskriterien
Konfigurierung
© Bernd Neumann
Was ist das Gemeinsame hinter den Kulissen?
Beschreibung von Objekten einer AnwendungAuf welchen Techniken basiert die
Problemlösung?Lassen sich Grundprinzipien erkennen? Ja! Davon berichtet diese Vorlesung!Die Vorlesung vermittelt Grundlagen, um z.B.
obige Anwendungen in sicherer Weise mit minimalem Aufwand zu erstellen
Bezug dieser Vorlesung zu WI und MI
Erklärung von Repräsentationssprachen anhand von Beispielen in Geschäftsanwendungen
Grundlagen der Modellbildung und ModellierungPraktisch verwendbare
Repräsentations- und AnfragesprachenInferenzdienste und -algorithmenSMART-Systems:
Systems based on Symbol-Manipulating Automated Reasoning Techniques
Abgrenzung: RobotiksystemeTechnische Systeme
Signalverarbeitung dominiertKennzeichen
Autonomie Beweglichkeit Sensoren Aktuatoren
SciFi-Beispiele R2D2, C3PO
Aktuell: RoboSoccer
Abgrenzung: Subsymbolische Modellierung
Handschrifterkennung
Das Mehrschichtensystem "lernt" handgeschriebene Zeichen zu erkennen.Dabei "lernen" die verborgenen Zellen (hidden units), wichtige Merkmale in der Eingabe zu erkennen.
0 1 2 3 4 5 6 7 8 9
© Bernd Neumann
Der Anwendungskontext: Vernetzung
intranet
ISP
desktop computer:
backbone
satellite link
server:
network link:
Voraussetzungen für SMART-Systems
Middleware für verteilte SystemeTechnische Voraussetzungen für Verteilung
und Strukturierung (z.B. Agenten)Siehe die Vorlesung "Realisierung verteilter
Anwendungen"Verteilte
Geschäfts-anwendungen
Ein Szenario
Unternehmensübergreifende Standards
zur Produktmodellierungzum Informationsaustausch (B2B, B2C,
App2App) Stichwort: Enterprise Application Integration Nicht die Übertragung von Daten macht Probleme,
aber die Bedeutung der ausgetauschten Informationseinheiten
XML, RDF
XML: eXtensible Markup Language Nur syntaktische Einschränkung von
Graphstrukturen durch DTDs (Document Type Definitions)
Nur für Menschen "lesbar"RDF: Resource Description Framework
Metadaten zur Beschreibung von DatenGrundlagen von Beschreibungssprachen
Repräsentationsmittel und derenformale Semantik
InferenzenWas kann ich hier lernen?
SMART-Systems
Netzwerkorientierte Softwaresysteme, ... Server, Komponenten, Agenten
... die in klassische Anwendungen (z.B. E-Business-Systeme) eingebettet werden,
in Kommunikation miteinander treten,ihre Umgebung befragen (Sensoren) und auch
beeinflussen (Aktoren) sowieplanen und handeln, um ein (vorgegebenes) Ziel zu erfüllen
Warum SMART-Systems?
Heterogenität der Umgebungen Wechsel der Umgebung bei Agenten Modularisierungsgedanke auch bei statischer
UmgebungImplizite Voraussetzungen bei der
Kommunikation mit der Umgebung Systeme von Begrifflichkeiten (Ontologien) Konventionen oder "Übersetzung" notwendig Schließen über implizite Informationen notwendig ggf. durch Vermittler (Broker)
Warum SMART-Systems?
Software- oder Werkzeug-orientierte Sicht auf verteilte Systeme reicht nicht!
OOA- und OOD nicht für heterogene SystemeRepräsentationstheorie für Begrifflichkeiten,
Ereignisse, Vorgänge und raum-zeitliche Phänomene notwendig (vgl. DB-Theorie)
Theorie der Ereigniserkennung, des Planens, des Handelns und der Kommunikation erforderlich
Automat. Schließen über implizite Informationen
Aktuelles Schlagwort: Wissensmanagement
Wirtschaftswissenschaft: z.B. Arbeitsorganisation
Informatik: z.B. das "Semantic Web"Bereitstellung und Suche von InformationenInformationen im Web
nicht nur für denMenschen "lesbar"
Informationen im Webzur maschinellenVerarbeitung
Diese Vorlesung: SMART-Systems
Formale Repräsentations- und InferenzsystemeWichtig aus Sicht der WI und MI:
Verstehen der Grundlagen des "Semantic Web" Verstehen der Grundlagen von Agentensystemen
Übertragung in andere Anwendungskontexte z.B. Diagnose, Konfigurierung, Bild- und
SprachverstehenAus Sicht der Forschung:
Neue Repräsentationsstrukturen Neue Inferenzalgorithmen zur Anfragebeantwortung
Probleme und Herausforderungen
Repräsentationssprachen Syntax und Semantik (letzteres ist wichtiger!)
Anfragesprachen (Inferenzdienste) Pragmatik
Informationsintegration: Schließen über Schemata
Schließen über WissenszuständeErmangelungsschließen / NichtmonotoniePlanen und KonfigurierenLernen
Literatur, Details und Zusatzinformationen
http://www.fh-wedel.de/~mo/lectures/smart.htmlHandbuch der Künstlichen Intelligenz
G. Görz, C.-R Rollinger, J. Schneeberger (Hrsg.)Principles of
Knowledge Representation G. Brewka (Hrsg.)
Semantic Web: Systeme und Werkzeuge
Universitäten: http://kogs-www.informatik.uni-hamburg.de/~race/ http://www.cs.man.ac.uk/FaCT http://img.cs.man.ac.uk/oil ...
Firmen: http://www.wimmelvonbargen.de/ http://www.ontoprise.de/ http://www.networkinference.com/ ...
Organisatorisches
Sprechstunde RM: Dienstag nachmittagKlausur
Wann? Am Ende des Semesters Wo? Wie lernt man für dieses Fach?
Wiedergeben Anwenden Übertragen
Übungen zur Klausurvorbereitung unter: http://www.fh-wedel.de/~mo/lectures/smart.html
Was kommt beim nächsten Mal?
Wir werden konkreter und ...... diskutieren Repräsentations- und
Inferenzechniken ...... anhand von Beispielen in
GeschäftsanwendungenInsbesondere: "Ontologien" und die
Herausforderung des "Semantic Web"