Unsupervised Tokenization for Machine Translation

Tagyoung Chung, Daniel GildeaEMNLP 2009 · OpenReview

Abstract

Training a statistical machine translation starts with tokenizing a parallel corpus. Some languages such as Chinese do not incorporate spacing in their writing system, which creates a challenge for tokenization. Moreover, morphologically rich languages such as Korean present an even bigger challenge, since optimal token boundaries for machine translation in these languages are often unclear. Both rule-based solutions and statistical solutions are currently used. In this paper, we present unsupervised methods to solve tokenization problem. Our methods incorporate information available from parallel corpus to determine a good tokenization for machine translation.

Introduction

In statistical machine translation (SMT), the initial step involves tokenization—the process of segmenting a continuous stream of characters into discrete "words." While straightforward for languages like English, this task is complex for languages without explicit spacing (e.g., Chinese) or agglutinative languages (e.g., Korean), where a single unit may contain multiple morphemes corresponding to several English words.

Traditionally, researchers rely on supervised segmenters trained on human-annotated "gold standard" data. However, this approach faces two major hurdles: the scarcity of annotated resources for many languages and the "Gold Standard Fallacy." A linguistically correct tokenization according to a dictionary is not necessarily the most efficient for machine translation. Ideally, we seek a tokenization that facilitates a one-to-one mapping between source and target tokens, which standard linguistic rules may not prioritize.

Methodology

We propose two unsupervised approaches to determine optimal token boundaries by leveraging the inherent structure of parallel corpora.

The Bilingual Model

The core innovation is a model that treats tokenization as a hidden variable within a word-alignment framework. Building upon a modified IBM Model 1, the model operates without knowing the source sentence's segmentation. We utilize dynamic programming to sum over all possible segmentations and apply Variational Bayes with a sparse Dirichlet prior to prevent the model from overfitting by memorizing excessively long strings.

The bilingual model treats tokenization as a hidden variable $f$ aligned to target words $e$.

Length Factors and Monolingual Baseline

To control token granularity, we introduced two length factors:

  • $\phi_1$ (Geometric): Based on the probability of a boundary occurring between characters.
  • $\phi_2$ (Exponential-like): A custom factor that penalizes longer tokens more heavily.

As a baseline, we also implemented a monolingual model that segments text based solely on substring frequency counts to isolate the impact of bilingual information.

Experimental Setup

The models were evaluated on two distinct language pairs:

  1. Chinese-English: Using the FBIS newswire corpus (approx. 2M words, 60K sentences), evaluated on the NIST 2002 set.
  2. Korean-English: A custom corpus of news articles (approx. 2M words, 60K sentences).

Key Results and Discussion

Our results demonstrate that unsupervised methods are highly competitive with, and often superior to, supervised alternatives for the purpose of translation quality.

Comparison of BLEU and F-scores across supervised and unsupervised methods.

Performance Highlights

  • Chinese-English: The bilingual model using the $\phi_2$ factor achieved a 22.31 BLEU score, outperforming the supervised LDC segmenter (20.03) and matching the performance of the Stanford segmenter (22.45).
  • Korean-English: The bilingual model reached 7.46 BLEU, surpassing both the rule-based morphological analyzer (7.27) and the monolingual baseline (7.02).

Insights on Translation Optimization

A critical finding is that "linguistically correct" segmentation is not always "translationally optimal." While the unsupervised bilingual model achieved a lower F-score against the Chinese Treebank gold standard than supervised models, it produced higher BLEU scores. This suggests that the target language provides a vital signal for source-language segmentation; for instance, the model learns to split Korean blocks into components that map directly to distinct English words.

Conclusion

This work demonstrates that tokenization learned directly from bilingual data can rival traditional dictionary-based methods. By prioritizing alignment consistency over linguistic conventions, SMT systems can achieve better translation quality even in resource-poor scenarios. Future work may involve iterative tokenization of both source and target languages and the integration of more complex alignment models like IBM Model 4.

Summary updated

Abstract

Training a statistical machine translation starts with tokenizing a parallel corpus. Some languages such as Chinese do not incorporate spacing in their writing system, which creates a challenge for tokenization. Moreover, morphologically rich languages such as Korean present an even bigger challenge, since optimal token boundaries for machine translation in these languages are often unclear. Both rule-based solutions and statistical solutions are currently used. In this paper, we present unsupervised methods to solve tokenization problem. Our methods incorporate information available from parallel corpus to determine a good tokenization for machine translation.
BibTeX
@inproceedings{chung2009unsupervised,
  author = {Tagyoung Chung and Daniel Gildea},
  title = {{Unsupervised Tokenization for Machine Translation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=S1VQefzu-B},
}
Figure