%\documentclass[a4paper,twoside,10pt]{report}

%\usepackage[ngerman]{babel}
%\usepackage[T1]{fontenc}
%\usepackage[latin1]{inputenc}

%\begin{document}

\subsubsection{Definition und Zielsetzung}\label{definition}
Zielsetzung der Named Entity Recognition ist es, bestimmte Bestandteile eines natürlich-sprachlich verfassten Text, also Zeitungsartikel, Dossiers oder auch E-Mail, zu erkennen und einer vorgegebenen Kategorie zuzuordnen. Diese Bestandteile nennt man auch \textbf{Named Entities}. Die Named Entities dienen in der Regel dazu wichtige Fragen, die an einen natürlich-sprachlichen Text gestellt werden, zu beantworten. Was? Wann? Wo? und Wer? sind dabei typische Fragen, die mit der Named Entity Recognition geklärt werden können.\newline
Die Besonderheit dieser Named Entities ist ihre Einmaligkeit, denn üblicherweise handelt es sich dabei um eine Person, Organisation oder einen Ort. Angaben also, die in der Regel definit sind und nur einmal vorkommen. Beispielsweise könnte dem Begriff \emph{Angela Merkel} eindeutig die Klasse Person zugewiesen werden - es handelt sich also um ein Named Entity oder auch Eigenname, während der Begriff \emph{Bundeskanzler/in} nicht auf eine bestimmte Person hinweist, somit also nicht klassifiziert wird. Wichtig ist also, dass nur relevante Informationen klassifiziert werden, wobei sich die semantische Relevanz auf die Domäne des Texts bezieht. Die Relevanz kann durch die Auswahl passender Trainingsdaten sowie den Tags bestimmt werden. Neben den oben aufgeführten Kategorien Person, Organisation und Ort gehören auch Zeitangaben sowie quantitative Aussagen zu den möglichen Named Entities.\newline
Hier nun ein kurzes Beispiel für eine mögliche Ein- und Ausgabe eines NER-Systems:
\newline
\begin{description}
\item[Eingabe:] Auch die widersprüchlichen Angaben darüber, wie viel Geld Bohlen tatsächlich am 11. Dezember 2006 gestohlen wurde, wollte das Landgericht Bochum klären.
\item[Ausgabe:] Auch die widersprüchlichen Angaben darüber, wie viel Geld \textbf{<Person>Bohlen</Person>} tatsächlich am \textbf{<Datum> 11. Dezember 2006 </Datum>} gestohlen wurde, wollte das \textbf{<Organisation> Landgericht Bochum </Organisation>} klären.
\end{description}


\subsubsection{Geschichte der NER}\label{geschichte}
Named Entity Recognition wurde durch die von der DARPA instituierten Message Understanding Conferences (kurz: MUC) bekannt. Die Message Understanding Conferences fanden erstmals 1987 statt und hatten die Entwicklung besserer Information Extraction-Methoden zum Ziel. Dabei gibt es eine Reihe von Teams, die alle an einem genau definierten Ziel, unter Vorgabe der zu untersuchunden Texte, arbeiten. Die einzelnen Ergebnisse der Gruppen werden an den Konferenztagen vorgestellt und ermöglichen so einen umfassenden Blick über den aktuellen Stand der Technik.\newline
In diesem Zusammenhang wurde Named Entity Recognition / Koreferenz erstmals 1995 in der sechsten MUC als Ziel definiert. Das Forschungsgebiet ist in der Informatik also relativ neu.

\subsubsection{Evaluation}\label{evaluation}
Um gute Programme zu entwickeln, benötigt man ein Scoring-verfahren um die Qualität des Programms bemessen zu können. In der Named Entity Recognition haben sich dabei drei immer wieder verwendete Evaluationsmaße etabliert. Alle Werte gehen davon aus, dass wir den gesamten Korpus einer Datei oder eines Texts nach Named Entities durchsuchen.
\begin{description}
\item[Precision] 
Unter Precision, oder zu deutsch Präzision, versteht man die Anzahl der korrekt klassi\-fizierten Named Entities im Verhältnis zu der Anzahl der vom Recognizer gefundenen Named Entities.\newline
\begin{equation}
Precision = \frac{Anzahl korrekt klassifizierter NEs}{Anzahl NEs gefunden}
\end{equation}

