Counting non-reduntant parameters in probabilistic graphical models

Question

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?

Answer 1

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?