A Hierarchical Phrase-Based Model for Statistical Machine Translation

David Chiang

article2005ACL1,316 citationsBest Paper

Introduces a synchronous context-free grammar translation model that learns hierarchical phrase structures directly from parallel text without syntactic annotations, improving translation quality and long-distance reordering over standard phrase-based systems.

Listen

Standard phrase-based statistical machine translation systems excel at translating short, continuous word sequences, but they struggle with structural reordering across long distances, such as differing modifier placements between languages. Expanding conventional phrases to capture wider contexts typically fails due to data sparseness, while standard distortion models reorder words independently of their semantic content. The article evaluates a hierarchical phrase-based translation model designed to capture long-distance structural relationships and phrase reordering without relying on syntactically annotated linguistic data.

To address this limitation, the approach learns hierarchical translation rules—phrases containing gaps or subphrases—represented as a weighted synchronous context-free grammar. The grammar is induced automatically from word-aligned parallel text without linguistic parsers or syntactic treebanks, using heuristic rule extraction and beam-search chart parsing for decoding. The model was evaluated on a Chinese-to-English translation task using the Foreign Broadcast Information Service training corpus (over 16 million words combined) and standard benchmark test sets, comparing translation quality against Pharaoh, a state-of-the-art phrase-based baseline.

The analysis produced three primary findings. First, the hierarchical phrase-based model achieved a translation score of 0.2877 compared to 0.2676 for the baseline, representing a statistically significant relative improvement of 7.5% using the same training data. Second, precision improvements over the baseline grew progressively larger on longer word sequences (higher-order n-grams), confirming superior long-range structural coherence. Third, adding an explicit linguistic syntax feature from a syntactic parser yielded no statistically significant performance increase on the evaluation test set, showing that the unconstrained hierarchical phrases were already capturing the necessary structural alignments.

These findings demonstrate that translation systems can gain the structural strengths of syntax-based translation while retaining the flexibility and robustness of statistical phrase-based methods, all without requiring expensive annotated linguistic treebanks. However, large grammar sizes pose computational memory demands and risk search ambiguity, and the evaluated implementation exhibited search pruning trade-offs. Organizations deploying or researching machine translation should adopt hierarchical phrase architectures for languages with major word-order differences, while prioritizing grammar pruning and optimized decoding implementations to reduce memory overhead and support larger training volumes.

Institute for Advanced Computer Studies University of Maryland context-free syntactic information syntactic structure hierarchical phrase-based model statistical machine translation hierarchical phrase pairs

Chiang (2005).pdf

Paper: Statistical Phrase-Based Translation, Philipp Koehn et al. (2003). It introduces the standard phrase-based statistical machine translation framework that Chiang generalizes into a hierarchical phrase-based model.
Paper: Minimum Error Rate Training in Statistical Machine Translation, Franz Josef Och (2003). It defines Minimum Error Rate Training (MERT), which provides the fundamental parameter optimization method used to tune the log-linear features of the hierarchical translation model.
Paper: Bleu: a Method for Automatic Evaluation of Machine Translation, Kishore Papineni et al. (2002). It introduces the BLEU evaluation metric that serves as the primary benchmark and optimization target for assessing the hierarchical model against baseline phrase-based systems.
Paper: Statistical Significance Tests for Machine Translation Evaluation, Philipp Koehn (2004). It provides the bootstrap resampling methodology required to rigorously establish statistical significance when comparing machine translation system improvements.

Paper: Moses: Open Source Toolkit for Statistical Machine Translation, Philipp Koehn et al. (2007). It builds an open-source statistical machine translation toolkit that incorporates phrase-based and hierarchical/syntax-based decoding methods popularized by Chiang's work.
Paper: Learning Phrase Representations using RNN Encoder–Decoder for Statistical Machine Translation, Kyunghyun Cho et al. (2014). It advances statistical machine translation by introducing an RNN Encoder–Decoder to score phrase pairs and capture richer compositional dependencies within SMT pipelines.
Paper: Recurrent Continuous Translation Models, Nal Kalchbrenner et al. (2013). It demonstrates how continuous recurrent models can translate sentences directly, replacing discrete phrase-table and synchronous grammar derivations with neural continuous representations.
Paper: Sequence to Sequence Learning with Neural Networks, Ilya Sutskever et al. (2014). It shifts machine translation away from formal grammar rules and phrase segmentation toward end-to-end neural sequence-to-sequence mapping.
Paper: Neural Machine Translation by Jointly Learning to Align and Translate, Dzmitry Bahdanau et al. (2015). It introduces soft attention mechanisms in neural machine translation, dynamically handling alignment and reordering without explicit synchronous context-free grammars.
Paper: Six Challenges for Neural Machine Translation, Philipp Koehn et al. (2017). It benchmarks the modern neural paradigm against traditional phrase-based statistical machine translation across six core operational challenges.

