n -gram - n-gram

Noen n-gram finnes ofte i titler på publikasjoner om Coronavirussykdom 2019 .

Når det gjelder beregningslingvistikk og sannsynlighet , er et n -gram (noen ganger også kalt Q -gram ) en sammenhengende sekvens av n elementer fra et gitt eksempel på tekst eller tale. Elementene kan være fonemer , stavelser , bokstaver , ord eller basepar i henhold til applikasjonen. Den n -grams vanligvis er hentet fra en tekst eller tale corpus . Når elementene er ord, kan $n$ -gram også kalles helvetesild .

Ved bruk av latinske numeriske prefikser blir et n -gram i størrelse 1 referert til som et "unigram"; størrelse 2 er en " bigram " (eller, mindre vanlig, en "digram"); størrelse 3 er et " trigram ". Noen ganger brukes engelske kardinalnumre , f.eks. "Fire gram", "fem gram" og så videre. I beregningsbiologi kalles en polymer eller oligomer av en kjent størrelse en k -mer i stedet for et n -gram, med spesifikke navn ved hjelp av greske numeriske prefikser som "monomer", "dimer", "trimer", "tetramer", "pentamer", etc., eller engelske kardinalnumre, "one-mer", "two-mer", "three-mer", etc.

applikasjoner

En n -grammodell er en type sannsynlig språkmodell for å forutsi neste element i en slik sekvens i form av en ( n -1) -ordre Markov -modell . n -grammodeller er nå mye brukt i sannsynlighet , kommunikasjonsteori , beregningslingvistikk (for eksempel statistisk behandling av naturlig språk ), beregningsbiologi (for eksempel biologisk sekvensanalyse ) og datakomprimering . To fordeler med n -grammodeller (og algoritmer som bruker dem) er enkelhet og skalerbarhet -med større n kan en modell lagre mer kontekst med et godt forstått mellomrom mellom rom og tid , slik at små eksperimenter kan skalere effektivt.

Eksempler

Figur 1 n -gram eksempler fra ulike disipliner
Felt	Enhet	Eksempelsekvens	1 gram sekvens	2 gram sekvens	3 gram sekvens
Spektakulært navn			unigram	bigram	trigram
Rekkefølgen på den resulterende Markov -modellen			0	1	2
Proteinsekvensering	aminosyre	... Cys-Gly-Leu-Ser-Trp ...	…, Cys, Gly, Leu, Ser, Trp,…	…, Cys-Gly, Gly-Leu, Leu-Ser, Ser-Trp,…	…, Cys-Gly-Leu, Gly-Leu-Ser, Leu-Ser-Trp,…
DNA -sekvensering	basepar	... AGCTTCGA ...	…, A, G, C, T, T, C, G, A,…	…, AG, GC, CT, TT, TC, CG, GA,…	…, AGC, GCT, CTT, TTC, TCG, CGA,…
Computational lingvistikk	karakter	…å være eller ikke være…	…, å være eller ikke være, …	…, Til, o_, _b, be, e_, _o, eller, r_, _n, nei, ot, t_, _t, til, o_, _b, be,…	…, To_, o_b, _be, be_, e_o, _or, or_, r_n, _no, not, ot_, t_t, _to, to_, o_b, _be,…
Computational lingvistikk	ord	… å være eller ikke være …	…, å være eller ikke være, …	..., å være, være eller, eller ikke, ikke å, å være, ...	…, Å være eller, være eller ikke, eller ikke å, ikke å være,…

Figur 1 viser flere eksempelsekvenser og de tilsvarende 1-gram, 2-gram og 3-gram-sekvensene.

Her er ytterligere eksempler; disse er ordnivå 3-gram og 4-gram (og tellinger av antall ganger de dukket opp) fra Google n -gram-korpuset.

3 gram

samleobjekter i keramikk (55)
keramikk samleobjekter fint (130)
keramikk samlet av (52)
keramikk keramikk (50)
keramikk samleobjekter matlaging (45)

4 gram

tjene som innkommende (92)
tjene som inkubator (99)
tjene som uavhengige (794)
tjene som indeks (223)
tjene som indikasjon (72)
tjene som indikator (120)

n -gram modeller

En n -gram modell modellerer sekvenser, særlig naturlige språk, ved bruk av de statistiske egenskapene til n -gram.

