Automatische Klassifikation mit Automatische Klassifikation mit Maximum-Entropie-Modellen und BootstrappingMaximum-Entropie-Modellen und Bootstrapping

Anwendung bei der Bestimmung von Begriffstypen Anwendung bei der Bestimmung von Begriffstypen

und der Wortsinn-Disambiguierung und der Wortsinn-Disambiguierung

Christof RumpfHeinrich-Heine-Universität Düsseldorf

10. Dezember 2008

ÜberblickÜberblick

• Automatische Klassifikation– Probleme und Anwendungsfelder– Methoden

• Wortsinn-Disambiguierung– Problemstellung– Methoden

• Bestimmung von Begriffstypen– Problemstellung– Methoden

KlassifikationKlassifikation

Klassifikation [lateinisch] die, allg.: Einteilung von Dingen oder Begriffen nach gemeinsamen MerkmalenMeyers Lexikon Online

KlassifikationsproblemeKlassifikationsprobleme

• Systematik, Taxonomie– Hierarchische Ordnung der Lebewesen nach

phänotypischen bzw genetischen Kriterien

• Wissensrepräsentation– Thesaurus, Ontologie, semantisches Netz

• Linguistik– Wortartenbestimmung– Wortsinnbestimmung Ambiguität– Begriffstypbestimmung– u.v.m.

Gleiche Oberflächenformen mit verschiedenen Klassen-zugehörigkeiten

Automatische KlassifikationAutomatische KlassifikationDie automatische Klassifikation ist ein Teilgebiet des maschinellen Lernens und somit auch der sogenannten künstlichen Intelligenz.

Bei der automatischen Klassifikation geht es um das algorithmische Lernen eines Klassifikators, d.h. eine Funktion : Objekte Klassen (bzw 2Klassen).

Verfahren zur automatischen Klassifikation

überwachtsupervised

benötigt handannotierteTrainingsdaten: TEUER

nicht überwachtunsupervised

benötigt keine handannotiertenTrainingsdaten: BILLIG

halb-überwachtsemi-supervised

weniger handannotierteTrainingsdaten: PREISWERT

Clustering:unbenannte

Gruppen

Klassifikation:

benannte Klassen

KlassifikatorKlassifikatorEs gibt zwei konkurrierende Paradigmen zur Bestimmung von Klassifikatoren

: Objekte Klassen Funktion

Symbolische Methoden Logik, Automatentheorie

Objektbeschreibung Klasse Deduktion aufgrund von Regeln

Monotone vs nicht-monotone Systeme, Ausnahmen, Präferenzen,

Formale Begriffsanalyse als symbolisches Clustering

Statistische Methoden Wahrscheinlichkeits- und Informationstheorie

P( Klasse | Objektbeschreibung ) bedingte Wahrscheinlichkeiten

Beliebig feine Modellierung der Evidenz einzelner Faktoren in derObjektbeschreibung

Die Objektbeschreibung enthält Merkmale des Objekts und ggf. des Kontexts, in dem das Objekt auftritt, z.B. in Form von Attribut-Wert-Paaren.

Statistischer KlassifikatorStatistischer KlassifikatorDie primitivste Möglichkeit zur Berechnung eines statistischen Klassifikators besteht darin, gemeinsame Vorkommen von Klassen mit Kontexten in einem annotierten Trainingskorpus zu zählen:

P(Klasse|Kontext) = Count(Klasse,Kontext) / Count(Klasse)

Entscheidungsregel für automatische Klassifikation:

arg maxKlassse P(Klasse|Kontext)

Das ist meistens keine gute Methode, denn es bleibt unberücksichtigt:

neue Kontexte können auftreten, die im Modell nicht vorkommen unterschiedliche Evidenz einzelner Kontextmerkmaleunterschiedliche Abhängigkeiten von Merkmalen untereinander

Alternativen:

Naiver Bayes-KlassifikatorMaximum-Entropie-Modell

Naiver Bayes-KlassifikatorNaiver Bayes-KlassifikatorBayes Entscheidungsregel Wähle die Klasse höchster Wahrscheinlichkeit

Gewinnerklasse = arg maxKlasse P(Klasse|Kontext)

Bayes Theorem Umkehrung bedingter Wahrscheinlichkeiten

P(Klasse|Kontext) = P(Kontext|Klasse) P(Klasse) / P(Kontext)

arg maxKlasse P(Klasse|Kontext) = arg maxKlasse P(Kontext|Klasse) P(Klasse)

Naive Bayes Annahme Kontextmerkmale sind voneinander unabhängig

P(Kontext|Klasse) = ∏Merkmal Kontext P(Merkmal|Klasse)

