# Counting non-reduntant parameters in probabilistic graphical models

Let's say we have the following problem from this book:

Consider a very simple medical diagnosis setting, where we focus on two diseases — flu and hayfever; these are not mutually exclusive, as a patient can have either, both, or none. Thus, we might have two binary-valued random variables, Flu and Hayfever. We also have a 4-valued random variable Season, which is correlated both with flu and hayfever. We may also have two symptoms, Congestion and Muscle Pain, each of which is also binary-valued. Overall, our probability space has 2 × 2 × 4 × 2 × 2 = 64 values.

Now let's take the following graph: which describes the following independence rules: $$F\bot H|S$$ $$C\bot S|F,H$$ $$M\bot H,C|F$$ $$M\bot C|F$$

where the notation in general means:
$$A\bot B|C \Longleftrightarrow P(A \cap B|C)=P(A|C)P(B|C)\Longleftrightarrow P(A|B \cap C) = P(A|C) \Longleftrightarrow\ Given\ C, then\ A,B\ are\ conditionally\ independent$$

The first independence means that if we know the season, we don't need to know if the person has hayfever to diagnose if he has the flu.

So the book states that if we take into account these independencies then:

This parameterization is significantly more compact, requiring only 3+4+4+4+2 = 17 nonredundant parameters, as opposed to 64...

My question is why 17 nonredundant parameters? How did we reach to this result?

In general, directed graphical models allow you to express the joint distribution as a product of conditional distributions,

$$P(X|Y_1, \dots, Y_n),$$

where $Y_i$ is a parent of $x$ for every $i$. If all of these RVs are discrete we can store the above conditional distribution by saving a bunch of values. Of course, for each configuration of values that the $Y_i$'s take we have a (potentially) distinct distribution. Notating the event space of the RV $Y_i$ by $|Y_i|$, that gives us $\prod_i|Y_i|$ different distributions. To be completely clear, there are $\prod_i|Y_i|$ choices of $(y_1, \dots, y_n)$, each yielding a distribution: $$P(X|Y_1=y_1, \dots, Y_n=y_n),$$

Now for each of these, we don't need to record a probability for every value of $X$, because we know they must sum to 1. So we only need to record $(|X|-1)$ values. So in the end, for any discrete conditional as above we need to record $(|X|-1) \cdot \prod_i|Y_i|$ values.

For example, for $P(C|F,H)$, we need to record $(2-1)\cdot(2\cdot 2) = 4$ values.

Edit

To be totally clear: the joint distribution on the 5 events factors to

$$P(S,F,H,M,C) = P(S)\cdot P(D|S) \cdot P(H|S) \cdot P(C|F,H) \cdot P(M|F).$$

I showed you how to compute how many parameters when need to store for $P(C|F,H)$. How many do you need to store for the others?

• OK, I understand the concept of non-redundancy that derives from the probability law. What I don't understand is how to count the elements of the probability space given some independences (I mean practically). I cannot reach to the numbers 3,4,4,4,2. Also, why do we have sum instead of product? – mgus Sep 30 '15 at 20:24
• @KonstantinosKonstantinidis Added to my answer. If you don't understand the computation for $P(C|F,H)$ let me know. – jlimahaverford Sep 30 '15 at 20:33
• OK, I got it now. First, I think you meant $P(F|S)$ instead of $P(D|S)$. I still don't understand the use of sum instead of product to count the size of the probability space. I mean that without the independencies we would have $4 (seasons) \cdot 4 (diseases) \cdot 4 (symptons) = 64$. – mgus Oct 2 '15 at 8:04
• @KonstantinosKonstantinidis were not counting the probability space. We're counting how many parameters determine the probability space. – jlimahaverford Oct 2 '15 at 10:27