Denne ideen kan spores til et eksperiment av Claude Shannons arbeid med informasjonsteori . Shannon stilte spørsmålet: gitt en bokstavssekvens (for eksempel sekvensen "for eks"), hva er sannsynligheten for den neste bokstaven? Fra treningsdata kan man utlede en sannsynlighetsfordeling for neste bokstav gitt en historikk med størrelse : a = 0,4, b = 0,00001, c = 0, ....; hvor sannsynligheten for alle mulige "neste bokstaver" summerer til 1,0. ${\ displaystyle n}$

Mer presist, en n -gram modell forutsier basert på . I sannsynlighetshensyn er dette . Når det brukes til språkmodellering , antas uavhengighetsforutsetninger slik at hvert ord bare er avhengig av de siste n - 1 ordene. Denne Markov -modellen brukes som en tilnærming til det sanne underliggende språket. Denne antagelsen er viktig fordi den massivt forenkler problemet med å estimere språkmodellen ut fra data. I tillegg, på grunn av språkets åpne natur, er det vanlig å gruppere ord som er ukjente for språkmodellen. ${\ displaystyle x_ {i}}$ ${\ displaystyle x_ {i- (n-1)}, \ dots, x_ {i-1}}$ ${\ displaystyle P (x_ {i} \ mid x_ {i- (n-1)}, \ dots, x_ {i-1})}$

Vær oppmerksom på at i en enkel n -gram språkmodell kan sannsynligheten for et ord, betinget av et antall tidligere ord (ett ord i en bigram -modell, to ord i en trigram -modell, etc.) beskrives som å følge en kategorisk fordeling (ofte upresist kalt en " multinomial fordeling ").

I praksis utjevnes sannsynlighetsfordelingene ved å tilordne ikke -null sannsynligheter til usynlige ord eller n -gram; se utjevningsteknikker .

Søknader og hensyn

n -gram -modeller er mye brukt i statistisk behandling av naturlig språk . I talegjenkjenning er fonemer og sekvenser av fonemer modellert ved hjelp av en n -gram -fordeling. For analyse er ord modellert slik at hvert n -gram er sammensatt av n ord. For språkidentifikasjon er sekvenser av tegn / grafemer ( f.eks . Bokstaver i alfabetet ) modellert for forskjellige språk. For sekvenser av tegn er 3-gramene (noen ganger referert til som "trigrammer") som kan genereres fra "god morgen" "goo", "ood", "od", "dm", "mo", "mor "og så videre, telle mellomromstegnet som et gram (noen ganger er begynnelsen og slutten av en tekst eksplisitt modellert, og legger til" _ ⁠_g "," _go "," ng_ "og" g_ ⁠_ "). For ordsekvenser er trigrammer (helvetesild) som kan genereres fra "hunden luktet som en skunk" "# hunden", "hunden luktet", "hunden luktet som", "luktet som en", "som en skunk "og" en skunk #".

Utøvere som er mer interessert i flere ordtermer, kan forbehandle strenger for å fjerne mellomrom. Mange kollapser ganske enkelt mellomrom til et enkelt mellomrom mens de beholder avsnittsmerker, fordi mellomrommet ofte enten er et element i skrivestil eller introduserer layout eller presentasjon som ikke kreves av forutsigelses- og fradragsmetodikken. Tegnsetting blir også ofte redusert eller fjernet ved forbehandling og brukes ofte for å utløse funksjonalitet.

n -gram kan også brukes til ordsekvenser eller nesten alle typer data. For eksempel har de blitt brukt til å trekke ut funksjoner for å samle store sett med satellittjordbilder og for å bestemme hvilken del av jorden et bestemt bilde kom fra. De har også vært veldig vellykkede som det første passet i genetisk sekvens søk og i identifiseringen av arten som korte sekvenser av DNA stammer fra.

n -gram -modeller blir ofte kritisert fordi de mangler noen eksplisitt representasjon av langdistanseavhengighet. Dette er fordi det eneste eksplisitte avhengighetsområdet er ( n -1 ) tokens for en n -grammodell, og siden naturlige språk inneholder mange tilfeller av ubegrensede avhengigheter (for eksempel wh -movement ), betyr dette at en n -gram -modell ikke kan prinsipp skille ubegrensede avhengigheter fra støy (siden langdistanse -korrelasjoner synker eksponentielt med avstand for enhver Markov -modell). Av denne grunn har n -gram -modeller ikke hatt stor innvirkning på språklig teori, der en del av det eksplisitte målet er å modellere slike avhengigheter.

