N-gram - N-gram

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Únor 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Některé n-gramy se často vyskytují v názvech publikací o Koronavirové onemocnění 2019.

V polích výpočetní lingvistika a pravděpodobnost, an n-gram je souvislá posloupnost n položky z daného vzorek textu nebo řeči. Položky mohou být fonémy, slabiky, písmena, slova nebo základní páry podle aplikace. The n-gramy se obvykle shromažďují od a text nebo řečový korpus. Pokud jsou položkami slova, n-gramy mohou také být volány pásový opar^{[je zapotřebí objasnění ]}.^[1]

Použitím Latinské číselné předpony, an n-gram o velikosti 1 se označuje jako „unigram“; velikost 2 je „bigram „(nebo méně často„ digram “); velikost 3 je„trigram ". Anglická základní čísla jsou někdy používány, např. „čtyři gramy“, „pět gramů“ atd. Ve výpočetní biologii, a polymer nebo oligomer známé velikosti se nazývá a k-mer místo n-gram, s konkrétními jmény pomocí Řecké číselné předpony jako „monomer“, „dimer“, „trimer“, „tetramer“, „pentamer“ atd., nebo anglická základní čísla, „one-mer“, „two-mer“, „three-mer“ atd.

Aplikace

An n-gramový model je typ pravděpodobnosti jazykový model pro predikci další položky v takové posloupnosti ve formě (n - 1) –objednávka Markovův model.^[2] n-gramové modely jsou nyní široce používány v pravděpodobnost, teorie komunikace, výpočetní lingvistika (například statistické zpracování přirozeného jazyka ), výpočetní biologie (například biologický sekvenční analýza ), a komprese dat. Dvě výhody n-gramové modely (a algoritmy, které je používají) jsou jednoduchost a škálovatelnost - s většími n, model může uložit více kontextů s dobře pochopeným časoprostorový kompromis, což umožňuje efektivní zvětšení malých experimentů.

Příklady

Obrázek 1 ukazuje několik příkladných sekvencí a odpovídající 1-gramové, 2-gramové a 3-gramové sekvence.

Zde jsou další příklady; jedná se o 3 gramy a 4 gramy na úrovni slov (a počet jejich opakování) od Googlu n-gramový korpus.^[3]

3 gramy

• sběratelské předměty z keramiky (55)
• sběratelské předměty z keramiky jemné (130)
• keramika shromážděná (52)
• keramika sběratelská keramika (50)
• vaření keramických sběratelských předmětů (45)

4 gramy

• sloužit jako příchozí (92)
• slouží jako inkubátor (99)
• sloužit jako nezávislý (794)
• slouží jako index (223)
• slouží jako indikace (72)
• slouží jako indikátor (120)

n-gramové modely

An n-gramový model modeluje sekvence, zejména přirozené jazyky, pomocí statistických vlastností n-gramy.

Tuto myšlenku lze vysledovat až k experimentu Claude Shannon pracuje v teorie informace. Shannon položil otázku: vzhledem k posloupnosti písmen (například posloupnost „for ex“), co je to pravděpodobnost dalšího dopisu? Z tréninkových dat lze odvodit a rozdělení pravděpodobnosti pro další písmeno s historií velikosti ${ displaystyle n}$: A = 0.4, b = 0.00001, C = 0, ....; kde jsou pravděpodobnosti všech možných „dalších písmen“ 1,0.

Stručněji, an n-gramový model předpovídá ${ displaystyle x_ {i}}$ na základě ${ displaystyle x_ {i- (n-1)}, tečky, x_ {i-1}}$. Pravděpodobně to tak je ${ displaystyle P (x_ {i} mid x_ {i- (n-1)}, tečky, x_ {i-1})}$. Při použití pro jazykové modelování, jsou vytvořeny předpoklady nezávislosti, takže každé slovo závisí pouze na posledním n - 1 slova. Tento Markovův model se používá jako aproximace skutečného základního jazyka. Tento předpoklad je důležitý, protože výrazně zjednodušuje problém odhadu jazykového modelu z dat. Z důvodu otevřené povahy jazyka je navíc běžné seskupovat slova neznámá pro jazykový model.

