Probabilistyczna gramatyka bezkontekstowa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Prawdopodobieństwo drzewa parsingu[edytuj | edytuj kod]

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

\operatorname{P} (t) = \operatorname{P} (A \to B C \wedge C \to D) = \operatorname{P} (A \to B C) \operatorname{P} (C \to D | A \to B C) = \operatorname{P} (A \to B C) \operatorname{P} (C \to D)

Przykład[edytuj | edytuj kod]

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 X → Y, której przypisano prawdopodobieństwo 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[edytuj | edytuj kod]

Do znajdywania 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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]

Przypisy

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

Bibliografia[edytuj | edytuj kod]

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