ToSoBaP - Dokumentation

Ein Studienprojekt von Susanne Haaf und Kai Bormann, anfängtlich begleitet von Philipp Scheffzek.
Gesamtarchiv des Projektes
Verzeichnis der Quellen
Weitere Informationen: http://www.cl.uni-heidelberg.de/~bormann/documents/tosobap/
Kontakt: bormann@cl.uni-heidelberg.de oder haaf@cl.uni-heidelberg.de

Towards Solving the Babel Problem

Das folgende Abstract beschreibt die zu Begin des Projektes angestrebten Ziele sowie die Motivation für das Projekt:

Die Bestimmung der Sprache eines Textes ist Grundvoraussetzung für viele computerlinguistische Anwendungen und Verfahren (z.B. maschinelle Übersetzung, Syntaxanalyse, ...). Das vorliegende Studienprojekt hat deshalb das Ziel ein Verfahren zu entwickeln, das diese Aufgabe möglichst effizient und vor allem korrekt bewältigt.

Ausgehend von einem einfachen Ansatz mit Unigrammen (unsere Baseline) sollen verschiedene linguistische und statistische Verfahren, sowie deren Kombinationen implementiert und evaluiert werden. In einem ersten Schritt sollen die Verfahren auf möglichst viele Sprachen mit lateinischen Schriftzeichen angewandt werden und hierzu einzel-sprachliche Korpora, sowie ausführliche Testläufe erstellt werden. Die Ausweitung auf andere Schriftsysteme sollte aber ohne weiteres möglich sein.

Auf seinem aktuellen Stand verügt ToSoBaP über Implementierungen folgender Ansätze: Unigramme, Bigramme, Trigramme, kurze Wörter, Stopwörter, Wortlänge. Darüber hinaus in ein automatisches Evaluationsmodul in Ansätzen vorhanden.

Benutzung von ToSoBaP

Das Modul tosobap ist ein Programm zur Sprachidentifikation. Es beinhaltet konkrete Modelle aller dem Programm bekannten Sprachen in einer bestimmten Methode und mit einer gemeinsamen Filtereinstellung.

Der einfachste Fall: auszuwertender Text wird mit -t übergeben
> python tosobap.py -t "Finde raus in welcher Sprache ich bin"
    (0.53182149908671261, 'de')