En annen kritikk som har blitt fremsatt er at Markov -språkmodeller , inkludert n -grammodeller, ikke eksplisitt fanger opp ytelsen/kompetansen. Dette er fordi n -gram -modeller ikke er designet for å modellere språkkunnskap som sådan, og gjør ingen påstander om å være (selv potensielt) komplette modeller for språklig kunnskap; i stedet brukes de i praktiske applikasjoner.

I praksis, n er -gram modeller er vist å være svært effektiv i å modellere språkdata, som er en sentral komponent i moderne statistiske språkprogrammer.

De fleste moderne applikasjoner som er avhengige av n -grambaserte modeller, for eksempel maskinoversettelsesprogrammer , stoler ikke utelukkende på slike modeller; i stedet inneholder de vanligvis også bayesisk slutning . Moderne statistiske modeller består vanligvis av to deler, en tidligere fordeling som beskriver den iboende sannsynligheten for et mulig resultat og en sannsynlighetsfunksjon som brukes til å vurdere kompatibiliteten til et mulig resultat med observerte data. Når en språkmodell brukes, brukes den som en del av den tidligere distribusjonen (f.eks. For å måle den iboende "godheten" i en mulig oversettelse), og selv da er den ofte ikke den eneste komponenten i denne fordelingen.

Det brukes også håndlagde funksjoner av forskjellige slag, for eksempel variabler som representerer plasseringen av et ord i en setning eller det generelle temaet for diskurs. I tillegg brukes ofte funksjoner basert på strukturen til det potensielle resultatet, for eksempel syntaktiske hensyn. Slike funksjoner brukes også som en del av sannsynlighetsfunksjonen, som gjør bruk av de observerte dataene. Konvensjonell språklig teori kan inkorporeres i disse trekkene (selv om det i praksis er sjelden at trekk som er spesifikke for generative eller andre spesielle teorier om grammatikk er inkorporert, ettersom beregningslingvister har en tendens til å være "agnostiske" overfor individuelle grammatiske teorier).

Uten ordforråd

Et problem ved bruk av n-gram språkmodeller er ord uten ordforråd (OOV). De oppstår i beregningslingvistikk og behandling av naturlig språk når inngangen inkluderer ord som ikke var tilstede i systemets ordbok eller database under utarbeidelsen. Som standard, når en språkmodell er estimert, brukes hele det observerte ordforrådet. I noen tilfeller kan det være nødvendig å estimere språkmodellen med et bestemt fast ordforråd. I et slikt scenario ignoreres n-grammene i korpuset som inneholder et ord utenfor ordforrådet. N-gram-sannsynlighetene glattes over alle ordene i vokabularet, selv om de ikke ble observert.

Ikke desto mindre er det i noen tilfeller avgjørende å eksplisitt modellere sannsynligheten for ord utenfor ordforrådet ved å introdusere et spesielt tegn (f.eks . ) I vokabularet. Ord utenfor ordforrådet i korpuset erstattes effektivt med dette spesielle -tokenet før n-gram-tellinger kumuleres. Med dette alternativet er det mulig å estimere overgangssannsynligheter for n-gram som involverer ord utenfor ordforrådet.

n -gram for omtrentlig matching

