💬 NLP

Language Identification via Compositional Data Analysis: A Linear-Time Classifier Based on Log-Ratio Geometry

This paper proposes a computationally efficient, linear-time language identification classifier that models character and bigram frequencies as compositional data using centered log-ratio (CLR) transformations and Laplace smoothing, achieving robust accuracy while offering a deterministic and interpretable alternative to resource-intensive neural architectures.

Original authors: Paul-Andrei Pogăcean, Sanda-Maria Avram

Published 2026-07-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Paul-Andrei Pogăcean, Sanda-Maria Avram

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of fingerprints or footprints, your clues are the tiny, invisible patterns of letters in a sentence. This is the world of language identification, a crucial step in computer science that helps machines figure out if a block of text is written in English, French, or perhaps a secret code. For a long time, computers have tried to solve this in two main ways. The first way is like hiring a super-smart, but very expensive and hungry, robot that needs massive amounts of electricity and memory to read every word and guess the language. The second way is like using a simple tally sheet, counting how often the letter "e" or "t" appears. While the tally sheet is fast and cheap, it has a tricky flaw: it treats language like a bag of marbles where the total number of marbles can change, but in reality, language is more like a pie chart where all the slices must always add up to exactly 100%. If you try to measure the distance between two pie charts using a standard ruler, you get confused results because the slices are all tied together. This paper asks: Can we fix the simple, fast tally sheet so it respects the "pie chart" rules, making it both quick and incredibly accurate without needing a supercomputer?

The authors of this paper, Paul-Andrei Pog˘acean and Sanda-Maria Avram, say yes. They propose a clever new method that treats language frequencies not just as simple numbers, but as compositional data—a fancy way of saying "parts of a whole that must sum to unity." To fix the "ruler" problem, they use a mathematical magic trick called the Centered Log-Ratio (CLR) transformation. Imagine you have a pie chart where the slices are stuck together; this transformation is like carefully cutting the pie and laying it flat on a table so you can measure the distance between slices without them pulling on each other. By doing this, they can use standard, fast math (Euclidean distance) to compare languages, but the math now respects the unique geometry of language.

Their approach is a "deterministic" classifier, which means it doesn't learn or guess based on training data like a neural network; it follows a strict set of rules. They built a pipeline that counts single letters (unigrams) and pairs of letters (bigrams), smooths out the data to handle missing pieces, and then applies their special geometric transformation. They tested this on six languages: English, German, Turkish, Romanian, Hungarian, and Dutch. The results are striking. For short texts (under 50 characters), their method achieves about 84.0% accuracy. As the text gets longer, the accuracy climbs steadily, hitting 95.6% for medium-length texts and a perfect 100.0% for sequences longer than 150 characters.

What makes this particularly interesting is what the paper argues against. The authors explicitly reject the idea that you need massive, expensive neural networks (which take quadratic time, or $O(L^2)$ ) to get good results. They also show that simply using standard distance measurements on raw frequency data (like the raw Euclidean distance) leads to poor results, especially for short texts, because it ignores the "pie chart" constraint. Their method, which runs in linear time ( $O(L)$ ), is much faster and requires far less computing power, making it perfect for small devices like phones or edge hardware.

However, the paper is careful to note where this method hits a wall. It works best for languages that use alphabetic systems (like the Latin alphabet). It struggles with "code-switching," where a single sentence mixes two languages, because the math assumes the text belongs to just one "pie." It also hasn't been tested on non-alphabetic systems like Chinese characters or Arabic script, where the rules for counting "letters" are totally different. But for the languages they tested, the method suggests that by respecting the geometry of language, we can build a language detector that is both lightning-fast and incredibly precise, offering a transparent, explainable alternative to the "black box" of deep learning. In short, they found that sometimes, the best way to understand a language isn't to build a bigger brain, but to measure the existing patterns with a better ruler.

Technical Summary: Language Identification via Compositional Data Analysis

Problem Statement

Language identification (LID) is a critical preprocessing step in natural language processing, yet current methodologies face a dichotomy between computational efficiency and geometric validity. While neural architectures achieve state-of-the-art accuracy, they incur quadratic time complexity ( $O(L^2)$ ) and require substantial hardware resources. Conversely, classical statistical methods using $n$ -gram frequencies offer linear-time performance ( $O(L)$ ) but suffer from a fundamental mathematical flaw: they apply standard Euclidean or Manhattan distance metrics directly to relative frequency data.

Relative frequencies are compositional data, constrained to a probability simplex where components sum to unity. As established by Aitchison, applying standard geometry to this constrained space induces spurious negative correlations and subcompositional incoherence. This paper addresses the need for a deterministic, linear-time LID classifier that respects the intrinsic geometry of compositional data, specifically targeting alphabetic systems (e.g., Latin, Cyrillic) where character overlaps create subtle statistical boundaries.

Methodology

The proposed framework formalizes language identification within the theory of Compositional Data Analysis (CoDA). The methodology proceeds through the following stages:

1. Feature Space Formalization