Berechnung eines Modells Training aufgrund eines Tainingskorpus

P(Merkmal|Klasse) = Count(Merkmal,Klasse) / Count(Merkmal)

P(Klasse) = Count(Klasse) / Count(Klassen)

Automatische Klassifikation Disambiguierung aufgrund eines Modells

arg maxKlasse log(P(Klasse)) + ∑Merkmal Kontext log(P(Merkmal|Klasse))

vgl. Schütze/Manning 1999

Maximum Entropie ModelleMaximum Entropie Modelle• Grundlegendes

– Entropie: Anzahl der benötigten Bits zur Darstellung von Ereignissen eines bestimmten Typs (Münze werfen: 1 Bit, Würfeln: 2 ½ Bit).

– Prinzip der maximalen Entropie: Stecke nur die Information ins Modell, die sicher ist, d.h. beobachtet werden kann.

• Besonderheiten

– Dekompositon der Kontexte in einzelne Merkmale oder deren (Re)-Kombination.

– Möglichkeit der Kombination von Merkmalen aus heterogenen Quellen (Syntax, Semantik, Morphologie, …).

– Berechnung der Gewichte (Evidenz) einzelner Merkmale oder deren (Re-)Kombination für jede Klasse über alle Kontexte.

Maximum Entropie FrameworkMaximum Entropie Framework

( , )

1

( , )

1

1( | )

( )

( )

j

j

kf a b

jj

kf a b

ja A j

p a bZ b

Z b

Wobei j > 0 das Gewicht für Merkmal fj ist, k die Gesamtzahl der binären Merkmaleund Z(b) eine Normalisierungskonstante, die sicherstellt, dass a p(a|b) = 1 bzw. 100%

vgl. Ratnaparkhi 1998

Kontextuelle und binäre MerkmaleKontextuelle und binäre Merkmale

Die Gewichte für kontextuelle Merkmale werden in ME-Modellen über binäre Merkmale bestimmt. Diese setzen die kontextuellen Merkmale mit den Klassen in Beziehung.

– Einfache binäre Merkmale Beispiel

– Komplexe binäre Merkmale Beispiel

else 0

a'a and b cf if 1 baf acf ),(',

else 0

a'a and b cfs if 1 baf acfs ),(',

35

(art=def) 1( ,

f)

1 if b and af a b

0 else

17

art=def, poss=( , )

von f2 1 if b and af a b

0 else

Generalized Iterative ScalingGeneralized Iterative ScalingEs gibt kein analytisches Verfahren zur Bestimmung der Gewichte .

Es gibt mehrere iterative Näherungsverfahren zur Bestimmung der Gewichte , die zu einer ‚korrekten‘ Verteilung p(a|b) konvergieren und dabei das Prinzip der maximalen Entropie einhalten.

Wir verwenden Generalized Iterative Scaling (GIS):

0

1

1

1

n

j

Cp jn n

j jjp

E f

E f

ist der Erwartungswert für Merkmal fj im Trainingskorpus

ist der Erwartungswert für Merkmal fj in der letzten Iteration

Die Konstante C ist die Gesamtzahl der aktiven binären Merkmale über ‚alle‘ Kontexte

p jE f

n jpE f

Initialisierung

Iteration

Berechnung der ErwartungswerteBerechnung der Erwartungswerte

• Erwartungswert von fj im Trainingskorpus

• Erwartungswert von fj in der letzten Iteration

, 1

1( ) ( | ) ( , ) ( , )

N

p j j ja b i

E f p b p a b f a b f a bN

,

( , )

1

( ) ( | ) ( , )

1( | ) ( )

( )

n

j

nj jp

a A b

kf a bn n

jnj

E f p b p a b f a b

p a bZ b

wobei N die Anzahl der Kontexte im Trainingskorpus ist.Dieser Erwartungswert ist konstant über alle Iterationen.

Dieser Erwartungswert muss in jeder Iteration aufwändig neu berechnet werden

Berechnung der Konstanten Berechnung der Konstanten CC

1

( , ) for any ( , )k

jj

C f a b a b A B

Allgemein kann die Konstante C wie folgt berechnet werden:

wobei B die Potenzmenge der Kontextmerkmale ist. Diese Art der Berech-nung ist aber in den meisten Anwendungsszenarien nicht praktikabel. Insbesondere gilt: Je grösser der Wert der Konstanten C, desto zögerlicher die Konvergenz von GIS. Es gibt den Ausweg, C über die Kontexte des Trainingskopus zu berechnen:

,

1

max ,k

ja A b

j

C f a b

Dies erfordert das Hinzufügen eines Korrekturmerkmals fl, mit l = k+1:

