Úvod ooooooooooooooooooo Jazykové modely oooooooooooooc O Úvod do statistického strojového překladu 0 Jazykové modely Uvod »000000000000000000 Úvod Úvod do SMT Jazykové modely 0000000000000c • 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 o«ooooooooooooooooo Úvod Schéma SMT Spanish/English Bilingual Text CEnglish S. Text y Statistical Analysis Statistica 1 Analysi Spanish - Translation Model Broken , English Language Model Decoding Algorithm argmax P(e)*p(s|e) Úvod oo»oooooooooooooooo Jazykové Ú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 000*000000000000000 Jazykové modely oooooooooooooc Ú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 oooo»oooooooooooooo Jazykové modely oooooooooooooc Ú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 ooooo»ooooooooooooo oooooooooooooc 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 oooooo»oooooooooooo Základy SMT Zipfův zákon 1 10 100 1000 10000 100000 1e+ Ranking Úvod Jazykové modely oooooooooooooc ooooooo»ooooooooooo 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 oooooooo»oooooooooo Jazykové modely oooooooooooooc 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 ooooooooo»ooooooooo Jazykové modely oooooooooooooc 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 oooooooooo»oooooooo Jazykové modely oooooooooooooc 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 ooooooooooo»ooooooo Jazykové modely oooooooooooooc Úvod 000000000000*000000 Jazykové modely oooooooooooooc 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 ooooooooooooo»ooooo Základy pravděpodobnosti pro SMT Podmíněná pravděpodobnost Úvod 00000000000000*0000 Jazykové modely oooooooooooooc 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). • příklad s kostkou • p(x) - prior • p{y\x) - posterior Úvod 0000000000000000*00 Základy pravděpodobnosti pro SMT Statistika II • střední hodnota (diskrétní): EX = • rozptyl: a2 = [*, ~ E(*)]2P/ • očekávaná hodnota: E[X] = Y,Xe> Úvod Jazykové modely 00000000000000000*0 oooooooooooooc 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 000000000000000000» Jazykové modely oooooooooooooc 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 ooooooooooooooooooo Úvod O Úvod do statistického strojového 0 Jazykové modely Uvod ooooooooooooooooooo Úvod Jazykové modely Jazykové modely o«oooooooooooc 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ý ... Uvod ooooooooooooooooooo Úvod Jazykové modely Jazykové modely o«oooooooooooc 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 ooooooooooooooooooo Jazykové modely oo»ooooooooooc Ú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/jví(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 ooooooooooooooooooo Jazykové modely ooo«oooooooooc Ú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) Uvod ooooooooooooooooooo N-gramové modely N-gramové modely Jazykové modely oooo»ooooooooc • 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 ooooooooooooooooooo Jazykové modely ooooo»oooooooc 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 oooooo»ooooooc ooooooooooooooooooo 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 ooooooooooooooooooo Jazykové modely ooooooo»oooooc 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 ooooooooooooooooooo Jazykové modely oooooooo»ooooc 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 ooooooooooooooooooo Jazykové modely ooooooooo»oooc N-gramové modely Cross-entropy (křížová entropie) H{Plm) = ~- !0gPlM(^1, 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. Uvod ooooooooooooooooooo N-gramové modely Perplexita Jazykové modely oooooooooo»ooc p p — 2h(Plm) PP{W) = pLM(wAw2w3... wN) n 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 ooooooooooooooooooo Jazykové modely ooooooooooo»oc 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 ooooooooooooooooooo Jazykové modely oooooooooooo»c Vyhlazování jazykových modelů Add-one vyhlazování (Laplace) 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 v\e 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 ooooooooooooooooooo Jazykové modely 0000000000000« 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 oooooooooooooc ooooooooooooooooooo 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 ooooooooooooooooooo Jazykové modely oooooooooooooc 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. Speciálně pro n-gramy, které nejsou v korpusu máme r* — '0 — (0 + 1)—!- = 0.00015 kde N, = 1.1 x 106 a N0 = 7.5 x 109 (Europarl korpus). Úvod ooooooooooooooooooo Jazykové modely oooooooooooooc Vyhlazování jazykových modelů Ukázka Good-Turing vyhlazování (Europarl) r FF ŕ 0 7 514 941 065 0,00015 1 1 132 844 0,46539 2 263 611 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 14 880 9,31304 20 4 546 19.54487 Úvod ooooooooooooooooooo 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 ooooooooooooooooooo Jazykové modely oooooooooooooc 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 ooooooooooooooooooo Jazykové modely oooooooooooooc Vyhlazování jazykových modelů 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 ooooooooooooooooooo Závěr 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ů.