Stohastička kontekstno neovisna gramatika

Izvor: Wikipedija

Stohastička kontekstno neovisna gramatika (engl. stochastic context-free grammar (SCFG)), poznata i kao probabilistička kontekstno neovisna gramatika (engl. skr. PCFG) je kontekstno neovisna gramatika u kojoj je svakoj produkciji pridodana vjerojatnost. Vjerojatnost nekog postupka generiranja međuniza (parsiranja) jest tad umnožak vjerojatnosti svih produkcija korištenih u postupku, te su stoga neki postupci generiranja konzistentniji sa stohastičkom gramatikom od ostalih. SCFG proširuju kontekstno neovisne gramatike na isti način na koji skriveni Markovljevi modeli proširuju regularne gramatike. SCFG imaju primjenu u dva područja: obrada prirodnog jezika i proučavanje RNA molekula u bioinformatici. Ovu metodu aktivno koriste mnogi istaknuti istraživači kao što je Satish Gupta. SCFG su specijalizirani oblici težinskih kontekstno neovisnih gramatika.

Sadržaj 1 Tehnike 2 Primjene 2.1 Obrada prirodnog jezika 2.2 RNA 3 Reference 4 Vanjske poveznice

[uredi] Tehnike

Varijanta CYK algoritma pronalazi Viterbi parsiranje slijeda znakova za danu SCFG. Viterbi parsiranje je najizgledniji postupak generiranja (parsiranje) slijeda za danu SCFG.

Algoritmi unutar i izvana su analogoni algoritama naprijed i nazad, i mogu se koristiti za izračun ukupne vjerojatnosti svih postupaka generiranja koji su konzistentni sa danim slijedom, ovisno o nekoj SCFG. Ovo je istovjetno vjerojatnosti da SCFG generira slijed, i predstavlja intuitivnu mjeru konzistentnosti slijeda u danoj gramatici.

Algoritmi unutar/izvana se također mogu koristiti za izračun vjerojatnosti da će dani postupak generiranja biti korišten u slučajnom postupku generiranja slijeda. ovo se koristi kao dio algoritma očekivanja-maksimizacije da bi se naučile maksimalne izglednosti vjerojatnosti za SCFG baziranu na skupu uvježbanih slijedova koje bi SCFG trebala modelirati. Algoritam je analogan onome koji koriste skriveni Markovljevi modeli.

[uredi] Primjene

[uredi] Obrada prirodnog jezika

Kontekstno neovisne gramatike su izvorno zamišljene kao pokušaj modeliranja prirodnih jezika, tj. onih koje uobičajeno pričaju ljudi. Neka istraživanja su proširila ovu ideju sa SCFG.

Slijedi mali primjer PCFG gramatike sa dva pravila. Svakom pravilu prethodi vjerojatnost koja odražava relativnu frekvenciju njegova pojavljivanja.

0.7 VP --> V NP

0.3 VP --> V NP NP

Za ovako zadanu gramatiku sad možemo reći da broj očekivanih NP-ova prilikom postupka generiranja VP-ova iznosi 0.7 x 1 + 0.3 x 2 = 1.3.

Također, neki sustavi prepoznavanja govora koriste SCFG za poboljšanje svoje vjerojatnosti procjenjivanja a time i svojih performansi.

U zadnje vrijeme su probabilističke kontekstno neovisne gramatike odigrale važnu ulogu u objašnjavaju hijerarhije pristupačnosti, koja pokušava objasniti zašto je određene strukture teže razumjeti nego neke druge, tj. one sa odnosnim rečenicama poput ove u engl. "they had forgotten that the box which Pat brought with apples in was lost". Pokazalo se da ako postoji probabilistički utjecaj izglednijih konstrukcija, tada se može manipulirati informacijsko teoretska mjera entropije za konstrukte. Ako je kognitivni aparat za sintaksu baziran na informacijsko teoretskim podlogama, tada on može vrlo lako koristiti nešto slično PCFG.^[1]

[uredi] RNA

Kontekstno neovisne gramatike su vrlo pogodne u modeliranju sekundarne strukture ^[2][3]. Sekundarna struktura sadrži nukleotide sa jednolančanom RNA molekulom koji su međusobno komplementarni, i stoga čine par. Ovo sparivanje baza je biološki važno za pravilno funkcioniranje RNA molekule. Većina sparivanja ovih baza može biti predstavljeno kontekstno neovisnom gramatikom (veća iznimka od ovog pravila su pseudočvorovi).

Na primjer, u sljedećoj gramatici u kojoj a, c, g i u predstavljaju nukleotide i S je početni nezavršni znak:

S → aSu | cSg | gSc | uSa

Ova jednostavna KNG predstavlja RNA molekulu koja se u cijelosti sastoji od dvije potpuno komplementarne regije, u kojoj su dozvoljeni samo kanonski komplementarni parovi (tj. A-U i C-G).

Pridodavanjem vjerojatnosti sofisticiranijim kontekstno neovisnim gramatikama, moguće je modelirati baze ili sparivanja baza koja su manje ili više konzistentna sa očekivanim uzorkom RNA molekule. SCFG se koriste za modeliranje uzoraka u RNA familijama gena u Rfam bazi, te se koriste pri pretrazi slijedova genoma za izgledne dodatne članove tih familija. SCGF su također korištene za traženje RNA gena korištenjem komparativne genomike. U tom se slučaju homolozi potencijalnih RNA gena u dva srodna organizma ispituju korištenjem SCFG da bi se vidjelo je li njihova sekundarna struktura očuvana. Ako jest, slijed je izgledno RNA gen, a očuvanost sekundarne strukture se pretpostavlja zbog funkcionalnih potreba RNA gena. Pokazano je da SCFG mogu predvidjeti sekundarnu strukturu RNA molekule slično postojećim tehnikama, iako ova primjena nije naširoko prihvaćena.

[uredi] Reference

1. ↑ John Hale (2006). "Uncertainty About the Rest of the Sentence". Cognitive Science 30: 643-672.
2. ↑ Durbin, Eddy, Krogh, Mitchison, Biological sequence analysis, Cambridge University Press, 1998. Ovaj udžbenik bioinformatike sadrži vrlo prijemčiv uvod u uporabu SCFG za modeliranje RNA, kao i povijest ove primjene sve do 1999.
3. ↑ Sean R. Eddy and Richard Durbin (1994), "RNA sequence analysis using covariance models", Nucleic Acids Research, 22 (11): 2079-88. [1]

• Elena Rivas and Sean R. Eddy (2001), "Noncoding RNA gene detection using comparative sequence analysis", BMC Bioinformatics, 2 (1): 8. [2]

[uredi] Vanjske poveznice

• Rfam baza