Wissensverarbeitung

Wissensverarbeitung

Informationen

SHRDLU (offizielle Seite mit grafischem Java-Programm)

Lernziele

Einleitung
- Was bedeutet Wissensverarbeitung?
- Was unterscheidet Wissensverarbeitung von Datenverarbeitung?
- Warum und wozu ist diese andere Art der Computerprogrammierung erforderlich?
- Welche grundsätzlich unterschiedlichen Systeme gehören dazu?
- Wie sind diese aufgebaut und wie arbeiten sie?
Wissen
- Woraus besteht Wissen?
- Wie kann man Wissen strukturieren und darstellen?
- Wie kann man Wissen in formalen Sprachen formulieren?
Wie kann man mit Wissen Probleme lösen?
- Was ist ein Zustandsraum?
- Wie kann man daraus einen Zustandsbaum machen?
- Welche Suchverfahren im Zustandsbaum gibt es?
- Was ist Backtracking und wofür benötigt man es?
- Was ist eine Heuristikfunktion und insbesondere eine A-Heuristik?
- Was ist ein UND-ODER-Baum?
- Wie funktioniert Rekursion und warum ist sie für das Problemlösen wichtig?
Expertensysteme
- Aus welchen Komponenten ist ein Expertensystem aufgebaut?
- Wofür kann man es anwenden?
- Welche Arbeit muss dabei der Mensch übernehmen?
- Welche klassischen Beispiele gibt es?
- Warum sind Schachcomputer so schlecht?
- Was ist eine Inferenzmaschine?
- Wie kann man ein Expertensystem realisieren?
Expertensystem-Implementierung in Prolog
- Wie kann Wissen verschiedener Art in Prolog formuliert werden?
- Welche inneren Vorgänge werden beim Bearbeiten eines Goals bearbeitet?
- Wie geht man mit Listen um?
- Wie erstellt man ein Prolog-Programm mit SWI-Prolog, bringt es zum Laufen und testet es?
- Wie nutzt man die Standardprädikate sinnvoll?
- Wie implementiert man ein Planungssystem in Prolog?
- Wie implementiert man ein Beratungs- oder Diagnosesystem in Prolog?
- Für welche anderen Aufgaben kann Prolog eingesetzt werden?
Verarbeitung von ungenauem Wissen
- Wie können unscharfe (fuzzy) Mengen beschrieben werden?
- Wie werden Ausdrücke in Fuzzy Logic ausgewertet?
- Was ist das Ergebnis eines Fuzzy-Reglers bei gegebenen Eingangsgrößen?
- Wie kann man mit Prolog ein Fuzzy-System entwickeln?
Künstliche Neuronale Netze
- Wie kann der Lernvorgang eines Neurons beschrieben werden?
- Wie kann das Schaltverhalten eines Neurons mit den Eingängen x1 und x2 in der x1/x2-Ebene dargestellt werden?
- Wie bemisst man aus einem gewünschten Schaltverhalten die Gewichte eines Neurons?
- Wie können Neuronen und verschiedene KNN skizziert werden?
- Wie wählt man zu einem gegebenen Problem ein geeignetes neuronales Netz aus und dimensioniert dieses?
- Wie kann der Lernvorgang einer SOM beschrieben werden?
Data Mining
- Wofür braucht man Data Mining bzw. wo kann es eingesetzt werden?
- Was sind die wichtigsten Verfahren des Data Mining und wie funktionieren sie?
- Wie können diese Verfahren realisiert werden?
Globale Optimierung
- Warum ist Optimierung so schwierig?
- Was sind die wichtigsten Verfahren der globalen Optimierung?
- Wie können diese Verfahren realisiert werden?

Zusammenfassung des Skripts

Einleitung