The system extracts unigram (character) and bigram counts from input text $T$ . These counts are normalized to form relative frequency vectors, $x^{(c)}_T$ and $x^{(b)}_T$ , which reside in their respective probability simplices ( $S^{D_c-1}$ and $S^{D_b-1}$ ). To address sparsity and mathematical singularities in the logarithmic transformation, additive Laplace smoothing is applied to all components.

2. CLR Transformation and Aitchison Geometry

To resolve geometric distortions inherent in the simplex, the paper employs the Centered Log-Ratio (CLR) transformation. This maps the constrained frequency vectors bijectively onto the $(D-1)$ -dimensional zero-sum subspace of $\mathbb{R}^D$ :
$\text{CLR}(x)_i = \ln(x_i) - \frac{1}{D} \sum_{j=1}^{D} \ln(x_j)$
In this transformed space, the standard Euclidean $\ell_2$ norm corresponds exactly to the Aitchison distance, the unique metric satisfying scale invariance, permutation invariance, and subcompositional coherence.

3. Classification Pipeline

The algorithm computes the distance between the input text's CLR-transformed vectors and pre-computed reference profiles for each target language $\ell$ . The total divergence is a weighted sum of unigram and bigram Aitchison distances:
$d_{\text{total}}(\ell) = \lambda_c d_A^{(c)}(\ell) + \lambda_b d_A^{(b)}(\ell)$
Empirical tuning determined that equal weighting ( $\lambda_c = \lambda_b = 1$ ) yields the most robust performance, allowing the naturally larger magnitude of bigram distances to drive discrimination while unigrams provide a stabilizing baseline.

4. Diacritic Adjustment

To handle short texts where diacritics are highly informative but sparse, a length-dependent adjustment term $B(L)$ is subtracted from the distance score:
$B(L) = \frac{\beta \cdot m}{1 + \alpha \cdot L}$
where $m$ is the count of matching diacritics, and $\alpha, \beta$ are hyperparameters tuned via grid search ( $\alpha=0.05, \beta=2.0$ ). This ensures high sensitivity to diacritics in short sequences while preventing over-penalization in longer texts.

The predicted language $L^*$ is the one minimizing the final score $S(\ell) = d_{\text{total}}(\ell) - B(L)$ .

Key Contributions

Geometric Correction: The paper introduces a deterministic LID classifier that replaces standard distance metrics with Aitchison geometry, rigorously addressing the "compositional data gap" in traditional frequency-based models.
Linear-Time Efficiency: The algorithm maintains $O(L)$ computational complexity, making it suitable for edge devices and real-time applications without requiring GPU acceleration or model training.
Training-Free Determinism: Unlike neural networks, the system requires no iterative training. It relies solely on fixed reference profiles and interpretable hyperparameters, ensuring full reproducibility across computing environments.
Unified Pipeline: The integration of unigram and bigram features within a single CoDA framework, coupled with a specific diacritic adjustment mechanism, provides a robust solution for distinguishing closely related languages.

Experimental Results

The framework was evaluated on six languages (English, German, Turkish, Romanian, Hungarian, Dutch) using the Language Determinism Data Set (LDDS) and the OPUS multilingual corpus.

Accuracy by Length: Performance correlates strongly with sequence length.
- Short sequences ( $L < 50$ ): Aggregate accuracy of 84.0%. Errors primarily occur between English and Dutch due to overlapping unigram distributions and lack of diacritics.
- Medium sequences ( $50 \le L \le 150$ ): Accuracy rises to 95.6%.
- Long sequences ( $L > 150$ ): The model achieves 100.0% accuracy across all evaluated languages.
Comparison to Baselines: The CoDA approach outperforms raw Euclidean and Manhattan distance baselines, particularly in sparse conditions. It matches or slightly exceeds the robustness of optimized tools like langid.py and FastText while avoiding their computational overhead.
Per-Language Performance: Turkish achieved perfect accuracy (100%) across all lengths due to distinct morphological features. Dutch and Romanian showed lower accuracy in short sequences but converged to 100% as text length increased.

Significance and Claims

The authors claim that compositional representations provide a deterministic and computationally efficient alternative to neural language identification, particularly in settings where interpretability and low resource consumption are essential.

Key claims regarding the significance of this work include:

Interpretability: Unlike opaque neural embeddings, every classification decision can be geometrically interpreted within the Aitchison simplex, facilitating transparent error analysis.
Scalability: The framework avoids retraining costs; adding a new language requires only the construction of reference frequency distributions.
Robustness: The method effectively resolves geometric distortions inherent in raw frequency analysis, offering a mathematically sound approach to statistical language profiling.

Limitations

The paper explicitly acknowledges several constraints:

Monolingual Assumption: The model assumes monolingual input. Code-switching (mixed-language texts) results in compositional vectors that are linear combinations of multiple distributions, leading to ambiguous predictions in the intermediate Aitchison space.
Script Constraints: The current implementation is optimized for alphabetic systems (Latin, Cyrillic, Greek). Extending the framework to logographic systems (e.g., Mandarin) or abjads (e.g., Arabic) is challenging due to the need for fixed shared feature spaces and the difficulty of managing dynamic dimensionality $D$ .
Short Text Sparsity: While effective for sentences and paragraphs, performance degrades for very short sequences ( $L < 50$ ) due to the inherent sparsity of empirical frequency estimates.