<p>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.</p>

<p>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.  </p>

<p>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.</p>

<p>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
$$</p>

<p>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$.</p>

CC BY-SA 3.0
2012-03-09T19:20:39.510Z
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.
George Roy
CC BY-SA 3.0
2012-03-09T09:29:45.933Z
2012-03-09T09:29:45.933Z
Matthew Wiley
<p>The Equation1 in paper in <a href="http://cpl.cc.gatech.edu/pubs/PDF/aaai02-djmoore-essa.pdf" rel="nofollow">link</a> 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>

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

<p>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.</p>

CC BY-SA 3.0
2012-03-09T16:07:21.460Z
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.
Marcin Kotowski
<fl.formal-languages><automata-theory><pr.probability><context-free-languages><stochastic-process>
Issue in understanding conditional likelihood for a producton rule
George Roy
# Issue in understanding conditional likelihood for a producton rule

(Asked by: username_0 on 2012-03-09)

The Equation1 in paper in [link](http://cpl.cc.gatech.edu/pubs/PDF/aaai02-djmoore-essa.pdf) 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.

**Tags:** fl.formal-languages, automata-theory, pr.probability, context-free-languages, stochastic-process

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2012-03-09. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_0**: 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.  

---

