Warum wird bei der Textsprachenidentifikation n-Gramm anstelle von Wörtern verwendet?

12

In zwei weit verbreiteten Spracherkennungsbibliotheken, Compact Language Detector 2 für C ++ und Language Detector für Java, verwendeten beide (zeichenbasierte) n-Gramme, um Textfunktionen zu extrahieren. Warum wird ein Wortsack (einzelnes Wort / Wörterbuch) nicht verwendet, und was sind die Vor- und Nachteile von Wortsack und n-Gramm?

Was sind auch einige andere Verwendungen des n-Gramm-Modells bei der Textklassifizierung?

Oh, hoppla. Anscheinend gibt es hier eine ähnliche Frage: Bezüglich der Verwendung des Bigram-Modells (N-Gramm-Modells), um einen Merkmalsvektor für ein Textdokument zu erstellen

Aber kann jemand eine umfassendere Antwort geben? Was ist bei der Spracherkennung besser?

(Hoffentlich habe ich die Bedeutung von n-Gramm und Wortschatz richtig verstanden, haha, wenn nicht, helfen Sie mir bitte dabei.)

dennis97519
quelle

Antworten:

20

Ich denke, die detailliertesten Antworten finden sich in Mehryar Mohris umfangreicher Arbeit zu diesem Thema. Hier ist ein Link zu einer seiner Vortragsfolien zum Thema: http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

Das Problem der Spracherkennung ist, dass die menschliche Sprache (Wörter) eine Struktur hat. Im Englischen folgt der Buchstabe "u" zum Beispiel sehr häufig dem Buchstaben "q", während dies im transliterierten Arabisch nicht der Fall ist. n-Gramme erfassen diese Struktur. Daher sind bestimmte Buchstabenkombinationen in einigen Sprachen wahrscheinlicher als in anderen. Dies ist die Grundlage der n-Gramm-Klassifikation.

Bag-of-Words hingegen hängen davon ab, ob Sie ein großes Wörterbuch durchsuchen und im Wesentlichen Vorlagen abgleichen. Hier gibt es zwei Hauptnachteile: 1) Jede Sprache müsste über ein umfangreiches Wörterbuch verfügen, dessen Durchsuchung relativ lange dauern würde, und 2) Wortsäcke schlagen fehl, wenn keines der Wörter in der Datei enthalten ist Das Trainingsset ist im Test-Set enthalten.

Angenommen, Sie verwenden Bigramme (n = 2) und Ihr Alphabet enthält 26 Buchstaben, dann gibt es nur 26 ^ 2 = 676 mögliche Bigramme für dieses Alphabet, von denen viele niemals vorkommen werden. Daher benötigt das "Profil" (um die Wörter des Sprachdetektors zu verwenden) für jede Sprache eine sehr kleine Datenbank. Ein Wortsack-Klassifikator hingegen würde ein vollständiges Wörterbuch für JEDE Sprache benötigen, um zu gewährleisten, dass eine Sprache anhand des angegebenen Satzes erkannt werden kann.

Kurz gesagt: Jedes Sprachprofil kann mit einem relativ kleinen Funktionsbereich schnell erstellt werden. Interessanterweise funktionieren n-Gramm nur, weil Buchstaben nicht in einer Sprache gezeichnet werden - dies ist ausdrücklich eine Hebelwirkung.

Hinweis: Die allgemeine Gleichung für die Anzahl der n-Gramme für Wörter lautet l ^ n, wobei l die Anzahl der Buchstaben im Alphabet ist.