Cover for A Hierarchical Phrase-Based Model for Statistical Machine Translation

Abstract

We present a statistical phrase-based translation model that uses hierarchical phrases—phrases that contain subphrases. The model is formally a synchronous context-free grammar but is learned from a bitext without any syntactic information. Thus it can be seen as a shift to the formal machinery of syntax-based translation systems without any linguistic commitment. In our experiments using BLEU as a metric, the hierarchical phrase-based model achieves a relative improvement of 7.5% over Pharaoh, a state-of-the-art phrase-based system.

Topics

context-free syntactic information syntactic structure translation systems treebanks word alignment statistical machine translation system parallel corpora part of speech phonology

Keywords

hierarchical phrase-based model statistical machine translation hierarchical phrase pairs syntax-based MT word alignment phrase reordering context-free grammar phrase table Chinese Treebank

1 Introduction
2 The model
3 Training
4 Decoding
5 Experiments
5.1 Baseline
5.2 Hierarchical model
5.3 Adding a constituent feature
6 Conclusion
Acknowledgements
References

Knowls

Knowl 1 — Synchronous CFG Formalism for Hierarchical Phrase-Based Translation
model/method
Hierarchical phrase-based translation formalizes translation rules using a weighted synchronous context-free grammar (SCFG). In this grammar, rewrite rules map between source-language strings and target-language strings with aligned nonterminal symbols:

$X \to \langle \gamma, \alpha, \sim \rangle$

where $X$ is a nonterminal symbol, $\gamma$ is a string of source terminals and nonterminals, $\alpha$ is a string of target terminals and nonterminals, and $\sim$ is a one-to-one correspondence between the nonterminal occurrences in $\gamma$ and those in $\alpha$ .

Unlike linguistically syntax-based MT, the grammar uses a single generic nonterminal symbol $X$ for all phrase categories learned from parallel text without syntactic annotations. To combine translated phrases serially into a complete sentence, the grammar incorporates two special glue rules:

$S \to \langle S_{1} X_{2}, S_{1} X_{2} \rangle$

$S \to \langle X_{1}, X_{1} \rangle$

where $S$ is the start symbol, and subscripts denote co-indexed nonterminals linked by $\sim$ . These glue rules allow the system to concatenate partial hierarchical translations sequentially, backing off to standard phrase-based combinations when hierarchical rules are not applied.
Knowl 2 — Hierarchical Phrase Extraction and Rule Filtering
algorithm
Given a sentence pair with word alignments $\langle f, e, \sim \rangle$ (where $\sim$ is a binary relation between source positions in $f$ and target positions in $e$ ), the hierarchical phrase extraction algorithm identifies initial contiguous phrase pairs and recursively extracts hierarchical rules with nonterminals.
Input: Word-aligned sentence pair <f, e, ~>
Output: Set of filtered synchronous CFG rules R
1. Identify initial phrase pairs:
   Let Init = { <f_i^j, e_{i'}^{j'}> |
     (exists k in [i, j], k' in [i', j'] s.t. f_k ~ e_{k'}) and
     (for all k in [i, j], k' not in [i', j'], not (f_k ~ e_{k'})) and
     (for all k not in [i, j], k' in [i', j'], not (f_k ~ e_{k'})) }
2. Filter initial phrase pairs:
   If multiple pairs in Init share the identical set of alignment points, retain only the smallest.
   Discard pairs where the source phrase f_i^j has length > 10.
3. Initialize rule set:
   R = { X -> <f_i^j, e_{i'}^{j'}> | <f_i^j, e_{i'}^{j'}> in Init }
4. Form difference rules (hierarchical phrases):
   For each rule r = (X -> <gamma, alpha>) in R:
     For each initial phrase pair <f_i^j, e_{i'}^{j'}> in Init:
       If f_i^j is a substring of gamma (gamma = gamma_1 f_i^j gamma_2) with length > 1 and
          e_{i'}^{j'} is a substring of alpha (alpha = alpha_1 e_{i'}^{j'} alpha_2):
         Let k be an unused nonterminal index
         new_rule = X -> <gamma_1 X_k gamma_2, alpha_1 X_k alpha_2>
         If new_rule satisfies:
           - source RHS (gamma_1 X_k gamma_2) has <= 5 symbols (terminals + nonterminals)
           - total nonterminals on RHS <= 2
           - no adjacent nonterminals on the source RHS
           - contains >= 1 pair of aligned terminal words
         Then R = R union { new_rule }
