+ Named Entity Recognition

Named Entity Recognition and Classification (NER)

Inhalt

• Worum geht es
  • Einleitung
  • Definition und Abgrenzung
  • NER bei der MUC6
• Wo liegen die Probleme
  • Beispiele für Probleme bei der NER
• Welche Methoden werden benutzt
  • List-Lookups
  • Regelbasierte Systeme
  • Hidden Markov Modells
  • Maximum Entropy Modells
  • Lernende Systeme
• Beispiele
  • GaTe
  • Nymble
  • Beispiele im Web

Worum geht es?

Bei der Information Extraction ist es von grosser Bedeutung, Wörter und Wortfolgen im Text zu identifizieren, die Eigennamen bezeichnen. Viele IE-Tasks benötigen nämlich die Erkennung von Personen- oder Ortsnamen, um Kontexte im Dokument herzustellen und schließlich die gesuchte Information zu finden. Aber auch ausserhalb der reinen IE wird die NER benutzt. Beispielsweise bei der automatischen Übersetzung, der automatischen Erstellung von Textzusammenfassungen und der Dokumentenklassifikation (nach Autor, Titel, etc)

Die IE-Basiskomponente "Named Entity Recognition and Classification" soll eben dieses leisten: Die Erkennung Eigennamen in Textdokumenten und die Klassifikation in u.A. Personen, Orte, Firmen und ggf. anwendungsspezifische NE-Klassen (Datum, Medikamentennamen, etc). Die NE soll aber nicht Aufgaben wie etwa Koreferenzauflösung oder Relationserkennung wahrnehmen. Dazu werden andere Systeme eingesetzt.

Bei der MUC6, der ersten MUC, welche die NER als Tasks definierte, wurde von den Systemen gefordert, im Textkorpus Personen, Orte, Organisationen, Datums- und Zeitangaben sowie Numerale (Währungsgrössen und Prozentangaben) zu erkennen.

Wo liegen die Probleme bei der NER?

Das größte Problem, das NE-Systeme bewältigen müssen, ist die Auflösung von Zweideutigkeiten. Zum einen bezeichnen viele Wörter nicht nur Eigennamen sondern auch allgemeine Wörter (Beispiel: "Schuhmacher" Eigenname vs allgemeines Substantiv, Beruf). Zum anderen gibt es Zweideutigkeiten bei der Zuordnung in eine NE-Klasse (Beispiel: "Phillip Morris" Person vs Organisation) oder in eine Subklasse (Beispiel: "Meier, M." vs "M. Meier" Was ist hier Vor- und Nachname?). Weitere Hürden für ein NE-System sind die Klassifikation unbekannter Wörter und der Umgang mit Texteigenheiten, d.h. Textformatierung (eMail vs. Roman), Rechtschreibung und Interpunktion (eMail vs. wissenschaftliche Abhandlung) sowie domäneneigenen Formulierungen, zb starker Gebrauch von Abkürzungen und Fachworten (medizinische Dokumente).

Welche Methoden gibt es?

NE-Systeme sind stets modular aufgebaut. Als erstes wird der Text an einen Tokenizer gegeben, danach oder auch parallel wir ein Gazetteer geschaltet, der den Text mit einer Datenbank vergleicht, welche Eigennamen enthält und anschliessend kommt ein Modul, welches die Klassifikation der NEs vornimmt.

Das *List-Lookup*-Modul, auch Gazetteer genannt, vergleicht den Text mit einer vorgefertigten Liste, welche eine Reihe von Eigennamen enthält und taggt dann das Wort/Token entsprechend.

Vorteile:

• Listen sind sprachunabhängig. Deutsche Namen werden in englischen Texten erkannt
• Ein Gazetteer ist schnell und einfach in ein System implementiert
• Das NE-System kann durch einen Wechsel der Datenbank schnell an eine neue Domäne angepasst werden

Nachteile:

• Die Listen müssen aufwendig und langwirig meist von Hand erstellt werden
• Ein Gazetteer kann Zweideutigkeiten nicht auflösen
• Listen sind niemals vollständig

