AND/OR Search Spaces can capture the independencies in the graphical model to yield OR Search Trees that are exponentially smaller than the standard search tree (OR Search Tree). AND/OR search tree is bounded exponentially by the height of a pseudo tree that spans the graphical model. The AND/OR Search Tree may contain redundancy and can be removed yielding AND/OR Search Graphs. These additional savings can reduce the size of the AND/OR Search Space further to the point that it can be guaranteed to be no larger than exponentially in the graphical model treewidth
AND/OR Search Space - Representation Types
AND/OR Search Space - AOT & AOG Other Stuff
- AOT & AOG - Finding Good Pseudo Tree
- AOT & AOG - Solving Probabilistic Inference Queries
- AOT & AOG - Using Tree Decomposition as Guiding Pseudo Tree
AND/OR Search Space - Complexity Comparison (AOT vs AOG)
Click here to expand...
given:
- a graphical model 𝒢, where:
- 𝑘 bounds the domain size
- 𝑛 is the number of variables
- a primal graph 𝐺 of 𝒢
- a pseudo tree 𝑇 of 𝐺, where 𝑇 has height 𝘩
- an extended graph 𝐸 of 𝐺 relative to 𝑇, where 𝐸 has induced width 𝑤
AOT Complexity
AOG Complexity
- memory-space complexity = 𝑂(𝑛)
- search-space-size/time complexity = 𝑂(𝑛𝑘𝘩)
Using Tree Decomposition as Pseudo Tree
a tree decomposition of a primal graph 𝐺 can be used as a guiding pseudo tree 𝑇
given:
- tree decomposition of treewidth 𝑤, then the height 𝘩 satisfies 𝘩 ≤ 𝑤·𝑙𝑜𝑔(𝑛)
search-space-size/time complexity is:
- search-space-size/time complexity = 𝑂(𝑛·𝑘𝑤·𝑙𝑜𝑔(𝑛))
- memory-space complexity = 𝑂(𝑛𝑘𝑤)
- search-space-size/time complexity = 𝑂(𝑛𝑘𝑤)
Using Tree Decomposition as Pseudo Tree
a tree decomposition of a primal graph 𝐺 can be used as a guiding pseudo tree 𝑇
given:
search-space-size/time complexity is:
- Context Minimal AND/OR Graph is bounded by 𝑂(𝑛·𝑘𝑤)
- Context Minimal OR Search Graph is bounded by 𝑂(𝑛·𝑘𝑤·𝑙𝑜𝑔(𝑛))
Summary
- AOT is bounded exponentially by the height of the pseudo tree
- AOG is bounded exponentially by induced-width of pseudo tree
It is not possible to generate a pseudo tree that is optimal w.r.t. both: induced width and height (e.g. chain pseudo tree)