How to calculate the probability of a parse tree in PCFG

Probabilistic Context Free Grammar How to calculate the probability of a parse tree

Probability of a parse tree:

Page 1    Page 2    Page 3

We have formally defined PCFG. Now the next question is how to use PCFG to derive the probability of a parse tree (derivation tree). As discussed, a sentence can be parsed into more than one way. That means, we can have more than one parse trees for the sentence as per the CFG due to ambiguity.

Given a parse tree t, with the production rules α₁ → β₁, α₂ → β₂, … , α_n → β_n from R (ie., α_i → β_i ∈ R), we can find the probability of tree t using PCFG as follows;

As per the equation, the probability P(t) of parse tree is the product of probabilities of production rules in the tree t.

Example:

Find the probability of the parse tree t given below;

                   = 1.0 * 0.1 * 0.7 * 1.0 * 0.4 * 0.18 * 1.0 * 1.0 * 0.18

                   = 0.0009072

The probability of the parse tree t is calculated as 0.0009072.

 Page 1    Page 2    Page 3

********************

Related links:

• Go to Natural Language Processing (NLP) home

• Go to NLP Solved Exercise page

• Go to Context Free Grammar (CFG) Formal Definition page

• Go to How to derive production rule probability from Treebank using MLE - Solved exercise page

How to derive probabilities for production rules from Treebank using maximum likelihood estimate

PCFG probabilities estimation

How to calculated production rule probability in PCFG using tree banks

Probabilistic context free grammar rule probability estimation using tree banks