1

, ,k

l jj

f a b C f a b

Was ist die maximale Anzahl, mit der ein binäres Merkmal in den Kontexten des Trainingskorpus aktiv sein kann?

Merkmale als BitvektorenMerkmale als Bitvektoren

Wir haben eine Implementierung des Maximum Entropie Frameworks in der Programmiersprache Prolog, bei der die kontextuellen, als auch die binären Merkmale als Bitvektoren dargestellt werden.

Jedem Kontextmerkmal entspricht eine Position im Vektor: cfi = 2i-1

Sei die Bitvektorrepräsentation von Merkmal fj und die Bitvektorrepräsentation von Kontext bi, dann gilt

Es ist damit sehr einfach und effizient festzustellen, ob ein Merkmal in einem Kontext aktiv ist, oder nicht.

2 2 2j j if f b

2jf 2

ib

BootstrappingBootstrapping

A5-ErweiterungACLF, Christof Rumpf,

10.01.2008

A5-ShortcomingsA5-Shortcomings

• Das ME-Verfahren in A5 ist supervised und setzt einen vollständig annotierten Trainingskorpus voraus.

• Die für manuelle Annotierungen vorgesehene Hilfskraft wurde nicht bewilligt.

• Die Annotierung von Begriffstypen ist eine sehr anspruchsvolle Aufgabe.

Lösung: BootstrappingLösung: Bootstrapping

• Unter Bootstrapping versteht man semi-supervised Lernverfahren, die teilweise aus annotierten und teilweise aus nicht annotierten Korpora lernen.

• In der CL sind am verbreitetsten:– Yarowski-Algoritmus (Yarowski 1995)– Co-Training (Blum & Mitchell 1998)

Yarowski-AlgorithmusYarowski-Algorithmus

• Besteht aus zwei Ebenen:– Inner Loop

• Berechnet für einen annotierten Trainingskorpus einen Klassifikator.

– Outer Loop• Benutzt den Klassifikator, um einen neuen Korpus zu

annotieren.• Der annotierte neue Korpus wird dem innneren Loop zur

Neuberechnung des Klassifikators übergeben.• Anschliessend wird wieder der innere Loop gestartet.

Yarowski-VariantenYarowski-Varianten

• Berechnung des Klassifikators im inneren Loop:– Naive Bayes– EM: Expectation Maximization– ME: Maximum Entropie (gibt es das schon?)

• Reestimation im äusseren Loop:– Sequentiell: ein Merkmal pro Iteration– Vollständig: alle Merkmale pro Iteration

Abney 2004Abney 2004

• Abney, Steven (2004): Understanding the Yarowski Algorithm. CL 30(3).

• Main Claims:– Der Yarowski-Algorithmus wird viel benutzt,

ist aber mathematisch unklar.– Er optimiert eine ‚objective function‘, bzw.

maximiert ‚negative log likelihood‘.

Abney 2004Abney 2004

Abney 2004Abney 2004

Architektur des Frameworks in A5Architektur des Frameworks in A5

( , )

1

1( | )

( )j

kf a b

jj

p a bZ b

Morphosyntaktische Analyse

Trainingskorpus

Trainingssample

Maximum-Entropie-Modell

msyn: Dependenz-grammatik-Parser

Extraktion relevanter Kontextmerkmale

Morphosyntaktische Analyse

Testkorpus

Testsample

manuelle Annotierung von Begriffstypen

Lernen

Anw

enden

Generalized Iterative Scaling

Annotierter Testkorpus

Klassifikatorlernen / anwenden

TrainingskorpusTrainingskorpus

• Handannotierte Version von Löbner (2003) Semantik• Zur Zeit sind lediglich die lexikalisch zugrundeliegenden

Klassen annotiert, nicht der Verwendungstyp (kommt noch…)

Die <f1>Semantik</f1> ist das <r2>Teilgebiet</r2> der <f2>Linguistik</f2>, das sich mit <r2>Bedeutung</r2> befasst. Diese <r2>Art</r2> von <f2>Definition</f2> mag vielleicht ihrem <r2>Freund</r2> genügen, der Sie zufällig mit diesem <so>Buch </so> in der <r2>Hand</r2> sieht und Sie fragt, was denn nun schon wieder sei, aber als <f2>Autor</f2> einer solchen <r2>Einführung</r2> muss ich natürlich präziser erklären, was der <f2>Gegenstand</f2> dieser <so>Wissenschaft</so> ist.

Trainingskororpa: ErfordernisseTrainingskororpa: Erfordernisse

• Wir brauchen mehrere intellektuelle Annotatoren.

