⚡ electrical engineering

Recovering the Zipfian Distribution in Unsupervised Term Discovery

This paper demonstrates that graph-based clustering, specifically using the Leiden algorithm, outperforms traditional center-based methods like K-means in unsupervised term discovery by generating lexicons with more natural Zipfian distributions across multiple languages.

Original authors: Danel Slabbert, Simon Malan, Herman Kamper

Published 2026-06-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Danel Slabbert, Simon Malan, Herman Kamper

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 handed a giant, unlabelled audio tape of people speaking a language you don't know. Your goal is to figure out what the "words" are and build a dictionary just by listening. This is the challenge of unsupervised term discovery.

The researchers at Stellenbosch University tackled a specific problem with how computers usually try to solve this: the way they group sounds together is wrong.

Here is the breakdown of their findings using simple analogies.

The Problem: The "Cookie Cutter" Mistake

Most computers use a method called K-means to group sounds. Think of K-means like a baker using a round cookie cutter. No matter how much dough you have, the cutter forces every cookie to be roughly the same size and shape.

In language, this is a disaster. In real life, a few words (like "the" or "and") are used thousands of times, while most words are used only a few times. This is called a Zipfian distribution (a long tail of rare items).

The Reality: A few huge piles of common words, many tiny piles of rare words.
The K-means Mistake: Because the "cookie cutter" forces everything to be the same size, it chops up the big piles of common words into tiny, equal-sized chunks. The result is a dictionary where every word seems to appear the same number of times, which doesn't match how humans actually speak.

The Solution: The "Social Network" Approach

The authors tested a different way of grouping sounds, called Graph Clustering. Instead of forcing sounds into pre-sized buckets, imagine you are at a party and you want to find groups of people who know each other.

The Connection: You draw a line between two people if they seem to know each other (based on how similar their speech sounds are).
The Clusters: You look for "cliques"—groups of people where everyone is connected to everyone else.
The Result: Some cliques are huge (the popular kids who know everyone), and some are tiny (a quiet corner with just two people). This naturally creates the "long tail" distribution that matches real language.

They also tested a second method called Agglomerative Clustering, which is like building a family tree. You start with individual sounds and slowly merge the two most similar ones together, step by step, until you have your groups. This also worked well, though it was slower to compute.

The Experiment: Three Languages, Three Tests

To prove their point, they ran tests on three languages: English, Afrikaans, and French. They used a smart AI model (trained on English) to listen to the sounds, but they tested it on all three languages to see if the method worked even when the computer didn't "know" the language perfectly.

They tested three different ways of cutting the audio into pieces:

Perfect Words: Using a "gold standard" where they knew exactly where every word started and ended.
Perfect Syllables: Using the building blocks of words (like "ba-na-na").
Rough Guesses: Using a computer's best guess to find syllables (which is often messy).

The Results: The "Social Network" Wins

Across all three languages and all three ways of cutting the audio, the Graph Clustering and Agglomerative Clustering methods beat the standard "cookie cutter" (K-means) method every time.

Better Dictionary: The dictionaries created by the new methods looked much more like real human language. They had the right mix of very common words and rare words.
Efficiency: The graph method was also faster than the "family tree" method.
Control: The graph method gave the researchers a "volume knob" (a setting they could tweak) to decide how strict or loose they wanted the groups to be, allowing them to fine-tune the dictionary size.

The Bottom Line

The paper argues that the computer science community has been relying too heavily on the "cookie cutter" approach (K-means) for too long. By switching to a "social network" approach (Graph Clustering), we can build much better, more natural-sounding dictionaries for computers that are learning languages from scratch, without needing a human to teach them the rules first.

In short: If you want a computer to learn a language naturally, stop forcing its groups to be the same size. Let the groups form naturally based on who "knows" whom, and you'll get a much better result.

Problem Statement
Unsupervised term discovery aims to build a lexicon from unlabelled speech by identifying acoustic boundaries and clustering the resulting segments into phonetically homogeneous groups. While true natural language lexicons follow a long-tailed Zipfian distribution (where a few types are very frequent and many are rare), dominant unsupervised approaches fail to recover this structure. Specifically, the widely adopted centre-based clustering method, K-means, possesses an inductive bias toward similarly sized, compact clusters. This results in a near-uniform type-frequency distribution that poorly aligns with the statistical properties of natural language. The paper investigates whether alternative clustering methods with different inductive biases can recover the Zipfian distribution in unsupervised lexicon induction.

