Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
se:wissensverarbeitung [2008-07-21 11:20] stefan |
se:wissensverarbeitung [2014-04-05 11:42] |
||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
- | ====== 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 10<sup>11</sup> 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 ===== | ||
- | * <del>Prolog-Aufgaben S. 45/46 und</del> 49 | ||
- | * Beispielrechnung Defuzzyfikation S. 55 | ||
- | * Aufgaben S. 65/66 | ||
- | * Fuzzy-System S. 51 | ||
- | * <del>Missionare/Kannibalen-Problem</del> | ||
- | * Praktikumsaufgaben | ||
- | * "Ein ehrliches Strandvergnügen" | ||
- | * Abenteurer, max. 4 Tagesrationen Nahrung, 5 Lager bis Ziel | ||
- | * Programm Beweisführung S. 23 | ||
- | * Beratungssystem mit Fuzzy Logic | ||
- | * Optimierungsverfahren | ||
- | * Klausur WS 05 | ||
- | * Klausur SS 07 | ||
- | * <del>Kurvenapproximation durch Perceptrons</del> | ||
- | * 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 | ||