justanotherbrain
quelle
Ich denke, dass für einige enge Sprachen die Verwendung von Wortlisten zusätzlich zu n-Gramm hilfreich wäre. Ich habe manchmal norwegische Texte gesehen, die als dänisch klassifiziert wurden. Ich bezweifle, dass n-Gramm eine gute Möglichkeit ist, diese beiden Sprachen zu unterscheiden.
kjetil b halvorsen
Vielen Dank für Ihre ausführliche Antwort. Wie auch immer, ich habe einige Fragen dazu. Könnten Sie uns zunächst erklären, dass "jede Menge Wörter scheitern werden, wenn keines der Wörter im Trainingssatz im Testsatz enthalten ist"? und zweitens, warum verwendet CLD2 4 Gramm, was zu 456976 Einträgen für die englische Sprache führt, wenn eine Wörterbuchmethode verwendet wird, die ungefähr die Hälfte des Profils ausmacht ( oxforddictionaries.com/words/… )?
dennis97519
1
@ dennis97519 re: "Wortsack ..." Angenommen, Ihr Wörterbuch besteht nur aus den Wörtern {"Hund", "Katze", "Schildkröte", "Tier"} für Englisch und {"Perro", "Gato" , "tortuga", "animal"} für Spanisch. Ihr Wörterbuch könnte den folgenden Satz nicht klassifizieren: "Ein Esel ist ein Tier", da das Wort "Tier" in beiden Wörterbüchern vorkommt, aber keines der anderen Wörter vorhanden ist. Dies ist ein extremes Beispiel. Zu 4 Gramm: 1) Denken Sie daran, dass Sie für jede Sprache ein Wörterbuch benötigen, 2) n-Gramm sind in der Regel spärlich (schnellere Suche), und 3) wie Dougal sagte, können sie in nur wenigen Bytes dargestellt werden.
Justanotherbrain
1
@loretoparisi - Es gibt zwei Kompromisse: Das erste ist zwischen der Komplexität des Modells (großes N = komplexer) und dem Generalisierungsfehler (wie gut Sie bei einem Testsatz abschneiden) - Sie möchten nicht überanpassen. Der zweite Nachteil ist die Komplexität der Berechnungen. Die Speicherkomplexität wächst mit N exponentiell. Das Training verläuft normalerweise linear mit der Anzahl der Wörter im Text. Daher ist es normalerweise kein Problem, einen sehr langen Text zu haben. Großer Text bedeutet jedoch häufig mehr Wörter in Ihrem Wörterbuch D. Auch hier ist die Speicherkomplexität O (D ^ N). In der Praxis ist es normalerweise am besten, ein möglichst großes N zu verwenden.
Justanotherbrain
1
@loretoparisi - Wie bereits erwähnt, sind N-Gramm im Anschluss eher spärlich, aber das stimmt nicht immer. Wenn es für Ihren speziellen Text spärlich ist, ist eine Kreuzvalidierung mit unterschiedlichem N der beste Ansatz, um das optimale N zu finden (wiederum mit rechnerischen Einschränkungen).
Justanotherbrain
3

Buchstaben-N-Gramme werden aus mehreren Gründen anstelle von Wörtern verwendet:

1) Die Liste der Wörter, die für eine bestimmte Sprache benötigt werden, ist ziemlich groß, vielleicht 100.000, wenn Sie schnell, schneller, schneller, schneller, schneller, schneller, schneller, ... als alle verschiedenen Wörter betrachten. Für 80 Sprachen benötigen Sie etwa das 80-fache an Wörtern, was viel Platz einnimmt - über 50 Megabyte.

2) Die Anzahl der Buchstaben-Trigramme für ein Alphabet mit 26 Buchstaben beträgt 26 ** 3 oder ungefähr 17.000 und für Quadgramme (N = 4) ungefähr 450.000, die ALLE Sprachen abdecken, die dieses Alphabet verwenden. Ähnliche, aber etwas größere Zahlen für N-Gramme in größeren Buchstaben von 30-100 Zeichen. Für die CJK-Sprachen mit mehr als 4000 Buchstaben im Han-Skript sind Unigramme (N = 1) ausreichend. Für einige Unicode-Skripte gibt es nur eine Sprache pro Skript (Griechisch, Armenisch), sodass keine Buchstabenkombinationen erforderlich sind (sogenannte Null-Gramm-Werte N = 0).

3) Bei Wörtern haben Sie überhaupt keine Informationen, wenn Sie ein Wort außerhalb des Wörterbuchs eingeben, während Sie bei Buchstaben-N-Gramm häufig mindestens einige nützliche Buchstabenkombinationen innerhalb dieses Wortes haben.

CLD2 verwendet Quadgramme für die meisten Unicode-Skripte (Alphabete), einschließlich Latein, Kyrillisch und Arabisch, Unigramme für die CJK-Skripte, Nullgramme für andere Skripte und enthält außerdem eine begrenzte Anzahl von ziemlich unterscheidbaren und ziemlich häufigen vollständigen Wörtern und Wortpaaren zur Unterscheidung in schwierigen Gruppen statistisch ähnlicher Sprachen wie Indonesisch und Malaiisch. Buchstabenbigramme und Trigramme sind möglicherweise hilfreich, um zwischen einer kleinen Anzahl von Sprachen zu unterscheiden (ungefähr acht, siehe https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), sind aber für die Unterscheidung von Dutzenden von Sprachen unbrauchbar. Daher verwendet CLD2 Quadgramme und ordnet jeder Buchstabenkombination die drei wahrscheinlichsten Sprachen zu, die diese Kombination verwenden. Auf diese Weise können 80 Sprachen mit ca. 1,5 MB Tabellen und 160 Sprachen mit ca. 5 MB Tabellen ausführlicher behandelt werden.

Dick Sites
quelle