Possibilistische Netze Seminar: Fuzzy-Systeme in Industrieanwendungen 27. März 2003 Otto-von-Guericke-Universität Magdeburg Sebastian Stober

Possibilistische Netze

Seminar: Fuzzy-Systeme in Industrieanwendungen

27. März 2003Otto-von-Guericke-Universität Magdeburg

Sebastian Stober

27. März 2003 Seminar: Fuzzy Systeme in Industrieanwendungen - Sebastian Stober: Possibilistische Netze

2

Gliederung

1. Possibilitätstheorie2. Relationale Netze3. Possibilistische Netze4. Quellen


3

1. Possibilitätstheorie

Possibilität beschreibt die Möglichkeit eines Ereignisses/Auftreten eines Wertes

Oder: Gibt es einen existierenden aber nur partiell beschreibbaren Wert x0, so gibt die Possibilität (x) [0,1] an, inwieweit x0=x möglich ist.

Klar: (x)=1 heißt, der Wert x ist (uneingeschränkt) möglich (x)=0 heißt, der Wert x ist unmöglich

Was ist mit den Werten dazwischen?


4

Interpretation

Mehrere Interpretationsansätze möglich, z.B.: Epistemologische Interpretationen von Fuzzy Mengen Präferenzrelationen Ähnlichkeiten Hier: Kontext Modell

Kontext-Modell: Idee - ein Kontext kann sein: Physikalische Rahmenbedingungen Beobachtungsbedingungen Beobachter Meßgerät


5

Definition Zufallsmenge: (C, 2C, P) – endlicher Wahrscheinlichkeitsraum

C – modelliert die Kontexte P(c) – Wahrscheinlichkeit für das Auftreten / die Wahl

eines Kontexts c - nichtleere Menge Eine Zufallsmenge ist die mengenwertige Abbildung:

: C 2 (c), c C heißen Fokalmegen von

Beinhalten die Werte aus , die im Kontext c möglich sind Oft ist (c) gefordert

Achtung: Def. nimmt implizit an, daß die Kontexte disjunkt sind (als Elementarereignisse im Wahrscheinlichkeitsraum)

Mathematische Formalisierung (1)


6


Definition Elementare Possibilitätszuweisung

Der Possibilitätsgrad eines Ereignisses ist die Wahrscheinlichkeit der Möglichkeit des Ereignisses, d.h. die Wahrscheinlichkeit der Kontexte, in denen es möglich ist.

cCcP

1,0:


7

Mathematische Formalisierung (3) Normalisierung

Konsistenz (Widerspruchsfreiheit)

d.h. es gibt mindestens ein Element, das in allen Kontexten vorkommt

Normalisierung kann nur vorliegen, wenn Konsistenz vorliegt

Im Allgemeinen ist Konsistenz gefordert (plausibel), es können aber auch inkonsistente Fälle konstruiert werden.

1:

Cc

c


8


Definition Possibilitätsmaß

Erweiterung der Elementaren Possibilitätszuweisung auf Potenzmengen