Definition Wissensverarbeitung
- Wissenschaft, die sich mit Beschleunigung, Rationalisierung und Automatisierung der Transformation von Wissen in Informationen und umgekehrt befasst.
- Informationen werden aus der Umgebung exzerpiert und als Wissen gespeichert; aus gespeichertem Wissen werden Informationen gewonnen, die sinnvolles Handeln und Entscheiden ermöglichen.
Methoden
- künstliche Intelligenz (Simulation menschlicher Intelligenz)
  - Beschäftigung mit Methoden, die es Computern ermöglichen, Aufgaben zu lösen, zu denen Intelligenz nötig ist, wenn sie von Menschen durchgeführt werden.
  - Nachweis: Turing-Test
  - findet nicht unbedingt die beste Lösung, aber eine brauchbare mit vertretbarem Aufwand (siehe Travelling Salesman)
- Heuristik (Anwendung von menschlichen Problemlösungsverfahren in der Programmierung)
- automatisiertes Erkennen (Bild- und Spracherkennung)
Themengebiete
- Art, Struktur und computergerechte Speicherung des Wissens
- Extraktion von Wissen aus Informationen
- Generierung von Informationen aus Wissen
Probleme
- Komplexität der Aufgabe
- Ohnmacht der Computer
  - Programm ist niemals schlauer als Programmierer
  - Computer benötigen klare Algorithmen, ihnen fehlt die Kreativität und Intuition
  - Beispiel: Travelling Salesman
Abgrenzung zur Datenverarbeitung
- Problemlösung
  - Programmierer löst das Problem durch Finden eines Algorithmus
  - Computer löst das Problem durch Anwendung von Wissen
- Lösungsweg
  - Der Lösungsweg ist vorherbestimmt (Algorithmus)
  - Der Lösungsweg ist nicht vorherbestimmt
- Wissen
  - Das erforderliche Wissen steckt in den Funktionen des Programms
  - Das erforderliche Wissen ist unabhängig von der Funktion des Programms
Wissensbasierte Systeme
- Transformation Wissen <> Information
- Information → Wissen durch Menschen
- Wissen → Information durch System
Denkende Computer
- Schlussfolgerung
  - Logik, Prinzip der klassischen Expertensysteme, Wissen nicht präzise formulierbar → Fuzzy Logic
- Künstliches Gehirn (neuronale Netze)
- Datenbergwerk (Data Mining)
- Globale Optimierung
- Kombinationen der 4 oberen Verfahren

Wissen

Wissen besteht aus
- Fakten
  - gebunden an Objekte
    - Eigenschaften und Methoden
    - Instanzen von Objektklassen (für Attribute lediglich Slots)
    - Vererbung ist möglich (Taxonomie)
- Regeln
- Metawissen
Darstellung von Objektwissen in Frames oder assoziativen (OAW-)Tripeln (Vorteil OAW: stets gleiche Struktur)
Darstellung von Objektbeziehungen in Frames oder semantischen Netzen
Darstellung von Regelwissen
- Dämonen an jedem Slot: if-needed (trigger) und if-changed
- Formulierung in einer formalen Sprache
- Prädikatenlogik
  - Teilgebiet der mathematischen Logik
  - Ermöglicht präzise Formulierung von Fakten und Regeln
  - Prädikat: Satzaussage

Wie kann man mit Wissen Probleme lösen?

Denkansätze
- Suche im Zustandsraum
- Problemreduktion
- Rekursion
- Vorwärts-/Rückwärtsverkettung (Forward/Backward Chaining)
Suche im Zustandsraum
- Suche nach dem optimalen Weg durch einen gerichteten Graphen, der alle Zustände des Systems als Knoten und alle Operatoren als Kanten enthält
- Umwandlung in Zustandsbaum durch Verbieten bereits besuchter Zustände
- Suchverfahren
  - Tiefensuche
    - Backtracking
  - Breitensuche
    - Least-Cost-Suche
    - Heuristische Suche / Best-First-Suche
      - A-Heuristik: Heuristik (Schätzfunktion), die die Summe des bisherigen Aufwands mit einer Schätzung für den Restaufwand verbindet
