I am just getting into Bayesian networks, and I am having a hard time understanding how this algorithm works: http://pgm.stanford.edu/Algs/page-79.pdf
(The algorithm is from Probabilistic Graphical Models by Koller and Friedman. I couldn't find an online pdf version, and reluctant to buy the book from amazon just yet...)

I am especially lost on lines 4 and 5 of the algorithm:

  1. In line 4, how do I pick the subset U'? (I guess this is also a question of how to search this variable space) If i assume to just remove one variable at a time, would that work? Since I am not looking for a P-map but just a potential set of I-maps?

  2. This is probably a very silly question, but I don't really understand how I determine the independence in line 5. Especially assuming this is strictly derived from some data with no real known network structure.

I think I have seen a similar idea in some other places also as:

As long as the following holds true,
$$ P(X_i|\{X_1, ... , X_{i-1}\}) = P(X_i|U') $$ keep dropping variables from U'.

However, I am not quite sure how to test this? Some suggest to use chi-squared if the variables are binary. And for the sake of simplicity let's say that is the case. But I don't understand how these probability distributions can then be compared in this way, given the lengths wouldn't match?

Let's say I have 4 binary variables: $\{A, B, C, D\}$, how would I determine line 5 for $ (B \perp \{A, C, D\}\ −\ \{A,C\}\ |\ \{A,C\}) \in I$ ?

Thanks in advance for any help or other reference suggestions.


Your Answer

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

Browse other questions tagged or ask your own question.