PA153 Strojový překlad Vít Baisa Překlad Překlad je převod textu ze zdrojového jazyka do jazyka cílového. ► odborný překlad x literární překlad ► přesná reprodukce x volná převodová parafráze Maimonidés, 12. stol. Pro překlad slova je rozhodující kontext. Werner Winter Každé slovo je element vytržený z celkového jazykového systému a jeho vztahy k jiným segmentům systému jsou v jednotlivých jazycích rozdílné. Každý význam je element z celého systému segmentů, v něž mluvčí rozčleňuje skutečnost. V jazyce Mohave: otec ženy ^ otec muže Otázky překladu ► Je vůbec přesný překlad mezi jazyky možný? ► Jak se pozná, že je překladový ekvivalent slova w2? ► anglické typy větru, eskymácké typy sněhu, ... ► jak přeložit slova jako alkáč, večerníček, telka, čoklbuřt, knížečka, ČSSD ... ? Strojový překlad I - definice Strojový překlad Obor počítačové lingvistiky zabývající se návrhem, implementací a aplikací automatických systémů (programů) pro překlad textů s minimálním zásahem člověka. Např. používání elektronických slovníků při překladu nepatří do strojového překladu. Strojový překlad II - predmet zájmu Zejména: ► webové stránky ► technické manuály ► vědecké dokumenty ► prospekty, katalogy ► právnické texty ► obecně texty z omezených domén Nuance na různých jazykových vrstvách v umělecké literatuře jsou mimo schopnosti současných nástrojů NLP. Strojový překlad III Ve skutečnosti je výstup z MT vždy revidován. Mluví se o před-překladu resp. o post-editaci. Ta je někdy nutná i u člověka, ovšem systémy MT dělají zcela rozdílné chyby. Pro člověka jsou typické chyby: ► špatné předložky (/ am in school) ► chybějící členy (/ saw marí) ► špatné tvary slov: mouses, breaked, ... Pro počítač jsou typické zejména chyby významové: Kiss me, honey. Metody přímého zlepšení kvality strojového překladu ► omezení vstupu na: ► podjazyk (oznamovací věty) ► doménu (informatika) ► typ dokumentu (patentové dokumenty) ► pre-processing textu (např. ruční syntaktická analýza) Klasifikace podle přístupu (approach) ► pravidlový (znalostní) strojový překlad rule-based, knowledge-based - RBMT, KBMT ► transferový ► interlingua ► statistický strojový překlad statistical machine translation - SMT Example-based machine translation - EBMT ► hybridní strojový překlad hybrid machine translation - HMT, HyTran Vauquoisův trojúhelník Interlingua Klasifikace podle interakce s uživatelem ► (ruční překlad) ► ruční překlad s pomocí počítače machine-aided human translation - MAHT ► automatický překlad s interagujícím překladatelem human-aided machine translation - HAMT plně automatický překlad fully automated high-quality (M)T- FAHQT HAMT a MAHT někdy souhrnně označovány jako CAT -computer-aided translation. Rané názory na strojový překlad ► překlad je často opakovaná činnost - věřilo se, že bude tuto proceduru možné počítačem napodobit ► úspěchy použití počítačů v kryptografii: vhodné i pro strojový překlad? Warren Weaver When I look at an article in Chinese, I say: This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode. Georgetown experiment První funkční prototyp strojového překladu. ► 50 vět (zřejmě pečlivě vybraných) ► spolupráce s IBM ► slovník obsahoval 250 slov ► překlad z ruštiny do angličtiny ► gramatika pro ruštinu obsahovala 6 pravidel Demonstrace systému vyvolala nadšení. MT bylo očividně možné. Následně odstartovalo mnoho nových projektů, hlavně v USA a Rusku. Vývoj v 50. letech MT oblast podnítila rozvoj a výzkum na poli teoretické lingvistiky (Chomsky) počítačové lingvistiky ► umělé inteligence (60. léta) ► s větším pokrytím kvalita strojového překladu klesala ► i nejlepší systémy (GAT, Georgetown, RU^EN) poskytovaly nepoužitelný výstup Zklamání ze slabých výsledků ► i přes nevalné výsledky přetrvával optimismus ► Yehoshua Bar-Hillel píše v roce 1959 kritiku stavu strojového překladu ► tvrdí, že počítače nejsou schopné provádět lexikální desambiguaci ► fully automated high-quality translation (FAHQT) podle Bar-Hillela stěží dosažitelné Yehoshua Bar-Hillel - příklad pro desambiguaci Little John was looking for his toy box. Finally, he found it. The box was in the pen. John was very happy. Výdaje na projekty strojového překladu se začaly snižovat. ALPAC report ► Automatic Language Processing Advisory Commitee ► organizace pod U.S. National Academy of Science ► analýzy a vyhodnocení kvality a použitelnosti systémů MT ► doporučila omezit výdaje na podporu strojového překladu ► vývoj strojového překladu v Evropě a Japonsku pokračoval nepřerušené dál ► celých 15 let trvalo než MT v USA znovu získal vážnost a původní postavení TAUM, METEO TAUM ► Traduction Automatique ä l'Université de Montreal ► Universitě de Montreal in 1965 ► prototypy MT systémů: TAUM-73, TAUM-METEO ► jedny z prvních systémů provádějící automatický překlad přes analýzu zdrojového jazyka a syntézu cílového jazyka ► překlad z angličtiny do francouzštiny METEO ► 1981-2001 používán pro překlad předpovědí počasí ► autor John Chandiou, Kanada Systran ► jedna z nejstarších MT firem (1968) ► velmi populární překladový systém ► základ Yahoo Babel fish, do r. 2007 využíván v Google ► RBMT, od r. 2010 hybridní překlad ► od r. 1976 oficiální MT systém používaný Evropským hospodářským společenstvím Strojový překlad v současnosti ► intenzivní sběr paralelních dat ► vývoj systémů vzhledem k hodnotícím metrikám ► USA: zájem o angličtinu jako TL ► EU: překlad mezi 23 úředními jazyky EU (EuroMatrix) ► korporace (Microsoft) zaměřeny na En jako SL ► SMT obohacována syntaxí ► velké páry (En^Sp, En^Fr): velmi dobrý překlad ► Google Translate jako gold standard ► morfologicky bohaté jazyky jsou opomíjeny ► En-* a *-En páry převažují Motivace pro strojový překlad ve 21. století překlad webových stránek pro pochopení obsahu (gisting) ► metody pro výrazné urychlení překladatelské práce (překladové paměti) ► extrakce a vyhledávání informací mezi jazyky (cross-lingual IR) ► instantní překlad instantní komunikace ► překlad na mobilních zařízeních EuroMatrix, 2006-2009 ► překlad všech párů EU jazyků ► využití lingvistické znalosti ve statistickém MT ► vývoj a testování hybridních architektur ► každoroční vyhodnocování kvality MT ► open source: nástroje, software, data ► přehled stavu MT pro EU jazyky Závěr úvodu ► strojový překlad patří mezi Ul-kompletní problémy ► máme k dispozici obrovskou výpočetní sílu ► tržní potenciál je větší než kdy dřív ► statistické metody se aktuálně zdají vhodnější ► nové nápady jsou vítány! (BP, DP) Rule-based Machine Translation - RBMT ► lingvistické znalosti formou pravidel ► pravidla pro analýzu ► pravidla pro převod struktur mezi jazyky ► pravidla pro syntézu ► Knowledge-based Machine Translation Rozdělení systémů RBMT: ► přímý překlad ► systémy používající interlinguu ► transferové systémy Interlingua vs. transferové KBMT Proces analýzy ► tokenizace ► morfologická analýza (značkování) ► morfologická disambiguace (pravidlová, statistická) ► syntaktická analýza ► sémantická analýza: lexikálni disambiguace slovo analýzy disambiguace Pravidelné k2eAgMnPc4d1, k2eAglnPc1 d1, k2eAglnPc4d1, k2eAglnPc5d1, k2eAgFnSc2d1, k2eAgFnSc3d1, k2eAgFnSc6d1, k2eAgFnPc1d1, k2eAgFnPc4d1, k2eAgFnPc5d1, k2eAgNnSc1d1, k2eAgNnSc4d1, k2eAgNnSc5d1, ... (+5) k2eAgNnSc1d1 krmení k2eAgMnPc1 d1, k2eAgMnPc5d1, k1 gNnSd, k1gNnSc4, k1gNnSc5, k1gNnSc6, k1gNnSc3, k1gNnSc25 k1gNnPc25 klgNnPd, k1gNnPc45 k1gNnPc5 klgNnSd je k5eAalmlp3nS5 k3p3gMnPc45 k3p3glnPc45 k3p3gNnSc45 k3p3gNnPc45 k3p3gFnPc45 kO k5eAalmlp3nS pro k7c4 k7c4 správný k2eAgMnSc1d15 k2eAgMnSc5d1, k2eAglnSc1d1, k2eAglnSc4d15 k2eAglnSc5d1, ... (+18) k2eAglnSc4d1 růst k5eAalmF5 klglnSd, k1glnSc4 k1glnSc4 důležité k2eAgMnPc4d1, k2eAglnPd d1, k2eAglnPc4d1, k2eAglnPc5d1, k2eAgFnSc2d1, k2eAgFnSc3d1, k2eAgFnSc6d1, k2eAgFnPdd1, k2eAgFnPc4d1, k2eAgFnPc5d15 k2eAgNnSdd1, k2eAgNnSc4d1, k2eAgNnSc5d15 ... (+5) k2eAgNnSdd1 Statistický MT ► pravidlové systémy motivovány lingvistikou ► SMT inspirován teorií informace a statistikou ► 50 miliónů stránek denně přeložených pomocí SMT ► gisting: stačí, má-li překlad nějaký užitek, nepotřebujeme přesný význam; nejčastější užití MT na internetu Schéma SMT Spanish/English Bilingual Text CEnglish Text ^) Statistical Analysis Statistical Analysis Spanish Broken English English Translation Model Language Model 4 * Decoding Algorithm argmax P(e)*p(s|e) Data pro SMT - (paralelní) korpusy ► Europarl: kolekce textů Evropského parlamentu ► OPUS: paralelní texty různého původu ► Acquis Communautaire: právní dokumenty Evropské únie (20 jazyků) ► volně dostupné jsou řádově 10 a 100 miliónů slov veliké ► vícejazyčné stránky (Wikipedie) ► srovnatelné korpusy (comparable corpora): texty ze stejné domény, ne přímé překlady: New York Times - Le Monde ► Kapradí - korpus překladů Shakespearových dramat (Fl) ► InterCorp - ručně zarovnané beletr. texty (ČNK, FFUK) SMT - princip noisy channel Vyvinut Shannonem (1948) pro potřeby samoopravujících se kódů, pro korekce kódovaných signálů přenášených po zašuměných kanálech na základě informace o původní zprávě a typu chyb vznikajících v kanálu. Příklad s OCR. Rozpoznávání textu z obrázků je chybové, ale dokážeme odhadnout, co by mohlo být v textu (jazykový model) a jaké chyby často vznikají: záměna 1-1 -I, rn-m apod. e* = arg maxp(e|ř) e p{e)p{f\e) = arg max ' ,\ p{f) = arg maxp(e)p(ř|e). e Jazykové modely ► LM pomáhají zajistit plynulý výstup (správný slovosled) ► LM pomáhají s WSD v obecných případech ► pokud má slovo více významů, můžeme vybrat nejčastější překlad {pen pero) ► ve speciálních textech nelze použít, ale ► LM pomáhají s WSD pomocí kontextu ► PlmO 9° home) > pLM{\ go house) N-gramové modely ► n-gram je nejdůležitější nástroj ve zpracování řeči a jazyka ► využití statistického pozorování dat Generování unigramy To him swallowed confess hear both. Which. Of save on trail for are ay device and rote life have Every enter now severally so, let. Generování trigramy Sweet prince, Falstaff shall die. Harry of Monmouth's grave. This shall forbid it should be branded, if renown made it empty. Kvalita a srovnání jazykových modelů Chceme být schopni porovnávat kvalitu různých jazykových modelů (trénovány na různých datech, pomocí jakých n-gramů, jak vyhlazených apod.). Je možné použít 2 přístupy: vnější (extrinsic) a vnitřní (intrinsic) vyhodnocení. Dobrý model by měl přiřadit dobrému textu vyšší pravděpodobnost než špatnému textu. Pokud máme nějaký testovací text, můžeme spočítat pravděpodobnost, jakou mu přiřazuje zkoumaný LM. Lepší LM by mu měl přiřadit vyšší pravděpodobnost. Vyhlazování jazykových modelů Problém: pokud není v datech určitý n-gram, který se vyskytne v řetězci w, pro který hledáme pravděpodobnost, bude p{w) = 0. Potřebujeme rozlišovat p i pro neviděná data. Musí platit Mw.p{w) > 0 Ještě větší je problém u modelů vyšších řádů. Snaha o upravení reálných počtů n-gramů na očekávané počty těchto n-gramů v libovolných datech (jiných korpusech). Add-one, add-alpha, deleted estimation, Good-Turing vyhlazování Interpolace Předchozí metody zacházely se všemi neviděnými n-gramy stejně. Předpokládejme 3-gramy: nádherná červená řepa nádherná červená mrkev I když ani jeden nemáme v trénovacích datech, první 3-gram by měl být pravděpodobnější. Budeme využívat pravděpodobnosti n-gramů nižších řádů, u kterých máme k dispozici více dat: červená řepa červená mrkev Velké jazykové modely - počet n-gramů Kolik je různých n-gramů v korpusu? řád unikátní singletony unigram 86700 33447 (38,6%) bigram 1 948 935 1 132844 (58,1 %) trigram 8092798 6022286 (74,4%) 4-gram 15 303 847 13 081 621 (85,5%) 5-gram 19882175 18324577 (92,2%) Europarl, 30 miliónů tokenů. Výpočet překladové pravděpodobnosti Pro výpočet p(e, a|f) potřebujeme znát hodnotu funkce t pro všechna slova (věty). K tomu budeme využívat základní zdroj pro SMT: paralelní korpus se zarovnanými větami. Bohužel nemáme zarovnání slov mezi sebou. To je úkol tzv. word-alignment. Ke slovu přichází expectation-maximization (EM) algoritmus. Ilustrace EM algoritmu .., la maison .., la maison blue .,. la fleur ,.. ... the house ,,, the blue house ... the flower .,. .., la maison .,. la maison bleu ,.. la fleur ,.. ... the house ... the blue house .,. the flower ... p(la|the) = 0,453 p(le|the) - 0.334 p(maison|house) = 0,876 p(bleu|blue) = 0,563 Matice zarovnání slov 0 cti o E -t—1 o -C > 0 Cti O) "O CO cti CO CO cti "O o5 .1 CO _Q Cti ^ JZ _Q Problémy se zarovnáním slov Frázový překladový model State-of-the-art statistického strojového překladu. Nepřekládají se pouze samostatná slova. Když to jde, tak i celé sekvence slov. natuerlich of course spass am spiel fun with the game Fráze nejsou lingvisticky motivované, pouze statisticky. Německé am se zřídka překládá jedním slovem with. Statisticky významný kontext spass am pomáhá správnému překladu. Klasické fráze by se dělily jinak: (fun (with (the game))). Výhody PBTM ► často překládáme n : m slov, slovo je tedy nevhodný atomický prvek ► překlad skupin slov pomáhá řešit překladové víceznačnosti ► můžeme se učit překládat delší a delší fráze ► jednodušší model: neuvažujeme fertilitu, NULL token atd. Extrahování frází michael assumes that he will stay in the house Automatické hodnocení překladu ► výhody: rychlost, cena; nevýhody: měříme opravdu kvalitu? ► gold standard: ručně připravené referenční překlady ► kandidát c se srovnává s n referenčními překlady r, ► různé přístupy: n-gramová shoda mezi c a r,, editační vzdálenost, ... Pokrytí a přesnost na slovech Nejjednodušší způsob automatického hodnocení system a: Israeli officials rooponoibility ef airport safety / / \ reference: Israeli officials are responsible for airport security ► přesnost correct output-length 6 = - = 50°/ ► pokrytí correct reference-length 7 = = = 43°/ ► f-score precision x recall .5 x .43 (precision + recall) /2 (.5 + .43) /2 = 46% Pokrytí a přesnost - nedostatky system a: Israeli officials rooponoibility ef airport safety reference: Israeli officials are responsible for airport security system b: airport security Israeli officials are responsible metrika systém A systém B přesnost 50% 100% pokrytí 43% 100% f-score 46% 100% Nepostihuje se nesprávný slovosled. nejznámější (standard), nejpoužívanější, nejstarší (2001) IBM, Papineni n-gramová shoda mezi referencí a kandidáty počítá se přesnost pro 1 až 4-gramy extra postih za krátkost (brevity penalty) BLEU = min 1 output-length (J J precisionj)4 /=1 reference-length BLEU - příklad system a: Israeli officials | responsibility of | airport | safety 2-gram match 1 -gram match reference: Israeli officials are responsible for airport security system b: airport security 11Israeli officials are responsible 2-gram match 4-gram match metrika systém A systém B přesnost (1gram) 3/6 6/6 přesnost (2gram) 1/5 4/5 přesnost (3gram) 0/4 2/4 přesnost (4gram) 0/3 1/3 brevity penalty 6/7 6/7 BLEU 0% 52% Další metriky ► NIST, N EVA ► WAFT ► Word Accuracy for Translation ► editační vzdálenost mezi car ► WAFT = 1 - J+f+j > max(lr,lc) ► TER ► Translation Edit Rate ► nejmenší počet kroků (smazání, přidání, prohození, změna) ^ -|-ER _ počet editací * ~ prům. počet ret slov ► METEOR ► uvažuje synonyma (WordNet) a ► morfologické varianty slov Hodnocení hodnotících metrik Korelace automatického hodnocení s manuálním. Hodnocení překladu podle jazykových párů EG - A « 1 - 1 HU * 1 ut Mf N- =11 J 101 -e e 123 103 413 11.2 e- e 333 JO.l 372 104 593 434 33 3 :i 3 -3 2 113 493 44.7 10.7 123 as 33.7 334 393 341 43.9 211 26.7 424 22 :■ -e : 293 29.1 213 443 31.1 413 33 3 34..1 34.1 59.9 :?= 15 3 253 J = ľ 4 43.1 323 47.1 25.7 231 394 27 S 42.7 273 503 193 502 50.2 44.1 30.7 294 314 41.2 (5 ä* 323 42.5 > -3 e 343 43.9 30.7 301 413 274 443 341 313 11 3 131 392 41.7 361 433 413 42.9 HA 17 jS 25.7 44.1 31.7 J 343 47.1 273 313 413 242 433 29.7 = £ E 21.1 431 343 414 53.9 333 552 47.2 EL 591 324 45.1 37.7 ľ > 14.0 251 233 43.5 23.7 49.5 293 323 133 433 542 ľ = 7 2 53.1 553 45.3 3 3 50 jo 31.1 42.7 371 444 394 J 214 231 113 243 11.7 253 301 24 3 433 553 173 33.1 31.7 553 43.7 ET 523 24.5 373 312 373 232 -j 4 J 37.7 334 503 373 513 55.9 201 413 523 373 233 503 523 = ľ = H «3 232 ee j 32 jo 573 272 39.7 343 J 291 272 EE E 301 3:.: 194 -:■ 3 233 371 251 273 232 37.6 = =: :— :■ 5-4-1 41.1 E31 474 4£3 50.9 25.7 303 J 211 15.1 233 313 25 3 113 51.7 513 43 3 53.1 513 41.3 -_■ 453 24.7 =43 503 353 211 34.1 293 25 4 30.7 J 331 293 313 13.1 55.1 2= 5 =4 2 25.7 253 25 2 30.1 ir 513 32.1 ■143 ee e 453 403 2E e 213 29.7 12.7 242 J 294 323 243 501 512 151 393 321 34.7 44 E LT au 275 333 37 jo 553 231 11.1 342 323 = 44 231 553 J 10.1 :: 2 53.1 513 313 19.5 313 513 31.5 lv MjO 23.1 = ľ ľ. 373 331 23.7 25.3 34.2 324 313 233 53.9 534 / 233 411 544 593 513 333 57.1 55.0 v- 72_1 EDC3 37.2 373 533 33.7 43.7 253 2ľ e 424 11- -E ľ 332 532 J 443 3T . 41.9 53.9 313 403 41.6 ^. 153 233 433 373 414 313 13.7 271 233 434 :: = 441 2= E 31.7 223 J 523 47.7 533 50.1 =4 5 43.6 PL 503 311 402 —: 42.1 3*2 43.2 292 29 3 403 241 432 332 313 273 — 5 / 44.1 = = 2 = = 2 593 42.1 PT 50.7 314 423 334 e 40.2 63.7 234 292 152 233 123 233 311 243 493 541 J 394 32.1 344 43.9 Ed 503 33.1 331 373 403 313 .504 24 e 25 2 451 :■ — = 234 233 23.7 433 513 -E: J 311 51.1 394 3-í 50* 325 39 .i 13.1 4<3 ee e 43.2 293 234 394 274 413 553 33 ~ 231 —- 393 433 313 J 42 3 41.3 e. 613 33.1 373 431 -L e 343 47.0 31.1 2E e 332 21.7 423 343 373 303 413 532 44.1 513 533 / 42.7 5* 151 253 413 313 -e e 333 -e e 274 30 3 e e e 22.7 423 2= : 313 23.7 413 52: — 2 32.7 = . = 551 J