N-gram

N-gram  je posloupnost n prvků [1] . Ze sémantického hlediska se může jednat o sled hlásek, slabik, slov nebo písmen. V praxi je N-gram běžnější jako řada slov, stabilní fráze se nazývají kolokace . Sled dvou po sobě jdoucích prvků se často nazývá digram , posloupnost tří prvků se nazývá trigram . Nejméně čtyři nebo více prvků jsou označeny jako N-gram, N je nahrazeno počtem po sobě jdoucích prvků.

Použití N-gramů

Obecné použití N-gramů

N-gramy jako celek nacházejí své uplatnění v široké oblasti vědy. Uplatnění najdou například v oblasti teoretické matematiky , biologie , kartografie a také v hudbě . Mezi nejčastější použití N-gramů patří následující oblasti:

N-gramy jsou také široce používány při zpracování přirozeného jazyka .

Použití N-gramů pro potřeby zpracování přirozeného jazyka

V oblasti zpracování přirozeného jazyka se N-gramy používají především pro predikci na základě pravděpodobnostních modelů . N-gramový model počítá pravděpodobnost posledního slova N-gramu, pokud jsou známa všechna předchozí. Při použití tohoto přístupu pro jazykové modelování se předpokládá, že vzhled každého slova závisí pouze na slovech předchozích [2] .

Další aplikací N-gramů je detekce plagiátů . Pokud text rozdělíte na několik malých fragmentů, reprezentovaných N-gramy, lze je snadno vzájemně porovnávat a získat tak míru podobnosti analyzovaných dokumentů [3] . N-gramy se často úspěšně používají ke kategorizaci textu a jazyka. Kromě toho je lze použít k vytváření funkcí, které umožňují získat znalosti z textových dat. Pomocí N-gramů lze efektivně najít kandidáty na nahrazení chybně napsaných slov.

Příklad bigramového modelu

Účelem sestavení N-gramových modelů je určit pravděpodobnost použití dané fráze. Tuto pravděpodobnost lze formálně nastavit jako pravděpodobnost výskytu posloupnosti slov v určitém korpusu (množině textů). Například pravděpodobnost fráze „štěstí je potěšení bez výčitek svědomí“ lze vypočítat jako součin pravděpodobností každého ze slov této fráze:

P = P(štěstí) * P(je|štěstí) * P(potěšení|štěstí je) * P(bez|štěstí je potěšení) * P(pokání|štěstí je potěšení bez)

Chcete-li určit P(štěstí), musíte spočítat, kolikrát se toto slovo vyskytuje v textu, a vydělit tuto hodnotu celkovým počtem slov. Výpočet pravděpodobnosti P(pokání|štěstí je potěšení bez) je obtížnější. Pro zjednodušení této úlohy předpokládáme, že pravděpodobnost výskytu slova v textu závisí pouze na předchozím slově. Potom bude náš vzorec pro výpočet fráze mít následující podobu:

P = P(štěstí) * P(mít|štěstí) * P(radost|mít) * P(bez|potěšení) * P(výčitky|bez)

Výpočet podmíněné pravděpodobnosti P(je|štěstí) je snadný. Za tímto účelem spočítáme počet dvojic 'štěstí' a vydělíme počtem slov 'štěstí' v textu.

Pokud tedy spočítáme všechny dvojice slov v nějakém textu, můžeme vypočítat pravděpodobnost libovolné fráze. Tato sada vypočítaných pravděpodobností bude modelem bigramu.

Výzkumné projekty Google

Výzkumná centra Google použila N-gramové modely pro širokou škálu výzkumu a vývoje. Patří mezi ně projekty, jako je statistický překlad z jednoho jazyka do druhého, rozpoznávání řeči , opravy pravopisu, extrakce informací a další. Pro účely těchto projektů byly použity textové korpusy obsahující několik bilionů slov.

Google se rozhodl vytvořit vlastní vzdělávací budovu. Projekt se jmenuje Google teracorpus a obsahuje 1 024 908 267 229 slov nasbíraných z veřejných webů [4] .

Metody pro extrakci N-gramů

Vzhledem k častému používání N-gramů pro řešení různých problémů je k jejich extrakci z textu potřeba spolehlivý a rychlý algoritmus . Vhodný nástroj pro extrakci N-gramů by měl umět pracovat s neomezenou velikostí textu, pracovat rychle a efektivně využívat dostupné zdroje. Existuje několik metod pro extrakci N-gramů z textu. Tyto metody jsou založeny na různých principech:

Syntaktické N-gramy

Syntaktické N-gramy jsou N-gramy definované cestami ve stromech syntaktických závislostí nebo stromech komponent, spíše než lineární strukturou textu [6] [7] . Například větu: „Ekonomické zprávy mají malý dopad na finanční trhy“ lze převést na syntaktické N-gramy podle stromové struktury jejích závislostních vztahů : zprávy-ekonomické, dopad-menší, dopad-na-trhy-finanční, a další [6] .

Syntaktické N-gramy odrážejí syntaktickou strukturu na rozdíl od lineárních N-gramů a lze je použít ve stejných aplikacích jako lineární N-gramy, včetně funkcí ve vektorovém modelu. Použití syntaktických N-gramů dává lepší výsledky při řešení určitých problémů než použití standardních N-gramů např. pro určení autorství [8] .

Viz také

Poznámky

  1. ↑ Sborník příspěvků ze 7. výroční konference ZNALOSTI 2008, Bratislava, Slovensko, pp. 54-65, únor 2008. ISBN 978-80-227-2827-0 .
  2. ↑ Jurafsky, D. a Martin, JH Zpracování řeči a jazyka: Úvod do zpracování přirozeného jazyka, výpočetní lingvistiky a rozpoznávání řeči. - Pearson Prentice Hall, 2009. - 988 s. — ISBN 9780131873216 .
  3. ↑ Proceedings of the ITAT 2008, Information Technologies - Applications and Theory, Hrebienok, Slovakia, pp. 23-26, září 2008. ISBN 978-80-969184-8-5
  4. ↑ FRANZ, Alex, BRANTS, Thorsten. Oficiální blog výzkumu Google: Všechny naše N-gramy patří vám Archivováno 17. října 2006 na Wayback Machine . Čtvrtek 3. srpna 2006 v 8.3.2006 11:26:00. Vytvořený základ N-gramů je v prodeji ve formě 5 DVD.
  5. ↑ M. Nagao a S. Mori. Nová metoda N-gramové statistiky pro velký počet n a automatickou extrakci slov a frází z velkých textových dat japonštiny. In Proceedings of the 15th International Conference on Computational Linguistics (COLING 1994), Kyoto, Japan, 1994.
  6. ↑ 1 2 Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh a Liliana Chanona-Hernández. N-gramy založené na syntaktické závislosti jako klasifikační prvky. LNAI 7630, str. 1-11, 2012.
  7. ↑ Grigori Sidorov. N-gramy založené na syntaktické závislosti v automatické angličtině založené na pravidlech jako oprava gramatiky druhého jazyka. International Journal of Computational Linguistics and Applications, sv. 4, č. 2, str. 169-188, 2013.
  8. ↑ Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh a Liliana Chanona-Hernández. Syntaktické N-gramy jako funkce strojového učení pro zpracování přirozeného jazyka. Expertní systémy s aplikacemi, sv. 41, č. 3, str. 853-860, DOI 10.1016/j.eswa.2013.08.015 Archivováno 24. září 2015 ve Wayback Machine .