Morpheme Induction for Emergent Language

Brendon Boldt, David R. MortensenEMNLP 2025

TL;DR

This paper introduces CSAR, a novel algorithm for automatically discovering the fundamental building blocks (morphemes) of emergent languages – communication systems created by AI. By analyzing parallel utterances and their meanings, CSAR provides a crucial tool for understanding the structure and evolution of these artificial languages, offering insights into how meaning is encoded and how language itself develops.

What Problem Does This Paper Address?

Emergent languages, born from AI agents learning to communicate, offer a unique window into the fundamental processes of language development. However, these artificial languages are notoriously difficult to interpret. The strategies they use to convey meaning often don't align with human language patterns, and we lack general-purpose methods to systematically investigate their internal structure. This makes it hard to understand how meaning is encoded, leading to a significant gap in our ability to analyze and learn from these fascinating systems.

Methods

The core of this paper is the CSAR (Count, Select, Ablate, Repeat) algorithm. It's a greedy approach designed to identify minimal, well-founded form-meaning pairs (morphemes) within a corpus of utterances and their associated meanings. Here's how it works:

  1. Candidate Collection: CSAR identifies potential "form" candidates (sequences of tokens) and "meaning" candidates (sets of atomic meanings) from the data.
  2. Weighting and Co-occurrence: It calculates the mutual information between form and meaning candidates. This statistical measure quantifies how strongly a particular form is associated with a particular meaning.
  3. Selection: The algorithm selects the form-meaning pair with the highest weight (strongest association).
  4. Ablation: Once a pair is selected as a morpheme, all its occurrences are removed from the corpus. This allows the algorithm to find the next most significant morpheme in the remaining data.
  5. Iteration: Steps 2-4 are repeated until no more meaningful pairs can be found or a stopping criterion is met.

CSAR is designed to be robust to noise and looser form-meaning correspondences, which are common in emergent languages.

Datasets

The authors validate CSAR on two main types of datasets:

  • Procedurally Generated Datasets: These are synthetic datasets created by the authors to allow for controlled experiments. They include variations like synonymy (multiple forms for one meaning), polysemy (multiple meanings for one form), multi-token forms, and noise. These datasets are crucial because they provide "ground truth" morphemes, enabling quantitative evaluation.
  • Human Language Datasets: CSAR was also tested on real-world human language data from tasks like:
  • Morpho Challenge: English words at the character level, with meanings as constituent morphemes.
  • MS COCO Image Captions: Image captions as utterances, with labeled objects in the image as meanings.
  • Machine Translation (WMT16 English-German): English sentences as utterances, German sentences as meanings.

These human language datasets help demonstrate the algorithm's generalizability and qualitative performance.

Key Insights and Ideas

  • Greedy but Effective: CSAR's greedy approach, while potentially susceptible to local optima, proves highly effective and computationally efficient for morpheme induction.
  • Synonymy Over Polysemy: In emergent languages, the authors observe a higher degree of synonymy (multiple forms for one meaning) than polysemy (multiple meanings for one form). This suggests that emergent languages prioritize clarity over conciseness when under no pressure to be efficient.
  • Compositionality is Key: The tendency for emergent languages to have a meaning size of 1 suggests a non-trivial degree of compositionality, where individual morphemes contribute atomic meanings that combine to form complex ones.
  • Generalizability: CSAR performs well not only on synthetic data but also demonstrates reasonable results on diverse human language tasks, highlighting its broad applicability.

Key Results

  • Superior Performance: CSAR significantly outperforms baseline methods (like IBM alignment models and form-only tokenization methods) on procedural datasets, achieving a large margin in F₁ scores for both form-meaning and form-only inventories.
  • Human Language Success: CSAR successfully recovers a wide variety of morphemes from human language data, including roots, prefixes, and suffixes, and identifies phenomena like synonymy and polysemy in image captions.
  • Efficiency: The algorithm is designed to be an "anytime" algorithm, meaning it can be stopped at any point and still provide a useful partial inventory, making it practical for real-world applications.

Limitations and Future Work

  • Greediness and Local Optima: The greedy nature of CSAR means it can get trapped in local optima, potentially missing the globally optimal set of morphemes. Future work could explore non-greedy approaches or iterative refinement to address this.
  • Limited Emergent Language Data: The authors acknowledge the lack of ground truth morpheme inventories for emergent languages, which limits direct quantitative evaluation on this target domain. They suggest that more systematically generated data is needed for definitive claims about emergent language morphology.
  • Further Linguistic Analysis: The morpheme inventories produced by CSAR are a foundation for deeper linguistic analyses, such as uncovering syntactic structures and understanding the typological features of emergent languages, which could reveal how they resemble or differ from human languages.

Summary updated

BibTeX
@inproceedings{boldt2025morpheme,
  author = {Brendon Boldt and David R. Mortensen},
  title = {{Morpheme Induction for Emergent Language}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2025},
}
Figure