Meaning Representations in Statistical Word
Alignment

Tsuyoshi Okita
School of Computing
Dublin City University
Glasnevin, Dublin 9, Ireland
tokita@computing.dcu.ie

1

Statistical Word Alignment Implemented by Graphical Model

Using an architecture of our statistical word alignment, this paper presents 1) how meaning representations is structured in our system which intends to be easily interpreted by a computer and still
express rich / complex / conflicting knowledge, and 2) how we jointly infer semantics from several
fragmental evidences of semantics (modalities).
As a testbed of statistical word aligner, we implemented the prototype of statistical word aligner
by graphical models [2, 10]. The advantage of using graphical method resides in its extensibility
compared to the traditional approach for statistical word alignment [3, 22, 14]. Although there
are semi-supervised word aligner [6], we only talk about unsupervised word aligner [3, 22, 14].
The capabilities of this word aligner include that 1) it supports IBM / HMM models as well astree-based Models [13], 2) it can extend easily to support MAP assignment-based decoder (Viterbidecoding [21] as well as posterior decoding [10]) in these models [16, 15], 3) it can be used for theinput in the lattice-based decoding [1, 4] which are reinterpreted as the partial model selection, 4) it
supports flexible on / off capability of random variables which has advantageous in the lemma-basedalignment [5] and the morpheme avoided alignment, and 4) it can be used for the forced alignment[18]. This comes from the fact that the inference algorithms, such as sum-product and max-productalgorithms, are not affected by the form of network structures. Note that the traditional statisticalword alignment is built purely counting the frequency of words where syntax / semantics are notconsidered [11].
Let us e denote English word, f denote French word, and a denote alignment function [3, 8]. Let ai
denote the alignment function mapped from the i-th word in f into some word in e, fT denote the(dependency) tree structured input in f , and eT denote the (dependency) tree structured input in e.
e, f are random variables and a is hidden variable.
1. (Independent model) EM-based word alignment is the basis of other variations.
mllYXX
1 XmaxEp(f, a|e) =p(fj |eaj ) s.t.
p(f |e) = 1...
Z a =0 a =0 j=1
1(1)

fm

2. (Chain model) HMM-based word alignment considers the first-order Markov dependency
[22].
mYX
1maxEp(f, a|e) = maxp(a|a)p(f|e,a)s.t.
p(f |e) = 1(2)ii−1Z am
1i=1f

3. (Tree model) Tree-based word alignment consider the dependency structures in the source
and the target language [13].
YYX
1maxEp(f, a|e) = max
p(f|e,a)p(a|e)
p(e|f,a)p(a|f)
s.t.
p(fT |eT ) = 1 (3)TTTTTTZ am
1
T ∈TT ∈T

1T ∈T

It is noted that the above formulation omits the description of MAP inference approach [10, 12]. In
MAP inference, the random variables e, f are further partitioned into E (evidence) / Q (query) / H(hidden /nuisance), that is eE , eQ , fE , and fQ .

2

Meaning Representation

Instead of searching structured patterns from the beginning, we take the order of searching similar as
the frequent graph mining [20]: first we search the frequent subgraphs, and then we combine themto find structured patterns. The feasibility of this approach in word alignment is that the subgraphobjects that we listed in below, such as Multi Word Expressions (MWEs), pronoun, the coordinatedNoun Phrases (NPs), semantic role, and so on, are reasonably easily detectable by current NLP
technologies. Based on the detected subgraph objects, we write semantic action based on the typeof subgraph objects. We explicitly write semantic actions when such subgraph objects appear.
Firstly, our mechanical interface of semantics /syntax / information structure is limited in the ‘prior’in the MAP inference: we showed three types of word alignment models in the previous section. We
use the prior which indicates the alignment links between e and f in sentence i [16].
Secondly, we define the meaning representation which supports the existence of alignment links withquantifying by probabilities: 1) alignment links x1 , · · · , xm are (equally or with some probabilities)
possible, 2) alignment links x1 , · · · , xm is prohibited (or less likely), and 3) alignment link x islikely.
Thirdly, each of such semantic action will lead to the suggested word alignment links (whether it is
1-to-1, many-to-1, or many-to-many). Current version supports the following semantic actions: 1)
MWEs invokes MWE-TM unit, 2) pronoun (and no subject) invokes referent-table unit, 3) IS-adverb
invokes independent-IS-table unit, 4) the coordinated NPs invoke the coordination unit, 5) semanticrole invokes the SR-table unit, 6) proper noun / transliteration / localization term / equation invokes
the less-frequent-pair unit, 7) lexical semantics invokes the lexical-pair unit, 8) noise invokes thenoise unit (noise is important for Japanese / Chinese), and so forth. Each of these is reasonably
detected by current NLP technologies although this depends on the availability of such tools or
corpora on the specific language. In our experiments, MWE detection is unsupervised learning,
while POS-tagging, SRL, named-entity recognition are supervised learning. Note that currently theSR-table unit is only invokes semantic action when the semantic role in two languages are identical,
and the noise unit simply mutates itself with its semantic action.

3Inference

Each of these semantic action is converted into the suggested alignment links. Then, we combine
such suggested alignment links by noisy-or to form the prior, which is supplied as prior knowledge
to the MAP-based word aligner. Hence, the MAP inference follows the MAP assignment version of(1), (2) and (3) for given priors.
Note that the incorrect detection of subgraph object will lead to the incorrect invocation of thesemantic action. Note also that despite that the alignment link should be natively binary value, weoften set the prior not with binary value (0 or 1) but with probability.

