Dokumentenmodelle - asv.informatik.uni-leipzig.deasv.informatik.uni-leipzig.de/uploads/document/file_link/376/TMI05_Topicmodelle1.pdf–wenn dieser im Dokument vorkommt, ist der Vektor

Institut für Informatik

Dokumentenmodelle

Gerhard Heyer, Patrick JähnichenUniversität Leipzig

heyer@informa [email protected]

Gerhard Heyer, Patrick Jähnichen Modul Textmining

Ziel

• Retrieval von Information– Clustering von Wörtern anhand Bedeutung(Semantik)– Identifizierung von Synonymien und Polysemien– Themenzuordnung von Dokumenten– ...?

• Dimensionsreduktion– Trivial ist nur das Auszählen von Wörtern– Dimension hierbei: V (V aber oft sehr groß, oft >> 1000000)– Wie reduzierbar?


Grundlagen


Aufbau von Textkorpora

• Korpus C enthält Menge von D Dokumenten• Jedes Dokument enthält Menge von Nd Wörtern• Gesamter Korpus enthält Vokabular von V voneinander

verschiedenen Wörtern• Länge des Korpus ist N


Vektorraummodell

• Dokumente werden als Vektoren dargestellt– Jede Komponente im Vektor entspricht einem separaten Term– wenn dieser im Dokument vorkommt, ist der Vektor an dieser Stelle

von 0 verschieden– Die Dimension des Vektors ist V (Größe des Vokabulars)

– Möglichkeit der Nutzung von Vektoroperationen zum Vergleich vonDokumenten, z.B. Kosinusmaß

– Häufig werden statt reinen Termfrequenzen tf-idf Gewichte alsVektorkomponenten genutzt


Tf-idf

• Zähle Auftreten von Termen in Dokument• Vergleiche Auftreten von Term in Dokument mit Logarithmus

von inversem Auftreten des Terms in anderen Dokumentendes Korpus

• Ergebnis: Term-Dokumentmatrix (∈ RVxD) mit tf-idf Werten derTerme des Vokabular

• Reduktion von Dokumenten(unbestimmter Größe) auf Listevon Werten fixer Länge

• Berechnung:


Statistik

• Multinomiale Verteilung– Generalisierung der Binomialverteilung– Binomialverteilung ist Wahrscheinlichkeitsverteilung der Anzahl Erfolge

von n unbhänigen Bernoulli-Experimenten– Analogon der Bernoulli-Verteilung in mult. Verteilung ist die Kategoriale

Verteilung, hier resultiert jeder der n Versuche in genau einem von KAusgängen mit Wahrscheinlichkeiten p1, ..., pK und

– Zeigt ein Zufallsvariable Xi die Anzahl der Ausgänge mit Ergebnis i an,so folgt der Vektor X = (X1, ..., XK) einer Multinomialverteilung mitParameter n und p = (p1, ..., pK)

– Im Bereich der automatischen Sprachverarbeitung sprechen wir meistvon multinomialer Verteilung wenn wir eigentlich die KategorialeVerteilung meinen


Statistik

• Bedingte Wahrscheinlichkeit– Wahrscheinlichkeit für eine Beobachtung x unter der Voraussetzung

dass Beobachtung y zuvor eingetreten ist heißt bedingeWahrscheinlichkeit

Sind x und y voneinander unabhängig, so gilt

Und damit


Statistik

• Bayestheorem

• In Worten


Bag-of-words assumption

• Reihenfolge der Wörter wird nicht berücksichtigt• Ein Dokument entspricht einem „Sack“ voller Wörter• Für jedes Wort wird Frequenz gespeichert• Annahme:

– Informationen über Art und Anzahl von Wörtern reicht aus umRückschlüsse auf die Struktur von Text zu ziehen

– Grundlage: Satz von de Finetti• Annahme der Austauschbarkeit:

• Austauschbare Zufallsvariablen folgen einer vermischten Verteilung(mixture distribution), meist unendlich


Singulärwertzerlegung

• Ist die Darstellung einer Matrix als Produkt von drei speziellenMatrizen

• Singulärwerte sind spezifische Eigenschaft einer Matrix,vergleichbar mit Eigenwerten

• Singulärwertzerlegungenexistieren für jede Art vonMatrix


Singulärwertzerlegung - Anwendungen

• Statistik– Hauptkomponentenanalyse (engl. Principal Component Analysis, PCA)

• Strukturierung von Datensätzen durch Näherung von vielen statistischenVariabeln durch geringe Zahl von Linearkombinationen (denHauptkomponenten)

– Heißt auch Karhunen-Loève-Transformation• Bildkompression

– Bild (Matrix aus Farbwerten) wird zerlegt– Nur stark von Null verschieden Singulärwerte werden berücksichtigt– Rekonstruktion des Bildes möglich– Weglassen kleiner Singulärwerte ist verlustbehaftete Modellreduktion


Latent Semantic Analysis - LSALatent Semantic Indexing - LSI


LSA (Deerwester et. al.)

• Form der linearen Faktorisierung• Grundlage bildet eine Wort-Dokument Kookkurrenzmatrix• Diese wird per Singulärwertzerlegung in drei Matrizen zerlegt• Alle bis auf n höchste Singulärwerte werden 0 gesetzt• Ursprüngliche Matrix wird rekonstruiert (hat nun geringeren

Rang n)


