Gerhard Heyer Universität...

Strukturalistische Semantik

Institut für Informatik

Linguistische Informatik

Gerhard HeyerUniversität Leipzigheyer@informatik.uni-leipzig.de

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 2

1. Es gibt elementare Ausdrücke, deren Bedeutung Merkmale (in einem Merkmalsraum) sind.

2. Die Bedeutung anderer Ausdrücke sind Funktionen über diese elementaren Merkmale.

3. Die Bedeutung eines Satzes ist ein Merkmals-komplex.

Wie können wir semantische Merkmale identifizieren und für die strukturalistische Semantik verwenden?

Prinzipien der struktalistischen Semantik

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 3

Kookkurrenzanalyse

Grundannahmen der strukturalistischen Semantik (vgl. F. de Saussure 1898/1916)

- Zwei Zeichen, die meist gemeinsam auftreten, ergänzen sich funktional und inhaltlich (Nomen „Sonne“ und Verb „scheinen“)

- Zwei Zeichen, die meist in ähnlichen Kontexten auftreten, haben grammatikalisch und inhaltlich eine ähnliche Funktion (Nomen „Sonne“ und das sinnverwandte Nomen „Kerze“)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 4

Kookkurrenzanalyse

Als Grundlage der Kookkurrenzberechnung können wir definieren:L = (W,S) eine Sprache

W Menge von Wortformen (einfache Einheiten)

S Menge von Sätzen (Komplexe Einheiten), s {w1,…,wn} mit wi W

Der lokale Kontext Ks(w

i) eines Wortes sei die Menge von

Wörtern, mit denen das Wort zusammen auftritt:

Ks(wi)={w1,…, wn}\{wi}

Der globale Kontext KG(wi) einer Wortform sei die Menge von

Wörtern wi W, welche in L statistisch signifikant gemeinsam mit wi auftreten

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 5

Kookkurrenzanalyse - Beispiel

1. Die Sonne scheint.

w1 w2 w3

2. Die Sonne lacht.

w1 w2 w4

3. Die Kerze scheint.

w1 w5 w3

Beobachtungen:

K1(Sonne) = {Die, scheint}

K2(Sonne) = {Die, lacht}

K3(Kerze) = {Die, scheint}

KG(Sonne) = {Die, scheint, lacht}

KG(Sonne) ~ K3(Kerze)

(=> K1(Sonne) U K2(Sonne))

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 6

Kookkurrenzanalyse - Folgerungen

• statistisch signifikant mit einem Term gemeinsam auftretende Terme können als semantische Merkmale für diesen Term verwendet werden

• Terme, die ähnliche Kontexte haben, sind sich semantisch ähnlich

Benötigt werden • ein Maß für das statistisch auffällige gemeinsame

Auftreten von Termen (Kookkurrenzmaß)• ein Maß für die Ähnlichkeit von globalen Kontexten

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 7

Definitionen

Betrachtet werden zwei Wortformen A und B

na = Anzahl der Fenster, in denen A vorkommt

nb = Anzahl der Fenster, in denen B vorkommt

nab = Anzahl der Fenster, in denen sowohl A als auch B vorkommen

n = Anzahl aller Fenster

Bei Satzkookkurrenzen: Fenster = Satz

Mehrmaliges Auftreten eines Wortes innerhalb eines Fensters wird ignoriert (Bag Of Words Modell)

Definitionen

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 8

• Als Baseline betrachten wir als einfachstes Maß die gemeinsame Häufigkeit von A und B

( ),baseline ABsig A B n=

• Unter der Annahme stochastischer Unabhängigkeit

p(A,B)=p(A) * p(B)

werden Kookkurrenzen zwischen zwei häufigen, aber zufällig auftretenden Wörtern, ebenfalls „relativ“ häufig auftreten.

• Die Baseline ist demnach nur bei einer Gleichverteilung sinnvoll – Wörter sind aber Zipf-verteilt

Signifikanzmaße - Frequenz als Baseline

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 9

1 Mio. signifikantesten Kookk.

(1 Mio. frequentesten Kookk.)

10 Mio. unsignifikantesten Kookk.

(10 Mio. Kookk. mit Freq. 1 [Teil])

( ),baseline ABsig A B n=

Signifikanzmaße – Frequenz

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 10

Signifikanzmaße – Dice und Jaccard

( ) 2, AB

diceA B

nsig A B

n n

×=

×

Tanimoto Abstand bzw. Jaccard Koeffizient:

(Anteil der Doppeltreffer bzgl. Anzahl der Einzeltreffer)

abba

ab

nnn