\item[Recall]
Recall ist die Ausbeute an Named Entities aus dem gesamten Dokument. Hier wird also das Verhältnis der Anzahl an korrekt klassifizierten Named Entities zu den insgesamt im Text vorhandenen Named Entities betrachtet. \newline
\begin{equation}
Recall = \frac{Anzahl korrekt klassifizierter NEs}{Anzahl vorhandener NEs im Korpus}
\end{equation}

\item[F-Measure]
Um beide Größen, also Precision und Recall, zusammen betrachten zu können, bildet man den ungewichteten harmonischen Mittelwert beider Werte und erhält den so genannten F-Measure \cite{Van-Rijsbergen/79a}.
\begin{equation}
F-Measure = \frac{2*Precision*Recall}{Precision + Recall}
\end{equation}

\end{description}


\subsubsection{Interne / Externe Evidenz}\label{evidenzen}
Jedes Merkmal zur Klassifikation eines Named Entity kann ganz grob in Interne und Externe Evidenz aufgeteilt werden. So kann jedes Analyseverfahren in [\ref{analyseverfahren}] eine der beiden Gruppen aufgeteilt werden.

\begin{description}
\item[Interne Evidenz]
Verfahren der Internen Evidenz ziehen ihr Wissen nur aus dem betrachteten Wort. Dies kann ein Eintrag in einem Lexikon (zum gesuchten Wort) sein [\ref{lexikalisch}], bestimmte Bestandteile eines Wortes oder auch die Großschreibung einzelner Buchstaben. Wenn wir beispielsweise das Wort DARPA betrachten, ist es wahrscheinlich, dass es sich hierbei um eine Organisation handelt, da alle Buchstaben groß geschrieben sind, folglich es sichum eine Abkürzung handeln könnte.

\item[Externe Evidenz]
Viele Verfahren der Internen Evidenz gelangen rasch an ihre Grenzen. So unterscheidet sich rein syntaktisch eine Bank mit der Bedeutung einer Finanzeinrichtung nicht mit der einer (Sitz-) Bank. Auch ein Lexikon würde an dieser Stelle nur viele Möglichkeiten anzeigen, aber kein Aufschluss darüber geben, worum es sich nun wirklich handelt.\newline
Hier muss man weitergehen und den Kontext des Wortes betrachten. Der Kontext kann einerseits der umschlossene Satz, aber auch ein ganzer Textabsatz darstellen. So ist der Kontext \textit{Die französische Stadt...}  ein eindeutiger Hinweis auf ein Named Entity der Kategorie \textit{Ort}.Zum Kontext gehören aber auch die vorher bestimmten Named Entities, die oftmals ebenfalls ein hilfreiches Indiz für eine mögliche Einordnung liefern.

\end{description}

\subsubsection{Mögliche Analyseverfahren}\label{analyseverfahren}
\begin{description}
\item[Tokenisierung]\label{tokenisierung}
Bevor man einen Text bearbeiten und maschinell auswerten kann, muss man ihn in seine einzelnen Bestandteile, den Token, zerlegen. Diese Aufsplittung gestaltet sich bei den meisten Sprachen, beispielsweise englisch, deutsch oder spanisch, relativ einfach. Man sucht nach Leerzeichen, die üblicherweise jedes Wort abgrenzen und erhält damit einen einzelnen Token. Wichtig bei der Tokenisierung ist allerdings auch, dass dies nicht in allen Sprachen so einfach sein muss. \newline
Im nächsten Schritt kann man anhand von Satzzeichen ( \grq.\grq,  \grq,\grq, \grq ?\grq) die Struktur des Texts erfassen und bekommt damit wichtige Informationen wenn es darum geht den Kontext eines Worts zu untersuchen. Ausruf- oder Fragezeichen kann man hierbei als deutlichen Hinweis für ein Satzende ansehen. Bei einem \grq.\grq kann man sich dagegen nicht immer sicher sein, dass es sich um das Ende eines Satzes handelt. Hier ist beispielsweise auch eine Abkürzung möglich (bzw. , e.V.,usw.) und man muss anhand des Kontexts bzw. des syntaktischen Aufbaus das Satzende bestimmen.

 
\item[Morphologische Analyse]\label{morphologisch}
Die morphologische Analyse bedient sich sprachlicher Mittel um die im ersten Schritt erfassten Token für die weitere Bearbeitung zu vereinfachen. 
Ein wichtiger Bestandteil der morphologischen Analyse ist das \textbf{Stemming-Verfahren}. Hierbei werden Verben in ihre Stammform überführt um die Anzahl der Regeln, die in den nachfolgenden Schritten zur Erkennung der Kategorie dienen, klein zu halten. So wird aus \textsl{'schläft'} \textsl{'schlafen'} und aus \textsl{'sprach'} \textsl{'sprechen'}. Auch die Anzahl der Lexikoneinträge kann mit diesem Verfahren reduziert werden.\newline
Ganz ähnlich kann man sich die Motivation für die Präfix- und Suffix-Erkennung vorstellen. Auch hier geht es darum komplex zusammengesetzte Wörter zu vereinfachen und auf ihr Lemma zurückzuführen.\newline
Wichtig zu erwähnen ist, dass dieser Schritt bei manchen Sprachen sehr wichtig sein kann. Im Deutschen gibt es eine Vielzahl von morphologischen Veränderungen eines Wortes. Viele verschiedene Zusammensetzungen eines Wortes sind denkbar und müssen hier berücksichtigt werden. Gleiches gilt beispielsweise auch in der französischen Sprache. Im Gegensatz dazu kann man bei der Betrachtung eines englischen Textes einen Großteil dieser Verfahren wegfallen lassen und allenfalls noch ein Stemming von Verben durchführen. Die maschinelle Erfassung der Semantik eines Textes kann also in den verschiedenen Sprachen deutlich variieren.

