Stochastická bezkontextová gramatika ( SCS , také pravděpodobnostní bezkontextová gramatika , VCS ) je bezkontextová gramatika , ve které každé odvozovací pravidlo odpovídá pravděpodobnosti. Pravděpodobnost inference je definována jako součin pravděpodobností inferenčních pravidel, která používá, takže některé inference se hodí do stochastické gramatiky lépe než jiné. SCF gramatiky rozšiřují CF gramatiky stejným způsobem jako skryté Markovovy modely rozšiřují regulární gramatiky. SCS gramatiky jsou široce používány ve vědě: od zpracování přirozeného jazyka po studium molekul RNA . SCS gramatiky jsou speciální formou vážených bezkontextových gramatik .
Varianta Kok-Younger-Kasamiho algoritmu najde Viterbiho analýzu pro daný řetězec a gramatiku SCS. Viterbiho parsování je nejpravděpodobnější odvození z řetězce dané gramatikou SCS.
Vnitřní-vnější algoritmy, které jsou analogické k algoritmům tam a zpět, lze použít k výpočtu celkové pravděpodobnosti všech závěrů odpovídajících danému řetězci z dané gramatiky SCF. To je ekvivalentní pravděpodobnosti, že gramatika SCF vygeneruje daný řetězec, a je intuitivně měřítkem shody daného řetězce s danou gramatikou.
Vnitřní-vnější algoritmy lze také použít k výpočtu pravděpodobností, že dané odvozovací pravidlo bude použito v libovolném odvození pro daný řetězec. To se používá k aplikaci EM algoritmu k získání maximálních pravděpodobností pravděpodobnosti pro gramatiku SCS na základě trénovacích sekvencí, které gramatika SCS potřebuje modelovat. Algoritmus je podobný jako u skrytých Markovových modelů.
Bezkontextové gramatiky byly původně vytvořeny ve snaze modelovat přirozené jazyky. Někteří vědci tuto myšlenku rozšířili použitím gramatiky SCS.
Zde je příklad SCS gramatiky se dvěma pravidly. Každému pravidlu předchází pravděpodobnost, která odráží relativní četnost jeho aplikace.
0,7VP→VNP 0,3 VP → V NP NPZ této gramatiky můžeme vypočítat očekávaný počet NP generovaných z VP: 0,7 x 1 + 0,3 x 2 = 1,3.
Zejména některé systémy rozpoznávání řeči používají gramatiky SCF ke zlepšení aproximace pravděpodobnosti a tím i kvality rozpoznávání.
V poslední době hrají pravděpodobnostní CFG roli ve vysvětlení hierarchie přístupnosti, která se pokouší ukázat, proč jsou některé struktury hůře pochopitelné než jiné.
Ukázalo se, že pokud existují pravděpodobnostní informace o pravděpodobnějších konstrukcích, pak je možné vypočítat informační entropii těchto konstrukcí. Pokud je mechanismus vnímání syntaxe založen na konceptech teorie informace, pak může dobře používat něco podobného jako videokonferenční gramatiky. [jeden]
CS-gramatiky se používají k modelování sekundární struktury RNA [2] [3] . Sekundární struktura zahrnuje komplementární nukleotidy v jedné molekule RNA. Toto párování je biologicky důležité pro správné fungování molekuly RNA. Většina těchto párů může být reprezentována CF gramatikou (s výjimkou pseudouzlů).
Zvažte například následující gramatiku, ve které a, c, g a u představují nukleotidy a S je počáteční znak:
S → aSu | cSg | gSc | usaTato jednoduchá CFG představuje molekulu RNA sestávající pouze ze dvou plně komplementárních oblastí, ve kterých jsou povoleny pouze kanonické komplementární páry (např. AU a CG).
Přidáním pravděpodobností ke složitějším CFG je možné modelovat báze nebo páry bází, které více či méně odpovídají očekávanému tvaru molekuly RNA. SCS gramatiky se používají k modelování sekvencí v rodinách genů RNA v databázi Rfam a hledání sekvencí genomu pro pravděpodobné členy těchto rodin. SCS gramatiky byly také použity k hledání RNA genů pomocí komparativní genomiky. V této práci byly homology potenciálních genů RNA ze dvou příbuzných organismů zkoumány pomocí gramatických přístupů SCS, aby se zjistilo, zda byla zachována sekundární struktura. Pokud ano, pak je sekvencí pravděpodobně gen RNA a sekundární struktura je zachována pro funkční potřeby genu RNA. Ukázalo se také, že SCS gramatiky mohou předpovídat sekundární strukturu molekuly RNA podobně jako stávající přístupy: takové SCS gramatiky používá např. program Stemloc.
S publikací Goldova teorému v roce 1967 se tvrdilo, že gramatiky přirozených jazyků se řídí deterministickými pravidly, která se nelze naučit pouze z pozitivních příkladů. To bylo součástí argumentu stimulační chudoby zavedeného v roce 1980 a implicitního od Chomského raných prací v 50. letech 20. století. Kromě jiných argumentů to vedlo k nativistické představě, že formy gramatiky (včetně, v některých verzích, kompletního pojmového slovníku) jsou zakořeněné od narození. Tato reprezentace je výrazně omezena teorií GB a MP.
Je však třeba poznamenat, že Goldův výsledek týkající se učenlivosti lze snadno obejít předpokladem, že student se buď naučí téměř dokonalou aproximaci správného jazyka, nebo se naučí spíše typické vstupy než libovolně rozložené. Bylo skutečně ukázáno, že pouhé přijímání vstupu od mluvčího, který produkuje pozitivní příklady svévolně, spíše než podle předem stanoveného plánu, vede k identifikovatelnosti s limitem pravděpodobnosti 1. [4] [5] .
Problém s jakoukoli formální syntaxí je v tom, že často lze na strukturu použít více než jedno odvozovací pravidlo, což vede ke konfliktu. Čím větší pokrytí, tím větší konflikt a všichni gramatici (od Paniniho ) vynaložili značné úsilí na vytvoření systému přednosti pro pravidla, která se obvykle ukázala jako vyvratitelná. Další problém je s regenerací, která také generuje neplatné struktury. Pravděpodobnostní gramatiky tyto problémy obejdou tak, že k jejich seřazení použijí frekvence různých odvozovacích pravidel, což vede k „nejpravděpodobnějšímu“ výkladu, který je z definice vyvratitelný vzhledem k většímu množství dat. Vzhledem k tomu, že vzorce použití se diachronně mění, lze tato pravděpodobnostní pravidla přetrénovat, a tím aktualizovat gramatiku.
Pravděpodobnostní gramatiku je možné sestavit z tradiční formální syntaxe tak, že každému neterminálu přiřadíme pravděpodobnost vzatou z nějaké distribuce, která se má aproximovat na reálných datech. Ve většině příkladů široké škály jazyků mají pravděpodobnostní gramatiky, které upravují tyto pravděpodobnosti na základě dat, lepší výsledky než ručně vytvořené gramatiky (ačkoli některé gramatiky založené na pravidlech se v současnosti svou přesností blíží gramatikám VCS).
Pravděpodobnostní gramatiky nedávno získaly určitou subjektivní validaci. Je dobře známo, že různé syntaktické struktury jsou vnímány s různou složitostí (například hierarchie přístupnosti pro relativní fráze). Pravděpodobnostní verze minimalistických gramatik byly použity k výpočtu informační entropie, u které bylo zjištěno, že dobře koreluje s psycholingvistickými údaji o snadnosti porozumění a reprodukce. [jeden]