Inversion Transduction Grammars
Early work on synchronous context free grammars for machine translation made a distinction between lexical mapping rules and purely non-terminal binary rules to make reordering decisions.
Inversion Transduction Grammars is the main subject of 28 publications. 19 are discussed here.
Publications
Rooted in a finite state machine approach, head automata have been developed that allow for tree representation during the translation process
Hiyan Alshawi (1996):
Head Automata and Bilingual Tiling: Translation with Minimal Representations (Invited Talk), Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL)
@Inproceedings{Alshawi:1996,
author = {Hiyan Alshawi},
title = {Head Automata and Bilingual Tiling: Translation with Minimal Representations (Invited Talk)},
url = {
http://acl.ldc.upenn.edu/P/P96/P96-1023.pdf?origin=publicationDetail},
googlescholar = {11846375422406776920},
booktitle = {Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL)},
year = 1996
}
(Alshawi, 1996;
Hiyan Alshawi and Adam L. Buchsbaum and Fei Xia (1997):
A Comparison of Head Transducers and Transfer for a Limited Domain Translation Application, Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL)
@Inproceedings{Alshawi:1997,
author = {Hiyan Alshawi and Adam L. Buchsbaum and Fei Xia},
title = {A Comparison of Head Transducers and Transfer for a Limited Domain Translation Application},
url = {
http://acl.ldc.upenn.edu/P/P97/P97-1046.pdf},
googlescholar = {5948054786386064082},
booktitle = {Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL)},
year = 1997
}
Alshawi et al., 1997;
Hiyan Alshawi and Srinivas Bangalore and Shona Douglas (1998):
Automatic Acquisition of Hierarchical Transduction Models for Machine Translation, Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)
@Inproceedings{Alshawi:1998,
author = {Hiyan Alshawi and Srinivas Bangalore and Shona Douglas},
title = {Automatic Acquisition of Hierarchical Transduction Models for Machine Translation},
url = {
http://acl.ldc.upenn.edu/C/C98/C98-1006.pdf},
googlescholar = {11495305628758623054},
booktitle = {Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)},
year = 1998
}
Alshawi et al., 1998;
Hiyan Alshawi and Srinivas Bangalore and Shona Douglas (2000):
Learning Dependency Translation Models as Collection of Finite-State Head Transducers, Computational Linguistics
@Article{Alshawi:2000,
author = {Hiyan Alshawi and Srinivas Bangalore and Shona Douglas},
title = {Learning Dependency Translation Models as Collection of Finite-State Head Transducers},
url = {
http://acl.ldc.upenn.edu/J/J00/J00-1004.pdf},
journal = {Computational Linguistics},
volume = {26},
number = {1},
pages = {45--60},
year = 2000
}
Alshawi et al., 2000).
Ye-Yi Wang and Alex Waibel (1998):
Modeling with Structures in Statistical Machine translation, Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)
mentioned in Phrase Based Models and Inversion Transduction Grammars@Inproceedings{Wang:1998,
author = {Ye-Yi Wang and Alex Waibel},
title = {Modeling with Structures in Statistical Machine translation},
url = {
http://acl.ldc.upenn.edu/P/P98/P98-2221.pdf},
googlescholar = {12385920933414037529},
booktitle = {Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)},
year = 1998
}
Wang and Waibel (1998) also induce hierarchical structures in their statistical machine translation model.
The use of synchronous grammars for statistical machine translation has been pioneered by
Dekai Wu (1995):
Trainable Coarse Bilingual Grammars for Parallel Text Bracketing, Proceedings of the Third Workshop on Very Large Corpora (VLC)
@Inproceedings{Wu:1995b,
author = {Dekai Wu},
title = {Trainable Coarse Bilingual Grammars for Parallel Text Bracketing},
url = {
http://acl.ldc.upenn.edu/W/W95/W95-0106.pdf},
googlescholar = {8753937834967775813},
booktitle = {Proceedings of the Third Workshop on Very Large Corpora (VLC)},
year = 1995
}
Wu (1995);
Dekai Wu (1996):
A Polynomial-Time Algorithm for Statistical Machine Translation, Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL)
@Inproceedings{Wu:1996,
author = {Dekai Wu},
title = {A Polynomial-Time Algorithm for Statistical Machine Translation},
url = {
http://acl.ldc.upenn.edu/P/P96/P96-1021.pdf},
googlescholar = {3924641975573530982},
booktitle = {Proceedings of the 34th Annual Meeting of the Association for Computational Linguistics (ACL)},
year = 1996
}
Wu (1996);
Dekai Wu (1997):
Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora, Computational Linguistics
mentioned in Word Alignment Based On Coocurrence and Inversion Transduction Grammars@Article{Wu:1997,
author = {Dekai Wu},
title = {Stochastic Inversion Transduction Grammars and Bilingual Parsing of Parallel Corpora},
url = {
http://acl.ldc.upenn.edu/J/J97/J97-3002.pdf},
googlescholar = {7926725626202301933},
journal = {Computational Linguistics},
volume = {23},
number = {3},
year = 1997
}
Wu (1997);
Dekai Wu and Hongsing Wong (1998):
Machine Translation with a Stochastic Grammatical Channel, Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)
@Inproceedings{Wu:1998,
author = {Dekai Wu and Hongsing Wong},
title = {Machine Translation with a Stochastic Grammatical Channel},
url = {
http://acl.ldc.upenn.edu/P/P98/P98-2230.pdf},
googlescholar = {17922869678767927043},
booktitle = {Proceedings of the 36th Annual Meeting of the Association of Computational Linguistics (ACL)},
year = 1998
}
Wu and Wong (1998) with their work on inversion transduction grammars (ITG) and stochastic bracketing transduction grammars (SBTG). A different formal model are multitext grammars
I. Dan Melamed (2003):
Multitext grammars and synchronous parsers, Proceedings of the Joint Conference on Human Language Technologies and the Annual Meeting of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL)
@Inproceedings{Melamed:2003,
author = {I. Dan Melamed},
title = {Multitext grammars and synchronous parsers},
url = {
http://acl.ldc.upenn.edu/N/N03/N03-1021.pdf},
googlescholar = {11734294015301744662},
booktitle = {Proceedings of the Joint Conference on Human Language Technologies and the Annual Meeting of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL)},
year = 2003
}
(Melamed, 2003;
Melamed, I. Dan (2004):
Statistical Machine Translation by Parsing, Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL'04), Main Volume
@inproceedings{Melamed:2004,
author = {Melamed, I. Dan},
title = {Statistical Machine Translation by Parsing},
url = {
http://acl.ldc.upenn.edu/acl2004/main/pdf/113\_pdf\_2-col.pdf},
googlescholar = {10328834082011647315},
booktitle = {Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL'04), Main Volume},
month = {July},
address = {Barcelona, Spain},
pages = {653--660},
year = 2004
}
Melamed, 2004;
Melamed, I. Dan and Satta, Giorgio and Wellington, Benjamin (2004):
Generalized Multitext Grammars, Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL'04), Main Volume
@inproceedings{Melamed:2004b,
author = {Melamed, I. Dan and Satta, Giorgio and Wellington, Benjamin},
title = {Generalized Multitext Grammars},
url = {
http://acl.ldc.upenn.edu/acl2004/main/pdf/277\_pdf\_2-col.pdf},
googlescholar = {2355681091376158087},
booktitle = {Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL'04), Main Volume},
month = {July},
address = {Barcelona, Spain},
pages = {661--668},
year = 2004
}
Melamed et al., 2004) and range concatenation grammars
Søgaard, Anders (2008):
Range Concatenation Grammars for Translation, Coling 2008: Companion volume: Posters and Demonstrations
@InProceedings{sogaard:2008:POSTERS2,
author = {S{\o}gaard, Anders},
title = {Range Concatenation Grammars for Translation},
booktitle = {Coling 2008: Companion volume: Posters and Demonstrations},
month = {August},
address = {Manchester, UK},
publisher = {Coling 2008 Organizing Committee},
pages = {101--104},
url = {
http://www.aclweb.org/anthology/C08-3026},
year = 2008
}
(Søgaard, 2008).
Zhang, Hao and Gildea, Daniel (2005):
Stochastic Lexicalized Inversion Transduction Grammar for Alignment, Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)
@InProceedings{zhang-gildea:2005:ACL,
author = {Zhang, Hao and Gildea, Daniel},
title = {Stochastic Lexicalized Inversion Transduction Grammar for Alignment},
booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
month = {June},
address = {Ann Arbor, Michigan},
publisher = {Association for Computational Linguistics},
pages = {475--482},
url = {
http://www.aclweb.org/anthology/P/P05/P05-1059},
year = 2005
}
Zhang and Gildea (2005) extend the ITG formalism by lexicalizing grammar rules and apply it to a small-scale word alignment task. Armed with an efficient A* algorithm for this formalism
Zhang, Hao and Gildea, Daniel (2006):
Efficient Search for Inversion Transduction Grammar, Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing
@InProceedings{zhang-gildea:2006:EMNLP,
author = {Zhang, Hao and Gildea, Daniel},
title = {Efficient Search for Inversion Transduction Grammar},
booktitle = {Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing},
month = {July},
address = {Sydney, Australia},
publisher = {Association for Computational Linguistics},
pages = {224--231},
url = {
http://www.aclweb.org/anthology/W/W06/W06-1627},
year = 2006
}
(Zhang and Gildea, 2006), they extend the formalism with rules that are lexicalized in both input and output
Zhang, Hao and Gildea, Daniel (2006):
Inducing Word Alignments with Bilexical Synchronous Trees, Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions
@InProceedings{zhang-gildea:2006:POS,
author = {Zhang, Hao and Gildea, Daniel},
title = {Inducing Word Alignments with Bilexical Synchronous Trees},
booktitle = {Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions},
month = {July},
address = {Sydney, Australia},
publisher = {Association for Computational Linguistics},
pages = {953--960},
url = {
http://www.aclweb.org/anthology/P/P06/P06-2122},
year = 2006
}
(Zhang and Gildea, 2006).
Word alignments generated with ITG may also be used to extract phrase for phrase-based models
Joan Andreu Sánchez and José Miguel Benedí (2006):
Obtaining Word Phrases with Stochastic Inversion Translation Grammars for Phrase-based Statistical Machine Translation, Proceedings of the 11th Conference of the European Association for Machine Translation (EAMT)
@InProceedings{Sanchez:2006:EAMT,
author = {Joan Andreu S\'{a}nchez and Jos\'{e} Miguel Bened\'{i}},
title = {Obtaining Word Phrases with Stochastic Inversion Translation Grammars for Phrase-based Statistical Machine Translation},
url = {
http://mt-archive.info/EAMT-2006-Sanchez.pdf},
googlescholar = {16689080566077645608},
booktitle = {Proceedings of the 11th Conference of the European Association for Machine Translation (EAMT)},
month = {June},
address = {Oslo, Norway},
year = 2006
}
(Sánchez and Benedí, 2006;
Sánchez, Joan Andreu and Benedí, José Miguel (2006):
Stochastic Inversion Transduction Grammars for Obtaining Word Phrases for Phrase-based Statistical Machine Translation, Proceedings on the Workshop on Statistical Machine Translation
@InProceedings{sanchez-benedi:2006:WMT,
author = {S\'{a}nchez, Joan Andreu and Bened\'{i}, Jos\'{e} Miguel},
title = {Stochastic Inversion Transduction Grammars for Obtaining Word Phrases for Phrase-based Statistical Machine Translation},
booktitle = {Proceedings on the Workshop on Statistical Machine Translation},
month = {June},
address = {New York City},
publisher = {Association for Computational Linguistics},
pages = {130--133},
url = {
http://www.aclweb.org/anthology/W/W06/W06-3117},
year = 2006
}
Sánchez and Benedí, 2006b).
Zhang, Hao and Quirk, Chris and Moore, Robert C. and Gildea, Daniel (2008):
Bayesian Learning of Non-Compositional Phrases with Synchronous Parsing, Proceedings of ACL-08: HLT
@InProceedings{zhang-EtAl:2008:ACLMain2,
author = {Zhang, Hao and Quirk, Chris and Moore, Robert C. and Gildea, Daniel},
title = {{Bayesian} Learning of Non-Compositional Phrases with Synchronous Parsing},
booktitle = {Proceedings of ACL-08: HLT},
month = {June},
address = {Columbus, Ohio},
publisher = {Association for Computational Linguistics},
pages = {97--105},
url = {
http://www.aclweb.org/anthology/P/P08/P08-1012},
year = 2008
}
Zhang et al. (2008) present an efficient ITG phrase alignment algorithm that uses Bayesian learning with priors.
Benchmarks
Discussion
Related Topics
New Publications
Markus Saers and Dekai Wu (2013):
Unsupervised learning of bilingual categories in inversion transduction grammar induction, Proceedings of the International Workshop on Spoken Language Translation (IWSLT)
@inproceedings{Saers:iwslt:2013,
author = {Markus Saers and Dekai Wu},
title = {Unsupervised learning of bilingual categories in inversion transduction grammar induction},
url = {
http://www.mt-archive.info/10/IWSLT-2013-Saers.pdf},
booktitle = {Proceedings of the International Workshop on Spoken Language Translation (IWSLT)},
year = 2013
}
Saers and Wu (2013)
Saers, Markus and Wu, Dekai (2013):
Bayesian Induction of Bracketing Inversion Transduction Grammars, Proceedings of the Sixth International Joint Conference on Natural Language Processing
@InProceedings{saers-wu:2013:IJCNLP,
author = {Saers, Markus and Wu, Dekai},
title = {Bayesian Induction of Bracketing Inversion Transduction Grammars},
booktitle = {Proceedings of the Sixth International Joint Conference on Natural Language Processing},
month = {October},
address = {Nagoya, Japan},
publisher = {Asian Federation of Natural Language Processing},
pages = {1158--1166},
url = {
http://www.aclweb.org/anthology/I13-1165},
year = 2013
}
Saers and Wu (2013)
Anders S\ogaard (2011):
A O(|G|n6) time extension of inversion transduction grammars, Machine Translation
@article{MTJ:2011:Sogaard,
author = {Anders S\o{}gaard},
title = {A O(|G|n6) time extension of inversion transduction grammars},
pages = {291-315},
journal = {Machine Translation},
volume = {25},
number = {4},
month = {December},
year = 2011
}
S\ogaard (2011)
Saers, Markus and Addanki, Karteek and Wu, Dekai (2012):
From Finite-State to Inversion Transductions: Toward Unsupervised Bilingual Grammar Induction, Proceedings of COLING 2012
@InProceedings{saers-addanki-wu:2012:PAPERS,
author = {Saers, Markus and Addanki, Karteek and Wu, Dekai},
title = {From Finite-State to Inversion Transductions: Toward Unsupervised Bilingual Grammar Induction},
booktitle = {Proceedings of COLING 2012},
month = {December},
address = {Mumbai, India},
publisher = {The COLING 2012 Organizing Committee},
pages = {2325--2340},
url = {
http://www.aclweb.org/anthology/C12-1142},
year = 2012
}
Saers et al. (2012)
Liu, Shujie and Li, Chi-Ho and Zhou, Ming (2010):
Improved Discriminative ITG Alignment using Hierarchical Phrase Pairs and Semi-supervised Training, Coling 2010: Posters
@InProceedings{liu-li-zhou:2010:POSTERS,
author = {Liu, Shujie and Li, Chi-Ho and Zhou, Ming},
title = {Improved Discriminative ITG Alignment using Hierarchical Phrase Pairs and Semi-supervised Training},
booktitle = {Coling 2010: Posters},
month = {August},
address = {Beijing, China},
publisher = {Coling 2010 Organizing Committee},
pages = {730--738},
url = {
http://www.aclweb.org/anthology/C10-2084},
year = 2010
}
Liu et al. (2010)
Li, Peng and Liu, Yang and Sun, Maosong (2012):
A Beam Search Algorithm for ITG Word Alignment, Proceedings of COLING 2012: Posters
@InProceedings{li-liu-sun:2012:POSTERS2,
author = {Li, Peng and Liu, Yang and Sun, Maosong},
title = {A Beam Search Algorithm for {ITG} Word Alignment},
booktitle = {Proceedings of COLING 2012: Posters},
month = {December},
address = {Mumbai, India},
publisher = {The COLING 2012 Organizing Committee},
pages = {673--682},
url = {
http://www.aclweb.org/anthology/C12-2066},
year = 2012
}
Li et al. (2012)
K. Addanki and C. Lo and M. Saers and D. Wu (2012):
LTG vs. ITG Coverage of Cross-Lingual Verb Frame Alternation, Proceedings of th 16th International Conference of the European Association for Machine Translation (EAMT)
@inproceedings{EAMT-2012-Addanki,
author = {K. Addanki and C. Lo and M. Saers and D. Wu},
title = {LTG} vs. {ITG Coverage of Cross-Lingual Verb Frame Alternation},
url = {
http://www.mt-archive.info/EAMT-2012-Addanki},
pages = {295-304},
booktitle = {Proceedings of th 16th International Conference of the European Association for Machine Translation (EAMT)},
location = {Trento, Italy},
editor = {Mauro Cettolo and Marcello Federico and Lucia Specia and Andy Way},
year = 2012
}
Addanki et al. (2012)
Saers, Markus and Nivre, Joakim and Wu, Dekai (2010):
Linear Inversion Transduction Grammar Alignments as a Second Translation Path, Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR
@InProceedings{saers-nivre-wu:2010:WMT,
author = {Saers, Markus and Nivre, Joakim and Wu, Dekai},
title = {Linear Inversion Transduction Grammar Alignments as a Second Translation Path},
booktitle = {Proceedings of the Joint Fifth Workshop on Statistical Machine Translation and MetricsMATR},
month = {July},
address = {Uppsala, Sweden},
publisher = {Association for Computational Linguistics},
pages = {173--177},
url = {
http://www.aclweb.org/anthology/W10-1725},
year = 2010
}
Saers et al. (2010)
Haghighi, Aria and Blitzer, John and DeNero, John and Klein, Dan (2009):
Better Word Alignments with Supervised ITG Models, Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP
@InProceedings{haghighi-EtAl:2009:ACLIJCNLP,
author = {Haghighi, Aria and Blitzer, John and DeNero, John and Klein, Dan},
title = {Better Word Alignments with Supervised ITG Models},
booktitle = {Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP},
month = {August},
address = {Suntec, Singapore},
publisher = {Association for Computational Linguistics},
pages = {923--931},
url = {
http://www.aclweb.org/anthology/P/P09/P09-1104},
year = 2009
}
Haghighi et al. (2009)