Automated language identification
written and developed by Thomas Pietraho
It was a bright cold day in April, and the clocks were striking thirteen.
C’était une journée d’avril froide et claire. Les horloges sonnaient treize heures.
Era un día luminoso y frío de abril y los relojes daban las trece.
Es war ein klarer, kalter Apriltag, und die Uhren schlugen dreizehn.
Oli kirkas, kylmä huhtikuun päivä, ja kellot löivät kolmetoista.
Derült, hideg áprilisi nap volt, és az órák éppen tizenhármat ütöttek.
Hôm ấy là một ngày tháng Tư trời quang và lạnh giá, và những chiếc đồng hồ đang điểm mười ba tiếng.
Był jasny, zimny dzień kwietniowy i zegary biły trzynastą.
Ilikuwa siku angavu na baridi ya mwezi wa Aprili, na saa zilikuwa zikipiga kumi na tatu.
Soğuk ve güneşli bir nisan günüydü, saatler on üçü vuruyordu.
Era una luminosa e fredda giornata d’aprile, e gli orologi battevano tredici colpi.
Het was een heldere, koude dag in april en de klokken sloegen dertien.
Það var bjartur, kaldur dagur í apríl og klukkurnar slógu þrettán.
Is there an efficient way to identify the language in which a document is written?
A common and fairly important machine learning task is to identify the language of a document or a snippet of text. There are many solutions to this problem, but the goal of this lab exercise is to introduce you to a particularly efficient one. Our algorithm has one important limitation: it will only work for languages that are based on the Latin script used when writing English.
The vector of digraphs
A common approach in machine learning is to represent the objects of study as numerical vectors called feature vectors. So we are faced with the following question:
Question: Suppose you are given a sample of text written in a language that uses the Latin alphabet. Find a way of representing it as a numerical vector.
As machine learning has evolved, many ways to do this have been developed. We will study a particularly simple and efficient one. It begins with the following notion:
Definition: A digraph is a pair of consecutive letters that appear in a sample of text. Since the Latin alphabet has 26 letters, there are 676 possible digraphs. The digraph vector \(\vec{v}\) of a text sample counts how many times each digraph appears therein. It is a vector in \(\mathbb{R}^{676}\).
For example, consider the sentence I like homework. The first digraph is li, the second is ik, and the others are ke, ho, om, me, ew, wo, or, and rk. To construct the digraph vector, we must count the number of times each digraph appears in the text. Its first coordinate is the number of occurrences of the digraph aa, the second of ab, and so on; the last coordinate counts occurrences of the digraph zz. Try a sentence of your own:
As a more interesting example, here is the digraph vector of a longer English text, the opening of the Wikipedia article on mathematics, written out coordinate by coordinate from aa to zz. Scroll through it; the zero entries are dimmed.
The digraph vector of the English Wikipedia article Mathematics. Apparently mathematicians mention neither aardvarks nor pizza.
For languages that use slight modifications of the Latin alphabet, say by incorporating letters such as Ç, É, or Ñ, the digraph vector is formed by using the closest Latin letter for each; for instance, N instead of Ñ. The tools on this page do that automatically.
Comparing digraph vectors
Now suppose that we computed the digraph vectors for two different documents, say \(\vec{v}\) and \(\vec{w}\). We would like to decide whether or not the two text samples were written in the same language. This raises the following question:
Question: How should we measure similarity between digraph vectors so that text samples written in the same language are close to each other, and text samples written in different languages are far from each other?
Again, there are numerous approaches to this question. We will study one method that is especially useful in a variety of other machine learning tasks.
Definition: The cosine similarity score of two feature vectors is the angle \(\theta\) between the two vectors. We can use the dot product to compute it.
Before working with real data, let us decide whether the cosine similarity score has a chance of working in our task. Think about the following questions before proceeding.
Exercises:
- What is the cosine similarity score for two identical copies of the same text sample? What if the second text sample is formed by cutting-and-pasting the first sample three times?
- What would you expect the cosine similarity score to be if the two text samples were written in the same language? Why?
- What would you expect the cosine similarity score to be if the two text samples were written in two very different languages? Why?
Based on your answers to the above questions, is it reasonable to expect that the cosine similarity score might work for the language recognition task?
Language recognition using digraph vectors
We are ready for the main part of the lab. Our first goal is to get a feel for what kind of values one should expect as cosine similarity scores for text samples written in the same language, which angles occur for documents written in related languages, and what scores occur between unrelated languages. For our data set, we will use the texts of Wikipedia articles; they are available in a variety of languages.
The workbench below fetches random Wikipedia articles in a language you choose and computes their digraph vectors. If you type a topic, it searches that Wikipedia for the topic and picks one of the matching articles at random instead, so you can control what your samples are about. It gives you a small calculator that knows how to take dot products, square roots, and inverse cosines, but you will have to use our work from class to put those together into the cosine similarity score yourself.
1 · Collect text samples
First, we need to find some text samples and compute the digraph vectors.
- First, find four articles written in English.
- Then find four articles written in a language similar to English.
- Finally, find four articles written in a language that is not closely related to English.
characters
2 · Compute the angle
Once we have found the digraph vectors, we will need to compute the angles between them.
- First, select vectors v and w from the pull-down menus.
- Then, compute the angle between them. You should use the functions below to help.
Hints: Write one formula for the angle in terms of v and w, then reuse it by changing v and w. You should compute the magnitude of a vector using the dot product; what is the dot product of a vector with itself?
What these do
dot(a, b) is the dot product of two digraph vectors; a·b or a.b also works.sqrt(x) is the square root.acos(x) is the inverse cosine, and it answers in radians; arccos(x) and cos^-1(x) mean the same, and cos(x) also works.deg(x) converts radians to degrees, and rad(x) goes the other way. pi is π.v and w are the two vectors chosen above; any sample can also be named directly, e.g. fr1 for fr-1.- Type an expression and press Enter. As you type, the line below the box shows how it will be read.
- You can name intermediate results, for example
d = dot(v, w), and use them on later lines.
- A parenthesis you forget to close at the end is closed for you. Put the cursor next to a parenthesis to see its partner.
3 · Check and record
Check your computation, and if it is correct, record it for analysis later. The angle will appear in a table of the Results section with your other successful computations.
Questions to think about:
Think about the following questions as you work through the lab.
- What angle should you expect for text samples written in English? What was the average angle in your computations above? The largest? The smallest?
- Is your answer to the first question the same if your documents are all written in some other language?
- Based on your work so far, what range of scores do you expect for text samples both of which are written in the same language?
- Now consider text samples from languages closely related to English, perhaps French, Spanish, or German. What is the range of the cosine similarity scores between these text samples and English text samples?
- Now consider text samples from languages that are not closely related to English. Some examples are Finnish, Hungarian, and Vietnamese, but there are many others. What is the range of cosine similarity scores between these text samples and those from English?
- What are your conclusions? Is the digraph vector effective at the language recognition task?
The final problem related to this lab asks you to extend your observations to formulate a more complete language recognition algorithm.
Homework exercise: Using observations from your work above, describe an algorithm that a computer could use to detect the language of a text sample. To be more precise:
- assume that you are given a text document written in some language, your job is to identify it, and
- you are allowed to pre-compute anything you would like from a large database of text samples written in known languages.
In your write-up, outline the algorithm you propose and using evidence from this lab explain why you expect that this algorithm should work. Two or three detailed paragraphs should be sufficient.
The complaint tablet to Ea-nāṣir, written in Akkadian cuneiform around 1750 BC. In it, a customer named Nanni objects that the copper he was delivered was the wrong grade and that his messenger was treated rudely. Sadly, cuneiform is not written in a Latin script, so our language identification algorithm does not apply. But if we had data from Sumerian, Akkadian, Hittite, Elamite, Hurrian, Uratian, Luwian, and Eblaite; all of which used cuneiform, then we could develop a similar one. British Museum; photo by Joel Bellviure, CC BY 4.0.