Wissensverarbeitung für Wirtschaftsinformatiker

Jürgen Dorn und Markus Stumptner

Achtung: Diese Mitschrift ist nicht autorisiert. Für Fehler und Auslassungen bin ich allein verantwortlich, weder die Professoren, noch die Tutorin.

Aktuelle Informationen zur Vorlesung

2000-03-06

2000-03-13

2000-03-20

2000-03-27

2000-04-03

2000-04-10

2000-05-08

2000-05-15

2000-05-22

2000-05-29

2000-06-19

2000-03-06

Prüfung und Klausur: 16. 6. 2000 (vor allem Fragen zu Prolog)

Komplettes Skriptum kommt später erst raus; kann in Teilen von der Homepage runtergeladen werden. (Wenn es nicht verständlich ist, bitte melden.)

Übung:

Vier Aufgaben müssen in Prolog gelöst werden.

Unterstützung durch Tutorin: Bibiane Angerer

Termine: per e-mail anfragen, default Freitag 14-16 Uhr Favoritenstraße 11 Praktikumsraum HE 03.24, 3. Stock. 1. Termin: 17. 3. 14 Uhr, Einführung in SWI am PC.

SWI Prolog von der Uni Amsterdam (Link von der Übungshomepage).

Die Aufgaben müssen der Tutorin vorgeführt werden.

Eine Gruppe darf höchstens 3 Mitglieder haben, auch Einzelarbeiten möglich.

1. Aufgabe

(eine ähnliche Aufgabe könnte zur Prüfung kommen)

2. Aufgabe

parts_of(restaurant).
has(menu, zucker)

3. Aufgabe

4. Aufgabe

Anmeldung für die Übung per e-mail bei witutor: Matrikelnr, Studienkennzahl, Name usw.

Inhalt der VO

Einführung in Wissensbasierte Systeme

Prolog

Wissensrepräsentation (Frame-Notation)

Constraint Verarbeitung

Wissensbasierte Suche

Wissensbasierte Planung

Wissensbasierte Konfiguration

Maschinelles Lernen

Neuronale Netze

Data Mining

Einführung in Wissensbasierte Systeme

Künstliche Intelligenz (Artifical Intelligence)

Zu hoher Anspruch.

Kriterium für Intelligenz: Turing-Test
(Ein Computer imitiert einen Menschen so, daß der Unterschied von außen nicht festgestellt wird)

"das Salz in der Suppe": Maschinelles Lernen

Auch neuronale Netze führen nur Klassifizierungen innerhalb vorgegebener Attribute durch.

Anwendungsgebiete

2000-03-13

"Experten" verwenden sowohl heuristisches, auf Erfahrungen basierendes Wissen, aber auch Allgemeinwissen. Dieses "common sense knowledge" ist in Expertensystemen nicht gut darstellbar.

(Akku leer)

2000-03-20

Einfügen von Klauseln in die Wissensbasis

assertz(est_mere(mme_Pelloux, regine)).

Fakt soll immer gelten. Jede Eingabe mit Punkt abschließen!

Oder: eine ASCII-Textdatei [wissensbasis].pl schreiben und mit consult() oder [] laden.

Wenn ein Dateiname unter "" angegeben wird, können auch eine Verzeichnisstruktur und eine Endung angegeben werden.

Die Wissensbasis ist im Hauptspeicher, Prolog ist kein Datenbanksystem!

Nach halt. ist das Wissen weg. Zustände können aber abgespeichert werden.

<unix>Initialisierung mit [home]/.plrc oder mit der -f -Option.</unix>

<windows>Initialisierung mit ini.pl-Datei z.B.: :-file_search_path(speisen, 'c:\Wissensbasis\Speisekarten').</windows>

Klassifikation von Objekten

skript_restaurant1.pl

Anfragen

?- vorspeise(V).
V=cresson
?- vorspeise(cresson).
yes
?- vorspeise(tomate).
no %nicht in der Wissensbasis

Weitere Antworten mit ; ansehen, am Ende sagt Prolog "no".

Disjunktion

speise(S) :- fleischSpeise(S).
speise(S) :- fischSpeise(S).

oder

speise(S) :- fleischSpeise(S); fischSpeise(S).

Konjunktion

mahlzeit(V, H, D) :-
    vorspeise(V),
    speise(H),
    dessert(D).

V, H, D genügen der Relation mahlzeit, wenn V der Relation vorspeise genügt usw.