5. Probability estimation:
   Assign uniform weight to each initial phrase pair, and distribute that weight equally among all rules extracted from it.
   Compute P(gamma | alpha) and P(alpha | gamma) by relative frequency estimation on this weighted distribution.
return R
Knowl 3 — Log-Linear Derivation Scoring in Hierarchical SMT
equation
The score of a translation derivation $D$ generating source sentence $f(D)$ and target sentence $e(D)$ is defined under a log-linear model:

$w(D) = \left( \prod_{\langle r, i, j \rangle \in D} w(r) \right) \times p_{lm}(e(D))^{\lambda_{lm}} \times \exp\left(-\lambda_{wp} |e(D)|\right)$

where $\langle r, i, j \rangle \in D$ denotes an application of synchronous rule $r$ spanning source substring $f_i^j$ , $p_{lm}(e(D))$ is the $n$ -gram language model probability of the target string with weight $\lambda_{lm}$ , and $\exp(-\lambda_{wp} |e(D)|)$ is the word penalty with weight $\lambda_{wp}$ controlling target length.

Each synchronous rewrite rule $r = X \to \langle \gamma, \alpha \rangle$ has a weight determined by a product of rule features:

$w(X \to \langle \gamma, \alpha \rangle) = \prod_{k} \phi_k(X \to \langle \gamma, \alpha \rangle)^{\lambda_k}$

where the active rule features $\phi_k$ are:
1. Bidirectional phrase translation probabilities: $P(\gamma \mid \alpha)$ and $P(\alpha \mid \gamma)$ .
2. Bidirectional lexical weights: $P_w(\gamma \mid \alpha)$ and $P_w(\alpha \mid \gamma)$ , computed as weighted averages over word alignments observed during training.
3. Phrase penalty: $\exp(1)$ , enabling tuning of derivation length preference.
For glue rules, the terminal glue rule $S \to \langle X_1, X_1 \rangle$ has weight $1$ , while the recursive glue rule is weighted by a specific glue penalty:

$w(S \to \langle S_1 X_2, S_1 X_2 \rangle) = \exp(-\lambda_g)$

where $\lambda_g$ controls the system's preference for hierarchical rule compositions versus serial phrase combinations.
Knowl 4 — CKY Beam-Search Decoding for Hierarchical SMT
algorithm
Decoding finds the target yield of the single highest-scoring synchronous derivation generating the input source sentence $f$ :

$\hat{e} = e\left(\arg\max_{D: f(D) = f} w(D)\right)$

The search is implemented as a bottom-up CKY chart parser on the source sentence integrated with the target language model via finite-state intersection.
Input: Source sentence f of length n, grammar R, LM parameters, pruning parameters (b_X, beta_X, b_S, beta_S, b_rule)
Output: 1-best translation e
1. Initialize chart cells C[i, j] = empty for all 0 <= i < j <= n
2. For span length l = 1 to n:
     For start index i = 0 to n - l:
       j = i + l
       // Enforce span limit on X
       If l <= 10:
         For each rule r in R matching source span f_i^j:
           Combine r with antecedent chart items in sub-spans
           Intersect target side with LM states
           Score derivation items and add to cell C_X[i, j]

         // Prune X cell
         Keep at most b_X best items in C_X[i, j]
         Discard any item with score < beta_X * (best score in C_X[i, j])

       // Apply glue rules for S cells
       If l == 1:
         C_S[i, j] = { S -> <X_1, X_1> applied to items in C_X[i, j] }
       Else:
         For split point k from i+1 to j:
           Combine S in C_S[i, k] and X in C_X[k, j] using S -> <S_1 X_2, S_1 X_2>
           Add resulting items to C_S[i, j]

       // Prune S cell
       Keep at most b_S best items in C_S[i, j]
       Discard any item with score < beta_S * (best score in C_S[i, j])
3. Beam heuristic optimization:
   When populating a cell, if an antecedent item or rule falls outside the beam, skip generating candidates from any lower-scoring rules or lower-scoring antecedents.
4. Extract yield:
   Return the target string yield e of the highest-scoring S item in C_S[0, n].
Because the maximum span for $X$ is bounded ( $l \le 10$ ), the decoding complexity is asymptotically linear $O(n)$ in source sentence length.