• Wir brauchen Stylebooks zur Anleitung intellektueller Annotatoren.

• Es müssen Evaluationskriterien zur Ermittlung von Übereinstimmungen bzw. Abweichungen intellektueller Annotatoren ermittelt werden.

Morphosyntaktische AnalyseMorphosyntaktische Analyse<?xml version="1.0" encoding="iso-8859-1"?><!DOCTYPE analysis SYSTEM "http://www.connexor.com/dtds/4.0/fdg3.dtd"><analysis><sentence id="w1">

<token id="w2"> <text>Die</text> <lemma>die</lemma> <depend head="w3">det</depend> <tags><syntax>@PREMOD</syntax><morpho>DET Def FEM SG NOM</morpho></tags></token>

<token id="w3"> <text>Semantik</text> <lemma>semantik</lemma> <depend head="w4">subj</depend><tags><syntax>@NH</syntax> <morpho>N FEM SG NOM</morpho></tags></token>

<token id="w4"> <text>ist</text> <lemma>sein</lemma> <depend head="w1">main</depend><tags><syntax>@MAIN</syntax> <morpho>V IND PRES SG P3</morpho></tags></token>

<token id="w5"> <text>das</text> <lemma>das</lemma> <depend head="w6">det</depend>‘<tags><syntax>@PREMOD</syntax> <morpho>DET Def NEU SG NOM</morpho></tags></token>

<token id="w6"> <text>Teilgebiet</text> <lemma>teil#gebiet</lemma> <depend head="w4">comp</depend><tags><syntax>@NH</syntax> <morpho>N NEU SG NOM</morpho></tags></token>

<token id="w7"> <text>der</text> <lemma>die</lemma> <depend head="w8">det</depend><tags><syntax>@PREMOD</syntax> <morpho>DET Def FEM SG

GEN</morpho></tags></token>

<token id="w8"> <text>Linguistik</text> <lemma>linguistik</lemma> <depend head="w6">mod</depend><tags><syntax>@NH</syntax> <morpho>N FEM SG GEN</morpho></tags></token>

Dependenz-BaumDependenz-Baum

main - ist

subj - Semantik

det - DieDef

comp - Teilgebiet

det - dasDef

det - derDef

mod - LinguistikGen

Possessor

Die Semantik ist das Teilgebiet der Linguistik, …

TrainingssampleTrainingssampleExtraktion relevanter Kontextmerkmale über reguläre Ausdrücke mit Perl-

Skripten. Ergebnis:

t(f1, [tnr=2, tok=semantik, suff=ik, num=sg, art=def]).

