====== Wissensverarbeitung ====== ===== Informationen ===== * [[http://hci.stanford.edu/~winograd/shrdlu/|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 * {{:se:problemmengen.jpg|}} * 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 Zustands**baum** 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 - Was ist der einfachste Sonderfall und was ist in diesem Fall zu tun? - Was ist der nächst kompliziertere Fall und was ist dann zu tun? - Was ist der nächst kompliziertere Fall und wie kann dieser auf den vorherigen abgebildet werden? - Welches ist der allgemeine Fall und wie kann dieser auf den vorherigen abgebildet werden? - Lässt sich der zweite Fall ebenso auf den ersten zurückführen? - 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. * {{:se:aufbauexpertensystem.jpg|Aufbau eines Expertensystems}} * 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 1011 Neuronen. * {{:se:aufbauneuron.jpg|}} * 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