Regelbasierte Systeme: Jede Sprache hat gewisse Regeln, nach welchen Eigennamen gebraucht werden. Ein NE-System kann diese Regeln rückwärts anwenden und daraus ableiten, ob und welcher NE-Klasse ein unbekanntes Wort angehört. Beispiele:

• TITEL %$ \in $% {Dr.; Professor, Dozent, ...}
• KEYWORD %$ \in $% {Firma, Unternehmen, AG, Gesellschaft...}
• UC = Wort mit einem Grossbuchstaben am Anfang
• LN = Nachname
• FN = Vorname
• LOC = Ortsname
• ORG = Organisation

Mit diesen Bezeichnungen gelten etwa folgende Regeln:

TITEL + UC + LN => UC = FN: Dr. Hans Müller => Hans ist ein Vorname

KEYWORD + UC + LOC => UC = ORG: Das Unternehmen Müller in Hamburg => Müller bezeichnet eine Firma

Vorteile regelbasierter Systeme:

• Können mit einem angepassten Regelsatz eine hohe Performance erreichen
• Sind sehr robust im Umgang mit domänenfremden Worten, da deren Einbindung in Sätze meist den gleichen Regeln unterliegt

Nachteile

• Die Regeln müssen von Hand erstellt werden, was meist viele Mannstunden an Arbeit kostet
• Regeln sind immer abhängig von der Sprache des Korpus, der Domänen und auch dem Textformat

Stochastische Methoden werden zur hauptsächlich zur Klassifikation von NEs eingesetzt. Die zwei Wichtigsten sind das Hidden Markov Model (siehe HiddenMarkovModels und hmm.pdf für Papers) und das Maximum Entropy Model

(hier folgt hoffentlich noch ein Link auf den HMM.Vortrag aus dem Seminarprogramm)

Das Maximum Entropy Model versucht eine Wahrscheinlichkeitsverteilung aller möglichen NE-Klassen für ein Wort zu erstellen. Dabei werden die vergangenen x Tokens, welche bereits klassifiziert sind, und die folgenden x Tokens zur Erstellung herangezogen. Die Verteilung wird dann über der sog- History eines Tokens, das sind die x vorhergehenden Tokens, und die Menge aller möglichen Tags für das aktuelle Token erstellt. zur dieser Verteilung gibt es eine Formel, welche die Entropie der Verteilung beschreibt. Diese Entropie versucht man im Trainingslauf zu maximieren. Mehr mathematische Details gibt es hier

Vorteile stochastischer Systeme:

• Das notwendige Training läuft größtenteils Automatisch ab. Der User benötigt keine tiefgreifenden NLP-Kenntnisse um das System richtig zu trainieren
• Stochastische Systeme lassen sich leicht an neue Domänen und Sprachen anpassen, in dem sie einfach neu trainiert werden

Nachteile

• Das Training musst überwacht werden, damit sichergestellt wird, dass die Modellparameter in den richtigen Bereichen liegen.
• Die Performance des Systems hängt stark von Qualität und Umfang des Trainings ab.

Komplette NE-Systeme sind zumeist lernende Systeme, die sowohl ein Gazetteer-Modul als auch ein Klassifizierungsmodul (regelbasiert oder stochastisch) enthalten. Der Lerneffekt wird durch sukzesiven Aufbau der Gazetteerdatenbank erreicht: Das System hat nach dem ersten Durchlauf einige unbekannte, d.h. nicht in der Datenbank enthaltene, Wörter mithilfe des Klassifikationsmoduls erkannt und klassifiziert und fügt diese dann der Datenbank zu. Dann wird ein neuer Durchlauf gestartet, in dem nun eine grössere Datenbank zur Verfügung steht und somit möglicherweise wieder unbekannte Wörter klassifiziert werden.

NE-Systeme

Noch kurz zu zwei NE-Systemen, zum einem Muse, der Multi-Source Entity Finder des GaTe Systems. Muse ist ein regelbasiertes System und kann viele Dokumentenformate verarbeiten. Und zum anderen noch Nymble, ein Produkt der BBN-Corporation, Cambridge, welches auf dem HMM-Model basiert.

Papers

• Maximum Entropy Model
• Hidden Markov Model
• Das Nymble-System

-- MartinGoller - 07 Jul 2003