Knowl 5 — Translation Performance: Hierarchical SMT vs. Phrase-Based Baseline

data/table

The hierarchical phrase-based translation model was evaluated against Pharaoh (a state-of-the-art standard phrase-based decoder) on Chinese-to-English translation using the FBIS training corpus (7.2M source + 9.2M target words), NIST 2002 MT evaluation set (development), and NIST 2003 MT evaluation set (test). Both systems used a trigram language model trained on 155M words of English newswire and optimized feature weights via minimum error rate training (MERT) targeting BLEU.

	BLEU-4	$n$ -gram precisions
System		1	2	3	4	5	6	7	8
Pharaoh	0.2676	0.72	0.37	0.19	0.10	0.052	0.027	0.014	0.0075
hierarchical	0.2877	0.74	0.39	0.21	0.11	0.060	0.032	0.017	0.0084
+constituent	0.2881	0.73	0.39	0.21	0.11	0.062	0.032	0.017	0.0088

The hierarchical model achieved a BLEU score of 0.2877 on the test set, representing an absolute improvement of 0.0201 (a 7.5% relative gain) over Pharaoh's 0.2676, which is statistically significant ( $p < 0.01$ ). The relative precision gains are consistently higher at larger $n$ -gram orders.

Knowl 6 — MERT Feature Weights in Hierarchical Phrase-Based Translation

data/table

Minimum-error-rate training (MERT) weights obtained by maximizing BLEU on the NIST 2002 development set (normalized so absolute values sum to 1) for the Pharaoh baseline, the hierarchical model, and the hierarchical model augmented with a syntactic constituent feature:

System	$P_{lm}(e)$	$P(\gamma\|\alpha)$	$P(\alpha\|\gamma)$	$P_w(\gamma\|\alpha)$	$P_w(\alpha\|\gamma)$	Word	Phr	$\lambda_d$	$\lambda_g$	$\lambda_c$
Pharaoh	0.19	0.095	0.030	0.14	0.029	-0.20	0.22	0.11	—	—
hierarchical	0.15	0.036	0.074	0.037	0.076	-0.32	0.22	—	0.09	—
+constituent	0.11	0.026	0.062	0.025	0.029	-0.23	0.21	—	0.11	0.20

Key notation: Word is target word penalty $\lambda_{wp}$ ; Phr is phrase penalty (positive values indicate a penalty); $\lambda_d$ is the baseline distortion penalty; $\lambda_g$ is the glue rule penalty for $S \to \langle S_1 X_2, S_1 X_2 \rangle$ ; and $\lambda_c$ is the syntactic constituent feature weight.

In the hierarchical model, $\lambda_g = 0.09$ penalizes glue rule usage noticeably less than the regular phrase penalty ( $ext{Phr} = 0.22$ ) penalizes standard rules. Consequently, the decoder defaults to serial concatenation of phrases unless other model components (such as language model scoring) actively favor hierarchical rule derivations.

Knowl 7 — Syntactic Constituent Feature in Hierarchical SMT
model/method
To evaluate whether explicitly favoring syntactically coherent phrases improves hierarchical translation, an optional binary constituent feature is incorporated into the derivation score:

$c(i, j) = \begin{cases} 1 & \text{if source span } f_i^j \text{ is a syntactic constituent} \\ 0 & \text{otherwise} \end{cases}$

Constituency is determined by parsing the source sentences with an external statistical tree-substitution-grammar parser trained on the Penn Chinese Treebank. This feature adds a factor $\exp(\lambda_c \cdot c(i, j))$ to the weight of each rule application spanning $f_i^j$ .

While adding this constituent feature improved BLEU score on the development set (from 0.314 to 0.322 with learned weight $\lambda_c = 0.20$ ), it produced only a minor change on the test set (BLEU 0.2881 vs. 0.2877), which was not statistically significant.

Coverage note — None was omitted; all contributed aspects of the model definition, grammar induction, log-linear scoring, decoding algorithm, constituent feature extension, and empirical evaluation are covered.

References