LSA Beispiel


LSA Beispiel - Termfrequenzmatrix


LSA Beispiel - Singulärwertzerlegung


LSA Beispiel - rekonstruierte Matrix mit geringerem Rang


LSA

• Vorteil:– Keine Eins/Null Entscheidungen mehr– Dimensionsreduktion auf n Dimensionen („semantische Kategorien“)

• Nachteil:– Verlustbehaftete Methode– Schlechtes zugrundeliegendes statistisches Model --> schlechte

Begründbarkeit• Gemeinsame Verteilung von Wörtern und Dokumenten folgt nicht Gauss

sondern Poissonverteilung– Kein Vorwissen über n– Polysemie

• Jedes Wort wird genau einer semantischen Bedeutung zugeordnet(gleicher Datenpunkt im semantischen Raum)

• D.h. Ergebnis ist Durchschnitt aller verschiedenen Bedeutungen einerWortes (als Vektor)


LSA

• Geometrische Interpretation– Reduzierte Dimensionen spannen „semantischen Raum“– In Wortmatrix U

• Winkel zwischen Wortvektoren (Cosinus-Maß) entspricht ihrersemantischen Ähnlichkeit

• Möglichkeit semantisches Clustern– Ähnlich für Dokumentmatrix V

• Clustering von ähnlichen Dokumenten


Latente Variablen

• Theoretische Konstrukte, abhängig von Modell• Sind nicht direkt messbar• Können ausgehend von messbaren Variablen (Observablen)

bestimmt werden (auch: Operationalisierung)• Beispiel: Intelligenzquotient

– Kann nicht direkt gemessen werden– Wird anhand von vielen Testergebniss (Fragen) bestimmt– Da latente Variablen nur theoretische Konstrukte sind, ist der IQ nur so

aussagekräftig, wie die Theorie plausibel (daher teils massive Kritik anIQ Messung)


probabilistic Latent SemanticIndexing - pLSI


pLSI (Hofmann)

• Stammt nicht aus linearer Algebra (wie LSI)• Geht von vermischten Verteilungen und einem Modell der

latenten Klassen aus• Basiert auf Aspect-Modell

– Ordnet jeder Beobachtung (Term) eine latenten Variable (Klasse) zu– Gemeinsame Wahrscheinlichkeit über Dokument und Terme wird

definiert


pLSI

• Generiert Dokumente:– Auswählen eines Dokuments d mit Wkt. P(d)– Auswählen einer latenten Klasse z mit Wkt. P(z|d)– Generieren von Wort w mit Wkt. P(w|z)

• Übersetzung in Multivariates Modell

• Modell basiert auf zwei Annahmen von Unabhängigkeit– Beispieltupel (d,w) werden unabhängig generiert (Bag-of-words)– Bedingte Unabhängigkeit zwischen w und d, sind nur über latente

Klasse z gekoppelt


pLSI

• Umstellen mit Hilfe des Bayestheorem


pLSI

• Ähnlichkeit zu LSA– Definiere 3 Matrizen:

– Gemeinsames Wahrscheinlichkeitsmodell gegeben durch:

• Beobachtung– Äußere Produkte zwischen Zeilen von Û und V zeigen bedingte

Unabhängigkeit– K Faktoren entsprechen Mischkomponenten aus Aspect-Model– Mischanteile ersetzen Singulärwerte


pLSI

• Unterschied zu LSA– Funktion zum Bestimmen der optimalen Annäherung bei LSA: L2- oder

Frobenius-Norm– Entspricht der Annahme eines Gauss-Rauschens auf den

Termanzahlen– pLSI nutzt Likelihood-Funktion zur expliziten Maximierung der

Vorhersagequalität des Modells• Dies entspricht der Minimierung der Kullback-Leibler Divergenz zwischen

tatsächlicher und approximierter Wahrscheinlichkeitsverteilung


pLSI

• Geometrische Deutung– K klassenspezifische Multinomialverteilungen werden im M-1

dimensionalen Simplex über alle möglichen Multinomialverteilungendargestellt

– Bilden K-1 dimensionalen Subsimplex– P(w|d) gegeben durch konvexkombinierte P(w|z)


pLSI

• Würdigung– Approximation in P ist für jedes Wort eine wohldefinierte

Wahrscheinlichkeitsverteilung– Faktoren haben klare probabilistische Bedeutung– LSA arbeitet nicht mit Wahrscheinlichkeiten, sogar negative Werte sind

möglich– Keine offensichtliche Interpretation der Richtung im semantischen

Raum von LSA, in pLSI ist Richtung interpretierbar als multinomialeWortverteilung

– Da probabilistisches Modell: Möglichkeiten der Modellselektion,Herausfinden von optimalem K (Anzahl der latenten Klassen)


Bildquellen

• Wikipedia, Singulärwertzerlegung• Deerwester, Dumais, Furnas, Landauer, Harshman: Indexing

by Latent Semantic Analysis, Journal of the American Societyfor Information Science, 1990

• Hofmann: Probabilistic Latent Semantic Indexing, Proceedingsof the Twenty-Second SIGIR, 1999

Documents

Dokumentenmodelle - asv.informatik.uni-leipzig.deasv.informatik.uni-leipzig.de/uploads/document/file_link/376/TMI05_Topicmodelle1.pdf–wenn dieser im Dokument vorkommt, ist der Vektor