ProAlign: Shared Task System Description

Dekang Lin, Colin CherryParallelTexts @ NAACL 2003 · OpenReview

Abstract: ProAlign combines several different approaches in order to produce high quality word word alignments. Like competitive linking, ProAlign uses a constrained search to find high scoring alignments. Like EM-based methods, a probability model is used to rank possible alignments. The goal of this paper is to give a bird's eye view of the ProAlign system to encourage discussion and comparison.

Introduction

In the field of machine translation, word alignment is the foundational task of identifying correspondences between words in a source sentence and a target sentence. Historically, researchers have relied on two distinct paradigms: mathematically rigorous generative models (such as the IBM Models) and heuristic-based search methods (such as competitive linking). While generative models offer a strong statistical framework, they often treat sentences as unstructured collections of words, leading to "messy" alignments that ignore the underlying linguistic structure. Conversely, heuristic methods can be efficient but often lack a global probabilistic foundation.

ProAlign bridges this gap by introducing a system that is both statistically sound and linguistically informed. By utilizing English dependency trees to enforce "cohesion" constraints during a best-first search, ProAlign produces high-precision alignments that respect the grammatical structure of the sentences, effectively preventing "unnatural" alignments that violate phrase structure.

The ProAlign Methodology

ProAlign identifies the optimal alignment $A$ for a sentence pair $(E, F)$ through an iterative, search-based approach. The system employs a best-first search (specifically a beam search) that starts with an empty alignment and incrementally adds links, seeking the configuration with the highest probability.

Linguistic Constraints

To manage the search space and ensure linguistic accuracy, ProAlign enforces two primary constraints:

  1. One-to-One Mapping: Every word (excluding nulls) is restricted to participating in exactly one link.
  2. Cohesion Constraint: This is the system's core innovation. By leveraging a dependency tree of the English sentence, the system ensures that if two phrases are distinct in English, their translated counterparts in the target language do not overlap in a way that violates linguistic logic. This prevents "crossing" errors where the alignment contradicts the grammatical hierarchy.
Figure 1: An example of dependency-informed alignment between English and French sentences, showing how grammatical relationships like 'subj' and 'obj' guide the mapping process.

The Probability Model

Unlike traditional generative "noisy channel" models, ProAlign models the alignment probability $P(A|E, F)$ directly. It utilizes a Naive Bayes-style decomposition that incorporates two main feature types:

  • Adjacency Features: These capture the tendency of neighboring words in the source language to remain neighbors in the translation.
  • Dependency Features: These use the English parse tree to learn how specific grammatical relationships—such as a determiner and its head noun—typically map across the language pair.

Experimental Evaluation

The system was evaluated using the Word Alignment Workshop 2003 (WPT’03) Shared Task datasets for English-French and Romanian-English. The results demonstrate the effectiveness of combining structural constraints with probabilistic modeling.

Language Pair Alignment Error Rate (AER)
English-French 5.71%
Romanian-English 29.36%

The higher error rate for Romanian-English is attributed to the smaller training dataset and greater structural divergence between the languages, a common challenge in the field. Notably, these results were achieved using "no-null" data, as the initial system output was not configured for explicit null alignments.

Key Insights and Future Directions

ProAlign demonstrates that linguistics can act as a powerful filter. By using dependency trees as a hard constraint on the search space, the system rules out incoherent alignments early, making the search both more efficient and more accurate. Furthermore, the direct modeling of alignment probability allows for the easy integration of arbitrary features, such as the dependency relationships shown in Figure 1.

However, the system faces certain limitations. The strict one-to-one constraint requires auxiliary post-processing to handle many-to-one mappings. Additionally, the system's performance is inherently tied to the quality of the English dependency parser; errors in parsing can lead to incorrect cohesion constraints. Future work will focus on integrating complex mappings directly into the probability model and developing a more robust framework for handling null links.

Summary updated

Abstract

ProAlign combines several different approaches in order to produce high quality word word alignments. Like competitive linking, ProAlign uses a constrained search to find high scoring alignments. Like EM-based methods, a probability model is used to rank possible alignments. The goal of this paper is to give a bird's eye view of the ProAlign system to encourage discussion and comparison.
BibTeX
@inproceedings{lin2003proalign,
  author = {Dekang Lin and Colin Cherry},
  title = {{ProAlign: Shared Task System Description}},
  booktitle = {ParallelTexts @ NAACL},
  year = {2003},
  url = {https://openreview.net/forum?id=S1bjP7ZdWH},
}
Figure