0
$\begingroup$

I'm quite struggling with calculating the probability of a rule for a PCFG.

I've been looking for examples online and more information, but I am none the wiser. Here is an image of the slides. I cannot understand how the numbers are calculated on the left. From what I understood, I have to take a rule and see how many times it's been used in the tree and then divide it. However, then the numbers that I get do not match this example at all. I feel like I'm missing something small and I've been starting at this for a few hours now and I'm going crazy.

Thank you!

enter image description here

$\endgroup$
3
  • $\begingroup$ The probabilities on the left are not calculated. They are part of the description of the grammar. They cannot be calculated. $\endgroup$ Commented Apr 21, 2020 at 13:03
  • $\begingroup$ The probability of the derivation is the product of the probabilities of the various rules that are applied. This is what you see on the right. $\endgroup$ Commented Apr 21, 2020 at 13:03
  • $\begingroup$ From what I understood, I have to take a rule and see how many times it's been used in the tree and then divide it. Not at all. A PCFG is a generative model for generating random words in the language. It is specified by a probability distribution on the derivation rules involving each nonliteral (on the left). $\endgroup$ Commented Apr 21, 2020 at 13:04

1 Answer 1

1
$\begingroup$

A probabilistic context-free grammar is a generative model, which can be used to generate random words in the language of the underlying context-free grammar. In order to do this, for each nonterminal $A$ we give a probability distribution on the set of rules of the form $A\to \alpha$. To generate a sentence, you start with the starting symbol $S$. As long as the current sentential form contains some nonterminal, say $A$, you apply a random derivation rule $A\to \alpha$ according to the probability distribution. If the probabilities are chosen correctly, then eventually a terminal word will be generated (almost surely).

On the left of your image, you can see the probability distributions. You can estimate the probabilities from a collection of parse trees, but you can also come up with them in any other way. In particular, it doesn't make too much sense to determine them from a single parse tree, like your description seems to imply.

On the right of your image, you can see the calculation that the given parse tree be generated by the PCFG on the left. This probability is the product of all derivation rules that need to be applied to obtain the parse tree (the order of application is immaterial since it doesn't affect the product).

Your underlying difficulty seems to be that you don't understand what PCFGs are for and how they are used. Hopefully, my description above helps to clarify this somewhat.

$\endgroup$
2
  • $\begingroup$ Ah I see. I got confused. For my homework assignment I have to convert a given CFG to a PCFG with a treebank that I have. How can I estimate the probabilities from a treebank? Your answer clarified a lot for me, by the way. Thank you! $\endgroup$
    – ano
    Commented Apr 21, 2020 at 14:31
  • $\begingroup$ It should have been covered in class. Roughly speaking, $\Pr[A\to\alpha]$ is the fraction of times that $A\to\alpha$ appears in the databank among all rules of the type $A\to\cdots$ (but sometimes this is slightly corrected). $\endgroup$ Commented Apr 21, 2020 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.