Prozedurale Interpretation: Ausführung von mahlzeit bedeutet: Ausführung von vorspeise usw.

Um sofort alle Ergebnisse auszugeben:

findall([V, H, D], mahlzeit(V, H, D), L).

In die Liste L werden alle Elemente der Lösung reingeschrieben.

Einschränkung auf Fisch:

mahlzeit(V, H, D), fischSpeise(H).

skript_restaurant1.pl

(Akku leer)

2000-03-27

Datenstrukturen

Wissensbasis als Baumstruktur: Funktoren als Wurzel

Unifikation von Teilbäumen: Vergleich der Teilbäume / Instantiierung von Variablen zur Substitution

Lineare Liste

Kopf + '.' + Rest der Liste:

.('P', .('r', .('o',.('l',.('o',.('g',[])))))) 
['P', 'r', 'o', 'l', 'o', 'g']
"Prolog" /* für Zeichenketten */

aber 'Prolog' ist ein Atom (auch wenn großgeschrieben)!

Zugriff auf Listenelemente

Überprüfung, ob ein Element in der Liste ist (typische Prüfungsfrage):

Normalerweise können wir immer nur aufs erste Element zugreifen, den Rest müssen wir rekursiv aufrufen.

member(X, [X|_]).
member(X, [_|Y] :- meber(X, Y).
/* Aufruf: member(l, "Prolog").
| teilt die Liste auf => X = P. Wäre P gesucht, würde das Prädikat Erfolg haben.
Zweite Klausel wird rekursiv aufgerufen: Fragt, ob das erste Element der Restliste dem gesuchten Zeichen entspricht.
member(A, "Prolog").
Gibt A=P aus, weil A durch P (erstes Zeichen) unifiziert werden kann
 */

Hinweis: Listen sollten in der Verarbeitung, aber nicht in der Wissensrepräsentation benutzt werden, da das die Änderung erschwert. Besser ist es, wenn für jedes Objekt eine eigene Klausel existiert. Listen sind aber für die Verarbeitung effizienter; z.B. dynamisch eine Liste aller Speisen erstellen und mit denen arbeiten.

Geschachtelte Listen:

hors_d_oeuvres([[truffes_sous_le_sel, 212], [artichauts_melanie, 150]]).

Vorspeise mit weniger als 200 Kalorien:

find(X, [[X,C]| _]) :- c < 200.

find(X, [_|Y]) :- find(X, Y).

Zugriff auf X-tes Element: [X1, X2, X3, | Rest]

Kontrolle der Suche

Beschränkung des Suchbaums mit Cut-Operator (!)

Wenn Cut in einer Regel ausgeführt wird, wird jegliches Backtracking linksvom Cut-Operator verhindert.

Anwendungsfälle:

Beispiel:

plat(P), P/=grillade-de-boeuf, !.

/* gibt die erste Lösung und hört auf*/

Fazit: Cut sollte nur sparsam für die eigentliche Wissensverarbeitung verwendet werden, wo notwendig.

Notwendig z.B. bei mehrfacher Vererbung und widersprüchlichen Klauseln in den Eltern-Klassen.

Operatoren

Prädikate können als Operatoren interpretiert werden.

Normale Prädikate: präfix (vor den Argumenten): est_mere(mme_Pelloux, regine).

In der Mathematik typische Infix-Notation:

Y = X ** 2 + 3 * X + 5 wäre in Präfix: =(Y, +(+(**(x, 2), *(x, X)), 5))

Postfix-Notation: n!

Operatoren gestalten das Programm lesbarer, sind aber (für den Computer) nicht notwendig. Syntax ändert sich, aber die Verarbeitung nicht.

Für Frames sollte nicht eine einfache Liste genommen werden, sondern Operatoren definiert, die die Eigenschaften beschreiben und lesbarer trennen.

Operatordefinition

1. Position des Operators (f) und der Argumente (x und y)

fx und fy = Prefix

xfx, xfy und yfx = Infix

xf und yf = Postfix

2. Präzedenz (Reihenfolge der Bindung bei unterschiedlichen Operatoren)

(Spielt nicht nur bei der Berechnung, sondern auch bei der Unifikation eine Rolle.)

z.B. Präzedenz von * ist höher als von +

3. Assoziativität (Reihenfolge der Bindung bei mehreren gleichen Operatoren)

Rechtsassoziativität: xfy, z.B. a - (b - c)

Linksassoziativität: yfx, z.B. (a - b) - c

Merkregel: x ist ein Term, der nur durch stärkere Operatoren gebunden wird (oder Atom). y ist der Rest.

Beispiel für Operatordefinition: Boole'sche Algebra

and(C1, C2) :- C1, C2.

or(C1, C2) :- C1; C2.

op(60, yfx, 'and').

op(61, yfx, 'or').

/* nicht üblich! Normalerweise bindet and stärker */

op(950, xfy, ---).

op(949, xfy, ::).

op(948, xfy, :).

carte_menu(

chevalier --- hors_d_oeuvre::

artichauts_melanie: 150: 75::

truffes_sous_le_sel: 202: 160::

(...)

--- viande ::

grillade_de_boeuf: 532: 180 ::

(...)

Standardprädikate

(ISO-Norm und allgemein definierte Prädikate)

Bedeutung der abkürzenden Schreibweise für den Modus von Argumenten:

+ das Argument muß instantiiert sein (Eingabeparameter)

? das Argument kann instantiiert oder frei sein

@ kann zusammengesetzter Term sein

- muß eine Variable sein, die durchs Prädikat instantiiert wird (Ausgabevariable)

Kontrolle der Ausführung

true, fail

X = regine.

/= nicht unifizierbar

not(not(dessert(X)) => X wird nicht unifiziert sein

Variable "ausführen" (wenn ich weiß, daß sie ein Prädikat enthält): call(X).

Klassifikation von Ausdrücken

var(X), nonvar(X) ist die Variable belegt (instantiiert)?

Typüberprüfung:

atom(X).

number(X) :- integer(X); float(X).

atomic(X) :- number(X); atom(X).

compound(x) :- not(atomic(X), var(X)).

/* Term aus verschiedenen Variablen/Atomen */

functor(@Term, +Functor, +Number)

/* Funktor-Definition, Anzahl der Argumente*/

arg(+Number, +Term, ?Argument)

/* Was ist das X-te Argument? */

-nonvar =.. +list

/* Zusammensetzen von Prädikaten, sog. univ-Operator. Erlaubt, Operatoren selbst zusammenzusetzen.*/

atom_chars(?Atom, ?List)

/* Zusammensetzen von Zeichenketten zu Atomen */

recorda(20, est_mere(madame_Pelloux, regine)).

recorded()

/* für effizientere Speicherung mit einem Index */

listing.

clause(+Head, ?Tail)

/* wie eine Regel oder Fakt bewiesen wird */

abolish(+Name, +Arity). /* Alles mit diesem Namen löschen */

abolish(Functor/N).

retract(est_mere(mme_Pelloux, regine)).

/* Einzelne Aussage aus der Wissensbasis löschen */

retractall(dessert(X)). /* Alle dessert-Aussagen löschen */

asserta(counter(1)).

Retract(counter(X)), X1 is X + 1, asserta(counter(X1)).

/* Globale Variable simulieren. Ineffizient, nur in Notfällen verwenden. */

2000-04-03

Auffinden aller Lösungen

findall(+Var, +CompoundTerm, -List)

bagof(): auch doppelte Lösungen werden ausgegeben

setof(): Liste sortiert (im Wesentlichen alphabetisch)

"Update view" der Wissensbasis

Traditionelles Verhalten: bei einem assert() während eines Prädikats kann die Wissensbasis geändert werden.

Standard und SWI-Prolog: neues Fakt darf im Backtracking innerhalb des Prädikats nicht gefunden werden.

Ein- und Ausgabe von Daten

Ausgabe

Generisch: write_term(+T, +O) oder write_term(+S, +T, +O)

üblicherweise: write(+T) oder write(+S, +T)

write(poisson or viande) >> poisson or viande

write_canonical(poisson or viande) >> or(poisson, viande)

/* "kanonische" Form */

put(X) /* Steuerzeichen */

nl /* Zeilenvorschub */

Einlesen

read_term(-X), read(-X) /* oder mit (+S, -X) */

Ein Punkt ist Endekriterium im Eingabestrom.

get(X) bzw. get_char(X) /* liest ein druckbares Zeichen ein */

peek_char(X) /* lesen, ohne Dateizeiger zu bewegen */

skip(X)

Überwachung der Programmausführung

trace schaltet den "trace mode" ein, jeder Klauselaufruf wird am Terminal ausgeben.

notrace schaltet das ab.

debug / nodebug /* Debugger */

spy(+Pred), nospy(+Pred) /* Haltepunkt, schrittweise Debuggen ab da */

Wissensrepräsentation

Deklaratives Wissen:

Theoretische Vorteile: modular, veränderbar, verstehbar, erklärbar, verwendungsunabhängig (in der Praxis schwierig)

In der Praxis mehr oder weniger ausgeprägt

Symbolbasierte Darstellung (Symbol: Name eines Objekts in der Wissensbasis):

Prolog ist keine Wissensrepräsentationssprache, da nicht voll deklarativ.

Darstellung ungenauen Wissens

Es soll die Möglichkeit geben, nicht eindeutige Aussagen darzustellen:

Methoden der Wissensrepräsentation

  1. Logikorientierte Methoden

    1. Prädikatenlogik

    2. nichtmonotone Logiken (Defaultlogik)

  2. Produktionsregeln: für klassische Expertensysteme verwendet, heute weniger.

  3. Objektorientierte Methoden (Frames): Wissen wird über ein Objekt der realen Welt dargestellt.

  4. Semantische Netze

  5. Constraints: Spezielle Art von relationalen Tabellen, wobei die Tabelle nicht konkrete Daten, sondern mögliche Werte enthält. Bei der Verknüpfung mehrerer Tabellen können dann Lösungen ermittelt werden. Viele Probleme eignen sich gut für Constraint-Verarbeitung.

  6. Bayes'sche Netze/Causality Graphs

  7. Prozedurale Methoden: Bei Punkten, bei denen die deklarative Darstellung versagt, wird auf "herkömmliches" Programmieren ausgewichen.

... und andere. Häufig Mischformen.

Frames

Minsky 1975. Entstehung im Zusammenhang mit Computer Vision (Bilderkennung).

In Deutschland: Rahmen. In Österreich: Frame.

Ein Frame stellt dar

Einzelne Objekte der realen Welt

Aufhebung des Widerspruchs zwischen prozeduraler und deklarativer Repräsentation

Struktur von Frames

FRL (Frame Representation Language)

Facet (Facette): $VALUE [20]

instance $VALUE : Alle individuellen Frames

Facet:

$IF*: Möglichkeit, Procedural Attachments einzubinden

Wichtig: Abgesehen von der Vererbung bieten Frames relativ wenige eingebaute Schlußfolgerungsmechanismen.

Vererbung

Generischer Frame A kann Informationen an Frame B vererben.

A muß im ako-Slot (AKO = A Kind Of) von B eingetragen sein.

Wird in B nach einem Slotwert gesucht und keiner gefunden, dann wird A untersucht.

Inverser Slot zu ako: instance. B ist im instance-Slot von A eingetragen.

Mehrfachvererbung

Werte können auf drei Arten in der $VALUE-Facet eingetragen sein:

Funktionen in FRL

fget(Frame, Slot {, Facet})

Liefert den Inhalt von Facet von Slot von Frame. Wird kein Wert gefunden: Verwendung der Vererbung. Wenn immer noch erfolglos: Defaults.

fput(Frame, Slot {, Facet}, Wert)

Fügt Wert zum Inhalt des Slots hinzu. $IF-ADDED-demon wird ausgeführt, falls angegeben

fneed(Frame, Slot)

Führt den Inhalt der $IF-NEEDED-facet des Slots aus.

finstantiate(Frame, {, Präfix})

Liefert eine Instanz eines Frames, die nur den ako-Slot enthält.

fcheck(Frame, Slot, {, Wert})

Testet, ob alle in der $REQUIRE-Facet enthaltenen (oder vererbten) Bedingungen in Bezug auf den Slotwert erfüllt sind.

fassert(Name, Slot1 ... Slotn)

Fügt Slots zu einem Frame hinzu

Frames in Prolog

Verschiedene Möglichkeiten:

Einfachste Implementierung: frame(Framename, Slot, Facet, Value).

frame(peking_ente_1, ako, value, [peking_ente]).

Implementierung von fput:

fput(Frame, Slot, Facet, Value) :-
    asserta(current(Frame, Slot, Facet, Value)),
    get_and_retract(Frame Slot, Facet, OldValues),
    assert(frame(Slot, Facet, [Value | OldValues])),
    check_ifadded,
    retract(current(Frame, Slot, Facet, Value)).

get_and_retract(Frame, Slot, Facet, Value) :-
    % Wertzugriff ohne Vererbung
    frame(Frame, Slot, Facet, Value),
    retract(frame(Slot, Facet, OldValues)), !.
get_and_retract(Frame, Slot, Facet []).
% Wenn es den alten Wert nicht gab, leere Liste zurückgeben

% Annahme: Ausführung der Procedural Attachments immer erfolgreich

check_ifadded:-
    current(Frame, Slot, Facet, Value),
    fget(Frame, Slot, ifadded, Demon), !,
    Call(Demon).
check_ifadded. % kein Demon => nix tun

%Beispiel-Demon ($IF-ADDED für beauftragt() bei bestellung()):

add_Koch :-
    current(F, S, _, [V]),
    fput(V, belegt, value, F).

2000-04-10

Semantische Netze

Sehr viel für Sprachverarbeitung verwendet.

Grundlagen

Darstellung von Wissen in Form gerichteter Graphen

Relationale Graphen: Knoten und dazwischen benannte Relationen.

Semantische Fälle: Relationen zur Beschreibung von Satzstrukturen.

Vorteile:

Nachteil: weniger mächtig als Prädikatenlogik.

Anwendungen: Expertensysteme, Verarbeitung natürlicher Sprache, Machine Learning.

Propositionale Netzwerke

Netzwerke (Propositionen) werden geschachtelt. Eine Proposition ist ein abgeschlossener Sachverhalt ("Kontext").

Description Logics (Terminologische Logiken)

Vererbung in Description Logics

Monotone Vererbung: Überdecken von ererbten Eigenschaften nicht möglich!

Logikorientierte Methoden

Prädikatenlogik erster Stufe mit Identität und Funktionssymbolen (PIF).

PIF ist unentscheidbar: Es können Prädikate aufgeschrieben werden, die so komplex sind, daß sie nicht bewiesen werden können.

In der Praxis daher reduzierte Teilsysteme, aber manchmal um nicht-PIF-Elemente erweitert.

EFRS: Einfaches Fakten-Regel-System

Regeln von S: R(S)

Fakten von S: F(S)

z.B. Datenbanksprache DATALOG

Herbrand-Interpretation

Nur spezielle Interpretationen. Nur solche Fakten kommen vor, die in dieser Interpretation gelten.

Regel ist erfüllt, wenn bei beliebiger Ersetzung von Variablen durch Konstantensymbole der Kopf der Regel immer erfüllt ist.

Inferenzalgorithmus

In Prolog als Metainterpreter:

forward :-

(A -> B),

call(A),

call(not (C)), !,

assert(B),

forward.

forward.

Gibt alle beweisbaren Fakten aus. Extrem ineffizient. Die Reihenfolge der Regeln ist irrelevant (Unterschied zu Prolog).

Vererbung

Vereinfachter Beschreibungsvorgang durch teilweise Benutzung der Beschreibung existierender verwandter Objekte, Modifikation ihrer Eigenschaften. Nicht veränderte Eigenschaften werden vererbt.

Überdecken bestehender Eigenschaften

Alle Elefanten sind scheu. Zirkuselefanten sind Elefanten. Zirkuselefanten sind nicht scheu. Clyde ist ein Zirkuselefant. Ist Clyde scheu?

Mit normalen logischen Methoden führt das zu einem Widerspruch.

- ad-hoc definiert (Algorithmus): Frames

- formal: Nichtmonotoner Ansatz

Nichtmonotone Vererbung

"Nixon Diamond"

Nixon ist Quäker und Republikaner. Quäker sind Pazifisten. Republikaner sind keine Pazifisten ("negative Kante"). Ist Nixon jetzt ein Pazifist oder nicht?

Ansätze:

Ist Clyde scheu?

2000-05-08

Wissensbasierte Suche

Motivation: deklarative Wissensrepräsentation erfordert Suche: z.B. Wegsuche, Suche in Constraint Graphen, Vererbungshierarchien, Hypothesenraum (bei maschinellem Lernen), nach optimalen Lösungen

Implizite Graphen

Meist durch Regeln, Operatoren oder ähnliches beschrieben.

Kanten stehen nicht in der Wissensrepräsentation drinnen.

Die Regeln beschreiben den Übergang von einem Zustand zum nächsten; die Punkte der Suche sind die Zustände, die angewendeten Lösungswege sind die Kanten.

Explizite Graphen

Existieren direkt in der Wissensbasis.

Wegegraph in Prolog

u1(taubstummengasse, karlsplatz).
U1(karlsplatz, stephansplatz).
U3(stephansplatz, stubentor).

Nachteil bei Wegsuche: Alle Prädikate müßten bekannt sein

edge(taubstummengasse, karlsplatz, u1, 2, 1). 
% oder Listenstruktur, oder frame-basierte Struktur

primitive Suche:

connected(P1, P2) :-
    edge(P1, P2, _, _).
connected(P1, P2) :-
    edge(P1, P3, _, _), connected(P3, P2).
% Nachbarpunkt suchen und schauen, ob mit dem Ziel verbunden
% Problem: Suche im Kreis

Suchkonzepte

Suche in Graphen

Uninformierte Suchstrategien

Tiefensuche

Suche in die Breite

Backtracking

Suche in die Tiefe mit iterativer Vertiefung

Heuristische Suche

A*-Algorithmus

Typische Bewertungsfunktionen

Iterativ vertiefender A* (IDA*)

Und/Oder-Graphen

Entscheidungen bei Zielkonflikten

Aufgabe 3: Lösung mit A* (Prolog-Programm im Skriptum)

2000-05-15

Wissensbasierte (Handlung-) Planung

Was ist Planung?

Wissensbasierte Planung

Arten von Planung

Echtzeitplanung

Beispiel

beladen(Akteur, Essen, Transporteur, Restaurant)
entladen(Akteur, Essen, Transporter, Kunde)
fahren(Akteur, Fahrzeug, Ort1, Ort2)
zubereiten(Restaurant)
ausliefern(Essen, Kunde)

Das Planungsproblem

Operatoren

Operatorlisten

Ein Operator enthält vier Listen:

Aufgabe

Einfache lineare Planung

Strategie der Mittel-Ziel-Analyse

Algorithmus

"nicht-deterministische" Entscheidungen

1. Welches Teilziel einer Liste wird zuerst gelöst

2. unterschiedliche anwendbare Schemata

3. Unifikation der Literale (Zielaussagen)

Suchrichtung

Regressive Planung

Situationsabstraktion

Fragenliste für die Klausur noch nicht fertig, sollte bis 21. 5. im Netz erscheinen.

2000-05-22

Constraint Satisfaction Probleme

Problemlösen aus AI-Perspektive

3 Sichtweisen:

Grundsätzliche Sichtweise

Tabellendarstellung

z.B. Königinnen-Problem

j

Typ

Werte Z

Gültige Tupeln

Rj

1

A

{z1, z2}

{(13) (14) (24) (31) (41) (42)}

"6/16"

Rj: "Constraint looseness"

Reale Anwendungen

Algorithmen

Tree Search

erzeugt Baum aller möglichen Wertezuweisungen an die n Variablen z.

Mit Backtracking

Änderung der Suchreihenfolge kann helfen, die Menge der Vergleichoperationen zu verringern.

Heuristik: z.B. nach constraint looseness oder Anzahl der Constraints sortieren

Backjumping: Vermeidung eines ganzen Suchbaums ("dependency directed backtracking"): Schauen, wovon die Fehlschläge abhängen

Konsistenzalgorithmen

Anhand der Constraints wird angeschaut, welche Werte in der Lösung "sowieso" nicht vorkommen können.

Kantenkonsistenz: Variablen, die an den Enden einer "Kante" liegen, miteinander konstistent machen

Pfadkonsistenz: Forderungen suchen, die miteinander in Widerspruch stehen (Pfade durch den Graphen suchen)

Ein Constraint-Netz ist kantenkonsistent, wenn alle Kanten kantenkonsistent sind.

Worst case: 4-Königinnen: 90 Überprüfungen, aber keine eliminiert!

Problem: reicht im allgemeinen nicht aus, um ein CSP zu lösen.

Möglichkeiten:

Forward Checking: wenn ein Variablenwert ausgewählt wurde, werden von den folgenden Variablen gleich alle unpassenden Werte ausgefiltert.

Reparatur-Algorithmen

1. Suche eine zufällige Belegung

2. Suche eine Variable z heraus, die an Konflikten beteiligt ist

3. Wähle einen neuen Wert für z

4. Wenn noch keine Lösung, dann weiter bei 2.

2000-05-29

Die Vorlesung am 5. 6. entfällt.

Wissensbasiertes Konfigurieren

Konfiguration: Zusammensetzen komplexer Systeme aus einer Menge von Komponenten

Motivation: "individuelle Massenfertigung": einzelne Komponenten, automatische Zusammensetzung zu komplexen Systemen für den Einzelkunden.

Komplexe Produkte erfordern Software-Unterstützung => Einsatz wissensbasierter Systeme

Vorgangsweisen

Schwelleneffekt: kleine Unterschiede in der Spezifikation können große Effekte auslösen

Horizonteffekt: spätes Feststellen von getroffenen Fehlentscheidungen

Problem für heuristische Algorithmen (z.B. A*): in der Regel keine korrekte Abschrankung für Heuristiken möglich, es kann immer am Ende ein bisher nicht überprüfter Constraint auftauchen.

Spezielle Vorgehensweisen

Wissensdarstellung für Konfiguration

Constraints sind ausdrucksstärker als Regeln, können also eine Strategie besser unterstützen und auch ALLE Lösungen auffinden, während regelbasierte Systeme immer nur eine deterministische Lösung liefern.

Maschinelles Lernen

Motivation

Zielrichtungen des praktischen Lernens

Arten von Lernen (Psychologie)

Statisches Lernen

Lernsystem bekommt Beispiele und leitet daraus Wissen ab => Inferenzkomponente, Problemlöser

Inkrementelles Lernen

Das Lernsystem beobachtet seine Umwelt und baut auch diese Erfahrungen in seine Wissensbasis ein.

Deduktiver Schluß

Menschen sind sterblich => Anna ist Mensch => Anna ist sterblich

Induktiver Schluß

Alle dem System bekannten Menschen sind sterblich => Annahme: alle Menschen sterblich (statistische Bewertung)

Hinznahme einer Theorie möglich.

Erlernen von Konzepten

X: Menge von Objekten

C: ein Konzept aus X

C kann als Funktion interpretiert werden, die 1 ("stimmt") oder 0 liefert

[x, c(x)] ist ein Lernbeispiel.

Lernen als Suche

Ziel: Hypothese (bzw. Schätzfunktion h(X)), die

Suche durch einen Raum von Hypothesen

Strukturierung des Raums durch Generalisierungs- und Spezialisierungsrelation

Suchverfahren

Lernen von Entscheidungsbäumen

Hyperlinkstruktur als Entscheidungsbaum

Startseite

usw.

Welches Attribut soll zuerst abgefragt werden? Das, das am schnellsten zum Wunschgericht führt.

Wenn der Kunde nur österreichisch ißt, zuerst diese Auswahl anzeigen.

Lernalgorithmus ID3

Berechnung

Analoges Lernen: Fallbasiertes Schließen

Probleme samt Lösung werden als "Fallbasis" gespeichert. Bei einem neuen Problem wird nach ähnlichen Problemen (=Problemen mit ähnlichen Attributen) gesucht. Evt. Simulation des neuen Falls. Reparatur (automatisch oder mit menschlicher Einwirkung). Lernen der Fälle => wieder in der Fallbasis gespeichert.

2000-06-19

Data Mining und Knowledge Discovery

Data Mining

Ablauf

KDD ist der Prozeß der Suche nach gültigen, neuartigen, möglicherweise nützlichen, verständlichen, aber nichttrivialen Mustern.

Muster: Beschreibung einer Eigenschaft einer Datenmenge, die kürzer ist als die Aufzählung der Daten, z.B.: "wenn Einkommen < t $, dann wird die Person den Kredit nicht bezahlen".

Musterarten

Klassifikation

Gruppierung (Clustering)

z.B. Gruppierung von KundInnen

(Verwandt: Abschätzung der Dichtefunktionen für Wahrscheinlichkeitsverteilungen)

Andere Aufgaben

Abhängigkeiten (Assoziationen): "In 34 % der Transaktionen, bei denen Milch, Brot und Butter gekauft wurden, wurde auch Kaffee gekauft."

Zeitliche Abfolgen: Videorecorder => innerhalb von 5 Tagen auch Kassetten gekauft

Inductive Logic Programming

Muggleton, 1991

Ziel: Einschränkungen der Standard-Entscheidungsbaum-Algorithmen zu vermeiden

Data Warehousing

Auch bekannt als OLAP (On Line Analytical Processing) im Gegensatz zu OLTP (On Line Transactional Processing)

Diagnose



© Balázs Bárány. (Homepage)
Zuletzt geändert: 2003-12-23.