Lexikon

Informationsextraktion

Der überwiegende Teil der heutzutage verfügbaren Information ist nur in Texten und anderen unstrukturierten Medien enthalten und daher nicht direkt durch Rechner interpretierbar. Dieses schwer zugängliche Wissen ist jedoch für viele analytische Prozesse wichtig. Informationsextraktion (IE) setzt hier an: Sie befasst sich mit der Extraktion vordefinierterTypen von Informationen wie Entitäten oder Relationen aus maschinenlesbaren Dokumenten. IE grenzt sich von Information Retrieval ab, das sich auf das Finden von Dokumenten für bestimmte Suchanfragen konzentriert. Als Schnittstelle zwischen unstrukturierten und strukturierten Daten ist IE eine Schlüsseltechnologie für zahlreiche moderne Informationsverarbeitungssysteme.

In den letzten Jahren wurden dramatische Fortschrittein diesem Bereich erzielt, die ihren Ausdruck u. a. in dem Erfolg desWatson Programms von IBM fanden, das in einer anspruchsvollen amerikanischen Quizshow mit Freitextfragen gegen die besten menschlichen Gegner überzeugend gewann [6]. Zielder IE ist meist das Füllen von Datenbanken mit extrahierten Informationen, die dann zur weiteren Verarbeitung wie z. B. zum TextMining [8], für das SemanticWeb, Meinungsforschung, Textzusammenfassung und vieles andere mehr zur Verfügungstehen. Mögliche Anwendungsgebiete sind daher breit gestreut, wie z. B. die Auswertung von medizinischen Befundberichten und Arztbriefen für die Evidence-based Medicine, die Bearbeitung von textuellen Kundenanfragen und -problemen im Service Support, die Analyse von Dokumenten in finanziellen, juristischen, firmenbezogenen, sicherheitsrelevanten Bereichen oder die Extraktion von formalem Wissen aus Büchern. Der Begriff Open-Domain IE [11] bezieht sich auf die Identifikationallgemeinerer Informationen und vorher unbekannter Relationstypen aus großen Datenmengen, wie beispielsweise dem Web.

Wichtige Teilbereiche der IE, die an folgendem Beispieltext illustriert werden, sind:„Barack Obama hat einige Einschränkungen verfügt, doch er wird die NSA nicht entscheidend zügeln. Der Geheimdienst ist viel zu wertvoll für ihn.“ (Spiegel-Online vom17.1.2014, www.spiegel.de/netzwelt/netzpolitik/nsa-refoermchen-obamas-digitalewaffen-a-944123.html, letzter Zugriff: 10.2.2014.)

  • Named Entity Recognition (NER), bei der es um die Extraktion von benannten Einheiten wie Organisationen,Personen, Orte, Diagnosen usw. geht. Beispiele: „Barack Obama“, „NSA“.
  • Koreferenzauflösung (co-reference resolution) zum Erkennen von unterschiedlich benannten Referenzen auf dieselbe Entität. Beispiele: „er“,„ihn“→„Barack Obama“; „Geheimdienst“→„NSA“.
  • Relationsextraktion (relation extraction) zum Finden von vorbestimmten Beziehungen zwischen erkannten Entitäten. Beispiele: Einschränken
    (Obama NSA) mit Intensität = niedrig; Wertvoll (NSA Obama) mit Intensität = hoch.
  • Ereignisextraktion (event extraction) zur Identifikation von bestimmten Arten von Ereignissen im Text (wer, wem, wo, wann, was, usw.). Ereignisextraktion ist am schwierigsten und wertet meist viele Sätze in einem Text aus, die sich auf ein Ereignis beziehen (das kann z. B. eine Relation sein).
  •  

