This paper presents the results of some experiments on using a simple algorithm, aided by a few heuristics, for the purposes of language identi cation on Twitter data. These experiments were a part of a shared task focused on this problem. The core algorithm is an n-gram based distance metric algorithm. This algorithm has previously been shown to work very well on normal text. The distance metric used is symmetric cross entropy.
Language identi cation was perhaps the
rst natural language processing task for
which a statistical method was used
successfully
Our goal was to take one of the algorithms that has been shown to work very well for normal text, add some heuristics to it, and see how far it goes in performing language identi cation for microblog data. 2
The system we have used is quite simple. There are only two components in the system. At its core there is a language identi er for normal text. The only other module is a preprocessing module. This preprocessing module implements some heuristics. There are two main heuristics implemented. The rst one is based on the knowledge that word boundaries are an important source of linguistic information that can help a language processing system perform better. We just wrap every word (more accurately, a token) inside two special symbols, one for word beginning and the other for word ending. The e ect of this heuristic is that it not only provides additional information, it also `expands' the short microblogging text a little bit, which is statistically important.
The other heuristic relates to cleaning up the data. Microblogging text, particularly Twitter text, contains extra-textual tokens such as hashtags, mentions, retweet symbols, URLs etc. This heuristic removes such extratextual tokens from the data before training as well as before language identi cation.
The intuitive basis of our algorithm is
similar to the unique n-gram based approach,
which was rst used for human identi
cation
It is worth noting that when n-grams are used for language identi cation, normally no distinction is made between orders of ngrams, that is, unigrams, bigrams and trigrams etc. are all given the same status. Further, when using vector space based distance measures, n-grams of all orders are merged together and a single vector is formed. It is this vector over which the distance measures are applied. 3
The core algorithm that we have used
The algorithm can be described as follows: 1. Train the system by preparing character based and word based (optional) n-grams from the training data. 2. Combine n-grams of all orders (Oc for characters and Ow for words). 3. Sort them by rank. 4. Prune by selecting only the top Nc character n-grams and Nw word n-grams for each language-encoding. 5. For the given test data or string, calculate the character n-gram based score simc with every model for which the system has been trained. 6. Select the t most likely language-encoding pairs (training models) based on this score. 7. For each of the t best training models, calculate the score with the test model. The score is calculated as: score = simc + a simw (1) where c and w represent character based and word based n-grams, respectively. And a is the weight given to the word based ngrams. In our experiment, this weight was 1 for the case when word n-grams were considered and 0 when they were not. 8. Select the most likely language-encoding pair out of the t ambiguous pairs, based on the combined score obtained from word and character based models.
The parameters in the above algorithm are: 1. Character based n-gram models Pc and Qc 2. Word based n-gram models Pw and Qw 3. Orders Oc and Ow of n-grams models 4. Number of retained top n-grams Nc and Nw (pruning ranks for character based and word based n-grams, respectively) 5. Number t of character based models to be disambiguated by word based models 6. Weight a of word based models
In our case, for the twitter data, we have not used word based n-grams as they do not seem to help. Adding them does not improve the results. Perhaps the reason is that there is too little data in terms of word n-grams. So the parameters for our case are: Oc = 7, Ow = 0, Nc = 1000, Nw = 0, a = 0
We used an existing implementation of this algorithm which is available as part of a library called Sanchay1 (version 0.3.0).
The parameters were selected based on repeated experiments. The ones selected are those which gave the best results. The length of n-grams was selected as 7-grams and we did nd that increasing n-gram length improves the results.
In this paper we have used this technique
for monolingual identi cation in accordance
with the task de nition, but it can be used for
multilingual identi cation
For our experiments reported here we have only used the training data provided. We have not used any other resources. We have also, so far, not used any additional tools such as a name entity recognizer. We have implemented some heuristics as described in the previous section. 5
We evaluated with two di erent setups. Before the test data for the shared task was released, we had randomly divided the training data into two sets by the usual 80-20 split: one for training and one for evaluation. We also used two evaluation methods. 1http://sanchay.co.in One was simple precision based on microaverages, while the other was using the evaluation script provided by the organizers, which was based on macroaverages. Under this setup, on repeated runs, the algorithm described earlier, out of the box, gave a (microaverages based) precision of little more than 70%. On adding the word boundary heuristic to the data, the precision increased to around 78%. On further adding the cleaning heuristic, the precision reached 80.80%. The corresponding macroaverge based F-score was 68.26%.
However, once the test data for the shared task was released and we used it with our algorithm, along with the heuristics, the (macroaverage based) F-score was 61.5%. This increased a little after we slightly improved the implementation of the preprocessing module. The corresponding microaverage based precision was 77.47%. On looking at the results for each language, we nd that the performance was best for Spanish (89.38% F-measure) and worst for Galician (33.99% F-measure). These results are presented in table-1.
Tables 2 and 3 list the most frequent
single label errors for the two cases (80-20 split
of the training data and the test set). While
some of the results are as expected, others are
surprising. For example, Galician and
Portuguese are very similar and they are
confused for one another. Similarly for
Spanish and Catalan. But it is surprising that
Catalan is identi ed as English and Basque
as Spanish. Also, Galician and Portuguese
are similar, but the results for them are
different. These discrepancies become a
little clearer if we notice the fact that the
results are quite di erent in many ways for
the two cases: the 80-20 split and the test
set. The most probable reason for these
discrepancies is that since this method is based
purely on distributional similarity, di erences
in training or testing distributions cause
unexpected errors. The fact that there is more
data available for some languages (Spanish
and Portuguese) and less for others
(Galician, Catalan and Basque), the di erence
being very large, contributes to these
discrepancies. It may also be noted that the results
were much better in terms of microaverage
based precision because in that case our
evaluation method took into account multi-label
classi cation such as `en+pt'. In fact, each
multi-label combination was treated as a
single class, both in the case of code switching
and ambiguity. As a result, many (around
half) of the errors were of such as `en' being
identi ed as `en+pt'. This also contributed
to making our results lower as evaluated by
the script provided by the organizers.
We presented the results of our experiments
on using an existing algorithm for language
identi cation on the Twitter data provided
for the shared task. We tried the algorithm
as it is and also with some heuristics. The
two main heuristics were: adding the word
boundaries to the data in the form of
special symbols and cleaning up hashtags,
mentions etc. The results were not state of the
art for Twitter data
For future work, we plan to experiment
with techniques along the lines suggested
in recent work