t(r2, [tnr=5, tok=teil#gebiet, num=sg, art=def, poss=rgen]).

t(f1, [tnr=7, tok=linguistik, suff=ik, num=sg, art=def]).

t(f2, [tnr=12, tok=bedeutung, suff=ung, num=sg, art=none]).

t(r2, [tnr=16, tok=art, num=sg, art=indef, poss=von]).

t(f2, [tnr=18, tok=definition, num=sg, art=none]).

t(r2, [tnr=22, tok=freund, num=sg, art=def]).

t(so, [tnr=30, tok=buch, num=sg, art=indef]).

t(r2, [tnr=33, tok=hand, num=sg, art=def]).

t(f2, [tnr=49, tok=autor, num=sg, art=none]).

t(r2, [tnr=52, tok=einführung, suff=ung, num=sg, art=indef]).

t(f2, [tnr=61, tok=gegenstand, num=sg, art=def]).

t(so, [tnr=63, tok=wissenschaft, num=sg, poss=lgen, art=none]).

Erste experimentelle BefundeErste experimentelle Befunde

Input: Ein Trainingssample mit

645 TokensKlassen fe, f1, f2, so, r2, r323 verschiedene Kontexte mit Merkmalen

art={def, indef, none},poss={rgen, lgen, von}, suff={ik, ung, heit, keit, in, nis}

-Gewichte-Gewichte

J A BV Alpha CF 1 f1 128 101.16960 [suff=ik] 2 f1 4 0.46762 [art=none] 3 f1 1 2.83830 [art=def] 4 f2 2048 65.10268 [suff=ung] 5 f2 256 25.41862 [suff=in] 6 f2 128 0.89798 [suff=ik] 7 f2 32 3.84712 [poss=von] 8 f2 16 1.83738 [poss=rgen] 9 f2 8 47.40072 [poss=lgen]10 f2 4 1.23617 [art=none]11 f2 2 10.24894 [art=indef]12 f2 1 20.23730 [art=def]

J A BV Alpha CF13 fe 4 1.91720 [art=none]

14 r2 2048 15.73984 [suff=ung]15 r2 512 3.68845 [suff=keit]16 r2 128 1.85193 [suff=ik]17 r2 32 11.72706 [poss=von]18 r2 16 7.84761 [poss=rgen]19 r2 4 1.40162 [art=none]20 r2 2 62.60088 [art=indef]21 r2 1 4.73671 [art=def]

22 r3 2048 7.61280 [suff=ung]

23 so 4 30.77103 [art=none]

Klassifikatoren IKlassifikatoren I

(A|B) p~(A|B) p^100(A|B) B(f1| 1) 0.07692 0.09212 def(f2| 1) 0.73077 0.65679 def(fe| 1) 0.01923 0.03245 def(r2| 1) 0.15385 0.15373 def(r3| 1) 0.00000 0.03245 def(so| 1) 0.01923 0.03245 def

(f1| 2) 0.00000 0.01301 ind(f2| 2) 0.09091 0.13336 ind(fe| 2) 0.00000 0.01301 ind(r2| 2) 0.90909 0.81459 ind(r3| 2) 0.00000 0.01301 ind(so| 2) 0.00000 0.01301 ind

(f1| 4) 0.00826 0.01271 noa(f2| 4) 0.02204 0.03360 noa(fe| 4) 0.05234 0.05211 noa(r2| 4) 0.03306 0.03809 noa(r3| 4) 0.00000 0.02718 noa(so| 4) 0.88430 0.83631 noa

(A|B) p~(A|B) p^100(A|B) B(f1|66) 0.00000 0.01301 ind heit(f2|66) 0.00000 0.13336 ind heit(fe|66) 0.00000 0.01301 ind heit(r2|66) 1.00000 0.81459 ind heit(r3|66) 0.00000 0.01301 ind heit(so|66) 0.00000 0.01301 ind heit

(f1|68) 1.00000 0.01271 noa heit(f2|68) 0.00000 0.03360 noa heit(fe|68) 0.00000 0.05211 noa heit(r2|68) 0.00000 0.03809 noa heit(r3|68) 0.00000 0.02718 noa heit(so|68) 0.00000 0.83631 noa heit

(so, [art=none]) = 30.77103(f1, [art=none]) = 0.46762

-heit hat kein feature, weil es zu selten vorkommt

p~(A|B) ensteht durch Auszählen der Kontextep^100(A|B) ist der GIS-Klassifikator der 100sten Iteration

Klassifikatoren IIKlassifikatoren II(A|B) p~(A|B) p^100(A|B) B(f1|2060) 0.00000 0.00012 noa lgen ung(f2|2060) 1.00000 0.98380 noa lgen ung(fe|2060) 0.00000 0.00049 noa lgen ung(r2|2060) 0.00000 0.00569 noa lgen ung(r3|2060) 0.00000 0.00196 noa lgen ung(so|2060) 0.00000 0.00794 noa lgen ung

(f1|2065) 0.00000 0.00094 def rgen ung(f2|2065) 0.75000 0.80203 def rgen ung(fe|2065) 0.00000 0.00033 def rgen ung(r2|2065) 0.25000 0.19384 def rgen ung(r3|2065) 0.00000 0.00252 def rgen ung(so|2065) 0.00000 0.00033 def rgen ung

(f1|2081) 0.00000 0.00048 def von ung(f2|2081) 0.85000 0.85110 def von ung(fe|2081) 0.00000 0.00017 def von ung(r2|2081) 0.15000 0.14681 def von ung(r3|2081) 0.00000 0.00128 def von ung(so|2081) 0.00000 0.00017 def von ung

(f1|2084) 0.00000 0.00077 noa von ung(f2|2084) 1.00000 0.50831 noa von ung(fe|2084) 0.00000 0.00315 noa von ung(r2|2084) 0.00000 0.42475 noa von ung(r3|2084) 0.00000 0.01250 noa von ung(so|2084) 0.00000 0.05052 noa von ung

Alle Kontexte der Länge 3:

Fazit und AusblickFazit und Ausblick• Das Maximum Entropie Framework erlaubt eine feine Analyse der

Evidenz, die ein einzelnes Kontextmerkmal für die Klassifikation liefert.

• Die Auswahl der richtigen Merkmale ist essentiell für den Erfolg der automatischen Klassifikation. Unser Forschungsgegenstand besteht in erster Linie in der Untersuchung dieser Merkmale.

• Es werden Experimente mit kombinierten Merkmalen folgen, um die kombinierte Evidenz zu modellieren.

• Unerlässlich ist natürlich auch die Existenz von handannotierten Trainingskorpora, in denen die Verwendungstypen vermerkt sind, die wir leider noch nicht haben.