Exact inference using Variable Elimination on a general Bayesian Network has time complexity governed by:
Variable elimination time complexity is exponential in the tree-width w of the elimination ordering.
Given P(A) = 0.4, P(B|A) = 0.7, and P(B|~A) = 0.2, calculate P(B) using Law of Total Probability:
$P(B) = P(B|A)P(A) + P(B|~A)P(~A) = 0.7*0.4 + 0.2*0.6 = 0.28 + 0.12 = 0.40.$
If P(A, B) = P(A) * P(B), then variables A and B are:
Factorization P(A, B) = P(A)P(B) is the definition of unconditional (marginal) independence.
Naive Bayes classifier assumes that all feature attributes $X_{i}$ are:
$Naive Bayes assumes P(X1, X2, ... | Y) = prod P(Xi | Y).$
In Variable Elimination, 'summing out' a variable X from a factor f(X, Y, Z) is called:
Summing out a variable reduces factor dimensionality by marginalizing over all assignments of X.