4Experiments

We evaluate the performance by BLEU [17] using EN-JP corpus [7] of 200k sentence pairs. We use
the above word aligner, SRILM [19], and Moses [9]. Firstly, when we apply only a small amountof prior knowledge about alignment links, the effect of this is considerably small. However, once
this surpasses some threshold, the effect becomes radically big. In this sense, one interest of ours
is what is a threshold and how much (prior) knowledge we need to supply in order to achieve suchthreshold. In a sentence, when 50-60% of alignment links is a priori detected, the result reaches
precision of 97%.
2References[1] B ERTOLDI , N., Z ENS , R., AND F EDERICO , M. Speech translation by confusion network decoding.
ICASSP (2007), 1297–1300.
[2] B ISHOP, C. M. Pattern recognition and machine learning. Springer (2006).
[3] B ROWN , P. F., P IETRA , V. J., A.D.P IETRA , S., AND M ERCER , R. L. The mathematics of statisticalmachine translation: Parameter estimation. Computational Linguistics, Vol.19, Issue 2 (1993), 263–311.
[4] DYER , C., M URESAN , S., AND R ESNIK , P. Generalizing word lattice translation. In Proceedings of the46th Annual Meeting of the Association for Computational Linguistics (ACL-08) (2008), 1012–1020.
[5] F ISHEL , M., B OJAR , O., Z EMAN , D., AND B ERKA , J. Automatic translation error analysis. In theproceedings of TSD 2011 (2011).
[6] F RASER , A., AND M ARCU , D. Getting the structure right for word alignment: Leaf. In Proceedingsof the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational
Natural Language Learning (EMNLP-CoNLL) (2007), 51–60.
[7] F UJII , A., U TIYAMA , M., YAMAMOTO , M., U TSURO , T., E HARA , T., E CHIZEN - YA , H., AND S HI MOHATA , S. Overview of the patent translation task at the NTCIR-8 workshop. In Proceedings of the8th NTCIR Workshop Meeting on Evaluation of Information Access Technologies: Information Retrieval,Question Answering and Cross-lingual Information Access (2010), 293–302.
[8] KOEHN , P. Statistical machine translation. Cambridge University Press (2010).
[9] KOEHN , P., H OANG , H., B IRCH , A., C ALLISON -B URCH , C., F EDERICO , M., B ERTOLDI , N.,
C OWAN , B., S HEN , W., M ORAN , C., Z ENS , R., DYER , C., B OJAR , O., C ONSTANTIN , A., AND
H ERBST, E. Moses: Open source toolkit for Statistical Machine Translation. In Proceedings of the 45th
Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of theDemo and Poster Sessions (2007), 177–180.
[10] KOLLER , D., AND F RIEDMAN , N. Probabilistic graphical models: Principles and techniques. MIT Press(2009).
[11] M A , Y., L AMBERT, P., AND WAY, A. Tuning syntactically enhanced word alignment for statisticalmachine translation. In Proceedings of the 13th Annual Meeting of the European Association for MachineTranslation(EAMT 2009) (2009), 250–257.
[12] M URPHY, K. P. Lecture slides at university of british columbia. http://www.cs.ubc.ca/ murphyk/ (2011).
[13] NAKAZAWA , T., AND K UROHASHI , S. Statistical phrase alignment model using dependency relation
probability. In Proceedings of the third Workshop on Syntax and Structure in Statistical Translation(SSST-3) (2009), 10–18.
[14] O CH , F., AND N EY, H. A systematic comparison of various statistical alignment models. Computational
Linguistics 29, 1 (2003), 19–51.
[15] O KITA , T., G RAHAM , Y., AND WAY, A. Gap between theory and practice: Noise sensitive wordalignment in machine translation. In Proceedings of the Workshop on Applications of Pattern Analysis(WAPA2010). Cumberland Lodge, England. (2010).
[16] O KITA , T., G UERRA , A. M., G RAHAM , Y., AND WAY, A. Multi-Word Expression sensitive wordalignment. In Proceedings of the Fourth International Workshop On Cross Lingual Information Access(CLIA2010, collocated with COLING2010), Beijing, China. (2010), 1–8.
[17] PAPINENI , K., ROUKOS , S., WARD , T., AND Z HU , W. BLEU: A Method For Automatic Evaluation ofMachine Translation. In Proceedings of the 40th Annual Meeting of the Association for Computational
Linguistics (ACL-02) (2002).
[18] S CHWARTZ , L. Multi-source translation methods. In Proc. AMTA (October 2008).
[19] S TOLCKE , A. SRILM – An extensible language modeling toolkit. In Proceedings of the International
Conference on Spoken Language Processing (2002), 901–904.
[20] T SUDA , K., AND K UDO , T. Clustering graphs by weighted substructure mining. In Proceedings of the23rd International Conference on Machine Learning (ICML) (2006), 953–960.
[21] V ITERBI , A. J. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.
IEEE Transactions on Information Theory 13, 2 (1967), 260–269.
[22] VOGEL , S., N EY, H., AND T ILLMANN , C. HMM-Based word alignment in statistical translation. In
Proceedings of the 16th International Conference on Computational Linguistics (COLING 1996) (1996),836–841.

3