Is it feasible to use k-Nearest Neighbours to identify text language?

Question

I have seen various language identification libraries that claim to use naive Bayes classifier for text language identification, like CLD2 and language detector, but not any library that uses other algorithms.

I wrote a simple program that uses 1-NN with Euclidian distance measure for identifying language of texts. The features I have chosen are the occurrence of each word, or n-grams, where n can be anything from 1 to 4. I trained it with a few paragraphs of English and French text from some novels, and then put in some random (short) sections of text from English and French Wikipedia respectively. It turned out that when using whole words or n-grams with n above 2 as features, it detects correctly.

Update: When using cosine similarity measure, even 1-gram and 2-gram feature detected correctly. Also I added both whole passage without splitting at line breaks and paragraphs(strings splitting at line breaks) as training sample.

Also, when I used each paragraph from the novels as training sample data points, the algorithm detected the languages of the unseen text correctly under the conditions stated above(whole words or n-grams with n greater than 2). However, when I used the whole section of multiple paragraphs as one training sample, the shorter french novel text (about half of the length of the English text) seems to have caused both the English and Frech Wikipedia short text to be identified as French.

Update: So, it seems like document length affects the results more than word occurrence when using Euclidean distance. While for cosine similarity, using a longer passage that contains more comprehensive vocabulary/letters/n-grams as training sample improved the accuracy.

Update: When I added sections of Mein Kampf as training text both Euclidean distance metric and cosine similarity detected two short French and English text as German when using 4-grams O.O. Also the similarity values doesn't seem to differ by a lot.

So,

• Why do most of the libraries use naive Bayes classifier? Is it more suitable for this purpose?
• Is it feasible to use k-NN for language identification? If yes, is there any advantage in using this over naive Bayes classifier? If not, why?
• What other types of features could I have used, other than term frequency?
• Would binary model(record of whether a term exists or not) features suffice for this purpose?
• What is the best similarity/dissimilarity metric to use for this particular purpose?
• Will k-d tree or k-d tree with best bin first approach help in speeding up the detection when there is a large training sample base? (There is likely to be hundreds of thousands of dimensions/features :P)
• If cosine similarity distance metric is used, what data structure/algorithm could be used to reduce the time complexity of language detection? Can angles be precomputed, LSH be used, or k-d tree be used?

Please answer below as long as you know any of the sub-questions, or can provide an analysis to the above phenomenon mentioned :)

I'm not sure if I should put all the above questions in one. If not, please tell me and I will move the unrelated ones into a separate question.

Answer 1

Perhaps one reason that NB is used is that it's a very simple method that gets extremely high accuracy. I mean, extremely high. Detecting a language is not really an "open problem" any more. Perhaps, as someone mentioned, it may be worth trying to improve classification between very similar dialects or something.

Here is a report on research towards distinguishing Serbian from Croatian, Mandarin from Taiwan vs. mainland China, Indonesian vs. Malay,Portuguese from Brazil vs. Portugal, etc. State of the art accuracy for most of these is around 99%.

Answer 2

A drawback of k-NN is that it needs to compute the distance to all classified observations to identify its nearest neighbours: the approach is not parametric. The biggest issue to overcome with the k-NN approach is speed and memory. An experiment might prove interesting. Even if k-NN turns out slower, the approach could have merits if the detection is more precise.

Answer 3

I think in a SAX variation of the approach it might work. Maybe. Irish vs. English is going to be tough. Irish vs. Klingon might be higher yield.

If you treat each letter as a symbol, and compute the frequency of next letters. Assembled together it makes a matrix of transition probabilities. The transition probability can be considered an inverse distance. One could do clustering in that space. Personally, if I had a collection of documents or languages that I was trying to uniquely identify, I might perform PCA before performing clustering in the space. This would help to accentuate the signal.

It is likely that languages have strong overlap. There are only 128 phonemes produced by the human vocal aparatus. This means your max transition matrix is 128x128. This is why centering, detrending, then rotating in the distance-domain before performing clustering is likely to have better results.

Best of luck.

EDIT:

• Each language tends to use about 60 or so of the phonemes, so what they tend to do is amoeba (fun verb, huh?) the unused 60 or so phonemes into the used ones. The problem is that the amoeba is not universal. Dialects are a case where the main sounds are similar, but amoeba-ing is different. If you were working in sound, not written text, this would be a decent approach. There are translators to convert written text into phonetic text. The more advanced ones will take into account some subset of the prosody.
• SAX -- http://www.cs.ucr.edu/~eamonn/SAX.htm
• PCA and mahalanobis distance -- Bottom to top explanation of the Mahalanobis distance?
• center and scale means one first subtracts the central tendency (like mean, median, or mode) then fits the inputs/outputs to a simple linear model, then subtract the linear model from the data, and work the advanced stuff on the difference. This keeps the fancy tools from doing the simple work and thinking they are done - it makes them work, if they can, for a living.

EDIT2:

• Why do most of the libraries use naive Bayes classifier? Is it more suitable for this purpose?

My guess is because it works. Data Scientists love methods that do the job.

• Is it feasible to use k-NN for language identification? If yes, is there any advantage in using this over naive Bayes classifier? If not, why?

Feasible? I think my previous material gives a sense that it could work. Advantageous? Those folks using Naive Bayes turned over a number of stones to come up with the solution they have. KNN is going to be "low-hanging fruit". Unless you have a novel transform to change the space (SAX+PCA) or such, there isn't much chance of beating the current tool.

• What other types of features could I have used, other than term frequency?

Two-term frequency? Three-term frequency. N-term frequency. Auto-regressive (skip-term) analogs of the previous. Combinations of the previous. Transform to phoneme, then repeat the previous. we know Baidu uses Deep Belief Networks. You could try and do a "poor man's knock-off" by training it on libraries of known works. You could use some form of cosine-distance meets gradient boosted tree.

• Would binary model(record of whether a term exists or not) features suffice for this purpose?

You mean multivariate logistic regression? It might have some level of function. It is going to take a long time to "train".

• What is the best similarity/dissimilarity metric to use for this particular purpose?

There are many breeds of best. Some "bests" are mutually exclusive. What do you mean by best? Best path might be shortest path, unless you are going to your execution, in which case longest path or most pleasant by longest path might be more desirable. Many "bests" are mutually exclusive - time optimal tends to use the most fuel while fuel optimal tends to take the longest time. There are many families with infinite sub-members where each member is a variation on "best". Consider a weighted linear interpolation between time-optimal and fuel-optimal. The line between them has an infinite number of points, and each place on that line comprises a version of "optimal" or "best". Adding constraints like maximum time below a threshold changes the entire space, and makes the space of bests to be 2-dimensional.

• Will k-d tree or k-d tree with best bin first approach help in speeding up the detection when there is a large training sample base? (There is likely to be hundreds of thousands of dimensions/features :P)

I would think there would be millions of dimensions. Again the Baidu spoken word autoencoder suggests that.

• If cosine similarity distance metric is used, what data structure/algorithm could be used to reduce the time complexity of language detection? Can angles be precomputed, LSH be used, or k-d tree be used?

I work more with engineering data than words, so I can't answer this.