Problemreduktion
- Zerlegung des Problems in Teilprobleme, bis Teilprobleme direkt aus der Wissensbasis lösbar sind
- Darstellung als UND-ODER-Baum
- Auf ODER-Knoten können wieder die obigen Suchverfahren angewandt werden
Rekursion
- Sonderfall der Problemreduktion
- Lösungsverfahren für Problem ist auch für Teilprobleme anwendbar
- Vorgehensweise
  1. Was ist der einfachste Sonderfall und was ist in diesem Fall zu tun?
  2. Was ist der nächst kompliziertere Fall und was ist dann zu tun?
  3. Was ist der nächst kompliziertere Fall und wie kann dieser auf den vorherigen abgebildet werden?
  4. Welches ist der allgemeine Fall und wie kann dieser auf den vorherigen abgebildet werden?
  5. Lässt sich der zweite Fall ebenso auf den ersten zurückführen?
  6. Formulieren des Gesamtalgorithmus

Expertensysteme

Definition: System, das nach Eingabe des Wissens eines Experten, Probleme aus dem Fachgebiet dieses Experten selbstständig lösen kann.
Die Bestandteile des Systems können standardisiert werden.
Anwendungsbereiche
- Planungssysteme
- Diagnosesysteme
- Beratungssysteme
Transformation von Informationen zu Wissen ist dem Menschen vorbehalten

Expertensystem-Implementierung in Prolog

Prolog
- deklarative Programmiersprache
- Wissensdarstellung
  - Prädikatenlogik
  - Meta-Wissen: Problemlösungsverfahren
- Problemlösungsmechanismen
  - Rückwärtsverkettung
  - Rekursion
  - Tiefen-/Breitensuche
  - Backtracking
  - Pattern Matching
  - Unifikation von Variablen
Syntax
- Variablen: großer Anfangsbuchstabe, Konstanten: kleiner Anfangsbuchstabe, anonyme Variable: _
- Arity: Anzahl der Parameter eines Prädikats
Goal ist eine Anfrage an das Programm
Unifikation/Bindung von Variablen
Box-Modell: call, redo, exit, fail
Standardprädikate
- write, nl, writenl
- asserta, assertz, assert, retract, abolish
- fail, cut
- member, sort, msort, reverse, append
- findall

Verarbeitung von ungenauem Wissen

Unscharfe Mengen
- Die Zugehörigkeit eines Objekts zu einer Menge wird nicht mit wahr oder falsch, sondern mit einem Zugehörigkeitswert zwischen 0 und 1 beschrieben.
- Der Wertebereich einer linguistischen Variablen kann in linguistische Werte unterteilt werden.
- Die Zugehörigkeit eines numerischen Werts zu einem linguistischen Wert wird über eine Zugehörigkeitsfunktion (meistens Dreiecks- oder Trapezfunktionen) beschrieben.
- Die Umsetzung eines numerischen Wertes in einen oder mehrere linguistische Werte mit Zugehörigkeitswert wird Fuzzyfikation genannt.
Fuzzy Logic
- x UND y → minimum(x, y)
- x OR y → maximum(x, y)
- not x → 1 - x
Expertensystem mit Fuzzy Logic
- OAW-Tripel werden zu VWZ-Tripeln
Fuzzy Control

Künstliche neuronale Netze

