plyne:
V této úloze bylo mým cílem zjistit, která slova se nejčastěji vyskytují společně, a která se naopak společně vyskytují nejméně.
Abych toto určil, použil jsem pointwise mutual information (dále jen PMI).
Ze vzorečku plyne:
|
|
|
|
Tabulky pro oba jazyky vypadají vypadají velmi podobně. Nejčastěji se spolu vyskytují více slovná vlastní jména a ustálená slovní spojení. Naopak nejméně často se spolu vyskytují slovní spojení, která se vedle sebe můžou vyskytnout jen v důsledku nějaké chyby při předzpracování text (2 interpunknční znaménka, 2 pomocná slova).
|
|
|
|
Pro obě tabulky opět platí, že jsou velmi podobné. Výskyt dvou stejných slov je způsoben tím, že několik sousedících vět (vzdálenost 50) popisuje jedno téma, a proto se v ních opakuje jedno slovo.
Český korpus obsahoval velké množství výsledků sportovních utkání (fotbal a tenis), které obsahovaly velké množství čísel a dvojteček. Toto je patrné zejména na české tabulce s negativními asociacemi.
Přijde mi zajímavé, že jsou všechny hodnoty kladné (kromě 1 hodnoty pro češtinu)
Řešené je možné získat pomocí příkazu make task1, případně pomocí ./task1a.pl CORPUS pro sousední slova a ./task1b.pl CORPUS pro vzdálená slova.
V této úloze bylo mým úkolem spočítat úplnou hierarchii slov. Použil jsem prvních 8000 slov z korpusu. Pomocí hladového algoritmu, který využíval vzájemnou informaci (mutual information, MI) jsem slučoval slova, která se v korpusu vyskytla alespoň 10 do tříd. Ostatní slova jsem používal jen pro výpočet pravděpodobností.
Nejdříve jsem implementoval základní verzi algoritmu, která byla dostatečně rychlá pro všechny zadání, kromě slučování značek v českém korpusu. Optimalizovaná verze dává rozdílné výsledky, protože díky chybám v zaokrouhlování se hodnoty mírně liší. Výsledek také ovlivní, pokud si pamatujeme první nebo poslední největší zrátu.
| Tříd | Levé | Pravé | MI | Δ | Nová třída |
|---|---|---|---|---|---|
| 60 | listopadu | OKD | 7.55800162777408 | 0.00308288427059992 | ((listopadu) + (OKD)) |
| 59 | který | které | 7.55568285570843 | 0.00337715725827173 | ((který) + (které)) |
| 58 | státu | J | 7.55307286122496 | 0.00403078845443623 | ((státu) + (J)) |
| 57 | nás | bylo | 7.54981041229344 | 0.00443001740582646 | ((nás) + (bylo)) |
| 56 | musí | bude | 7.54592473159899 | 0.00443832113333579 | ((musí) + (bude)) |
| 55 | ale | aby | 7.54226364546871 | 0.00458514828119256 | ((ale) + (aby)) |
| 54 | si | nás | 7.53841930153996 | 0.00433575562679432 | ((si) + ((nás) + (bylo))) |
| 53 | už | musí | 7.53273997725943 | 0.00472057564992331 | ((už) + ((musí) + (bude))) |
| 52 | pouze | být | 7.52657459670258 | 0.00474951358616901 | ((pouze) + (být)) |
| 51 | však | už | 7.52218215247935 | 0.00468440359779063 | ((však) + ((už) + ((musí) + (bude)))) |
| 50 | ze | si | 7.51520002180639 | 0.00499826269513748 | ((ze) + ((si) + ((nás) + (bylo)))) |
| 49 | NATO | &slash; | 7.5067205303714 | 0.0049734009713178 | ((NATO) + (&slash;)) |
| 48 | u | státu | 7.50190977969972 | 0.00530621996946778 | ((u) + ((státu) + (J))) |
| 47 | jeho | NATO | 7.49373392902828 | 0.00500827752330371 | ((jeho) + ((NATO) + (&slash;))) |
| 46 | zákona | ze | 7.48670090869553 | 0.00517320151793244 | ((zákona) + ((ze) + ((si) + ((nás) + (bylo))))) |
Sloučení slov (který + které) a (musí + bude) do jedné třídy hned nazačátku je podle očákávání. Sloučení (listopadu + OKD), případně (státu + J) je překvapivé.
Na těchto třídách mi přijde zajímavé, že předložky (na) a (v) zůstaly samostatné, přestože již existuje několik tříd, které předložky obsahují - 6, 13, 14. Také je zajímavé, že interpunkční znaménka (,), (.), (-) zůstaly samostatně. Zřejmě je to způsobené tím, že se používají v rozdílých kontextech.
| Tříd | Levé | Pravé | MI | Δ | Nová třída |
|---|---|---|---|---|---|
| 111 | subject | case | 4.99726326162518 | 0.00219656653357569 | ((subject) + (case)) |
| 110 | may | cannot | 4.99551078578768 | 0.00267307199568141 | ((may) + (cannot)) |
| 109 | structure | individuals | 4.99328515801807 | 0.00267867444717366 | ((structure) + (individuals)) |
| 108 | there | It | 4.99105327930244 | 0.00348686342639491 | ((there) + (It)) |
| 107 | variation | structure | 4.98801582605303 | 0.00326440020171332 | ((variation) + ((structure) + (individuals))) |
| 106 | less | even | 4.98327893988384 | 0.00366788840496749 | ((less) + (even)) |
| 105 | what | there | 4.98006333804047 | 0.00371129669485222 | ((what) + ((there) + (It))) |
| 104 | shall | see | 4.97494991392501 | 0.00373999234908198 | ((shall) + (see)) |
| 103 | such | less | 4.97149002081017 | 0.00386262176886489 | ((such) + ((less) + (even))) |
| 102 | distinct | certain | 4.96652018486623 | 0.00381367578955801 | ((distinct) + (certain)) |
| 101 | slight | short | 4.96296384638732 | 0.00393371087351907 | ((slight) + (short)) |
| 100 | variation | nature | 4.95949323182728 | 0.0040345181712515 | (((variation) + ((structure) + (individuals))) + (nature)) |
| 99 | subject | state | 4.95579679886649 | 0.00412132286218402 | (((subject) + (case)) + (state)) |
| 98 | must | can | 4.95195274383051 | 0.00416841070827361 | ((must) + (can)) |
| 97 | when | if | 4.94812146367093 | 0.00420406443163896 | ((when) + (if)) |
Podle očekávání se na začátku sloučila pomocná slovesa (may + cannot), (must + can), stejně jako zájména (there + it) a spojky (when + if).
Pro angličtinu mi přijde zajímavá třída číslo 9, která obsahuje pomocná slovesa.
Tento úkol je velmí podobný úkolu Word Classes. Jen místo slov jsem použil značky. Prováděl jsem slučování těch značek, které se vyskytly alespoň pět krát.
Čeština měla 676 takovýchto tříd, zatímco angličtina jen 35.
| Tříd | Levé | Pravé | MI | Δ | Nová třída |
|---|---|---|---|---|---|
| 676 | CrIP6---------- | AAIP6----3A---- | 1.65256679126702 | 0 | ((CrIP6----------) + (AAIP6----3A----)) |
| 675 | NNNXX-----A---8 | J^------------8 | 1.65256772593943 | 2.53247078646642e-06 | ((NNNXX-----A---8) + (J^------------8)) |
| 674 | PSFS6-P1------- | AAFS6----2A---- | 1.65256612897209 | 1.1930582269243e-05 | ((PSFS6-P1-------) + (AAFS6----2A----)) |
| 673 | Vi-P---1--N---- | PJXP2---------- | 1.65255513957433 | 2.002719144699e-05 | ((Vi-P---1--N----) + (PJXP2----------)) |
| 672 | PSFS6-P1------- | AAFS6----3A---- | 1.6525360500901 | 2.0320662501027e-05 | (((PSFS6-P1-------) + (AAFS6----2A----)) + (AAFS6----3A----)) |
| 671 | AGIP3-----A---- | AAIP3----3A---- | 1.65251666854118 | 2.2740379430976e-05 | ((AGIP3-----A----) + (AAIP3----3A----)) |
| 670 | PZXP6---------- | PSXP6-P1------- | 1.65249487380029 | 2.33503104394993e-05 | ((PZXP6----------) + (PSXP6-P1-------)) |
| 669 | PLXP6---------- | AGFP6-----A---- | 1.65247249100285 | 2.36489903890711e-05 | ((PLXP6----------) + (AGFP6-----A----)) |
| 668 | PSFS7-P1------- | AGFS7-----A---- | 1.65244979724866 | 2.61364738529226e-05 | ((PSFS7-P1-------) + (AGFS7-----A----)) |
| 667 | VB-S---2P-NA--- | NNNXX-----A---8 | 1.65242461603261 | 2.62461565891859e-05 | ((VB-S---2P-NA---) + ((NNNXX-----A---8) + (J^------------8))) |
| 666 | CrNP6---------- | AANP6----1A---- | 1.65237633512269 | 2.7001722845481e-05 | ((CrNP6----------) + (AANP6----1A----)) |
| 665 | AAFP7----2A---- | AAFP7----1N---- | 1.6523480149638 | 2.78939134954551e-05 | ((AAFP7----2A----) + (AAFP7----1N----)) |
| 664 | AAIS6----3A---- | AAIS6----1N---- | 1.65232107178083 | 2.7920856205121e-05 | ((AAIS6----3A----) + (AAIS6----1N----)) |
| 663 | PDFS3---------- | ClFS3---------- | 1.65229411790194 | 2.92521506371643e-05 | ((PDFS3----------) + (ClFS3----------)) |
| 662 | PWZS6---------- | AAIS6----3A---- | 1.65226584167111 | 2.82919116085627e-05 | ((PWZS6----------) + ((AAIS6----3A----) + (AAIS6----1N----))) |
Z výsledku je patrné, že se nejdříve slučovaly slovní druhy, které se ve větě podobně chovají. Například hned první sloučení je mezi číslovkou a přídavným jménem se shodou v čísle a pádě. Většina výsledků z první patnáctky jsou sloučení neurčitých zájmén, číslovek a přídavných jmén se shodou v čísle a pádě.
| Tříd | Levé | Pravé | MI | Δ | Nová třída |
|---|---|---|---|---|---|
| 35 | WP$ | RBR | 0.883347644115876 | 0.000218938901571533 | ((WP$) + (RBR)) |
| 34 | WP$ | JJR | 0.88312617433601 | 0.000348883371974458 | (((WP$) + (RBR)) + (JJR)) |
| 33 | NNPS | SYM | 0.882774758455361 | 0.00081936595676983 | ((NNPS) + (SYM)) |
| 32 | PRP | EX | 0.881952856231551 | 0.00108471985485757 | ((PRP) + (EX)) |
| 31 | NNP | FW | 0.880865595151047 | 0.0012186099436301 | ((NNP) + (FW)) |
| 30 | ( | . | 0.879644438417516 | 0.00131696119660064 | ((() + (.)) |
| 29 | WP | " | 0.878318399644737 | 0.0013896994339382 | ((WP) + (")) |
| 28 | JJ | JJS | 0.876926141043961 | 0.0017369574603936 | ((JJ) + (JJS)) |
| 27 | WP$ | RBS | 0.875186616507728 | 0.00210767263749093 | ((((WP$) + (RBR)) + (JJR)) + (RBS)) |
| 26 | WP | WRB | 0.873076367208517 | 0.00231054429217332 | (((WP) + (")) + (WRB)) |
| 25 | DT | PRP$ | 0.87076323575101 | 0.002654018724977 | ((DT) + (PRP$)) |
| 24 | CD | JJ | 0.868106617803369 | 0.00328816183362138 | ((CD) + ((JJ) + (JJS))) |
| 23 | NNP | NNPS | 0.864815841821281 | 0.00364973320405668 | (((NNP) + (FW)) + ((NNPS) + (SYM))) |
| 22 | WP | WDT | 0.86116347790731 | 0.00601226015664256 | ((((WP) + (")) + (WRB)) + (WDT)) |
| 21 | , | : | 0.855148559792979 | 0.0059474568665758 | ((,) + (:)) |
| 20 | VBN | VBD | 0.849198418013684 | 0.00619973092647955 | ((VBN) + (VBD)) |
Ve druhém kole slučování se sloučí komparativ přídavného jména a příslovce. V osmém kole dojde ke sloučení přídavných jmen.
Textový korpus jsem rozdělil na část pro testování (40000 slov), vyhlazování (20000 slov) a zbytek. Velikosti jednotlivých částí jsou nepatrně větší, protože jsem korpus dělil po větách.
Celkově jsem vytvořil 5 různých rozdělení. První dva způsoby dělení jsem použil ze zadání (testovací data, 20000 slov na vyhlazování, 40000 slov na testování) a (40000 slov na testování, 20000 slov na vyhlazování, testovací data). Pro zbylá 3 dělení jsem použil náhodné rozdělení. Tento přístup jsem zvolil, abych se vyhnul problémům, když by jednotlivé části korpusu byly získány z různých zdrojů.
Data se připraví pomocí příkazu ./prepare-data.pl CORPUS. Výsledkem je 15 nových souboru CORPUS.01.train, CORPUS.01.heldout, CORPUS.01.test, CORPUS.02.train, ..., CORPUS.05.test.
Většině pomocných skriptů stačí zadat jako parametr CORPUS.01 a skript sám použije jednotlivé soubory.
Součástí Brillova taggeru je také skript pro vyhodnocení úspěšnosti na slovech. Já jsem se rozhodl použít vlastní skript eval.pl, který spočítá úspěšnost na jednotlivých slovech i větách. Také vypíše nejčastější chyby. Spouští se pomocí příkazu ./eval.pl CORPUS_EXPECTED CORPUS_ACTUAL
Ke každému taggeru existuje Makefile, který provede všechny akce s konkrétním taggerem.
Pro spuštění úkolu s brillovým taggerem stačí jen napsat: nohup nice -n19 make -f Makefile.brill > out.brill &.
Ke každému taggeru také existuje pomocný skript, který provede natrénování i vyhodnocení na zadaném korpusu.
Tento pomocný skript vytvoří adresář CORPUS_TAGGER, do tohoto adresáře překopíruje použité soubory, a také v něm vytváří všechny pomocné soubory. Výsledek je v souboru CORPUS.result. Spuštění skriptu může vypadat například takto: ./brill-tagger.sh texten2.ptg.01.
Brillův tagger jsem získal ze zdroje uvedeného na wikipedii.
Aby bylo možné tento tagger použít i pro češtinu, tak jsem musel změnit velikost bufferu pro maximální velikost řádku z 500 na 50000 (ani zvětšení na 5000 nebylo dostatečné).
Nejdříve jsem nastavil prahovou hranici pro ukončení učení nových lexikálních a kontextových pravidel na 3. Na anglických datech trval celý proces 2h, zatímco na českých datech ani 12 dní nestačilo.
Proto jsem postupně zvyšoval prahové hranice pro lexikální a kontextová pravidla. Nakonec jsme použil hodnoty (30, 10) (lexikální, kontextové).
Pro češtinu jsem zjistil, že používání nízkých prahových hodnot nepřináší příliš výhod:
| Doba | Slova | Věty |
|---|---|---|
| 12 dní | 84.5183% | 24.1216% |
| 8 hodin | 84.3085% | 20.0249% |
| 7 hodin | 83.6464% | 18.6539% |
| 6 hodin | 82.8245% | 17.2419% |
| Angličtina (3, 3) | Angličtina (30, 10) | Čeština (30, 10) | ||||||||||
| Set | Slova | Slova (%) | Věty | Věty (%) | Slova | Slova (%) | Věty | Věty (%) | Slova | Slova (%) | Věty | Věty (%) |
| 1. | 37982/40009 | 94.9336% | 599/1715 | 34.9271% | 37771/40009 | 94.4063% | 511/1715 | 29.7959% | 33203/40005 | 82.9971% | 539/2533 | 21.2791% |
| 2. | 38017/40004 | 95.0330% | 621/1709 | 36.3370% | 37831/40004 | 94.5680% | 559/1709 | 32.7092% | 33371/40015 | 83.3962% | 473/2507 | 18.8672% |
| 3. | 38179/40010 | 95.4236% | 663/1709 | 38.7946% | 38067/40010 | 95.1437% | 622/1709 | 36.3956% | 33858/40001 | 84.6429% | 501/2357 | 21.2558% |
| 4. | 38099/40004 | 95.2380% | 623/1676 | 37.1718% | 37898/40004 | 94.7355% | 565/1676 | 33.7112% | 33750/40000 | 84.3750% | 507/2441 | 20.7702% |
| 5. | 38165/40027 | 95.3481% | 643/1686 | 38.1376% | 38006/40027 | 94.9509% | 579/1686 | 34.3416% | 33747/40028 | 84.3085% | 482/2407 | 20.0249% |
| Celkem | 95.0898% ± 0.4094% | 37.0736% ± 1.5210% | 94.8663% ± 0.2206% | 33.3907% ± 2.4199% | 83.9439% ± 0.7078% | 20.4394% ± 1.0155% | ||||||
Zvýšení hranic pro lexikální a kontextová pravidla příliš nesnížili úspěšnost taggeru na jednotlivých slovech, ale významně snižilo úspěšnost správného otagování celé věty.
Tagger měl na českých datech nižší úspěšnost. Tato nižší úspěšnost je důsledkem mnohem většího počtu značek a omezeným výhledem taggeru.
Pro češtinu často docházelo k chybám u tvarů, které mají mají stejné koncovky (viz ukázka). Toto bylo zřejmě způsebeno tím, že tagger měl přístup jen k sousedním slovům, takže nemohl určit nějaká lepší pravidla.
NNIS1-----A---- NNIS4-----A---- 127 RR--6---------- RR--4---------- 119 X@------------- NNMS1-----A---- 88 NNIS4-----A---- NNIS1-----A---- 86 NNFP1-----A---- NNFS2-----A---- 85 NNNS4-----A---- NNNS1-----A---- 63
V tomto úkolu jsem implementoval HMM tagger. Tento tagger používá trigramový model pro přechodové pravděpodobnosti (dvojice značek) a lexikální model pro výstupní pravděpodobnosti.
Pro vyhlazování jsem použil EM algoritmus z minulého semestru. U lexikálního modelu se navíc část heldout dat používá pro odhad distribuce neznámých slov.
Opět byl problém s českým korpusem. Proto jsem implementoval prořezávání, které v každé etapě nechávalo pouze N nejlepších stavů. Opět se ukázalo, že nemá příliš smysl optimalizovat algoritmus, protože snížením parametru N nedochází příliš k poklesu úspěšnosti.
Když jsem spustil HMM tagger s prořezáváním na 60 paprsků, tak pro angličtinu bylo potřeba jen okolo 150MB paměti, zatímco pro češtinu nebylo možné tento tagger spustit, protože potřeboval více než 4GB paměti.
Snížil jsem tedy počet paprsků na 15, takže i pro českou verzi stačilo 170MB paměti.
| Angličtina (60) | Angličtina (15) | Čeština (15) | ||||||||||
| Set | Slova | Slova (%) | Věty | Věty (%) | Slova | Slova (%) | Věty | Věty (%) | Slova | Slova (%) | Věty | Věty (%) |
| 1. | 37559/40009 | 93.8764% | 543/1715 | 31.6618% | 37560/40009 | 93.8789% | 543/1715 | 31.6618% | 32565/40005 | 81.4023% | 469/2533 | 18.5156% |
| 2. | 37400/40004 | 93.4907% | 534/1709 | 31.2463% | 37399/40004 | 93.4882% | 533/1709 | 31.1878% | 32988/40015 | 82.4391% | 513/2507 | 20.4627% |
| 3. | 37755/40010 | 94.3639% | 587/1709 | 34.3476% | 37758/40010 | 94.3714% | 588/1709 | 34.4060% | 33366/40001 | 83.4129% | 546/2357 | 23.1650% |
| 4. | 37691/40004 | 94.2181% | 570/1676 | 34.0095% | 37697/40004 | 94.2330% | 572/1676 | 34.1289% | 33177/40000 | 82.9425% | 552/2441 | 22.6137% |
| 5. | 37810/40027 | 94.4612% | 603/1686 | 35.7651% | 37814/40027 | 94.4712% | 604/1686 | 35.8244% | 33342/40028 | 83.2967% | 548/2407 | 22.7669% |
| Celkem | 94.0820% ± 0.3980% | 33.4061% ± 1.9054% | 94.0885% ± 0.4036% | 33.4418% ± 1.95752% | 82.6987% ± 0.8178% | 21.5048% ± 1.9748% | ||||||
Nesplněno.
| Brill | HMM | |||
| Set | Slova (%) | Věty (%) | Slova (%) | Věty (%) |
| 1. | 94.4063% | 29.7959% | 93.8789% | 31.6618% |
| 2. | 94.5680% | 32.7092% | 93.4882% | 31.1878% |
| 3. | 95.1437% | 36.3956% | 94.3714% | 34.4060% |
| 4. | 94.7355% | 33.7112% | 94.2330% | 34.1289% |
| 5. | 94.9509% | 34.3416% | 94.4712% | 35.8244% |
| Celkem | 94.8663% ± 0.2206% | 33.3907% ± 2.4199% | 94.0885% ± 0.4036% | 33.4418% ± 1.95752% |
Oba taggery měly na setech 1 a 2 nižší úspěšnost, než na zbylých třech, které byly vytvořeny náhodně. To může být způsobeno tím, že korpus byl složen z několika tématicky rozdílných částí.
Oba taggery také dosáhly srovnatelných výsledků - jak na slovech tak na celých větách.
| Brill | HMM | |||
| Set | Slova (%) | Věty (%) | Slova (%) | Věty (%) |
| 1. | 82.9971% | 21.2791% | 81.4023% | 18.5156% |
| 2. | 83.3962% | 18.8672% | 82.4391% | 20.4627% |
| 3. | 84.6429% | 21.2558% | 83.4129% | 23.1650% |
| 4. | 84.3750% | 20.7702% | 82.9425% | 22.6137% |
| 5. | 84.3085% | 20.0249% | 83.2967% | 22.7669% |
| Celkem | 83.9439% ± 0.7078% | 20.4394% ± 1.0155% | 82.6987% ± 0.8178% | 21.5048% ± 1.9748% |
Opět nastala situace, kdy na náhodně rozdělených korpusech taggery dosáhly lepších výsledků, než na pevně rozdělených korpusech.
HMM tagger měl sice nižší úspěšnost najednotlivých slovech, ale měl vyšší úspěšnost na větách. To je zřejmě způsobeno trigramovým modelem, který je součástí HMM.
V těchto úlohách jsem se naučil, že kvalita výstupu se přidáváním času zlepšuje velmi pomalu. Hlavně u úlohy s Brillovým taggerem, kdy po 288h běhu byla úspěšnost taggeru 84.5183%, zatímco už po 6h běhu je možné mít 82.8245% úspěšnost. Takže před nějakými pokusy o optimalizaci algoritmu je dobré nejdříve snížit parametry, a zjistit, o kolik se zhorší výsledek. Pokud není zhoršení příliš významné, nemá smysl se do optimalizací pouštět.