Probabilistyczna gramatyka bezkontekstowa

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 ${\displaystyle N_{i}}$ oznaczają symbole nieterminalne, a ${\displaystyle \zeta _{j}}$ ciągi symboli (terminalnych lub nieterminalnych), to powyższy warunek na prawdopodobieństwa reguł można zapisać jako ${\displaystyle \sum _{j}\operatorname {P} (N_{i}\to \zeta _{j})=1}$ dla każdego ${\displaystyle i.}$ Zapis ${\displaystyle \operatorname {P} (N_{i}\to \zeta _{j}}$) należy tutaj rozumieć jako prawdopodobieństwo warunkowe ${\displaystyle \operatorname {P} (N_{i}\to \zeta _{j}|N_{i}).}$

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:

A

B

C

D

${\displaystyle \operatorname {P} (t)=\operatorname {P} (A\to BC\wedge C\to D)=\operatorname {P} (A\to BC)\operatorname {P} (C\to D|A\to BC)=\operatorname {P} (A\to BC)\operatorname {P} (C\to D)}$

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 ${\displaystyle X\to Y,}$ której przypisano prawdopodobieństwo ${\displaystyle p,}$ 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.

PCFG mogą być użyte także do innych celów, takich jak modelowanie struktury drugorzędowej RNA^[2].

Zobacz też

• gramatyka formalna
• gramatyka bezkontekstowa

Przypisy

1. Dan Klein, Christopher D. Manning: A* parsing: Fast exact Viterbi parse selection. [dostęp 2009-01-03]. (ang.).
2. S.R. Eddy, R. Durbin: RNA sequence analysis using covariance models. [dostęp 2009-01-03]. (ang.).

Bibliografia

• Probabilistic Context Free Grammars. W: Chris Manning, Hinrich Schütze: Foundations of Statistical Natural Language Processing. Cambridge: MIT Press, 1999, s. 381.