TL;DR
This paper introduces a novel method to more accurately bound the computational complexity of search algorithms for graphical models. By combining tree decompositions with the concept of hypertree decompositions, the authors exploit problem-specific determinism to achieve bounds that are orders of magnitude tighter than previous methods, leading to better predictions of algorithm performance.
What Problem Does This Paper Address?
Solving complex reasoning problems over graphical models (like belief networks or constraint satisfaction problems) often involves searching through a vast space of possible solutions. Traditional complexity bounds, often based on the "tree width" of the model's underlying graph, are useful but can be overly pessimistic. This is because they don't account for "determinism" – situations where certain variable assignments or function properties inherently prune the search space. For example, in constraint satisfaction, a disallowed tuple immediately eliminates a branch of the search. Similarly, in probabilistic models, zero probabilities can have a similar effect. The challenge is to develop bounds that capture this problem-specific determinism to provide a more realistic estimate of the actual computational effort required.
Methods
The core of this paper lies in refining existing complexity bounds for AND/OR search algorithms. The authors build upon two key ideas:
- Tree Decompositions: These are a standard technique to represent the structure of a graphical model as a tree, where clusters of variables are grouped. The "tree width" of this decomposition provides a bound on complexity.
- Hypertree Decompositions: This is a generalization of tree decompositions that can better capture problem structure, especially when functions (constraints or probabilities) have overlapping scopes. The "hypertree width" is related to the number of functions within these clusters.
The paper's novel contribution is to combine these two concepts. They leverage the structure provided by a bucket tree decomposition (derived from a variable ordering) and then, for each cluster in this decomposition, they apply a greedy covering algorithm. This algorithm aims to select a subset of functions within a cluster that "tightly" cover the variables. The "tightness" of a function refers to the number of relevant entries in its table (e.g., allowed tuples for constraints, non-zero probabilities). By multiplying the tightness of the selected functions and the domain sizes of any remaining uncovered variables, they derive a new bound, termed hwb. This process effectively exploits determinism by prioritizing functions that significantly reduce the search space.
Datasets
The authors evaluated their method on a comprehensive set of benchmarks:
- 112 Bayesian networks from various domains (coding networks, dynamic Bayesian networks, genetic linkage instances, CPCS medical diagnosis networks).
- 30 weighted constraint satisfaction problem (WCSP) instances, including digital circuits, satellite scheduling, and radio frequency assignment problems.
They also mention using a subset of smaller instances for a more direct comparison of their bounds to the exact search space size.
Key Insights and Ideas
- Determinism is Key: The most significant insight is that standard tree-width bounds are often too coarse because they ignore problem-specific determinism. Exploiting this determinism can lead to dramatic reductions in the estimated search space size.
- Hypertree Decomposition as a Tool: While hypertree decompositions themselves don't always yield better bounds in practice (as shown in prior work), the concept of "tightness" from hypertree decompositions is crucial. Applying this concept greedily within the context of a bucket tree decomposition is the paper's innovation.
- Greedy Covering Works: The paper demonstrates that a simple greedy heuristic for selecting "tight" functions within a cluster is effective in producing significantly improved bounds. This suggests that even without a full hypertree decomposition, the idea of function tightness is powerful.
- Bounds Can Be Very Tight: For smaller instances, the proposed bound (hwb) can be remarkably close to the actual search space size, indicating its potential for accurate complexity prediction.
Key Results
- The proposed bound (hwb) consistently outperforms the standard tree-width bound (twb) and the worst-case bound (n·kw+1).
- Improvements are often seen by several orders of magnitude. For example, on pedigree genetic linkage instances, the reduction can be ten orders of magnitude. Digital circuits show improvements of 3-4 orders of magnitude.
- For some smaller instances, the computed bound is very tight, closely matching the exact number of AND nodes in the search graph.
- The computational cost of computing these new bounds is low, typically taking only a few hundred milliseconds.
Limitations and Future Work
- Deterioration for Larger Instances: The authors acknowledge that as problem instances become larger and more complex, the tightness of the bound can deteriorate. This suggests that the structure of the decomposition and the distribution of determinism play a significant role.
- Predicting Determinism's Impact: It's not always predictable when functions with high determinism will have their scopes fully instantiated during search, which affects the effectiveness of the covering heuristic.
- Future Directions:
- Conducting more in-depth comparisons on even larger problem instances.
- Exploring ways to incorporate information propagation down the bucket tree to further refine bounds.
- Using approximate counting methods (like sampling) to estimate cluster sizes.
- Adapting the bounds for optimization tasks and branch-and-bound algorithms.
- Using these bounds to guide static and dynamic variable ordering selection.
- Leveraging the bounds for parallelizing search algorithms across distributed systems.
Summary updated