{'fraction_non_alphanumeric': 0.030873208975398757, 'fraction_numerical': 0.007839956745066235, 'mean_word_length': 4.7387527148619295, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Language Identification in Code-Switching Scenario

This paper describes a CRF based token level language identification system entry to Language Identification in CodeSwitched (CS) Data task of CodeSwitch 2014. Our system hinges on using conditional posterior probabilities for the individual codes (words) in code-switched data to solve the language identification task. We also experiment with other linguistically motivated language specific as well as generic features to train the CRF based sequence labeling algorithm achieving reasonable results.


Introduction
This paper describes our participation in the Language Identification in Code-Switched Data task at CodeSwitch 2014 (Solorio et al., 2014). The workshop focuses on NLP approaches for the analysis and processing of mixed-language data with a focus on intra sentential code-switching, while the shared task focuses on the identification of the language of each word in a codeswitched data, which is a prerequisite for analyzing/processing such data. Code-switching is a sociolinguistics phenomenon, where multilingual speakers switch back and forth between two or more common languages or language-varieties, in the context of a single written or spoken conversation. Natural language analysis of codeswitched (henceforth CS) data for various NLP tasks like Parsing, Machine Translation (MT), Automatic Speech Recognition (ASR), Information Retrieval (IR) and Extraction (IE) and Semantic Processing, is more complex than monolingual data. Traditional NLP techniques perform miserably when processing mixed language data. The performance degrades at a rate proportional to the amount and level of code-switching present in the data. Therefore, in order to process such data, a separate language identification component is needed, to first identify the language of individual words.
Language identification in code-switched data can be thought of as a sub-task of a document level language identification task. The latter aims to identify the language a given document is written in (Baldwin and Lui, 2010), while the former addresses the same problem, however at the token level. Although, both the problems have separate goals, they can fundamentally be modeled with a similar set of features and techniques. However, language identification at the word level is more challenging than a typical document level language identification problem. The number of features available at document level is much higher than at word level. The available features for word level identification are word morphology, syllable structure and phonemic (letter) inventory of the language(s). Since these features are related to the structure of a word, letter based n-gram models have been reported to give reasonably accurate and comparable results (Dunning, 1994;Elfardy and Diab, 2012;King and Abney, 2013;Nguyen and Dogruoz, 2014;Lui et al., 2014). In this work, we present a token level language identification system which mainly hinges on the posterior probabilities computed using n-gram based language models.
The rest of the paper is organized as follows: In Section 2, we discuss about the data of the shared task. In Section 3, we discuss the methodology we adapted to address the problem of language identification, in detail. Experiments based on our methodology are discussed in Section 4. In Section 5, we present the results obtained, with a brief discussion. Finally we conclude in Section 6 with some future directions.

Data
The Language Identification in the Code-Switched (CS) data shared task is meant for language identification in 4 language pairs (henceforth LP) namely, Nepali-English (N-E), Spanish-English (S-E), Mandarin-English (M-E) and Modern Standard Arabic-Arabic dialects (MSA-A). So as to get familiar with the training and testing data, trial data sets consisting of 20 tweets each, corresponding to all the language-pairs, were first released. Additional test data as "surprise genre" for S-E, N-E and MSA-A were also released, which comprised of data from Facebook, blogs and Arabic commentaries.

Tag Description
Each word in the training data is classified into one of the 6 different classes which are, Lang1, Lang2, Mixed, Other, Ambiguous and NE. "Lang1" and "Lang2" tags correspond to words specific to the languages in an LP. "Mixed" words are those words that are partially in both the languages. "Ambiguous" words are the ones that could belong to either of the language. All gibberish and unintelligible words and words that do not belong to any of the languages fall under "Other" category. "Named Entities" (NE) comprise of proper names that refer to people, places, organizations, locations, movie titles and song titles etc.

Data Format and Data Crawling
Due to Twitter policies, distributing the data directly is not possible in the shared task and thus the trial, training and testing data are provided as char offsets with label information along with tweetID 1 and userID 2 . We use twitter 3 python script to crawl the tweets and our own python script to further tokenize and synchronize the tags in the data.
Since the data for "surprise genre" comes from different social media sources, the ID format varies from file to file but all the other details are kept as is. In addition to the details, the tokens referenced by the offsets are provided unlike Twitter data. (1) and (2) below, show the format of tweets in train and test data respectively, while (3) shows a typical tweet in the surprise genre data.

Data Statistics
The CS data is divided into two types of tweets (henceforth posts) 4 namely, Code-switched posts and Monolingual posts. Table 1 shows the original number of posts that are released for the shared task for all LPs, along with their tag counts. Due to the dynamic nature of social media, the posts can be either deleted or updated and thus different participants would have crawled different number of posts. Thus, to come up with a comparable platform for all the teams, the intersection of data from all the users is used as final testing data to report the results. Table 1 shows the number of tweets or posts in testing data that are finally used for the evaluation.

Methodology
We divided the language identification task into a pipeline of 3 sub-tasks namely Pre-Processing, Language Modeling, and Sequence labeling using CRF 5 . The pipeline is followed for all the LPs with some LP specific variations in selecting the most relevant features to boost the results.

Pre-Processing
In the pre-processing stage, we crawl the tweets from Twitter given their offsets in the training data and then tokenize and synchronize the words with their tags as mentioned in Section 2.2. For each LP we separate out the tokens into six classes to use the data for Language Modeling and also to manually analyze the language specific properties to be used as features further in sequence labeling . While synchronizing the words in a tweet with their tags, we observed that some offsets do not match with the words and this would lead to mismatch of labels with tokens and thus degrade the quality of training data.
To filter out the incorrect instances from the training data, we frame pattern matching rules which are specific to the languages present. But this filtering is done only for the words present in   Table 1, and thus have a higher impact on the overall accuracy of the language identification system. In addition to the above, these categories correspond to the focus point of the shared task. Second, for 'Ambiguous', 'NE' and 'Other' categories, it is difficult to find the patterns according to their definitions. Although rules can be framed for 'Mixed' category, since their count is too less as compared to the other categories (Table 1), it is of no use to train a separate language model with very less number of instances.
For Mandarin and Arabic data sets, any word present in Roman script is excluded from the data. Similarly for English and Nepali, if any word contains characters other than Roman or numeral they are excluded from the data. In addition to the rule for English and Nepali, the additional alphabets in Spanish are also included in the set of Roman and numeral entries. Table 2 shows the number of words that remained in each of the languages/dialects, after the preprocessing.
One of the bonus points in the shared task is that 3 out of 4 LPs share 'English' as their second language. In order to increase the training size for English, we merged all the English words into a single file and thus reduced the number of language models to be trained from 8 to 6, one for each language (or dialect).

Language Modeling
In this stage, we train separate smoothed n-gram based language models for each language in an LP. We compute the conditional probability for each word using these language models, which is then used as a feature, among others for sequence labeling to finally predict the tags.

N-gram Language Models
Given a word w, we compute the conditional probability corresponding to k 6 classes c 1 , c 2 , ... , c k as: The prior distribution p(c) of a class is estimated from the respective training sets shown in Table 2. Each training set is used to train a separate letter-based language model to estimate the probability of word w. The language model p(w) is implemented as an n-gram model using the IRSTLM-Toolkit (Federico et al., 2008) with Kneser-Ney smoothing. The language model is defined as: where l is a letter and k is a parameter indicating the amount of context used (e.g., k=4 means 5gram model).

CRF based Sequence Labeling
After Language Modeling, we use CRF-based (Conditional Random Fields (Lafferty et al., 2001)) sequence labeling to predict the labels of words in their surrounding context. The CRF algorithm predicts the class of a word in its surrounding context taking into account other features not explicitly represented in its structure.

Feature Set
In order to train CRF models, we define a feature set which is a hybrid combination of three subtypes of features namely, Language Model Fea-

tures (LMF), Language Specific Features (LSF) and Morphological Features (MF).
LMF: This sub-feature set consists of posterior probability scores calculated using language models for each language in an LP. Although we trained language models only for 'Lang1' and 'Lang2' classes, we computed the probability scores for all the words belonging to any of the categories.
LSF: Each language carries some specific traits that could assist in language identification. In this sub-feature set we exploited some of the language specific features exclusively based on the description of the tags provided. The common features for all the LPs are HAS NUM (Numeral is present in the word), HAS PUNC (Punctuation is present in the word), IS NUM (Word is a numeral), IS PUNC (word is a punctuation or a collection of punctuations), STARTS NUM (word starts with a numeral) and STARTS PUNC (word starts with a punctuation). All these features are used to generate variations to distinguish 'Other' class from rest of the classes during prediction. Two features exclusively used for the English sharing LPs are HAS CAPITAL (capital letters are present in the word) and IS ENGLISH (word belongs to English or not). HAS CAPITAL is used to capture the capitalization property of the English writing system. This feature is expected to help in the identification of 'NEs'. IS ENGLISH is used to indicate whether a word is an valid English word or not, based on its presence in English dictionaries. We used dictionaries available in PyEnchant 7 .
For the M-E LP, we are using 'TYPE' 8 as a feature with possible values as ENGLISH, MAN-DARIN, NUM, PUNC and OTHER. If all the characters in the word are English alphabets EN-GLISH is taken as the value and Mandarin otherwise. Similar checks are used for NUM and PUNC types. But if no case is satisfied, OTHER is taken as the value.
We observed that the above features did not contribute much to distinguish between any of the tags in case of the MSA-A LP. Since this pair consists of two different dialects of a language rather than two different languages, the posterior probabilities would be close to each other as compared to other LPs. Thus we use the difference of these probabilities as a feature in order to discriminate ambiguous words or NEs that are spelled similarly.
MF: This sub-feature set comprises of the morphological features corresponding to a word. We automatically extracted these features using a python script. The first feature of this set is a binary length variable (MORE/LESS) depending on the length of the word with threshold value 4. The other 8 features capture the prefix and suffix properties of a word, 4 for each type. In prefix type, 4, 3, 2 and 1 characters, if present, are taken from the beginning of a word as 4 features. Similarly for the suffix type, 1, 2, 3 and 4 characters, again if present, are taken from the end of a word as 4 features. In both the cases if any value is missing, it is kept as NULL (LL). (4) below, shows a typical example from English data with the MF sub-feature set for the word 'one', where F1 represents the value of binary length variable, F2-F5 and F6-F9 represent the prefix and suffix features respectively.

Context Window
Along with the above mentioned features, we chose an optimal context template to train the CRF models. We selected the window size to be 5, with 2 words before and after the target word. Furnishing the training, testing and surprise genre data with the features discussed in 3.3.1, we trained 4 CRF models on training data using feature templates based on the context decided. These models are used to finally predict the tags on the testing and surprise genre data.

Experiments
The pipeline mentioned in Section 3 was used for the language identification task for all the LPs. We carried out a series of experiments with preprocessing to clean the training data and also to synchronize the testing data. We also did some post-processing to handle language and tag specific cases.
In order to generate language model scores, we trained 6 language models (one for each language/dialect) on the filtered-out training data as mentioned in Table 2. We experimented with different values of n-gram to select the optimal value based on the F1-measure. Table 3 shows the optimal order of n-gram, selected corresponding to the highest value of F1-score. Using the optimal value of n-gram, language models have been trained and then posterior probabilities have been calculated using equation (1).
Finally, we trained separate CRF models for each LP, using the CRF++ 9 tool kit based on the features described in Section 3.3.1 and the feature template in Section 3.3.2. To empirically find the relevance of features we also performed leave-one out experiments so as to decide the optimal features for the language identification task (more details in Section 4.1). Then, using these CRF models, tags were predicted on the testing and surprise genre datasets. We expect that some features would be more important than others and would impact the task 9 http://crfpp.googlecode.com/svn/trunk/doc/index.html? source=navbar of language identification irrespective of the language pair. In order to identify such optimal features for the language identification task, we rank them based on their information gain scores.

Information Gain
We used information gain to score features according to their expected usefulness for the task at hand. Information gain is an information theoretic concept that measures the amount of knowledge that is gained about a given class by having access to a particular feature. If f is the occurrence an individual feature andf the non-occurrence of a feature, information gain can be measured by the following formula: For each language pair, the importance of feature types are represented by the following order: • MSA-A dialects: token > word morphology > posterior probabilities > others • Mandarin-English: token > posterior probabilities > word morphology > language type > others • Nepali-English: token > posterior probabilities > word morphology > dictionary > others • Spanish-English: token > posterior probabilities > word morphology > others > dictionary Apart from MSA-A dialects, top 3 features suggested by information gain are token and its surrounding context, posterior probabilities and word morphology. For Arabic dialects word morphology is more important than posterior probabilities. It could be due to the fact that Arabic dialects share a similar phonetic inventory and thus have similar posterior probabilities. However, they differ significantly in their morphological structure (Zaidan and Callison-Burch, 2013). We also carried out leave-one-out experiments over all the features to ascertain their impact on the classification performance. The results of these experiments are shown in Table (5). Accuracies are averaged over 5-fold cross-validation.

Results and Discussion
Each language identification system is evaluated against two data tracks namely, 'Testing' and 'Surprise Genre' data as mentioned in Section 2. Surprise genre data of Mandarin-English LP was not provided, so no results are available. All the results are provided on two levels, comment/post/tweet and token level. Tables 4 and 6 show results of our language identification system on both the levels respectively. In case of Tweets, systems are evaluated using the following measures: Accuracy, Recall, Precision and F-Score. However at token level, systems are evaluated separately for each tag in an LP using Recall, Precision and F1-Score as the measures. Table 4 shows that the results for 'Ambiguous' and 'Mixed' categories are either missing (due to absence of tokens in that category), or have 0.00 F1-Score. One obvious reason could be the sparsity of data for these categories.

Conclusion and Future Work
In this paper, we have described a CRF based token level language identification system that uses a set of naive easily computable features guaranteeing reasonable accuracies over multiple language pairs. Our analysis showed that the most important  feature is the word structure which in our system is captured by n-gram posterior probabilities and word morphology. Our analysis of Arabic dialects shows that word morphology plays an important role in the identification of mixed codes of closely related languages.