Všimněte si, že v jednoduchém n-gramový jazykový model, pravděpodobnost slova, podmíněný určitým počtem předchozích slov (jedno slovo v modelu bigram, dvě slova v modelu trigram atd.), lze popsat jako následující kategorické rozdělení (často nepřesně nazývané „multinomiální distribuce ").

V praxi se rozdělení pravděpodobnosti vyhlazuje přiřazením nenulových pravděpodobností neviditelným slovům nebo n-gramy; vidět vyhlazovací techniky.

Aplikace a úvahy

n-gramové modely jsou široce používány ve statistice zpracování přirozeného jazyka. v rozpoznávání řeči, fonémy a sekvence fonémů jsou modelovány pomocí a n-gramová distribuce. Pro analýzu jsou slova modelována tak, že každá z nich n-gram se skládá z n slova. Pro jazyková identifikace, sekvence postavy /grafémy (např., písmena abecedy ) jsou modelovány pro různé jazyky.^[4] U sekvencí znaků jsou 3 gramy (někdy označované jako „trigramy“), které lze vygenerovat z „dobrého rána“, „goo“, „ood“, „od“, „dm“, „mo“, „mor "a tak dále, počítání mezerového znaku jako gramu (někdy je začátek a konec textu modelován explicitně, s přidáním" _ ⁠_g "," _go "," ng_ "a" g_ ⁠_ "). Pro posloupnosti slov jsou trigramy (šindele), které lze generovat z „psa vonícího jako skunk“, „# pes“, „pes voněl“, „pes voněl jako“, „voněl jako“, „jako skunk "a" skunk # ".

Praktici^{[SZO? ]} více zajímající se o víceslovné výrazy by mohly předzpracovat řetězce k odstranění mezer.^{[SZO? ]} Mnozí se jednoduše zhroutí mezery do jednoho prostoru při zachování značek odstavců, protože mezery jsou často buď prvkem stylu psaní, nebo zavádějí rozložení nebo prezentaci, které metodika predikce a dedukce nevyžaduje. Interpunkce se také běžně snižuje nebo odstraňuje předzpracováním a často se používá ke spuštění funkčnosti.

n-gramy lze také použít pro sekvence slov nebo téměř jakýkoli typ dat. Například se používají k extrakci funkcí pro shlukování velkých souborů satelitních snímků Země a k určení, z jaké části Země konkrétní snímek pochází.^[5] Byli také velmi úspěšní jako první průchod při hledání genetických sekvencí a při identifikaci druhů, z nichž pocházejí krátké sekvence DNA.^[6]

n-gramové modely jsou často kritizovány, protože jim chybí explicitní vyjádření závislosti na velké vzdálenosti. Je to proto, že jediný explicitní rozsah závislostí je (n - 1) žetony pro n-gramový model, a protože přirozené jazyky obsahují mnoho případů neomezených závislostí (např wh-pohyb ), to znamená, že an n-gramový model nemůže v zásadě rozlišit neomezené závislosti od šumu (protože korelace s dlouhým dosahem exponenciálně klesají se vzdáleností pro jakýkoli model Markov). Z tohoto důvodu, n-gramové modely neměly velký vliv na lingvistickou teorii, kde součástí explicitního cíle je modelovat takové závislosti.

Další kritika, která byla učiněna, je, že Markovovy modely jazyka, včetně n-gramové modely, výslovně nezachycují rozdíl výkon / kompetence. To je proto, že n-gramové modely nejsou určeny k modelování jazykových znalostí jako takových a nevyžadují žádné nároky na to, aby byly (i potenciálně) úplnými modely jazykových znalostí; místo toho se používají v praktických aplikacích.

V praxi, nUkázalo se, že -gramové modely jsou extrémně účinné při modelování jazykových dat, což je základní součást moderních statistik Jazyk aplikace.

Většina moderních aplikací, na které se spoléhá n-gramové modely, jako např strojový překlad nespoléhejte se výhradně na tyto modely; místo toho obvykle také začleňují Bayesovský závěr. Moderní statistické modely se obvykle skládají ze dvou částí, a předchozí distribuce popisující inherentní pravděpodobnost možného výsledku a funkce pravděpodobnosti slouží k posouzení slučitelnosti možného výsledku s pozorovanými údaji. Když se použije jazykový model, použije se jako součást předchozí distribuce (např. K měření inherentní „dobroty“ možného překladu), a přesto často není jedinou součástí této distribuce.

Ručně vyrobené funkce používají se také různé druhy, například proměnné, které představují pozici slova ve větě nebo obecné téma diskurzu. Kromě toho se často používají funkce založené na struktuře potenciálního výsledku, například syntaktické úvahy. Tyto funkce se také používají jako součást funkce pravděpodobnosti, která využívá pozorovaná data. Do těchto znaků lze zahrnout konvenční lingvistickou teorii (i když v praxi je vzácné, že jsou začleněny funkce specifické pro generativní nebo jiné konkrétní teorie gramatiky, jako výpočetní lingvisté mají tendenci být „agnostik“ vůči jednotlivým teoriím gramatiky^{[Citace je zapotřebí ]}).

Slova mimo slovní zásobu

Problémem při používání jazykových modelů n-gram jsou slova mimo slovní zásobu (OOV). Setkávají se s nimi výpočetní lingvistika a zpracování přirozeného jazyka když vstup obsahuje slova, která nebyla během jeho přípravy ve slovníku nebo databázi systému. Ve výchozím nastavení se při odhadu jazykového modelu použije celá pozorovaná slovní zásoba. V některých případech může být nutné odhadnout jazykový model se specifickou pevnou slovní zásobou. V takovém scénáři jsou n-gramy v korpus které obsahují slovo mimo slovní zásobu, jsou ignorovány. Pravděpodobnosti n-gramů jsou vyhlazeny přes všechna slova ve slovníku, i když nebyla dodržena.^[7]

V některých případech je však zásadní výslovně modelovat pravděpodobnost slov mimo slovní zásobu zavedením speciálního tokenu (např. <unk>) do slovníku. Slova mimo slovní zásobu v korpusu jsou účinně nahrazena tímto speciálním tokenem předtím, než se kumuluje počet n-gramů. Pomocí této možnosti je možné odhadnout pravděpodobnosti přechodu n-gramů zahrnujících slova mimo slovní zásobu.^[8]

n-gramy pro přibližnou shodu

n-gramy lze také použít pro efektivní přibližnou shodu. Převáděním sekvence položek na sadu n-gramů, může být vložen do a vektorový prostor, což umožňuje efektivní porovnání sekvence s jinými sekvencemi. Například pokud převedeme řetězce s pouze písmeny v anglické abecedě na jednoznakové 3 gramy, dostaneme a ${ displaystyle 26 ^ {3}}$-dimenzionální prostor (první dimenze měří počet výskytů „aaa“, druhá „aab“ atd. pro všechny možné kombinace tří písmen). Pomocí tohoto vyjádření přijdeme o informace o řetězci. Například řetězce „abc“ a „bca“ dávají vzniknout přesně stejnému 2-gramovému „bc“ (ačkoli {„ab“, „bc“} zjevně není totéž jako {„bc“, „ca“ }). Empiricky však víme, že pokud mají dva řetězce skutečného textu podobnou vektorovou reprezentaci (měřeno pomocí kosinová vzdálenost ), pak si budou pravděpodobně podobné. Další metriky byly také použity pro vektory n-gramy s různými, někdy lepšími výsledky. Například, z-skóre byly použity k porovnání dokumentů zkoumáním počtu směrodatných odchylek n-gram se liší od svého průměrného výskytu ve velké sbírce, nebo textový korpus, dokumentů (které tvoří vektor „pozadí“). V případě malého počtu se g-skóre (také známý jako g-test ) může poskytnout lepší výsledky při porovnání alternativních modelů.

Je také možné zaujmout principiálnější přístup ke statistikám n-gramy, modelování podobnosti jako pravděpodobnost, že dva řetězce pocházejí ze stejného zdroje přímo z hlediska problému v Bayesovský závěr.

nlze také použít vyhledávání založené na gramech detekce plagiátů.

Další aplikace

n-gramy nacházejí uplatnění v několika oblastech informatiky, výpočetní lingvistika a aplikovaná matematika.

Byli zvyklí na:

• design jádra které umožňují strojové učení algoritmy jako např podporovat vektorové stroje učit se z dat řetězce
• najít pravděpodobné kandidáty na správné hláskování chybně napsaného slova
• zlepšit kompresi v kompresní algoritmy kde vyžaduje malá oblast dat n-gramy větší délky
• posoudit pravděpodobnost, že se daná posloupnost slov objeví v textu zájmového jazyka v systémech rozpoznávání vzorů, rozpoznávání řeči, OCR (optické rozpoznávání znaků ), Inteligentní rozpoznávání znaků (ICR ), strojový překlad a podobné aplikace
• zlepšit vyhledávání v vyhledávání informací systémy, pokud se předpokládá, že najdete podobné „dokumenty“ (termín, u kterého se běžný význam někdy natáhne, v závislosti na souboru dat) s jediným dokumentem dotazu a databází referenčních dokumentů
• zlepšit výkon vyhledávání v genetické sekvenční analýze jako v VÝBUCH rodina programů
• identifikovat jazyk, ve kterém je text, nebo druh, ze kterého byla odebrána malá sekvence DNA
• náhodně předpovídat písmena nebo slova za účelem vytváření textu, jako v disociovaný tisk algoritmus.
• dešifrování

Místo potřebné pro n-gram

Zvažte n-gram, kde jednotkami jsou znaky a text s t postavy. Prostor to n-gram vyžaduje je exponenciální:

${ displaystyle n (t-2 (n-1)) + součet _ {i = 1} ^ {n-1} 2i qquad n, t v { mathcal {N}}}$

Parabolu lze vložit do každého diskrétního datového bodu získáním tří párů souřadnic a řešením lineárního systému se třemi proměnnými, což vede k obecnému vzorci:

${ displaystyle -n ^ {2} + (t + 1) n}$

Kompenzace zkreslení proti variantě

Chcete-li vybrat hodnotu pro n v n-gramový model, je nutné najít správný kompromis mezi stabilitou odhadu a jeho vhodností. To znamená, že trigram (tj. Trojice slov) je běžná volba u velkých tréninkových korpusů (miliony slov), zatímco bigram se často používá u menších.

Vyhlazovací techniky

Existují problémy s vyvážením řídké gramy (například pokud se v tréninkových datech objevilo vlastní jméno) a časté gramy. Rovněž budou uvedeny položky, které nejsou uvedeny v tréninkových datech a pravděpodobnost 0,0 bez vyhlazení. Pro neviditelné, ale věrohodné údaje ze vzorku lze zavést pseudoúčty. Pseudoúčty jsou obecně motivovány na základě Bayesianů.

V praxi je nutné hladký rozdělení pravděpodobnosti také přiřazením nenulových pravděpodobností neviditelným slovům nebo n-gramy. Důvodem je, že modely odvozené přímo z nPočty frekvence gramů mají vážné problémy, když jsou konfrontovány s jakýmkoli n-gramy, které ještě nebyly výslovně vidět - problém s nulovou frekvencí. Používají se různé metody vyhlazování, od jednoduchého vyhlazení typu „add-one“ (Laplace) (přiřadit počet 1 k neviditelnému n-gramy; vidět Pravidlo posloupnosti ) k sofistikovanějším modelům, jako je Good – Turingova sleva nebo back-off modely. Některé z těchto metod jsou ekvivalentní přiřazení a předchozí distribuce k pravděpodobnostem n-gramy a použití Bayesovský závěr vypočítat výsledek zadní n-gramové pravděpodobnosti. Sofistikovanější vyhlazovací modely však obvykle nebyly odvozeny tímto způsobem, ale místo toho prostřednictvím nezávislých úvah.

• Lineární interpolace (např Vážený průměr unigramu, bigramu a trigramu)
• Dobrý – Turing diskontování
• Witten – Bell diskontování
• Lidstone je vyhlazování
• Katzův back-off model (trigram)
• Kneser – Ney vyhlazování

Přeskočit gram

V oblasti výpočetní lingvistika, zejména jazykové modelování, skip-gramy^[9] jsou zobecněním n-gramy, ve kterých komponenty (obvykle slova) nemusí být v uvažovaném textu za sebou, ale mohou zanechat mezery, které jsou přeskočeno přes.^[10] Poskytují jeden způsob překonání problém s datovou sparitou nalezeno u konvenčních n-gramová analýza.

Formálně an n-gram je po sobě jdoucí posloupnost délky n nějaké sekvence žetonů w₁ … w_n. A k-přeskočit-n-gram je délka-n posloupnost, kde se komponenty vyskytují maximálně na dálku k od sebe navzájem.

Například ve vstupním textu:

déšť ve Španělsku padá hlavně na rovinu

sada 1-skip-2-gramů zahrnuje všechny bigramy (2-gramy) a navíc subsekvence

v, déšť Španělsko, při pádech, Španělsko hlavně, padá na, hlavně, a na rovinu.

Syntaktický n-gramy

Syntaktický n-gramy jsou n-gramy definované cestami v syntaktických závislostech nebo stromech složek, spíše než lineární struktura textu.^[11][12][13] Například větu „ekonomické zprávy mají malý vliv na finanční trhy“ lze transformovat na syntaktickou n-gramy sledující jeho stromovou strukturu závislostní vztahy: novinky-ekonomický, malý účinek, účinek na trhy-finanční.^[11]

Syntaktický n-gramy mají odrážet syntaktickou strukturu věrněji než lineárně n-gramy a mají mnoho stejných aplikací, zejména jako funkce ve vektorovém vesmírném modelu. Syntaktický n-gramy pro určité úkoly poskytují lepší výsledky než použití standardu n-gramy, například pro přidělování autorství.^[14]

Další typ syntaktické n-gramy jsou součástí řeči n-gramy, definované jako souvislé překrývající se subsekvence s pevnou délkou, které jsou extrahovány z textových sekvencí části řeči. Část mluvy n-gramy mají několik aplikací, nejčastěji při získávání informací.^[15]

Viz také

• Kolokace
• Skrytý Markovův model
• n-tice
• Řetězec jádra
• MinHash
• Extrakce funkcí
• Nejdelší běžný problém s podřetězcem

Reference

Další čtení

• Christopher D. Manning, Hinrich Schütze, Základy statistického zpracování přirozeného jazyka, MIT Press: 1999. ISBN  0-262-13360-1.
• White, Owen; Dunning, Ted; Sutton, Granger; Adams, Mark; Venter, J.Craig; Fields, Chris (1993). „Algoritmus řízení kvality pro projekty sekvenování DNA“. Výzkum nukleových kyselin. 21 (16): 3829–3838. doi:10.1093 / nar / 21.16.3829. PMC  309901. PMID  8367301.
• Frederick J. Damerau, Markovovy modely a lingvistická teorie. Mouton. Haag, 1971.
• Figueroa, Alejandro; Atkinson, John (2012). „Kontextové jazykové modely pro hodnocení odpovědí na otázky týkající se definice přirozeného jazyka“. Výpočetní inteligence. 28 (4): 528–548. doi:10.1111 / j.1467-8640.2012.00426.x.
• Brocardo, Marcelo Luiz; Issa Traore; Sherif Saad; Isaac Woungang (2013). Ověření autorství pro krátké zprávy pomocí stylometrie (PDF). Mezinárodní IEEE Konference o počítačových, informačních a telekomunikačních systémech (CITS).

externí odkazy

• Google Book Google n-gramový prohlížeč a Web n-gramová databáze (Září 2006)
• Web společnosti Microsoft n-gramová služba
• STATOPERÁTOR N-gramy Projekt vážený n-gramový prohlížeč pro každou doménu v Alexa Top 1M
• 1 000 000 nejčastějších 2,3,4,5 gramů ze 425 milionů slov Korpus současné americké angličtiny
• Prohlížeč hudebních programů Peachnote
• Stochastické jazykové modely (n-Gram) Specifikace (W3C)
• Poznámky Michaela Collinsa n-Gramové jazykové modely
• OpenRefine: Shlukování do hloubky