N-gram

N-gram  er en sekvens af n elementer [1] . Set fra et semantisk synspunkt kan det være en sekvens af lyde, stavelser, ord eller bogstaver. I praksis er N-grammet mere almindeligt som en række ord, stabile sætninger kaldes kollokation . En sekvens af to på hinanden følgende elementer kaldes ofte et diggram , en sekvens af tre elementer kaldes et trigram . Mindst fire eller flere elementer er angivet som et N-gram, N erstattes af antallet af på hinanden følgende elementer.

Brug af N-gram

Generel brug af N-gram

N-gram som helhed finder deres anvendelse inden for et bredt videnskabsområde. De kan for eksempel anvendes inden for teoretisk matematik , biologi , kartografi og også i musik . De mest almindelige anvendelser af N-gram omfatter følgende områder:

N-gram er også meget brugt i naturlig sprogbehandling .

Brug af N-gram til behov for naturlig sprogbehandling

Inden for naturlig sprogbehandling bruges N-gram primært til forudsigelse baseret på probabilistiske modeller . N-gram-modellen beregner sandsynligheden for det sidste ord i et N-gram, hvis alle de foregående er kendte. Når man bruger denne tilgang til sprogmodellering, antages det, at hvert ords udseende kun afhænger af de foregående ord [2] .

En anden anvendelse af N-gram er plagiatdetektion . Hvis man deler teksten op i flere små fragmenter, repræsenteret ved N-gram, kan de let sammenlignes med hinanden og dermed opnå graden af ​​lighed i de analyserede dokumenter [3] . N-gram bruges ofte med succes til at kategorisere tekst og sprog. Derudover kan de bruges til at skabe funktioner, der giver dig mulighed for at få viden fra tekstdata. Ved at bruge N-gram kan man effektivt finde kandidater til at erstatte fejlstavede ord.

Et eksempel på en bigrammodel

Formålet med at bygge N-gram modeller er at bestemme sandsynligheden for at bruge en given sætning. Denne sandsynlighed kan formelt angives som sandsynligheden for forekomst af en række ord i et bestemt korpus (sæt af tekster). For eksempel kan sandsynligheden for sætningen "lykke er fornøjelse uden anger" beregnes som produktet af sandsynligheden for hvert af ordene i denne sætning:

P = P(lykke) * P(der er|lykke) * P(fornøjelse|lykke er) * P(uden|lykke er fornøjelse) * P(omvendelse|lykke er fornøjelse uden)

For at bestemme P(lykke), skal du tælle, hvor mange gange dette ord forekommer i teksten, og dividere denne værdi med det samlede antal ord. At beregne sandsynligheden P(omvendelse|lykke er fornøjelse uden) er vanskeligere. For at forenkle denne opgave antager vi, at sandsynligheden for et ord i en tekst kun afhænger af det foregående ord. Derefter vil vores formel til beregning af sætningen have følgende form:

P = P(lykke) * P(har|lykke) * P(fornøjelse|har) * P(uden|fornøjelse) * P(anger|uden)

At beregne den betingede sandsynlighed P(er|lykke) er let. For at gøre dette tæller vi antallet af par 'lykke' og dividerer med antallet af ord 'lykke' i teksten.

Som et resultat, hvis vi tæller alle ordpar i en eller anden tekst, kan vi beregne sandsynligheden for en vilkårlig sætning. Dette sæt af beregnede sandsynligheder vil være bigrammodellen.

Googles forskningsprojekter

Googles forskningscentre har brugt N-gram-modeller til en bred vifte af forskning og udvikling. Disse omfatter projekter såsom statistisk oversættelse fra et sprog til et andet, talegenkendelse , stavekorrektion, informationsudtrækning og mere. Til formålet med disse projekter blev der brugt tekstkorpus indeholdende adskillige billioner ord.

Google besluttede at skabe sin egen uddannelsesbygning. Projektet hedder Google teracorpus og indeholder 1.024.908.267.229 ord indsamlet fra offentlige hjemmesider [4] .

Metoder til udtrækning af N-gram

På grund af den hyppige brug af N-gram til at løse forskellige problemer, er en pålidelig og hurtig algoritme nødvendig for at udtrække dem fra teksten. Et passende N-gram-udtræksværktøj skal kunne arbejde med ubegrænset tekststørrelse, arbejde hurtigt og udnytte de tilgængelige ressourcer effektivt. Der er flere metoder til at udtrække N-gram fra tekst. Disse metoder er baseret på forskellige principper:

Syntaktiske N-gram

Syntaktiske N-gram er N-gram defineret af stier i syntaktiske afhængighedstræer eller komponenttræer, snarere end af tekstens lineære struktur [6] [7] . For eksempel kan sætningen: "Økonomiske nyheder har ringe indflydelse på de finansielle markeder" konverteres til syntaktiske N-gram, efter træstrukturen af ​​dets afhængighedsforhold : nyheder-økonomiske, indvirkning-mindre, indvirkning-på-markeder-finansielle, og andre [6] .

Syntaktiske N-gram afspejler den syntaktiske struktur i modsætning til lineære N-gram og kan bruges i de samme applikationer som lineære N-gram, herunder som funktioner i en vektormodel. Brugen af ​​syntaktiske N-gram giver bedre resultater til at løse visse problemer end brugen af ​​standard N-gram, for eksempel til at bestemme forfatterskab [8] .

Se også

Noter

  1. ↑ Proceedings of the 7th Annual Conference ZNALOSTI 2008, Bratislava, Slovakiet, s. 54-65, februar 2008. ISBN 978-80-227-2827-0 .
  2. ↑ Jurafsky, D. og Martin, JH Tale- og sprogbehandling: En introduktion til naturlig sprogbehandling, beregningslingvistik og talegenkendelse. - Pearson Prentice Hall, 2009. - 988 s. — ISBN 9780131873216 .
  3. ↑ Proceedings of the ITAT 2008, Information Technologies - Applications and Theory, Hrebienok, Slovakiet, pp. 23-26, september 2008. ISBN 978-80-969184-8-5
  4. ↑ FRANZ, Alex, BRANTS, Thorsten. Officiel Google Research Blog: All Our N-gram are Belong to You Arkiveret 17. oktober 2006 på Wayback Machine . Torsdag den 3. august 2006 kl. 8/03/2006 11:26:00. Den skabte base af N-gram er til salg i form af 5 DVD.
  5. ↑ M. Nagao og S. Mori. En ny metode til N-gram-statistik for stort antal n og automatisk udtrækning af ord og sætninger fra store tekstdata fra japansk. I 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 og Liliana Chanona-Hernández. Syntaktisk afhængighedsbaseret N-gram som klassifikationsfunktioner. LNAI 7630, s. 1-11, 2012.
  7. ↑ Grigori Sidorov. Syntaktisk afhængighedsbaseret N-gram i regelbaseret automatisk engelsk som andetsprogs grammatikkorrektion. International Journal of Computational Linguistics and Applications, Vol. 4, nr. 2, s. 169-188, 2013.
  8. ↑ Grigori Sidorov, Francisco Velasquez, Efstathios Stamatatos, Alexander Gelbukh og Liliana Chanona-Hernández. Syntaktiske N-grammer som maskinlæringsfunktioner til naturlig sprogbehandling. Ekspertsystemer med applikationer, Vol. 41, nr. 3, s. 853-860, DOI 10.1016/j.eswa.2013.08.015 Arkiveret 24. september 2015 på Wayback Machine .