Upload
nguyenmien
View
215
Download
0
Embed Size (px)
Citation preview
Universität PotsdamInstitut für Informatik
Lehrstuhl Maschinelles Lernen
Latente Dirichlet-AllokationTobias Scheffer
Peter HaiderPaul Prasse
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Themenmodellierung
Themenmodellierung (Topic modeling) liefertMethoden, große elektronische Archive automatisch zu organisieren, verstehen, durchsuchen und zusammenzufassen
1. Versteckte Themenmuster finden, die in der Dokumentensammlung reflektiert sind
2. Dokumente anhand der gefundenen Themen annotieren
3. Annotationen verwenden, um Dokumente zu organisieren und durchsuchen
2
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Beispielthemen eines Textkorpus
3
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Entwicklung von Themen über die Zeit
4
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Zusammenhänge zwischen Themen
5
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Annotation von Bildern
6
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Probabilistische Modellierung
1. Behandlung der Daten als Beobachtungen, die aus einem generativen probabilistischen Prozess mit versteckten Variablen entstehen Bei Dokumenten reflektieren die versteckten
Variablen die thematische Struktur der Textsammlung
2. Versteckte Struktur finden mit Posterior-Inferenz Was sind die Themen, die diese Sammlung
beschreiben?3. Neue Daten in das geschätzte Modell
„einsortieren“ Wie passt das neue Dokument in die
Themenstruktur?7
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Latente Dirichlet-Allokation
Generatives Modell für Texte (als bag-of-words) Jeder Text kann mehrere Themen enthalten Jedem Wort ist genau ein Thema zugeordnet
8
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Generatives Modell
Jedes Dokument hat eine Mischung aus (korpus-globalen) Themen Themen sind Verteilungen über die Wörter des Vokabulars Jedes Wort ist aus einem der Themen gezogen 10
Themen Dokumente Themenanteile und Zuweisungen
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Inferenzproblem
In Wirklichkeit sind nur die Dokumente beobachtet Das Ziel ist, die zugrundeliegende Themenstruktur zu inferieren
11
Themen Dokumente Themenanteile und Zuweisungen
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Graphische Modelle
Knoten sind Zufallsvariablen Kanten beschreiben mögliche Abhängigkeiten Beobachtete Variablen sind schattiert Tafeln (plates) beschreiben replizierte Struktur
12
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Graphische Modelle
13
Struktur des Graphen definiert bedingteUnabhängigkeiten zwischen den Zufallsvariablen
Obiger Graph bedeutet:
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Latente Dirichlet-Allokation
14
Dirichlet-Hyperparameter
Themenzuweisung pro Wort
Themenanteile pro Dokument
Beobachtetes WortThemen
Themen-Hyperparameter
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Latente Dirichlet-Allokation
15
Modell spezifiziert bedingte Unabhängigkeiten:
Hyperparameter α und η sind fest
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Latente Dirichlet-Allokation
Modellierung der einzelnen Verteilungen:
Jedes Thema βk ist eine Verteilung über Wörter des Vokabulars (Multinomialverteilung)
Verteilung über Themen ist Verteilung über Parameter der Multinomialverteilung
Wahl bei LDA: Dirichlet-Verteilung
16
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Wiederholung: Dirichlet-Verteilung
Verteilung über nichtnegative Vektoren, deren Summe 1 ergibt
Verallgemeinerung der Beta-Verteilung auf mehr als 2 Dimensionen
Parametrisiert durch positiven Vektor Dichtefunktion:
17
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Wiederholung: Dirichlet-Verteilung
18
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Wiederholung: Dirichlet-Verteilung
Je größer die Summe der Alphas, desto „spitzer“ ist die Verteilung Zieht man aus einer „spitzen“ Verteilung, erhält man
Vektoren, die schwach variieren Je kleiner die Summe der Alphas, desto mehr
Wahrscheinlichkeitsmasse konzentriert sich auf die Ränder und Ecken Zieht man daraus, erhält man sparse Vektoren
(meiste Komponenten 0)
19
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Wiederholung: Dirichlet-Verteilung
Dirichlet-Verteilung ist der konjugierte Prior der Multinomialverteilung Posterior hat selbe Form wie der Prior
Bei LDA: normalerweise austauschbarerDirichletprior alle Komponenten des Parametervektors identisch effektiv nur ein Parameter
20
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Latente Dirichlet-Allokation
Modellierung der einzelnen Verteilungen:
andere Schreibweise für
wichtig hier: α < 1, um sparse θ zu erzeugen
Jedes Wort wird aus dem entsprechenden Themagezogen
21
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
LDA: Teilprobleme
Aus gegebener Dokumentensammlung, inferiere Themenzuweisungen für jedes Wort zd,n
Themenanteile für jedes Dokument θd
Verteilung über Vokabular für jedes Thema βk
jeweils die Posterior-Verteilungen davon Benutze Posterior-Erwartungswerte für
verschiedene Anwendungen, z.B. Information Retrieval, Dokumentähnlichkeit, usw. 22
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Posterior-Inferenz
Berechnung der Posterior-Verteilung zu schwierig:
Daher: Approximative Posterior-Inferenz Mehrere Möglichkeiten:
Mean-field-variational-Methoden Expectation propagation Collapsed variational inference Gibbs sampling
einfachstes Verfahren
23
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Echte Posteriorverteilung zu schwierig
Gibbs-Sampling produziert Samples aus der echten Verteilung
Idee: Posterior für einzelne Zufallsvariablen ist leicht zu berechnen, z.B.
D.h. man kann nacheinander jede einzelneZufallsvariable neu aus ihrem Posterior gegebenalle anderen Variablen ziehen
24
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Neu ziehen von einzelnen Variablen entspricht Zustandsübergang
Zustand = komplette Belegung von allen Variablen Iteratives neu ziehen ist Random Walk auf dem
Zustandsgraphen
25
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Häufigkeiten des Besuchs von Zuständen entspricht Verteilung über die Belegungen der Zufallsvariablen
Theorem: Wenn man sich lange genug auf dem Zustandsgraphen bewegt, und die Zustandsübergänge aus den Einzel-Posteriorszieht, konvergieren die Besuchshäufigkeiten zur Gesamt-Posterior-Verteilung 26
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Theorem: Wenn man sich lange genug auf dem Zustandsgraphen bewegt, und die Zustandsübergänge aus den Einzel-Posteriorszieht, konvergieren die Besuchshäufigkeiten zur Gesamt-Posterior-Verteilung egal wo man anfängt
27
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Um Samples aus dem Gesamtposterior zu erhalten,
mit beliebigem Startwert beginnen, und samplen, bis die Verteilung konvergiert
zwischen dem Entnehmen einzelner Samples viele Sampleschritte durchführen, damit die Samples voneinander unabhängig sind
28
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling: Algorithmus
Für i von 1 bis … Für j von 1 bis 1000
Für alle Themen k: • Ziehe
Für alle Dokumente d:• Ziehe • Für alle Wörter n in Dokument d:
– Ziehe Gib Posterior-Sample aus
29
z.B.
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Gibbs-Sampling
Anwendung der Posterior-Samples: Vorhersagenmitteln
Z.B. Berechnung der Ähnlichkeit zweier Dokumente als inneres Produkt der Themenverteilungen
30
Bayesian Model Averaging
Ersetzen des Integrals über die Posterior-Verteilung durch Summe über Samples aus dem Posterior
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Collapsed Gibbs-Sampling
Bei normalem Gibbs-Sampling: sehr viele Iterationen notwendig
Verbesserung: nur Z samplen, θ und βrausintegrieren Idee dahinter: kleinerer Zustandsgraph, da Zustand
nur noch aus Z besteht Statt :
31
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Collapsed Gibbs-Sampling
32
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Collapsed Gibbs-Sampling
33
1. Term („Likelihood“):
Zähler, wie oft Wort w Thema z zugewiesen ist (ohne wd,n)
Zähler, wie viele Wörter Thema z zugewiesen sind (ohne wd,n)
Größe des Vokabulars
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Collapsed Gibbs-Sampling
34
2. Term („Prior“):
Zähler, wie viele Wörter in d Thema z zugewiesen sind (ohne wd,n)
Anzahl der Wörter in d (ohne wd,n)
Anzahl der Themen
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Collapsed Gibbs-Sampling
35
Effizient implementierbar Man muss sich immer nur die 4 verschiedenen
Typen von Zählern merken Bei Bedarf lassen sich zusätzlich Samples für θ und
β generieren Einfach aus dem Posterior ziehen
Braucht weniger Iterationen als normales Gibbs-Sampling, da kleinerer Zustandsgraph →schnelleres Einpendeln auf richtige Verteilung
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Beispielinferenz
Daten: Sammlung von Artikeln in Science von 1990-2000 17.000 Dokumente 11 Mio. Wörter 20.000 verschiedene Vokabeln (ohne Stopwörter und
seltene Wörter) Modell: LDA mit 100 Themen 36
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Beispielinferenz
37
Themen
Wah
rsch
einl
ichk
eit
Scheffer/Vanck: S
prachtechnologieS
cheffer/Haider/P
rasse: Sprachtechnologie
Verwendung, um Dokumentensammlungen zu durchforsten
41