1.A. V. Aho and J. D. Ullman. 1969. Syntax directed translations and the pushdown assembler. Journal of Computer and System Sciences, 3:37–56.
2.Daniel M. Bikel and David Chiang. 2000. Two statistical parsing models applied to the Chinese Treebank. In Proceedings of the Second Chinese Language Processing Workshop, pages 1–6.
3.Hans Ulrich Block. 2000. Example-based incremental synchronous interpretation. In Wolfgang Wahlster, editor, Verbmobil: Foundations of Speech-to-Speech Translation, pages 411–417. Springer-Verlag, Berlin.
4.Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19:263–311.
5.Stanley F. Chen and Joshua Goodman. 1998. An empirical study of smoothing techniques for language modeling. Technical Report TR-10-98, Harvard University Center for Research in Computing Technology.
6.Philipp Koehn, Franz Josef Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of HLT-NAACL 2003, pages 127–133.
7.Philipp Koehn. 2003. Noun Phrase Translation. Ph.D. thesis, University of Southern California.
8.Philipp Koehn. 2004a. Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proceedings of the Sixth Conference of the Association for Machine Translation in the Americas, pages 115–124.
9.Philipp Koehn. 2004b. Statistical significance tests for machine translation evaluation. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 388–395.
10.Shankar Kumar, Yonggang Deng, and William Byrne. 2005. A weighted finite state transducer translation template model for statistical machine translation. Natural Language Engineering. To appear.
11.Daniel Marcu and William Wong. 2002. A phrase-based, joint probability model for statistical machine translation. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 133–139.
12.Franz Josef Och and Hermann Ney. 2000. Improved statistical alignment models. In Proceedings of the 38th Annual Meeting of the ACL, pages 440–447.
13.Franz Josef Och and Hermann Ney. 2002. Discriminative training and maximum entropy models for statistical machine translation. In Proceedings of the 40th Annual Meeting of the ACL, pages 295–302.
14.Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30:417–449.
15.Franz Josef Och, Ignacio Thayer, Daniel Marcu, Kevin Knight, Dragos Stefan Munteanu, Quamrul Tipu, Michel Galley, and Mark Hopkins. 2004. Arabic and Chinese MT at USC/ISI. Presentation given at NIST Machine Translation Evaluation Workshop.
16.Franz Josef Och. 2003. Minimum error rate training in statistical machine translation. In Proceedings of the 41st Annual Meeting of the ACL, pages 160–167.
17.Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. Bʐᴇᴜ: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting of the ACL, pages 311–318.
18.Andreas Stolcke. 2002. SRILM – an extensible language modeling toolkit. In Proceedings of the International Conference on Spoken Language Processing, volume 2, pages 901–904.
19.Dekai Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23:377–404.
20.Kenji Yamada and Kevin Knight. 2001. A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting of the ACL, pages 523–530.
21.Richard Zens and Hermann Ney. 2004. Improvements in phrase-based statistical machine translation. In Proceedings of HLT-NAACL 2004, pages 257–264.
22.Ying Zhang, Stephan Vogel, and Alex Waibel. 2004. Interpreting BLEU/NIST scores: How much improvement do we need to have a better system? In Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC), pages 2051–2054.

Citation

MLA

Chiang, D. “A Hierarchical Phrase-Based Model for Statistical Machine Translation”. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 2005, pp. 263–70, https://doi.org/10.3115/1219840.1219873.

APA

Chiang, D. (2005). A Hierarchical Phrase-Based Model for Statistical Machine Translation. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 263–270. https://doi.org/10.3115/1219840.1219873

Chicago

Chiang, D. 2005. “A Hierarchical Phrase-Based Model for Statistical Machine Translation”. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 263–70. https://doi.org/10.3115/1219840.1219873.

Harvard

Chiang, D. (2005) “A Hierarchical Phrase-Based Model for Statistical Machine Translation”, Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05). Association for Computational Linguistics, pp. 263–270. Available at: https://doi.org/10.3115/1219840.1219873.

Vancouver

1. Chiang D (2005) A Hierarchical Phrase-Based Model for Statistical Machine Translation. In: Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05). Association for Computational Linguistics, pp 263–270

BibTeX

@inproceedings{chiang-2005-hierarchical,
    title = "A Hierarchical Phrase-Based Model for Statistical Machine Translation",
    author = "Chiang, David",
    editor = "Knight, Kevin  and
      Ng, Hwee Tou  and
      Oflazer, Kemal",
    booktitle = "Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics ({ACL}{'}05)",
    month = jun,
    year = "2005",
    address = "Ann Arbor, Michigan",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/P05-1033/",
    doi = "10.3115/1219840.1219873",
    pages = "263--270"
}

Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/

A Hierarchical Phrase-Based Model for Statistical Machine Translation

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Synchronous CFG Formalism for Hierarchical Phrase-Based Translation

Knowl 2 — Hierarchical Phrase Extraction and Rule Filtering

Knowl 3 — Log-Linear Derivation Scoring in Hierarchical SMT