\item[Lexikalische Analyse]\label{lexikalisch}
Die Lexikalische Analyse in der Named Entity Recognition ist ein einfacher LookUp in einem vorbereiteten Lexikon. In den meisten Fällen kann an dieser Stelle schon eine eindeutige für das Named Entity gefunden werden. So wird man unter dem Stichwort \textsl{Angela Merkel} sicherlich nur eine mögliche Kategorie-Zuordnung zulassen, nämlich \textsl{Person}.\newline
Da es sich hierbei allerdings um ein Verfahren der Internen Evidenz (\ref{evidenzen}) handelt, sprich es wird nur die Struktur des Wortes / Token betrachtet und nicht der Kontext, können Mehrdeutigkeiten auftreten. Diese Mehrdeutigkeiten können nur aufgehoben werden, wenn man sich den kompletten Satz, bzw. den ganzen Abschnitt ansieht und nach möglichen Relationen zur gesuchten Entität Ausschau hält. Dies wird in der Syntaktischen Analyse gemacht.\newline
Hier einige Beispiele für Mehrdeutigkeiten:
\begin{table*}[ht]
	\centering
		\begin{tabular}[ht]{|l|c|}
				\hline
		  	Wort & Mögliche Deutung\\
		  	\hline\hline
		  	Essen & Stadt in NRW oder Mahlzeit?\\
		  	Bank & Finanzeinrichtung oder Sitzmöbel?\\
		  	Buchen & Baum oder Imperativ von \textsl{buchen}. \newline Bsp.: \textbf{Buchen} Sie mir einen Flug!\\
		  	Hamburger & Burger oder Einwohner von Hamburg? \\
		  	\hline
		\end{tabular}
	\caption{Beispiele von Mehrdeutigkeiten}
	\label{tab:BeispieleVonMehrdeutigkeiten}
\end{table*}
 
\item[Syntaktische Analyse]\label{syntaktisch}
Um Mehrdeutigkeiten in der Struktur der Wörter aufzuheben, kommt man nicht umher den Kontext eines Wortes zu betrachten. Kleinräumig ist dies ein Satz, im größeren Maßstab kann man hier aber auch einen Textabschnitt betrachten. Bei der Betrachtung des Kontexts geht es darum den Satz in syntaktische Bestandteile zu zerlegen. Es geht dabei also um die Erkennung von Nomen, Verben, Präpositionen, usw.. Auch bereits erkannte und klassifizierte Named Entities gehören zum Kontext und können hilfreich sein, beispielsweise wenn es darum geht zwei gleiche Referenzen auf ein Objekt aufzulösen. So steht die Abkürzung \textsl{IBM} für \textsl{International Business Machine}. Beides sind Named Entities, die aber die gleiche Firma beschreiben. Anhand der Abkürzung könnte man dies erkennnen.\newline
Für die syntaktische Analyse eines Satzes werden in der Named Entity Recognition \textbf{Part-of-Speech Tagger} eingesetzt. Diese weisen jedem Wort eines Satzes eine Wortklasse zu. Anhand von Kontextinformationen können hier Mehrdeutigkeiten aufgehoben werden, wobei auch unbekannten Wortphrasen eine Wortklasse zugeteilt wird.
TnT ist ein relativ bekannter POS-Tagger und klassifiziert englische Wörter mit bis zu 86 Prozent und deutsche mit 89 Prozent Wahrscheinlichkeit zur richtigen Wortgattung. \newline
Eine Alternative zum POS-Tagger wäre ein \textbf{Full-Parsing}, wo die Analyse einer Satzkonstruktion über einen Parsebaum geschieht, der an kontextfreie Grammatiken angelehnt ist und Wortgattungen aufgrund von Position und Vorkommen im Satz ableitet. Allerdings ist diese Verfahren sehr fehlerbehaftet und benötigt viel Rechenzeit, weswegen man es in der Regel nicht anwendet \cite{Appelt/Israel/99a}.

