2
$\begingroup$

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.

$\endgroup$

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.