Meist werden Vorverarbeitungstechniken auf dieTexte angewendet wie das Zerlegen des Textes in Basiseinheiten (Token) wie Wörter und Satzzeichen, das Erkennen von Satzgrenzen, das Erkennen von Wortarten (part of speech tagging), das Rückführender Wörter auf Grundformen (morphologische Analyse), ggf. Rechtschreibkorrektur und das Erkennen von Satzteilen (chunking). Der Stand der IE wurde durch die Message Understanding Konferenzen von 1987–1998 stark vorangebracht, bei denen jeweils zunehmend komplexere vordefinierte Aufgaben zu lösen waren und zu denen es verschiedene Nachfolgeprogramme gab und gibt (http://semanticweb.org/wiki/ACE,_MUC,_TAC,_etc._notes, letzter Zugriff:10.2.2014).  Der Erfolg von IE-Methoden wird mit den beiden Maßen Precision und Recall gegenüber einem Goldstandard (d. h.manuell korrekt annotiertes Dokument) gemessen, wobei Recall der Prozentsatz der richtig extrahierten von allen richtigen Textstellen im Goldstandard ist und Precision der Prozentsatz der richtig extrahierten von allen extrahierten Textstellen ist. Häufig werden Precision und Recall zum F-Maß kombiniert, bei denen Precision und Recall unterschiedlich gewichtet werden können. In vielen Anwendungenwerden Werte für Precision und Recall von über 90% erreicht, insbesondere in spezialisierten Domänen. Es gibt mächtige Frameworks, die den Pipeline-Ansatz zur IE unterstützen (der Output einer Komponente ist der Input der nächsten), von denen GATE (General Architecture for Text Engineering, gate.ac.uk, letzter Zugriff: 10.2.2014.) und UIMA (Unstructured Information Management Architecture, uima.apache.org, letzter Zugriff: 10.2.2014.) weitverbreitete Open-Source Software-Pakete sind. IE kann mit Knowledge-Engineering-Ansätzen oder automatisch trainierbaren Lernverfahren umgesetzt werden. Bei ersteren erstellen Menschen Regeln, Muster oder Automaten zur Extraktion von Informationen, bei letzteren werden in größeren Korpora zu allen Textstellen die zu extrahierenden Informationen manuell annotiert, woraus die Lernverfahren Modelle generieren, um Informationen aus ähnlichen, unbekannten Texten zu extrahieren. Die Modelle können Black-Box-Modelle oder White-Box-Modelle wie die oben erwähnten Regeln und Muster sein. Während in kommerziellen Anwendungen eher regelbasierte Ansätze dominieren, finden sich in der wissenschaftlichen Literatur überwiegend Lernverfahren [3]. Gemischte Verfahren, welche die jeweiligen Stärken und Schwächen kombinieren, sind ebenfalls populär.

Knowledge Engineering Ansätze zur Informationsextraktion

Manuell erstellte Informationsextraktionssysteme basieren oft auf kaskadierenden Regel-Grammatiken [2]. Der Knowledge Engineer definiert eine Menge von Regeln, deren Kondition aus einem regulären Ausdruck über den Eigenschaften des Textes besteht, wie zum Beispiel bestimmte Einträge eines Wörterbuches oder Wortklassen. Falls dieses Muster im Text erkannt wurde, weist die Aktion der Regel dieser Textstelle eine Entität oder Relation zu. Eine Menge von Regeln (Grammatik) wird oft als ein Finite State Transducer umgesetzt, welcher die Regeln in einem einzelnen Automaten kompiliert und somit die Ausführungszeit optimiert. Regelbasierte Informationsextraktionssysteme verwenden meist mehrere aufeinander aufbauende Grammatiken, d. h. kaskadierende Grammatiken, welche komplexere Eigenschaften oder bereits Entitäten für spätere Phasen herleiten. Ein bekannter Formalismus für die Spezifikation solcher regelbasierten Systeme ist die Common Pattern Specification Language (CPSL) [1], welche durch die weit verbreitete Java Annotation Pattern Engine (JAPE, 5 gate.ac.uk/sale/tao/splitch8.html, letzter Zugriff: 10.2.2014) im Framework Gate implementiert ist. Im Bereich des UIMA Frameworks existieren unterschiedliche regelbasierte Systeme wie beispielsweise LanguageWare (http://www.alphaworks.ibm.com/tech/lrw, letzter Zugriff: 10.2.2014) oder UIMA Ruta (http://uima.apache.org/ruta.html, letzter Zugriff: 10.2.2014). Obwohl sich diese Regelsprachen und deren Interpreter in Syntax und Ausführungsstrategien der Regeln unterscheiden, besitzen sie oft eine ähnliche algorithmische Basis und erweitern diese durch bestimmte Aspekte. Das System SProUT [5] beispielsweise kombiniert die Implementierung der regulären Ausdrücke als Finite State Transducer mit Techniken der unifikationsbasierten Grammatiken, wodurch die Spezifikation bestimmter Muster ermöglicht oder vereinfacht wird. Neben den Ansätzen, welche auf Finite State Transducer basieren, wurden auch unterschiedliche Systeme entwickelt, welche eher einen deklarativeren Ansatz verfolgen. Hierzu gehört SystemT [2], in welchem die Regeln in einer Sprache ähnlich SQL spezifiziert werden. Die Regeln werden vor der Ausführung in einen Graphen algebraischer Operatoren überführt und können daher in einem optimierten Ausführungsplan überprüft werden.

Interessante Herausforderungen im Bereich der Knowledge-Engineering-Ansätze umfassen unter anderem die Definition einer standardisierten Regelsprache, welche viele Vorteile für zukünftige Forschung und Anwendungen mit sich bringt. Diese sollte sich durch eine ausreichende Ausdrucksmächtigkeit, deklarative Natur und Erweiterbarkeit auszeichnen [3]. Ein aktueller Trend ist die Entwicklung performanter Ansätze für die Ausführung der Regelmengen, um die Verarbeitung die immer größer werdenden Datenmengen zu bewältigen [2], aber auch die Entwicklung besserer Werkzeuge für die Spezifikation der Regeln.

Informationsextraktion mit maschinellen Lernverfahren

Anstatt einen menschlichen Domänenexperten Informationsextraktionsmuster manuell eingeben zu lassen, ist es oft auch möglich, Abhängigkeiten zwischen dem Vorhandensein von gesuchten Informationstypen und Textmerkmalen anhand von Beispieldokumenten automatisch zu lernen. In der Regel bedeutet das, eine Abbildung gemäß einer Kostenfunktion zu optimieren. Voraussetzung ist das Vorhandensein einer ausreichend großen Stichprobe von repräsentativen Dokumenten der Domäne und die Annotation der Texte mit den gesuchten Informationstypen. Für die Klassifikation ist eine Vielzahl unterschiedlicher Methoden anwendbar. Oft werden probabilistische graphische Modelle [10] benutzt, wie Hidden-Markov-Modelle oder Conditional Random Fields. Entscheidend für die Qualität eines Systems ist insbesondere die Auswahl und Definition von relevanten Merkmalen, welche die Unterscheidung zwischen den gesuchten Informationstypen ermöglichen. Diese Indikatoren sind oft lexikalisch, wie z. B. die Merkmale ,,das folgende Wort ist ,berichtet‘ “ und ,,das Wort ist großgeschrieben“, die für die Erkennung von Personen oder Organisationen hilfreich sein können. Ohne geeignete Textmerkmale, kann kein gutes Modell zur IE gelernt werden. Ähnlich zum Knowledge Engineering Ansatz ist hier Domänenwissen gefragt.

Neben rein lexikalischen Merkmalen gibt es in den IE Teilbereichen unterschiedliche strukturelle Abhängigkeiten, die für die Klassifikation notwendig sein können. Für NER sind beispielsweise sequenzielle Abhängigkeiten relevant, welche die Klassifikation eines Wortes von dem Typ des vorherigen bzw. nachfolgenden Wortes abhängig machen. Die oben erwähnten Hidden-Markov-Modelle oder Conditional Random Fields modellieren diese Eigenschaft. Sie segmentieren und klassifizieren den Text gleichzeitig unter Nutzung effizienter Automaten. Baum- oder Graphstrukturen, wie z. B. Dependenzstrukturen, sind beispielsweise für die Relationsextraktion nützlich.

Viele Forschungsgebiete der Informationsextraktion ergeben sich aus Problembereichen des maschinellen Lernens im Allgemeinen. Dazu gehören unter anderem die Domänenanpassung (domain adaptation) [4], bei der Unterschiede zwischen Trainingsdaten und Test- bzw. Anwendungsdaten bestehen (z. B. Zeitungsartikel vs. Tweets vs. medizinischer Telegrammstil) sowie halbüberwachte Lernverfahren, bei denen zusätzliche Dokumente (z. B. unannotierte Wikipedia-Artikel) die IE unterstützen.

Weiterhin kann man unterschiedliche Forschungsgebiete abgrenzen, die sich in der Regel mit der Integration nicht-sequenzieller Abhängigkeiten beschäftigen, da einzelne Textstellen oft zu wenig Kontext liefern, um sicher Informationen extrahieren zu können. Collective Inference Ansätze betrachten mehrere ähnliche Textstellen zusammen (z. B. alle Vorkommen eines bestimmten Wortes in einem festen Dokument), um das Vorkommen eines Informationstyps zu bestimmen. In vielen Domänen können darüber hinaus kontextspezifische Abhängigkeiten ausgenutzt werden. Man kann beispielsweise versuchen, automatisch zu erkennen, ob Dokumente vom gleichen Autor geschrieben wurden oder innerhalb eines Dokumentes verschiedene Abschnitte ähnlich gestaltet sind, um dieses Wissen anschließend auszunutzen [9]. So können z. B. Literaturlisten sehr verschieden formatiert sein, aber bei der Extraktion von Publikationen aus wissenschaftlichen Arbeiten kann man meistens davon ausgehen, dass alle Publikationen in einer Arbeit den gleichen Stil haben.

Beispiel:Medizinische IE

Da in der Medizin der überwiegende Teil der Informationen textuell vorliegt, ist IE die Voraussetzung für eine Weiterverarbeitung der Daten beispielsweise für statistische Auswertungen, Qualitätssicherung, Auswahl von Patienten für klinische Studien sowie wissensbasierte Dienste im Allgemeinen, da diese strukturierte bzw. kodierte Daten benötigen. Für eine typische Aufgabe wie die IE aus Arztbriefen werden folgende Phasen durchlaufen: Anonymisierung aller Daten, die auf Personen hinweisen; Segmentierung des Arztbriefes in Abschnittstypen wie Diagnosen, Anamnese, Körperliche Untersuchung usw.; Extraktion der eigentlichen Informationen aus jedem Abschnittstyp gemäß einer speziellen Ontologie; Integration und Plausibilitätsprüfung der Daten, ggf. unter Zuhilfenahme von Informationen aus anderen Dokumenten; Transfer in eine Datenbank. Dabei gibt es einige Besonderheiten, welche die IE teils erleichtern, teils erschweren. So müssen in medizinischen Dokumenten hauptsächlich Begriffe erkannt werden, was mit der NER die am besten verstandene Aufgabe des IE ist. Die Terminologie insbesondere der Diagnosen ist im ICD (International Classification of Diseases) standardisiert; reichhaltigere Vokabulare findet man in SNOMED und insbesondere im UMLS, das verschiedene Terminologien aufeinander abbildet. Andererseits gibt es für die Begriffe oft keinen einheitlichen Sprachgebrauch, es werden viele, darunter auch ad-hoc-Abkürzungen verwendet und die Rechtschreibung ist oft fehlerhaft. Begriffe werden zudem häufig negiert (z. B. „keine Luftnot“), mit Unsicherheitsgraden belegt (z. B. „Verdacht auf Lungenentzündung“) und der Zeitverlauf kann eine große Rolle spielen. Eine weitere Besonderheit ist der häufig verwendete Telegrammstil, z. B. „EKG: Sinusrhythmus, HF 55/min, Mitteltyp, Überleitungszeiten in der Norm, keine ERBS“. Ein in den USA häufig eingesetztes, inzwischen kommerzialisiertes medizinisches IEGesamt- System ist MEDLEE [7]; ein erfolgreiches Open-Source-System ist das auf Apache UIMA basierende cTAKES [12]. Auch das oben erwähnte System Watson wird für die medizinische IE angepasst (http://www-03.ibm.com/innovation/us/watson/watson_in_healthcare.shtml,
letzter Zugriff: 10.2.2014).

Zusammenfassung

Informationsextraktion ist eine Schlüsseltechnologie, die ein vereinfachtes Teilproblem der Sprachverarbeitung löst, nämlich die Extraktion vordefinierter Informationstypen aus Texten. In vielen Teilbereichen gibt es schon beachtliche Erfolge. Allerdings ist die Technologie noch sehr domänen und sprachabhängig, so lassen sich viele Ansätze nicht ohne weiteres vom Englischen in andere Sprachen übertragen. Ein breiterer Überblick über den aktuellen Stand zur Informationsextraktion findet sich in [11]. 

Literatur

1. Appelt D, Onyshkevych B (1998) The common pattern specification language. In: Proc. of a Workshop of the Association for Computational Linguistics, TIPSTER ’98, Stroudsburg, PA, USA, pp 23–30
2. Chiticariu L, Krishnamurthy R, Li Y, Raghavan S, Reiss F, Vaithyanathan S (2010) SystemT: An Algebraic Approach to Declarative Information Extraction. In: Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL ’10, Association for Computational Linguistics, Stroudsburg, PA, USA, pp 128–137
3. Chiticariu L, Li Y, Reiss F (2013) Rule-based Information Extraction is Dead! Long Live Rule-based Information Extraction Systems! In: Proc. of 2013 Conference on Empirical Methods in Natural Language Processing, pp 827–832
4. Daumé III H, Marcu D (2006) Domain Adaptation for Statistical Classifiers. J Artif Intell Res 26:101–126
5. Drozdzynski W, Krieger H-U, Piskorski J, Schäfer U, Xu F (2004) Shallow Processing with Unification and Typed Feature Structures – Foundations and Applications. Künstliche Intelligenz 18(1):17–23
6. Ferrucci D, Brown E, Chu-Carroll J, Fan J, Gondek D, Kalyanpur A, Lally A, Murdock W, Nyberg E, Prager J, Schlaefer N, Welty C (2010) Building Watson: An Overview of the DeepQA Project. AI Mag 31(3):59–79
7. Friedman C, Shagina L, Lussier YA, Hripcsak G (2004) Automated encoding of clinical documents based on natural language processing. J Am Med Inform Assoc 11(5):392–402
8. Hippner H, Rentzmann R (2006) Text Mining. Aktuelles Schlagwort in: Informatik- Spektrum 29(4):287–290
9. Klügl P, Toepfer M, Lemmerich F, Hotho A, Puppe F (2012) Collective Information Extraction with Context-Specific Consistencies. In: Flach PA, Bie TD, Cristianini N(eds) ECML/PKDD (1). Lecture Notes in Computer Science, Bd. 7523, Springer, pp 728–743
10. Koller D, Friedman N (2009) Probabilistic Graphical Models: Principles and Techniques. MIT Press, Cambridge, MA
11. Piskorski J, Yangarber R (2013) Information Extraction: Past, Present and Future. In: Poibeau et al. (eds) Multi-source, Multilingual Information Extraction and Summarization, Springer-Verlag, pp 23–49
12. Savova G, Masanz J, Ogren P, Zheng J, Sohn S, Kipper-Schuler K, Chute C (2010)Mayo clinical Text Analysis and Knowledge Extraction System (cTAKES): architecture, component evaluation and applications. J Am Med Inform Assoc 17(5): 507–513

Autor und Copyright

Martin Toepfer
Universität Würzburg, Lehrstuhl für Informatik VI,
Würzburg
E-Mail

Peter Klügl
Universitätsklinikum Würzburg,
Deutsches Zentrum

© Springer-Verlag Berlin Heidelberg 2014