UoL CS Notes
Menu

Probabilistic CFGs

COMP218 Lectures

  • A PCFG is a probabilistic version of a CFG where each production has a probability.
  • Probabilities of all productions rewriting a given non-terminal must add up to 1, defining a distribution for each non-terminal.
  • String generation is now probabilistic where production probabilities are used to nondeterministically select a production for rewriting a given non-terminal.

This allows us to find the most likely meaning of a sentence in ambiguous languages.

Probabilistic Context Free Grammars

Each production is is assigned a probability. For each non-terminal this probability must add up to 1:

Production Probability
$S\rightarrow NPVP$ 0.8
$S\rightarrow Aux NPVP$ 0.1
$S\rightarrow VP$ 0.1

Parse Tree Probability

The probability of a parse tree is the product of all the production probabilities used.

  • If multiple parse trees are valid then we interpret the meaning from the parse tree with the greatest probability.

Probabilistic CYK

In addition to storing the non-terminal in each cell, we also need to store the probability:

  • Cell $ij$ contains the most probable parse tree of each non-terminal that can generate the part of the input word from $i$ through $j$ together with its associated probability.

Probabilistic Chomsky Normal Form Conversion

When transforming the grammar to CNF, we set the production probabilities to preserve the probability of derivations.

Parsing CYK Tables

  • Use $\max$ to combine probabilities of multiple parse trees in each cell.
  • The probability of generating a given sentence is the sum of all probabilities of multiple parse tree in each cell.

Sentence Probability

For all cells in last row
	If there is a production A -> xi with probability p
	 Put A:p in table cell ii
For cells st in other rows (going bottom to top)
	If there is a production A -> BC with probability p
		where B:pB is in cell sj and C:pC is in cell (j + 1)t and
			A:pA in cell st (if not present assume pA = 0)
		Update  A:pA + p * pB * pC in cell st

Most Likely Parse Tree

For all cells in last row
	If there is a production A -> xi with probability p
		Put A;p in table cell ii
For cells st in other rows (going bottom up)
	If there is a production A -> BC with probability p
		where B:pB is in cell sj and C:pC is in cell (j + 1)t and
			A:pA in cell st (if not present assume pA=0)
		Update A:max(pA, p * pB * pC) in cell st