20.06.01Maschinelle Lernverfahren für IE und TM 1 Topic Detection

20.06.01 Maschinelle Lernverfahren für IE und TM

1

Topic DetectionTopic Detection


2

Inhalt• Motivation• Begriffe• Aufgaben

– Segmentierung– First Story Detection– Topic Detection – Topic Tracking– Story Link Detection

• Verbesserungen• Zusammenfassung• Referenzen


3

Motivation• immer mehr Informationen immer schneller verfügbar, Aktualität

oft entscheidend• Ziele:

– automatische Klassifizierung von Dokumenten– neue Themen entdecken / verfolgen (Text-Mining)

• bisherige IR-Methoden reichen nicht aus:– Keyword-Suche vs. generische Queries

• “was ist passiert?”

– Abstraktions-Level: “Asienkrise”

– zeitliche Dimension: • “was ist neu?”, “wie entwickelt sich ein Thema?”


4

Anwendungen

• Journalismus• Börsen- und Finanzmarkt-Analyse• Konsum-Marktforschung• Politik, Krisen-Erkennung• private Information und

Unterhaltung• Suchmaschinen

• verbesserte

Übersetzung


5

Begriffe• event: "A reported occurrence at a specific time and place, and

the unavoidable consequences. Specific elections, accidents, crimes, natural disasters.”

• activity: "A connected set of actions that have a common focus or purpose - campaigns, investigations, disaster relief efforts."

• topic: "A seminal event or activity, plus all derivative (directly related) facts, events or activities."

• story: "A topically cohesive segment of news that includes two or more declarative independent clauses about a single event."


6

Beispiele

• Hurricane Mitch (Sep./Oct.’98)– On topic: coverage of the disaster itself; estimates of damage and reports of

loss of life; relief efforts by aid organizations; impact of the hurricane on the economies of the effected countries.

• Thai Airbus Crash (11.12.98)– On topic: stories reporting details of the crash, injuries and deaths; reports on

the investigation following the crash; policy changes due to the crash (new runway lights were installed at airports).

• Euro Introduced (1.1.1999)– On topic: stories about the preparation for the common currency

(negotiations about exchange rates and financial standards to be shared among the member nations); official introduction of the Euro; economic details of the shared currency; reactions within the EU and around the world.


7

TDT2000 - Corpus• TDT3:

– 45k Stories, Okt.-Dez. 1998– Englisch (CNN, ABC, NBC,...), Mandarin (VOA, XIN, ZBN)– News-Stories aus Radio / TV / Agenturen– Texte und Audio / ASR-Daten, chronologisch geordnet– 60 markierte Topics– Trainings-Corpus pro Topic: “yes”, “no”, “brief”(<10%

relevant)

• TDT2000:– 60 weitere Topics


8

TDT2000 - Aufgaben


9

SegmentationHMM (Mitre) [1]

• baue HMM aus Trainings-Stories:– 250 Knoten: entsprechen ersten 250 Worten einer Story

– pro Knoten: Wahrscheinlichkeits-Verteilung über Feature-Value- Kombinationen, z.B. P(F1=v2)=0.5

• Segmentation:– lese Wort w und bestimme Werte aller Features

– bestimme wahrscheinlichsten Übergang zu nächstem Knoten

– falls danach in Knoten 1: “boundary”

...250 states


10

SegmentationHMM (Mitre) [1]

Features: X-duration, Coherence, Trigger• X-duration:

– Dauer der “non-speech”-Phase (ASR-Skript: “X”) vor w

– 0, falls nicht existent

• Coherence-1, 2, 3, 4:– (erstes...) Fenster von 50 Worten vor w

– 0, falls w nicht vorkommt, sonst

– allgemein: Worte wiederholen sich vermutlich innerhalb einer Story

– z.B. P(coh-2=0): max. für w1-50, weil Fenster ganz in vorheriger Story, kleiner für w50-100, am kleinsten ab w100

sw: # Stories mit w s: # Stories insgesamt

s

swlog


11

SegmentationHMM (Mitres) [1]

• Trigger:– Region R: erstes, zweites, letztes, vorletztes Wort

# Vorkommen von w insgesamt

# Vorkommen von w in R

Anteil Tokens von w, die in R vorkommen