n -gram kan også brukes for effektiv tilnærmet samsvar. Ved å konvertere en sekvens av elementer til et sett med n -gram, kan den bli innebygd i et vektorrom , og dermed tillate at sekvensen kan sammenlignes med andre sekvenser på en effektiv måte. For eksempel, hvis vi konverterer strenger med bare bokstaver i det engelske alfabetet til 3 -gram med ett tegn, får vi et -dimensjonalt mellomrom (den første dimensjonen måler antall forekomster av "aaa", den andre "aab", og så videre for alle mulige kombinasjoner av tre bokstaver). Ved å bruke denne representasjonen mister vi informasjon om strengen. For eksempel gir både strengene "abc" og "bca" opphav til nøyaktig samme 2-gram "bc" (selv om {"ab", "bc"} tydeligvis ikke er det samme som {"bc", "ca" }). Imidlertid vet vi empirisk at hvis to strenger av ekte tekst har en lignende vektorrepresentasjon (målt ved cosinusavstand ), vil de sannsynligvis være like. Andre beregninger har også blitt brukt på vektorer av n -gram med varierende, noen ganger bedre resultater. For eksempel har z -score blitt brukt til å sammenligne dokumenter ved å undersøke hvor mange standardavvik hvert n -gram skiller seg fra gjennomsnittlig forekomst i en stor samling, eller tekstkorpus , av dokumenter (som danner "bakgrunnen" -vektoren). Ved små tellinger kan g-score (også kjent som g-test ) gi bedre resultater for sammenligning av alternative modeller. ${\ displaystyle 26^{3}}$

Det er også mulig å ta en mer prinsipiell tilnærming til statistikken over n -grammer, modellere likhet som sannsynligheten for at to strenger kom fra samme kilde direkte når det gjelder et problem i Bayesian slutning .

n -gram basert søking kan også brukes for plagiat deteksjon .

Andre applikasjoner

n -gram finner bruk på flere områder innen datavitenskap, beregningslingvistikk og anvendt matematikk.

De har vært vant til:

designe kjerner som lar maskinlæringsalgoritmer som støttevektormaskiner lære av strengdata
finne sannsynlige kandidater for riktig stavemåte for et feilstavet ord
forbedre komprimering i komprimeringsalgoritmer der et lite dataområde krever n -gram med større lengde
vurdere sannsynligheten for at en gitt ordsekvens vises i teksten til et språk av interesse i mønstergjenkjenningssystemer, talegjenkjenning , OCR ( optisk tegngjenkjenning ), Intelligent Character Recognition ( ICR ), maskinoversettelse og lignende applikasjoner
forbedre henting i informasjonshentingssystemer når det er håp om å finne lignende "dokumenter" (et begrep som den konvensjonelle betydningen noen ganger strekkes for, avhengig av datasettet) gitt et enkelt spørredokument og en database med referansedokumenter
forbedre hentingsytelsen i genetisk sekvensanalyse som i BLAST -familien av programmer
identifisere språket en tekst er på eller arten en liten sekvens av DNA ble hentet fra
forutsi bokstaver eller ord tilfeldig for å lage tekst, som i den dissosierte pressealgoritmen.
kryptanalyse

Plass kreves for et n -gram

Vurder et n -gram der enhetene er tegn og en tekst med t -tegn, hvor . Det er totalt strenger, hvor hver streng krever mellomrom. Dermed er den totale plassen som kreves for dette n -grammet , som er forenklet til: ${\ displaystyle n, t \ in \ mathbb {N}}$ ${\ displaystyle t-n+1}$ ${\ displaystyle n}$ ${\ displaystyle (t-n+1) \ cdot n}$

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

Bias-mot-varians-avveining

For å velge en verdi for n i en n -gram -modell, er det nødvendig å finne den riktige avveiningen mellom estimatets stabilitet og dets hensiktsmessighet. Dette betyr at trigram (dvs. trillinger av ord) er et vanlig valg med store opplæringskorpora (millioner av ord), mens et bigram ofte brukes med mindre.

Utjevningsteknikker

Det er problemer med balansevekten mellom sjeldne gram (for eksempel hvis et eget navn dukket opp i treningsdataene) og hyppige gram . Også elementer som ikke er sett i treningsdataene, vil bli gitt en sannsynlighet på 0,0 uten utjevning . For usynlige, men sannsynlige data fra en prøve, kan man introdusere pseudocounts . Pseudokounts er generelt motivert på bayesiansk grunnlag.

