Stokastisk kontekstfri grammatik ( SCS , også probabilistisk kontekstfri grammatik , VCS ) er en kontekstfri grammatik , hvor hver inferensregel svarer til en sandsynlighed. Sandsynligheden for en slutning defineres som produktet af sandsynligheden for de slutningsregler, den bruger, så nogle slutninger passer bedre til en stokastisk grammatik end andre. SCF-grammatikker udvider CF-grammatikker på samme måde, som skjulte Markov-modeller udvider almindelige grammatikker. SCS-grammatikker er meget udbredt i videnskaben: fra naturlig sprogbehandling til studiet af RNA- molekyler . SCS-grammatikker er en særlig form for vægtet kontekstfri grammatik .
En variant af Kok-Younger-Kasami-algoritmen finder Viterbi-parsingen for en given streng og SCS-grammatik. Viterbi-parsing er den mest sandsynlige afledning fra en streng givet SCS-grammatikken.
Indre-ydre algoritmer, som er analoge med frem og tilbage algoritmer, kan bruges til at beregne den samlede sandsynlighed for alle inferenser svarende til en given streng fra en given SCF grammatik. Dette svarer til sandsynligheden for, at SCF-grammatikken vil generere en given streng, og er intuitivt et mål for en given strengs overensstemmelse med en given grammatik.
Indre-ydre algoritmer kan også bruges til at beregne sandsynligheden for, at en given inferensregel vil blive brugt i vilkårlig inferens for en given streng. Dette bruges til at anvende EM-algoritmen for at opnå de maksimale sandsynligheder for SCS-grammatikken baseret på de træningssekvenser, som SCS-grammatikken skal modellere. Algoritmen ligner den, der bruges til skjulte Markov-modeller.
Kontekstfrie grammatikker blev oprindeligt skabt i et forsøg på at modellere naturlige sprog. Nogle forskere har udvidet denne idé ved at anvende SCS-grammatikken.
Her er et eksempel på en SCS-grammatik med to regler. Hver regel er indledt med en sandsynlighed, der afspejler den relative hyppighed af dens anvendelse.
0,7VP→VNP 0,3 VP → V NP NPUd fra denne grammatik kan vi beregne det forventede antal NP'er genereret fra VP: 0,7 x 1 + 0,3 x 2 = 1,3.
Især bruger nogle talegenkendelsessystemer SCF-grammatikker til at forbedre sandsynlighedstilnærmelse og dermed genkendelseskvalitet.
For nylig har probabilistiske CFG'er spillet en rolle i at forklare tilgængelighedshierarkiet, som forsøger at vise, hvorfor nogle strukturer er sværere at forstå end andre.
Det viste sig, at hvis der er sandsynlighedsoplysninger om mere sandsynlige konstruktioner, så er det muligt at beregne informationsentropien for disse konstruktioner. Hvis mekanismen for opfattelse af syntaks er baseret på begreberne informationsteori, så kan den godt bruge noget, der ligner videokonferencegrammatikker. [en]
CS-grammatikker bruges til at modellere den sekundære struktur af RNA [2] [3] . Den sekundære struktur inkluderer komplementære nukleotider i et enkelt RNA-molekyle. Denne parring er biologisk vigtig for den korrekte funktion af RNA-molekylet. De fleste af disse parringer kan repræsenteres af en CF-grammatik (med undtagelse af pseudoknoter).
Overvej for eksempel følgende grammatik, hvor a, c, g og u repræsenterer nukleotider og S er startkarakteren:
S → aSu | cSg | gSc | USADenne simple CFG repræsenterer et RNA-molekyle, der udelukkende består af to fuldt komplementære regioner, hvor kun kanoniske komplementære par er tilladt (f.eks. AU og CG).
Ved at tilføje sandsynligheder til mere komplekse CFG'er er det muligt at modellere baser eller basepar, der mere eller mindre matcher den forventede form af RNA-molekylet. SCS-grammatikker bruges til at modellere sekvenser i RNA-genfamilier i Rfam-databasen og søge genomsekvenser for sandsynlige medlemmer af disse familier. SCS-grammatikker er også blevet brugt til at søge efter RNA-gener ved hjælp af komparativ genomik. I dette arbejde blev homologerne af potentielle RNA-gener fra to beslægtede organismer undersøgt ved hjælp af SCS grammatiktilgange for at bestemme, om den sekundære struktur blev bibeholdt. Hvis det er tilfældet, er sekvensen sandsynligvis et RNA-gen, og den sekundære struktur bibeholdes til RNA-genets funktionelle behov. Det er også blevet vist, at SCS-grammatikker kan forudsige den sekundære struktur af et RNA-molekyle svarende til eksisterende tilgange: Sådanne SCS-grammatikker bruges for eksempel af Stemloc-programmet.
Med udgivelsen af Golds teorem i 1967 blev det hævdet, at grammatikerne i naturlige sprog er styret af deterministiske regler, som ikke kan læres af positive eksempler alene. Dette var en del af argumentet om stimulerende fattigdom, der blev introduceret i 1980 og implicit siden Chomskys tidlige arbejde i 1950'erne. Blandt andre argumenter har dette ført til den nativistiske forestilling om, at formerne for grammatik (herunder, i nogle versioner, et komplet konceptuelt leksikon) er indgroet fra fødslen. Denne repræsentation er væsentligt begrænset af GB- og MP-teorierne.
Det skal dog bemærkes, at Golds resultat på indlæringsevne let kan omgås ved at antage, at den lærende enten lærer en næsten perfekt tilnærmelse af det korrekte sprog, eller lærer typiske input frem for vilkårligt fordelte. Faktisk har det vist sig, at blot at modtage input fra taleren, der producerer positive eksempler vilkårligt, snarere end efter en forudbestemt plan, fører til identificerbarhed med en sandsynlighedsgrænse på 1. [4] [5] .
Problemet med enhver formel syntaks er, at der ofte kan anvendes mere end én inferensregel på en struktur, hvilket resulterer i en konflikt. Jo større dækning, jo større konflikt, og alle grammatikere (siden Panini ) har brugt betydelige kræfter på at skabe et system med forrang for regler, der normalt har vist sig at kunne afkræftes. En anden vanskelighed er med regenerering, som også genererer ugyldige strukturer. Probabilistiske grammatikker kommer uden om disse problemer ved at bruge frekvenserne af de forskellige inferensregler til at ordne dem, hvilket resulterer i en "mest sandsynlig" fortolkning, som per definition er gendrivelig, givet flere data. Da brugsmønstrene ændrer sig diakront, kan disse sandsynlighedsregler genoptrænes og dermed opdatere grammatikken.
Det er muligt at konstruere en probabilistisk grammatik ud fra den traditionelle formelle syntaks ved at tildele hver ikke-terminal en sandsynlighed taget fra en eller anden fordeling, der skal tilnærmes på reelle data. I de fleste eksempler på en lang række sprog yder probabilistiske grammatikker, der justerer disse sandsynligheder baseret på data, bedre end håndlavede grammatikker (selvom nogle regelbaserede grammatikker i øjeblikket nærmer sig VCS-grammatikker i nøjagtighed).
For nylig har probabilistiske grammatikker modtaget en vis subjektiv validering. Det er velkendt, at forskellige syntaktiske strukturer opfattes med forskellig kompleksitet (f.eks. tilgængelighedshierarkiet for relative sætninger). Probabilistiske versioner af minimalistiske grammatikker er blevet brugt til at beregne informationsentropi, som har vist sig at korrelere godt med psykolingvistiske data om nem forståelse og reproduktion. [en]