\item[Domänenspezifische Analyse]\label{domaenen}
In der Domänenspezifischen Analyse geht es darum die Klassifizierung durch Einbezug des Text-Themas - daher Domänenspezifisch - zu verbessern. Hierbei kommt insbesondere die Koreferenz-Auflösung zum Einsatz. 
Die Aufgabe der \textbf{Koreferenz-Auflösung} ist die Erkennung von gleichen Referenzen innerhalb eines Texts. Falls also am Anfang eines Texts von G.W. Bush die Reder ist und in späteren Abschnitten nur von Er die Rede ist, muss erkannt werden, dass es sich hierbei um die anfangs genannte Person handelt. Auch bei Organisationen/Firmen ist die Erkennung dieser Personalpronomen wichtig um den Inhalt des Texts verfolgen zu können. Auch temporale Referenzen müssen allerdings aufgelöst werden. So bedeutet die Phrase \grq um Viertel vor Vier \grq genausoviel wie 15:45 Uhr.\newline
Beim \textbf{Merging} geht es hingegen darum gegebene Named Entities zu verschmelzen, falls es sich dabei um ein und dasselbe Objekt handelt. Hier einige Merging-Beispiele:
\begin{table*}[ht]
	\centering
		\begin{tabular}[ht]{|l|c|}
				\hline
		  	Abkürzung & Referenz\\
		  	\hline\hline
		  	IBM & International Business Machine\\
		  	Deutsche Bahn AG  & Die Bahn entlässt Mitarbeiter\\
		  	USA & United States of America\\
		  	Hamburger & Burger oder Einwohner von Hamburg? \\
		  	\hline
		\end{tabular}
	\caption{Beispiele für Merging-Operationen}
	\label{tab:BeispielefürMergingOp}
\end{table*} 
\end{description}


\subsubsection{Systemarchitekturen}\label{architekturen}
\begin{description}
\item[Listenbasierte Systeme]\label{listenbasiert}
Beim Entwurf einer Systemarchitektur für ein NER-System kann man sich ganz einfach eine riesige Liste mit allen Named Entities vorstellen, die es gibt. In dieser Liste müssten dann aber auch immer alle neuen Wortschöpfungen ergänzt, sowie morpholgische Varianten eines Wortes abgespeichert werden. (aus \cite{Cunningham/Bontcheva/2003a}) \newline
Während diese beiden Punkte noch relativ gut realisierbar sind, führen die möglichen Mehrdeutigkeiten dazu, dass ein Listenbasiertes Verfahren keine gute Option für die Named Entity Recognition darstellt. Mann kann zwar nachschlagen, was Essen alles bedeuten kann, aber ohne Betrachtung des Kontexts wird es nicht möglich sein, die passende Kategorie der Entität zu finden. Rein Listenbasierte Verfahren scheiden also aufgrund der zu hohen Fehlerrate  aus.