Über den Parameter -v erhält man die Ergebnisdaten für alle Sprachen:
> python tosobap.py -v -t "Finde raus in welcher Sprache ich bin"
    [(0.53182149908671261, 'de'), (0.42759318388988588, 'en'), (0.385443165 ...

Hierbei wurde automatisch ein serialisiertes Bigrammodell verwendet. Andere serialisierte Modelle können über den Schalter -d (deserialize) verwendet werden:
> python tosobap.py -d "trigram.toso" "Finde raus in welcher Sprache ich bin"
    (0.26615897497267732, 'de')

Es können selbstverständlich auch neue Modelle erzeugt werden. Hierzu dient der Schalter -m - gültige Werte sind zur Zeit unigram, bigram, trigram, shortwords, stopwords und wordlength. Achtung: Die erzeugung eines Modelles kann etwas Zeit in Anspruch nehmen, es empfielt sich daher öfter benötigte Modelle zu serialisieren. Dies ist über die Option -s möglich:
> python tosobap.py -m "trigram" -s "trigram.toso"

Ab jetzt kann das Trigrammodell über die Option -d "trigram.toso" benutzt werden, ohne dass es jedes mal neu aus den Korpusdaten erzeugt werden muss.

Die weiteren Parameter können wie folgt angezeigt werden:
> python tosobap.py -h

Ergänzung um weitere Sprachen

Eigene Sprachen bzw. Sprachvarianten können sehr einfach zu ToSoBaP hinzugefügt werden:

Im Verzeichnis res/corpus/ muss ein neues Unterverzeichnis angelegt werden.
Dessen Name wird als Kennung für die neuen Sprache verwendet, es empfielt sich daher sich an sich an den internationalen Ländercodes zu orrientieren.
In dieses Verzeichnis müssen nun einige Textdaten der entsprechenden Sprache gelegt werden.
Wie die Dateien heißen, die diese Daten enthalten ist egal, ebenso spielt es keine Rolle ob es eine große oder viele kleine Dateien sind.
ToSoBaP erkennt die neue Sprache automatisch und berücksichtigt sie ab sofort.
Serialisierte Tosobap-Instanzen müssen jedoch durch neue ersetzt werden.

Zum Dauerhaften entfernen einer Sprache kann das entsprechende Verzeichnis gelöscht werden.

Eine Besonderheit ist die Datei stopwords.txt, die in jedem Sprachverzeichnis liegen kann. Sie sollte eine Liste von Stopwörtern der Sprache enthalten und wird vom Stopword-Modell verwendet. Alle andere Methoden ignorieren diese Datei.
Verfügt eine Sprache nicht über eine stopwords.txt Datei kann sie vom Stopword-Modell nicht berücksichtigt werden.

Automatische Evaluation

Die Klasse evaluator.py ist derzeit leider nicht wie ursprünglich geplant nutzbar.
Es war angedacht, dass automatisch eine ausfürliche Evaluation nach einem vorgegebenen Testplan durchgeführt wird. Hierbei sollte evaluator.py dem Testplan entsprechend immer wieder neue Instanzen von ToSoBaP mit verschiedenen Parametern erzeugen und diese im Anschluss einer Evaluation unterziehen.
Angedacht ist der folgende Ablauf

Einlesen eines Testplanes. Dieser enhält Angaben dazu welche Methoden mit welchen Filterkombinationen und welchen Trainingskorpusgrößen erzeugt werden sollen. Ebenso in welchem Ramen und in welcher Schrittweise die Länge der Testdaten verändert werden soll.
evaluator.py erzeugt eine neue Instanz der Klasse Tosobap, mit der Methode, den Filtern und den angegebenen Trainingsdaten.
dieser Tosobap-Instanz werden jetzt Testdaten verschiedener Länge und verschiedener Sprachen vorgesetzt und die Ergebnisse notiert.
Dies wird für alle anderen Trainingssets wiederholt
Die Gesammelten Daten werden gespeichert und können jetzt Weiterverarbeitet werden. So könnten etwa mit GnuPlot Kurven erzeugt werden, die die Effizienz einzelner Verfahren in Abhängigkeit von der Größe des Trainingskorpus und der Länge der Eingabedaten aufzeigt.

Sobald durch eine gründliche Evaluation das "beste" (korrekteste, schnellste, mit den wenigesten Daten auskommendste, ...) Modell mit den passenden Parametern ermittelt wurde könnte ein sehr einfaches ToSoBaP-Modul erzeugt und distributiert werden, dass dann nur noch die Identifikation der Sprache der Eingabedaten -ohne weitere Wahlmöglichkeiten- übernimmt.

Programmstruktur

ToSoBaP gliedert sich in die folgenden Module. Hier soll kurz ihre Funktion sowie ihre wichtigsten Methoden erläutert werden. Für weitergehende Informationen sei an die embedded documentation verwiesen.

models/*.py

In diesem Ordner befinden sich die Implementierungen der einzelnen Sprachidentifikationsmodelle. In der Regel sind die folgenden Funktionen vorhanden:

train(data) - Erzeugt die eigentliche Repräsentation des Modells. Die Übergebenen Trainingsdaten werden ausgewertet und die Ergebnisse in entsprechenden Datenstrukturen abgelegt.
compare(data) - erzeugt aus den Eingabedaten ein temporäres Modell des gleichen Typs und vergleicht beide daraufhin mit Hilfe der Funktion __similarity()
compareModel(model) - Vergleicht das Modell der aktuellen Instanz mit einem anderen bestenden Modell.
__similarity(testmodel) - Führt die eigentlichen Berechnungen zur Ähnlichkeit von Modellen durch. Es können immer nur Modelle des gleichen Typs miteinander verglichen werden, da unterschiedliche Datenstrukturen zu Grunde liegen. Denkbar ist es auch gleiche Ansätze mit Verschiedenen Metriken auszuwerten, hierbei müsste jeweils nur diese Funktion geändert werden.

tosobap.py

Dies ist das zentrale Modul, das in der Regel vom Endbenutzer verwendet werden soll. Die Verwendung ist weiter oben in dieser Dokumentation erläutert.
Die Hauptaufgabe liegt in der Analyse der passenden Sprache zu einem Eingabetext. Hierzu werden für alle bekannten Sprachen (von fileIO->corpusScanner() ermittelt) ein jeweiliges Model erzeugt. Danach wird die Ähnlichkeit eines jeden dieser Modelle zum Eingabetext ermittelt und per default die wahrscheinlichste Sprache ausgegeben.
Per Kommandozeile lassen sich diverse Parameter übergeben, die unter anderem steuern was für ein Modell erzeugt werden soll oder dass z.B. ein vorher serialisiertes Modell wieder verwendet werden soll.
Neben der init()-Methode stehen noch

identify() - liefert die wahrscheinlichste Sprache zurück - sowie
getResults() - liefert für alle Sprachen die jeweilige Sprache zurück, angefangen mit der wahrscheinlichsten

zur Verfüfung.

fileIO.py

Übernimmt alle Aufgaben aus dem Breich Datenein- und Ausgabe. Insbesondere:

DataReader() - Diese Klasse verarbeitet die Korpusdaten für die einzelnen Sprachen. Die im Verzeichnis src/corpora/ gelegen Verzeichnisse entsprechen jeweils einer eigenen Sprache, in den Verzeichnissen liegen Texte dieser Sprache. DataReader erzeugt aus den Daten einer einzelnen Sprache nun einen einzelnen String als Eingabe für das Training der Modelle. Außerdem werden unter anderem auch Stopwortlisten aus Dateien mit dem Namen stopwords.txt erzeugt.
corpusScanner() - liefert eine Liste von Sprachobjekten zurück, in Abhängikeit von den im Korpusverzeichnis gefundenen Verzeichnissen.
saveModel() - dient zum serialiseren verschiedener Objekte, vor allem von ganzen tosobap-instanzen
loadModel() - deserialisert vorhanden gespeicherte Objekte

language.py

Realisiert eine einzelne Sprache und enthält einen passenden DataReader (siehe fileIO), der allen Moduelen die mit Sprachobjekten arbeiten benutzt wird um an passende Trainings- und Testdaten zu gelangen. Außerdem werden hier die Namen der einzelnen Sprache verwaltet.

filters.py

Enthält einige Filter, die auf die Eingabedaten angewendet werden können. Unter anderem alles groß schreiben, alles klein schreiben, Sonderzeichen außerhalb ASCII rauswerfen, ...

evaluator.py

Angedachte Evaluationsklasse, in ihrer jetzigen Version leider nicht sinnvoll nutzbar.

Literatur

G. Adams, P. Resnik: A Language Identification Application Built on the Java Client/Server Platform.
S. Bastrup, C. Pöpper: Language Detection based on Unigram Analysis and Decision Trees.
K. Beesley: Language Identifier: A Computer Program for Automatic Natural-Language Identification of On-line Text.
D. Benedetto, E. Caglioti, V. Loreto: Language Trees and Zipping.
W. Cavnar, J. Trenkle: N-Gram Based Text Categorization.
T. Dunning: Statistical Identification of Language.
E. Giguet: Categorization according to Language: A step toward combining Linguistic Knowledge and Statistic Learning.
E. Giguet: Multilingual Sentence Categorization according to Language.
E. Giguet: The Stakes of multilinguality: Multilingual Text Tokenization in Natural Language Diagnosis.
G. Grefenstette: Comparing two Language Identification Schemes.
K.Y. Hung, R.W.P. Luk, D. Yeung, K.F.L. Chung, W. Shu: Detection of Language (Model) Errors.
Ch. D. Manning/ H. Schütze, 2003: Foundations of statistical natural language processing. MIT Press.
P. Sibun, A. Lawrence Spitz: Language Determination. Natural Language Processing from Scanned Document Images.

last change: 20070310 by Kai Bormann