Cutset conditioning is a method for performing Tree Decomposition on a dependency graph. By identifying and conditioning on the “cut set” of the graph, a tree structure is produced.
The cut set of a graph is the set of variables which, if removed, will “cut” all loops in the graph and produce an acyclic graph.
Loop-cutset decomposition (Loop-cutset conditioning) uses [http://en.wikipedia.org/wiki/Decomposition_method_(constraint_satisfaction)#Cycle_cutset Cutset-Conditioning] to transform a belief graph into a tree structure by removing large-degree variables from the network. It improves time performance at the cost of space. The result is a forest of probability trees which can be easily processed by Belief Propagation. Unfortunately, the resulting cutset forest forms a tree which takes additional memory and must be searched over via tree search spaces.
- Input is a belief network.
- Identify the cycle cutset: the set of nodes which must be removed in order to produce a tree.
- For each node in this cutset:
- use VEC on that node
- Output is a forest of probability trees
Inference work is exponential in $C$ for cycle [http://en.wikipedia.org/wiki/Cut_set cutset] of size $C$. $ C + 1 > w$ for cutset size $C$ and induced-width w. For example, in a chain of cliques, the induced width is a function of clique size while the cutset is a function of the total number of nodes in the graph. Finding a minimal cycle cutset is not easy.
Because full loop-cutset decomposition produces a very large graph, it is generally better to not condition all the way to a tree structure but to stop when some target graph width $\omega$ is met. This is called a w-cutset algorithm.
Cutset Selection
Small cycle-cutsets require a smaller number of tree-solving algorithms to be run, but finding a minimal-size cycle-cutset is [http://en.wikipedia.org/wiki/Feedback_vertex_set NP-complete]. One heuristic for quickly choosing a cutset is to perform a depth-first search.
Variable Elimination Conditioning
Variable Elimination Conditioning, or VEC, is the fundamental operation of cutset conditioning.
VEC-Evidence
This is an algorithm for using VEC to optimize Bucket Elimination inference:
- Use VEC to decompose the belief graph into a poly tree
#* Each sub-tree is a dependency graph of some kind #* The main tree is a tree of variable assignments leading to a sub-tree
- Solve each sub-tree (including any evidence that applies) e.g. using Bucket Elimination
- Sum over the main tree for the final probability of all evidence
W-cutset
For a target treewidth $\omega$ , run loop-cutset decomposition but stop when the target width is achieved. Time complexity is $O(n * k^{c + \omega + 1})$ Space complexity is $O(k^\omega)$
- * $n$ is number of variables
- * $c$ is the number of variables in the cutset
- * $k$ is the domain size
- * $\omega$ is the treewidth
It can be shown that $c \geq \omega - 1$. So decreasing $\omega$ results in a greater time requirement and lesser space requirements.
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 4.0 International