Generative Modelle - Professur für Theoretische ... Modelle Handout.pdf · I Das Prinzip der Maximum Entropie: Wähle eine alle Eigenschaften erfüllende Verteilung mit maximaler

Generative Modelle

Generative Modelle 1 / 49

Die Zielstellung

Bisher:Lerne eine unbekannte Zielfunktion approximativ nachBeobachtung zufällig erzeugter Beispiele

Jetzt:Finde möglichst viel über die zugrunde liegendeBeispiel-Verteilung D heraus.

Die Fragestellung ist weitaus schwieriger geworden: Nimm an, dassD zu einer eingeschränkten Klasse von Verteilungen gehört bzw.bestimmte Unabhängigkeits-Eigenschaften erfüllt.

Generative Modelle 2 / 49

Maximum Likelihood

Generative Modelle Maximum-Likelihood 3 / 49

Maximum-Likelihood: Der Ansatz

B ist eine Beobachtung (oder Folge von Beispielen):

Von welcher Verteilung wurde B erzeugt?

Verteilungen werden über ihre Parameter Θ beschrieben:

pΘ(B ) := Wahrscheinlichkeit von B „im Modell“ Θ.

Ein Parameterwert Θopt beschreibt eine

Maximum Likelihood Hypothese (ML-Hypothese),

wennprobΘopt

[ B ] = maxΘ

probΘ[ B ]


Maximum-Likelihood: Ein Beispiel (1/2)

1 X ist eine binäre Zufallsvariable mit unbekannter Verteilung D.I Es ist Θ = probΘ [X = 1 ].I Bestimme Θ.

2 Wir erhalten die Beobachtung

B = (x1, . . . ,xm) ∈ {0,1}m.

Chernoff-Ungleichung: Θ wird durch∑m

i=1 xim scharf approximiert.

Was liefert Maximum-Likelihood?


Maximum-Likelihood: Ein Beispiel (2/2)

1. Bestimme die Wahrscheinlichkeit von B im Modell Θ, also:

probΘ[B ] =Πmi=1Θ

xi · (1−Θ)1−xi =Θ∑m

i=1 xi · (1−Θ)∑m

i=1(1−xi ).

2. Bestimme die Log-Likelihood durch Logarithmieren

L(B;Θ) :=m∑

i=1

xi · logΘ+m∑

i=1

(1− xi) · log(1−Θ).

3. Für welchen Wert von Θ wird B am wahrscheinlichsten?I Differenziere L(B;Θ) nach Θ. Nach Null-Setzung:∑m

i=1 xi

Θopt=

∑mi=1(1− xi)

1−Θopt.

I Die Lösung dieser Gleichung ist Θopt =1m ·

∑mi=1 xi

Maximum-Likelihood: Der Mittelwert ist das wahrscheinlichste Modell.

.Generative Modelle Maximum-Likelihood 6 / 49

Normalverteilung: Parameterschätzung (1/2)

Die unbekannte Normalverteilung

PΘ[x ] :=1

σ√

2π·exp−

(x−µ)2

2σ2

erzeugt B = (x1, . . . ,xm) ∈Rm. Bestimme Erwartungswert und Varianz.

1. Die Log-Likelihood für Θ = (µ,σ) ist

L(x1, . . . ,xm;Θ) :=m∑

i=1

logPΘ[xi ] =−12σ2 ·

m∑i=1

(xi −µ)2 −m log(σ ·√

2π).

2. Differenziere nach µ:

∂L∂µ

(x1, . . . ,xm;Θ) =1σ2

m∑i=1

(xi −µ)!= 0


Normalverteilung: Parameterschätzung (2/2)

3. Es ist

L(x1, . . . ,xm;Θ) =−12σ2 ·

m∑i=1

(xi −µ)2 −m log(σ ·√

2π).

Differenziere nach σ :

∂L∂σ

(x1, . . . ,xm;Θ) =1σ3

m∑i=1

(xi −µ)2 − mσ

!= 0.

Maximum-Likelihood liefert als wahrscheinlichste Parameter

µopt =1m

m∑i=1

xi und σopt =

√√1m

m∑i=1

(xi −µopt)2.


Maximum-Likelihood und neuronale NetzwerkeBackpropagation versucht, den empirischen Log-Loss

LossSD = −1

s·

∑(x ,y)∈S

logpw (y |x),

zu minimieren. Für die tatsächliche Wahrscheinlichkeit p(x ,y) von (x ,y) ist

