PG 520
Intelligence Service
Gezielte Suche im Internet
Forschung
Praxis
Lehrstuhl für künstliche Intelligenz
Informationen im Internet
• Suchmaschinen:
– Es werden nur Dokumente geliefert, die den
Suchbegriff enthalten.
– Die Seiten sind von sehr unterschiedlicher
Qualität.
– Vorwissen über zuverlässige Seiten und ihre
Struktur wird nicht ausgenutzt.
Intelligence Service
• Zusammenhänge zwischen Dokumenten:
– Firmen wollen ihre Konkurrenz beobachten.
– Anleger wollen eine Entwicklung verfolgen.
– Bürger wollen wissen, wie es zu einer
Entscheidung in der Politik kam.
• Direkte Fragebeantwortung:
– Innerhalb des Dokuments muss die betreffende
Textstelle gefunden werden! Forschungsthema
Named Entity Recognition!
16.Wahlperiode, Drucksache, Antrag
Drs-Nr.
Typ
Fraktion
16.Wahlperiode, Drucksache, Antrag
Drs-Nr.
Typ
Person
16.Wahlperiode, 57. Sitzung, 19.10.2006, TOP 5
16/2790
16/267
Direkte Fragebeantwortung
• Der Antrag der FDP zur Entsorgung radioaktiven
Abfalls wurde abgelehnt.
• Der Antrag der Grünen zur ergebnisoffenen
Standortwahl für Endlagerung radioaktiven Mülls
wurde an Ausschüsse verwiesen.
Für diese Antworten braucht man manuell 7
Stunden
PG-Arbeit
• Gezielte Recherche gemäß der Struktur
bestimmter Webserver (Suchanfragen)
• Indexierung gemäß bestimmter Entitäten:
Themen, Personen, Orte, Firmen...
• Named Entity Recognition:
– Einige Dokumente nach Entitäten annotieren,
– maschinell Annotationsregeln lernen
– Annotationsregeln anwenden
• Informationen zu den Entitäten
zusammenstellen
Named Entity Recognition
• Ursprung Message Understanding Contest
– Fragebeantwortung
– Dann: Markierung der Entitäten
• Traditionelle NE: Personen, Orte, Firmen
Tom arbeitet bei Mercedes Benz
PER
O
O
ORG
ORG
• Intelligence Service: Personen, Orte,
Firmen, Datum, DrucksachenNr.,
Fraktionen, etc.
Probleme
• Alle möglichen NEs in Listen zu sammeln
ist keine perfekte Lösung bzw. nicht immer
möglich
• Beide Arten der Evidenz beachten:
– interne – Merkmale des Wortes an sich
– externe – Merkmale des das Wort
umgebenden Kontextes
• Tom arbeitet bei Mercedes Benz
• intern/ extern
Beispiele für interne/externe Evidenz
• Intern:
– Das Wort enthält Sonderzeichen (reg. Ex.)
– Das Wort ist ‘Hans’
– Das Wort enthält das 3-gram ‘ans’
• Extern:
– Vor dem Wort steht das Wort ‘Herr’
– Das Wort steht am Satzanfang
– Das Wort vor dem Wort hat die Markierung
PERSON
NER-Verfahren
• Regelbasierte Verfahren
– kontextfreie Grammatiken
– endliche Automaten
• Verfahren des ML
– Transformationsbasiertes Regellernen
– SVM
– Graphenbasiert: HMM -> MEMM -> CRF
Support Vector Machines
• Bilden bestseparierende Hyperebene
• Lösen somit binäres Klassifikationsproblem
• Können viele und hochdimensionale
Daten verarbeiten
• Sind robust gegenüber overfitting
• Für NER ist aufgrund mehrerer NEs ein
Verbund aus SVMs nötig
Hidden Markov Models
• Hidden Markov Model (HMM)
– Generatives (gerichtetes) Modell
Y1
Y2
Y3
Labelsequenz Y
Beobachtungssequenz X
T
 
p( x , y )   p( yi | yi 1 ) p( xi | yi )
X1
X2
i 1
X3
 
ˆ
p( x , y )

y  arg maxy

p( x )
Maximum Entropy Markov Models
• Maximum Entropy Markov Model
(MEMM)
– Bedingtes (gerichtetes) Modell
Y0
Y1
Y2
Y3
Labelsequenz Y
X1
X2
X3
Beobachtungssequenz X
– Label hängt vom Vorgänger und
Beobachtung ab
Conditional Random Fields
• Conditional Random Fields (CRF)
– Bedingtes ungerichtetes Modell
Y1
Y2
X
Y3
Labelsequenz Y
Beobachtungssequenz X
– Labelsequenz hängt von Beobachtungssequenz ab
– Beste Labelsequenz erfüllt die meisten
features für Beobachtungssequenz
Anwendung von NER-Verfahren
• YALE als grundlegende Lernumgebung
• Fast alle Lernverfahren vorhanden
– u.a. auch SVM
• Problem: NER-Umgebung noch in der
Entwicklung begriffen!
– Ausgereift: statistische Textanalyse
– Statistische Textanalyse beachtet nicht den
sequentiellen Charakter des Textes
– CRF-Plugin liefert erste Grundlagen für NER
Statistische Textanalyse vs. NER
• Statistische Verfahren analysieren
Wortvorkommen sowie ihre Anzahl
• Text wird in ‘bag of words’ zerlegt
– or; is; has; …; politician; …; nuclear; …
– Dient zur Klassifikation von Texten
• NER benötigt Texte in ursprünglicher Form
– mit zusätzlichen Informationen
– Preprocessing liefert diese Informationen
Aktuell in YALE vorhanden
• CRF-Plugin bietet Preprocessing mit
unterschiedlichen Merkmalen
– Präfix, Suffix, NGramme, Reguläre Ausdrücke, …
• Außerdem:
– CRF-Model-Learner
– CRF-Model-Applier
• Ziel:
– modulare, allgemeinnutzbare PreprocessingOperatoren
– Möglichkeit zur Einbindung vieler Lernverfahren
– Einsatz von evolutionären Algorithmen zum Lernen
des besten Experiment-Setups für versch. NER-tasks
Rahmenterminplan 1. Semester
• 1. Seminarphase 08. – 12.10.2007
• Lernverfahren
–
–
–
–
SVM
MEMM
HMM
CRF
• Methoden der Personalisierung von Suchmaschinen
• Basistechniken des WWW
– Indexierung
– XML (RSS)
• Werkzeuge der PG
–
–
–
–
Yale
Google API
CVS
Crawling
Rahmenterminplan 1. Semester
• Aufgaben des ersten Semesters
– Wahl eines Anwendungsszenarios, Festlegen
der Fragen und der NE
– Erstellung eines Anfrageplans
– Erstellen der Trainingsdatensätze
– Experimente mit vorhandenen NER-Verfahren
– Ansätze zur Verbesserung der NER
• 2. Seminarphase 04. – 08.02.2008
– Zusammentragen der Ergebnisse
Rahmenterminplan 2. Semester
• 3. Seminarphase Anfang April 2008
•
•
•
•
•
•
automatische Thesaurus-Erstellung
automatische Fragebeantwortung
Text-Clustering
Webseiten-Ranking
First-Story Detection
Topic Tracking
• u. U. noch andere Themen möglich!
Rahmenterminplan 2. Semester
• Aufgaben des zweiten Semesters
– Sammeln der Daten (Anfrageplan beachten)
– Konkrete Ausnutzung der NER aus erstem
Semester
– Verbesserung der NER (?)
• Ende des zweiten Semesters:
– PG Abschlussbericht und -präsentation

PG Intelligence Service