4
$\begingroup$

Imagine a Bayesian Network with binary random variables, with the structure of a binary tree of arbitrary height:

enter image description here

I want to find the minimum number of probabilities that I must store at depth k to describe the entire tree up to that point (i.e. the joint distribution)

  • Starting at depth 0 (the root node A), I only need to store 1 probability, i.e. $P(A = True) = P(a)$ because I get $P(\bar{a}) = 1 - P(a)$ for free.
  • At depth 1, I need to store $P(ABC) = \sum_{ABC} P(A)P(B|A)P(C|A)$.
    • I need to only store $P(a), P(b|a), P(b|\bar{a}), P(c|a), P(c|\bar{a})$ = 5 probabilities. This is because from $P(b|a)$ I get $P(\bar{b}|a) = 1 - P(b|a)$, and $P(\bar{c}|a)$ similarly.
  • At depth 2, using similar logic, I store 1 + 4 + 8 = 13 probabilities
  • And so on.

So at depth k, I store $\sum_{i=0}^{k} 2^{i+1}-1$ probabilities.

Is this correct?

$\endgroup$
1
+50
$\begingroup$

I'm no expert in this field, but I think your reasoning is correct. (I found this pdf helpful in writing the answer.)

Your network is a directed acyclic graph (DAG), which means that the probabilities you need at a particular node are the conditional probability of that node (say, $X$), given every combination of its ancestors (say, $Y_i$, where $i = 1...n$). So, in the general case of a node with $n$ ancestors, you'd need to store $2^n$ probabilities for that particular node (since the "truth table" would have $2^n$ rows).

In your case, each node has only one ancestor. So, you need $2^1 = 2$ probabilities ($P(X|Y)$ and $P(X|\bar{Y})$) for every node that has an ancestor. So, for the overall tree, with $N$ nodes with ancestors and 1 node without an ancestor, you'd need $2*N$ probabilities for the former + 1 probability for the latter.

I think this works out to be the same as your formula (which, by the way, you can simplify to $2^{k+2} - 3$), since a complete binary tree at level $k$ (in your notation) has $2^{k+1} - 1$ total nodes and therefore $2^{k+1} - 2$ nodes with ancestors and 1 without.

$\endgroup$
2
$\begingroup$

From the law of total probability, the state of node $n_j$ given the state of the input node $n_i$ can be expressed as,

(1) $P(n_j) = P(n_j|n_i)P(n_i) + P(n_j|\bar n_i)P(\bar n_i), \forall j>0$,

Now if we can assume,

(2) $P({n_j=1}|n_i)P(n_i)+P({n_j=1}|\bar n_i)P(\bar n_i) = 1$,

that is, $n_j$ is entirely determined by the state of the input node $n_i$, then for the $N-1$ non-root nodes we will only need $N-1$ probabilities.

If we can't assume (2) above then we will need to store the behavior of each node for both input states. For the $N-1$ non-root nodes with binary input this will be $2(N-1)$ PDFs. The total number of PDFs including the root that has no binary input, would be,

(3) Total Quantity of PDFs = $2N-1$, where N = total number of nodes.

EDIT: If you want this total in terms of specific depths, then for depth k we have $2^{k+1}, k>0$.

$\endgroup$
  • $\begingroup$ I use $k$ to be the depth (starting at 0), where there are $2^k$ non-root nodes. So you propose there are $2\times 2^k-1 = 2^{k+1}-1$ probabilities to be stored at depth k? $\endgroup$ – ilanman Dec 25 '16 at 21:15
  • $\begingroup$ The -1 should be outside the summation. $\endgroup$ – fuzzyhedge Dec 25 '16 at 21:42

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.