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 w-\ 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 - předmět 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 schod) ► chybějící členy (/ saw man) ► š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 (EnoSp, EnoFr): 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 ► 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, k2eAglnPc1d1, k2eAglnPc4d1, k2eAglnPc5d1, k2eAgFnSc2d1, k2eAgFnSc3d1, k2eAgFnSc6d1, k2eAgFnPc1d1, k2eAgFnPc4d1, k2eAgFnPc5d1, k2eAgNnSc1d1, k2eAgNnSc4d1, k2eAgNnSc5d1, ... (+5) k2eAgNnSc1d1 krmení k2eAgMnPdd1, k2eAgMnPc5d1, klgNnSd, k1gNnSc4, k1gNnSc5, k1gNnSc6, k1gNnSc3, k1gNnSc2, k1gNnPc2, klgNnPd, k1gNnPc4, k1gNnPc5 klgNnSd je k5eAalmlp3nS, k3p3gMnPc4, k3p3glnPc4, k3p3gNnSc4, k3p3gNnPc4, k3p3gFnPc4, kO k5eAalmlp3nS pro k7c4 k7c4 správny k2eAgMnSc1d1, k2eAgMnSc5d1, k2eAglnSc1d1, k2eAglnSc4d1, k2eAglnSc5d1, ... (+18) k2eAglnSc4d1 růst k5eAalmF, klglnSd, k1glnSc4 k1glnSc4 důležité k2eAgMnPc4d1, k2eAglnPc1d1, k2eAglnPc4d1, k2eAglnPc5d1, k2eAgFnSc2d1, k2eAgFnSc3d1, k2eAgFnSc6d1, k2eAgFnPc1d1, k2eAgFnPc4d1, k2eAgFnPc5d1, k2eAgNnSc1d1, k2eAgNnSc4d1, k2eAgNnSc5d1, ... (+5) k2eAgNnSc1d1 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 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. arg waxp(e\f) p{é)p{f\e) arg max ,). p(f) arg maxp(e)p(f\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 * Pim(í go home) > puwO 9° 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 Vw.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 86 700 33447 (38,6%) bigram 1 948935 1 132 844 (58,1 %) trigram 8 092 798 6 022 286 (74,4%) 4-gram 15 303847 13 081 621 (85,5%) 5-gram 19882175 18 324 577 (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 Matice zarovnání slov CD CO CD O) michael assumes that he will stay in the house Problémy se zarovnáním slov .C 03 W .o -_q c co O) john kicked the bucket C SZ i- -C .C O <ľ) o .o 5 Z 'c john does not live here S 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 hat John spass am spiel / X ■ of course John has 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 responsibility ef airport safety reference: Israeli officials are responsible for airport security ► přesnost correct 3 = 5Q% pokrytí output-length 6 correct 3 43% ► f-score reference-length 7 precision x recall .5 x .43 {precision + recall)/2 (.5 + .43)/2 46% Pokrytí a přesnost - nedostatky system a: Israeli officials responsibility 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, fP"^M (TTprecision^ l V reference-length J 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 11 Israeli 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, NEVA ► WAFT ► Word Accuracy for Translation ► editační vzdálenost mezi car \ ► TER ► WAFT^I-,^ ► Translation Edit Rate ► nejmenší počet kroků (smazání, přidání, prohození, změna) ^ j^pj počet editací ~ prům. počet ref. slov ► METEOR ► uvažuje synonyma (WordNet) a ► morfologické varianty slov Hodnocení hodnotících metrik Korelace automatického hodnocení s manuálním. Human Judgments Hodnocení překladu podle jazykových párů larga -=-;.: 3A - ■» hu u, wtt p. ^i :1 ZH J -j.Z -e e É e : j :■ -. i ::; e- e- EE e :í : E7 3. e e.e -e - ee e :l e :: :■ iE i 44.7 \<.<\ b n EL e J 3E.7 EE - ee e E4 ľ- -e e 3i i 26.7 -3- 33 0 -e ľ 3E e ZSL1 3i.E 443 Ei . iľ e ee e Ei : 34J. \\ e 3E := e U e J e: - -e : e i e 47.1 le i le :■ e e - L7 e 42.7 17 e e i e :š e ZV i. Ei l 44.1 Ei7 lEi e. i i- l ce E3.i i3 e ^ -e e- e- e iE e Ei 7 e l i 41i 27* 44J E- i Eľ e ZE e -: ľ ee 3 iľ 7 e e ľ iE e- 413 i3 E ZfA ľ T e 3E 7 44.1 Eľ r J Ei.e 47.5 37 e e. e i. e 3i 3 -e =■ 3E _ e 3 e 3. . iE- ľ Ei e iľ - ee ŕ e e i ee 3 47. Z e. ľ = ľ EEjí =7.7 — ľ J ľ- :■ 35 ľ 3E i -e e 3E 7 -e =■ 3E i e 3 e 3E e iE- e Z4.2 ľ3 ľ E7 3 e e _ ee e i= E e:- j El . 4Z.7 = 7: 444- ee - J 3i.i 3E .ľ ľ . e l-v 311.7 3E e E i.i 3i.=■ iE e e e.e ľ7 e ee l e. ~ e e.E i= J :_ :i; Li r Z73 5i l ž" e le.: 4ÍL4 J ZJ.l e e - EU e zra = i :■ e i e 13 : -. e EL j e: e LE- j ž j e- ELE Eľ e F1 -e e a i ee j e i. j e 7 e 37 3 EEL7 e- e J 3E i 272 ee e Ei i E 3.i Ll-A -j e Z7J 3E.: 37 e 3E 3 E7 E = í E— :■ i- J «1 :=: -7- -I i i-j i Ii.7 i j -3 J lí : 1: . 1= e e. e Li.e :. e e:.7 e. ľ -e i = e _ e: e --. e - j —E j 3i.7 äís ■j j ee i 3i.i Z4.1 3E- e 3E - e i 7 ^ ee ľ 3E e e l e ľE.: EU 3E e 34JZ 3i 7 3ľ e- 3E.3 Ei ľ rr e. j El . — e ee e -• e- -3 r le e Z" H 73.7 : ĺ t M ĺ J le - e l r l^ r ::■: Ei ĺ :e : ee. e el : 34.7 ^- e lt i- e 37 e ee e E7 i ee e 3E ľ 31.1 e-.3 e 3.i Eii 3E ľ ee e J -i . 33 3 ee- . e l e JtUG 3E.e E. e- Ei e e: e :\ :-i le . Eľ j et e ee- ľ- 3E 7 Lľ- e e-.i el - e : e le e ee e ee - J le e -. : Eii ee e e. í ee e E7 . ee j WTT 72j EL l 17jz e 7 E e e e H17 43.7 le e 3i 5 - l - 33-i 43.7 Ei 3 ee 3 J ii i Z7J. iľ e ee e Eľ e ii i i. e hl ľ = e Ie e -e e E7 j -ľ- - Eľ e 4BL7 37 ľ 3E e iE - 3i.e — ľ 3E e 31.7 33.i J E3i 47.7 ee i Ei : Ei e i= e fl e;- e e. ľ 4ÍĽZ — 3 43 J. e- 3 -e 3 3E- 3 3E i Ámň 3^ ľ -e 3 E e 3 Ei e 37 e — e / 44.1 EE 3 ee 3 e e e i3 l pt e j r e. - -i e ee - e -i 3 e"i E 3E-- 3E 3 ľ e 3 3E e ľ3 =: 3E i e l i 3i e iE e Ei ľ J ee i = 3 . 544 i= E ro e-?.: e: . ee : Eľ =• -j e e:.e- - ľ- E ľ: l -e : l: i — = iE - le.e := ■ i Ei i i= : J = .: Eii e = .i e < EO e E3 E ee - 43.1 41 .g e e.e 445,7. 3E e 3E - e e - 27.4 413 EE i ee - 3= ľ 44.4 e e i iE e Eľ e J i3 e i. E e. e-l 0 EE-l ZJ3 i= : -l.e ESU 47.0 e-: LE e e e l Li 7 422! =-; 37J! e 3 :■ í: e ee l 44.1 e: e ŽE e iL 7 :\ ľ = ľ 3E.E Eľ- e -e e ee e -e e Ei e e e e 33 ľ 4Z.Q 3E 3 e: i 3= 7 iľ e E3 3 ii3 iZ.7 e. E ee ľ J