LossD(w) = E(x ,y)∼D[`(w ,x ,y) ] = −∑

(x ,y)∈X×Y

p(x ,y) · logpw (y |x)

=∑x∈X

p(x) ·∑y∈Y

p(y |x) · log( 1pw (y |x)

)=

∑x∈X

p(x) ·∑y∈Y

p(y |x) · log(

p(y |x)pw (y |x)

)︸︷︷︸

Kullback-Leibler Divergenz > 0

+∑x∈X

p(x) ·∑y∈Y

p(y |x) · log( 1p(y |x)

)︸︷︷︸

Entropie H(p(∗ |x))

LossD(w) >∑

x∈X p(x) ·∑

y∈Y p(y |x) · log(

1p(y |x)

). (mittlere Entropie)


Maximum a Posteriori Hypothese

Bayes-Lernen MAP-Hypothesen 10 / 49

MAP-Hypothesen

Sei H eine Hypothesenklasse.

Hypothesen entsprechen diesmal Zufallsvariablen.

Der Prior bzw. die A-priori Verteilung

prob[h ]

sei bekannt ebenso wie die Wahrscheinlichkeit

prob[B |h ]

mit der B bei angenommener Hypothese h erzeugt wird.

Bestimme die Maximum a Posteriori (oder MAP-) Hypothese

prob[ h∗ | B ] = maxh∈H

prob[ h | B ]


Der Satz von Bayes

Bekannt: prob[h ] und prob[B |h ].

Gesucht: maxh∈H prob[h |B ].

prob[ h | B ] =prob[ B | h ] · prob[ h ]

prob[ B ].

Warum? Es ist

prob[ h | B ] · prob[ B ] = prob[ h,B ] = prob[ B | h ] · prob[ h ]

Wenn alle Hypothesen gleichwahrscheinlich sind:

ML-Hypothesen = MAP-Hypothen


MAP-Hypothesen: Ein Beispiel (1/2)

Fakten:

0.8% der Bevölkerung haben eine bestimmte Erkrankung,Wenn eine Erkrankung vorliegt: Positiver Befund in 98% aller FälleWenn nicht erkrankt: Negativer Befund in 97% aller Fälle.

Hypothesenklasse: H= { erkrankt, nicht erkrankt }.

Bestimme eine MAP-Hypothese, wobeiPrior : prob[ erkrankt ] = 0,008, prob[ nicht erkrankt ] = 0,992.

Die Wahrscheinlichkeit von Befunden:I prob[ Befund: erkrankt | erkrankt ] = 0.98,I prob[ Befund: nicht erkrankt | erkrankt ] = 0.02,I prob[ Befund: erkrankt | nicht-erkrankt ] = 0.03I prob[ Befund: nicht-erkrankt | nicht-erkrankt ] = 0.97.


MAP-Hypothesen: Ein Beispiel (2/2)

prob[ Befund: erkrankt | erkrankt ] = 0.98,prob[ Befund: nicht erkrankt | erkrankt ] = 0.02,prob[ Befund: erkrankt | nicht-erkrankt ] = 0.03prob[ Befund: nicht-erkrankt | nicht-erkrankt ] = 0.97.

Mit dem Satz von Bayes:

prob[erkrankt |Befund: erkrankt ] ·prob[Befund: erkrankt ]= 0.98 ·0.008 = 0.00784

prob[nicht-erkrankt |Befund: erkrankt ] ·prob[Befund: erkrankt ]= 0.03 ·0.992 = 0.02976.

Bei positivem Befund: Die MAP-Hypothese ist „nicht erkrankt“.Desweiteren: Ein positiver Befund ist falsch mit Wahrscheinlichkeit

0.029760.00784+0.02976

≈ 0,7914


Bayes-Klassifikation


Bayes-Hypothese

Sei D eine bekannte Verteilung über der Menge X × {0,1}.

Für die Beispielmenge S = {x1, . . . ,xs} ⊆ X ist die Bayes-Hypothese

hD(xi) =

{1 probD[y = 1 |xi ] >

12 ,

0 sonst

Bei unbekannter Zielfunktion ist hD optimal, d.h. f. a. Hypothesen h gilt

LossD(h) > LossD(hD).

Aber natürlich ist D i.A. nicht bekannt: Benutze die Bayes-Hypotheseals Referenz-Hypothese (wie etwa für 1-Nearest-Neighbor).


Klassifikation einzelner Beispiele

Die Hypothesenklasse H bestehe aus Zufallsvariablen. Klassifiziereein einziges Beispiel B mit einem Wert c ∈ C. Bekannt seien:

1 prob[ h | B ] für jede Hypothese h ∈ H und2 prob[ c | h ] für jedes c ∈ C.

Gesucht ist eine optimale Bayes-Klassifikation c∗ ∈ C, d.h. es gelte

prob[ c∗ | B ] = maxc∈C

prob[ c | B ].

Es istprob[ c | B ] =

∑h∈H

prob[ c | h ] · prob[ h | B ].

und das vorhandene Wissen ist ausreichend.


Bayes-Klassifikation und Weighted Majority

Weighted-Majority bestimmt eine MAP-Klassifikation.

(a) Definiere die A-priori Wahrscheinlichkeit prob[ h | B ]der Hypothese h durch das relative Gewicht des „Experten“ h.

(b) prob[ c | h ] ist 0-1-wertig, denn Experten sind deterministisch.

Weighted Majority entscheidet sich für das Mehrheitsvotum

prob[ c∗ |B ] = maxc∈C

prob[ c |B ]

und damit für die optimale Bayes-Klassifikation.


Naive Bayes-Klassifikation

Bayes-Lernen Naive Bayes-Klassifikation 19 / 49

Naive Bayes-Klassifikation (1/2)

Wie bestimmt man eine optimale Bayes-Klassifizierung effizient?

1 Es gelte X := Σ1 × · · · ×Σn für Alphabete Σ1, . . . ,Σn.2 Eine unbekannte Zielfunktion f : X → C ist vorgegeben.3 Für ein Beispiel B = (a1, . . . ,an) ∈ X bestimme

maxc∈C

prob[ c | a1 · · ·an ].

Mit dem Satz von Bayes ist

prob[ c | a1 · · ·an ] =prob[ a1 · · ·an | c ] · prob[ c ]

prob[ a1 · · ·an ].

=⇒ Maximiere

prob[ a1 · · ·an | c ] · prob[ c ]


Naive Bayes-Klassifikation (2/2)

Maximiere prob[ a1 · · ·an | c ] · prob[ c ].

Wir machen die naive Annahme der stochastischen Unabhängigkeit:

prob[ a1 · · ·an | c ] =n∏

i=1

prob[ ai | c ].

=⇒ Bestimme eine Klassifizierung c∗ ∈ C, so dass

n∏i=1

prob[ ai | c∗ ] · prob[ c∗ ] = maxc∈C

n∏i=1

prob[ ai | c ]

· prob[ c ].︸︷︷︸Bestimme die

∑ni=1 | Σi | · | C | Terme prob[ ai | c ] sowie die |C| Terme

prob[ c ] durch eine Statistik auf den Trainingsdaten.

Die naive Bayes-Klassifikation ist in „vielen“ Anwendungen erfolgreich.


Naive Bayes-Klassifikation: Ein Beispiel

Wir erhalten als interessant bzw uninteressant markierte Textdateien.

Lerne den Geschmack des Nutzers!

1 Sei V das benutzte Vokabular. Es ist Σi = V für jedes i =⇒Repräsentiere Textdateien durch den Vektor ihrer Worte.

2 Mit der lächerlichen Annahme der stochastischen Unabhängigkeitfolgt

prob[ w1 · · ·wn | c ] =n∏

i=1

prob[ wi | c ]

3 Setze prob[ w | c ] =Häufigkeitc(w)

Pc+|V |, wobei

Pc die Gesamtlänge aller Textdateien mit Klassifizierung c ist.

Der Ansatz funktioniert! Und der Bag-of-Words Ansatz für SVMs?


Bayes (Belief) Netzwerke

Bayes-Lernen Bayes (Belief) Netzwerke 23 / 49

Gemeinsame Verteilungen

Die Zufallsvariable X1, . . . ,Xn sind gegeben.

Bestimme die gemeinsame Wahrscheinlichkeitsverteilung

p[X1 = x1, . . . ,Xn = xn]

und werte sie aus: Z. B. bestimmme die Randverteilung

p(XU = xU |XV = xV ) =∑

yp(XU = xU , X{1,...,n}\(U∪V ) = y |XV = xV )

für disjunkte Teilmengen U ,V ⊆ {1, . . . ,n}.

Wenn die Zufallsvariablen unabhängig sind, gilt

p[X1 = x1, . . . ,Xn = xn] = p[X1 = x1] · · ·p[Xn = xn].

und die Bestimmung ist trivial. Ansonsten mache Abhängigkeiten unterden Variablen explizit: Stelle ein Bayes Netzwerk auf.


Bayes Netzwerke (1/2)

Ein Bayes Netzwerk (B = V ,E ,p) besitzt die Komponenten:1 V = {X1, . . . ,Xn} und (V ,E) ist ein kreisfreier gerichteter Graph.2 Für den Knoten Xi seien Xi1 , . . . ,Xiki

alle direkten Vorgänger (bzwdie Eltern) von Xi . Wir fordern

p[Xi = xi | Xi1 = xi1 , . . . ,Xik = xik ] =

p[Xi = xi | X1 = x1, . . . ,Xi−1 = xi−1,Xi+1 = xi+1, . . . ,Xn = xn]

Der Gesamteinfluss aller Variablen auf Xi entspricht genau demEinfluss der Eltern auf Xi .

3 Jeder Knoten Xi erhält die Tabellen

p[Xi = xi | Xi1 = xi1 , . . . ,Xik = xik ]

der bedingten Wahrscheinlichkeiten.


Bayes Netzwerke (2/2)

Die Graphstruktur eines Bayes Netzwerks zeigt alle maßgeblichenkausalen Beziehungen unter den Zufallsvaribalen:

Sei B ein Bayes Netzwerk mit den Zufallsvariablen X1, . . . ,Xn.Wenn Xi1 , . . . ,Xik(i) die Eltern von Xi sind, gilt

p[X1 = x1, . . . ,Xn = xn] =n∏

i=1

p[Xi = xi | Xi1 = xi1 , . . . ,Xik(i) = xik(i) ].

Wie bestimmt man die bedingten Wahrscheinlichkeiten?


Bestimmung bedingter Wahrscheinlichkeiten

1 Heuristische Rechnungen: Z.B. bei verrauschterODER-Beziehung mit (fast) unabhängigen Eltern, schätze

prob[X = 0 |X1 = 1, . . . ,Xk = 1 ] ≈k∏

i=1

prob[X = 0 |Xi = 1 ].

2 Wenn nur einige Eigenschaften (wie etwa Erwartungswerte )bekannt sind:I Das Prinzip der Maximum Entropie: Wähle eine alle

Eigenschaften erfüllende Verteilung mit maximaler Entropie.

3 Der EM-Algorithmus versucht eine Schätzung mit Hilfebeobachteter Variablen.I Die Schätzung soll die Beobachtungen hochwahrscheinlich

machen.I Die Werte einiger Variablen mit „Einfluss“ dürfen fehlen.


Pathfinder I-IV

Pathfinder: Ein Diagnose-System für Lymphknotenerkrankungen

1 Pathfinder führt ≈ 135 Symptome, Befunde und Laborwerte undgibt 60 verschiedene Diagnosen.

2 Nach Setzung der Evidenz-VariablenI Symptome, Befunde und Laborwerte eines Patienten

wird ein Überblick über die Wahrscheinlichkeiten der jeweiligenDiagnose gegeben.

Bayes Netzwerke werden auch in der

probabilistischen Inferenz

eingesetzt.


Die Komplexität der Berechnung vonRandverteilungen

! Ein einfaches, schwieriges Bayes-Netzwerk, das nur aus binärenZufallsvariablen besteht:I Die Zufallsvariablen X1, . . . ,Xn sind unabhängig mit

prob[Xi = 1 ] = 12 .

I Jede der Zufallsvariablen K1, . . . ,Km hängt von genau dreiX -Variablen ab und es ist prob[Kj = 1 ] = 7/8.

I Für die Zufallsvariable X gilt

X = 1 ⇐⇒ K1 = · · ·= Km = 1.

Schon die Frage, ob prob[X = 1] > 0 führt auf einNP-vollständiges Problem.

X Eine effiziente Berechnung von Randverteilungen gelingt fürFaktorgraphen, die einem Baum entsprechen.


Faktorgraphen, eine eingeschränkte Version

Ein Faktorgraph G = (V ,F ,E ,Funktion) ist ein bipartiter Graph.(a) Die Menge V = {X1, . . . ,Xn} der Variablen ist die erste,

die Menge F der Faktoren ist die zweite Schicht von B.(b) Für jeden Faktor f ist Funktion(f) eine Funktion, die nur von den

Variablen Xv für Nachbarn v von f abhängt.Forderung:

prob[X1 = x1, . . . ,Xn = xn] =∏f∈F

Funktion(f ).

Wenn der Faktorgraph ein Baum mit kleinem Grad ist, dann ist

prob[XU = a |XV = b ]

für alle disjunkten Teilmengen U ,V ⊆ {1, . . . ,n} und alle a,b effizientberechenbar.


Bayes Netzwerke und Faktorgraphen

Sei B ein Bayes Netzwerk mit den Zufallsvariablen X1, . . . ,Xn.Wenn Xi1 , . . . ,Xik(i) die Eltern von Xi sind, gilt

p[X1 = x1, . . . ,Xn = xn] =n∏

i=1

p[Xi = xi | Xi1 = xi1 , . . . ,Xik(i) = xik(i) ].

Baue einen Faktorgraphen F := (V ,F ,E ,Funktion) für B:1. V := {X1, . . . ,Xn },2. F := {F1, . . . ,Fn },3. Kante {Xi ,Fj } gehört zu E ⇐⇒ i = j oder Xi ist Elternknoten von Xj ,4. falls Xj1 , . . . ,Xjk die Elternknoten von Xj sind, ist

Funktion(Fj) := p[Xj = xj | Xj1 = xj1 , . . . ,Xjk(i) = xjk(i) ].


Belief Propagation (BP) für Bäume

Bayes-Lernen Belief Propagation für Bäume 32 / 49

BP für Bäume: Das „eingeschränkte“ Ziel

T sei ein gewurzelter „Faktorbaum“.(a) BP rechnet von den Blättern aufwärts bis zur Wurzel.(b) Die Wurzel ist die Variable v : Bestimme die Randverteilung, d.h.

prob[Xv = a]

für alle Elemente a im Wertebereich von Xv .

Für eine Variable oder einen Faktor t definiere

prob(t)T

als das Produkt aller Faktoren im Teilbaum von t . Des Weiteren ist

[prob(t)T ] =

∑y

prob(t)T (y),

wobei über alle Wertekombinationen y für Variablen „unterhalb t“summiert wird.


Belief Propagation: Die Invarianten

(F) Erreicht BP einen Faktor g, dann sendet BP die Nachricht

mg→v := [prob(g)T ]

an den Elternknoten v von g.Achtung: [prob(g)

T ] ist eine Funktion der Werte von Xv .(V) Erreicht BP eine Variable v , dann sendet BP die Nachricht

mv→f := [prob(v)T ]

an den Elternknoten f von v .Achtung: [prob(v)

T ] ist eine Funktion der Werte von Xv .

BP sendet stets eine „Randverteilung“ für Xv .


BP: Das Programm für Bäume (1/3)

BP erreicht das Blatt x .

(a) Wenn x der Faktorknoten f ist und v sein Elternknoten ist, dannhängt f nur von xv ab =⇒ BP sendet die Nachricht

mf→v := Funktion(f )

an die Variable v . Beachte, dass [prob(f )T ] = Funktion(f ) gilt.

(b) Wenn x die Variable v ist, dann sendet BP die Nachricht

mv→g := 1

an den Elternknoten g. (Die Funktion 1 weist jedem Wert von Xv

den Wert 1 zu. Beachte, dass [prob(v)T ] = 1 gilt.)



BP erreicht den Faktor f mit Kindern v1, . . . ,v` und Elternknoten v =⇒

prob(f )T = Funktion(f ) ·prob(v1)

T · · ·prob(v`)T .

Invariante (V) =⇒ BP hat die Nachrichten

mvi→f := [prob(vi )T ]

an f gesendet. Hat f alle Nachrichten erhalten, sendet BP

mf→v := [Funktion(f ) ·∏̀i=1

mvi→f ] = [Funktion(f ) ·∏̀i=1

[prob(vi )T ] ]

Distributivität= [Funktion(f ) ·

∏̀i=1

prob(vi )T ] = [prob(f )

T ]

an den Elternknoten v von f . Invariante (F) wird bewahrt.Bayes-Lernen Belief Propagation für Bäume 36 / 49


BP erreicht die Variable v mit Kindern f1, . . . , fk und Elternknoten g=⇒

prob(v)T = prob(f1)

T · · ·prob(fk )T .

Invariante (F) =⇒ BP hat die Nachrichten

mfi→v := [prob(fi )T ]

von fi an v gesendet. Hat v alle Nachrichten erhalten, sendet BP

mv→g :=k∏

i=1

mfi→v =k∏

i=1

[prob(fi )T ]

Distributivität!= [prob(v)

T ]

von v an den Elternknoten g =⇒ Invariante V wird bewahrt.Bayes-Lernen Belief Propagation für Bäume 37 / 49

BP auf Bäumen: Eine Zusammenfassung

Sei (V ,F ,E ,Funktion) ein Baum der Tiefe T . Ist die Variable v Wurzeldes Baums, dann bestimmt Belief Propagation

prob[Xv = a]

für alle Werte a von Xv in T Runden.

Beweis: Es ist [prob(v)T ] = prob[Xv = ∗] �

BP ist effizient, wenn der Grad des Baums klein ist.

Für allgemeine Graphen wird BP zu

Loopy Belief Propagation.


Loopy Belief Propagation

Nachrichten werden nach der folgenden Vorschrift versandt:

1. Hat die Variable v die Nachrichten mf→v von ihren Nachbarn ferhalten, so schickt v die Nachricht

mv→g :=∏

f ist Nachbar von v ,f,g

mf→v

an ihren Nachbarn g.2. Hat der Faktor f die Nachrichten mv→f von seinem Nachbarn v

erhalten, so schickt f die Nachricht

mf→w := [Funktion(f ) ·∏

v ist Nachbar von f ,v,w

mv→f ]

an seine Nachbarin w .Bayes-Lernen Loopy Belief Propagation 39 / 49

Expectation Maximization

Bayes-Lernen Der EM-Algorithmus 40 / 49

Expectation Maximization: Das Modell

Beobachtete Daten x und versteckte Daten y liegen vor.Bestimme ein Modell (mit Parametern Θ), das x „am besten erklärt“.

Die Parameter Θ definieren die gemeinsame Wahrscheinlichkeit

PΘ(x ,y)

Wenn PΘ(x) die Wahrscheinlichkeit von x ist, dann ist

PΘ(x) =∑

yPΘ(x ,y).

Bestimme ein ML-Modell Θ∗:

PΘ∗(x)!= max

ΘPΘ(x) bzw logPΘ∗(x)

!= max

ΘlogPΘ(x).


Hidden Markov Model (HMM)

Für M eine Markov-Kette und alle Zustände p legt Verteilung Dp dieWahrscheinlichkeit fest, mit der M in p Buchstaben a ∈ Σ ausdruckt.

1 Die Markov-Kette M wie auch die Verteilungen Dp über einemAlphabet Σ sind unbekannt =⇒ Θ = (M ,(Dp |p)).

2 Wir beobachten die Ausgabenfolge x , wenn die Kette einezufällige (versteckte) Zustandsfolge y annimmt =⇒

PΘ(x ,y)

ist die Wahrscheinlichkeit, dass das HMM Θ die Ausgabefolge xmit der (versteckten) Zustandsfolge y produziert =⇒∑

yPΘ(x ,y)

ist die Wahrscheinlichkeit, dass Θ die Folge x ausgibt.

Maximum Likelihood soll uns helfen, die HMM Θ zu bestimmen.


Der EM-Algorithmus (1/4)

Es ist PΘ(y | x) ·PΘ(x) = PΘ(x ,y) und deshalb folgt

logPΘ(x) = logPΘ(x ,y)− logPΘ(y | x).

Multipliziere beide Seiten mit PΘ(y | x) und summiere über y

logPΘ(x) =∑

yPΘ(y | x) · logPΘ(x)

=∑

yPΘ(y | x) · logPΘ(x ,y)−

∑y

PΘ(y | x) · logPΘ(y | x).

Wir möchten von Θ zu einem besseren Modell Θ′ übergehen.

logPΘ′(x) =∑

yPΘ(y | x) · logPΘ′(x ,y)︸︷︷︸

=:Q(Θ′ |Θ)

−∑

yPΘ(y | x) · logPΘ′(y | x).



Es ist Q(Θ′ |Θ) :=∑

y PΘ(y | x) · logPΘ′(x ,y).

(a) Q(Θ′ |Θ) = EPΘ(y |x)[ logPΘ′(x ,y) ] ist ein Erwartungswert.(b) Fasse Q(Θ′ |Θ) als Funktion von Θ′ auf.

0!6 logPΘ′(x)− logPΘ(x)

=∑

yPΘ(y | x) · logPΘ′(x ,y)︸︷︷︸

Q(Θ′ |Θ)

−∑

yPΘ(y | x) · logPΘ′(y | x)

−∑

yPΘ(y | x) · logPΘ(x ,y)︸︷︷︸

Q(Θ |Θ)

+∑

yPΘ(y | x) · logPΘ(y | x)

= Q(Θ′ |Θ)−Q(Θ |Θ)+∑

yPΘ(y | x) · log

PΘ(y | x)PΘ′(y | x)



logPΘ′ − logPΘ = Q(Θ′ |Θ)−Q(Θ |Θ)+∑

yPΘ(y | x) · log

PΘ(y | x)PΘ′(y | x)︸︷︷︸

=D(PΘ(∗ |x)||PΘ′ (∗ |x))

> Q(Θ′ |Θ)−Q(Θ |Θ)

Die Kullback-Leibler Divergenz D(PΘ(∗ |x)||PΘ′(∗ |x)) ist stetsnicht-negativ!

Falls Q(Θ′ |Θ)−Q(Θ |Θ) > 0 ist das neue Modell Θ′ besser als Θ.



Eingabe: Eine Beobachtung x .

1. Initialisiere die Parameter für ein Modell Θ(0).2. /* Expectation Schritt */

Bestimme Q(Θ |Θ(t)) als Funktion von Θ.3. /* Maximization Schritt */

Bestimme Θ(t+1), so dass

Q(Θ(t+1) |Θ(t)) = maxΘ

Q(Θ |Θ(t))

und setze t = t +1.4. Wiederhole, solange logPΘ(t)(x)− logPΘ(t−1)(x) zu groß ist.

Der EM-Algorithmus konvergiert i. A gegen ein lokales Maximum.Gutes Verhalten vor Allem bei Exponentialfamiliena

az.B. mehrdimensionale Binomial-, Exponential- und Normalverteilungen.


Der EM-Algorithmus für Mischverteilungen (1/2)

Punkte x1, . . . ,xn ∈R werden durch zwei Normalverteilungen erzeugt.

(a) Wir kennen die beiden Normalverteilungen nicht,I aber beobachten die Daten x = (x1, . . . ,xn).

(b) Wir wissen nicht, ob xi von der ersten (yi = 1) oder der zweitenNormalverteilung (yi = 2) erzeugt wurde.I y = (y1, . . . ,yn) ist der Vektor der versteckten Daten.

(c) Bestimme die Parameter µ1,σ1,µ2,σ2 der Normalverteilungen =⇒I Θ = (µ1,σ1,µ2,σ2) ist das unbekannte Modell.


Der EM-Algorithmus für Mischverteilungen (2/2)

1. Der EM-Algorithmus beginnt mit zwei Normalverteilungen.2. Expectation-Schritt:

I Bestimme die Wahrscheinlichkeit PΘ(t)(yi = 1 |xi), dass xi von derersten Normalverteilung erzeugt wird, d.h

I berechne die Dichten in xi für die beiden durch Θ(t) spezifiziertenNormalverteilungen und setze sie in Relation zueinander.

3. Maximization-Schritt:I Bestimme das optimal auf Θ(t) „eingestellte“ Modell Θ(t+1), d.hI berechne neue, optimale Mittelwerte und Varianzen für die

Verteilungen PΘ(t)(∗ |xi) für alle i .


Der k-Means Algorithmus für das Clustering Problem

1. Bestimme k Werte µ1, . . . ,µk .2. „Expectation-Schritt“: Weise jedem Punkt x das Cluster Ci zu, für

das die Distanz ||x −µi || minimal ist.3. „Maximization Schritt“: Bestimme die Schwerpunkte µi von Cluster

Ci für i = 1, . . . ,k .4. Wiederhole gegebenenfalls.

k -Means ist eine „harte“ Variante des „weichen“ EM-Algorithmus:

Jeder Punkt wird „hart“ einem Cluster zugewiesen,während EM die Zuweisung „weich“ über die Verteilung PΘ(t)(y |x)ausführt.


Documents

Generative Modelle - Professur für Theoretische ... Modelle Handout.pdf · I Das Prinzip der Maximum Entropie: Wähle eine alle Eigenschaften erfüllende Verteilung mit maximaler