Stokastisk kontextfri grammatik ( SCS , även probabilistisk kontextfri grammatik , VCS ) är en kontextfri grammatik där varje slutledningsregel motsvarar en sannolikhet. Sannolikheten för en slutledning definieras som produkten av sannolikheterna för de slutledningsregler den använder, så vissa slutsatser passar bättre med en stokastisk grammatik än andra. SCF-grammatiker utökar CF-grammatik på samma sätt som dolda Markov-modeller utökar vanliga grammatiker. SCS-grammatik används i stor utsträckning inom vetenskapen: från naturlig språkbehandling till studiet av RNA- molekyler . SCS-grammatik är en speciell form av viktad kontextfri grammatik .
En variant av Kok-Younger-Kasami-algoritmen hittar Viterbi-parsningen för en given sträng och SCS-grammatik. Viterbi-parsning är den mest troliga härledningen från en sträng givet SCS-grammatiken.
Inre-yttre algoritmer, som är analoga med fram-och-tillbaka-algoritmer, kan användas för att beräkna den totala sannolikheten för alla inferenser som motsvarar en given sträng från en given SCF-grammatik. Detta är ekvivalent med sannolikheten att SCF-grammatiken kommer att generera en given sträng, och är intuitivt ett mått på en given strängs överensstämmelse med en given grammatik.
Inre-yttre algoritmer kan också användas för att beräkna sannolikheterna för att en given inferensregel kommer att användas i godtycklig slutledning för en given sträng. Detta används för att tillämpa EM-algoritmen för att erhålla den maximala sannolikheten för SCS-grammatiken baserat på de träningssekvenser som SCS-grammatiken behöver modellera. Algoritmen liknar den som används för dolda Markov-modeller.
Kontextfria grammatiker skapades ursprungligen i ett försök att modellera naturliga språk. Vissa forskare har utökat denna idé genom att tillämpa SCS-grammatiken.
Här är ett exempel på en SCS-grammatik med två regler. Varje regel föregås av en sannolikhet som återspeglar den relativa frekvensen av dess tillämpning.
0,7VP→VNP 0,3 VP → V NP NPFrån denna grammatik kan vi beräkna det förväntade antalet NP genererade från VP: 0,7 x 1 + 0,3 x 2 = 1,3.
I synnerhet använder vissa taligenkänningssystem SCF-grammatik för att förbättra sannolikhetsapproximationen och därmed igenkänningskvaliteten.
På senare tid har probabilistiska CFG:er spelat en roll för att förklara tillgänglighetshierarkin, som försöker visa varför vissa strukturer är svårare att förstå än andra.
Det visade sig att om det finns probabilistisk information om mer sannolika konstruktioner, så är det möjligt att beräkna informationsentropin för dessa konstruktioner. Om mekanismen för uppfattning av syntax är baserad på begreppen informationsteori, kan den mycket väl använda något som liknar videokonferensgrammatik. [ett]
CS-grammatik används för att modellera den sekundära strukturen av RNA [2] [3] . Den sekundära strukturen inkluderar komplementära nukleotider i en enda RNA-molekyl. Denna parning är biologiskt viktig för att RNA-molekylen ska fungera korrekt. De flesta av dessa parningar kan representeras av en CF-grammatik (med undantag för pseudoknoter).
Betrakta till exempel följande grammatik, där a, c, g och u representerar nukleotider och S är starttecken:
S → aSu | cSg | gSc | usaDenna enkla CFG representerar en RNA-molekyl som enbart består av två helt komplementära regioner där endast kanoniska komplementära par är tillåtna (t.ex. AU och CG).
Genom att lägga till sannolikheter till mer komplexa CFG är det möjligt att modellera baser eller baspar som mer eller mindre matchar den förväntade formen på RNA-molekylen. SCS-grammatik används för att modellera sekvenser i RNA-genfamiljer i Rfam-databasen, och söka genomsekvenser efter troliga medlemmar av dessa familjer. SCS-grammatik har också använts för att söka efter RNA-gener med hjälp av jämförande genomik. I detta arbete undersöktes homologerna av potentiella RNA-gener från två besläktade organismer med hjälp av SCS-grammatiska metoder för att bestämma om den sekundära strukturen behölls. Om så är fallet är sekvensen troligen en RNA-gen, och den sekundära strukturen bibehålls för RNA-genens funktionella behov. Det har också visat sig att SCS-grammatik kan förutsäga den sekundära strukturen hos en RNA-molekyl som liknar befintliga tillvägagångssätt: sådana SCS-grammatiker används till exempel av Stemloc-programmet.
Med publiceringen av Golds teorem 1967 hävdades det att grammatikerna för naturliga språk styrs av deterministiska regler som inte kan läras av enbart positiva exempel. Detta var en del av argumentet för stimulansfattigdom som introducerades 1980 och implicit sedan Chomskys tidiga arbete på 1950-talet. Detta har bland annat lett till den nativistiska föreställningen att grammatikens former (inklusive, i vissa versioner, ett komplett konceptuellt lexikon) är invanda från födseln. Denna representation är avsevärt begränsad av GB- och MP-teorierna.
Det bör dock noteras att Golds resultat på lärbarhet lätt kan kringgås genom att anta att eleven antingen lär sig en nästan perfekt approximation av det korrekta språket, eller lär sig typiska inmatningar snarare än godtyckligt fördelade. Det har faktiskt visat sig att helt enkelt ta emot input från talaren som producerar positiva exempel godtyckligt, snarare än enligt en förutbestämd plan, leder till identifierbarhet med en sannolikhetsgräns på 1. [4] [5] .
Problemet med någon formell syntax är att ofta mer än en slutledningsregel kan tillämpas på en struktur, vilket resulterar i en konflikt. Ju större täckning, desto större konflikt, och alla grammatiker (sedan Panini ) har lagt ner avsevärda ansträngningar på att skapa ett system med företräde för regler som vanligtvis har visat sig motsägbara. En annan svårighet är med regenerering, som också genererar ogiltiga strukturer. Probabilistisk grammatik kommer runt dessa problem genom att använda frekvenserna för de olika slutledningsreglerna för att ordna dem, vilket resulterar i en "mest trolig" tolkning, som per definition är vederlagsbar, givet mer data. Eftersom användningsmönster förändras diakront, kan dessa sannolikhetsregler tränas om och på så sätt uppdatera grammatiken.
Det är möjligt att konstruera en probabilistisk grammatik från den traditionella formella syntaxen genom att tilldela varje icke-terminal en sannolikhet hämtad från någon distribution som ska approximeras på verkliga data. I de flesta exempel på ett brett spektrum av språk presterar probabilistiska grammatiker som justerar dessa sannolikheter baserat på data bättre än handgjorda grammatiker (även om vissa regelbaserade grammatiker för närvarande närmar sig VCS-grammatik i noggrannhet).
På senare tid har probabilistiska grammatiker fått viss subjektiv validering. Det är välkänt att olika syntaktiska strukturer uppfattas med olika komplexitet (till exempel tillgänglighetshierarkin för relativa fraser). Probabilistiska versioner av minimalistisk grammatik har använts för att beräkna informationsentropi, som har visat sig korrelera väl med psykolingvistiska data om enkel förståelse och reproduktion. [ett]