I praksis er det nødvendig å jevne ut sannsynlighetsfordelingene ved også å tilordne usannsynlige sannsynligheter til usynlige ord eller n -gram. Årsaken er at modellene stammer direkte fra n -gram frekvenstellinger har alvorlige problemer når de blir konfrontert med noen n -grams som ikke eksplisitt blitt sett før - null-frekvens problem . Det brukes forskjellige utjevningsmetoder, fra enkel "add-one" (Laplace) utjevning (tildel 1 til usettede n- programmer; se succession-regelen ) til mer sofistikerte modeller, for eksempel Good-Turing-rabatter eller back-off-modeller . Noen av disse metodene er ekvivalente med å tildele en tidligere fordeling til sannsynligheten for n -gram og bruke Bayesian slutning for å beregne de resulterende posterior n -gram sannsynlighetene. Imidlertid ble de mer sofistikerte utjevningsmodellene vanligvis ikke avledet på denne måten, men i stedet gjennom uavhengige hensyn.

Lineær interpolasjon (f.eks. Å ta det veide gjennomsnittet av unigram, bigram og trigram)
God – Turing rabatt
Witten – Bell rabatter
Lidstones utjevning
Katz back-off-modell (trigram)
Kneser – Ney utjevning

Hopp over gram

Innen beregningslingvistikk , spesielt språkmodellering , er hopp -gram en generalisering av n -gram der komponentene (vanligvis ord) ikke trenger å være sammenhengende i teksten som vurderes, men kan etterlate hull som hoppes over. De gir en måte å overvinne problematikken med data sparsitet funnet med konvensjonell n -gram -analyse. På datasikkerhetsområdet har hopp-gram vist seg å være mer robuste for angrep enn ngram.

Formelt sett er et $n$ -gram en påfølgende undersekvens av lengde $n$ av noen sekvens av tokens $w 1 ... w n$ . En $k$ -skip- $n$ -gram er et lengde- $n$ delsekvens hvor komponentene forekommer i en avstand på høyst $k$ fra hverandre.

For eksempel i inndatateksten:

regnet i Spania faller hovedsakelig på sletten

settet med 1-hopp-2-gram inneholder alle bigrammene (2-gram), og i tillegg undersekvensene

in , regn Spania , i falls , Spania hovedsakelig , faller på , hovedsakelig , og på sletten .

Syntaktisk n -gram

Syntaktiske n -grammer er n -grammer definert av baner i syntaktisk avhengighet eller bestanddeler i stedet for tekstens lineære struktur. For eksempel kan setningen "økonomiske nyheter har liten effekt på finansmarkeder" omdannes til syntaktiske n -grammer etter trestrukturen i dets avhengighetsforhold : nyhetsøkonomisk , effekt-liten, effekt-på-markeder-finansiell.

Syntaktiske n -grammer er ment å reflektere syntaktisk struktur mer trofast enn lineære n -programmer, og har mange av de samme programmene, spesielt som funksjoner i en vektorrommodell. Syntaktisk n -gram for visse oppgaver gir bedre resultater enn bruk av standard n -gram, for eksempel for forfatterskapstilskrivning.

En annen type syntaktiske n -grammer er n- grammatikkord, definert som sammenhengende overlappende delsekvenser med fast lengde som er hentet fra tekst-sekvenser av tekst. Dele -av-tale n -grammer har flere applikasjoner, oftest i informasjonsinnhenting.

Se også

Referanser

Videre lesning

Christopher D. Manning, Hinrich Schütze, Foundations of Statistical Natural Language Processing , MIT Press: 1999. ISBN 0-262-13360-1 .
White, Owen; Dunning, Ted; Sutton, Granger; Adams, Mark; Venter, J.Craig; Fields, Chris (1993). "En kvalitetskontrollalgoritme for dna -sekvenseringsprosjekter" . Forskning på nukleinsyrer . 21 (16): 3829–3838. doi : 10.1093/nar/21.16.3829 . PMC 309901 . PMID 8367301 .
Frederick J. Damerau, Markov Models and Linguistic Theory . Mouton. Haag, 1971.
Figueroa, Alejandro; Atkinson, John (2012). "Kontekstuelle språkmodeller for rangering av svar på spørsmål om naturlig språkdefinisjon" . Computational Intelligence . 28 (4): 528–548. doi : 10.1111/j.1467-8640.2012.00426.x . S2CID 27378409 .
Brocardo, Marcelo Luiz; Issa Traore; Sherif Saad; Isaac Woungang (2013). Forfatterverifisering for korte meldinger ved hjelp av stylometri (PDF) . IEEE internasjonale flyplass Konferanse om data-, informasjons- og telekommunikasjonssystemer (CITS).

Languages

In other projects