TL;DR
This paper investigates the computational complexity of combining multiple belief networks (BNs) from different experts into a single consensus network. The authors demonstrate that many of the operations required for this structural fusion are NP-hard, suggesting that finding optimal consensus networks is generally intractable and that heuristic approaches are necessary.
What Problem Does This Paper Address?
In knowledge-based systems, a common scenario involves integrating information from multiple experts, each providing their domain knowledge in the form of a belief network. The challenge lies in combining these independently constructed BNs into a single, coherent "consensus" BN that represents a unified view. This consensus BN is needed before specific case data is considered, allowing for a prior agreement on the structure and relationships within the domain. The paper focuses on the "structural combination" aspect, specifically how to merge the underlying graphical structures of these BNs, which is crucial for representing combined probabilistic dependencies.
Methods
The paper delves into the theoretical underpinnings of combining belief networks by analyzing the complexity of operations on abstract independence models and their graphical representations (DAGs). They define concepts like "recursive basis" and "k-union-DAGs" to formalize the process of extracting independencies from individual networks and combining them. The core of their methodology involves reducing known NP-hard problems (like the Minimum Feedback Arc Set problem) to problems related to combining belief networks. This reduction technique is used to prove that certain operations, such as finding minimal sets of arcs to reverse to make a combined graph acyclic, are themselves NP-hard.
Datasets
Not discussed in the paper. The paper is theoretical and focuses on the complexity of algorithms rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Structural Combination is Hard: The most significant insight is that merging the graphical structures of belief networks from multiple experts is computationally challenging. Many fundamental operations required for this fusion are NP-hard.
- Heuristics are Necessary: Due to the NP-hard nature of optimal solutions, the paper strongly advocates for the use of heuristic methods to construct "good" consensus networks. This means accepting solutions that are not guaranteed to be optimal but are computationally feasible.
- Graph Theory is the Bottleneck: While combining probabilities from experts is relatively well-understood, the paper highlights that the complexity lies primarily in the graph-theoretic aspects of combining the network structures.
- Abstract vs. Graphical Models: The intractability holds true for both abstract independence models and their graphical representations (DAGs), indicating a fundamental difficulty in consensus formation.
Key Results
The paper establishes that several key operations for combining belief networks are NP-hard. Specifically:
- MRS (Minimal Reversal Set) is NP-hard: Finding a minimal set of arcs to reverse in a digraph to make it acyclic is NP-hard.
- DMRS (Digraph Reversal for Consensus) is NP-hard: This problem, related to making a combined graph acyclic by reversing arcs in one of the input graphs, is also NP-hard.
- 2DMRS (2-Digraph Reversal for Consensus) is NP-hard: Allowing reversals in both input graphs for consensus also remains NP-hard.
- MNAS (Minimizing Arc Reversals for Consensus) is NP-hard: Minimizing the number of new arcs generated by reversals to achieve an acyclic union-DAG is NP-hard.
- 2MNAS (2-Digraph Minimizing Arc Reversals) is NP-hard: Extending MNAS to allow reversals in both input graphs also results in an NP-hard problem.
These results imply that finding an "optimal" consensus network that perfectly captures all agreed-upon independencies is generally infeasible.
Limitations and Future Work
The authors acknowledge that their analysis, while theoretical, points towards the need for practical, heuristic approaches. They mention that research on developing such heuristics is ongoing. Future work could focus on:
- Developing and evaluating specific heuristic algorithms for constructing consensus belief networks.
- Exploring how to combine the domain knowledge with the topology of contributed models to guide these heuristics.
- Investigating the complexity of other operations related to consensus BN generation, which they suggest are likely also NP-hard.
- Potentially exploring the application of concepts like "entailment among belief networks" to this problem, though its applicability is noted as unclear.
Summary updated