Cutset Conditioning Scheme
- is an extension of exact inference algorithm
- is based on the fact, that observing the value of certain variables can simplify the variable elimination process
- idea: when a variable is not observed, we can enumerate all of its possible values, then for each value perform an exact inference algorithm of your choice (e.g. Variable Elimination), and then sum the results
- the cutset is the set of unobserved variables we are conditioning on
- in terms of number of operations, the conditioning algorithm offers no benefit over the variable elimination algorithm. However, it offers a continuum of time-space trade-offs, which can be extremely important in cases where the factors created by variable elimination are too big to fit in main memory
Cutset Conditioning - Example
Click here to expand...
suppose we have a graphical model above with binary variables
Suppose Cutset = {𝐿}:
- this results in 2 networks, each with 𝐿 instantiated with a corresponding value: 0 or 1
- for each instantiated network we feed it into an exact inference algorithm and record its output probability
- sum all probabilities and return that result
Suppose Cutset = {𝐿,𝐴}:
- this results in 4 networks, each with 𝐿 and 𝐴 instantiated with a corresponding value: 0 or 1
- for each instantiated network we feed it into an exact inference algorithm and record its output probability
- sum all probabilities and return that result
Cutset Conditioning - Problems
- if the cutset consists of 𝑤 nodes each with 𝑑 states, then we would need to run the exact inference algorithm𝑑𝑤 times
- to combine the result of the many possible instantiations of the cutset we need to find priors to each one