Gramatica stocastică fără context ( SCS , și probabilistic context-free grammar , VCS ) este o gramatică fără context în care fiecare regulă de inferență corespunde unei probabilități. Probabilitatea unei inferențe este definită ca produsul dintre probabilitățile regulilor de inferență pe care le folosește, astfel încât unele inferențe se potrivesc mai bine cu o gramatică stocastică decât altele. Gramaticile SCF extind gramaticile CF în același mod în care modelele Markov ascunse extind gramaticile obișnuite. Gramaticile SCS sunt utilizate pe scară largă în știință: de la procesarea limbajului natural până la studiul moleculelor de ARN . Gramaticile SCS sunt o formă specială de gramatici ponderate fără context .
O variantă a algoritmului Kok-Younger-Kasami găsește analiza Viterbi pentru un șir dat și gramatică SCS. Analiza Viterbi este cea mai probabilă derivare dintr-un șir având în vedere gramatica SCS.
Algoritmii interior-exterior, care sunt analogi cu algoritmii dus-întors, pot fi utilizați pentru a calcula probabilitatea totală a tuturor inferențelor corespunzătoare unui șir dat dintr-o gramatică SCF dată. Aceasta este echivalentă cu probabilitatea ca gramatica SCF să genereze un șir dat și este intuitiv o măsură a conformității unui șir dat cu o gramatică dată.
Algoritmii interior-exterior pot fi utilizați și pentru a calcula probabilitățile ca o anumită regulă de inferență să fie utilizată în inferența arbitrară pentru un șir dat. Acesta este folosit pentru a aplica algoritmul EM pentru a obține probabilitățile maxime de probabilitate pentru gramatica SCS pe baza secvențelor de antrenament pe care gramatica SCS trebuie să le modeleze. Algoritmul este similar cu cel folosit pentru modelele Markov ascunse.
Gramaticile fără context au fost create inițial în încercarea de a modela limbajele naturale. Unii cercetători au extins această idee prin aplicarea gramaticii SCS.
Iată un exemplu de gramatică SCS cu două reguli. Fiecare regulă este precedată de o probabilitate care reflectă frecvența relativă a aplicării ei.
0,7VP→VNP 0,3 VP → V NP NPDin această gramatică, putem calcula numărul așteptat de NP generate din VP: 0,7 x 1 + 0,3 x 2 = 1,3.
În special, unele sisteme de recunoaștere a vorbirii folosesc gramaticile SCF pentru a îmbunătăți aproximarea probabilității și, prin urmare, calitatea recunoașterii.
Recent, CFG-urile probabilistice au jucat un rol în explicarea ierarhiei de accesibilitate, care încearcă să arate de ce unele structuri sunt mai greu de înțeles decât altele.
S-a dovedit că, dacă există informații probabilistice despre construcții mai probabile, atunci este posibil să se calculeze entropia informațională a acestor construcții. Dacă mecanismul de percepție a sintaxei se bazează pe conceptele teoriei informației, atunci s-ar putea să folosească ceva similar cu gramatica videoconferinței. [unu]
Gramaticile CS sunt folosite pentru a modela structura secundară a ARN-ului [2] [3] . Structura secundară include nucleotide complementare într-o singură moleculă de ARN. Această împerechere este importantă din punct de vedere biologic pentru buna funcționare a moleculei de ARN. Majoritatea acestor perechi pot fi reprezentate printr-o gramatică CF (cu excepția pseudonodurilor).
Luați în considerare, de exemplu, următoarea gramatică, în care a, c, g și u reprezintă nucleotide și S este caracterul de început:
S → aSu | cSg | gSc | Statele Unite ale AmericiiAcest CFG simplu reprezintă o moleculă de ARN constând numai din două regiuni complet complementare în care sunt permise doar perechile complementare canonice (de exemplu, AU și CG).
Adăugând probabilități la CFG-uri mai complexe, este posibil să se modeleze baze sau perechi de baze care se potrivesc mai mult sau mai puțin cu forma așteptată a moleculei de ARN. Gramaticile SCS sunt utilizate pentru a modela secvențele din familiile de gene ARN din baza de date Rfam și pentru a căuta secvențe de genom pentru membrii probabili ai acestor familii. Gramaticile SCS au fost, de asemenea, folosite pentru a căuta gene ARN folosind genomica comparativă. În această lucrare, omologii genelor potențiale de ARN de la două organisme înrudite au fost examinați folosind abordări gramaticale SCS pentru a determina dacă structura secundară a fost reținută. Dacă da, atunci secvența este probabil o genă ARN, iar structura secundară este reținută pentru nevoile funcționale ale genei ARN. De asemenea, s-a demonstrat că gramaticile SCS pot prezice structura secundară a unei molecule de ARN similar abordărilor existente: astfel de gramatici SCS sunt utilizate, de exemplu, de programul Stemloc.
Odată cu publicarea teoremei lui Gold în 1967, s-a susținut că gramaticile limbilor naturale sunt guvernate de reguli deterministe care nu pot fi învățate numai din exemple pozitive. Aceasta a făcut parte din argumentul sărăciei de stimulare introdus în 1980 și implicit încă de la primele lucrări ale lui Chomsky în anii 1950. Printre alte argumente, acest lucru a condus la noțiunea nativistă conform căreia formele de gramatică (inclusiv, în unele versiuni, un lexic conceptual complet) sunt înrădăcinate încă de la naștere. Această reprezentare este limitată semnificativ de teoriile GB și MP.
Cu toate acestea, trebuie remarcat că rezultatul Gold privind capacitatea de învățare poate fi ocolit cu ușurință presupunând că elevul fie învață o aproximare aproape perfectă a limbajului corect, fie învață intrări tipice, mai degrabă decât cele distribuite arbitrar. Într-adevăr, s-a demonstrat că simpla primire de input de la vorbitor care produce exemple pozitive în mod arbitrar, mai degrabă decât conform unui plan predeterminat, duce la identificarea cu o limită de probabilitate de 1. [4] [5] .
Problema cu orice sintaxă formală este că de multe ori mai multe reguli de inferență pot fi aplicate unei structuri, ducând la un conflict. Cu cât acoperirea este mai mare, cu atât conflictul este mai mare și toți gramaticienii (de la Panini ) au depus un efort considerabil creând un sistem de prioritate pentru regulile care s-au dovedit de obicei refutabile. O altă dificultate este regenerarea, care generează și structuri invalide. Gramaticile probabiliste rezolvă aceste probleme utilizând frecvențele diferitelor reguli de inferență pentru a le ordona, rezultând o interpretare „cel mai probabilă”, care este prin definiție refutabilă, având în vedere mai multe date. Deoarece modelele de utilizare se schimbă diacronic, aceste reguli probabilistice pot fi reeducate, actualizându-se astfel gramatica.
Este posibil să se construiască o gramatică probabilistică din sintaxa formală tradițională, atribuind fiecărui non-terminal o probabilitate luată dintr-o distribuție pentru a fi aproximată pe date reale. În majoritatea exemplelor dintr-o gamă largă de limbi, gramaticile probabilistice care ajustează aceste probabilități pe baza datelor au rezultate mai bune decât gramaticile realizate manual (deși unele gramaticale bazate pe reguli se apropie în prezent de gramaticile VCS cu acuratețe).
Recent, gramaticile probabilistice au primit o oarecare validare subiectivă. Este bine cunoscut faptul că diferite structuri sintactice sunt percepute cu o complexitate diferită (de exemplu, ierarhia de accesibilitate pentru frazele relative). Versiunile probabiliste ale gramaticilor minimaliste au fost folosite pentru a calcula entropia informației, care s-a descoperit că se corelează bine cu datele psiholingvistice privind ușurința de înțelegere și reproducere. [unu]