Unsupervised Cross Lingual Alignment via Expectation Maximization

25 concepts26 papers1 proposal

When mapping linguistic units between two different languages, we rarely have access to perfect, manually annotated token-to-token alignments. Whether we are trying to translate a sentence, transliterate a proper noun, or map morphological variants, we face a classic chicken-and-egg problem:

  1. If we knew the exact alignments between the source and target units, we could easily calculate the translation probabilities by counting how often they co-occur.
  2. If we knew the translation probabilities, we could easily determine the most likely alignments.

Without human annotations, we have neither. The Expectation-Maximization (EM) algorithm provides an elegant mathematical escape from this loop. By treating the true alignments as latent (hidden) variables, EM allows a system to start from complete ignorance and iteratively bootstrap highly accurate cross-lingual mappings.

The Core Intuition: Fractional Counting

To understand why EM works in cross-lingual alignment, imagine looking at an unaligned parallel sentence pair: English "the cat" and French "le chat".

Initially, the model assumes a uniform distribution: the is equally likely to map to le or chat.

In the Expectation step (E-step), the model uses its current, imperfect probabilities to distribute "fractional credit" across all possible alignments. It calculates the likelihood of every combination given the observed data.

In the Maximization step (M-step), the model treats these fractional credits as real data. It aggregates them across the entire corpus and updates its translation probabilities to maximize the likelihood of what it saw.

Because correct alignments co-occur consistently across different contexts while incorrect alignments happen only randomly, the true signal reinforces itself over multiple iterations. Improbable links fade away, and the correct mappings emerge.

Iteration 0 (Uniform)      E-Step (Fractional Credit)      M-Step (Updated Probabilities)
the ─── le   (0.50)         the ─── le   (0.75)             P(le | the)   = 0.85
the ─── chat (0.50)         the ─── chat (0.25)             P(chat | the) = 0.15

Character and Substring Alignment

This iterative bootstrapping mechanism works across multiple scales of language, starting at the lowest level: characters and substrings.

When translating proper nouns or technical terms across different writing systems (transliteration), traditional systems historically relied on converting text into an intermediate phonetic representation. To bypass this error-prone step, Li et al. (2004) and Li et al. (2004) applied EM to learn direct orthographic mappings between character clusters. By treating the segmentation and alignment of character strings as latent variables, the algorithm automatically discovers how letter groups in one script correspond to character groups in another without human intervention.

Instead of fixing the size of these character groups, Pasternack et al. (2009) demonstrated that EM could dynamically segment words into variable-length substrings. Using dynamic programming in the E-step, their model efficiently sums over all possible segmentations to learn production probabilities, significantly improving transliteration accuracy across diverse scripts like Chinese, Hebrew, and Russian.

This capability becomes even more powerful when deciphering closely related or morphologically complex languages. Pourdamghani et al. (2017) showed that translation between related languages can be framed as a character-level decipherment problem. By running EM on monolingual corpora paired with a word-based language model, the system iteratively refines character mapping probabilities until the transformed source text matches the statistical profile of the target language. Similarly, Gasser et al. (2020) adapted these statistical alignment techniques to the character level to automatically expose phonological and morphological correspondences in low-resource, morphologically complex translation sets.

Scaling Up to Words, Phrases, and Structures

The exact same mathematical intuition scales seamlessly from characters to words and syntactic structures.

Early work by Julian Kupiec (1993) demonstrated that EM could align complex noun phrases across bilingual corpora by combining part-of-speech tagging with iterative probability updates.

Remarkably, EM does not even require parallel text to learn lexical mappings. Kevin Knight (2000) proved that word translation probabilities could be estimated from entirely unrelated monolingual corpora. By alternating between guessing translations based on a target language model (E-step) and updating the lexical probability distributions (M-step), the algorithm exploits the underlying statistical structure of language to map words without a single shared sentence.

[Source Corpus] ───> ( EM Alignment + Target Language Model ) <─── [Unrelated Target Corpus]
                                      │
                                      ▼
                        [Accurate Lexical Mapping]

This concept was extended to structural patterns by Lü et al. (2004), who used EM to align syntactic dependency triples across independent monolingual corpora, moving beyond single words to capture multi-word collocations. Even non-textual structural elements can be aligned this way: Shi et al. (2008) treated HTML markup trees as structural guides, using EM to discover which structural tags corresponded across different languages to drastically improve web page sentence alignment.

Powering Downstream Cross-Lingual Tasks

Once an EM framework can reliably estimate latent alignments, it can be repurposed to solve a wide variety of cross-lingual problems without requiring expensive machine translation pipelines.

Plagiarism and Information Retrieval

The classic IBM Alignment Model 1 relies on EM to learn word-level alignments. Pinto et al. (2008) demonstrated that this underlying engine could be directly applied to cross-lingual text classification and information retrieval. By capturing word correlations directly across languages, it bypasses the need to translate documents first. For example, Barrón-Cedeño et al. (2008) utilized this exact mechanism to build statistical bilingual dictionaries that calculate the direct probability that a text in one language is a plagiarized translation of a text in another.

Text Classification and Sentiment Analysis

When labeled data is scarce in a target language, EM can bridge the gap. Wu et al. (2008) introduced a Cross Language Naive Bayes Classifier that takes a static, ambiguous bilingual dictionary and applies EM to the target document distribution, tuning the translation probabilities to the specific context of the dataset. Taking this further, Meng et al. (2012) developed the Cross-Lingual Mixture Model (CLMM), which uses EM to iteratively estimate the sentiment orientation of target-language words directly from unlabeled parallel corpora, creating a fast, unified optimization process for sentiment projection.

Entity Linking and Modern Translation

For complex tasks like cross-lingual wikification—linking foreign text mentions to English Wikipedia entries—Tsai et al. (2018) showed that EM can jointly optimize word alignment and sub-word transliteration simultaneously, extracting clean patterns from noisy inter-language links.

Even in the era of deep learning, the probabilistic foundation of EM remains vital. Garcia et al. (2020) demonstrated that modern unsupervised multilingual machine translation can be framed entirely as an EM process. In this formulation, the E-step generates pseudo-parallel sentences via back-translation and decoding, while the M-step optimizes the neural network's parameters based on those targets.

Whether operating on individual characters, syntactic trees, or deep neural representations, the core mechanism remains unchanged: EM systematically converts cross-lingual co-occurrence into structured, probabilistic knowledge.

Key Foundational Work

An Algorithm for finding Noun Phrase Correspondences in Bilingual Corpora (1993) — contributed 1 concept elements to this direction.
A Statistical Approach to Language Translation (1988) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unsupervised_character_alignment_a14b0376,
  title = {unsupervised character alignment},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unsupervised-character-alignment/rdr_a14b0376fc6147bba894539b9ca73bf9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_unsupervised_character_alignment_a14b0376_v1,
  title = {unsupervised character alignment},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unsupervised-character-alignment/rdr_a14b0376fc6147bba894539b9ca73bf9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake