It is often the case that a search space that is a tree can become a graph if nodes that root identical search subspaces, or correspond to identical subproblems, are identified. Any two such nodes can be merged, yielding a graph and thus reducing the size of the search space

read: OR Search Trees (AOT)

AND/OR Search Graph - Example

Click here to expand...

given a constraint graph above where:

• each variable have domain {1, 2, 3}
• each node should be assigned a value such that adjacent nodes have different values

we choose some pseudo tree. lets say it is the same as the constraint graph

the OR Search Tree (shown below) is guided by the pseudo tree

Observe that at level 3 of the OR Search Tree, node ⟨𝑌, 1⟩ appears twice, (and so are ⟨𝑌, 2⟩ and ⟨𝑌, 3⟩) (not shown explicitly in the figure). Clearly however, the subtrees rooted at each of these two AND nodes are identical and they can be merged because in this tree model, any specific assignment to 𝑌 uniquely determines its rooted subtree

the result after merging all identical subtrees, is an AND/OR Search Graph shown below

AND/OR Search Graph - Intuition on Merging Subtrees (Context Minimal AND/OR Search Graph “CM-AOG”)

Click here to expand...

Assume a given weighted AND/OR search graph 𝑆_𝑇’ of a graphical model 𝒢 and assume two paths: 𝑝₁ and 𝑝₂ ending at nodes at level 𝑖 and having the same label 𝑥_𝑖. These nodes can be merged iff the weighted search subgraphs rooted at these nodes are identical. The merge operator, 𝑚𝑒𝑟𝑔𝑒(𝑛𝑜𝑑𝑒-1, 𝑛𝑜𝑑𝑒-2), redirects all the arcs going into 𝑛𝑜𝑑𝑒-2 into 𝑛𝑜𝑑𝑒-1 and removes 𝑛𝑜𝑑𝑒-2 and its subgraph

We can generate the AND/OR search tree and then recursively merge identical subtrees going from leaves to root. This, however, requires generating the whole search tree first, which would still be costly. It turns out that for some nodes it is possible to recognize that they can be merged by using graph properties only, namely based on their contexts. The context of a variable is the set of its ancestor variables in the pseudo tree T that completely determine the conditioned subproblems below it

The general idea of a context is to identify a minimal set of ancestor variables, along the path from the root to the node in the pseudo tree, such that when assigned the same values they yield the same conditioned subproblem, regardless of value assigned to the other ancestors

given:

• a graphical model 𝒢 is a tuple 𝒢 = ⟨𝐗, 𝐃, 𝐒, 𝐅, 𝐂⟩
• a primal graph 𝐺 of 𝒢
• a pseudo tree 𝑇 of 𝐺
• an extended graph 𝐸 of 𝐺 relative to 𝑇

induced width of a pseudo tree

the induced width of 𝐺 relative to a pseudo tree 𝑇, is the maximum width of its induced graph of extended graph 𝐸. This induced graph is obtained by recursively connecting the parents of each node in the extended graph, going from leaves to root along each branch

ancestors - descendants

• 𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟𝑠 of 𝑋_𝑖 are the nodes from 𝑋_𝑖to the root of 𝑇
• 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡𝑠 of 𝑋_𝑖in are any nodes below 𝑋_𝑖 in 𝑇

parents - parent-separators

• 𝑝𝑎𝑟𝑒𝑛𝑡𝑠 of 𝑋_𝑖 are any 𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟𝑠 of 𝑋_𝑖 that are connected (in 𝐺) to either:
  • 𝑋_𝑖
  • 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡𝑠 of 𝑋_𝑖
• 𝑝𝑎𝑟𝑒𝑛𝑡-𝑠𝑒𝑝𝑎𝑟𝑎𝑡𝑜𝑟 of 𝑋_𝑖 are 𝑋_𝑖 plus the 𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟𝑠 of 𝑋_𝑖that are connected (in 𝐺) to 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡𝑠 of 𝑋_𝑖

We use both in order to characterize 2 types of merging: AND node merge & OR node merge

• 𝑝𝑎𝑟𝑒𝑛𝑡𝑠 of 𝑋_𝑖 separate the (𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟𝑠 of 𝑋_𝑖) from (𝑋_𝑖 and its 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡𝑠) in 𝐺
• 𝑝𝑎𝑟𝑒𝑛𝑡-𝑠𝑒𝑝𝑎𝑟𝑎𝑡𝑜𝑟 of 𝑋_𝑖 separate the (𝑎𝑛𝑐𝑒𝑠𝑡𝑜𝑟𝑠 of 𝑋_𝑖) from (its 𝑑𝑒𝑠𝑐𝑒𝑛𝑑𝑎𝑛𝑡𝑠) in 𝐺

It is also easy to see that each variable 𝑋_𝑖 and its 𝑝𝑎𝑟𝑒𝑛𝑡𝑠 form a clique in the induced pseudo-graph

relations between contexts

• if 𝑋 has a single child 𝑌 in 𝑇, then 𝑝𝑎𝑟𝑒𝑛𝑡-𝑠𝑒𝑝𝑎𝑟𝑎𝑡𝑜𝑟𝑠(𝑋) = 𝑝𝑎𝑟𝑒𝑛𝑡𝑠(𝑌)
• if 𝑋 has children 𝑌₁, …, 𝑌_𝑘 in 𝑇, then 𝑝𝑎𝑟𝑒𝑛𝑡-𝑠𝑒𝑝𝑎𝑟𝑎𝑡𝑜𝑟𝑠(𝑋) = ⋃_{1≤𝑖≤𝑘}[𝑝𝑎𝑟𝑒𝑛𝑡𝑠(𝑌_𝑖)]

context

𝑐𝑜𝑛𝑡𝑒𝑥𝑡(𝑋_𝑖) is defined as:

• if 𝑋_𝑖is an AND node
  • 𝑐𝑜𝑛𝑡𝑒𝑥𝑡(𝑋_𝑖) = 𝑣𝑎𝑙(𝑝𝑎𝑡𝘩(𝑛₁))[𝑝𝑎𝑟𝑒𝑛𝑡-𝑠𝑒𝑝𝑎𝑟𝑎𝑡𝑜𝑟(𝑋_𝑖)]
• if 𝑋_𝑖is an OR node
  • 𝑐𝑜𝑛𝑡𝑒𝑥𝑡(𝑋_𝑖) = 𝑣𝑎𝑙(𝑝𝑎𝑡𝘩(𝑛₁))[𝑝𝑎𝑟𝑒𝑛𝑡𝑠(𝑋_𝑖)]

context-based merge operators

let:

• 𝐺^𝑇*be the induced pseudo tree of 𝑇
• 𝑝𝑎𝑡𝘩(𝑋₁) & 𝑝𝑎𝑡𝘩(𝑋₂) be any paths in an AND/OR search graph

if both are true:

• 𝑋₁and 𝑋₂are either: both AND nodes or both OR nodes
• 𝑐𝑜𝑛𝑡𝑒𝑥𝑡(𝑋₁) = 𝑐𝑜𝑛𝑡𝑒𝑥𝑡(𝑋₂)

then the AND/OR search subtrees rooted at 𝑋₁ and 𝑋₂ can be merged

Context Minimal AND/OR Search Graph

The AND/OR Search Graph of graphical model 𝒢 guided by a pseudo-tree 𝑇 that is closed under context-based merge operator, (namely no more merging is possible), is called the Context Minimal AND/OR Search Graph and is denoted by 𝐶𝑀_𝑇(𝒢)

AND/OR Search Graph - CM-AOG Examples

Click here to expand...

given primal graph above, we will show 2 examples with of the following steps:

• choose a guiding pseudo tree
• form an AND/OR Search Tree based on guiding pseudo tree
• find contexts of each variable, by computing the extended graph and then its induced graph
• use the contexts to merge subtrees
• end up with a context minimal AND/OR Search Graph

Example 1

Example 2

For the primal graph above consider the chain pseudo tree 𝑑 = (𝑋, 𝑌, 𝑇, 𝑅, 𝑍, 𝐿, 𝑀) this guiding pseudo tree would construct OR Search Tree as shown below (note: since the guiding pseudo tree is a chain the AND/OR Search Tree is the same as an OR Search Tree) now we merge the subtrees of the OR Search Tree based on 𝑐𝑜𝑛𝑡𝑒𝑥𝑡 whenever possible pseudo tree - only black edges extended graph - includes gray edges induced graph of extended graph - includes gray edges & blue edges induced-width of induced-graph is 3 the context of: 𝑋 is 𝑋 𝑌 is 𝑋𝑌 𝑇 is 𝑋𝑌𝑇 (since the induced graph has the arc (𝑇,𝑋)) 𝑅 is 𝑋𝑅 𝑍 is 𝑍 𝐿 is 𝑍𝐿 𝑀 is 𝑀 The guiding chain pseudo tree would produce an Context Minimal AND/OR Search Graph equivalent to an Context Minimal OR Search Graph (“minimal” means all possible merges are made) Indeed in the first three levels of the minimal OR search graph in figure belowthere are no merged nodes

In contrast, for the primal graph above if we consider the pseudo tree of any DFS ordering, the context of every node is itself yielding a single appearance of each AND node having the same assignment annotation in the minimal AND/OR graph this guiding pseudo tree would construct an OR Search Tree as shown below now we merge the subtrees of the OR Search Tree based on 𝑐𝑜𝑛𝑡𝑒𝑥𝑡 whenever possible pseudo tree (any DFS ordering) - black edges extended graph - same induced graph of extended graph - same induced-width of induced-graph is 1 the context of: 𝑋 is 𝑋 𝑌 is 𝑌 𝑇 is 𝑇 𝑅 is 𝑅 𝑍 is 𝑍 𝐿 is 𝐿 𝑀 is 𝑀 The guiding pseudo tree would produce an Context Minimal AND/OR Search Graph as shown below (“minimal” means all possible merges are made)

AND/OR Search Graph - CM-AOG Complexity

Click here to expand...

Since each context must appear only once in the CM-AOG (different appearances should be merged) the number of nodes in the CM-AOG cannot exceed the number of different contexts. Since the context’s scope size is bounded by the induced-width of a pseudo-tree ordering that guides it, the size of the CM-AOG can be bounded exponentially by the induced-width along the pseudo-tree ordering

given:

• a graphical model 𝒢, where:
  • 𝑘 bounds the domain size
  • 𝑛 is the number of variables
• a primal graph 𝐺 of 𝒢
• a pseudo tree 𝑇 of 𝐺
• an extended graph 𝐸 of 𝐺 relative to 𝑇, where 𝐸 has induced width 𝑤

the size of the CM-AOG 𝐶𝑀_𝑇(𝒢) based on 𝑇 is:

• 𝑂(𝑛·𝑘^𝑤)

since 1 ≤ 𝑤 ≤ 𝑛, then the size can range from:

• 𝑂(𝑛·𝑘) to 𝑂(𝑛·𝑘^𝑛)

since the CM-AOG size is bounded by 𝑂(𝑛·𝑘^𝑤), we want to find a pseudo tree ordering of minimum induced-width 𝑤

AND/OR Search Graph - Other Stuff

• AOT & AOG - Finding Good Pseudo Tree
• AOT & AOG - Solving Probabilistic Inference Queries
• AOT & AOG - Using Tree Decomposition as Guiding Pseudo Tree