Probabilistyczna (stochastyczna) gramatyka bezkontekstowa (PCFG, ang.probabilistic context-free grammar, SCFG, ang. stochastic context-free grammar) to gramatykabezkontekstowa, 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:
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:
X (p)
Y
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):
S (1)
NPN (0,6)
VP (0,75)
NN (0,4)
V (1)
NPA (0,4)
NA (0,3)
PP (1)
NPG (0,7)
NG (0,3)
szewc
schował
pastę
do
butów
2. Pasta została schowana do butów:
S (1)
NPN (0,6)
VP (0,25)
NN (0,4)
V (1)
NPA (0,6)
PP (1)
NA (0,3)
NPG (0,7)
NG (0,3)
szewc
schował
pastę
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*[1].
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.
Probabilistic Context Free Grammars. W: Chris Manning, Hinrich Schütze: Foundations of Statistical Natural Language Processing. Cambridge: MIT Press, 1999, s. 381.