Algoritmo Decodificación Traducción Automática En N-Gramas

Algoritmo de Decodificaci´n de Traducci´n Autom´tica o o a Estoc´stica basado en N -gramas a
Josep M. Crego Jos´ B. Mari˜ o e n Adri` de Gispert a

Centro de Investigaci´n TALP o Campus Nord UPC, 08034-Barcelona {jmcrego,canton,agispert}@gps.tsc.upc.es
Resumen: En esta comunicaci´n se presenta MARIE, un algoritmo de decodifio caci´n para un sistema de traducci´n autom´tica estoc´stica basado enN -gramas. o o a a Para su implementaci´n se utiliza una estrategia de b´squeda en haz, con capacidad o u para realizar reordenamientos (distorsi´n). El modelo de traducci´n est´ basado en o o a N -gramas biling¨es, ampliado para introducir reordenamientos en las cadenas de u palabras. La estructura del espacio de b´squeda permite realizar un alto grado de u poda, incrementando as´ la eficienciadel algoritmo. ı Palabras clave: traducci´n autom´tica estoc´stica, modelos de traducci´n basados o a a o en N -gramas, algoritmos de decodificaci´n o Abstract: In this paper we describe MARIE, an N -gram-based stochastic machine translation decoder. It is implemented using a beam search strategy, with distortion (or reordering) capabilities. The underlying translation model is based on an N gramapproach, extended to introduce reordering at the phrase level. The search graph structure is designed to perform very accurate comparisons, what allows for a high level of pruning, improving the decoder efficiency. Keywords: stochastic machine translation, N -gram-based translation models, decoding algorithms

1.

Introducci´n o

La traducci´n autom´tica estoc´stica o a a (TAE), se define comouna tarea donde caJ da oraci´n fuente f1 se transforma (o geneo ra) en una oraci´n destino dI , a trav´s de un o e 1 proceso estoc´stico. a La traducci´n de una oraci´n fuente pueo o de formularse como la b´squeda de la oraci´n u o destino que maximiza la probabilidad condiJ cional p(dI |f1 ), que usando la regla de Bayes 1 puede reescribirse como: arg m´x a
dI 1 J p(f1 |dI ) · p(dI ) 1 1

(1)J donde p(f1 |dI ) representa el modelo de tra1 ducci´n y p(dI ) es el modelo de lenguaje del o 1 idioma destino. La descomposici´n del problema en dos o fuentes sigue el enfoque llamado ’modelo de canal ruidoso’. La operaci´n de maximizaci´n o o (argmax) denota el problema de b´squeda. u En este punto podemos describir la tarea de traducci´n autom´tica como el proceso de o a b´squeda de laspalabras del idioma destino u

que maximizan conjuntamente dos objetivos: (primero) encontrar las palabras que mejor traducen las palabras de la oraci´n fuente. Y o (segundo) encontrar la secuencia de palabras que genera una oraci´n destino correcta. Para o el primero se utiliza un modelo de traducci´n, o que indica para cada par de palabras (fuente y destino) la probabilidad de que una seatraducci´n de la otra. Para el segundo se utiliza o un modelo de lenguage (destino), que indica para cada oraci´n (o secuencia) la probabilio dad de que ´sta pertenezca al idioma destino. e En referencia al modelo de traducci´n, los o primeros sistemas de traducci´n autom´tica o a trabajaban a nivel de palabras (Brown et al., 1990) (las unidades biling¨es se componian u de palabras aisladas). Losalgoritmos de decodificaci´n de estos primeros sistemas pueo den clasificarse bajo diferentes aproximaciones: b´squeda A∗ (Och, Ueffing, y Ney, 2001), u programaci´n entera (Germann et al., 2001), o algoritmos voraces (Germann, 2003), (Berger et al., 1994), (Wang y Waibel, 1998). Recientemente, los sistemas de TAE tien-

den a utilizar secuencias de palabras como unidades b´sicas del modelo de traducci´n,a o con el objetivo de introducir el contexto en dicho modelo. Estos sistemas llevan a cabo la traducci´n mediante la maximizaci´n de o o una combinaci´n lineal de los logaritmos de o la probabilidad asignada a la traducci´n por o el modelo de traducci´n y otras caracter´ o ısticas, siguiendo la aproximaci´n por m´xima o a entrop´ (Berger, Della Pietra, y Della Pieıa, tra, 1996) (facilitando...