Weist (allgemeinen) Ereignissen, d.h. Mengen von Elementarereignissen, Possibilitätsgrade zu

)(

1,02:

cECcPE


9

Beispiel: Würfelexperiment

1 bis 4 1 bis 6 1 bis 8 1 bis 10 1 bis 12

1 bis 5

1. Wurf: Auswahl des Bechers

21 3 4 5

2. Wurf: Ermittlung des Ergebnisses

Die Würfelbecher stellen die Kontexte dar.


10

Possibilität vs. Wahrscheinlichkeit


11

Modifiziertes Würfelexperiment

1 bis 4 1 bis 6 1 bis 8 1 bis 10 1 bis 12

1 bis 5

1. Wurf: Auswahl des Bechers

21 3 4 5

2. Wurf: Ermittlung des Ergebnisses

Modifikation: Jetzt 2 identische Würfel je Becher (wähle Maximum)

Ergebnis: Es verändern sich nur die Wahrscheinlichkeiten!


12

Erkenntnisse Beim possibilistischen Ansatz wird im Experiment kein

Wissen über die Wahl des Würfelbechers hinaus modelliert Modellierung des Unwissens über die Vorgänge beim zweiten Wurf

Hier werden die Becher als Kontext gewählt (grob) Genaueres Wissen über den Vorgang würde es möglich

machen, die Kontexte feiner zu modellieren Dabei wird versucht, in jedem Kontext, so viele Ergebnisse wie

möglich auszuschließen („negative Information“) Definiert man für jeden Verlauf (!) des Experimentes einen

Kontext (feinste Modellierung), so entsprechen die Possibilitätsgrade den Wahrscheinlichkeiten

Possibilität ist (lose) obere Grenze für die Wahrscheinlichkeit


13

2. Einführung Relationale Netze Idee:

Unter bestimmten Umständen läßt sich eine mehrdimensionale Verteilung (Relation) , welche ein bestimmtes domainspezifisches Vorwissen darstellt, zerlegen in eine Menge von (überlappenden) Verteilungen {1,..., k} auf Unterräumen geringerer Dimension

Vorteile: Effizienteres Speichern, Vermeidung von Redundanzen (Analogie

zur Theorie der relationalen Datenbanken) Effizientes Schlußfolgern auf {1,..., k} ist möglich, ohne dazu die

Gesamtverteilung rekonstruieren zu müssen Leite die Information von Unterraumverteilung zu

Unterraumverteilung weiter bis alle aktualisiert sind Unterscheidung verschiedener Ansätze, u.a.:

Markovnetze – Ungerichtete Graphen Bayes‘sche Netze – Gerichtete Graphen


14

Beispiel 3 Attribute A,B,C:

dom(A)={a1,a2,a3,a4} dom(B)={b1,b2,b3} dom(C)={c1,c2,c3}

Gesamtraum: dom(A) dom(B) dom(C) = {A,B,C} RABC:

Es gilt die „closed-world assumption“, d.h. alle nicht in RABC enthaltenen Wertekombinationen sind unmöglich.


15

Beispiel: 2-dimensionale Projektionen

RABC RAB

RAC RBC


16

Beispiel: Schlußfolgern

Angenommen, der Wert eines Attributes ist bekannt. Was kann über die anderen Attribute gefolgert werden?

Naiv: betrachte alle Objekte in RABC mit der entsprechenden Attributausprägung – für höherdimensionale Verteilungen ist das nicht machbar

Graphische Modelle: versuche, die Verteilung zu zerlegen, indem bedingte Unabhängigkeiten genutzt werden


17

Bedingte Relationale Unabhägigkeit Die Attribute A und C sind genau dann bedingt

relational unabhängig gegeben Attribut B, wenn gilt:

D.h. ist der Wert für B gegeben können alle Werte, die für A und C möglich sind frei kombiniert werden.

(*) liefert eine Formel für die Zerlegung

cCbBRbBaARcCbBaAR

CdomcBdombAdoma

bzw

bBcCRbBaARbBcCaAR

CdomcBdombAdoma

,,,min,,

:::*

.

,min,

:::


18

Beispiel: Zyl. Erweiterung und Schnitt

Zylindrische Erweiterung:RAB C

RBC A

Schnitt der zylindrischen Erweiterungen:min{(RAB C), (RBC A)} = RABC Zylindrische

Erweiterung:


19

Beispiel: Evidenzen-Propagation

Beobachtung des Wertes für Attribut A:

Schließen auf Werte der Attribute B und C:


20

Beispiel: Bedingte Unabhängigkeit

Graphisches Modell:

Die Attribute A und C sind bedingt unabhängig gegeben Attribut B, da alle Wege von A nach C durch Entfernen von B zerstört werden („u-Separation“).


21

Bemerkungen

Eine Zerlegung ist nicht immer möglich. Nicht jede Menge von Projektionen einer

Relation liefert eine Zerlegung. Zerlegbare Relationen sind selten. In der Anwendung ist oft ein gewisser Verlust

an Information akzeptabel (verglichen mit dem Vorteil der geringeren Komplexität)


22

3. Possibilistische Netze

Übertragen der Idee der Zerlegung einer (mehrdimensionalen) Relation auf (mehrdimensionale) Possibilitätsverteilungen

Modifikation der Operationen Projektion: berechne den maximalen Possibilitätsgrad über

den entfernten Dimensionen Zylindrische Erweiterung und Schnitt (kombiniert):

berechne das Minimum aus der a priori Verbund-Verteilung und der a posteriori Rand-Possibilitätsgrade


23

Beispiel: Verteilung und Projektionen


24

Beispiel: Schlußfolgern


25

Bedingte Possibilistische Unabhängigkeit Possibilistische Netze können als „Fuzzyfikation“ von

Relationalen Netzen gesehen werden, indem anstelle der Beschränkung auf die Werte 0 und 1 alle Werte aus dem Intervall [0,1] betrachtet werden.

Daraus ergibt sich analog zur bedingten relationalen Unabhängigkeit: A und C sind genau dann bedingt possibilistisch unabhängig, wenn gilt:

wobei Possibilitätsmaß auf einem (endlichen) Beispiel-Raum ist.

bBcCbBaAbBcCaA

CdomcBdombAdoma

,min,

:::


26

Wahrscheinlichkeit vs. Possibilität

Suche nach dem wahrscheinlichsten Tupel:

Nicht alle Attributwerte tragen zum Resultat der Projektion bei, nur die mit maximalem Possibilitätsgrad

Es geht nicht die gesamte Information über die entfernten Attribute verloren

Gibt es nur einen Maximalwert in jeder Zeile / Spalte wird das Tupel mit höchstem Possibilitätsgrad zurückgeliefert

Alle Attributwerte tragen zum Resultat der Projektion bei

Durch die Summe geht die Information über die entfernten Dimensionen verloren

Um das richtige Tupel zu wählen muß zuerst die Verbund-Verteilung rekonstruiert werden


27

Zusammenfassung

Graphische Modelle stellen eine wichtige Methode zur effizienten Repräsentation und Analyse unsicherer Information in wissensbasierten Systemen dar

Durch Verwendung der Possibilitätstheorie ist es möglich, impräzise Informationen zu berücksichtigen

Possibilistische Netze bieten als Kombination beider Ansätze die Möglichkeit mit sowohl unsicherer als auch impräziser Information zu arbeiten


28

4. Quellen Graphical Models - Methods for Data Analysis and Mining.

Christian Borgelt and Rudolf Kruse. J. Wiley and Sons, Chichester, United Kingdom 2002, ISBN 0-470-84337-3

Possibilistic Graphical Models. Christian Borgelt, Jörg Gebhardt, and Rudolf Kruse. Computational Intelligence in Data Mining (Proc. 3rd Int. Workshop, Udine, Italy 1998), pp. 51-68. G. Della Riccia, R. Kruse, and H.-J. Lenz, eds. CISM Courses and Lectures 408, Springer, Wien, Austria 2000.

Fuzzy-Systeme. Series Leitfäden und Monographien der Informatik.

R. Kruse, J. Gebhardt und F. Klawonn. Teubner Verlag, Stuttgart, 1. Auflage 1993, 2. Auflage 1995

Vorlesung „Unsicherheit und Vagheit in wissensbasierten Systemen“.R. Kruse, C. Borgelt. Sommersemester 2002


29

Vielen Dank für Ihre Aufmerksamkeit.

Documents

Possibilistische Netze Seminar: Fuzzy-Systeme in Industrieanwendungen 27. März 2003 Otto-von-Guericke-Universität Magdeburg Sebastian Stober