Das menschliche Gehirn besteht aus 10¹¹ Neuronen.
Vernetzung Synapse → Axon
Lernen beruht auf Änderung der Synapsenstärke
Lerntypen
- überwacht: dem neuronalen Netz müssen auch die korrekten Antworten vorgegeben werden
- nicht überwacht: das Netz lernt selbstständig die ihm angebotenen Informationen zu unterscheiden
Aufgaben: Klassifikation, Rekonstruktion und Erkennung von Mustern
Aufgaben des Entwicklers
- Auswahl des geeigneten Netztyps und Konfiguration
- Aufbereitung der Muster
- Bereitstellen von Trainingsmaterial
Perceptron
- Bildet eine n-dimensionale Eingangsinformation auf eine m-dimensionale Ausgangsinformation ab
- Ausgänge sind nicht rückgekoppelt → Feed-Forward-Netz
- Lernen durch Anpassen der Eingangsgewichte mittels Soll-Ist-Vergleich → überwachtes Lernen
Hebb'sche Regel
- Wer Recht hat, wird gestärkt, wer Unrecht hat, wird geschwächt.
- Vereinfachte Lernregel: Wenn das Ergebnis falsch ist, wird (Sollergebnis * Eingangsvektor) zum Gewichtsvektor addiert.
Grenzen
- Lineare Separierbarkeit → RBF-Neuron oder Mehrschicht-Perceptron
Mehrschicht-Perceptron
- verdeckte Schichten (Anzahl und Größe: Erfahrungswerte)
- Lernen durch Backpropagation
- Eignung: Klassifizierung von Mustern/Kurvenapproximation
Hopfield-Netz
- rückgekoppeltes Perceptron
- Eignung: Rekonstruktion von Mustern
Kohonen-Netz (SOM = Self Organizing Map)
- nicht überwachtes Lernen
- die Neuronen, die am dichtesten am Eingangssignal liegen, werden in Richtung desselben verschoben
- Auswertung meist mit nachgelagertem Mehrschicht-Preceptron

Data Mining

Ziel: Zusammenhänge und Auffälligkeiten in Datenbeständen finden
Verfahren
- Clusteranalyse
  - Cluster finden
    - Least-Cost-Suche, dann Weg an längsten Wegen auftrennen
    - Kohonennetz mit nachgeschaltetem Backpropagation-Netz
  - Besonderheiten (Punkte außerhalb der Cluster) untersuchen
- Assoziationsanalyse
- Zeitreihenanalyse

Globale Optimierung

Verfahren basieren auf zufälligen Änderungen und nicht auf zielgerichteten Algorithmen
Stochastische Verfahren (pro Schritt eine neue Kombination: besser → weiterverfolgen, schlechter → vielleicht weiterverfolgen)
- Simulated Annealing (Wahrscheinlichkeit, dass schlechtere Kombination weiterverfolgt wird, wird langsam verringert)
- Sintflut-Verfahren (schlechtere Kombination wird weiterverfolgt, wenn sie besser ist als ein ansteigender Grenzwert)
- Threshold Accepting (schlechtere Kombination wird weiterverfolgt, wenn die Verschlechterung kleiner ist als ein abnehmender Grenzwert)
Evolutionäre Verfahren (pro Schritt mehrere neue Kombinationen, Auswahl der besten hiervon)
- Evolutionsstrategien (Nachfolgeversionen werden durch Mutation der Vaterversion erzeugt)
- Genetische Algorithmen (Nachfolgeversionen werden durch Kombination des Elternpaares erzeugt)
- Variationen: Eltern werden in die neue Generation mit aufgenommen oder nicht, oder vergreisen

ToDo

~~Prolog-Aufgaben S. 45/46 und 49~~
~~Beispielrechnung Defuzzyfikation S. 55~~
~~Aufgaben S. 65/66~~
~~Fuzzy-System S. 51~~
~~Missionare/Kannibalen-Problem~~
~~Praktikumsaufgaben~~
~~Handlungsreisender S. 46~~
~~"Ein ehrliches Strandvergnügen"~~
~~Abenteurer, max. 4 Tagesrationen Nahrung, 5 Lager bis Ziel~~
~~Beratungssystem mit Fuzzy Logic~~
~~Klausur WS 05~~
~~Klausur SS 07~~
~~Optimierungsverfahren~~
~~Kurvenapproximation durch Perceptrons~~
~~Programm Beweisführung S. 23~~
~~Typen von neuronalen Netzen (verteilt, vernetzt, rückgekoppelt etc.) S. 59~~
~~Backpropagation (of error)~~
~~Hopfield-Netz~~
~~Minimax- und Alpha-Beta-Algorithmus~~
~~Informationen zu Systemen: MYCIN, EMYCIN, PUFF, XCON, PROSPECTOR, MOVER, SHRDLU, Ham-RPM, ELIZA~~
~~Expertensystemshells: NEXPERT Object, Smart Elements, KEE, EMYCIN, TWAICE~~