– Feature-Wert für w und R groß, wenn:• w oft in R vorkommt (Trainings-Corpus)• viele Tokens von w in R vorkommen• w insgesamt selten ist

– z.B. P(“hi”=“erstes Wort”) relativ groß

)/1(

1)(

Rw

Rw

fn

nRwP

Rwn

Rf

wn


12

Segmentation - Ergebnisse


13

First Story Detection• bestimme Ähnlickeit der aktuellen Story mit “Vergangenheit”• Story ist NEW, falls Ähnlichkeit “gering”, sonst OLD

Vektorraum-Modell: – repräsentiere Stories als Query-Vektoren

– Stemming, Stopwort-Elimination, Termgewichtung

Varianten:– Termgewichte (“raw” tf, tf*idf, ...)

– Ähnlickeits-Maße (Cosinus, gewichtete Summe, ...)

– Grenzwerte für NEW/OLD

– Menge der Vergleichs-Stories (Zeit-Ausschnitt)


14

First Story DetectionSingle-Pass Clustering (Umass) [2]

• für aktuelle Story S mit Term-Vektor d:– bilde Query q aus N gewichteten Features von S

– bestimme Basis-Schwellwert x = sim(q,S)

– vergleiche Queries bisheriger Stories mit S

– falls dabei x + “Zeitstrafe” überschritten wird OLD(S), sonst NEW(S)

– optional, OLD: “Cluster”-Bildung (assoziiere S mit “Trigger-Query”)

N

i i

N

i ii

qw

dqbeliefqwdqsim

1

1

)(

),()(),(

iii idftfdqbelief 6.04.0),(


15

FSD - Ergebnisse

Umass [2], CMU [3]: Single-Pass Clustering

Dragon [5]: Language Model


16

Topic Detection• repräsentiere Topics als Cluster bereits betrachteter Stories

• Single-Pass Clustering: (IBM [10], CMU [3], Dragon [5])für aktuelle Story S...

– bestimme ähnlichsten Cluster C

– falls Ähnlichkeit “groß” ist addiere S zu C, sonst bilde neuen Cluster (FSD: markiere S als NEW)

• kNN, Nearest Neighbour: (Umass [4])– vergleiche S direkt mit bisherigen Stories (Zeitfenster)

– betrachte k ähnlichste Stories und deren Topics

– Topic (Cluster) von S durch “einfache Mehrheit”


17

Topic DetectionSingle-Pass Clustering (CMU) [9]

• clustering (Tc) und novelty threshold (Tn), Tn<=Tc, context W• aktuelle Story x:

OLD(x), x in ähnlichsten Cluster aus W

OLD(x), neuer Cluster

NEW(x), neuer Cluster

• FSD: Tc=unendlich (kein Clustering)• TD: Tc=Tn (Tn nicht berücksichtigen)

)},({max1)( icxsimw

ixscore

Wic

)(1)(max xscorexsim

cTxsim )(max

nc TxsimT )(max

)(max xsimTn


18

Topic DetectionSingle-Pass Clustering, Language Model - Dragon [5]

bestimme Wort-Verteilung für jeden Cluster C (Wahrscheinlichkeit, daß ein Wort w in C vorkommt)

• für aktuelle Story S ähnlichsten Cluster:

• N=Länge von S, pc(w)=Prob(w) in Cluster, pb(w)=Prob(w) in Background-Modell, t=“Zeitstrafe”

• sim groß, wenn:– Terme in S kommen oft in C und selten in Background vor

– Stories in C sind “neu”

N

iibic twpwpCSsim

1

)(log)(log),(


19

Topic Detection - Ergebnisse

CMU [3], Dragon [5]: Single-Pass Clustering, Umass [4]: kNN


20

Topic Tracking• gegeben Trainings-Corpus für Topic T, Frage S “on topic”?

• kNN: (CMU [6])– bestimme kNN von aktueller Story S aus Trainings-Corpus

– falls davon mehr mit “yes”, als mit “no” markiert sind YES, sonst NO

• Decision Trees: (CMU [6])– baue je einen Decision Tree pro Topic T

– repräsentiere Trainings-Stories für T (markiert mit "yes", "no") als Queries

– Knoten-Labels sind Aussagen über Term-Gewichte qi

– maximiere Informationsgewinn, "Reinheit" der Unterbäume

– Ziel: pro Blatt nur "yes"/"no"-Queries

– Kosten: ca. 2 Min für 25 Topics / DTs mit je 15.000 Trainings-Stories


21

Topic TrackingkNN-Algorithmus (CMU) [6]

• Parameter: k>0 und 0<k1<k, 0<k2<k• für aktuelle Story S bestimme... • K(k’,m) := Menge der k’ zu S ähnlichsten Stories aus Trainings-

Corpus mit Markierung m• P(S,k1) := K(k1,m), m=“yes”/“brief”• N(S,k2) := K(k2,m), m=“no”• Wahrscheinlichkeit, daß S bzgl. des geg. Topics relevant ist:

• Gesamtzahl pos. Trainings-Beispiele pro Event (<=16), z.B. k=5

),cos(2

1),cos(

1

1)|(

)1,( )2,(

ksPd ksNdsd

ksd

ksyesP

20.06.01 22

Mandarin Audio

Term Translation

President Bill Clinton and…

English Story

Term Selection

Bilingual

TermList

Query Construction

IR-System

StoryBoundaries

ScoreNormalization

DocumentConstruction

SpeechRecognition

RankedList of TS

Score

IDFComputation

MandarinTrainingStories

n-word units

(weighted) top-N translations

Topic TrackingUMD [7]


23

Topic Tracking - Ergebnisse(CMU) [6]


24

Story Link Detectiontf*idf, LCA (Umass) [4]

• Cosinus-Ähnlichkeit mit Gewichten tf*idf, threshold 0.8• Problem:

– meist relativ kurze Stories, kleine gemeinsame Term-Menge, Synonyme

• Local Context Analysis (LCA) “smoothing”:– nehme Top-n Terme aus Story-Vektor für Query

– Query Q gegen Rest-Corpus (zeitlich davor)

– extrahiere alle Terme aus Menge ähnlicher Stories

– gewichte jeden Term t basierend auf...• Gewicht von t in Q• räumlicher Distanz von t zu anderen Termen aus Q und• deren Gewicht in Q

– bilde neuen Dokument-Vektor aus Q und Top-n der LCA-Expansion


25

Story Link Detection


26

Verbesserungenbereits getestet:• verschiedene Termgewichte, Ähnlichkeitsmaße (Vektorraum)• Verwendung von Named Entities

weitere Möglichkeiten:• Ausnutzung von...

– Text-Struktur (z.B. erster / letzter Satz)

– Einfluß von Topic auf Art der Terme: wo vs. wer (NE’s), Verben

• NLP: “Schlüsselsätze” finden• prob. Vorhersagen auf Basis von zeitlicher Topic-Entwicklung

– Verbrechen -> Untersuchung -> Prozess


27

Named EntitiesTracking (Univ.Iowa) [8]

• zusätzlich zu Term-Vektor: NE-Vektoren– Personen, Organisationen, Orte, Events, MeSH (Medical Subject

Headings)

• gewichtet nach Vektor-Länge und Häufigkeit der vork. Terme• separate NER in Mandarin vor Übersetzung

• vergleiche S mit Trainings-Stories:– für jedes Paar von NE-Vektoren bestimme Cos-Ähnlichkeit

– bilde gewichtete Summe: sim(s1,s2) = 0.3*sim(per) + 0.3*sim(org) + 0.2*sim(loc) + 0.1*sim(event) +

0.1*sim(mesh)


28

Named EntitiesFSD / Tracking

•


29

Named Entities - Probleme

• Abhängigkeit von Qualität der NER• nicht robust gegenüber Qualität der ASR (>20% Fehler):

– Groß- und Kleinschreibung

– unterschiedliche Schreibweisen

• Anzahl der vorkommenden NE’s in gesuchten Stories • Zuordnung von NE’s zu Topics

– NE’s in mehreren Topics (z.B. Politiker)

– gleiche Namen für verschiedene NE’s

– manche Topics nicht durch spezifische NE’s charakterisiert

– NE’s nicht Topic-relevant (z.B. Reporter)


30

Zusammenfassung• Topic-Definition ergeignisbasiert

• Hauptaufgaben: – Topic Detection

– First Story Detection

– Tracking

• Voraussetzungen: ASR, Übersetzung, Segmentierung, SLD

• viel Raum für Verbesserungen und Forschung– reines Vektorraum-Modell in Effizienz begrenzt

– Kombination mit NER / NLP?


31

Referenzen

• [1] Mitre TDT2000 Segmentation System, Greiff, Morgan, Fish, (Mitre Corporation, 2000)

• [2] Online New Event Detection using Single-Pass Clustering, Papka, Allan (University of Massachusetts, 1997)

• [3] A study on Retrospective and On-Line Event Detection, Yang, Pierce, Carbonell (Carnegie Mellon University, 1998)

• [4] Umass at TDT2000, Allan, Lavrenko, Frey, Khandelwal (Umass, 2000)

• [5] Statistical Models for Tracking and Detection, (Dragon Systems, 1999)

• [6] Learning Approaches for Detecting and Tracking News Events, Yang, Carbonell, Brown (CMU, 1999)

• [7] Translingual Topic Tracking: Applying Lessons from the MEI Project, Levow, Oard, (University of Maryland, 2000)


32

Referenzen

• [8] Entity Based Tracking, Eichmann (University Iowa, 2000)

• [9] A study on Retrospective and On-Line Event Detection, Yang, Pierce, Carbonell (CMU, 1998)

• [10] Story Segmentation and Topic Detection in the Broadcast News Domain, Dharanipragada, Franz, Carley (IBM, 1998)


33

Beispiele

• Pinochet Trial (16.10.98)– On topic: stories covering any angle of the legal process surrounding this trial

(including Pinochet's initial arrest in October, his appeals, British Court rulings, reactions of world leaders and Chilean citizens to the trial, etc.).


34

SegmentationDecision Trees (IBM) [1]

• System: – sprachl. Vorverarbeitung (Satzerkennung, Stemmer) -> Feature

Extraction -> DT -> Refinement (Vergleich adjazenter Segmente)

• Eingabe für Decision Tree: – je eine NSP im ASR-Skript, endlich viele Sätze davor und danach

• Features, erlernte Indikatoren für Segment-Grenzen: – Dauer der NSP

– Vorkommen von Worten/Paaren (Distanz von Story-Grenzen)

– Menge der Nomen im Vor- und Nachfeld

• Refinement: Vergleich adjazenter Segmente (false alarms)


35

Termgewichte

• df(i) = Anzahl (bisheriger) Dokumente mit Term ti• idf(i) = N / df(i), N = Anzahl aller (bisherigen) Dokumente• tf(ij) = Anzahl Vorkommen von ti in Dokument dj

• tf*idf:

• adaptive idf, Zeitpunkt p: )(log2p

pip

df

Nidf

ikjk

ijij

df

N

tf

tfw log

max


36

Dokument-Ähnlichkeit

• Cosinus-Ähnlichkeit:

• gewichtete Summe:

i

ii

q

dq

22ii

ii

dq

dq


37

First Story DetectionSingle-Pass Clustering (Umass) [2]

• für aktuelle Story S mit Term-Vektor d:– bilde Query q aus N gewichteten Features von S

– bestimme Basis-Schwellwert x = sim(q,S)

– vergleiche Queries bisheriger Stories mit S

– falls dabei x + “Zeitstrafe” überschritten wird OLD(S), sonst NEW(S)

– optional, OLD: “Cluster”-Bildung (assoziiere S mit “Trigger-Query”)

• t = Häufigkeit von qi in d

N

i i

N

i ii

qw

dqbeliefqwdqsim

1

1

)(

),()(),( iii idftfdqbelief 6.04.0),(

))(

5.15.0/(davg

dtttf i

)1log(

)5.0

log(

cdf

c

idf ii


38

FSD - Ergebnisse


39

Topic Tracking

• Single-Pass Clustering: – nur zwei Cluster: Yes und No (initialisiert mit entsprechenden

Dokumenten aus T)

– bestimme Ähnlichkeit von S mit Yes und No

– füge S zu ähnlichstem Cluster hinzu

Documents

20.06.01Maschinelle Lernverfahren für IE und TM 1 Topic Detection