nBAsig

),(tan

Dice Koeffizient:

Signifikanzmaße – Dice und Jaccard

+

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 11

1 Mio. signifikantesten Kookk. 10 Mio. unsignifikantesten Kookk.

( ) 2, AB

diceA B

nsig A B

n n

×=

×

Signifikanzmaße – Dice und Jaccard

+

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 12

Mutual Information (Church et al. 1990):

Unter der Annahme der stochastischen Unabhängigkeit wird die Abweichung von der beobachteten zu der erwarteten Frequenz berechnet

( ) ( )( ) ( )

,, log log AB

MIA B

p A B n nsig A B

p A p B n n

æ ö æ ö×= =ç ÷ ç ÷× ×è øè ø

)(*)(),( BpApBAp

))(*)(log()),(log( BpApBAp

0)(*)(

),(log

BpAp

BAp

Signifikanzmaße – Mutual Information

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 13

1 Mio. signifikantesten Kookk. 10 Mio. unsignifikantesten Kookk.

( ) ( )( ) ( )

,, log log AB

MIA B

p A B n nsig A B

p A p B n n

æ ö æ ö×= =ç ÷ ç ÷× ×è øè ø

Signifikanzmaße – Mutual Information

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 14

Signifikanzmaße – Log Likelihood (nach Dunning 1993)

Annahme:

Für je zwei Wortformen w1 und w2 eines Textes der Länge n stelle man sich das folgende statistische Experiment vor:

Wir vergleichen das gemeinsame Auftreten (Bigramm) von w1 und w2 mit einem Bigramm x im Text. Das Ergebnis des Experiments ist positiv, wenn x = (w1, w2), sonst negativ.

Diesen Test wiederhole man für alle Bigramme. Wir interessieren uns nun für die Wahrscheinlichkeit von k positiven Ergebnissen, d.h. wir möchten wissen, wie wahrscheinlich es ist, dass (w1, w2) genau k-mal im Text auftritt.

Diese Wahrscheinlichkeit von k gemeinsamen Vorkommen von w1 und w2 vergleichen wir dann mit einem Erwartungswert, der auf der Annahme stochastischer Unabhängigkeit beruht. Wir messen damit die Signifikanz des gemeinsamen Auftretens von w1 und w2 .

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 15

Log Likelihood - Wahrscheinlichkeitsverteilung

• Sei p die Wahrscheinlichkeit, bei einem Vergleich ein positives Ergebnis zu erzielen, so ist die Wahrscheinlichkeit, bei n Versuchen k positive Ergebnisse zu erzielen, gegeben durch die Binomialverteilung:

• Die Binomialverteilung hat einen Erwartungswert np und eine Varianz von np (1- p).

• Für seltene Ereignisse (in unserem Fall: Bigramme) weicht die Normalverteilung signifikant von der Binomialverteilung ab.

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 16

Log Likelihood – likelihood ratio

• Die likelihood Funktion H beschreibt die erwartete und tatsäch-liche Auftretenswahrscheinlichkeit eines Bigramms (w1, w2) durch zwei unabhängige Binomialverteilungen (Approximation der Zipf- bzw. Power-Law-Verteilung)

• Die Nullhypothese basiert auf der Erwartung der stochastischen Unabhängigkeit : p(w1, w2) = p(w1) * p(w2)

• Die likelihood ratio ist nun der Quotient zweier Maxima: dem maximalen Wert der likelihood-Funktion H auf dem Teilraum , der durch die Nullhypothese gegeben ist, geteilt durch das Maximum von H auf dem gesamten Ereignisraum :

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 17

Log Likelihood – likelihood ratio (2)

• In unserem Fall lautet dies:

• Die Maxima werden erreicht durch die maximum likelihood estimates p1 = k1/n1, p2 = k2/n2 und p = (k1 + k2)/(n1 + n2)

• Nach Einsetzen und Umformen erhält man die eigentliche Prüfgröße −2 log (mit L(p, k, n) = pk(1 − p)n−k ):

• Demnach sind alle Bigramme, für die −2 log groß genug ist (und die mit einer gewissen Mindestfrequenz auftreten), statistisch signifikant.

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 18

Beispiel (nach Dunning 1993)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 19

Beispiel (nach Dunning 1993)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 2020

1 Mio. signifikantesten Kookk. 10 Mio. unsignifikantesten Kookk.

Signifikanzmaße – Loglikelihood (Approximation)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 2121

Signifikanzmaße - Beispiele Eingabe logl dice baseline MI

| Abfall | radioaktiv | radioaktiv | d- | Abklingzeit| Abfall | Tonne | entsorgen | und | Bodenwurzel| Abfall | entsorgen | Endlager | in | Chemie-Praktikum| Abfall | Endlager | Entsorgung | werden | Dosenbier-Trinker| Abfall | werden | hochradioaktiv | ein | STAWA

| Zink | Kupfer | Blei | d- | Verzinken| Zink | Blei | Kupfer | und | Eisengegenstand| Zink | und | Cadmium | %N% | Hartlot| Zink | Cadmium | Zinn | ein | Bismut| Zink | Silber | Nickel | in | stolberger

| Montag | am | am | d- | VHS-Öffnungszeit| Montag | %N% | abend | am | Focus-Tag| Montag | Uhr | Uhr | %N% | Einzelhandlesverband| Montag | abend | Freitag | in | FIS-Sicherheitsexperte| Montag | in | kommend | ein | Freischützstras

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 22

• Berechnung der Menge von Kookkurrenten, welche als signifikante Elemente in der Menge der Kookkurrenzen aller Kookkurrenten eines Ausgangswortes enthalten sind

• Graphische Darstellung auf der Basis von simulated annealing

• Darstellung als interaktiver Graph, d.h. von jedem Knoten im Graph kann ein neuer Graph interaktiv ausgewählt werden

Visualisierung von Kookkurrenzmengen

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 23

Graf zum Beispiel

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 24

Wichtige Eigenschaften von Kookkurrenzen

• Abhängig vom zugrundegelegten Korpus• allgemeinsprachliche vs. fachsprachliche Verwendung• Zeitabhängigkeit

• Wenn die Kookkurrenten einer Wortform nach abnehmender Signifikanz geordnet werden, können die Ränge einzelner Kookkurrenten variieren (abhängig vom Signifikanzmaß)

• Die Graphen einzelner Wortformen können kombiniert werden (lexikalische Struktur, Textgraphen, small worlds of concepts, ...)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 25

Example graph for Dublin (German Newspaper text)http://www.wortschatz.uni-leipzig.de/

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 26

Example graph for Dublin (Birith newspaper text)http://www.corpora.uni-leipzig.de

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 27

Example graph for Dublin (German Wikipedia text)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 28

Example graph for Dublin (German Wikipedia links)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 29

Example graph for Benzineinspritzung (Wikipedia)http://www.wortschatz.uni-leipzig.de/WP

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 30

Example graph for Benzineinspritzung (Wikipedia links)

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 31

Example Co-occurrence of Graph “iraq” 1/3

March 2001

strong cluster related to the Madrid train bombings

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 32

Example Co-occ. Graph “iraq” 2/3

May 2004

strong cluster related to the scandal at Abu Ghraib prison

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 33

Example Co-occ. Graph “iraq” 3/3

August 2004 skirmishes in and

around Najaf ceasefire with

Muqtada al-Sadr installation of Iyad

Allawi

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 34

Relativer Rang von Wortkookkurrenten

While the statistical significance of two term‘s co-occurrence is symmetric, their rank on the list of a term‘s set of co-occurrences may differ

Signifikance of co-occurrence „Welt“ and „der“:

SYNS(Welt, der) = 26646

Rank (Co: Welt, Source: der) = 13

Rank (Co: der, Source: Welt) = 1

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 35

Ähnliche Ränge

Other examples with similar rank

Rank (Papst, Benedikt) = 1

Rank (Benedikt, Papst) = 1

Rank (Diesel-Pkw, Rußpartikelfilern) = 7

Rank (Rußpartikelfiltern, Diesel-Pkw) = 6

Rank (Bundestag, Bundesrat) = 1

Rank (Bundesrat, Bundestag) = 1

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 36

Verschiedene Ränge

Examples of different rank

Rank (Bundestag, Ökosteuer) = 29

Rank (Ökosteuer, Bundestag) = 68

Rank (Krieg, USA) = 18

Rank (USA, Krieg) = 53

Rank (Krieg, Deutschland) = 46

Rank (Deutschland, Krieg) = 143

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 37

Changing ranks

Rank t1

t2

t3

… ti

… tn

1

2

3

…

k

…

m

Changing ranks of co-occurrences wj of w over time

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 38

Interactively exploring 2004

38Prof. Dr. G. Heyer Dagstuhl Workshop on Document Mining, April 2011

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 39

Textgraphen

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 40

Small Worlds - Hintergrund

Small World GraphenEin Optimum zwischen zwei Extremen

Graph regulär zufällig small-world

Durchschnittliche Pfadlänge

lang kurz kurz

Cluster-Koeffizient hoch niedrig hoch

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 41

Merkmale von small worlds

§ Hoher Cluster-KoefficientIm gesamten Grafen existieren lokale Cluster, die skalierbar sind – vergleichbar Fraktalen (Prinzip der Selbstähnlichkeit)

§ Kurze durchschnittliche PfadlängeIm gesamten Grafen können lokale Cluster in wenigen Schritten erreicht werden. (Small World Effekt: “Oh, Sie kennen den auch?”)

D.J. Watts and S.H. Strogatz, (1998). Collective dynamics of ‘small world’ networks. Nature, (393), p440-442.

A.L. Barabasi et al (2000). Scale-free characteristics of random networks: the topology of the World-wide web. Physica A (281)70-77.

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 42

„Roter Faden“ – Bewegung im Textgraphen

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 43

• Der globale Kontext einer Wortform reflektiert textspezifisch seine Verwendung

• Als Grundlage der semantischen Merkmale eines Wortes werden signifikante Kookkurrenzen verwendet

• Diese werden in Form eines Bedeutungsvektors jedem Wort zugeordnet

• Theoretischer Hintergrund bildet das Vector Space Model

Vector Space basierte Operationalisierung

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 44

Hintergrund: Die Text-Dokument-Matrix als Grundlage des IR

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 45

ar2 * T2

T2 * Dr

T2

Dr

ar1 * T1

T1 * Dr

T1

Bildliche Darstellung eines zweidimensionalen Vektorraumes

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 46

• Anstelle einer Term-Dokument-Matrix verwenden wir eine Term-Term-Matrix (basierend auf der Menge signifikanter Terme einer Textkollektion und deren Kookkurrenzen)

• Jedem Term wird ein Bedeutungsvektor zugeordnet

Grundidee einer strukturalistischen Semantik

t1 t2 … tn

t1 - a12 … a1n

t2 a21 - … a2n

… …

tn an1 an2 … -

),.....,,( 21 iniii aaaT

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 47

Ähnlichkeitsberechnungen

Unter der Annahme orthogonaler Vektoren entfällt eine Berechnung von Termkorrelationen.

Ähnlichkeitsmaße für den Vergleich von Termen:

n

jisirisr aaTTsim

1,

)(

Skalarprodukt City Block Metrik

Cosinus Koeffizient

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 48

Ein Beispiel

blue boy girl ocean red white

blue - 2 1 4 43 37

boy 2 - 47 0 1 13

girl 1 47 - 1 3 37

ocean 4 0 1 - 2 0

red 43 1 3 2 - 23

white 37 13 37 0 23 -

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 49

Addierte Differenz

blue boy girl ocean red white

blue - 2 1 4 43 37

red 43 1 3 2 - 23

Diff. - 1 2 2 - 14 =>19

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 50

Berechnete Distanzen

blue boy girl ocean red white

bluered

-43

21

13

42

43-

3723 => 19

boyred

243

-1

473

02

1-

1323 => 97

girlred

143

471

-3

12

3-

3723 => 103

oceanred

443

01

13

-2

2-

023 => 65

redred

4343

11

33

22

--

2323 => 0

whitered

3743

131

373

02

23-

-23 => 54

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 51

Ergebnisse Bedeutungsähnlichkeiten

girl blue foot baby bread butter

boy red leg child meat cheese

man green hand mother cake bread

woman grey head girl cheese sugar

mother yellow back boy milk chocolate

child white side father toast milk

Strukturalistische Semantik

Prof. Dr. G. Heyer Modul Linguistische Informatik 52

Literatur

• Dunning, T. (1993). Accurate methods for the statistics of surprise and coincidence. Computational Linguistics, 19(1), 61-74.

• Heyer, G., Läuter, M., Quasthoff, U., Wittig, T. & Wolff, C. (2001): Learning relations using collocations, In: A. Maedche, S. Staab, C. Nedellec & E. Hovy, (eds.). Proc. IJCAI Workshop on Ontology Learning, Seattle/ WA.

• Manning, C. & Schütze, H. (1999): Foundations of Statistical Natural Language Processing. Cambridge, MA: MIT Press.

• Quasthoff, U. & Wolff. C. (2002): The poisson collocation measure and its applications. Proc. Second International Workshop on Computational Approaches to Collocations, Wien.

• Schmidt, F. (1999): Automatische Ermittlung semantischer Zusammenhänge lexikalischer Einheiten und deren graphische Darstellung, Diplomarbeit, Universität Leipzig.

• Smadja, F. (1993): Retrieving collocations from text: Xtract. Computational Linguistics 19(1), 143-177.

• Wittgenstein: Tractatus logico-philosophicus.