Aportacions a la millora d'un sistema interactiu d'ajuda a la traducció basat en mètodes estadístics
Abstract
El propòsit d'aquest treball és, doncs, millorar les prestacions d'aquests sistemes. S'han plantejat una sèrie de millores que afecten directament al sistema de traducció automàtica subjacent, ja que és aquest el que s'encarrega de generar les propostes de traducció, i és on resideix el punt clau de millora: a major qualitat de la traducció, major qualitat del sistema. Per tant, aquest Projecte de Final de Carrera es centrarà fonamentalment en la disciplina de la traducció automàtica.
Full text
memoria 2010/11/17 19:32 page i #1 i i UNIVERSITAT POLITÈCNICA DE VALÈNCIA ESCOLA TÈCNICA SUPERIOR D'ENGINYERIA INFORMÀTICA DEPARTAMENT DE SISTEMES INFORMÀTICS I COMPUTACIÓ Ap ortaions a la millora d'un sistema interatiu d'a juda a la traduió basat en mèto des estadístis. Pro jete Final de Carrera - Enginyeria Informàtia Joan Alb ert Silvestre Cerdà Sup ervisat p er: Dr. Jorge Civera Saiz Dr. Jesús Andrés Ferrer 17 de novembre de 2010
memoria 2010/11/17 19:32 page ii #2 i i
memoria 2010/11/17 19:32 page iii #3 i i A la memòria del meu pare, Luis.
memoria 2010/11/17 19:32 page iv #4 i i
memoria 2010/11/17 19:32 page v #5 i i Agraïments No és molt habitual esriure aquestes línies en un pro jete de nal de arrera, i realment no enten el p er què. Aquest treball representa la ulminaió dels estudis universitaris, una etapa molt imp ortant de la nostra vida, larament marada p er la inuènia de les p ersones del nostre entorn: familiars, amis, enemis, oneguts, professors, et. Totes aquestes persones són el nostre referent so ial i la prinipal font de oneixements de la que es no drim en el dia a dia (la universitat de la vida), sent la seva interaió amb nosaltres un fator determinant en la nostra eduaió, esp e- ialment en la universitària, on els estudiants omenem a mostrar-nos al món om p ersones formades, madures i indep endents. Per aquest motiu trob e que tota la gent que ha inuït de forma p ositiva en la meva p ersona durant aquest p erío de de temps es mereix, p er la meva part, una menió esp eial, una esp èie de reoneixement p ersonal. I són preisament aquestes línies les més idònies p er expressar el més siner i profund agraïment a totes aquelles p ersones que m'han aompanyat en aquest reorregut. He de onfessar que aquestes són les línies més difíils d'esriure de tot el do ument, dons les paraules que segueixen no són més que meres aproximaions a l'afete i estima que tin a les p ersones que, sense llo a dubte, formen part d'aquest pro jete de nal de arrera, i més enara, de la meva formaió om a enginyer informàti i om a p ersona. En primer llo , i om a prinipal impulsor d'aquest treball, vull donar les grà- ies a Alfons Juan p er haver-me brindat l'op ortunitat de realitzar aquest apassionant pro jete, preo upar-se p el meu futur immediat om a enginyer informàti i aollir-me al seu grup. Un tren així no passa tots els dies p er la vida d'una p ersona, i, fran- ament, em sent molt afortunat de no haver-lo deixat esapar. En la mateixa línia, vull fer esp eial menió als diretors d'aquest pro jete, Jorge Civera i Jesús Andrés, p er la gran impliaió que han mostrat en tot moment durant l'elaboraió d'aquest treball, p er la omuniaió onstant i uïda que hem mantingut al llarg d'aquests quasi in mesos, p els seus grans oneixements i passió p er la traduió automàtia i el reoneixement de formes, p el seu altruisme, p er preo upar-se pel meu futur, p er la seva enorme simpatia, i sobretot, p er la paiènia innita que han tingut amb mi. He de destaar, a més, el gran llegat que han deixat en mi en forma de nous oneixements i habilitats, que no són p o s. Moltes gràies a tots dos. Per proximitat tamb é voldria donar les gràies al meus ompanys de laboratori del DSIC: Adrià, Ihab, Miguel, Nio, Isaías i Riardo (la omunitat del lúster), el quals m'han aollit molt amablement i m'han a judat en moltes oses durant la realitzaió d'aquest treball, esp eialment Miguel, p er prestar-me la plantilla Latex d'aquest prov
memoria 2010/11/17 19:32 page vi #6 i i jete i p els seus onsells, i Adrià p er les seves ap ortaions de Latex, C++, i els seus xilets de després de dinar. Tots ells m'han fet passar una estança al lab oratori molt agradable. No al oblidar tamp o als meus ompanys de arrera, tant de l'Enginyeria Tènia om de l'Enginyeria Sup erior, on he trobat amis i amigues que, enara que les nostres vides ara segueixen amins diferents, almenys tenim el grat reord d'haver-nos reuat i ompartir uns b ons ratets junts. De tots ells vull fer esp eial menió de Jordi, Kike, Miguel i Berni, els meus primers ompanys de lasse amb els que he passat molt b ons moments; Cèsar, p els dos magnís anys que hem ompartit al segon ile d'informàtia; a Raül (Rulo), amb qui mantin una estreta amistat a p esar dels anys que fa que des que es deixà la arrera; i sobretot, a un gran ami meu de tota la vida i ompany de pis durant aquests 5 anys: Àngel, una b ellíssima p ersona a la qual po dria ns i tot atribuir-li l'obtenió del meu títol d'enginyer tèni (ell sap que vull dir amb això). No m'agradaria deixar en el tinter a la gent que he onegut en la meva vessant musial om a trompista, la ma jor de les meves passions que, malauradament, per motius de salut, entre d'altres, no m'he p ogut dediar de forma més intensa o inlús de forma professional om m'hagués agradat. Reorde amb nostàlgia a professors i ompanys de lasse de l'esola de músia de Boairent, del onservatori d'Ontinyent i del onservatori de Valènia. Vull fer menió esp eial, d'una banda, als ompanys que fundarem el Grup Instrumental Simfonies, un gran grup d'amis apassionats de la músia simfònia, així om a Àngela i Cèsar, dos ompanys del onservatori d'Ontinyent amb els que enara mantin una b ona amistat; i d'altra banda, als professors que més m'han marat en la meva formaió musial: Rosell, gran trompista i millor p ersona, p erò sobretot, Titín, un trompista exep ional i un professor exel · lent que em va ontagiar la seva passió p er la Músia i que va aonseguir pro duir la meva millor versió om a trompista, al fer-me reup erar la onança amb mi mateix, ns al punt que l'úni que desitjava era menjar-me l'esenari. No vull oblidar tamp o a Luís Serrano, un gran do ent i magní omp ositor de músia simfònia del que vaig aprendre molt, i que em va donar la p ossibilitat d'explorar nous horitzons musials. També és molt imp ortant per a mi el meu ex-alumne i ami Asensio, a qui vaig p o der transferir gran part dels meus oneixements musials ensenyant-li des de zero solfeig musial i Trompa durant 3 anys. I om no, a l'Asso iaió Unió Musial Bo airent, la banda dels meus amors i bressol de la meva eduaió musial, en la que he visut vivènies inoblidables i on trob e b ons amis i oneguts, entre ells amis de tota la vida. Esti molt trist p er no p o der partiipar ativament en ella, p erò promet que prompte o tard tornaré. El meu os ho demana a rits. També vull aprotar per menionar, d'una banda, els meus ompanys de la delegaió d'àrbitres d'Aloi del Comité Tèni d'Àrbitres de la FFCV, estament arbitral al que p ertany des de fa 4 anys, i amb els que he passat molts bons moments en la pràtia d'una feina molt gratiant i útil p er al desenvolupament de la meva p ersona, enara que de vegades p erillosa, tot s'ha de dir. D'altra banda, també vull reordar als membres de la que fou l'Asso iaió d'Informàtia Boairent.net ja fa bastants anys, als quals de, en erta manera, la meva aió al món de la informàtia, i vi JASC-DSIC-UPV
memoria 2010/11/17 19:32 page vii #7 i i d'entre els quals destaque a Manel Espinós i a Pere Cresp o, dos grandíssimes persones amb les que enara mantin una bona relaió, i amb les que en el seu dia vaig passar molts b ons ratets junts, gestionant i muntant les suessives bekiparty's, entre d'altres ativitats. Vull menionar esp eialment a Pere, qui ha marat molt la meva vida om a informàti, dons la seva p ersona ha estat el meu referent om a futur enginyer. Els meus amis i amigues han estat la base fonamental no sols d'aquesta titulaió que esti apunt d'assolir, sinó tamb é de la meva vida: amb ells he visut experiènies genials que m'han servit p er desonnetar dels estudis, i sobretot, p er gaudir de la vida. N'esti molt agraït p el reolzament que he trobat en ells i p er tot allò que han aguantat, sobretot en aquests 4 mesos en els que he realitzat el pro jete: re que tots ells tenen més ganes d'aabar-lo que jo! Po dria omençar a parlar, un p er un, de tots ells, p erò en son tants i tant b ons que p o dria estendre'm pàgines i pàgines parlant meravelles d'ells, així que esp ere que em donen la lliènia d'evitar aquest desprop òsit, que ja trob e que me n'esti exedint bastant en quant a extensió. Tots ells sab en quant me'ls estime, així que esti tranquil. Sobren les paraules. Gràies p er estar ahí, genteta. He de destaar, a més, aquelles p ersones que més han estat en ontate amb mi durant aquests 5 anys, que són els meus ompanys de pis a Valènia. Tots ells, Adrià, Àngel, Rub én, i Vítor, ompanys i amis de tota la vida, són les persones amb les que més vivènies, de lluny, he ompartit, molt divertides i gratiants, p er ert. Sobretot és de lloar om de b é m'han tratat i tot el que han tingut que sup ortar. Que em feren el sopar els dies que tornava tardíssim a asa p erquè em trobava a lasses del onservatori, o el gran esforç que realitzaven aguantant les meves dues hores d'estudi diàries de Trompa a asa, són dues mostres de om m'han mimat. Inlús en irumstànies extremes, om per exemple aquests els últims 5 mesos, quan em passava hores i hores al lab oratori elab orant aquest treball: sempre que tornava a asa em trobava amb el dinar i el sopar fet (reentment amb un nou ompanyer de pis, Raül). Això no té preu. Sols l'amistat de deb ò p ot fer eixes oses. A tots ells l'úni que pu dir-los és que gràies, moltes gràies p er ser tant b ons ompanys i amis, de tot or, aquest pro jete també és vostre. També tin paraules de gratitud ap a Teresa Llavador i als seus dos lls, Pep e i Paqui Tomàs, amis del meu pare i meus p er afortunada herènia, p er aollir-nos tant b é al seu pis de Valènia durant els últims 3 anys, p erò sobretot p er ser tant b ones p ersones, i p er la gran amistat i ordialitat que mantin amb ells om amb la resta de la seva família. Per damunt de tot està el pap er fonamental que ha jugat la meva família en la meva eduaió. Vull agrair el reolzament inondiional que he rebut p er part dels meus familiars, tant en aquests 5 anys om en tota la meva vida. Esp eialment, he de donar les gràies al meu germà Luís, p er la seva inestimable ompanyia, el seu afete, p er iniiar-me al món de la informàtia i de la músia, i sobretot, pels seus onsells i p er la seva saviesa om a germà ma jor que tant apreie om a germà xiotet; i om no, a la meva mare, Mari Carmen, per dur-me al món, uidar-me, estimar-me i eduar-me JASC-DSIC-UPV vii
memoria 2010/11/17 19:32 page viii #8 i i de la forma apropiada per fer-me arribar ns on esti ara: ella és la prinipal ulpable de la redaió d'aquestes línies, no s'equivoquem. Estaré eternament agraït amb la meva núvia Lídia, p er tot el que ha fet p er mi i la paiènia que ha tingut en tot el temps que estem junts, tot a p esar de la distània, que malauradament se'ns fa eterna. Per estar sempre al meu ostat, per uidar-me i mimar-me, p er a judar-me en els moments més difíils, p er fer-me gaudir de tants b ons moments... p er moltes raons, p erò sobretot, p el seu amor inondiional que he ompartit i que esp ere ompartir amb ella ns que s'apague la llum del sol, i de la lluna. Per últim, m'agradaria reordar amb aquestes paraules la persona que més mereix la meva admiraió: el meu pare Luís, un gran home, p ersona patidora i lluitadora, que es va desviure p el b enestar de la seva família i p er po der assegurar un futur millor als seus lls, osa que sense dubte ha aonseguit. De segur que estaria molt orgullós de veure om els seus lls han resp ost al seu sarii, als valors que ens ha inulat, al seu esp erit lluitador. Malauradament, la seva vida es va esvair de forma prematura, p erò no així el seu reord. És p er això que aquest treball vull dediar-lo íntegrament a la memòria del meu pare, sobretot p erquè m'agradaria que sab era, allà on estiga, que l'ob jetiu que va p erseguir ns l'últim dia de la seva vida s'ha assolit. I que p er això, i p er moltes més raons, n'esti molt agraït i orgullós d'ell. Gràies a tots i totes. Joan Alb ert Silvestre Cerdà Valènia, 17 de novembre de 2010 viii JASC-DSIC-UPV
memoria 2010/11/17 19:32 page ix #9 i i Índex 1 Intro duió 1 1.1 Visió general de la traduió automàtia . . . . . . . . . . . . . . . . . 3 1.1.1 Un breu repàs a la història . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Aproximaions a la traduió automàtia . . . . . . . . . . . . 4 1.1.3 Sistemes d'a juda a la traduió . . . . . . . . . . . . . . . . . . 7 1.2 Traduió automàtia estadístia . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Coneptes bàsis de probabilitat . . . . . . . . . . . . . . . . . 9 1.2.2 Traduió estadístia . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Mo dels de llenguatge . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.4 Mo dels de traduió . . . . . . . . . . . . . . . . . . . . . . . . 18 1.3 Aproximaions a la traduió automàtia estadístia . . . . . . . . . . 19 1.3.1 Mo dels basats en paraules . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 Mo dels basats en seqüènies de paraules . . . . . . . . . . . . . 26 1.3.3 Mo dels basats en transdutors . . . . . . . . . . . . . . . . . . 31 1.3.4 Mo dels jeràrquis o basats en arbres . . . . . . . . . . . . . . . 33 2 Traduió automàtia estadístia basada en seqüènies de paraules 37 2.1 El sistema de TA Moses . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.1 Mo dels logarítmi-lineals . . . . . . . . . . . . . . . . . . . . . 38 2.1.2 Extensions del mo del original . . . . . . . . . . . . . . . . . . . 39 2.1.3 El mo del logarítmi-lineal de Moses . . . . . . . . . . . . . . . 43 2.1.4 Entrenament del mo del . . . . . . . . . . . . . . . . . . . . . . 44 2.1.5 Pro és de traduió . . . . . . . . . . . . . . . . . . . . . . . . 46 2.1.6 Avaluaió de la qualitat de la traduió . . . . . . . . . . . . . 48 2.1.7 Ajustament de paràmetres . . . . . . . . . . . . . . . . . . . . . 50 2.2 Mananes del mo del de seqüènies de paraules . . . . . . . . . . . . . 50 3 Mo dels de Longitud 55 3.1 Mo del de longitud estàndard . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.1 Estimaió del mo del i implementaió . . . . . . . . . . . . . . . 56 3.1.2 Integraió en Moses . . . . . . . . . . . . . . . . . . . . . . . . 61 3.2 Mo del de longitud esp eialitzat . . . . . . . . . . . . . . . . . . . . . . 62 3.2.1 Estimaió del mo del i implementaió . . . . . . . . . . . . . . . 62 3.2.2 Integraió . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 ix
memoria 2010/11/17 19:32 page 6 #16 i i Capítol 1. Intro duió de les frases origen a una representaió equivalent en el llenguatge destí, tot mitjançant l'apliaió de regles que indiquen la orresp ondènia dels fragments de l'arbre sintàti origen als de l'arbre sintàti destí. Per últim, l'arbre destí es transforma en un text llegible per a l'usuari. • Interlingua : Aquesta aproximaió és el as extrem de la traduió per transferènia, dons es realitza un minuiós i exhaustiu pro és d'anàlisi del text origen ns aonseguir una representaió oneptual ompletament indep endent dels llenguatges origen i destí anomenada Interlingua . Aquesta aproximaió presenta el gran avantatge de que, en llo de denir orresp ondènies entre ada parell de p ossibles llenguatges a traduir, és suient amb denir la orresp ondènia entre ada llenguatge i l' Interlingua . Ara b é, la omplexitat d'aquesta aproximaió resideix en dissenyar un Interlingua adequat, que p ermeta tant representar on- eptes de forma únia om establir orresp ondènies úniques (ada paraula de l' Interlingua estarà relaionada amb una i sols una paraula d'un llenguatge on- ret). Aproximaió basada en orpus D'altra banda, l'aproximaió basada en orpus es onep om una aproximaió empíri- a, ja que la informaió emprada p er onstruir el sistema s'obté a partir d'un orpus d'exemples de traduions del llenguatge font al llenguatge destí. El gran avantatge que presenten aquests sistemes és que la tenologia que els implementa pot ser fà- ilment reutilitzada p er a altres dominis d'apliaió o inlús altres parells d'idiomes, p erò p er ontra requereixen reopilar grans quantitats d'informaió p er tal de apturar una representaió signiativa del domini en el que es pretén realitzar el pro és de traduió. A trets generals, aquests sistemes parteixen d'un orpus d'entrenament onformat p er parells de frases traduïdes p er un grup d'exp erts, i que en la ma joria del asos requereixen una fase prepro és (separar signes de puntuaió de les paraules, transformar ma júsules en minúsules, et.) p er tal de failitar i garantir l'adquisiió de fonts de oneixement robustes i de qualitat durant la fase d'entrenament. Amb el sistema entrenat es pot dur a terme la tasa de traduió d'una frase d'entrada, onstruint de la forma més òptima p ossible la frase en l'idioma destí, en base a tota la informaió que el sistema té al seu abast. Si en la fase d'entrenament s'ha realitzat un prepro és de les dades, aleshores és impresindible que la frase a traduir siga sotmesa al mateix preproés, i p osteriorment, a una fase de p ostpro és, en la que es desfan els anvis realitzats al prepro és. Dins d'aquesta ategoria existeixen dues grans aproximaions: els sistemes basats en exemples 6 i els sistemes estadístis 7 [GV03℄. • Sistemes Basats en Exemples : L'idea prinipal d'aquesta aproximaió és que durant el pro és de traduió la frase d'entrada es ompara en una base de dades onstruïda a partir del orpus d'entrenament, generant-se hip òtesis i ombinant-les de forma apropiada ns obtindre la traduió orresp onent. Per 6 EBMT, Example-Based Mahine Translation . 7 SMT, Stadistial Mahine Translation . 6 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 7 #17 i i 1.1. Visió general de la traduió automàtia ser un p o més onrets, en primer llo es desomp osa la frase d'entrada en fragments, donant llo a un gran nombre de p ossibles hipòtesis o amins de traduió (ja que la desomp osiió es pot realitzar de moltes maneres diferents); en segon llo , els fragments es omparen amb la base de dades d'exemples i s'identiquen les seves traduions orresp onents; i en terer llo, es ombinen de forma adequada els fragments traduïts, originant la frase nal. • Sistemes Estadístis : L'aproximaió estadístia a la TA és molt similar a la seguida p els sistemes basats en exemples, p erò es desmara larament en el proés de omparaió-ombinaió emprat per aquests, ja que en el seu llo s'empren tèniques estadístiques tant en l'entrenament del sistema om en el pro és de traduió. Aquest treball es entra en el mar estadísti de la TA, amb la qual osa en la Seió 1.2 s'expliarà en ma jor detall els asp etes més imp ortants que onerneixen a la traduió automàtia estadístia. 1.1.3 Sistemes d'a juda a la traduió Com ja sab em, el prinipal prop òsit de la traduió automàtia és dissenyar sistemes apaços de traduir texts sense la partiipaió humana, és a dir, de forma ompletament automàtia. No obstant, la tenologia atual no p ermet assolir tal prop òsit [Kay97℄, amb la qual osa es requereix una p ost-ediió manual de les traduions proveïdes p er aquests sistemes. Aquests dos pro essos aïllats imp edeixen, d'una banda, que el sistema aprenga del oneixement del tradutor humà, i d'altra banda, que el tradutor humà obtinga beneis de les apaitats adaptatives i de l'eiènia que presenta d'un sistema de TA. Una forma de resoldre aquesta mana de feedbak és, preisament, donar llo a un espai oop eratiu on màquina i humà partiip en interativament en el pro és de tradu- ió [IC97℄, en entorns oneguts om sistemes d'a juda a la traduió 8 . Històriament, els sistemes d'a juda a la traduió i els sistemes de traduió automàtia han estat onsiderats sistemes diferents, enara que tenològiament semblants, dons po dem onsiderar que els sistemes d'a juda a la traduió són un superonjunt dels sistemes de traduió automàtia. Històriament, la interativitat entre sistemes de traduió i humans s'ha materialitzat en diferents enfo aments. Un dels més exitosos ha estat el basat en memòries de traduió, en el que l'usuari fa ús d'un sistema que ompta amb una base de dades immensa d'exemples de traduió. Un altre enfoament fou requerir la intervenió dels humans p er tal de resoldre ambigüitats de aire lèxi, sintàti o semànti del text d'entrada, o inlús mantindre i atualitzar diionaris d'usuari o busar a través d'ells [Slo85, WWC + 86℄, amb més o menys èxit. Posteriorment, el pro jete TransType [LFL00, LLL02, FLL02, Fos02℄ va aportar un nou enfo ament que onsistia en entrar la interativitat diretament al text traduït, integrant sistemes autònoms de TA en l'entorn interatiu. Aquest darrer enfoament va donar origen al que oneixem p er 8 En anglès, Computer-Assisted Translation Systems . JASC-DSIC-UPV 7
memoria 2010/11/17 19:32 page 8 #18 i i Capítol 1. Intro duió sistemes de traduió interatius-preditius, el quals estan reb ent en l'atualitat un ampli sup ort de la omunitat investigadora [Civ08, BBC + 09℄. Tot seguit detallem el funionament de les dues aproximaions més importants de la traduió assistida: els sistemes de memòria de traduió, i els sistemes interatiuspreditius. Sistemes de memòria de traduió Aquesta aproximaió es basa en la reopilaió d'exemples de traduió en una (presumiblement) extensa base de dades [UoG95℄. Durant el pro és de traduió, la frase origen és segmentada, de forma que p er a ada segment es realitza una era de l'exemple de traduió més semblant emmagatzemat a la base de dades. Si aquesta onté un segment en l'idioma origen que oinideix exatament en el segment busat, aleshores la traduió orresp onent és mostrada p er pantalla, amb un grau de similitud del 100%. Per ontra, si no s'ha trobat un segment idènti, aleshores es prop oriona la traduió més similar existent a la base de dades. Siga om siga, el sistema presenta a l'usuari la prop osta de traduió, de forma que aquest pot, b é aeptar la prop osta, o b é mo diar-la / orregir-la. En aquest darrer as, la traduió mo diada és emmagatzemada a la base de dades. Pot haver-hi asos en els que no es prop orione ap prop osta de traduió (p.e. no existeix a la base de dades ap segment amb un grau de similitud sup erior a un llindar mínim preestablert), amb la qual osa l'usuari ha de realitzar manualment la traduió que p osteriorment és emmagatzemada a la base de dades. Notar la gran similitud tenològia existent entre aquest tipus de sistemes i els sistemes de TA basats en exemples de traduió (Capítol 1.1.2): p o dem onsiderar aquests om una extensió dels sistemes de TA originals. Amb tot, aquests sistemes milloren les seves prestaions amb el pas del temps, ja que la realimentaió existent entre el sistema i l'usuari p ermet inrementar el nombre d'exemples existents a la base de dades, a la vegada que el sistema s'esp eialitza si es treballa amb dominis molt onrets. És p er això que aquests sistemes funionen esp e- ialment b é amb texts que presenten moltes rep etiions, o en traduions inrementals realitzades sobre do uments prèviament traduïts. Cal remarar que en aquests sistemes el motor de era és el punt ríti, ja que p er trobar oinidènies s'ha d'explorar grans quantitats d'informaió, així om identiar patrons i similituds en el as en que no es troben oinidènies. Per tant, la rapidesa del motor de era deneix en gran mesura les prestaions del sistema, donat que la latènia dels resultats de la era afeta diretament a l'usuari que es troba interatuant amb el sistema. D'altra banda, al notar que la qualitat de les traduions dep èn de la grandària de la base de dades, però al mateix temps una grandària exessiva de la base de dades p ot induir a latènies de era elevades (degut a la ma jor omplexitat del pro és de era). Existeixen diferent sistemes omerials de memòria de traduió om són Trados (SLD Trados Studio) [HK℄, Dejavú [Dej℄ o Google Translate Toolkit [Go o℄. 8 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 9 #19 i i 1.2. Traduió automàtia estadístia Sistemes interatius-preditius Aquesta aproximaió pretén fusionar els paradigmes de la traduió assistida i la traduió automàtia. Davant d'un text d'entrada, un sistema omplet de TA pro dueix hip òtesis de traduió de frases ompletes o de p orions d'aquestes, que po den ser aeptades o orregides p er l'usuari. Però la araterístia més interessant d'aquests sistemes és que són apaços de prop orionar prediions de traduió [Civ08℄: davant d'una traduió parial intro duïda p er l'usuari d'una frase origen (prex), el sistema prediu les traduions més probables que ompleten la frase (suxos), de les quals l'usuari p o drà aeptar o modiar una d'elles. Siga om siga, ada segment orregit és pro essat p el sistema de TA sub jaent p er tal de millorar la qualitat tant de les traduions om de les prediions. Així dons, aquests sistemes són requerits p er generar prediions adequades i de forma eient. 1.2 Traduió automàtia estadístia En aquesta seió intro duirem alguns oneptes bàsis p er entendre de forma intuïtiva l'enfo ament estadísti de la TA. D'ara endavant onsiderarem el problema de traduir una frase f d'un voabulari 9 d'entrada F a una frase e d'un voabulari d'eixida E 10 . 1.2.1 Coneptes bàsis de probabilitat En primer llo introduirem una sèrie de no ions bàsiques estadístiques que seran àmpliament emprades en aquest doument, esp eialment el àlul de probabilitats, expliant intuïtivament el seu signiat dins del ontext de la TA. El àlul de probabilitats, om b é sab em, és una forma de quantiar la inertesa que tenim sobre les oses, om per exemple la possibilitat de si demà plourà o no, o la p ossibilitat de que la nostra partiipaió en un sorteig ens onvertisa en milionaris. Aquesta inertesa es p ot apturar fàilment amb l'ús de variables aleatòries: una variable aleatòria X representa el resultat d'un esdeveniment en onret i pren una sèrie de valors dependents del resultat d'eixe esdeveniment. Per exemple, si la variable aleatòria X representa l'esdeveniment resultat del llançament d'una moneda, i onsiderem om a p ossible resultat de l'esdeveniment ara ( X= ara ), aleshores la probabilitat de que el resultat de llançar una moneda siga ara és P(X= ara ) = 1/2 (p er simpliitat esriurem P( ara ) = 1/2 ). Tota variable aleatòria segueix una distribuió de probabilitat, que és la forma en que es reparteix la totalitat de la massa de probabilitat entre tots els suessos p ossibles. Hi ha asos en els que és fatible estimar la distribuió de probabilitat que segueixen els valors que p ot prendre d'una variable aleatòria mitjançant un anàlisi freqüenial (reopilar dades de p ossibles suessos i estimar la probabilitat d'o urrènia de adasun d'ells), p erò hi ha d'altres en els que la mesura d'inertesa dels 9 Anomenarem voabulari al onjunt de totes les paraules que p ertanyen un llenguatge. 10 Per onveni, s'utilitza f ( frenh, foreign ) i e ( english ) per denotar les frases d'entrada i d'eixida resp etivament. JASC-DSIC-UPV 9
memoria 2010/11/17 19:32 page 10 #20 i i Capítol 1. Intro duió suessos es pot a justar a alguna distribuió de probabilitat ja oneguda que es dona llo en altres esenaris 11 . Per exemple, el llançament d'una moneda segueix una distribuió de probabilitat uniforme, en la que tots els possibles esdeveniments són equiprobables: P( ara ) = P( reu ) = 1/2 . Imaginem que p er uns moments no se'n reem i deidim llançar, p er exemple, un milió de vegades una moneda a l'aire, a veure que passa. Comprovaríem om aproximadament la meitat de vegades apareixeria ara, i l'altra meitat apareixeria reu: hauríem estimat la distribuió de probabilitat mitjançant un anàlisi freqüenial, que no és més que omptar freqüènies d'apariió d'un esdeveniment i normalitzar amb total d'esdeveniments. Aquest tipus d'estimaió, en la qual hem tratat d'a justar la nostra distribuió de probabilitat el màxim p ossible a les dades que hem reaptat, s'anomena estimaió p er màxima versemblança. Per exemple, sup osem que al llançar un milió de vegades una moneda a l'aire hem obtingut ara 500.427 vegades: P( ara ) = N( ara ) N( llançaments )=500427 1000000 = 0.500427 ≈1/2 (1.1) Com p o dem omprovar, no és neessari invertir tant de temps reopilant dades sobre aquesta variable aleatòria: sab em que el resultat del llançament d'una moneda ve mo delat p er una distribuió uniforme. En denitiva, p o dem veure una distribuió de probabilitat om una funió que assigna, a ada sués denit sobre una variable aleatòria, la probabilitat de que aquest sués s'esdevinga. Tota distribuió de probabilitat ompleix dues propietats: en primer llo , la probabilitat d'un sués en onret pren valors entre 0 i 1 (veure Equaió (1.2)), i en segon llo , la suma de les probabilitats de tots els p ossibles suessos deu sumar 1 (veure Equaió (1.3)). ∀x: 0 ≤p(x)≤1 (1.2) X x p(x) = 1 (1.3) Amb aquestes no ions bàsiques, es entrarem ara en el ontext de la TA. En aquest do ument tratarem prinipalment amb dues variables aleatòries: F (frase d'entrada) i E (frase d'eixida), amb valors e i f , resp etivament. Tot seguit detallem les expressions de probabilitat que emprarem a aquest do ument: p(e) És la probabilitat a priori . Representa la p ossibilitat de que e s'esdevinga. Per exemple, si e representa a la frase en anglès I like b ees, aleshores p(e) expressa la probabilitat de que una persona onreta pronunie en un moment donat la frase I like b ees. Notar que tamb é ens trobarem p(f) , amb un signiat anàleg. 11 Hi existeixen nombroses distribuions de probabilitat om són la uniforme, la normal (o gaussiana), la binomial o la multinomial, entre d'altres. 10 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 11 #21 i i 1.2. Traduió automàtia estadístia p(f|e) És la probabilitat ondiional. Representa la p ossibilitat que s'esdevinga f donat que e s'ha esdevingut. Per exemple, si e representa la frase en anglès I like b ees, i f representa la frase en atalà "Demà plourà", aleshores p(f|e) expressa la probabilitat de que un tradutor exp ert, després de llegir la frase e , la traduïsa en f (no sembla molt probable). Ara b é, si en anvi onsiderem que f representa la frase en atalà "M'agraden les ab elles", aleshores la osa anvia. Cal notar que tamb é ens trobarem p(e|f) , amb un signiat anàleg. p(e, f) És la probabilitat onjunta. Representa la possibilitat de que s'esdevinguen simultàniament e i f . Si e i f són indep endents (no existeix ap inuenia entre una i altra), aleshores p(e, f) = p(e)p(f) . Per exemple, si e representa l'event Llançar una moneda i treure ara, i e Llançar una moneda i treure reu, òbviament aquests esdeveniments no interfereixen l'un en l'altre, amb la qual osa la p ossibilitat de que a l'efetuar dos llançaments de moneda, en primer llo s'obtinga ara i després reu és p(e, f) = p(e)p(f) = 1/2×1/2 = 1/4 . D'altra banda, si e i f estan relaionades, aleshores s'aplia l'anomenada regla de la adena, de forma que p(e, f) = p(e)p(f|e) (o de forma equivalent, p(e, f) = p(f)p(e|f) ). Això signia que la probabilitat de que e i f s'esdevinguen simultàniament ve donada per la probabilitat de que e s'esdevinga multipliat p er la probabilitat de que si e s'esdevé, aleshores f tamb é s'esdevé. En el as de la TA, si e i f són traduions mútues, aleshores existeix una lara relaió d'inuènia entre elles. Cal notar que p(e, f) i p(f, e) representen el mateix onepte. Per aabar, intro duïm la regla de Bayes, que és el pilar estadísti sobre el qual es fonamenta la TAE: p(e|f) = p(f, e) p(f)=p(e)p(f|e) p(f) (1.4) La regla de Bayes ens p ermetrà reformular la forma de alular om de b ona o dolenta és una frase e om a traduió d'una frase f . Més endavant raonarem sobre açò. 1.2.2 Traduió estadístia Po dem denir més formalment el problema al que s'afronta la TAE de la següent forma: donada una frase f d'un voabulari origen F , desitgem trobar aquella frase e d'un vo abulari destí E que maximitza p(e|f) , és a dir, busquem la traduió més probable ˆe : ˆe= argmax e p(e|f) (1.5) La funió argmax la po dem llegir de la següent forma: de totes les p ossibles frases (traduions) e , busquem aquella que maximitze el valor de p(e|f) , és a dir, la traduió més probable ˆe . Ara b é, om obtenim el valor de p(e|f) p er a ada p ossible JASC-DSIC-UPV 11
memoria 2010/11/17 19:32 page 12 #22 i i Capítol 1. Intro duió Transformació Cerca global ê = argmax_e p(e) · p(f|e) Transformació Frase d’eixida Frase d’entrada f e Model de Traducció p(f|e) Model de Llenguatge p(e) Figura 1.2: Arquitetura general del pro és de traduió basat en el raonament sobre la regla de Bayes. adena e ? La regla de Bayes ens p ermet raonar sobre el àlul d'aquesta distribuió de probabilitat: ˆe= argmax e p(e|f) = argmax e p(e)p(f|e) p(f)= argmax e p(e)p(f|e) (1.6) Cal notar que, om busquem la traduió més probable, p o dem estalviar-nos mo delar la distribuió de probabilitat p(f) , ja que no dep èn d' e i p er tant no afeta a la funió argmax . D'aquesta manera, la traduió ˆe més probable és aquella que maximitza el produte de dos termes: d'una banda, la probabilitat que s'esdevinga la frase e (p.e. la p ossibilitat de que algú pronunie en un moment donat la frase e ), i d'altra banda, la probabilitat de generar f havent observat e (p.e. la possibilitat de que algú traduïsa e en f ). Aquesta aproximaió es oneix om el mo del de la font i del anal [B + 90℄, el qual deneix l'equaió fonamental de la traduió automàtia estadístia [B + 93℄. Com veurem més endavant, p(e) es alula mitjançant mo dels de llenguatge (veure Seió 1.2.3), i p(f|e) mitjançant mo dels de traduió (veure Seió 1.2.4). A la Figura 1.2 p o dem observar l'arquitetura general de la traduió automàtia estadístia basada en la inferènia de Bayes [GV03℄. 12 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 13 #23 i i 1.2. Traduió automàtia estadístia Apliaió de la regla de Bayes Si analitzem un p o més el signiat de l'Equaió (1.6), p o dem omprovar om se'ns insta a generar una frase e en l'idioma destí p er p osteriorment onvertir-la en una frase f en l'idioma origen, quan en realitat el que ens interessa és justament el ontrari, onvertir una frase f en una frase e en un idioma destí. Per que això, i no mo delar diretament p(e|f) ? Tot seguit entendrem per què amb un senzill exemple [Kni99b℄. Anem a raonar sobre la relaió existent entre infermetats i símptomes. Si onsiderem que f és un onjunt de símptomes i e és una infermetat en onret, des d'un punt de vista mèdi seria molt interessant p o der diagnostiar immediatament una infermetat a partir d'uns símptomes, és a dir, mo delar diretament p(e|f) . No obstant, és molt ompliat onstruir diretament aquest model, ja que hi ha moltes infermetats que p o den provo ar els mateixos símptomes. En anvi, sí que es oneix amb ertesa quins símptomes són provo ats p er una infermetat en onret, amb la qual osa és molt més viable onstruir un mo del p(f|e) . D'altra banda, tamb é seria fatible mo delar p(e) , la freqüènia d'apariió d'una infermetat en la p oblaió. Així dons, p er p o der soluionar el problema de mo delar diretament p(e|f) , p o dem raonar sobre la probabilitat de que una infermetat e s'esdevinga ( p(e) ), així om en la probabilitat de que els símptomes f que pateix un paient siguen provo ats p er eixa infermetat e en onret ( p(f|e )). Tanmateix, des d'un punt de vista lingüísti no sembla tant obvi que mo delar p(f|e) resulte menys omplex que p(e|f) : en realitat, i om veurem més endavant, a partir de la mateixa informaió p o drem onstruir indistintament ambdós mo dels. L'únia raó p er la qual s'aplia la regla de Bayes és que s'inlou una font d'informaió addiional i indep endent, p(e) , que ens p ermetrà millorar la qualitat de les traduions, i que a més resulta molt més fàil de onstruir, ja que aquest mo del dep èn úniament del llenguatge destí i p er tant p ot ser onstruït a partir d'un orpus monolingüe (om és obvi, és molt més fàil obtindre text monolingüe que text bilingüe). Ap ortaions dels mo dels al pro és de traduió Anem a expliar de forma intuïtiva allò que ap orten adasun dels mò duls que hem obtingut al raonar mitjançant la regla de Bayes: el mo del de llenguatge p(e) , i el mo del de traduió p(f|e) [Kni99b℄. D'una banda, sup osem que s'assigna un valor alt a p(f|e) sols si les paraules de la frase f són en general traduions de les paraules de la frase e . Baix aquesta assump ió, les paraules de f p o drien aparèixer en qualsevol ordre, així que p(f|e) no seria un b on mo del p er traduir frases de F a frases de E . D'altra banda, sup osem que assignarem un valor alt a p(e) si i sols si e és una frase gramatialment orreta, osa raonable p erò molt ompliada en la pràtia. Aleshores, si utilitzem amb dues fonts d'informaió en el pro és de onvertir la frase observada f en la seva traduió més probable e , d'aord amb l'Equaió (1.6) a ada p ossible e se li assignarà una puntuaió p(e)p(f|e) . El mo del p(f|e) ens garantirà que una hip òtesi e ontindrà paraules que en general seran traduions de les paraules de f . Per exemple, si onsiderem la frase f= la bruixa verda , les frases JASC-DSIC-UPV 13
memoria 2010/11/17 19:32 page 14 #24 i i Capítol 1. Intro duió e1= the green with i e2= with the green són dues traduions a les quals el mo del que estem onsiderant atorgarà una b ona puntuaió (molt p ossiblement la mateixa), p erò és obvi que e2 no és una b ona traduió de f . És en aquest aspete on intervé el fator p(e) , ja que aquest assignarà una puntuaió més baixa a aquelles frases no gramatials, i vieversa. Aleshores, en el òmput global de p(e|f) , e1 obtindrà una puntuaió ma jor que e2 . Donada aquesta p ersp etiva, p(e) efetivament es preoupa per l'ordre de les paraules de la frase d'eixida, mentre que p(f|e) no, amb la qual osa sembla més fàil onstruir p(f|e) que mo delar diretament p(e|f) . No obstant, seguir aquesta assump ió presenta ertes deiènies. Imaginem que el nostre mo del de traduió p(e|f) ens prop oriona la següent seqüènia de paraules: vaig del i vaig blava l'altre meu a anar una ami dia Toni serp asa trobar . Sembla bastant omplex reordenar aquesta frase, ns i tot per a un ésser humà, el qual disp osa d'una font de oneixement molt més ompleta que la d'una màquina. Per tant, arrib em a la onlusió de que p(f|e) deuria de saber almenys un p o sobre l'ordre de les paraules, i no limitar-se a prop orionar un onjunt de paraules sense més. De la mateixa forma, resultaria molt útil si el mo del de llenguatge p(e) ap orta informaió sobre quines paraules elegir en la traduió nal. Per p osar un exemple, la prep osiió en anglès in p ot traduir-se al atalà de forma equivalent om a o en . Imaginem que, om a traduió a la frase I live in Beniolet , el mo del de traduió ens prop oriona dues p ossibles hip òtesis equiprobables: Vis en Beniolet i Vis a Beni- olet . La segon frase es troba en un atalà més orrete, amb la qual osa el mo del de llenguatge li assignarà ma jor probabilitat, i p er tant s'erigirà om la traduió més probable. Fins al moment hem presentat de forma intuïtiva om es modelitza el pro és de traduió, en el qual intervenen dos mò duls indep endents: un mo del de llenguatge p(e) i un mo del de traduió p(f|e) . Tot seguit desrivim més a fons aquests dos mo dels. 1.2.3 Mo dels de llenguatge Com ja hem esmentat adés, el mo del de llenguatge és l'esp eialista de l'idioma destí, dons és apaç de donar ma jor imp ortània a aquelles traduions gramatialment orretes, en detriment d'altres traduions més impreises. Ara b é, om obté aquest mo del tot el oneixement que té al seu abast? Els as ideal seria onferir al mo del informaió sobre les propietats gramatials, sintàtiques i semàntiques del llenguatge, i inlús informaió sobre allò que diuen i esriuen les p ersones. Ara b é, obtindre i representar tota aquesta informaió és una tasa tant exessivament omplexa que no és assumible. En la pràtia, resulta molt més senzill emmagatzemar frases que es p o den esriure o pronuniar en el llenguatge que es mo delitza, reopilades a partir d'un orpus monolingüe d'exemples de frases, estimant la distribuió de probabilitat de les frases en E p er màxima versemblança. Per exemple, si al reopilar 10000 frases en atalà detetem que la frase M'agrada la assola al forn apareix 12 vegades, aleshores la probabilitat de que aquesta frase s'esdevinga és p( M'agrada la assola al forn ) = 14 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 15 #25 i i 1.2. Traduió automàtia estadístia 12/10000 = 0.0012 . Seguir aquesta aproximaió presenta un problema: és imp ossible apturar totes les frases que es p o den generar en un llenguatge (p.e. la frase El meu besnét menja gossos verds i àguiles blaves és ompletament orreta, però p o freqüent). Aleshores, ap la p ossibilitat que durant el pro és de traduió s'assigne una p(e) igual a zero a frases p erfetament orretes degut a que mai s'han vist en l'entrenament del mo del. Per tant, no serviria de res tenir un b on mo del de traduió p(f|e) si el mo del de llenguatge p(e) assigna probabilitat zero a frases orretes, ja que en el òmput total de p(e|f) obtindríem una probabilitat nul · la. Arribats a aquest punt, ens donem ompte que no és neessari emmagatzemar una gran base de dades de frases p er jutjar si una frase és gramatialment orreta o no (p ensem en l'exemple anterior). En anvi, si trossegem la frase i els segments resultants són gramatialment orretes, i després aquests segments els p o dem ombinar de forma raonable, aleshores p o dem armar que la frase és b ona. I és preisament aquesta aproximaió la que més b ones prestaions onfereix als mo dels de llenguatges i la més omunament emprada als sistemes estadístis de traduió automàtia [GV03℄. Mo dels d' n -grames D'aord amb l'aproximaió que aab em d'exp osar, la frase d'eixida e es trosseja en segments o sub adenes. Una sub adena d' n paraules s'anomena n -grama, de forma que, p er exemple, si n= 2 parlem de bigrames, si n= 3 parlem de trigrames, o si n= 1 parlem d'unigrames (o simplement paraules). Aleshores, si una frase està formada p er una sèrie d' n -grames raonables, és molt probable que siga una frase gramatialment orreta [Kni99b℄. En general, i més formalment, un mo del d' n -grames es deneix de la següent forma [GV03℄: p(e) = I Y i=1 p(ei|e1,...,ei−1) (1.7) on I és la longitud de la frase e , ei és la paraula i -èsima de la frase e , i e0=e−1= . . . =e−n+1 =eI+1 = $ , que és un símbol emprat p er delimitar les frases. En realitat, l'Equaió (1.7) és el resultat apliar a p(e) la regla de la adena a nivell de paraula [Ko e10℄: p(e) = p(e1, e2, ..., eI) = p(e1)p(e2|e1)p(e3|e2, e1). . . p(eI|e1, ..., eI−1) (1.8) D'aquesta forma, la probabilitat del model p(e1, e2, ..., eI) és el pro dute de les probabilitats de ada paraula ei donada la història de la mateixa 12 . Ara b é, és molt ostós i 12 Conjunt de paraules preedents a la paraula onsiderada. JASC-DSIC-UPV 15
memoria 2010/11/17 19:32 page 22 #32 i i Capítol 1. Intro duió ple lletde the glass està el got is full of milk 1 1 2 2 3 3 4 4 5 5 6 6 a:{1→4,2→5,3→6,4→3,5→1,6→2} Figura 1.4: Exemple d'alineament en el que les paraules alineades o up en p osiions diferents en adasuna de les frases. els bonics pobles the nicest villages 1 1 2 2 3 3 4 més a:{1→1,2→3,3→2,4→2} Figura 1.5: Exemple d'alineament en el que una paraula d'eixida es troba relaionada amb més d'una paraula d'entrada. Cal notar que, a p esar d'estar mo delitzant la traduió d'anglès a atalà (mo del invers), la funió d'alineament assigna p osiions de paraules en atalà a p osiions de paraules en anglès. Com p o dem observar, l'alineament de la Figura 1.3 és molt senzill, ja que les paraules alineades presenten el mateix ordre a la frase d'entrada i d'eixida. En general, p o dem trobar-nos en aquests asos: 1. Les paraules alineades apareixen en el mateix ordre a la frase d'entrada i d'eixida (Figura 1.3). 2. Les paraules alineades p o den aparèixer en ordres diferents a adasuna de les frases (Figura 1.4). 3. Una paraula de la frase d'eixida e p ot estar alineada amb més d'una paraula de la frase d'entrada f p er expressar el mateix onepte (Figura 1.5). 22 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 23 #33 i i 1.3. Aproximaions a la traduió automàtia estadístia és un it is xiulet ! whistle ! 1 1 2 2 3 3 4 4 5 a a:{1→2,2→3,3→4,4→5} Figura 1.6: Exemple d'alineament en el que paraules de la frase d'eixida no han estat alineades amb ap paraula de la frase d'entrada. hi haver van NULL yesterday discussions there were discussions 1 1 2 2 3 3 4 4 5 ahir 0 a:{1→1,2→0,3→3,4→3,5→4} Figura 1.7: Exemple d'alineament en el que paraules de la frase origen es trob en alineades amb la paraula destí esp eial NULL . 4. Poden haver-hi paraules de la frase d'eixida e que no tenen un lar equivalent en la frase d'entrada f , i que p er tant no són alineades. (Figura 1.6). 5. De la mateixa forma, p o den haver-hi paraules de la frase d'entrada f que no tenen relaió amb ap paraula de la frase d'eixida. Aquest as rep un trate esp eial: donat que la funió d'alineament és ompleta i p er tant totes les paraules de la frase d'entrada deuen estar alineades amb exatament una paraula de la frase d'eixida, s'intro dueix una paraula esp eial, NULL 16 , que s'alinea amb les paraules de la frase d'entrada que es trob en en aquest as (Figura 1.7). Com hem esmentat abans, els nostres orpus d'entrenament no es trob en alineats a nivell de paraula, sinó a nivell de frase, amb la qual osa resulta neessari alular aquests alineaments p er p o der estimar els paràmetres del mo del de tradu- ió. Aleshores, un model de traduió basat en paraules presenta de forma implíita un mo del d'alineament que haurem d'estimar, de forma que estarem mo delitzant 16 Paraula nul · la. JASC-DSIC-UPV 23
memoria 2010/11/17 19:32 page 24 #34 i i Capítol 1. Intro duió p(f, a |e) (és a dir, donada la frase e , quina és la probabilitat d'obtenir la frase f amb un alineament a ). Mo dels d'IBM Amb tot, aab em de prop osar un mo del de traduió p(f, a |e) que onsidera l'alineament existent entre les paraules de les frases d'entrada i d'eixida om una variable o ulta (no disp osem d'aquests alineaments). Aquest model és onegut om el Mo del 1 d'IBM, prop osat p er P.F. Brown i altres investigadors d'IBM a l'any 1990 [B + 90, B + 93℄, i que va sup osar una gran revoluió en el amp de la TA. El primer mo del d'IBM deneix la probabilitat de traduir una frase d'eixida e= e1. . . eI de longitud I en una frase destí f=f1...fJ de longitud J , amb una funió d'alineament a que relaiona ada p osiió (paraula) de la frase d'entrada fj amb una p osiió (paraula) de la frase d'eixida ei , d'aquesta forma [Ko e10℄: p(f, a |e) = J Y j=1 1 I+ 1 t(fj|ea(j)) = 1 (I+ 1)J J Y j=1 t(fj|ea(j)) (1.22) és a dir, la probabilitat de traduir una frase e en una frase f d'aord amb un alineament a és el pro dute de les probabilitats del mo del de traduió lèxia p er traduir adasuna de les J paraules de la frase d'entrada a la posiió j en les seves respetives paraules d'eixida a la p osiió a(j) , normalitzat p el nombre total d'alineaments p ossibles (notar que p er la inlusió de la paraula NULL hi ha un total de I+ 1 paraules d'eixida, a ombinar amb J paraules d'entrada). Si a l'exemple de la Figura 1.3 li apliquem la deniió d'aquest mo del, la probabilitat de traduir la frase the glass is ful l of milk en el got està ple de l let és: p(f, a |e) = 1 76·t( el | the )·t( got | glass )·t( està | is )·t( ple | ful l )·t( de | of )·t( l let | milk ) La relaió existent entre un mo del de traduió i el mo del d'alineament sub jaent ve donat p er la següent expressió [Ko e10, GV03℄: p(f|e) = X a p(f, a |e) (1.23) és a dir, la probabilitat de que la frase e es traduisa en la frase f onsidera tot p ossible alineament entre e i f . En la pràtia sols es onsidera l'alineament més probable (l'anomenat alineament de Viterbi) p er aproximar el àlul del sumatori denit sobre a [GV03℄: X a p(f, a |e)≈max ap(f, a |e) (1.24) 24 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 25 #35 i i 1.3. Aproximaions a la traduió automàtia estadístia Cal notar que l'alineament més probable és aquell que maximitza la probabilitat de que la frase e es traduisa en la frase f : ˆa= argmax a p(f, a |e) (1.25) Un mo del de traduió basat en paraules dep èn d'una sèrie de paràmetres θ que són estimats maximitzant la versemblança per a un orpus d'entrenament {(fn, en)∈C: n= 1,...,N} [GV03℄: ˆ θ= argmax θ N Y n=1 X a pθ(fn, a |en) (1.26) Ara bé, p er a realitzar aquesta estimaió de paràmetres tenim un problema. Des d'un primer moment hem assumit que disp osàvem dels alineaments paraula p er paraula p er a ada parell de frases del orpus d'entrenament, amb la qual osa estimar les probabilitats de traduió lèxia (o siga, estimar els paràmetres del mo del de traduió lèxia) p er màxima versemblança ha estat quasi trivial. Però om sabem, no disp osem de ap mo del d'alineament. No p o dem estimar el nostre mo del de traduió a partir d'informaió inompleta: és p er això que l'alineament entre paraules és onsiderat una variable o ulta al nostre mo del. D'una banda, si oneixerem els alineaments entre paraules, resultaria fàil estimar el model de traduió de paraules. Per l'altra banda, si disp osarem del mo del ja estimat, seria p ossible obtindre els alineaments de paraules més probables p er a ada parell de frases. Malauradament, no disp osem ni d'una osa ni de l'altra. Ara b é, existeix una tènia amb la qual sí p o dem fer front a aquest problema. L'algoritme EM 17 [DLR77℄ permet enarar el problema de la informaió inompleta i de l'estimaió de paràmetres de mo dels probabilístis amb variables o ultes. Podem trobar més informaió al resp ete a [Koe10, B + 93℄. A més del Mo del 1 d'IBM, existeixen quatre models de omplexitat reixent que intro dueixen millores resp ete als mo dels anteriors. Aquests són: • Mo del 2 d'IBM : Afegeix al mo del original un mo del d'alineament absolut. • Mo del 3 d'IBM : Afegeix un mo del de fertilitats 18 . • Mo del 4 d'IBM : Afegeix un mo del d'alineament relatiu. • Mo del 5 d'IBM : Esmena la deiènia que presenten onjuntament els models 3 i 4. Per a més informaió sobre els models d'IBM, remetem al letor a [Ko e10, GV03, B + 90, B + 93℄. 17 Expetation-Maximization Algorithm . 18 Mo dela la probabilitat de que una paraula de la frase origen s'alinee amb n paraules de la frase destí. JASC-DSIC-UPV 25
memoria 2010/11/17 19:32 page 26 #36 i i Capítol 1. Intro duió my best friend ’s girlfriend la nuvia has lived for del meu millor amic ha viscut durant 10 anys 10 years in bocairent . a bocairent . Figura 1.8: Exemple del pro és de traduió automàtia en sistemes basats en seqüènies de paraules. 1.3.2 Mo dels basats en seqüènies de paraules En la seió anterior hem presentat un mo del que es basa en la traduió de paraules aïllades. Ara bé, om ja s'ha esmentat, traduir a nivell de paraula no és molt reomanable, dons hi ha paraules d'un llenguatge origen que es p o den traduir en dues o més paraules del llenguatge destí, i vieversa. Considerar solament paraules aïllades, a més, imp edeix apturar el ontext en que es trob en, i en onseqüènia, la semàntia o signiat de la paraula, informaió que resultaria molt valuosa a l'hora d'esollir entre múltiples aep ions. Aquests són els prinipals motius p els quals resulta més onvenient esollir una unitat bàsia de traduió de ma jor grandària que p ermeta apturar informaió ontextual. Aquest element bàsi, que p ot englobar una o més paraules, s'anomena seqüènia de paraules 19 . Les seqüènies de paraules s'obtenenen dividint una frase ompleta en segments de paraules ontigues i de longitud variable. La Figura 1.8 il · lustra om funionen aquests sistemes: la frase d'eixida e és segmentada en seqüènies de paraules, de forma que ada seqüènia e és traduïda al llenguatge origen F , originant seqüènies f que són reordenades a posteriori (si s'esau). Si ens xem en l'exemple, la seqüènia de paraules en anglès girlfriend es tradueix de forma òptima al atalà om la núvia . Per tal de onèixer les traduions més probables p er a ada seqüènia de paraules, haurem de disposar d'una distribuió de probabilitat que ens prop orione la probabilitat d'obtindre una seqüènia de paraules d'entrada f om a traduió d'una seqüènia e d'eixida (atès que onsiderem el mo del de traduió invers). Cal destaar que els sistemes de TA basats en seqüènies de paraules no empren ap mèto de lingüísti p er segmentar una frase. Per exemple, si ens xem novament en l'exemple de la Figura 1.8, una de les seqüènies de paraules obtingudes és has lived for , la qual, baix un d'un punt de vista sintàti, representa un agrupament inorrete, dons seria més lògi segmentar de forma separada verb ( has lived ) i omplement ( for 10 years ). No obstant, realitzar aquest tipus d'agrupaions ( has lived for ) resulta molt útil, ja que p ermet apturar fàilment el signiat sempre onfús de les prep osiions. Vegem un exemple: si tratarem de traduir de forma aïllada la prep osiió for p o dríem esollir entre per, per a, a ausa de, en, a favor de, durant, , et. Ara b é, atenent al ontext en que apareix, la traduió més apropiada sembla ser durant . Aquesta valuosa informaió es aptura agrupant verb i prep osiió en la segmentaió, i generant 19 Phrase , en anglès. 26 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 27 #37 i i 1.3. Aproximaions a la traduió automàtia estadístia la orresp onent seqüènia de paraules traduió (en el nostre as has lived for , en ha visut durant ). Per tant, realitzar agrupaments de paraules en llo de onsiderar paraules aïllades ens p ermetrà resoldre moltes de les ambigüitats que se'ns puguen presentar al pro és de traduió. Addiionalment, emprar aquest enfo ament basat en seqüènies de paraules omp orta un b enei extra. El p o der obtenir segments de longitud variable a partir de les frases origen del orpus d'entrenament ens p ermet memoritzar les seves resp e- tives traduions, p o dent arribar a emmagatzemar ns i tot traduions de frases ompletes. Ara b é, en la pràtia el nombre de paraules que p ot abastar una seqüèn- ia és limitat (típiament a 7), dons la omplexitat d'aquests mo dels (el nombre de paràmetres) reix exponenialment onforme a la longitud o grandària màxima que p o den assolir les seqüènies de paraules. Deniió del mo del de seqüènies de paraules Formalment, un mo del de traduió invers p(f|e) basat en seqüènies de paraules deneix la probabilitat de traduir una frase d'eixida e=e1, e2,...,eK , segmentada en K seqüènies de paraules, en una frase d'entrada f=f1, f2, . . . , fK de la següent forma: p(f|e) = K Y k=1 p(fk|ek) (1.27) és a dir, p(f|e) es deneix om el pro dute de les probabilitats de traduir ada seqüènia de paraules ek en fk . Cal notar que ambdues frases e i f presenten el mateix nombre de segmentaions, fet p el qual tota seqüènia de paraules d'eixida ek genera una seqüènia de paraules d'entrada fk durant el pro és de traduió. Extraió de seqüènies de paraules Com ja sab em, partim d'un orpus de parells de frases {(fn, en)∈C:n= 1,...N} , a partir del qual s'obtenen els parells de seqüènies de paraules (f, e) , que són els paràmetres del nostre model. Com s'obtenen aquestes seqüènies de paraules? És obvi que un riteri aleatori no té gens de sentit, dons a banda de que p er ada parell de frases es po drien extraure desenes, entenars, o inlús milers de parells de seqüèn- ies, osa que seria impossible de gestionar, extraure per exemple un hip otèti parell de seqüènies de paraules ( 10 anys , my best friend ), és inútil i ontrapro duent. Un p ossible mèto de seria onsiderar la segmentaió de les frases del orpus d'entrenament om una variable o ulta en el mo del, i estimar les segmentaions més probables per màxima versemblança apliant un entrenament Expetation-Maximization [DLR77℄. No obstant, emprar aquesta tènia d'estimaió és una tasa molt ostosa, així que optarem p er una estratègia alternativa més manejable basada en tèniques heurístiques, a osta de p erdre erta orreió i rigor estadísti. Es trata de partir dels alineaments de paraules p er a ada parell de frases (que es po den obtindre mitjançant els mo dels d'IBM, Seió 1.3.1) en amb dues direions de traduió, ombinar-los JASC-DSIC-UPV 27
memoria 2010/11/17 19:32 page 28 #38 i i Capítol 1. Intro duió pense que Lídia serà molt bona directora I think that Lídia will be a very good head teacher Figura 1.9: Exemple d'extraió de parells de seqüènies de paraules a partir de l'alineament entre paraules d'un parell de frases. apliant un algorisme heurísti, i extraure aquells parells de seqüènies de paraules que siguen onsistents amb els alineaments ombinats. Un parell de seqüènies de paraules (f, e) és vàlid i onsistent amb un alineament A si totes les paraules f1,...,fn∈f que presenten alineaments en A trob en totes les seves paraules alineades en la seqüènia e , i vieversa. Més formalment [Koe10℄: (f, e) és onsistent amb A⇔ ∀fj∈f: (fj, ei)∈A⇒ei∈e∧ ∧ ∀ei∈e: (fj, ei)∈A⇒fj∈f∧ ∧ ∃fj∈f, ei∈e: (fj, ei)∈A (1.28) Cal notar que l'última ondiió determina que un parell de seqüènies de paraules deu ontenir almenys un alineament entre paraules. Per desomptat, es p o den inloure paraules no alineades, ja que no es violaria ap de les ondiions estipulades a l'Equaió (1.28). Això signia que, quant menys alineaments, més p ossibles parells de seqüènies de paraules a extraure, a exep ió del as extrem (ap alineament), dons no es p o dria extraure ap seqüènia de paraules al violar-se la terera ondiió. 28 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 29 #39 i i 1.3. Aproximaions a la traduió automàtia estadístia Figura 1.10: Exemples de p ossibles seqüènies de paraules onsistents i in- onsistents, dep enent de l'alineament entre les paraules d'un parell de frases qualsevol. A la Figura 1.9 p o dem observar un exemple d'extraió de seqüènies de paraules a partir d'un alineament entre paraules d'un parell de frases. En la quadríula es mostren els alineaments existents entre les paraules que formen part de la frase en anglès I think that Lídia wil l be a very good teaher i en atalà pense que Lídia serà molt bona diretora . Les zones negres denoten l'existènia d'un alineament entre paraules, mentre que la zona gris (inlo ent les zones negres dels alineaments) determina un parell de seqüènies de paraules extretes de forma vàlida ( serà molt bona diretora - wil l be a very good head teaher ). Fixem-nos en que les restriions adés formulades (veure Equaió (1.28)) es ompleixen: d'una banda existeix almenys un alineament entre les paraules que formen part de les seqüènies de paraules extretes, i d'altra banda s'abasta tot p ossible alineament de les paraules inloses. Aquest és només un dels nombrosos parells de seqüènies de paraules que es p o den extraure partint d'aquest alineament. Podem observar, a ontinuaió, part dels p ossibles parells de seqüènies de paraules que es po den extreure de forma vàlida: pense I think pense que I think that que that pense que Lídia I think that Lídia Lídia Lídia que Lídia that Lídia pense que Lídia serà I think that Lídia wil l be ... pense que Lídia serà molt bona diretora I think that Lídia wil l be a very good teaher D'altra banda, la Figura 1.10, extreta de [Ko e10℄, mostra asos en els que un p ossible parell de seqüènies de paraules és onsistent o no donat l'alineament entre paraules d'un parell de frases. Tenint en ment que totes les paraules que formen part del parell de seqüènies deuen d'estar alineades les unes amb les altres (si és que presenten algun alineament), p o dem determinar que el primer exemple (esquerra) és ompletament vàlid; el segon exemple (entre) viola una de les ondiions, ja que JASC-DSIC-UPV 29
memoria 2010/11/17 19:32 page 30 #40 i i Capítol 1. Intro duió un punt d'alineament marat amb una reu es troba fora del rang de paraules que abasta la seqüènia; i p er últim, el terer exemple (dreta) representa una extraió vàlida, dons inlou la paraula de la terera olumna que no es troba alineada amb ap paraula. Cal remarar que les seqüènies de paraules que s'extrauran p o den tenir una longitud variable, dons p o den abastar des de paraules aïllades ns frases seneres. No obstant, om ja hem esmentat adés, és molt onvenient que la longitud de les seqüèn- ies de paraules extretes siga limitada. D'altra banda, al tenir en ompte que les seqüènies de paraules llargues permeten apturar ma jor informaió de ontext, motiu p el qual aquestes són esp eialment útils en la traduió d'expressions fetes (seria un sistema de TA apaç de traduir orretament l'expressió feta en atalà a burro barra , que signia aleatòriament ?). Ara, al notar que les seqüènies de paraules de ma jor longitud es donen llo amb molt menor freqüènia que les seqüènies més urtes, molt més freqüentment emprades per onstruir les traduions de les frases d'entrada, p erò que presenten l'inonvenient d'ap ortar menys informaió de ontext. La onlusió és que neessitarem tant de segments urts que p o drem apliar en nombroses o asions, om segments llargs que ens p ermetran realitzar traduions molt més preises. Estimaió del mo del L'estimaió d'un model de traduió de seqüènies de paraules invers es realitza, a partir de les seqüènies de paraules extretes de forma heurístia a partir d'un orpus d'entrenament de parells de frases {(fn, en)∈C:n= 1,...N} , de la següent forma [Ko e10℄: p(f|e) = N(f, e) Pf′N(f′, e) (1.29) on N(f, e) és el nombre de vegades que s'ha extret el parell de seqüènies de paraules (f, e) . Reordenament de seqüènies de paraules Com hem vist a l'Equaió 1.27, el mo del de traduió s'ha denit úniament a partir de les probabilitats de traduió de ada seqüènia de paraules en que s'ha segmentat la frase origen. Com hem esmentat al prinipi d'aquesta seió, durant el pro és de traduió la frase origen és segmentada en seqüènies de paraules que p osteriorment són traduïdes i, p ossiblement, reordenades, ja que l'ordre en que apareixen les paraules p ot ser diferent en adasun dels idiomes onsiderats. En general, preferim que les seqüènies de paraules destí no es reordenen (és a dir, que les seqüènies es traduïsquen de forma monòtona, seguint el mateix ordre que les seqüènies de paraules de la frase origen), o b é que anvien la seva p osiió el mínim p ossible, dons salts llargs són infreqüents i, p er tant, p o probables (tot i que això dep èn del parell de llenguatges). Per tant, premiarem la immobilitat de les seqüènies de paraules traduïdes, i p enalitzarem els salts llargs al reordenar-les. 30 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 31 #41 i i 1.3. Aproximaions a la traduió automàtia estadístia En aquest sentit, s'introdueix un mo del de distorsió o reordenament que es deneix om una funió exp onenial d(x) = αx amb un valor apropiat del paràmetre α∈[0,1] , on x és la distània en paraules del salt efetuat p er la seqüènia de paraules al ser reordenada. La distània del salt x es alula de la següent forma: x=| inii k− k−1−1| (1.30) on inii k és la p osiió, resp ete a la frase origen, de la primera paraula de la seqüènia de paraules d'entrada que es tradueix a la k -èsima seqüènia de paraules d'eixida, i k−1 és la p osiió de l'última paraula de la seqüènia de paraules d'entrada que es tradueix a la ( k−1 )-èsima seqüènia de paraules d'eixida (és a dir, la seqüènia d'eixida preedent a la onsiderada). Aleshores, si ombinem aquest mo del amb el mo del de traduió de seqüènies de paraules, obtenim un nou mo del prop orional al presentat a l'Equaió (1.27): p(e|f)∝ K Y k=1 p(ek|fk)d(| inii k− k−1−1|) (1.31) Com veiem, aquest mo del de distorsió és extremadament simple, dons no té en ompte ap informaió sobre les paraules i/o seqüènies de paraules que intervenen en la traduió. Per exemple, p o den haver-hi ertes seqüènies que, al traduir-les a un llenguatge onret, siguen més prop enses a ser reordenades que altres. Un as típi és el que oorre amb els noms i els adjetius, que al traduir de l'anglès al atalà anvien molt freqüentment la seva p osiió. Existeixen altres models de reordenament més omplexos que p ermeten apturar aquesta informaió que estudiarem al següent apítol. Per onloure aquesta seió, remarar que, en el moment en que s'esriuen aquestes línies, els sistemes de TA basats en seqüènies de paraules són els que millors prestaions ofereixen en omparaió amb altres aproximaions, i un dels prinipals ob jetes de la omunitat investigadora [CBKM + 10, Ko e10℄. 1.3.3 Mo dels basats en transdutors Aquesta aproximaió trata de mo delar la relaió entre el llenguatge origen i el llenguatge destí mitjançant autòmates o transdutors d'estats nits esto àstis 20 (TEFS). La araterístia més interessant d'aquesta aproximaió és que els TEFS inlouen de forma implíita un mo del de llenguatge de l'idioma destí. Conseqüentment, es p ot mo delar diretament la probabilitat onjunta de la frase origen f i destí e . Aleshores, baix aquest prinipi, la traduió més probable e ve donada p er la següent expressió: ˆe= argmax e p(f, e) (1.32) 20 Amb probabilitats asso iades a transiions i/o estats. JASC-DSIC-UPV 31
memoria 2010/11/17 19:32 page 38 #48 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules 2.1.1 Mo dels logarítmi-lineals Un mo del logarítmi-lineal 1 (log-lineal, d'ara endavant) és un mo del emprat reentment al món del reoneixement de formes que p ermet onstruir una distribuió de probabilitat integrant diverses distribuions de probabilitat (o mo dels), que en aquest ontext s'anomenem araterístiques o features , tot mitjançant una ombinaió lineal dels logaritmes de les probabilitats en forma exp onenial. Formalment, es deneixen de la següent manera: p(x) = exp N X i=1 λihi(x)!1 Z (2.1) on p(x) és la distribuió de probabilitat a mo delar, N és el nombre de araterístiques a onsiderar en el mo del omplet, hi és la araterístia i -èsima, els λi són els paràmetres del mo del asso iats a la araterístia i -èsima, i Z és el fator de normalitzaió, denit així: Z=X x′ exp N X i=1 λihi(x′)! (2.2) En el as onret de la TA basada en seqüènies de paraules, d'aord amb l'Equaió (1.5) la distribuió de probabilitat que volem mo delar amb un mo del log-lineal és p(e|f) : p(e|f) = exp K X k=1 N X i=1 λihi(f, e, fk, ek)!1 Z(f) (2.3) on K és el nombre de seqüènies de paraules en que es desomposa la frase d'entrada, de forma que ada araterístia hi(f, e, fk, ek) dep èn del k -èsim segment, mentre que Z(f) es deneix de forma a anàloga a l'Equaió (2.2). Si integrem aquest mo del en el riteri de deisió de l'Equaió (1.5), tenim que: ˆe= argmax e"exp K X k=1 N X i=1 λihi(f, e, fk, ek)!1 Z(f)# (2.4) Donat que busquem aquella frase e que maximitze la probabilitat del mo del mitjançant la funió argmax , p o dem simpliar aquesta expressió: en primer llo p o dem presindir de Z(f) , ja que és una onstant respete a e , i p er tant no afeta al riteri de deisió argmax ; i en segon llo, p o dem eliminar la funió exp , dons és una funió monòtona reixent, i p er tant tampo afeta al resultat de la funió argmax , ja que tots els termes sobre els quals es alularia el màxim serien prop orionals a la funió exp . 1 Log-linear model , en anglès. 38 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 39 #49 i i 2.1. El sistema de TA Moses ˆe= argmax e"K X k=1 N X i=1 λihi(f, e, fk, ek)# (2.5) Si instaniem un mo del log-lineal emprant els mo dels vists a la Seió 1.3.2, tenim un total de tres araterístiques, que són: •h1(f, e, fk, ek) : Mo del de traduió de seqüènies de paraules log p(fk|ek) •h2(f, e, fk, ek) : Mo del de distorsió log d(| inii k− k−1−1|) •h3(f, e, fk, ek) : Mo del de llenguatge log p(ek) Integrar tota aquesta informaió en un mo del log-lineal presenta una sèrie d'avantatges: en primer llo , p ermet a justar l'ap ortaió de adasun dels mo dels, amb els paràmetres λi . En segon llo , se'ns p ermet afegir de forma natural nous mo dels que p o den ontribuir a millorar la qualitat de les traduions. Per últim, se'ns dona la p ossibilitat d'entrenar adasun dels mo dels de forma separada, ja que s'assumeix que són indep endents els uns dels altres. A la Seió 2.1.2 desriurem les araterístiques addiionals, no presentades en- ara, que s'inlouen al mo del log-lineal de Moses , i p osteriorment, a la Seió 2.1.3 desriurem el model omplet d'aquest sistema, que integra totes les araterístiques que s'exp osen a aquest do ument. 2.1.2 Extensions del mo del original En aquesta seió desriurem les araterístiques, no presentades enara, que implementa Moses al mo del log-lineal. Mo del de traduió de seqüènies de paraules direte Com hem vist al apítol intro dutori, a l'apliar la regla de Bayes (veure Equaió (1.6)) hem onsiderat un mo del de traduió invers p(f|e) , el qual hem aproximat a la traduió de seqüènies de paraules (veure Equaió (1.27)). Al passar d'un mo del purament generatiu a un mo del log-lineal, s'habilita la p ossibilitat d'inloure el model de traduió direte p(e|f) om una nova araterístia del mo del log-lineal, ja que p o dem trobar asos partiulars en els que disp osar del raonament direte és molt útil. En Moses s'empren ambdues direions del mo del de traduió de seqüènies de paraules, p(f|e) i p(e|f) , que amb un a just adequat dels p esos asso iats s'ha demostrat que onjuntament milloren de forma signiativa les prestaions globals del sistema [Koe10℄. JASC-DSIC-UPV 39
memoria 2010/11/17 19:32 page 40 #50 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules Mo del de suavitzat lèxi A l'entrenar el model de traduió de seqüènies de paraules p o dem trobar-nos amb asos no desitjats relaionats amb el tratament de seqüènies de paraules po freqüents, om és el as en que un parell de seqüènies f i e s'han extret una únia vegada del orpus d'entrenament i a més de forma onurrent, fet que implia una sobreestimaió del mo del, dons p(f|e) = p(e|f) = 1 . En aquest ontext s'intro dueix un mèto de de suavitzat om una araterístia addiional en el mo del log-lineal, anomenat model de suavitzat lèxi 2 , el qual mo dela la probabilitat de traduió, paraula p er paraula, de la seqüènia de paraules f en la seqüènia e a partir d'un alineament a entre les paraules d'amb dós seqüènies. Dit mo del es troba larament inspirat en el mo del 1 d'IBM vist a la Seió 1.3.1. Així, la falta d'informaió que es deriva, en erts asos, en una sobreestimaió del mo del de traduió de seqüènies de paraules, es omp ensa inlo ent un mo del de traduió lèxi, estadístiament més signiatiu i robust. L'estimaió d'aquest mo del ve donada p er la següent equaió [Koe10℄: lex (e|f, a) = I Y i=1 1 |{j|(i, j)∈a}| X ∀(i,j)∈a t(ei|fj) (2.6) on t(ei|fj) és la probabilitat de traduir la paraula fj en ei , i a és un alineament entre les paraules de les seqüènies f i e . Donat que una paraula ei p ot estar alineada amb més d'una paraula de f , la probabilitat de traduió lèxia per a ada ei és normalitzada p el nombre d'alineaments que presenta la paraula ei . El sistema Moses inlou ambdues direions del mo del lèxi: lex (e|f, a) i lex (f| e, a) . Penalitzaió p er paraula Una araterístia del mo del log-lineal de Moses que en o asions dona problemes és el mo del de llenguatge. Com hem vist a la Seió 1.2.3, la ma joria dels sistemes TA inlouen un mo del de llenguatge d' n -grames, om és el as de Moses . El que no hem esmentat a dita seió és que els mo dels de llenguatge basats en n -grames són deients per naturalesa, dons aquests mo delen tant frases orretes om inorretes del llenguatge destí, des d'un punt de vista lingüísti. En altres paraules, po dem veure el mo del de llenguatge om un element que mo dela E∗ (totes les p ossibles ombinaions de paraules del voabulari destí E ), de forma que p ot onferir probabilitats altes a frases sintàtiament no vàlides. A més, els mo dels de llenguatge basats en n -grames són deients p er un altre motiu: en general, assignen ma jor probabilitat a frases urtes que a frases llargues. Això és així p erquè, a ma jor longitud de frase (ma jor nombre de paraules), ma jor nombre d' n -grames a onsiderar, fet que es tradueix en un ma jor nombre de termes de probabilitats multipliant-se, obtenint un valor de probabilitat ada op més baix. En 2 Lexial weighting , en anglès. 40 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 41 #51 i i 2.1. El sistema de TA Moses denitiva, p o dem onsiderar que un mo del de llenguatge basat en n -grames assumeix, p er a qualsevol llenguatge, que les frases urtes són molt més probables que les frases llargues. L'efete negatiu que provo a la deiènia del model de llenguatge, des de la p ersp etiva del pro és de traduió, es tradueix en una tendènia del sistema a deantar-se p er traduions de menor longitud i p ossiblement inorretes des d'un punt de vista lingüísti, en detriment de traduions de ma jor longitud i p ossiblement orretes. En termes de deisió de la traduió més probable, aquesta irumstània s'observa en que la baixa puntuaió atorgada p el mo del de llenguatge a les traduions més llargues i l'alta puntuaió onferida a les traduions més urtes p ot alterar aquesta deisió (veure Equaió (2.5)). Per orregir aquest omportament no desitjat del sistema p o dem onsiderar dues op ions: b é emprar un mo del de llenguatge més omplex (no neessàriament basat en n -grames) que reduïsa o elimine p er omplet la deiènia que presenta el mo del atual, o b é inloure al mo del log-lineal un fator o araterístia que ompense l'efete negatiu del mo del de llenguatge. El sistema Moses implementa la segon op ió, amb la inlusió al mo del log-lineal d'un fator ω anomenat penalitzaió per paraula 3 , el qual b onia les traduions generades de ma jor longitud p er ontrarestar la sobrevaloraió de les traduions de menor longitud. Penalitzaió p er seqüènies de paraules De la mateixa forma que resulta interessant ontrolar la longitud en paraules de la frase senera, també hi és b eneiós afavorir onstruió d'hip òtesis a partir de seqüènies de paraules de ma jor o menor longitud, mitjançant la inlusió d'un fator ρ anomenat penalitzaió per seqüènies de paraules 4 . Açò ve motivat p erquè totes les p ossibles segmentaions de la frase origen són equiprobables, sent la resta de fators (models de traduió, reordenament, llenguatge) els qui determinen, de forma indireta, la millor segmentaió p ossible. Més onretament, la inlusió d'aquest fator ve motivada p erquè l'ús de seqüèn- ies de paraules molt llargues per generar la frase d'eixida provoa, en molts asos, que les seqüènies de paraules emprades per ompletar la traduió siguen de p o a longitud (p ossiblement paraules aïllades) i p er tant de mala qualitat, generant nalment una traduió dolenta, p erò que, no obstant, p ot tenir assignada una probabilitat alta, degut a que les seqüènies de paraules molt llargues solen tenir assoiades probabilitats de traduió molt altes (inlús la màxima probabilitat, 1). Llavors, aquestes traduions es p o den p erlar om serioses andidates a erigir-se om les traduions més probables, fet que no és desitjable. En aquest sentit, la nalitat que es p ersegueix amb la inlusió d'aquest fator és afavorir aquelles segmentaions de la frase d'entrada que originen un ma jor nombre de seqüènies de paraules, i en onseqüènia, que generen seqüènies de paraules de longitud mo derada. Així, p er ada seqüènia de paraules emprada p er onstruir la frase d'eixida, s'afegeix un fator de b oniaió ρ a la puntuaió o probabilitat 3 Word penalty , en anglés. 4 Phrase penalty , en anglès. JASC-DSIC-UPV 41
memoria 2010/11/17 19:32 page 42 #52 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules Figura 2.1: Exemples dels tres tipus d'orientaions que p o den donar-se llo a un mo del de reordenament lexialitzat. asso iada a la traduió. D'aquesta forma, s'atenua l'efete negatiu del model de traduió, que sobrevalora traduions possiblement inorretes generades a partir de l'apliaió de seqüènies de paraules molt llargues (opions de traduió de gran longitud). Mo del de reordenament lexialitzat A la Seió 1.3.2 hem presentat un model de distorsió d(| inii k− k−1−1|) molt senzill que tant sols es troba ondiionat p er la distània del moviment realitzat p er ada seqüènia de paraules de la frase destí al ser reubiat, i p osteriorment hem disutit sobre la onveniènia de ondiionar el mo del a seqüènies de paraules onretes, ja que p o den haver-hi ertes seqüènies més suseptibles a ser reordenades, om havem vist que passa, p er exemple, amb els sintagmes nominals formats p er nom i adjetiu en llenguatges om el atalà o l'espanyol, on amb dues ategories gramatials interanvien les seves posiions al traduir a l'anglès. Aquest és el motiu p el qual Moses inlou un mo del de reordenament addiional que p ermet ap ortar aquest tipus d'informaió, rep el nom de model de reordenament lexialitzat 5 . En termes generals, aquest nou mo del ontempla tres tipus diferents de reordenament d'una seqüènia de paraules resp ete a la seqüènia anterior: monòton (m), interanvi (s) i disontinu (d) 6 , el signiat dels quals es p ot entendre de forma intuïtiva a la Figura 2.1. Més formalment, presentem una distribuió de probabilitat que prediu el tipus d'orientaió més probable que seguirà un parell de seqüènies de paraules f, e : 5 Lexialized reordering model , en anglès. 6 En anglès: monotone (m), swith (s), i disontinous (d). 42 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 43 #53 i i 2.1. El sistema de TA Moses orientaió ∈ {m, s, d} p( orientaió |f, e) (2.7) Aquest mo del s'estima, a partir de les seqüènies de paraules extretes heurístiament del orpus d'entrenament (veure Seió 1.3.2), de la següent forma: en primer llo s'ha de determinar el tipus d'orientaió que segueix ada parell de seqüènies de paraules, p er a p osteriorment obtindre estadístiques que revelen amb quina freqüènia un parell de seqüènies de paraules onret ha seguit un determinat tipus de reordenament, és a dir: p( orientaió |f, e) = N( orientaió , f, e) PoN(o, f, e) (2.8) on N(o, f, e) és el nombre de vegades que s'ha vist al orpus el parell de seqüènies de paraules (f, e) seguint una orientaió o resp ete al parell de seqüènies anterior. En la pràtia, p er evitar la sobreestimaió del mo del, es suavitza el nombre d'o urrènies dels diferents esdeveniments amb la probabilitat a priori de l'orientaió, estimada de forma similar a la probabilitat ondiionada, omptant esdeveniments i normalitzant: p( orientaió ) = PfPeN( orientaió , f, e) PoPfPeN(o, f, e) (2.9) i p er tant, l'estimaió suavitzada del model de l'Equaió, (2.8) amb un valor apropiat del fator σ , es realitza d'aquesta forma: p( orientaió |f, e) = σ p( orientaió ) + N( orientaió , f, e) σ+PoN(o, f, e) (2.10) Existeixen moltes variants d'aquest mo del de reordenament: p er exemple, p o dem onsiderar el tipus de reordenament existent no sols resp ete a la seqüènia de paraules anterior, sinó tamb é resp ete a la seqüènia de paraules p osterior. Per obtindre informaió més detallada sobre aquestes variants i ampliar allò exp osat a aquesta seió, remetem al letor a [Ko e10℄. 2.1.3 El mo del logarítmi-lineal de Moses Com hem vist, a la Seió 2.1.1 s'han intro duït els models log-lineals, instaniant-los p er al as de la TA. Posteriorment, a la Seió 2.1.2 s'han exp osat les araterístiques que formen part del mo del log-lineal de Moses , p erò de forma aïllada. Resta p er tant integrar aquestes araterístiques en el model log-lineal de Moses, que sumen un total de 14, sis de les quals p ertanyen al model de reordenament lexialitzat. • Asso iades al mo del de traduió: JASC-DSIC-UPV 43
memoria 2010/11/17 19:32 page 44 #54 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules Mo del de traduió de seqüènies de paraules direte i invers: p(ek|fk) i p(fk|ek) . Mo del de suavitzat lèxi direte i invers: lex (ek|fk) i lex (fk|ek) . Penalitzaió p er seqüènies de paraules ρ . • Penalitzaió p er paraula ω . • Mo del de distorsió uniforme d(| inii k− k−1−1|) . • Asso iades al mo del de reordenament (onguraió msd-bidiretional-fe ): Mo dels d'orientaió ( m,s,d ) resp ete al parell de seqüènies de paraules anterior: p(m, p |fk, ek) , p(s, p |fk, ek) , i p(d, p |fk, ek) Mo dels d'orientaió ( m,s,d ) resp ete al parell de seqüènies de paraules p osterior: p(m, n |fk, ek) , p(s, n |fk, ek) , i p(d, n |fk, ek) • Mo del de llenguatge p(e) . 2.1.4 Entrenament del mo del En la present seió desriurem el pro és d'entrenament d'un sistema Moses , dividit en 8 etapes. En primer llo al resoldre la dep endènia dels mo dels de Moses amb l'alineament entre paraules de les frases d'entrenament (passos 1, 2 i 3) mitjançant el programari GIZA++ que és una implementaió lliure dels models d'IBM. Una vegada estimats els alineaments, el sistema pot obtindre els mo dels de traduió lèxia (pas 4), de traduió de seqüènies de paraules (passos 5 i 6), i el mo del de reordenament (pas 7). Per últim, es genera un txer que arreplega la onguraió del sistema. 1. Preparar dades p er al GIZA++ to olkit : Es pro essa el orpus paral · lel d'entrenament p er a p o der ser utilitzat amb el programari GIZA++ . 2. Exeutar GIZA++ : Obté els alineaments més probables entre les paraules de ada parell de frases del orpus d'entrenament en ambdues direions de traduió d'aord amb els mo dels d'IBM (veure Seió 1.3.1). 3. Obtindre alineaments bidireionals : S'aplia un mèto de heurísti p er ombinar els alineaments d'amb dós direions de traduió, obtenint els alineaments nals neessaris p er a la extraió de seqüènies de paraules a partir del orpus. 4. Generar taula de traduió lèxia : S'estimen, a partir dels alineaments de paraules obtinguts als pas 3, els mo dels de traduió lèxia lex(f|e) i lex(e|f) (veure Seió 2.1.2). 5. Extraure seqüènies de paraules : S'obtenen tots els parells de seqüènies de paraules onsistents amb els alineaments de paraules (veure Seió 1.3.2) obtinguts al nal del pas 3, els quals es desen a un txer omprimit anomenat 44 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 45 #55 i i 2.1. El sistema de TA Moses extrat.gz . Aquest txer presenta, línia a línia, tots els parells de seqüènies de paraules extrets del orpus d'entrenament. Les línies d'aquest txer tenen un asp ete similar a aquest: resumption ||| reanudaión ||| 0-0 resumption of the ||| reanudaión del ||| 0-0 1-1 2-1 resumption of the session ||| reanudaión del p erío do de sesiones ||| 1-1 2-1 3-2 3-4 of the ||| del ||| 0-0 1-0 of the session ||| del p erío do de sesiones ||| 0-0 1-0 2-1 2-3 session ||| p erío do de sesiones ||| 0-0 0-2 Les seqüènies de paraules apareixen delimitades p el símbol |||, de forma que la primera seqüènia de paraules representa a la seqüènia en el llenguatge origen f , mentre que la segona seqüènia de paraules representa a la seqüènia en el llenguatge destí e . Per últim, l'últim amp delimitat p er ||| mostra els alineaments existents entre les paraules que onformen amb dues seqüènies. 6. Generar taula de seqüènies de paraules : A partir del txer extrat.gz es genera la taula de seqüènies de paraules 7 , que és la implementaió físia de les araterístiques del mo del log-lineal asso iades al mo del de traduió de Moses (veure Seió 2.1.3). En aquesta taula apareixen tots els parells de seqüènies de paraules observats al txer extrat.gz sense rep etiions, aompanyats de les probabilitats asso iades a les araterístiques del mo del de traduió, per al as partiular del parell de seqüènies de paraules onsiderat. Les línies d'aquesta taula presenten un asp ete om aquest: a gradual resumption of ||| una reanudaión paulatina de ||| 1 0.0407673 1 0.011889 2.718 a gradual resumption ||| una reanudaión paulatina ||| 1 0.123856 1 0.0183073 2.718 a legal presumption of ||| una presunión judiial de ||| 1 0.0173598 1 0.00322516 2.718 a legal presumption ||| una presunión judiial ||| 1 0.0527413 1 0.00496625 2.718 a presumption against ||| una presunión en ontra de ||| 1 0.0811048 0.5 0.00329944 2.718 a presumption against ||| una presunión en ontra ||| 1 0.0811048 0.5 0.0152981 2.718 Po dem observar tres amps delimitats pel separador |||. En primer llo , trob em la seqüènia de paraules en el llenguatge origen f , en segon llo , la seqüènia de paraules en el llenguatge destí e , i en terer i darrer llo , les probabilitats, separades p er espais en blan, de les araterístiques assoiades al model de traduió. En l'exemple trob em, d'esquerra a dreta, p(f|e) , lex(f|e) , p(e|f) , lex(e|f) i ρ , que en el nostre as sempre és exp(1) = 2.718 . 7. Construir mo del de reordenament : Es genera un txer omprimit que onté la informaió relaionada amb el mo del de reordenament estimat d'aord amb la onguraió elegida (veure Seió 2.1.2). En el nostre as emprarem la onguraió p er defete ( msd-bidiretional-fe ). 7 Phrase Table , en anglès. JASC-DSIC-UPV 45
memoria 2010/11/17 19:32 page 46 #56 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules 8. Crear arxiu de onguraió : Per nalitzar el pro és d'entrenament del sistema, es rea un txer de onguraió que arreplega tota la informaió neessària p er fer funionar el sistema: p esos asso iats a les araterístiques del mo del log-lineal, rutes on es trob en la taula de seqüènies de paraules, el mo del de reordenament, et. D'aquest pro és al tenir en ompte dos asp etes imp ortants: en primer llo , els p esos assignats a les araterístiques del mo del log-lineal després d'entrenar el mo del prenen uns valors predenits (típiament 0.1 ó 0.2 p er a la ma joria de araterístiques), els quals s'han d'a justar p er balanejar les ap ortaions de adasuna d'aquestes araterístiques al model global, en termes de millorar les prestaions - nals del sistema, tot d'aord amb les araterístiques del orpus (aquest pro ediment és expliat breument a la Seió 2.1.7). En segon llo , al onstruir un mo del de llenguatge amb alguna ferramenta externa, om p er exemple la ferramenta SRILM [Sto02℄, la qual p ermet onstruir un mo del d' n -grames a partir de la part monolingüe del orpus paral · lel emprat p er entrenar el sistema, si b é p o dria emprar-se un orpus monolingüe indep endent. 2.1.5 Pro és de traduió La tasa de traduió o deso diaió és el pro és en el que el sistema genera un gran nombre de p ossibles traduions de la frase d'entrada, elegint aquella que maximitza la probabilitat o puntuaió onferida p el mo del log-lineal: ˆe= argmax e"K X k=1 N X i=1 λihi(f, e, fk, ek)# (2.11) instaniat amb les araterístiques exp osades a la Seió 2.1.3. No obstant, aquesta tasa és molt omplexa, tant que existeix un nombre exponenial de p ossibles traduions resp ete a la longitud de la frase d'entrada. De fet s'ha demostrat que el problema de la era de la traduió més probable és NP-Complet [Kni99a℄, amb la qual osa, l'exploraió de tot l'espai de era en busa de la traduió més probable és una tasa tant ostosa om imp ossible. El pro és de traduió onsisteix en segmentar de totes les formes p ossibles la frase d'entrada, p er a p osteriorment traduir de diferents formes ada seqüènia de paraules denida per la segmentaió de la frase d'entrada, i p er últim es genera la frase d'eixida de forma monòtona (d'esquerra a dreta i de forma inremental), reordenant de tota forma p ossible les seqüènies de paraules traduïdes (un as onret de traduió l'havem vist a la Figura 1.8). Com veiem, existeix un gran nombre d'alternatives (segmentaió, traduió i reordenament) a onsiderar, o el que és el mateix, un gran espai de era, fet que demostra larament la omplexitat de trobar la traduió més probable. L'espai de era és denit p er estats o hip òtesis que, entre altres oses, determinen el nombre de paraules de la frase origen que han estat obertes (traduïdes) i l'última 46 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 47 #57 i i 2.1. El sistema de TA Moses seqüènia de paraules de la frase destí generada. Durant el proés de era aquestes hip òtesis són expandides amb l'ús de noves op ions de traduió (traduió de seqüènies de paraules de la frase d'entrada que englob en paraules no ob ertes) per donar llo a noves hip òtesis que abasten (tradueixen) paraules de la frase origen no ob ertes anteriorment. Una hip òtesi que obreix totes les paraules de la frase origen és un estat soluió, i la traduió asso iada a tal estat s'obté reorrent el amí que parteix des de la hip òtesi iniial (ap paraula ob erta) ns la hip òtesi soluió. El pro és de era de la traduió més probable es realitza mitjançant un algorisme de era heurísti A*. Els algorismes heurístis utilitzen una funió de puntuaió f(n) , que serveix per valorar el prometedor que és un estat o hip òtesi n , i que es deneix om el ost per arribar des de l'estat iniial ns l'estat n , denotat p er g(n) , més una estimaió heurístia del ost restant p er trobar la soluió (traduió) òptima, denotada p er h(n) . És a dir, de forma matemàtia: f(n) = g(n) + h(n) . Cal notar que, en aquest ontext, a menor ost, ma jor probabilitat asso iada a la p ossible traduió, i vieversa. L'algorisme heurísti emprat al sistema Moses presenta les següents araterístiques: • No Complet : L'algorisme no pot garantir trobar la traduió d'una frase d'entrada enara que el mo del siga apaç de proveir-la, ja que durant el pro és de era s'apliquen tèniques de p o da (expliades a ontinuaió) que p o den eliminar els estats que ondueixen a alguna soluió fatible (traduió ompleta). • Admissible : La funió d'estimaió del ost restant p er arribar a la traduió òptima no sobreestima el ost restant real per arribar a la mateixa, de forma que es ompleix que: F(n)≥g(n) + h(n)∀n F(n) = g(n) + h(n)n∈S on F(n) representa el ost real d'arribar a l'estat o hip òtesi n , i S representa al onjunt traduions ompletes (estats soluió) de la frase d'entrada. • Estratègia de era p er amplària : S'expandeixen totes les hip òtesis de nivell i abans d'expandir hip òtesis de nivell i+1 . El nivell i -èsim engloba totes aquelles hip òtesis generades després d'apliar i op ions de traduió. Per tal d'aotar l'espai de era i, en onseqüènia, reduir la omplexitat omputaional del pro és de traduió, s'empren les següents tèniques: • Reombinaió d'hip òtesis : Les hip òtesis semblants, que són aquelles obreixen les mateixes paraules de la frase d'entrada, són reombinades, onservant úniament aquella que presenta menor funió de ost g(n) . JASC-DSIC-UPV 47
memoria 2010/11/17 19:32 page 54 #64 i i Capítol 2. Traduió automàtia estadístia basada en seqüènies de paraules mt (o |ek| ), ja que és redundant si es oneix y(t) (o ek ). Aquesta variant del mo del és la que al Capítol 3 presentarem om el mo del de longitud esp eialitzat. De la mateixa forma que al mo del de longitud estàndard, p o dem obtindre una variant del mo del esp eialitzat onsiderant que la probabilitat de la segmentaió de la frase origen p(f|e, J) és uniforme, de forma que el mo del quedaria reesrit de la següent forma: p(f|e, J) := Y k p(|fk|/ ek)p(fk|ek) (2.28) En denitiva, tant l'Equaió (2.23) om l'Equaió (2.27) ens mostren om modelar la longitud dels segments juntament amb un mo del de traduió invers de seqüènies de paraules. Al Capítol 3 veurem om implementar i integrar aquests mo dels al sistema Moses . 54 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 55 #65 i i Capítol 3 Models de Longitud En el apítol anterior hem presentat els sistemes log-lineals, els quals ens brinden la p ossibilitat d'afegir fonts d'informaió addiionals al proés de traduió. En aquest ontext, a la Seió 2.2 hem disutit la p ossibilitat d'inloure informaió sobre la longitud de les seqüènies de paraules al mo del, donades les b ones p ersp etives que es desprenen del treball menionat. Aquesta p ossibilitat es onverteix en realitat en aquest Capítol, on prop osarem la inlusió del mo delat de les longituds de les seqüènies de paraules al mo del de traduió de Moses . 3.1 Mo del de longitud estàndard El primer dels dos mo dels de longitud que hem onsiderat a aquest treball és aquell que mo dela les relaions existents entre les longituds de les seqüènies de paraules d'entrada i d'eixida a partir d'un orpus d'entrenament. D'aord amb l'Equaió (2.23), el mo del de traduió invers p(f|e) ve donat p er tres termes (que en realitat p o dríem onsiderar-ne úniament dos, donat que p(|e|)p(|f|/|e|) = p(|f|,|e|) ): • Un mo del de traduió de seqüènies de paraules p(f|e) (veure Seió 1.3.2). • Un mo del de longitud inondiional p(|e|) , que representa la probabilitat de trobar una seqüènia de paraules del llenguatge destí de longitud |e| . Aquest mo del és apaç de resp ondre a preguntes om la següent: quina és la probabilitat d'observar una seqüènia de 5 paraules de longitud en anglès? • Un mo del de longitud ondiional p(|f|/|e|) , que representa la probabilitat de traduir una seqüènia de paraules del llenguatge destí de longitud |e| en una seqüènia de paraules del llenguatge origen de longitud |f| . Aquest mo del p o dria resp ondre, p er exemple, la següent pregunta: quina és la probabilitat de traduir una seqüènia (qualsevol) de 6 paraules de longitud en anglès, en una seqüènia (qualsevol) de 4 paraules de longitud en atalà? 55
memoria 2010/11/17 19:32 page 56 #66 i i Capítol 3. Mo dels de Longitud Cal notar que, si invertim la direió de la traduió, obtindrem mo dels de longitud anàlegs: p(|f|) i p(|e|/|f|) , en addiió al mo del de traduió de seqüènies de paraules invers p(e|f) . 3.1.1 Estimaió del mo del i implementaió El mo del de traduió de seqüènies de paraules s'estima onforme a l'esmentat a la Seió 1.3.2, mentre que que els mo dels relaionats amb la longitud s'estimen p er màxima versemblança resp ete a un onjunt de seqüènies de paraules (f, e) extretes d'un orpus d'entrenament de parells de frases {(fn, en)∈C:n= 1,...N} . D'una banda, el model de longitud inondiional s'estima de la següent forma: p(|e|) = N(|e|) N (3.1) on N(|e|) és el nombre de vegades que s'han observat seqüènies de paraules de longitud |e| en el llenguatge d'eixida, i N és el nombre total de seqüènies de paraules observades. No obstant, p er evitar una sobreestimaió del mo del es realitza un suavitzat mitjançant la interp olaió lineal entre el mo del de longitud i la distribuió uniforme de la longitud, amb un valor adequat d' ǫ : pǫ(|e|) = (1 −ǫ)N(|e|) N+ǫ1 L (3.2) on L és la longitud màxima que p o den assolir les seqüènies de paraules (reordar que la longitud està aotada per termes d'eiènia, veure Seió 1.3.2). L'estimaió de p(|f|) es realitza de forma similar. D'altra banda, l'estimaió del mo del de longitud ondiional s'efetua om segueix: p(|f|/|e|) = N(|f|,|e|) N(|e|) (3.3) on N(|f|,|e|) és el nombre de vegades que s'han observat de forma onjunta seqüènies de paraules de longitud |e| en el llenguatge d'eixida i seqüènies de paraules de longitud |f| en el llenguatge d'entrada. L'estimaió de p(|e|/|f|) tamb é es realitza de forma similar. De nou, aquesta distribuió de probabilitat és suavitzada p er evitar la seva sobreestimaió: pǫ(|f|/|e|) = (1 −ǫ)N(|f|,|e|) N(|e|)+ǫ1 L (3.4) Fins al moment hem vist om estimar aquests models, p erò no d'on extraure la informaió neessària p er estimar-los. El pro és desrit no és més que una simpliaió del 56 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 57 #67 i i 3.1. Mo del de longitud estàndard pro és d'estimaió dels mo dels de longitud, dons resulta omplex estimar-lo diretament p er màxima versemblança a partir del orpus d'entrenament (s'hauria d'apliar un entrenament basat en l'algorisme Expetation-Maximization [DLR77℄, ja que no disp osem de les segmentaions de les frases). En el ontext de Moses , trob em dues maneres d'obtindre seqüènies de paraules a partir del orpus d'entrenament: d'una banda, a partir de les seqüènies de paraules extretes de forma onsistent respete a un heurísti d'alineaments de paraules (veure Seió 1.3.2), i d'altra banda, a partir de les segmentaions de Viterbi proveïdes p el sistema en un pro és de traduió restringit (dirigit) a obtindre la traduió orreta. Amb dues alternatives es basen en l'ús de tèniques heurístiques, tal i om hem vist a les Seions 1.3.2 i 2.1.5 resp etivament, amb la qual osa l'estimaió dels models no serà estritament orreta. Anem a detallar adasuna de les vies prop osades. Estimaió a partir de seqüènies de paraules extretes en la fase d'entrenament Com ja sab em, el sistema Moses , en llo d'obtindre les seqüènies de paraules a partir de les segmentaions més probables estimades p er màxima versemblança a partir del orpus d'entrenament, aplia un algorisme que extrau, p er a ada parell de frases del orpus, totes les seqüènies de paraules onsistents amb un heurísti dels alineaments entre paraules estimats prèviament mitjançant una implementaió dels mo dels d'IBM. Això es tradueix en que, p er ada parell de frases del orpus, existeixen moltes segmentaions p ossibles que donen llo a múltiples parells de seqüènies de paraules, la ma joria de les quals no tenen p er què expliar la forma més idònia de traduir la frase origen en la frase destí, p erò tot i això, formen part dels paràmetres del mo del de traduió de seqüènies de paraules, i p er extensió, multipliquen el nombre d'esdeveniments a observar en la estimaió del mo del de longitud. A p esar de la inorreió que presenta aquesta tènia des d'un punt de vista teòri, la primera de les dues fonts d'informaió que onsiderarem p er estimar els nostres mo dels és aquest onjunt de seqüènies de paraules extretes de forma heurístia. Com hem vist a la Seió 2.1.4, els parells de seqüènies de paraules extretes amb aquest heurísti es desen, línia p er línia, al txer extrat.gz . Cal dons pro essar ada línia d'aquest txer, alular la longitud de les seqüènies de paraules i inrementar els omptes dels esdeveniments observats. Una vegada s'ha pro essat tot el txer, es normalitzen els omptes i es suavitzen les distribuions de probabilitat resultants onforme a les Equaions (3.2) i (3.4). Estimaió a partir de les segmentaions de Viterbi Com ja s'ha esmentat adés, la forma més natural i estadístiament orreta d'estimar els mo dels que aí prop osem és l'entrenament p er màxima versemblança a partir del orpus d'entrenament de parells de frases. Mitjançant aquest mèto de onsiderem que el nostre model és un mo del paramètri, els paràmetres del qual són denotats per θ i estimats a partir de les dades del orpus apliant una funió de versemblança L , que en el nostre as es deneix així: JASC-DSIC-UPV 57
memoria 2010/11/17 19:32 page 58 #68 i i Capítol 3. Mo dels de Longitud L(θ) = N Y n=1 pθ(fn|en, Jn) (3.5) on pθ és el mo del de traduió paramètri i N és el nombre de mostres del orpus. Ja que el nostre riteri és maximitzar la versemblança resp ete el orpus d'entrenament, neessitem trobar els paràmetres òptims ˆ θ que maximitzen aquest riteri: ˆ θ= argmax θ L(θ) (3.6) En aquesta literatura és habitual emprar la funió log-versemblança, atès que la funió log és monòtona reixent i no afeta al òmput de la funió argmax . Aleshores, tenim que: ˆ θ= argmax θ (log L(θ)) = argmax θ N X n=1 log pθ(fn|en, Jn)! (3.7) Ara b é, en realitat el nostre mo del de traduió paramètri pθ(f|e, J) és inomplet: no explia la forma de segmentar les frases d'eixida i d'entrada, om tamp o la forma de reordenar els segments de la frase d'eixida p er generar, de forma monòtona, la frase d'entrada (reordem que estem mo delant el mo del de traduió invers). Per tant, el mo del requereix tres variables addiionals: l i m , que denoten resp etivament la segmentaió de les frases f i e en seqüènies de paraules, i r , que representa un reordenament de les seqüènies de paraules de la frase d'eixida e expliades p er m . Aquestes variables són o ultes al nostre mo del, dons el orpus d'entrenament no es troba etiquetat amb tal informaió, i p er tant neessitem estimar aquesta informaió p er p o der p osteriorment estimar el mo del. Llavors, si destap em les variables o ultes del mo del de traduió, tenim que: ˆ θ= argmax θ N X n=1 log X lX mX r pθ(fn, l, m, r |en, Jn)!! (3.8) Així, no és p ossible estimar el mo del apliant una maximitzaió del riteri de la logversemblança, dons no tenim informaió sobre les variables o ultes l , m i r . Hauríem de reórrer a l'apliaió d'un entrenament Expetation-Maximization [DLR77℄, ja que sols aquesta tènia ens p ermet estimar el nostre mo del amb variables o ultes p er màxima versemblança. No obstant, aquest tipus d'estimaió és molt ostosa, així que optarem p er realitzar una aproximaió heurístia d'aquest pro és. La idea és que la traduió més probable d'una frase, d'aord amb el mo del log-lineal de Moses , és aquella que explia la forma més òptima de segmentar i reordenar la frase d'eixida p er generar de forma monòtona les seqüènies de paraules que onformen la frase d'entrada. En altres paraules, la traduió més probable f d'una frase d'eixida e prop oriona una aproximaió heurístia dels valors òptims de les variables o ultes del nostre mo del: 58 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 59 #69 i i 3.1. Mo del de longitud estàndard ˆ l, ˆm, ˆr= argmax l,m,r p(f, l, m, r |e, J) (3.9) Les segmentaions denides p er ˆ l i ˆm són aquelles que expliquen la generaió de la traduió més probable segons el mo del log-lineal de Moses , i reb en el nom de segmentaions de Viterbi. Per tant, p o dem aonseguir extraure parells de seqüènies de paraules del orpus d'entrenament d'una forma més preisa emprant el deso di- ador de Moses : al prop orionar-li tant el onjunt de frases d'entrenament p er a ser traduïdes om les seves respetives referènies, orientant el pro és de deso diaió a la produió de les referènies prop orionades. La generaió p er part del deso di- ador de la traduió de referènia (la millor traduió p ossible) p ermet obtindre les segmentaions de les frases d'eixida i d'entrada i les relaions o asso iaions entre les seqüènies de paraules resultants, que és preisament una aproximaió a la informaió que prop orionen les variables o ultes del mo del l , m i r , resp etivament. Cal reordar que el proés de traduió es basa en una tènia de era heurístia que trata de trobar més probable segons el mo del log-lineal (veure Seió 2.1.5). Aleshores, p er p o der realitzar aquest pro és es requereix un sistema base Moses entrenat i optimitzat. En primer llo , al entrenar el sistema amb un onjunt d'entrenament (veure Seió 2.1.4). Posteriorment, és aonsellable a justar els p esos de les araterístiques del mo del log-lineal amb un onjunt de validaió (veure Seió 2.1.7), deixant així el sistema enllestit p er ab ordar el següent pas, que és traduir el onjunt d'entrenament, obligant al deso diador a obtindre les traduions de referènia, de forma que el sistema prop orionarà les segmentaions de les frases d'entrada i d'eixida que millor expliquen el pro és de traduió d'aord amb els paràmetres del mo del. Llavors, a partir d'aquesta informaió es p o den estimar els mo dels de longitud onforme a les Equaions (3.2) i (3.4). Un exemple d'eixida proveïda p el deso diador, al traduir de l'anglès a l'espanyol el orpus Europarl-v3 (veure Seió 4.1), és la següent: aprobaión |0-0| del |1-2| ata |3-3| Aquesta eixida india, p er exemple, que la seqüènia de paraules del es troba alineada amb la seqüènia de paraules determinada p el rang de posiions de paraules en la frase origen 1-2 (les paraules en les p osiions 1 i 2), que onsultant la referènia és of the . En realitat no ens preoupa sab er quina és la seqüènia de paraules rela- ionada amb la seqüènia origen, sinó la seva longitud, que en el as de l'exemple es p ot alular de forma trivial: (2 −1) + 1 = 2 . Hem implementat un programa que p ermet pro essar aquesta eixida de forma adient p er obtindre la informaió neessària p er estimar els mo dels d'una forma similar a la realitzada a partir del txer extrat.gz . Cal destaar un asp ete imp ortant relaionat amb el pro és de traduió guiat p er les referènies: el sistema no sempre serà apaç de generar om a traduió més probable la referènia proporionada, i en aquests asos, el deso diador no mostrarà JASC-DSIC-UPV 59
memoria 2010/11/17 19:32 page 60 #70 i i Capítol 3. Mo dels de Longitud el parlamento ha intervenido y , muy apropiadamente parliament has stepped in and , correctly , pointed , así lo ha puesto de relieve . this out . Figura 3.1: Exemple d'alineament entre paraules d'un parell de frases, extret del orpus Europarl-v3 p er al parell de llenguatges anglès - espanyol (veure Seió 4.1). Aquest alineament requereix, en el pro és de traduió, l'extraió d'una seqüènia d'11 paraules de longitud om a mínim (denotada per la franja grisa), segons l'algorisme d'extraió de seqüènies de paraules de Moses . ap eixida: simplement ignorarà la frase pro essada. Això p ot o órrer prinipalment p er dos motius: b é p el problema derivat de la inompletitud de l'algorisme heurísti de era de la traduió més probable (generalment motivat p el límit de distorsió en la era, veure Seió 2.1.5), o b é degut a que p o den haver-hi seqüènies de paraules que no es p o den extraure de forma onsistent de ap de les maneres resp ete a l'alineament entre paraules prop orionat, generalment a ausa de que la longitud màxima a la que estan limitades les seqüènies de paraules imp edeix abastar una seqüènia de paraules de suient longitud que resp ete la propietat de onsistènia amb els alineaments. És p er això que aquest efete negatiu és inversament prop orional a la longitud màxima de les seqüènies de paraules: a menor longitud màxima, ma jor és el nombre de frases que no es p o den traduir forçadament en les seves referènies, i vieversa. A la gura 3.1 p o dem observar un exemple d'alineament 1 entre paraules d'un parell de frases extret del orpus Europarl-v3 p er al parell de llenguatges anglès - espanyol (veure Seió 4.1). Si ens xem, aquest alineament no p ermetria obtindre una segmentaió vàlida d'amb dós frases si onsiderarem seqüènies de paraules amb una longitud màxima limitada, p er exemple, a 7 paraules, dons es requereix l'extraió d'un parell de seqüènies de paraules (denotat per la franja grisa) format p er una seqüènia en espanyol d'almenys 11 paraules de longitud i una seqüènia en anglès d'almenys 8 paraules de longitud. Llavors, en aquest as el deso diador de Moses 1 Cal reordar que aquests alineaments són estadístis, és dir, no s'estableixen a partir de oneixements lingüístis. 60 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 61 #71 i i 3.1. Mo del de longitud estàndard no seria apaç d'obtindre la traduió de referènia si el mo del s'entrena limitant la longitud màxima de les seqüènies de paraules a menys d'11 paraules. En denitiva, aquesta forma d'obtindre la informaió neessària per estimar els mo dels presenta un gran avantatge i un gran inonvenient. D'una banda, onsiderar sols les seqüènies de paraules que millor expliquen les traduions orretes (referènies), o en altres paraules, les segmentaions més probables, implia augmentar la preisió del mo del de longitud. Però d'altra banda, el fet que el deso diador no puga, en ertes o asions, obtindre om a traduió més probable la referènia prop or- ionada, a part que és un mostra de la deiènia del model de traduió de Moses (veure Seió 1.2.4), això provo a que el nombre d'events disp onibles p er estimar els mo dels disminuïsa rítiament, amb la qual osa el sistema serà menys onable i robust. No obstant, en el as del mo del de longitud estàndard, al onsiderar úniament esdeveniments de tipus longitud de seqüènies de paraules, l'impate negatiu no és tant signiatiu om en el as del mo del de longitud esp eialitzat, om omprovarem més endavant. 3.1.2 Integraió en Moses La inlusió d'aquests mo dels al sistema es realitza mo diant el mo del log-lineal de Moses (veure Seió 2.1.3). Es onsideren tres variants del sistema original: • Moses-LConjunta : Substitueix les araterístiques de traduió de seqüènies de paraules direta i inversa p els mo dels de traduió direte i invers prop osats a l'Equaió (2.23). • Moses-LCondiional : Aquest sistema és similar a l'anterior, p erò implementa la variant del model de longitud estàndard presentada a l'Equaió (2.25) (no es mo dela la probabilitat de longitud inondiional). Aquest nou sistema permetrà onferir ma jor expressivitat al model de longitud ondiional, de forma que, si la informaió que ap orta és realment útil, aleshores ma jor efete benigne tindrà sobre el pro és de traduió, dons onsiderar el mo del onjunt implia que els mo dels de traduió de seqüènies de paraules direte i invers ap orten la mateixa funió de probabilitat de longitud: p(|e|)p(|f|/|e|) = p(|f|)p(|e|/|f|) = p(|f|,|e|) . • Moses + LCondiional : Aquest sistema inlou les araterístiques del sistema base Moses sense mo diar, més dues araterístiques addiionals: les probabilitats ondiionades de les longituds en amb dues direions de la traduió, és a dir, els mo dels p(|f|/|e|) i p(|e|/|f|) . Aquest sistema ens p ermetrà avaluar d'una forma més transparent l'aportaió real del model de longitud al pro és de traduió, donat que es trata d'una araterístia (en realitat dues) addiional i indep endent. A més, al destaar que amb aquest sistema ens evitem p ertorbar el mo del de traduió de seqüènies de paraules de Moses . Com ja havem vist a la Seió 2.1.4, les araterístiques que formen part del mo del de traduió de seqüènies de paraules s'integren a la taula de seqüènies de paraules, JASC-DSIC-UPV 61
memoria 2010/11/17 19:32 page 62 #72 i i Capítol 3. Mo dels de Longitud en l'apartat de puntuaions. Hem desenvolupat una ferramenta que proessa íntegrament aquesta taula, de forma que, p er a ada parell de seqüènies de paraules f i e es alulen les seves resp etives longituds | f |i| e | i es mo diquen les probabilitats de les araterístiques en funió del parell de seqüènies de paraules onsiderat i del sistema que s'està onstruint ( Moses-LConjunta, Moses-LCondiional, Moses + LCondiional ). Per exemple, al onstruir el sistema Moses-LCondiional , p er a tot parell de seqüènies de paraules es mo diaran les puntuaions p(f|e) i p(e|f) p er p(|f|/|e|)p(f|e) i p(|e|/|f|)p(e|f) ) resp etivament. Al Capítol 4 s'analitzaran les prestaions d'aquests tres sistemes en omparaió amb el sistema Moses onvenional. 3.2 Mo del de longitud esp eialitzat L'altre model de longitud que proposem a aquest apítol, originat om una variant del primer, és el que anomenem mo del de longitud esp eialitzat. Resp ete al mo del de longitud estàndard, i d'aord amb la deniió formal del mo del esp eialitzat (veure Equaió (2.27)), l'úni terme que anvia és el model de longitud ondiional, que en aquest as és ondiionat a una seqüènia de paraules: aquest mo del l'anomenarem mo del de longitud ondiionat a seqüènies de paraules p(|f|/ e) , que representa la probabilitat de traduir una seqüènia de paraules e onreta del llenguatge destí en una seqüènia de paraules del llenguatge origen de longitud |f| . Aquest mo del p ermet resp ondre a preguntes om aquesta: quina és la probabilitat de traduir la seqüènia de paraules en anglès La meva mare és universitària en una seqüènia (qualsevol) de 2 paraules de longitud en atalà? Es p ot omprovar om la naturalesa d'aquest mo del és la que motiva la nomen- latura del mateix (mo del de longitud esp eialitzat), dons ap orta informaió sobre la longitud dels segments en que es p ot traduir ada seqüènia de paraules onreta. Si invertim la direió de la traduió, obtindrem mo dels de longitud anàlegs: p(|f|) i p(|e|/ f) , en addiió al model de traduió de seqüènies de paraules direte p(e|f) . 3.2.1 Estimaió del mo del i implementaió L'estimaió d'aquests models es realitza, a l'igual que els mo dels de longitud estàndard, p er màxima versemblança resp ete a un onjunt de seqüènies de paraules (f, e) extretes d'un orpus d'entrenament de parells de frases {(fn, en)∈C:n= 1,...N} i onsistents amb uns alineaments entre paraules p er a ada parell de frases. D'una banda, el mo del de longitud inondiional s'estima tal i om s'india a l'Equaió (3.2). D'altra banda, l'estimaió del mo del de longitud ondiionat a seqüènies de paraules es realitza de forma similar al mo del de longitud ondiionat del mo del estàndard: p(|f|/ e) = N(|f|, e) N(e) (3.10) 62 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 63 #73 i i 3.2. Mo del de longitud esp eialitzat vesprada bona Àngel Raül nit Rubén hola Víctor Adrià els meus companys Figura 3.2: Exemple d'una estrutura de dades trie. on N(|f|, e) és el nombre de vegades que s'han observat onjuntament seqüènies de paraules de longitud |f| en el llenguatge d'entrada i la seqüènia de paraules e en el llenguatge d'eixida. Novament suavitzarem aquest mo del p er evitar problemes de sobreestimaió, mitjançant una interpolaió lineal amb el mo del de longitud ondiional estàndard amb un valor d' ǫ adequat: pǫ(|f|/ e) = (1 −ǫ)N(|f|, e) N(e)+ǫN(|f|,|e|) N(|e|) (3.11) Cal notar que l'estimaió de p(|e|/ f) es realitza de forma similar. Ara b é, estimar el mo del ondiional presenta una omplexitat afegida, dons p er a la part dreta del mo del (la ondiió) no onsiderem longituds de segments (valors enters), sinó seqüènies de paraules (adenes de text de longitud variable). L'esp eialitzaió del mo del de longitud implia una ma jor omplexitat de l'algorisme d'estimaió, p erò sobretot, de l'estrutura de dades enarregada d'emmagatzemar, p er a totes les seqüènies de paraules e , els omptadors N(|f|, e) , neessaris p er p o der estimar dit mo del (veure Equaió (3.11)). Per p o der satisfer aquest requeriment de la forma més eient p ossible, s'ha implementat una estrutura de dades anomenada trie , una estrutura en forma d'arbre molt apropiada p er emmagatzemar grans quantitats de dades que presenten la propietat de prex entre elles, om és el as partiular de les seqüènies de paraules (reordar la forma en que s'extrauen, veure Seió 1.3.2). Emprar una estrutura jeràrquia d'aquest tipus en llo de ap altra estrutura de dades p ermet reduir la omplexitat espaial del model, ja no s'emmagatzemen prexos rep etits, i p er extensió, també redueix la omplexitat temp oral de les op eraions elementals a realitzar sobre l'arbre, ja que existiran menys elements a pro essar. Po dem observar un exemple d'un trie a la Figura 3.2. En una estrutura de dades trie adaptada i implementada onforme a les nostres neessitats, ada no de representa una únia adena de text (una paraula, signe de puntuaió, et.). L'arbre de prexos JASC-DSIC-UPV 63
memoria 2010/11/17 19:32 page 70 #80 i i Capítol 3. Mo dels de Longitud Estimaió a partir de les segmentaions de Viterbi Una altra font d'informaió més preisa p erò menys robusta són les segmentaions de Viterbi proveïdes p el sistema al traduir el onjunt d'entrenament de forma guiada p er les referènies de traduió. L'estimaió es realitza de forma molt similar a la vista en el as del mo del de longitud estàndard, p erò al tenir en ompte una sèrie de onsideraions partiulars de l'estrutura de dades trie . Com ja sab em, el prinipal inonvenient que presenta aquesta font d'informaió és que el nombre d'esdeveniments a observar es redueix de forma onsiderable resp ete a l'altra font d'informaió onsiderada (seqüènies de paraules extretes durant l'entrenament del sistema), fet que p ot provo ar no sols problemes de sobreestimaió dels mo dels (atenuats gràies a l'apliaió de tèniques de suavitzat), sinó tamb é problemes relaionats amb la no observaió de seqüènies de paraules que sí s'han observat en l'entrenament del sistema p er mitjà de l'heurísti d'extraió de seqüènies de paraules, i que per tant formen part dels paràmetres del model de traduió de seqüènies de paraules de Moses (de la mateixa forma que apareixen al txer extrat.gz o a la taula de seqüènies de paraules). Aleshores el problema real el trobarem al tratar d'integrar aquests mo dels al sistema Moses , dons això requereix pro essar la taula de seqüènies de paraules (txer phrase-table.gz ), en la que p o den aparèixer seqüènies de paraules que no s'han observat en la onstruió del mo del de longitud esp eialitzat. Teoria en mà, en aquests asos la probabilitat asso iada al mo del de longitud esp eialitzat deuria ser nul · la, p erò om que això no és ert (realment és degut a una estimaió p o robusta del mo del), i donat que la distribuió de probabilitat ondiionada és suavitzada amb la probabilitat del mo del de longitud estàndard ondiional (veure Equaió (3.4)), en la pràtia s'assigna íntegrament la informaió ap ortada p el mo del de longitud estàndard ondiional, molt millor estimat. 3.2.2 Integraió A l'igual que en el mo del de longitud estàndard, integrarem el mo del de longitud esp eialitzat al mo del log-lineal de Moses de tres maneres diferents: • Moses-SConjunta : Substitueix els mo dels de traduió de seqüènies de paraules direte i invers p els mo dels de traduió direte i invers prop osats a l'Equaió (2.27). • Moses-SCondiional : A l'igual que en el as del mo del de longitud estàndard, aquest sistema implementa la variant del mo del de longitud esp eialitzat presentada a l'Equaió (2.28). • Moses + SCondiional : Aquest sistema inlou les araterístiques del sistema base Moses sense mo diar, més dues araterístiques addiionals: les probabilitats ondiionades de les longituds en amb dós direions de la traduió, és a dir, els mo dels p(|f|/ e) i p(|e|/ f) . De nou, aquest sistema ens p ermetrà avaluar d'una forma més transparent l'aportaió real del mo del de longitud al pro és de traduió. 70 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 71 #81 i i 3.2. Mo del de longitud esp eialitzat De forma similar al as en el que integràvem el model de longitud estàndard a Moses (veure Seió 3.1.2), hem desenvolupat un programa que pro essa íntegrament la taula de segments, línia p er línia, de forma que, p er a ada parell de seqüènies de paraules ( f , e ), es busa al trie la seqüènia de paraules que ondiiona el mo del ondiional, i llavors es modiquen els valors de les probabilitats de les araterístiques d'aord amb les seqüènies de paraules identiades i el sistema que s'està onstruint ( Moses-SConjunta, Moses-SCondiional, Moses + SCondiional ). Al Capítol 4 també s'analitzaran les prestaions d'aquests tres sistemes en omparaió amb el sistema base de Moses . JASC-DSIC-UPV 71
memoria 2010/11/17 19:32 page 72 #82 i i
memoria 2010/11/17 19:32 page 73 #83 i i Capítol 4 Corpora i Experimentaió Al present apítol avaluarem les prestaions dels sistemes prop osats al apítol anterior. En primer llo , presentarem el orpus que s'ha emprat p er dur a terme aquestes proves, i en segon llo , detallarem els exp eriments realitzats amb els sistemes prop osats i els seus resp etius resultats. 4.1 Corp ora Com ja sab em, un sistema de TAE basat en seqüènies de paraules om Moses requereix, en primer llo , un orpus d'entrenament de parells de frases per p o der entrenar els models que s'integren al mo del log-lineal; en segon llo , un onjunt de validaió p er a justar de forma adequada els paràmetres del mo del log-lineal; i en terer i darrer llo , un onjunt de test p er avaluar les prestaions del sistema. Per tal de obrir aquestes neessitats i p o der dur a terme les exp erimentaions que proposem a la Seió 4.2, s'ha emprat el orpus Europarl-v3 [Ko e05℄. Aquest orpus arreplega les transrip ions de les sessions plenàries de l'Europarlament i les seves orresp onents traduions a un total d'11 llenguatges: Anglès, Alemany, Franès, Italià, Holandès, Portuguès, Danès, Sue, Finès, Gre i Espanyol. Per anitat lingüístia s'ha esollit el orpus assoiat al parell de llenguatges Anglès - Espanyol, en la seva versió 3, que arreplega totes les transrip ions i traduions entre aquests dos llenguatges generades en les sessions esdevingudes entre abril de 1996 i o tubre de 2006. A la taula 4.1 po dem observar les estadístiques d'aquest orpus p er als tres onjunts proveïts (entrenament, validaió i test), abans de ser prepro essats 1 : el nombre total de parells de frases, i p er a adasun dels idiomes, la longitud mitjana en paraules de les frases, la grandària del voabulari (nombre de paraules úniques), el nombre total de paraules, i la p erplexitat del onjunt alulada p er a un mo del de llenguatge de 5-grames, entrenat amb el onjunt d'entrenament i suavitzat amb el mèto de de Kneser-Ney mo diat. 1 Cal notar que: M = Mega = 1.000.000 i K = Kilo = 1.000 73
memoria 2010/11/17 19:32 page 74 #84 i i Capítol 4. Corp ora i Exp erimentaió C. Entrenament C. Validaió C. Test Llenguatge An Es An Es An Es Nombre Frases 730740 2000 2000 Longitud Mitjana (paraules) 20.8 21.5 29.3 30.3 30.0 30.2 Tamany Vo abulari 72.7K 113.9K 6.5K 8.2K 6.5K 8.3K Total paraules 15.2M 15.7M 58.7K 60.6K 58.0K 60.3K Perplexitat (5-grames) - - 79.6 78.8 78.3 79.8 Taula 4.1: Estadístiques del orpus Europarl-v3. Aquest orpus requereix un prepro és (veure Seió 1.1.2) p er ser utilitzat amb el sistema Moses , que onsisteix en tres passos: 1. Tokenitzar les frases ( Tokenize ): Converteix la frase en una adena de text equivalent en la que les unitats bàsiques (paraules, signes de puntuaió, et.) apareixen separades mitjançant espais en blan. Cada unitat bàsia s'anomena token . 2. Filtrar frases llargues ( Filter ): S'eliminen del orpus les frases amb un nombre de tokens ma jor o igual a 40. 3. Transformar aràters a minúsules ( Lowerase ): Els aràters en ma jús- ula es transformen en minúsula. Després de prepro essar el orpus, ens trob em en disp osiió d'entrenar els nostres sistemes i provar les seves prestaions. 4.2 Exp erimentaió En la present seió detallarem adasun dels experiments realitzats, destinats a avaluar si les millores proposades del sistema base de Moses es tradueixen efetivament en una millora de les prestaions. En primera instània exp erimentarem amb el sistema base, p er dues raons: en primer llo , p erquè les seves prestaions seran la referèn- ia p er avaluar si els nous sistemes proposats representen una millora signiativa de l'estat d'art de la disiplina; i en segon llo, p erquè a partir del sistema entrenat ens és molt fàil obtindre la informaió neessària p er estimar els mo dels de longitud prop osats (veure Seions 3.1.1 i 3.2.1). Això té un altre avantatge, i és que p o dem estalviar-nos l'entrenament dels nous sistemes proposats, ja que en tots els asos partirem del sistema base entrenat, al qual se li mo diarà la taula de seqüènies de paraules i el txer de onguraió moses.ini (veure Seió 2.1.4). Tots els sistemes s'han avaluat p er a les dues direions de traduió (an-es i es-en), limitant la longitud màxima de les seqüènies de paraules amb valors que osil · len entre 2 i 7. L'avaluaió de resultats es realitza mitjançant la mètria BLEU (presentada a la Seió 2.1.6) apliant una tènia anomenada b o otstrapping [Koe04, 74 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 75 #85 i i 4.2. Exp erimentaió 28.0 28.2 28.4 28.6 28.8 29.0 29.2 29.4 29.6 29.8 30.0 30.2 30.4 30.6 30.8 31.0 31.2 31.4 2 3 4 5 6 7 Taxa BLEU Max. Longitud de Phrase Sistema Base Moses-LCondicional Moses-LConjunta Moses + LCondicional Figura 4.1: Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes prop osats que implementen el mo del de longitud estàndard, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarlv3, p er a la direió de traduió Anglès - Espanyol. BN04℄, que ens p ermet obtindre la taxa BLEU del onjunt d'hipòtesis amb un interval del 95% de onança. Com a resultats dels exp eriments prop orionarem la mitjana dels extrems de l'interval, arro donida a dèimes. 4.2.1 Sistema base Els exp eriments amb el sistema base s'han realitzat de la següent forma: p er a ada direió de traduió (an-es i es-an), s'ha entrenat el sistema base limitant la longitud màxima de les seqüènies de paraules entre 2 i 7, donant llo a 2×6 = 12 sistemes diferents. El mo del log-lineal del sistema base, om hem desrit a la Seió 2.1.3, presenta les següents araterístiques: • Mo dels de traduió de seqüènies de paraules direte i invers. • Mo dels de suavitzat lèxi direte i invers. • Penalitzaió de seqüènies de paraules (amb ρ= 2.718 ). • Penalitzaió p er paraula. • Mo del de distorsió uniforme. JASC-DSIC-UPV 75
memoria 2010/11/17 19:32 page 76 #86 i i Capítol 4. Corp ora i Exp erimentaió 28.4 28.6 28.8 29.0 29.2 29.4 29.6 29.8 30.0 30.2 30.4 30.6 30.8 31.0 31.2 31.4 31.6 31.8 32.0 2 3 4 5 6 7 Taxa BLEU Max. Longitud de Phrase Sistema Base Moses-LCondicional Moses-LConjunta Moses + LCondicional Figura 4.2: Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes prop osats que implementen el mo del de longitud estàndard, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarlv3, p er a la direió de traduió Espanyol - Anglès. • Mo del de reordenament (onguraió msd-bidiretional-fe ). • Mo del de llenguatge de 5-grames, suavitzat p er interpolaió lineal amb el desompte mo diat de Kneser-Ney. Per laritat i p er evitar redundànies, els resultats dels exp eriments amb el sistema base p er ambdues direions de traduió (an-es i es-en) es mostren onjuntament amb els resultats dels exp eriments realitzats amb els sistemes que implementen ambdós aproximaions del mo del de longitud. A la Seió 4.2.2 s'exposen els resultats del mo del de longitud estàndard, mentre que a la Seió 4.2.3 es mostren els resultats del mo del de longitud esp eialitzat. 4.2.2 Mo del de longitud estàndard En aquesta seió es presenten els resultats obtinguts a l'exp erimentar amb els sistemes que afegeixen informaió del mo dels de longitud estàndard, difereniant els resultats p er a ada via d'estimaió dels mo dels i p er ada direió de traduió. 76 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 77 #87 i i 4.2. Exp erimentaió 28.0 28.2 28.4 28.6 28.8 29.0 29.2 29.4 29.6 29.8 30.0 30.2 30.4 30.6 30.8 31.0 31.2 31.4 2 3 4 5 6 7 Taxa BLEU Max. Longitud de Phrase Sistema Base Moses-LCondicional Moses-LConjunta Moses + LCondicional Figura 4.3: Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes prop osats que implementen el mo del de longitud estàndard, estimat a partir de les segmenta- ions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Anglès - Espanyol. Estimaió a partir de seqüènies de paraules extretes en la fase d'entrenament En primer llo onsiderarem els resultats dels experiments realitzats amb els tres sistemes prop osats, estimant els mo dels de longitud a partir del onjunt de seqüènies de paraules extretes de orpus. D'una banda, a la Figura 4.1 p o dem observar els resultats p er a la direió de traduió Anglès - Espanyol. Com es p ot apreiar, els sistemes Moses-LCondiional i Moses-LConjunta presenten en general prestaions inferiors al sistema base, mentre que el sistema Moses + LCondiional presenta un omp ortament similar al del sistema base, p erò ap ortant ertes millores puntuals, om s'observa als resultats d'aquest sistema entrenat amb una longitud de seqüènies de paraules limitada a 4 i 7, on es millora el sistema base en 3 i 4 dèimes de BLEU, resp etivament. Crida esp eialment l'atenió el punt oinident p er a tots els sistemes entrenats limitant la longitud de les seqüènies de paraules a un màxim de 5, ja que és molt improbable que aquesta irumstània s'esdevinga. No obstant, en realitat els resultats no són idèntis, dons es diferenien en entèsimes de BLEU, però l'arro doniment dels resultats a dèimes ha propiiat aquesta uriosa oinidènia de resultats. Tamb é s'observa JASC-DSIC-UPV 77
memoria 2010/11/17 19:32 page 78 #88 i i Capítol 4. Corp ora i Exp erimentaió 28.4 28.6 28.8 29.0 29.2 29.4 29.6 29.8 30.0 30.2 30.4 30.6 30.8 31.0 31.2 31.4 31.6 31.8 32.0 2 3 4 5 6 7 Taxa BLEU Max. Longitud de Phrase Sistema Base Moses-LCondicional Moses-LConjunta Moses + LCondicional Figura 4.4: Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes prop osats que implementen el mo del de longitud estàndard, estimat a partir de les segmenta- ions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Espanyol - Anglès. una erta inestabilitat en el omp ortament dels sistemes prop osats: p er exemple, el sistema Moses-LConjunta entrenat amb una màxima longitud de 7 avantatja en 2 dèimes al sistema base i en 5 al sistema Moses-LCondiional , quan en la resta de ondiions mostra resultats inferiors al sistema base i molt similars al sistema MosesLCondiional . Trob em que això és degut a un pro és d'a justament de paràmetres p o estable i amb moltes utuaions que deneix uns p esos p o adequats p er a les araterístiques del mo del log-lineal. D'altra banda, a la Figura 4.2 p o dem observar els resultats per a la direió de traduió Espanyol - Anglès. Els sistemes Moses-LCondiional i Moses-LConjunta mostren unes prestaions larament inferiors al sistema base, mentre que el sistema Moses + LCondiional mostra un omp ortament similar al sistema base, o inlús p o dríem dir que lleugerament millor, p er a longituds màximes més urtes (de 2 a 5 paraules). A partir d'una longitud màxima de 6 les prestaions auen p er baix del sistema base. 78 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 79 #89 i i 4.2. Exp erimentaió 28.2 28.4 28.6 28.8 29.0 29.2 29.4 29.6 29.8 30.0 30.2 30.4 30.6 30.8 31.0 31.2 31.4 2 3 4 5 6 7 Taxa BLEU Max. Longitud de Phrase Sistema Base Moses-SCondicional Moses-SConjunta Moses + SCondicional Figura 4.5: Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes prop osats que implementen el mo del de longitud espeialitzat, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarlv3, p er a la direió de traduió Anglès - Espanyol. Estimaió a partir de les segmentaions de Viterbi En segon llo, es mostren els resultats de la exp erimentaió amb els sistemes prop osats, amb els mo dels de longitud onstruïts a partir de les segmentaions de Viterbi. D'una banda, a la Figura 4.3 p o dem observar els resultats p er a la direió de traduió Anglès - Espanyol. De nou ens trob em en que els sistemes Moses-LCondiional i Moses-LConjunta són omparativament inferiors al sistema base. Ara b é, en aquest as el sistema Moses + LCondiional sí que presenta un omp ortament larament millor al sistema base, destaant l'inrement de 5 dèimes de BLEU en el as de la longitud de seqüènies limitada a 2 paraules, o l'inrement de 3 dèimes per a longituds màximes de 5 i 7 paraules. D'altra banda, a la Figura 4.4 p o dem observar els resultats p er a la direió de traduió Espanyol - Anglès. Els resultats són molt similars als observats a la Figura 4.2: els sistemes Moses-LCondiional i Moses-LConjunta mostren unes prestaions larament inferiors al sistema base, mentre que el sistema Moses + LCondiional presenta una qualitat de resultats molt similar al sistema base, si b é en aquest as el grau de similitud és ma jor, i mostrant novament que les prestaions d'aquest sistema JASC-DSIC-UPV 79
memoria 2010/11/17 19:32 page 86 #96 i i Capítol 5. Conlusions i treball futur • Emprar altres tèniques alternatives a la interp olaió lineal p er suavitzar el mo del de longitud esp eialitzat (p er exemple el desompte de Kneser-Ney emprat als mo dels de llenguatges d' n -grames), donat que presenta ma jors indiis de sobreestimaió. • Inloure informaió de la longitud de les seqüènies de paraules al mo del de reordenament lexialitzat, de forma anàloga a la inlusió d'aquesta informaió al mo del de traduió. La realitzaió d'aquestes ampliaions po drien traduir-se en un inrement signi- atiu de les prestaions del sistema base, que és un dels ob jetius que s'ha p erseguit a aquest treball, i que s'ha aonseguit de forma parial. 86 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 87 #97 i i Bibliografia [AdT82℄ D. Arnold and L. des Tomb e. Basi theory and methodology in eurotra. In S. Niremburg, editor, Mahine Translation: Theoretial and Methodologial Issues , pages 114135, 1982. [AF10℄ Jesús Andrés-Ferrer. Statistial approahes for natural language model ling and monotone statistial mahine translation . PhD thesis, Universidad Politénia de Valenia, Valenia (Spain), Feb 2010. Advisors: A. Juan and F. Casaub erta. [AFJ09℄ Jesús Andrés-Ferrer and Alfons Juan. A phrase-based hidden semimarkov approah to mahine translation. In Proedings of European Assoiation for Mahine Translation (EAMT) , pages 168175, Barelona, Spain, May 2009. Europ ean Asso iation for Mahine Translation. [B + 90℄ P. F. Brown et al. A Statistial Approah to Mahine Translation. Computational Linguistis , 16(2):7985, 1990. [B + 93℄ P. F. Brown et al. The Mathematis of Statistial Mahine Translation: Parameter Estimation. Computational Linguistis , 19(2):263311, 1993. [BBC + 09℄ Sergio Barrahina, Oliver Bender, Franiso Casaub erta, Jorge Civera, Elsa Cub el, Shahram Khadivi, Antonio Lagarda, Hermann Ney, Jesús Tomás, Enrique Vidal, and Juan M. Vilar. Statistial approahes to omputer-assisted translation. Comput. Linguist. , 35(1):328, 2009. [BF81℄ A. Ban and A. Feigenbann. The Handbook of Artiial Intel ligene . Pitman, 1981. [BH60℄ Y. Bar-Hillel. The present status of automati translation of languages. Advanes in Computers , 1:91163, 1960. [Bil82℄ R. Billmeyer. Zu den linguistishen Grundlagen von SYSTRAN. Multilingua , 2(1):8396, 1982. [BN04℄ M. Bisani and H. Ney. Bo otstrap estimates for ondene intervals in asr p erformane evaluation. In IEEE International Conferene on Aoustis, Speeh, and Signal Proessing , volume 1, pages 409412, Montreal, may 2004. [CBKM + 10℄ Chris Callison-Burh, Philipp Koehn, Christof Monz, Kay Peterson, Mark Przyb o ki, and Omar Zaidan. Findings of the 2010 joint workshop on statistial mahine translation and metris for mahine translation. In 87
memoria 2010/11/17 19:32 page 88 #98 i i Bibliograa Proeedings of the Joint Fifth Workshop on Statistial Mahine Translation and MetrisMATR , pages 1753, Uppsala, Sweden, July 2010. Asso iation for Computational Linguistis. [Civ08℄ J. Civera. Novel statistial approahes to text lassiation, mahine translation and omputer-assisted translation . PhD thesis, Universidad Politénia de Valenia, Valenia (Spain), Juny 2008. Advisors: A. Juan and F. Casaub erta. [CV04℄ Franiso Casaub erta and Enrique Vidal. Mahine translation with inferred sto hasti nite-state transduers. Comput. Linguist. , 30(2):205 225, 2004. [CV07℄ F. Casaub erta and E. Vidal. Learning nite-state mo dels for mahine translation. Mahine Learning , 66(1):6991, 2007. [CVP05℄ F. Casaub erta, E. Vidal, and D. Pió. Inferene of nite-state transduers from regular languages. Pattern Reognition , 38:14311443, 2005. [Dej℄ Dejavú. http://www.atril.om. [DLR77℄ A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likeliho o d from inomplete data via the em algorithm. JOURNAL OF THE ROYAL STATISTICAL SOCIETY, SERIES B , 39(1):138, 1977. [Do d02℄ George Do ddington. Automati evaluation of mahine translation quality using n-gram o-o urrene statistis. In HLT '02: Proeedings of the seond international onferene on Human Language Tehnology Researh , pages 138145, San Franiso, CA, USA, 2002. Morgan Kaufmann Publishers In. [FLL02℄ G. Foster, P. Langlais, and G. Lapalme. User-friendly text predition for translators. In Pro. of EMNLP'02 , pages 148155, Morristown, NJ, USA, July 2002. Asso iation for Computational Linguistis. [Fos02℄ G. Foster. Text Predition for Translators . PhD thesis, Université de Montréal, May 2002. [Go o℄ Go ogle translate to olkit. http://translate.go ogle.om/supp ort/to olkit/. [GV03℄ I. Garía-Varea. Traduión automátia estadístia: modelos de tradu- ión basados en máxima entropía y algoritmos de búsqueda . PhD thesis, Departamento de Sistemas Informátios y Computaión, Universidad Politénia de Valenia, Deemb er 2003. [HK℄ Johen Hummel and Iko Knyphausen. Trados. http://www.trados.om. [IC97℄ P. Isab elle and K. Churh. Sp eial issue on new tools for human translators. Mahine Translation , 12(12), 1997. 88 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 89 #99 i i Bibliograa [Kay97℄ M. Kay. The prop er plae of men and mahines in language translation. Mahine Translation , 12:323, 1997. [KHB + 07℄ Philipp Koehn, Hieu Hoang, Alexandra Birh, Chris Callison-Burh, Marello Federio, Niola Bertoldi, Bro oke Cowan, Wade Shen, Christine Moran, Rihard Zens, Chris Dyer, Ondrej Bo jar, Alexandra Constantin, and Evan Herbst. Moses: Op en soure to olkit for statistial mahine translation. In ACL . The Asso iation for Computer Linguistis, 2007. [Kni99a℄ K. Knight. Deo ding omplexity in word-replaement translation mo dels. Computional Linguistis , 25(4):607615, 1999. [Kni99b℄ Kevin Knight. A stadistial mahine translation tutorial workb o ok. http://www.isi.edu/natural-language/mt/wkbk.p df, August 1999. [Ko e04℄ Philipp Ko ehn. Statistial signiane tests for mahine translation evaluation, 2004. [Ko e05℄ P. Ko ehn. Europarl: A parallel orpus for statistial mahine translation. In Pro. of the MT Summit X , pages 7986, Septemb er 2005. [Ko e10℄ Philipp Ko ehn. Stadistial Mahine Translation . Cambridge University Press, Edinburgh (United Kingdom), 2010. [LFL00℄ P. Langlais, G. Foster, and G. Lapalme. Unit ompletion for a omputeraided translation typing system. Mahine Translation , 15(4):267294, 2000. [LLL02℄ P. Langlais, G. Lapalme, and M. Loranger. Transtyp e: Developmentevaluation yles to b o ost translator's pro dutivity. Mahine Translation , 15(4):7798, 2002. [MS99℄ Christopher D. Manning and Hinrih Shütze. Foundations of Statistial Natural Language Proessing . The MIT Press, Cambridge, Massahusetts, 1999. [Mur66℄ Hub ert Murray. Methods for Satisfying the Needs of the Sientist and the Engineer for Sienti and Tehnial Communiation . In a Press Release, Washington D.C., 1966. [NGW95℄ Hermann Ney, M. Generet, and F. Wessel. Extensions of absolute dis- ounting for language mo deling. In Pro. of the Fourth European Conferene on Speeh Communiation and Tehnology , pages 12451248, Madrid, Spain, September 1995. [Oh03℄ F. J. Oh. Minimum error rate training in statistial mahine translation. In Pro. of ACL'03 , pages 160167, Morristown, NJ, USA, July 2003. Assoiation for Computational Linguistis. JASC-DSIC-UPV 89
memoria 2010/11/17 19:32 page 90 #100 i i Bibliograa [ON03℄ Franz Josef Oh and Hermann Ney. A systemati omparison of various statistial alignment mo dels. Computational Linguistis , 29, 2003. [PC66℄ John R. Piere and John B. Carroll. Languages and mahines omputers in translation and linguistis. Tehnial rep ort, Automati Language Pro essing Advisory Committe (ALPAC), National Aademy of Sienes, 1966. [PRWZ01℄ K. Papineni, S. Roukos, T. Ward, and W. Zhu. BLEU: a Metho d for Automati Evaluation of Mahine Translation. Tehnial Rep ort RC22176, Thomas J. Watson Researh Center, 2001. [SDS + 06℄ Matthew Snover, Bonnie Dorr, Rihard Shwartz, Linnea Miiulla, and John Makhoul. A study of translation edit rate with targeted human annotation. In In Proeedings of Assoiation for Mahine Translation in the Amerias , pages 223231, 2006. [Slo85℄ J. Slo um. A survey of mahine translation: its history, urrent status and future prosp ets. Computational Linguistis , 11(1):117, 1985. [Sto02℄ A. Stolke. Srilm an extensible language mo deling to olkit. http://www.sp eeh.sri.om, 2002. [Tih82℄ B. Tihouin. The Meteo System. In Veronia Lawson, editor, Pro. of Pratial Experiene of Mahine Translation , pages 3944, 1982. [TVN + 97℄ C. Tillmann, S. Vogel, H. Ney, A. Zubiaga, and H. Sawaf. Aelerated dp based searh for statistial translation. In In European Conf. on Speeh Communiation and Tehnology , pages 26672670, 1997. [UoG95℄ Multilingual Information Proessing Department University of Geneva. Evaluation of natural language proessing systems. http://www.isso.unige.h/en/researh/pro jets/ewg95/, 1995. [VB85℄ Bernard Vauquois and Christian Boitet. Automated translation at grenoble university. Comput. Linguist. , 11(1):2836, 1985. [Wea55℄ W. Weaver. Translation. In W. N. Loke and A. D. Bo oth, editors, Mahine Translation of Languages: fourteen essays , pages 1523. MIT Press, Cambridge, MA., 1955. [WWC + 86℄ P. J. Whitelo k, M. MGee Wo o d, B. J. Chandler, N. Holden, and H. J. Horsfall. Strategies for interative mahine translation: the exp eriene and impliations of the UMIST Japanese pro jet. In Pro. of COLING'86 , pages 329334, Bonn, Germany, August 1986. 90 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 91 #101 i i Índex de figures 1.1 Triangle de Vauquois . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Arquitetura general del pro és de traduió basat en el raonament sobre la regla de Bayes. . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Exemple senzill d'alineament de paraules entre dues frases. . . . . . . 21 1.4 Exemple d'alineament en el que les paraules alineades o up en p osiions diferents en adasuna de les frases. . . . . . . . . . . . . . . . . . . . 22 1.5 Exemple d'alineament en el que una paraula d'eixida es troba rela- ionada amb més d'una paraula d'entrada. . . . . . . . . . . . . . . . . 22 1.6 Exemple d'alineament en el que paraules de la frase d'eixida no han estat alineades amb ap paraula de la frase d'entrada. . . . . . . . . . 23 1.7 Exemple d'alineament en el que paraules de la frase origen es trob en alineades amb la paraula destí esp eial NULL . . . . . . . . . . . . . . 23 1.8 Exemple del pro és de traduió automàtia en sistemes basats en seqüènies de paraules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.9 Exemple d'extraió de parells de seqüènies de paraules a partir de l'alineament entre paraules d'un parell de frases. . . . . . . . . . . . . 28 1.10 Exemples de p ossibles seqüènies de paraules onsistents i inonsistents, dep enent de l'alineament entre les paraules d'un parell de frases qualsevol. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.11 Exemple d'un transdutor esto àsti d'estats nits (sense probabilitats asso iades). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.12 Exemple d'arbre que representa la frase en anglès I shal l be passing on to you some omments mo delada amb una gramàtia d'estruturaió de frases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.1 Exemples dels tres tipus d'orientaions que p o den donar-se llo a un mo del de reordenament lexialitzat. . . . . . . . . . . . . . . . . . . . . 42 3.1 Exemple d'alineament entre paraules d'un parell de frases, extret del orpus Europarl-v3 per al parell de llenguatges anglès - espanyol (veure Seió 4.1). Aquest alineament requereix, en el pro és de traduió, l'extraió d'una seqüènia d'11 paraules de longitud om a mínim (denotada p er la franja grisa), segons l'algorisme d'extraió de seqüènies de paraules de Moses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2 Exemple d'una estrutura de dades trie. . . . . . . . . . . . . . . . . . 63 91
memoria 2010/11/17 19:32 page 92 #102 i i Índex de gures 3.3 Distribuió del nombre de no des emmagatzemats a ada nivell de trie . S'apreia, en esala logarítmia, el nombre mitjà de no des residents a ada nivell d'un trie onstruït a partir de les seqüènies de paraules en espanyol extretes de forma heurístia a partir del onjunt d'entrenament del orpus Europarl-v3 (veure Seió 4.1), onsiderant seqüènies de paraules limitades a 7 paraules de longitud. S'observa una lara tendènia exp onenial inversa del nombre mitjà de no des onforme s'aprofundeix en l'arbre. . . . . . . . . . . . . . . . . . . . . . . . . . . 66 3.4 Distribuió del la longitud de les seqüènies de paraules, estimada a partir de les seqüènies de paraules en espanyol extretes de forma heurístia a partir del onjunt d'entrenament del orpus Europarl-v3 (veure Se- ió 4.1), onsiderant seqüènies de paraules limitades a 7 paraules de longitud. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.1 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud estàndard, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Anglès - Espanyol. 75 4.2 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud estàndard, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Espanyol - Anglès. 76 4.3 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud estàndard, estimat a partir de les segmentaions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Anglès - Espanyol. . 77 4.4 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud estàndard, estimat a partir de les segmentaions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Espanyol - Anglès. . 78 4.5 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud esp eialitzat, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Anglès - Espanyol. 79 4.6 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud esp eialitzat, estimat a partir del onjunt de seqüènies de paraules extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Espanyol - Anglès. 80 92 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 93 #103 i i Índex de gures 4.7 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud esp eialitzat, estimat a partir de les segmentaions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Anglès - Espanyol. . 81 4.8 Taxa BLEU, en funió de la màxima longitud que p o den assolir les seqüènies de paraules, del sistema base i dels tres sistemes proposats que implementen el mo del de longitud esp eialitzat, estimat a partir de les segmentaions de Viterbi extretes del onjunt d'entrenament del orpus Europarl-v3, p er a la direió de traduió Espanyol - Anglès. . 82 JASC-DSIC-UPV 93
memoria 2010/11/17 19:32 page 94 #104 i i Índex de gures 94 JASC-DSIC-UPV
memoria 2010/11/17 19:32 page 95 #105 i i Índex de taules 1.1 Exemple d'anàlisi freqüenial de trigrames i estimaió de probabilitats d'o urrènia d'una paraula donada la història the red al orpus Europarl (on the red s'esdevé 225 vegades). . . . . . . . . . . . . . . . . . . . . . 17 1.2 Exemple d'estimaió de probabilitats de traduió lèxiques p er a la paraula glass (on N( glass ) = 1000 ). . . . . . . . . . . . . . . . . . . . . 20 3.1 Anàlisi de la omplexitat temp oral de les op eraions de era i inserió al trie original i al trie optimitzat. . . . . . . . . . . . . . . . . . . . . 69 4.1 Estadístiques del orpus Europarl-v3. . . . . . . . . . . . . . . . . . . . 74 95