Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Q Úvod do statistického strojového překladu 0 Jazykové modely Q Překladové modely Q Dekódování Úvod Jazykové modely »000000000000000000 000000000000000000000 Překladové modely Dekódování 00000000000000000000000000000 00000 Úvod Úvod do SMT • pravidlové systémy motivovány lingvistikou • SMT inspirován teorií informace a statistikou • v současnosti mnoho společností se zaměřením na SMT: Google, IBM, Microsoft, Language Weaver (2002) a 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 Úvod Jazykové modely 0*00000000000000000 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Jazykové modely oo»oooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Nástroje SMT • GIZA++: trénování IBM modelů, zarovnávání na úrovni slov (word alignment pomocí HMM) • SRILM: trénování jazykových modelů • IRST: trénování velkých jazykových modelů • Moses: frázový dekodér, trénování modelů • Pharaoh: předchůdce Mosese • Thot: trénování frázových modelů • SAMT: tree-based modely Úvod Jazykové modely 000*000000000000000 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Data pro SMT - (paralelní) korpusy • Linguistics Data Consorcium (LDC): paralelní korpusy pro páry arabština-angličtina, čínština-angličtina atd. Gigaword korpus (angličtina, 7 mld slov) • Europarl: kolekce textů Evropského parlamentu (11 jazyků, 40 M slov) • OPUS: paralelní texty různého původu (lokalizace software) • Acquis Communautaire: právní dokumenty Evropské únie (20 jazyků) Úvod Jazykové modely oooo»oooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Pravidelné události v oblasti SMT, soutěže Většinou roční vyhodnocování kvality SMT. Tvorba testovacích sad, manuální vyhodnocování dat, referenční systémy. • NIST: National Institute of Standards and Technology; nejstarší, prestižní; hodnocení překladu arabštiny, čínštiny • IWSLT: mezinárodní workshop překladu mluveného jazyka; překlad řeči; asijské jazyky • WMT: Workshop on SMT; překlady mezi evropskými jazyky Úvod Jazykové modely Překladové modely Dekódování ooooo»ooooooooooooo ooooooooooooooooooooo Základy SMT Slova • pro SMT v drtivé většině případů základní jednotka = slovo • v mluvené řeči slova neoddělujeme: jak je od sebe oddělíme? • SMT systémy provádí de-tokenizaci • překlad samotný je většinou s lowercase textem • jaká slova má angličtina ->• jaká slova jsou v anglických korpusech • the tvoří 7% anglického textu • 10 nejčastějších slov (tokenů) tvoří 30% textu (!) • Zipfůvzákon: r rank (pořadí ve frekvenčním seznamu slov), f = frekvence výskytu slova, c = konstanta; platí r x f = c • překlepy, čísla, vlastní jména, názvy a cizí slova Úvod Jazykové modely Překladové modely Dekódování oooooo»oooooooooooo ooooooooooooooooooooo Základy SMT Zipfův zákon 1 10 100 1000 10000 100000 1e+06 Ranking Úvod Jazykové modely ooooooo»ooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy SMT Věty • syntaktická struktura se v jazycích liší • vkládání funkčních slov, která jsou typická pro daný jazyk (the, interpunkce) • přerovnávání: er wird mít uns gehen he willgo with us • některé jevy nelze přeložit na úrovni věty: anafory • úroveň celého dokumentu: téma (topič) může pomoci při volbě vhodného překladového ekvivalentu • v textu o jeskynních živočiších zřejmě nebude překládat Ďařjako pálka Úvod Jazykové modely oooooooo»oooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy SMT Paralelní korpusy a základní datový zdroj pro SMT • volně dostupné jsou řádově 10 a 100 miliónů slov veliké • je možné stáhnout paralelní texty z internetu • vícejazyčné stránky (BBC, Wikipedie) • problém se zarovnáním dokumentů, odstavců,... • 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) Úvod Jazykové modely Překladové modely Dekódování ooooooooo»ooooooooo ooooooooooooooooooooo Základy SMT Zarovnávání vět • věty si neodpovídají 1:1 • některé jazyky explicitně nenaznačují hranice vět (thajština) • It is small, but cozy. - Es is klein. Aber es ist gemütlich. • pro věty e^, ■ ■ ■ ene a ŕ,, • • • fn, a hledáme páry s-\,...sn • si = ({4tart-r(;)) " " " 4nd-ř(;)}) {estart-e(;)> " " " eend-e(;)}) P typ zarovnání 0.98 0.0099 0.089 0.011 1- 1 1 -0 nebo 0-1 2- 1 nebo 1-2 2-2 Úvod Jazykové modely oooooooooo#oooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT Pravděpodobnostní rozložení • graf hodnot pravděpodobnosti pro elementární jevy náhodné veličiny • rovnoměrné: hod kostkou, mincí (diskrétní veličina) • binomické: vícenásobný hod • normální, Gaussovo: spojité, dobře aproximuje ostatní rozložení; zahrnuje rozptyl p) n-k Úvod Jazykové modely ooooooooooo»ooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Jazykové modely 000000000000*000000 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT Statistika I • náhodná proměnná, pravděpodobnostní funkce, ... • máme data, chceme spočítat rozložení, které nejlépe tato data vystihuje • zákon velkých čísel: čím víc máme dat, tím lépe jsme schopni odhadnout pravděpodobnostní rozložení • např.: hod falešnou kostkou; výpočet -k • nezávislé proměnné: Vx, y : p(x, y) = p(x).p(y) • spojená (joint) pravděpodobnost: hod mincí a kostkou • podmíněná pravděpodobnost: p(y|x) = pro nez. proměnné platí: p(y|x) = p(y) Úvod Jazykové modely 0000000000000*00000 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT Podmíněná pravděpodobnost Úvod Jazykové modely 00000000000000*0000 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT Shannonova hra Pravděpodobnostní rozložení pro následující znak v textu se liší v závislosti na předchozích znacích. Doplňujeme postupně znaky (malá abeceda a mezera). Některé znaky nesou více informace (jsou uhádnuty později). Úvod Jazykové modely Překladové modely Dekódování 000000000000000*000 ooooooooooooooooooooo Základy pravděpodobnosti pro SMT Bayesovo pravidlo , . , p(yx).p(x) pí*i/) = / r p(y) • příklad s kostkou • p(x) - prior • p(y|x) - posterior Úvod Jazykové modely 0000000000000000*00 ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT Statistika II • střední hodnota (diskrétní): EX = J2isí-Pí • rozptyl: a2 = [*, ~ E(*)]2P/ • očekávaná hodnota: E[X] = Y,Xex X-P(x) Úvod Jazykové modely Překladové modely Dekódování 00000000000000000*0 ooooooooooooooooooooo Základy pravděpodobnosti pro SMT 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 maxp(e\f) p{é)p{f\e) arg max ,). p(f) arg maxp(e)p(f\e). Úvod Jazykové modely oooooooooooooooooo* ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Základy pravděpodobnosti pro SMT SMT - komponenty noisy channel principu • jazykový model: • jak zjistit p(e) pro libovolný řetěz e o čím víc vypadá e správně utvořené, tím vyší je p(e) • problém: co přiřadit řetězci, který nebyl v trénovacích datech? • překladový model: • pro e a f vypočítej p(f\e) • čím víc vypadá e jako správný překlad f, tím vyšší p • dekódovací algoritmus • na základě předchozího najdi pro větu f nejlepší překlad e • co nejrychleji, za použití co nejmenší paměti Úvod Jazykové modely Překladové modely Dekódování OOOOOOOOOOOOOOOOOOO »00000000000000000000 ooooooooooooooooooooooooooooo ooooo Úvod Q Úvod do statistického strojového překladu 0 Jazykové modely Q Překladové modely Q Dekódování Úvod Jazykové modely ooooooooooooooooooo o»ooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Jazykové modely Noam Chomsky, 1969 But it must be recognized that the notion "probability of a sentence" is an entirely useless one, under any known interpretation of this term. Fred Jelinek, 1988 Anytime a linguist leaves the group the recognition rate goes up. Jak pravděpodobné je pronesení české věty s? Ke snídani jsem měl celozrnný ... Úvod Jazykové modely ooooooooooooooooooo o»ooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Jazykové modely Noam Chomsky, 1969 But it must be recognized that the notion "probability of a sentence" is an entirely useless one, under any known interpretation of this term. Fred Jelinek, 1988 Anytime a linguist leaves the group the recognition rate goes up-___ Jak pravděpodobné je pronesení české věty s? Ke snídani jsem měl celozrnný ... chléb > pečivo > zákusek > mléko > babičku Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO 00*000000000000000000 Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod Jazykové modely • zajímá nás určování pravděpodobnosti následujícího slova • jazykový model je pravděpodobnostní rozložení nad všemi možnými sekvencemi slov daného jazyka Pravděpodobnost sekvencí slov P/.M(včera jsem jel do Brna) Puw(včera jel do Brna jsem) Puw(jel jsem včera do Brna) Použijeme • podmíněnou pravděpodobnost p(x\ y) a • joint probability (společná pravděpodobnost) Úvod Jazykové modely ooooooooooooooooooo ooo»ooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Úvod 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) > pLM(\ go house) Úvod Jazykové modely ooooooooooooooooooo oooo»oooooooooooooooo N-gramové modely N-gramové modely Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo • n-gram je nejdůležitější nástroj ve zpracování řeči a jazyka • využití statistického pozorování dat • dvojí využití ve strojovém překladu: • po slovech I go je častější home než house apod. • I go to home vs. I go home • generování jazyka 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. , i mpty. J Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO 00000*000000000000000 Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo N-gramové modely N-gramové modely - naivní přístup 1/1/ = w-\, w2, • • • ,wn Jak vypočítat p{W)7 Spočítáme výskyty všech 1/1/ v datech a normalizujeme je velikostí dat. Pro většinu velkých 1/1/ však nebudeme mít v datech ani jeden výskyt. Úkolem je zobecnit pozorované vlastnosti trénovacích dat, která jsou většinou řídká (sparse data). „, ,....... ■■ , ' \ ke snídani jsem měl celozrnný chléb P(chleb|ke snídani jsem mel celozrnný) = ke snídani jsem měl celozrnný Úvod Jazykové modely ooooooooooooooooooo oooooo»oooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo N-gramové modely Markovův řetězec a Markovův předpoklad p{W), kde W je posloupnost slov, budeme modelovat postupně, slovo po slovu, užitím tzv. pravidla řetězu: p(Wi,W2,...Wn) = p(wi )p( w2\wi )p{w3\wi ,w2)... p{wn\Wi... Wn_i ) Jelikož nemáme k dispozici pravděpodobnosti pro dlouhé řetězce slov, omezíme historii na m slov použitím Markovova předpokladu: p{wn\w^ W2, . . . Wn-l) ^ p{wn\wn-m, ■ ■ ■ Wn_2, Wn_-|) Číslo m nazýváme řádem odpovídajícího modelu. Nejčastěji se používají trigramové modely. Úvod Jazykové modely ooooooooooooooooooo ooooooo#ooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo N-gramové modely Výpočet, odhad pravděpodobností LM Trigramový model používá pro určení pravděpodobnosti slova dvě slova předcházející. Použitím tzv. odhadu maximální věrohodnosti (maximum likelihood estimation): p{w3\w:, w2) county, w2,w3) 52wcount(wi,w2,w) trigram: (the, green, w) (1748) w počet p{w) paper 801 0.458 group 640 0.367 light 110 0.063 party 27 0.015 ecu 21 0.012 Úvod Jazykové modely ooooooooooooooooooo oooooooo»oooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo N-gramové modely 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: extrinsic a 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. Úvod Jazykové modely ooooooooooooooooooo ooooooooo#ooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo N-gramové modely Cross-entropy (křížová entropie) H{Plm) = ~- l0gP/Jw(Wi, wz, ...wn) 1 n = ~p 5ľlog Plm(wí\w:,... ) Křížová entropie je průměrná hodnota záporných logaritmů pravděpodobností slov v testovacím textu. Odpovídá míře nejistoty pravděpodobnostního rozložení (zde LM). Čím menší, tím lepší. Dobrý LM by měl dosahovat entropie blízké skutečné entropii jazyka. Tu nelze změřit, ale existují relativně spolehlivé odhady (např. Shannonova hádači hra). Pro angličtinu je entropie na znak rovna cca 1.3 bitu. Úvod Jazykové modely ooooooooooooooooooo oooooooooo»oooooooooo N-gramové modely Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Perplexita pp _ 2h(Pí-m) PP{W) = pLM{wAw2w3... wNy* Perplexita je jednoduchá transformace křížové entropie. Dobrý model by neměl plýtvat p na nepravděpodobné jevy a naopak. Čím nižší entropie, tím lépe čím nižší perplexita, tím lépe. Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO OOOOOOOOOOOÄOOOOOOOOO Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů 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). Úvod Jazykové modely ooooooooooooooooooo oooooooooooo»oooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Add-one vyhlazování (Lapiace) Maximum likelihood estimation přiřazuje pravděpodobnost na základě vzorce c Add-one vyhlazování používá upravený vzorec c+1 P =- n+v kde i/je počet všech možných n-gramů. To je však velmi nepřesné, neboť všech možných kombinací je většinou řádově víc než ve skutečnosti (Europarl korpus má 86,700 tokenů, tedy víc jak 7,5 mld možných bigramů. Ve skutečnosti má korpus 30 mil. slov, tedy maximálně 30 mil. bigramů.) Vyhlazování nadhodnocuje neviděné n-gramy. Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO 0000000000000*0000000 Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Add-a vyhlazování Nebudeme přidávat 1, ale koeficient a. Ten lze odhadnout tak, aby add-a vyhlazování bylo spravedlivější. C + a p =- n + av a můžeme experimentálně zjistit: zvolit více různých a hledat pomocí perplexity nejlepší z nich. Typicky bude spíše malé (O.OOOX). Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO 00000000000000*000000 Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Deleted estimation Neviděné n-gramy můžeme vytvořit uměle tak, že použijeme druhý korpus, případně část trénovacího korpusu. N-gramy obsažené v jednom a ne v druhém nám pomohou odhadnout množství neviděných n-gramů obecně. Např. bigramy, které se nevyskytují v trénovacím korpusu, ale vyskytují se v druhém korpusu miliónkrát (a všech možných bigramů je cca 7,5 mld), se vyskytnou cca 106 ———ô = 0.00013x 7.5 x 109 Úvod Jazykové modely Překladové modely Dekódování ooooooooooooooooooo ooooooooooooooo«ooooo ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Good-Turing vyhlazování Potřebujeme upravit počet výskytů v korpusu tak, aby odpovídal obecnému výskytu v textu. Použijeme frekvenci frekvencí: počet různých n-gramů, které se vyskytují n-krát. Použijeme četnost hapax legomena pro odhad četnostní nikdy neviděných dat. r* = (r+1)^±l Speciálně pro n-gramy, které nejsou v korpusu máme r* = (0 + 1)^ = 0.00015 ty kde ty = 1.1 x 106 a ty = 7.5 x 109 (Europarl korpus). Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOO0OOOO Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Ukázka Good-Turing vyhlazování (Europarl) r FF r* 0 7 514 941 065 0,00015 1 1 132 844 0,46539 2 263611 1,40679 3 123615 2.38767 4 73 788 3,33753 5 49 254 4,36967 6 35 869 5,32929 8 21 693 7,43798 10 14880 9,31304 20 4 546 19.54487 Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooo»ooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Srovnání metod vyhlazování (Europarl) metoda perplexita add-one 382,2 add-a 113,2 deleted est. 113,4 Good-Turing 112,9 Úvod Jazykové modely OOOOOOOOOOOOOOOOOOO 000000000000000000*00 Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Vyhlazování jazykových modelů Interpolace a back-off 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 Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooo»o Vyhlazování jazykových modelů Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Interpolace Použijeme interpolaci: Pi{w3\w-\W2) = A-ip(w3) x \2p{w3\w2) x \3p(w3\w-\w2) Pokud máme hodně dat, můžeme věřit modelům vyšších řádů a přiřadit odpovídajícím pravděpodobnostem větší váhu. Pi je pravděpodobnostní rozložení, proto musí platit: VAn : 0 < Xn < 1 n Úvod Jazykové modely ooooooooooooooooooo oooooooooooooooooooo* Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo 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ů. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Q Úvod do statistického strojového překladu Q Jazykové modely Q Překladové modely Q Dekódování Úvod Jazykové modely Překladové modely Dekódování OOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOO »0000000000000000000000000000 ooooo Lexikální překlad Lexikální překlad Standardní slovník neobsahuje informace o tom, jak často se překládá dané slovo na své různé překladové ekvivalenty. key ->• klíč, tónina, klávesa Jak často jsou zastoupeny jednotlivé překlady v překladech? key klíč (0.7), tónina (0.18), klávesa (0.12) Potřebujeme lexikální překladové pravděpodobnostní rozložení pf s vlastností £p'(e) = 1 e Ve : O < pf{e) < 1 Pklíč(key)?Pmrkev(carrot) Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 0*000000000000000000000000000 ooooo Lexikální překlad Zarovnání slov, zarovnávací funkce Překlady si často neodpovídají v počtu slov ani ve slovosledu. Zavádí se alignment function kde y je pozice odpovídajícího slovo v cílové větě (čeština), / je pozice ve zdrojové větě (angličtina). i: 1 2 3 4 5 the castle is very old ten hrad je velmi starý j: 1 2 3 4 5 a je funkce, tedy pro každé slovo we z cílové věty existuje právě jedno slovo wf ze zdrojové věty. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování oo»oooooooooooooooooooooooooo ooooo Lexikální překlad Zarovnání slov - další případy • jiný slovosled: it was written here bylo to zde napsané a: 1 -^2,2^ 1,3->4,4->3 • jiný počet slov: jsem maličký i am very small a: 1 -> 1,2-> 1,3->2,4->2 • slova bez překladových ekvivalentů: have you got it ? máš to ? a:1->1,2->4,3->5 • opačný případ, přidáme nové slovo NULL, pozice 0: NULL laugh smát se a: 1 -> 1,2->0 Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 000*0000000000000000000000000 ooooo IBM modely IBM model 1 Nemůžeme hledat pf pro jednotlivé věty. Překlad rozložíme do menších kroků, budeme používat pf pro slova. Tomuto přístupu se říká generative modeling. Překladový model IBM-1 je definován jako kde e = (e-i,... e/J je cílová věta, f = (ři,... ftf) zdrojová věta, le je délka cílové věty, lf délka zdrojové věty, e je normalizující konstanta, aby byl výsledný součin pravděpodobnostní rozložení. (If + 1 )/e je počet všech možných zarovnání mezi e a f, přičemž k lf přičítáme 1 kvůli speciálnímu slovu NULL, ř je pravděpodobnostní překladová funkce. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 0000*000000000000000000000000 ooooo IBM modely 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. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 00000*00000000000000000000000 ooooo IBM modely EM algoritmus O inicializuj model (typicky uniformní p. rozložení) O aplikuj model na data (krok expectation) hledáme p(a| e, O = ^? kde p(e\f) = EaP(e,a\f) Q uprav model podle dat (krok maximization) upravíme počty zarovnání slova we na wf (funkce c) pomocí předchozího c{we\Wf, e, f) = EaP(ale> f) EjLi á(e, ej)5{f, fa[j)) kde S(x, y) = 1 \f) Pro každé zdrojové slovo f rozložení n říká, na kolik cílových slovo se obvykle f přeloží. n(0|a) = 0.999 n(1|king) = 0.997 n(2|steep) = 0.25 Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování OOOOOOOOOOOOOOÄOOOOOOOOOOOOOO ooooo IBM modely Vložení tokenu NULL Pokud chceme správně překládat do cílového jazyka, který používá slova, jež nemají ve zdrojovém jazyce překladové ekvivalenty, musíme řešit vkládání pomocného tokenu NULL. Nepoužívá se n(x\NULL), protože vložení NULL záleží na délce věty. Přidáme tedy další krok vložení NULL do procesu překladu. Používají se p-i a p0 = 1 - p-i, kde p-i znamená pravděpodobnost vložení tokenu NULL za libovolné slovo ve větě. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooo»ooooooooooooo ooooo IBM modely IBM-3 1 2 3 4 5 6 ich gehe ja nicht zum haus i i VA \ ich gehe nicht zum zum haus A \ \ \ \ \ ich null gehe nicht zum zum haus 1 l 1 1 1 1 1 I do go not to the house 11X111 I do not go to the house 1 2 3 4 5 6 7 fertility step NULL insertion step lexical translation step distortion step Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 0000000000000000*000000000000 ooooo IBM modely IBM-3-distortion Poslední krok je téměř shodný s 2. krokem překladového procesu IBM-2 a je modelován tzv. distortion probability distribution: d(j\ÍJe,lf) která modeluje pozice v opačném pořadí: pro zdrojové slovo na pozici / modeluje pozici j cílového slova. Proces překladu z předchozího obrázku se může drobně lišit (viz další obrázek). Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování OOOOOOOOOOOOOOOOO0OOOOOOOOOOO ooooo IBM modely IBM-3 1 2 3 4 5 6 ich gehe ja nicht zum haus l 1 VA \ ich gehe nicht zum zum haus /♦Ulli ich null gehe nicht zum zum haus 1 i i i 1 1 1 I do go not the to house Ii X X 1 I do not go to the house 1 2 3 4 5 6 7 fertility step NULL insertion step lexical translation step distortion step Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 000000000000000000*0000000000 ooooo IBM modely IBM-4, IBM-5 IBM-4 Problém distorze tkví v řídkých datech pro dlouhé věty. IBM-4 zavádí tzv. relativní distorzi, kde změny pozic slov závisí na předcházejících slovech. Vychází z předpokladu, že se překládá po frázích, které se přesunují vcelku, případně že některé přesuny jsou více časté (angličtina: ADJ SUB, francouzština SUB ADJ apod.). IBM-5 Tento model řeší další nedostatky předchozích modelů. Např. hlídá, aby se dvě různá zdrojová slova nedostala na jednu pozici v cílové větě atd. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 000000000000000000000*0000000 ooooo Frázový překladový model 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 zzx: of course john has spass am fun with the spiel I 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))). Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování oooooooooooooooooooooo»oooooo ooooo Frázový překladový model 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. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování 00000000000000000000000*00000 ooooo Frázový překladový model Phrase-based model - vzorec Překladová pravděpodobnost p(f\é) se rozloží na fráze / pQ[\~e\) = n^/lě/Mstart,- - end,---, - 1) /=1 Věta f se rozloží na / frází !■„ všechna dělení jsou stejně pravděpodobná. Funkce 0 je překladová pravděpodobnost pro fráze. Funkce d je přerovnávací model založený na vzdálenosti (distance-based reordering model), modelujeme pomocí předchozí fráze, start, je pozice prvního slova ve frázi věty f, které se překládá na /tou frázi věty e. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování oooooooooooooooooooooooo»oooo ooooo Frázový překladový model Distance-based reordering model Preferuje se minimální přesun frází. Čím větší přesun (měří se na straně výchozího jazyka), tím dražší tato operace je. d=-3 Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooo#ooo ooooo Frázový překladový model Budování překladové tabulky frází Použijeme zarovnání slov (získané pomocí EM algoritmu pro IBM-1) a pak hledáme konzistentní fráze. Fráze 1 a e jsou konzistentní se zarovnáním A, pokud všechna slova fi,...fnve frázi 1, která mají zarovnání v A, jsou zarovnaná se slovy e-i,... en ve frázi e a naopak. 33 33 konzistentní nekonzistentní konzistentní Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování oooooooooooooooooooooooooo»oo ooooo Frázový překladový model Extrahování frází Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooo#o ooooo Frázový překladový model Extrahované fráze michael michael assumes geht davon aus / geht davon aus , that dass /, dass he er will stay bleibt in the im house haus michael assumes michael geht davon aus / michael geht davon aus , assumes that geht davon aus , dass assumes that he geht davon aus , dass er that he dass er /, dass er in the house im haus michael assumes that michael geht davon aus , dass Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Frázový překladový model Překladové modely Dekódování 0000000000000000000000000000» ooooo Odhad pravděpodobnosti frází Odhad pravděpodobnosti frází count(ě,7) W|ě) = EíCount(ě,í) Model statistického překladu založený na frázích / _ |e| e* = argmaxe Jj0(í-|ě,-) d{start, - end,^ -1) JJp/./w(e/|ei...e/_i) /=i /=i Vážený frázový model / _ |e| e* = argmaxe Jj0(í-|ě/)A* d{start;-endi-^)Xd JJp/./w(e/|ei...e/-i);> Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooooo Q Úvod do statistického strojového překladu Q Jazykové modely Q Překladové modely Q Dekódování Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování OOOOOOOOOOOOOOOOOOOOOOOOOOOOO «0000 Dekódování Dekódování Máme jazykový model pLM a překladový model p(f\é). Potřebujeme vyhledat z exponenciálního množství všech překladů ten, kterému modely přiřazují nejvyšší pravděpodobnost. Používá se heuristické prohledávání. Nemáme tedy garantováno, že nalezneme nejpravděpodobnější překlad. Chyby překladu jsou způsobeny 1) chybou v prohledávání, kdy není nalezen nejlepší překlad v celém prohledávacím prostoru a 2) chybou v modelech, kdy i nejlepší překlad podle pravděpodobnostních funkcí není ten správný. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo o«ooo Dekódování Překlad věty po frázích er geht ja nicht er geht ja nicht nach hause nach hause go horne V každém kroku překladu počítáme předběžné hodnoty pravděpodobností z překladového modelu, přerovnávacího modelu a jazykového modelu. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo oo»oo Dekódování Prohledávací prostor překladových hypotéz er geht ja nicht nach hause f f yes ") f not ) f atter _) is j C do not j Q to j it goes he goes does not j ( according to f chamběi ) ( at home not ) ( _ he will be j f is not j f under house following is after all j f not after does isnot are not Rozšiřujeme hypotézy v exponenciálním prostoru všech možných překladů. Různými metodami se snažíme prostor zmenšit. Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo ooo»o Dekódování Budování hypotéz, beam search er geht ja nicht nach hause ■ MIM n_LL 1 yes he ■ III r ■ M ■ goes home ■-1 1 1 1 1 l~ ■ M 1 —► are does not r go —H home to Úvod Jazykové modely ooooooooooooooooooo ooooooooooooooooooooo Překladové modely Dekódování ooooooooooooooooooooooooooooo oooo* Dekódování Beam search Beam search používá tzv. breadth-first prohledávání. Na každé úrovni prohledávacího stromu generuje všechny následovníky stavů (uzlů) nadané úrovni, uspořádávaje podle heuristik. Ukládá ovšem pouze omezený počet nejlepších stavů na každé úrovni (beam width). Pouze tyto stavy jsou prozkoumávány dále. Čím větší beam width, tím méně stavů je prořezáno. Při nekonečné šířce jde o breadth-first prohledávání. Šířka určuje spotřebu paměti. Nejlepší konečný stav ovšem nemusí být nalezen, může být v nějaké fázi prořezán.