Methodology
The authors follow the standard three-stage unsupervised term discovery pipeline: segmentation, representation, and clustering.

Representation: The study utilizes fixed-dimensional embeddings derived from the 21st layer of WavLM Large (trained on English). Segment embeddings are created by averaging time-aligned features after PCA reduction and normalization.
Segmentation: Experiments are conducted under three conditions to isolate the effect of clustering: ground-truth word boundaries, ground-truth syllable boundaries, and unsupervised syllabic boundaries (using the ZeroSyl method).
Clustering Comparison: The paper compares five methods:
- Centre-based: K-means, BIRCH, and Finite Bayesian Gaussian Mixture Models (FBGMM). These represent clusters via centroids or parametric components.
- Bottom-up: Graph clustering and Agglomerative clustering (average linkage). These build clusters based on pairwise relationships between segment embeddings.
Graph Clustering Specifics: This approach constructs a similarity graph where edges exist if cosine similarity exceeds a threshold ( $\tau$ ). The graph is partitioned using the Leiden algorithm with a Constant Potts Model (CPM) objective, controlled by a resolution parameter ( $\gamma$ ). This allows for explicit control over cluster granularity and distribution shape.
Evaluation: The methods are evaluated on English, Afrikaans, and French. Metrics include Normalized Edit Similarity (NES), inverse NES (iNES), their harmonic mean (F1NES), and bitrate. Crucially, the study analyzes the resulting type-frequency distributions to assess Zipfian alignment.

Key Contributions

Clustering Method Impact: The paper demonstrates that the choice of clustering algorithm is critical for unsupervised lexicon induction. Bottom-up methods (graph and agglomerative clustering) consistently outperform centre-based methods (K-means, BIRCH, FBGMM) across all segmentation conditions and languages.
Recovery of Zipfian Distributions: Unlike centre-based approaches which produce flat, uniform distributions, bottom-up methods successfully recover the long-tailed type-frequency distributions characteristic of natural language at the word level, while also adapting to the less skewed distributions observed at the syllable level.
Controlled Granularity via Graph Clustering: The authors highlight graph clustering as a particularly effective bottom-up approach. It offers two interpretable hyperparameters—similarity threshold ( $\tau$ ) and resolution ( $\gamma$ )—that provide direct control over the induced type-frequency distribution, allowing the system to approximate target distributions more effectively than simply fixing the number of clusters ( $K$ ).

Results

Performance: On English data, graph and agglomerative clustering significantly outperformed K-means in terms of F1NES and iNES (recall of true types). For example, at the word level, graph clustering achieved an F1NES of 68.43% compared to 40.47% for K-means. This trend persisted for Afrikaans and French, even when using English-trained SSL features on unseen languages.
Distribution Shape: Visual analysis of type-frequency plots confirmed that centre-based methods fragment frequent types, leading to uniform distributions. In contrast, bottom-up methods produced distributions that closely tracked the ground-truth Zipfian curves.
Efficiency: While agglomerative clustering performed well, it was computationally slower (approx. 9 minutes vs. 3 minutes for graph clustering on the English dataset) due to repeated pairwise distance calculations. Graph clustering offered a balance of performance and efficiency, though the authors note that both bottom-up methods scale poorly compared to centre-based approaches.
Hyperparameter Sensitivity: The study showed that the threshold $\tau$ and resolution $\gamma$ in graph clustering govern a trade-off between intra-cluster consistency (NES) and inter-cluster separation of true types (iNES). Lower $\tau$ values favored denser graphs that better captured the long tail of frequent words.

Significance and Claims
The paper argues that the dominance of centre-based clustering in unsupervised term discovery is questionable due to its inherent bias toward uniform cluster sizes. The findings suggest that relaxing the geometric assumptions of centre-based methods in favor of bottom-up approaches is the key factor in recovering realistic lexicon structures. The authors position graph clustering as an attractive alternative that not only improves lexicon quality metrics but also provides a mechanism to control the statistical properties of the induced lexicon. The work concludes that clustering is a central modelling decision in term discovery and calls for future research into scalable bottom-up methods to make these approaches viable for larger, realistic datasets.

The Problem: The "Cookie Cutter" Mistake

The Solution: The "Social Network" Approach

The Experiment: Three Languages, Three Tests

The Results: The "Social Network" Wins

The Bottom Line

More like this