A study of n-gram and decision tree letter language modeling methods

It is concluded that the bottom-up deleted interpolation algorithm performs the best in the task of n -gram letter language model smoothing, significantly outperforming the back-off smoothing technique for large values of n .

Abstract

The goal of this paper is to investigate various language model smoothing techniques and decision tree based language model design algorithms. For this purpose, we build language models for printable characters (letters), based on the Brown corpus. We consider two classes of models for the text generation process: the n-gram language model and various decision tree based language models. In the first part of the paper, we compare the most popular smoothing algorithms applied to the former. We conclude that the bottom-up deleted interpolation algorithm performs the best in the task of n-gram letter language model smoothing, significantly outperforming the back-off smoothing technique for large values of n. In the second part of the paper, we consider various decision tree development algorithms. Among them, a K-means clustering type algorithm for the design of the decision tree questions gives the best results. However, the n-gram language model outperforms the decision tree language models for letter language modeling. We believe that this is due to the predictive nature of letter strings, which seems to be naturally modeled by n-grams. Das Ziel dieses Beitrags ist verschiedene Techniken zur Glättung von Sprachmodellen und Algorithmen zum Entwurf von Sprachmodellen auf der Basis von Entscheidungsbäumen zu untersuchen. Zu diesem Zweck verwenden wir den Brown-Korpus um Modelle von Buchstabenfolgen zu erstellen. Wir betrachten zwei Klassen von Modellen zur Textgenerierung: das n-Gramm Sprachmodell sowie verschiedene auf Entscheidungsbäumen basierende Verfahren. Im ersten Teil dieses Beitrags vergleichen wir die am häufigsten benutzten Glättungsalgorithmen angewandt auf n-Gramme. Wir folgern, daß der “bottom-up deleted interpolation”-Algorithmus am besten zur Glättung von n-Gramm Sprachmodellen geeignet ist und für große n dem “back-off”-Verfahren deutlich überlegen ist. Im zweiten Teil dieses Beitrags betrachten wir dann verschiedene Algorithmen zur Bildung von Entscheidungsbäumen. Unter diesen erzielt ein K-means-ähnlicher Algorithmus die besten Ergebnisse beim Entwurf der Fragen die der Entscheidungsbaum stellt. Für die Modellierung von Buchstabenfolgen erzielt das n-Gramm Sprachmodell aber trotzdem noch bessere Ergebnisse als alle Entscheidungsbäume. Wir glauben, daß dies durch die Fähigkeit der n-Gramme Buchstabenfolgen vorherzusagen begründet ist. Le but de cet article est d'étudier différentes techniques de lissage de modèles de langage et différents algorithmes de construction de modèles de langage à base d'arbres de décision. Pour cela, nous construisons des modèles de langage pour des caractères écrits (lettres) à partir du Brown corpus. Nous considérons deux classes de modèles pour le processus de génération du texte: le modèle de langage n-gram, et différents modèles de langage à base d'arbres de décision. Dans la première partie de l'article, nous comparons les algorithmes de lissage les plus couramment appliqués au modèle de langage n-gram. L'algorithme “bottom-up deleted interpolation” donne les meilleurs résultats pour le lissage du modèle de langage n-gram, dépassant de façon significative la technique de lissage “back-off” pour de grandes valeurs de n. Dans la seconde partie de l'article, nous considérons différents algorithmes de développement d'arbres de décision. Parmi eux, un algorithme de type classification K-means aboutit aux meilleurs résultats pour la construction des arbres de décision. Cependant, le modèle de langage n-gram fournit de meilleurs résultats que les modèles de langage à arbres de décision pour la modélisation du langage écrit. Nous croyons que cela est dû à la nature prédictive des chaı̂nes de caractères, qui semble être naturellement modélisée par les n-grams.