Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
.IN009 - Strojový překlad
Pravidlový strojový překlad Vít Baisa
jaro 2012
21. března 2013
Rozdělení systémů
Úvod
O Úvod
£ Tokenizace
Q Morfologická rovina
Q Lexikální rovina
Úvod
o«oooooo
Rozdělení systémů
Úvod
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
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 - KBMT
• systémy využívající znalosti o jazyce
• obecnější pojem
Úvod
oo»ooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
Rozdělení systémů
Knowledge-based MT
• je důležité správně analyzovat kompletní význam zdrojového textu
• ne ovšem totální význam (všechny konotace, explicitní a implicitní informace)
• dříve spíše význam systému využívajícího interlinguu
• zde jako ekvivalent pravidlového systému
Úvod Tokenizace Morfologická rovina
ooo»oooo ooo ooooooooooooooooo
Rozdělení systémů
Rozdělení systémů KBMT
• přímý překlad
• direct translation
• nejstarší, 1 krok - transfer
• Georgetown experiment, METEO
• zájem o něj rychle opadl
• systémy používající interlinguu
• interlingua-based
• dva kroky - analýza, syntéza
• Rosetta, KBMT-89
• transferové systémy
• tři kroky (+ transfer)
• PC Translator
Do 90. let pouze tyto dva typy systémů.
Úvod
oooo»ooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
Rozdělení systémů
Systém přímého překladu
• hledají se korespondence mezi zdrojovými a cílovými jazykovými jednotkami (slovy)
• první pokusy s překladem EN-RU
• všechny složky jsou striktně omezeny na konkrétní jazykový pár
• typicky se skládá z velkého překladového slovníku a a monolitického programu řešícího analýzu a syntézu
• nutně dvojjazyčné a jednosměrné
• pro překlad mezi N jazyky potřebujeme N x (N - 1) přímých dvojjazyčných systémů / modulů
Úvod
ooooo»oo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
Rozdělení systémů
Přístup pomocí interlinguy
• předpokládá, že je možné SL konvertovat do sémanticko-syntaktické reprezentace, která je (částečně) nezávislá na jazyku
• interlingua musí být jednoznačná (unambiguous)
• z této podoby (interlingua) je generován TL
• analýza SL je jazykově závislá, ale nezávislá na TL
• analogicky syntéza TL
• SL a TL nepřijdou do styku
• pro překlad mezi N jazyky potřebujeme 2 x N modulů
Úvod
oooooo»o
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
Rozdělení systémů
Transferové systémy strojového překladu
• provede se analýza po jistou úroveň
• transferová pravidla převedou zdrojové jednotky na cílové
• ne nutně na stejné úrovni
• převod na (nejčastěji) syntaktické úrovni dovoluje zavádět kontextová omezení u přímých překladů nedostupná
• na cílové straně se pak generuje cílový řetězec
• systém linearizace
• při hlubší analýze dochází ke stírání rozdílů mezi interlingua-based a transfer-based systémy
• značná část obou systémů se může překrývat
Uvod
0000000»
Rozdělení systémů
Token izace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooooot
Interlingua vs. transferové KBMT
0 Úvod
0 Tokenizace
Q Morfologická rovina Q Lexikální rovina
Úvod Tokenizace Morfologická rovina Lexikální rovina
oooooooo o«o OOOOOOOOOOOOOOOOO OOOOOOOOOOOOÍ
Od řetězce ke slovu
Tokenizace
Co to je?
• rozdělení vstupního řetězce do tokenů
• token = řetězec znaků
• výstup tokenizace = seznam tokenů
• slouží jako vstup pro další zpracování
• označení hranic vět
Problémy
• don't: do_n't, do_n_'t, don_'t, ?
• červeno-černý: červeno_-_černý, červeno-černý, červeno-_černý « Zeleninu jako rajče, mrkev atd. ^fPetr nemá rád.
• Složil zkoušku a získal titul Mgr. ^[Petr mu dost záviděl.
Úvod
Tokenizace oo»
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooootx
oooooooo
Od řetězce ke slovu
Tokenizace - jak se to dělá?
V drtivé většině případů heuristika, (unitok.py)
Dělení na tokeny « pro jazyky používající hlásková písma: dělení podle mezer a a podle dalších interpunkčních znamének
• ?!.,-()/:;
Dělení na věty
• MT v naprosté většině případů pro věty
• u plaintextu: podle seznamu interpunkčních znamének
• problém: Měl jsem 5 (sic!) poznámek.
• výjimky: zkratky (aj., atd., etc), tituly (RNDr., prof.)
• někdy (HTML) lze využít strukturní značky
Úvod Tokenizace Morfologická rovina
OOOOOOOO OOO »0000000000000000
Úvod
Morfologická rovina
O Úvod
Q Tokenizace
Q Morfologická rovina
Q Lexikální rovina
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina o»ooooooooooooooo
Lexikální rovina oooooooooootx
Úvod
Morfologická rovina
« druhé patro v překladovém trojúhelníku
• je nutné eliminovat obrovský počet slovních variant
• převod slovní formy na základní tvar give, gives, gave, given, giving give
dělá, dělám, dělal, dělaje, dělejme,... ->• dělat
• analýza gramatických kategorií slovních tvarů
dělali ->• dělat + minulost + průběh + plurál + 3. osoba did ^ do + minulost + dokonavost + osoba ? + číslo ? Robertovým    Robert + pád ? + adjektivum + číslo ?
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina oo»oooooooooooooo
Lexikální rovina oooooooooootx
Morfologická analýza
Morfologická analýza
• pro každé slovo získáme základní tvar, gramatické kategorie, případně segmentaci
• Co je to základní slovní tvar? Lemma.
• jména: singulár, nominativ, positiv, maskulinum
• bycha ->- bych?, nejpomalejšími ->- pomalý neschopný ->• schopný?
• slovesa: infinitiv
• neraď^ radit?, bojím se ->• bát (se)
• Proč infinitiv? nejčastější tvar slovesa
• lemma souvisí s rozsahem/obsahem použitého slovníku
Úvod
Tokenizace ooo
Morfologická rovina ooo»ooooooooooooo
Lexikální rovina oooooooooootx
oooooooo
Morfologická analýza
Morfologické značky, tagset
• silně závislé na jazyce (různé morfologické kategorie)
« brněnský atributový systém: dvojice kategorie-hodnota maminkou kigFnScľ Udělány k5eAaPmNgFnP
• pražský poziční systém: 16 pevných pozic kontury ->• NNFPl-----a----
zdajíc VB-P—3P-aa—
a Treebank tagset (angličtina): omezená množina značek f aster ->• rbr doing ->• vbg
• a další (němčina)
gigantische    adja . ad ja . Pos. Acc. Sg. Fem erreicht ->• WPP. vpp . Fuli. Psp
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina oooo«oooooooooooo
Morfologická disambiguace
Problém s víceznačností
• v mnoha případech: více morfologických značek
• víceznačnost mezi slovními druhy (více lemmat) jednou ->• k4gFnSc7, k6eAdl, k9
Ženu     klgFnSc4, k5eAaImIplnS
• víceznačnost v rámci slovního druhu
• typicky (čeština): nominativ = akuzativ víno     klgNnScl, klgNnSc4, ... odhalením 10 značek
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooo»ooooooooooo
Morfologická disambiguace
Morfologická disambiguace
a nutno vybrat jednu značku a jedno lemma
• ke slovu přichází morfologická disambiguace a nástroj tagger
a překladová víceznačnost je něco jiného pubblico    Öffentlichkeit, Publikum, Zuschauer
• drtivá většina metod využívá kontext
• okolní slova a jejich značky
Úvod Tokenizace Morfologická rovina
OOOOOOOO OOO 000000*0000000000
Morfologická disambiguace
Statistická disambiguace
• nejpravděpodobněji posloupnost značek Ženu je domů.
k5|kl, k3|k5, k6|kl Mladé muže gF|gM, nS|nP
a těžká situace: dítě škádlí lvíče
a strojové učení na ručně značkovaných datech
• různé metody: Brill, TreeTagger
• pro češtinu: Desamb (hybridní)
• je nutné mít k dispozici trénovací data (korpus)
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooo»ooooooooo
Lexikální rovina oooooooooootx
Morfologická disambiguace
Pravidlová disambiguace
• pokud není k dispozici anotovaný korpus - nutné
• pravidla vyžadují dobrou znalost jazyka
• většinou se používá jako filtr před použitím statistického taggeru
• pravidla mohou zachytit širší kontext
• typicky: shoda v pádu, čísle a rodu ve jmenných frázích
malému (c3,gIMN) Chlapci(nPcl57, nSc36, gM)
• sofistikovanější: valenční struktura věty valence: vidět koho/co
vidím stůl c4
• systémy DIS, VaDIS
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina
00000000*00000000
Lexikální rovina oooooooooooo<
Morfologická segmentace
Morfologická segmentace
• proč místo lemmatu (např. infinitiv) nepoužít kořen slova?
• existují i systémy, které provádí segmentaci automaticky na základě seznamu slov pro daný jazyk
• problém: mít, měj, mám, měl, mívá,... - různé podoby téhož morfému
• problém: /', ové, a, y- stejná gramatická funkce, různé morfémy
• bychom bych?
• gramatické kategorie mají konkrétní formu (gramémy) nad-měr-ný, ne-patr(n)-ně, vid-ím, ne-chci, čtyř-i-cet, po-po-sun-out, u-děl-al-i
• nutné pokud nemáme morfologický analyzátor k dispozici
Úvod Tokenizace Morfologická rovina Lexikální rovina
OOOOOOOO OOO OOOOOOOOOOOOOOOOO OOOOOOOOOOOOÍ
Morfologie - závěrem
slovo	analýzy	disambiguace
Pravidelné	k2eAgMnPc4d1, k2eAglnPc1d1, k2eAglnPc4d1, k2eAglnPc5d1, k2eAgFnSc2d1, k2eAgFnSc3d1, k2eAgFnSc6d1, k2eAgFnPc1d1, k2eAgFnPc4d1, k2eAgFnPc5d1, k2eAgNnSc1d1, k2eAgNnSc4d1, k2eAgNnSc5d1, ... (+5)	k2eAgNnSc1d1
krmení	k2eAgMnPc1d1, 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
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina
0000000000*000000
Morfologie - závěrem
Universal POS tags
Počet značek se v různých jazycích značně liší snaha o zjednodušení.
TAG	význam
VERB	verbs (all tenses and modes)
NOUN	nouns (common and proper)
PRON	pronouns
ADJ	adjectives
ADV	adverbs
ADP	adpositions (prepositions and postpositions)
CONJ	conjunctions
DET	determiners
NUM	cardinal numbers
PRT	particles or other function words
X	other: foreign words, typos, abbreviations
	punctuation
Vytvořeno mapování pro cca 25 jazyků s tree banky.
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooo»ooooo
Morfologie - závěrem
Odhadování POS na základě gramémů
EN	CZ	význam
-s	-á	3. os., j. č., přít.
-ed	-al, -1, -en.	minulý čas
-ing	-(ov)ání	průběhový čas
-en	-en(.)	příčestí minulé
-s	-y, -i, -ové, -a	množné číslo
-'s	ov(o, a, y)	přivlastňování
-er	-ší	komparativ
-est	nej-, -ší	superlativ
Problém: myší, west, fotbal,
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina oooooooooooo»oooo
Morfologie - závěrem
Tomáš Hanák - Sám v lese II
Když jsi sám v lese,
ano, sám-li v lese's,
však skutečně, v lese sám's-li.
Zkrátka v lese sám-li's.
Však kde vlastně vzal ty tu's?
Z meze-li v les's vlez?
Či z nebes v les se snesľs?
Pověz, ach, tvář tvá perlí přívalem se slz. Ted ruďs, zas bleďs, co pivoňka's Snad tedy autem's tu, či kolmo's?
Mlčíš a slza tvá dál
sama malá padá v mechu číš.
Ano, ted teprve snad poprvé sám svěťs.
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooo»ooo
Morfologie - závěrem
Brillův tagger
• učení z trénovacích dat
• transformation-based, error-driven
• úspěšnost přes 90%
O inicializuj značkování (nejčastější značka) 0 porovnej s trénovacími daty 0 vytvoř sadu pravidel pro změnu značek O ohodnoť pravidla
O aplikuj pravidlo a opakuj od 2. dokud je co zlepšovat
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina oooooooooooooo»oo
Lexikální rovina oooooooooootx
Morfologie - závěrem
Problémy s POS
• kvalita MA ovlivňuje všechny další roviny zpracování
• kvalita se liší pro různé jazyky (angličtina vs. maďarština)
• chončaam (tj) - můj malý dům (domek) (tádžičtina)
• kahramoni (tj) - jsi hrdina
• legeslegmagasabb (hu) - úplně nejvyšší
• raněný-SUBS/ADJ
• the big red fire truck - SUBS / ADJ?
a The Duchess was entertaining last night.
• Pokojem se neslo tiché pšššš
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooo»o
Morfologie - závěrem
Co s neznámými slovy?
• jde nám o pokrytí: analýza co nejvíce slov
• nová, přejatá slova
• řeší guesser
• sedm dunhillek
• bez facebooku strádám
• třitisícedvěstědevadesátpět znaků
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina
0000000000000000»
Lexikální rovina oooooooooooo<
Morfologie - závěrem
Morfologie - shrnutí
• první rovina, která zanáší do analýzy významné chyby
• snaha omezit počet slovních tvarů
• nahrazení slovního tvaru za dvojici lemma + značka
• pro angličtinu s 36 značkami snadné
• POS tagging dosahuje pro různé jazyky různé kvality « typicky kolem 95%
Úvod Tokenizace Morfologická rovina
oooooooo ooo ooooooooooooooooo
Úvod
Slova a slovníky ve strojovém překladu
Úvod
Tokenizace Morfologická rovina 0 Lexikální rovina
Úvod
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina o«oooooooooo<
oooooooo
Úvod
Slovníky ve strojovém překladu I
• propojení mezi jazyky typicky na úrovni slov (slovníky)
• u transferových systémů i na úrovni syntaktických struktur
• pro KBMT systémy jsou slovníky nezbytné
• typicky 10k a více položek « GNU-FDL slovník
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oo»ooooooooo<
Úvod
Slovníky ve strojovém překladu II
• kolik položek ve slovníku potřebujeme / chceme? ->•pojmenované entity, slang
listem - jazyková položka, kterou nelze odvodit na základě principu kompozicionality (slaměný vdovec)
• v jakém tvaru mají být slova ve slovníku? ->•lemmatizace
• jak odlišit jednotlivé významy pro potřeby strojového překladu?
->• budování slovníků pro strojový překlad
• kolik různých významů má smysl rozlišovat? ->•granularita
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Víceznačnost
Problém s víceznačností
• slovům odpovídají významy
• co je ale význam? pro počítač potřebujeme formál
• počítač je diskrétní, význam je zřejmě spojitý
• muž - dospělý člověk mužského pohlaví
• co 17letý člověk mužského pohlaví?
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Víceznačnost
Typy víceznačnosti
Víceznačnost se projevuje na více úrovních:
• morfologie (-s, viz výše)
• slova (oko)
• slovní spojení (bílá vrána)
• věty (I saw a man with a telescope.)
• homonymie: náhodný jev
• úplná homonymie: líčit, kolej
• částečná h.: los, stát
• polysémie je přirozená: oko, táhnout,...
Úvod Tokenizace Morfologická rovina Lexikální rovina
oooooooo ooo ooooooooooooooooo oooooo»ooooo<
Víceznačnost
Granularita
Kolik významů má slovo kočka?
• malá kočkovitá šelma chovaná v domácnostech
• malá nebo středně velká šelma s hustým kožichem
• samice kočkovité šelmy
• kožešina na límci, kolem krku nebo ramen
• kocovina
• věc připomínající vlastnost kočky a druh důtek
Pro strojový překlad může stačit granularita překladového slovníku: slovo x má tolik významů jako má překladových ekvivalentů ve slovníku.
Uvod
oooooooo
Víceznačnost
Token izace ooo
Morfologická rovina ooooooooooooooooo
Granularita - oko
oko
• zrakový orgán
• klička, smyčka, kroužek z různého materiálu
• věc připomínající tvarem oko (morské oko)
• jednotka v kartách, loterii
• druh karetní hry
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Víceznačnost
Granularita - dát, SSJČ
dát (bez se)
• odevzdat do vlastictví, darovat, prodat
• vyžádat, způsobit (dá to mnoho práce)
• umístění něčeho
• dopřát, dovolit, připustit (nedej pane)
• projevit nedostatek odporu (dát se ošidit)
• přikázat (dát něco udělat)
VerbaLex uvádí 32 (!) významů (nezvratné varianty)
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Víceznačnost
Granularita - malý
malý, malá
• neveliký rozměry, počtem, časovým rozsahem
• nedospělý
• slabý, nevydatný (malý rozhled)
• nevýznamný (malý pán)
• téměř (malý zázrak)
• děvčátko (malá)
• přihrávka vlastnímu brankáři (malá domů)
Uvod
oooooooo
Reprezentace významu
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina oooooooooo»oc
Reprezentace významu
• nejčastější způsob: banka významů
• graf: významy jsou uzly sémantické relace jsou hrany
• prostor: významy jsou body, podobné významy jsou prostorově blízko
RESERVE
EY
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Reprezentace významu
Sémantická síť - WordNet
• literál dát:8, synset louže:1, kaluž:1, tratoliště:1
• sémantické relace: hypero-, hypo-, holo-, meronymum
• 150k slov, 117k synsetů: n, adj, v a adv
• WN používán jako referenční banka významů
y     \    \ \
Úvod
oooooooo
Tokenizace ooo
Morfologická rovina ooooooooooooooooo
Lexikální rovina 000000000000«
Reprezentace významu
VerbaLex
• WordNet neobsahuje syntaktické vazby, morfosyntaktické omezení
• synsety (6 256)
atakovat:1, útočit:2, dorážet:3, napadnout:6
• valenční rámce (mačkat:1) a sloty (19 247) AG^on:1 + VERB + OBJS&cm + (PART™6)
• sémantické role
I: ABS, ISUB, AG, KNOW, PAT, VERB, ... (29)
II: abstractions, person:1, artifacts, body part:1, ... (103)
• další omezení:
předložkové pády, životnost, slovní druhy, obligatornost
• synsety napojeny na WordNet