Word association models and search strategies for discriminative word alignment

Word Association Models and Search Strategies for Discriminative Word Alignment Patrik Lambert1 and Rafael E. Banchs2 1 TALP Research Center, Jordi Girona Salgado 1 3, 08034 Barcelona, Spain⋆ lambert@gps.tsc.upc.edu 2 Barcelona Media Innovation Centre, Ocata 1, Barcelona 08003, Spain. rafael.banchs@barcelonamedia.org Abstract. This paper deals with core aspects of discriminative word alignment systems, namely basic word association models as well as search strategies. We compare various low-computational-cost word as- sociation models: χ2 score, log-likelihood ratio and IBM model 1. We also compare three beam-search strategies. We show that it is more flex- ible and accurate to let links to the same word compete together, than introducing them sequentially in the alignment hypotheses, which is the strategy followed in several systems. 1 Introduction In this paper, we study core aspects of discriminative alignment systems [1, 2]. In these systems, the best alignment hypothesis is the one that maximises a linear combination of features. In Sect. 2 we propose some improvements of the beam-search algorithm implemented by Moore [1]. Then we present experimen- tal results for different low-computational-cost word association score features (Sect. 3.1) and for the proposed search strategies (Sect. 3.2). Finally, we give some conclusions. 2 Search Strategies Search aims at finding the alignment (i.e. the set of links between source and target words) which maximises the sum of each feature cost, weighted by its respective weight. In order to limit the search space, a set of promising links is first selected. Then alignment hypotheses are created by introducing some of these promising links, and the cost of each feature function for these alignment hypotheses is calculated. Figure 1 shows the list of promising links considered (referred to as the list of possible links). This list is obtained by pruning the word association feature table3 with a threshold N. Only the best N target words for each source word, and the best N source words for each target word are considered. Possible links are arranged in a certain number of stacks of links to be expanded during search. ⋆ This work has been partially funded by the Spanish Government under grant TEC2006-13964-C03 (AVIVAVOZ project). 3 It contains the word association score for each word pair seen in the training corpus. 12th EAMT conference, 22-23 September 2008, Hamburg, Germany 97 Sentence pair: (0)the (1)member (2)state (3). (0)los (1)pais (2)miembr (3). Possible links (word association cost order): Link Cost Corresponding words 1-2 0.1736 member-miembr 3-3 0.6758 .-. 0-0 1.3865 the-los 2-2 1.8285 state-miembr 2-1 2.4027 state-pais Fig. 1. Possible links list example. Word position is indicated in parentheses. Cor- responding words are actually stemmed forms. Here N = 1. Notice that “state” is involved in two links because it is the best source word for both “miembr” and “pais”. The best alignment here would be {0-0,1-2,2-1,3-3}. The cost is − log χ2 (see Sect. 3.1). 2.1 Baseline Search With Moore’s search strategy, which will be referred to as baseline search, links of the example of Fig. 1 are arranged as depicted in Fig. …

Content truncated to 500 words