Probabilistyczna (stochastyczna) gramatyka bezkontekstowa (PCFG, ang. probabilistic context-free grammar, SCFG, ang. stochastic context-free grammar) to gramatyka bezkontekstowa, do której dołączono prawdopodobieństwa występujących w niej reguł (produkcji). Prawdopodobieństwa produkcji dołącza się w taki sposób, aby suma prawdopodobieństw reguł o tym samym poprzedniku wynosiła 1.
Innymi słowy, jeśli oznaczają symbole nieterminalne, a ciągi symboli (terminalnych lub nieterminalnych), to powyższy warunek na prawdopodobieństwa reguł można zapisać jako dla każdego Zapis ) należy tutaj rozumieć jako prawdopodobieństwo warunkowe
Prawdopodobieństwo drzewa parsingu Każde zdanie może mieć więcej niż jedną możliwą interpretację – dla każdego rozbioru składniowego zgodnego z gramatyką (przedstawionego najczęściej za pomocą drzewa) można obliczyć jego prawdopodobieństwo. Prawdopodobieństwo to uzyskujemy mnożąc wszystkie wartości prawdopodobieństwa występujące w drzewie.
Wynika to z faktu, że występujące w drzewie produkcje traktujemy jak zdarzenia niezależne:
Przykład Rozważmy następującą gramatykę bezkontekstową: symbole terminalne: butów, buty, do, pasta, pastę, pasty, schował, szewc, szewca; symbole nieterminalne: S (zdanie), VP (fraza czasownikowa), V (czasownik), NPN (fraza rzeczownikowa w mianowniku), NPG (fraza rzeczownikowa w dopełniaczu), NPA (fraza rzeczownikowa w bierniku), NN (rzeczownik w mianowniku), NG (rzeczownik w dopełniaczu), NA (rzeczownik w bierniku), PP (wyrażenie przyimkowe); symbol początkowy: S; reguły: S → NPN VP, VP → V NPA, VP → V NPA PP, V → schował, PP → do NPG, NPN → NN, NPN → NN PP, NPG → NG, NPG → NG PP, NPA → NA, NPA → NA PP, NN → szewc, NN → pasta, NN → buty, NG → szewca, NG → pasty, NG → butów, NA → szewca, NA → pastę, NA → buty.
Tworzymy z niej gramatykę probabilistyczną przez dodanie do każdej reguły prawdopodobieństwa zgodnie z zasadą podaną na wstępie:
poprzednik reguła prawdopodobieństwo S S → NPN VP 1 VP VP → V NPA 0,75 VP → V NPA PP 0,25 V V → schował 1 PP PP → do NPG 1 NPN NPN → NN 0,6 NPN → NN PP 0,4 NPG NPG → NG 0,7 NPG → NG PP 0,3 NPA NPA → NA 0,6 NPA → NA PP 0,4 NN NN → szewc 0,4 NN → pasta 0,3 NN → buty 0,3 NG NG → szewca 0,3 NG → pasty 0,4 NG → butów 0,3 NA NA → szewca 0,25 NA → pastę 0,3 NA → buty 0,45
Przyjmijmy regułę, że w drzewie parsingu wystąpienie reguły której przypisano prawdopodobieństwo będziemy oznaczać następująco:
Weźmy teraz zdanie należące do języka generowanego przez tę gramatykę:
Szewc schował pastę do butów.
Może ono powstać zgodnie z regułami tej gramatyki na dwa różne sposoby (które odpowiadają dwóm różnym znaczeniom tego zdania):
1. Pasta do butów została schowana (na przykład do szafy):
2. Pasta została schowana do butów:
Prawdopodobieństwo każdego z tych drzew obliczamy mnożąc występujące w nich prawdopodobieństwa. Prawdopodobieństwo pierwszego drzewa wynosi 1 · 0,6 · 0,4 · 0,75 · 1 · 0,4 · 0,3 · 1 · 0,7 · 0,3 = 0,004536, zaś drugiego 1 · 0,6 · 0,4 · 0,25 · 1 · 0,6 · 0,3 · 1 · 0,7 · 0,3 = 0,002268.
Algorytmy Do znajdowania najbardziej prawdopodobnego drzewa parsingu zdania w danej probabilistycznej gramatyce bezkontekstowej używa się na ogół zmodyfikowanego algorytmu Viterbiego (tzw. inside-outside algorithm). Można też użyć uogólnionego algorytmu A*.
Zastosowania Probabilistyczne gramatyki bezkontekstowe znajdują zastosowanie głównie w analizie języka naturalnego. Za ich pomocą można uzyskać więcej informacji o parsowanym zdaniu niż w przypadku zwykłych gramatyk bezkontekstwych, ponieważ oprócz prostej odpowiedzi, czy zdanie jest poprawne (i listy jego możliwych interpretacji), uzyskujemy również pojęcie o tym, które jego interpretacje są bardziej wiarygodne. PCFG pozwalają również na analizowanie fragmentów zdań lub zdań nie do końca poprawnych (zawierających błędy). Z tych powodów są pomocne przy rozpoznawaniu mowy.
PCFG mogą być użyte także do innych celów, takich jak modelowanie struktury drugorzędowej RNA.
Zobacz też gramatyka formalna gramatyka bezkontekstowa
Przypisy
Bibliografia
Kategoria:Języki formalne Kategoria:Lingwistyka komputerowa