The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it applies only for production E as

P(E->LKM)=3/5 =0.6 ; P(E->LM) =2/5=0.4.

Whereas for the other productions, I have a hard time in figuring out what goes in the numerator for instance for K, N etc productions and I am not able to understand how the probabilities are assigned to the other productions say G,H etc based on this formula. Am I misunderstanding the working of this formula? Would be highly obliged for an explanation and example. Thanking you.

  • 2
    $\begingroup$ I think it's a good practice to introduce some background in your question, so people reading it don't have to dig through the paper. $\endgroup$ – Marcin Kotowski Mar 9 '12 at 16:07

Equation 1 from the link is used to determine the probability for one production rule. Assume we have data that we can use for estimating these probabilities; i.e. we believe in the distribution of this data.

Then, to estimate the probability of $X \rightarrow \lambda$, use the following formula: $$ P(X \rightarrow \lambda) = \frac{c(X \rightarrow \lambda)}{\sum_{\mu}c(X \rightarrow \mu)} $$ where $c(X \rightarrow \lambda)$ is the number of times we observed $X$ producing $\lambda$ in the data; $\sum c(X \rightarrow \mu)$ is the number of times we observed $X$ producing $\mu$, for any $\mu$ in the data.

Thus, the denominator of the above equation becomes the number of times $X$ produces any symbol in the data, normalizing the probabilities for each left hand side of the production rule. Note, in Figure 1 of the link, the sum of the probabilities equals one for any symbol on the left hand side of the production rules.

For example, let us say that $G$ appeared on the left hand side of a production rule 10 times in the data. We observe that 8 out of these 10 times $G$ produced $J$. We also observed that $G$ produced $Hf$ and $bfffH$ once. Thus, $\sum_{\mu} c(G \rightarrow \mu) = 8 + 1 + 1 = 10$, $c(G \rightarrow J) = 8$, $c(G \rightarrow Hf)$ = 1, and $c(G \rightarrow bfffH) = 1$. Hence, we compute the probabilities to be: $$ P(G \rightarrow J) = \frac{8}{10} = 0.8\\ P(G \rightarrow Hf) = \frac{1}{10} = 0.1\\ P(G \rightarrow bfffH) = \frac{1}{10} = 0.1 $$

We can do the same for $H$. Say that we observed $H$ on the left hand side 4 times, producing $l$ and $lH$ two times each. The probabilities for both of these productions rules is then $\frac{2}{4} = 0.5$.

  • $\begingroup$ Thank you for such a lucid explanation. One thing is however unclear which is are these "observations" based on the training data? That is,the initial assumption that G appeared 8 times,J appeared once and so on. Can we just give any arbitrary number of assumptions?Can Kevin Murphys Hidden Markov Model toolkit be used for these purposes?If so then please be kind enough to explain that. $\endgroup$ – George Roy Mar 9 '12 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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