\item[Regelbasierte Systeme]\label{regelbasiert}
Bei Regelbasierten Systemen definiert man anhand der Merkmale der einzelnen Token Regeln, um das Einsortieren in Kategorien zu ermöglichen. Dabei nutzt man morpholgisches, lexikalisches, syntaktisches und domänenspezifisches Wissen aus, also alle Verfahren, die zur Bestimmung von Named Entities in Frage kommen. Hat man eine Reihe von Regeln entwickelt kann man daraus eine Grammatik (kontextfrei) entwickeln, die in Texten nach Named Entities sucht.\newline
Im Gegensatz zu lernbasierten Verfahren benötigt man hier allerdings spezielle Linguisten für die Entwicklung der einzelnen Regeln. Diese Regeln werden dann an relativ kleinen Trainings-Datensätzen getestet und falls erforderlich korrigiert und wieder getestet. Nach einigen Iterationen hat man so eine qualitativ gute Regelmenge zur Erkennung von Named Entities zusammen. Insgesamt ist die Entwicklung von Regelbasierten Verfahren zeitaufwändiger, da man hier sehr umfassende Grammatiken entwickeln muss. Und auch hinsichtlich der Flexibilität zeigen sich Regelbasierte Systeme eher nachteilig im Vergleich zu Lernbasierten Verfahren. Hier kann man die Grammatik in der Regel nicht schnell erweitern oder gar einige Teile verändern, da viele Regeln aufeinander aufbauen und transitiv abhängig sind. Auch die Anpassung an eine neue Domäne ist damit wesentlich schwieriger. (siehe \cite{Feldman/2003a})\newline \newline
Nachfolgend einige Beispiele wie solche Regeln aussehen können:\newline

\begin{itemize}
	\item Aufeinanderfolgende Phrasen der Form <Wort><Wort> GmbH deuten mit hoher Wahrscheinlichkeit auf eine Firma / Organisation hin
	\item Großgeschriebene Worte können Hinweise auf eine Firma oder Organisation sein: NASA, ADAC, UNICEF
	\item \grq denken\grq ist, unabhängig vom Tempus der Verbform, in der dritten Person immer ein starker Hinweis für ein menschliches Subjekt
	\item Vorkommen von \grq-burg\grq, \grq-dorf\grq, \grq-stadt\grq  deuten auf eine Ortsangabe aus dem deutschsprachigen Raum hin
\end{itemize}

\item[Lernende / Automatische Systeme]\label{lernbasiert}
Lernende oder Automatische Systeme nutzen statistische Verfahren oder Methoden des Maschinellen Lernens um in einem Textkorpus nach Named Entities zu suchen. Im Gegensatz zu Regelbasierten Verfahren werden dabei qualitativ und quantitativ hohe Anforderungen an Trainingstexte gestellt. Douglas E. Appelt und David J. Israel beschreiben in ihrem Paper \cite{Appelt/Israel/99a}, dass man für jede Verdopplung der Trainingsdatensätze den F-Measure um 1,5 Punkte steigern kann. Dabei ist die Auswahl der Trainingsdatensätze entscheiden für das spätere Verhalten des Recognizers und kann mitunter schwieriger sein als das Entwerfen von Regeln für ein Regelbasiertes System. \newline
Zu den wichtigsten Verfahren des Maschinellen Lernens gehören Hidden Markov Models \ref{hmm}, Maximum Entropy Markov Models \ref{memm}, Conditional Random Fields \ref{crf} und Support Vextor Machines \ref{svm}. Jedes Verfahren wird mit den möglichen Erweiterungen weiter unten beschrieben.\newline
Eine Gefahr bei Maschinellen Lernverfahren ist das so genannte \textbf{Overfitting}. Dabei wird dergleiche Trainingstext immer und immer wieder gelernt, so dass eine Überanpassung des Systems an den Datensatz vorkommen kann. Wird nun bei der Erkennung ein thematisch anderer Datensatz verwendet, ist eine hohe Fehlerrate bei der Klassifikation von Named Entities wahrscheinlich. 
\end{description}


\subsubsection{Vor- und Nachteile der Systemarchitekturen}\label{vornachteil}
Regelbasierte Systeme benötigen aufgrund der einfachen Erstellung eines Parsebaums relativ wenig Zeit zur Auswertung, wobei die Auswertungsergebnisse auf gleicher Höhe oder etwas besser im Vergleich zu Lernbasierten Systemen sind. So ergab die Auswertung eines Wall Street Journals in der siebten Message Understanding Conference einen Vorteil der Regelbasierten Systeme von 3,3 Prozentpunkten (93,7\% vs. 90,4\% gemessen an der Zahl der korrekt klassifizierten NE, \cite{Feldman/2003a}).\newline
Lernende Systeme sind hingegen wesentlich flexibler, wenn es darum geht, ein System zur Laufzeit zu verändern. Während wir bei Regelbasierten Systemen viele Regeln einzeln anpassen müssen, genügt es die Parameter zu verändern und das System mit neuen Trainingstexten zu füttern. Diese Flexibilität zeigt sich auch hinsichtlich der Anpassung an verschiedene Sprachen.

%\bibliographystyle{plain}
%\bibliography{ner}

%\end{document}

