TL;DR
This paper introduces a deterministic method, "Bound and Collapse" (BC), for learning Bayesian Belief Networks (BBNs) from databases with missing data. Unlike existing iterative methods that are computationally expensive and sensitive to missing data, BC offers a robust and efficient approach that is largely independent of the amount of missing information.
What Problem Does This Paper Address?
Learning Bayesian Belief Networks (BBNs) from data is a powerful technique for modeling complex systems. A crucial step in this process is learning the graphical structure of the network, which represents the dependencies between variables. Traditional methods for this "model selection" task often assume that the input database is complete, meaning every data point for every variable is known. However, real-world databases are frequently incomplete, with missing values. Existing methods to handle missing data, such as the EM algorithm or Gibbs Sampling, are computationally intensive, slow to converge, and their performance degrades significantly with more missing data. This paper addresses the need for a more efficient and robust method to learn BBN structures from incomplete databases.
Methods
The core contribution of this paper is the extension of the "Bound and Collapse" (BC) method, previously used for estimating conditional probabilities in BBNs with missing data, to the task of learning the graphical structure itself.
Here's a breakdown of the approach:
- Bayesian Framework: The paper operates within a Bayesian framework, aiming to find the model with the highest posterior probability given the data. This involves computing the marginal likelihood of the data given a model.
- The Challenge of Missing Data: For complete data, computing the marginal likelihood is straightforward. However, with missing data, this computation becomes intractable. Existing methods approximate this marginal likelihood using iterative techniques.
- Bound and Collapse (BC) for Structure Learning: The paper proposes using BC to estimate the marginal likelihood of the data given a model, even when data are missing. BC works by:
- Bounding: It first bounds the set of possible estimates for the conditional probabilities that are consistent with the available data.
- Collapsing: It then "collapses" these bounds into a single estimate using a convex combination. This collapse is guided by an assumed pattern of missing data.
- Estimating Posterior Precision: The paper also details how to estimate the posterior precision of the BBN parameters using the BC method, which is crucial for the overall model learning process.
- Greedy Search Strategy: The model induction process uses a greedy search strategy, where parents are added to nodes one at a time, selecting the parent that provides the largest contribution to the model's score (based on the BC-estimated marginal likelihood). This is a standard approach for tackling the NP-hard problem of structure learning.
The novelty lies in replacing the computationally expensive approximations of marginal likelihood with the deterministic BC estimation, making the entire structure learning process more efficient and robust to missing data.
Datasets
The paper does not introduce new benchmark datasets. Instead, it uses synthetically generated data based on four predefined generating structures (labeled M1, M2, M3, and M4 in Table 1). These structures are varied in terms of the number of variables and their states. The experiments involve systematically deleting percentages of data (from 100% down to 0%) from these generated complete datasets to simulate varying levels of missingness.
Key Insights and Ideas
- Deterministic Approach for Missing Data: The most significant insight is that a deterministic method (BC) can effectively handle missing data in BBN structure learning, bypassing the need for computationally expensive iterative approximations like EM or Gibbs Sampling.
- Robustness to Missing Data: The BC method demonstrates remarkable robustness. The execution time for learning the BBN structure is largely independent of the percentage of missing data, a stark contrast to traditional iterative methods.
- Quality of Information: The paper shows that even with a significant amount of missing data (e.g., 20% of entries available), the induced BBN structure can still be very close to the true generating structure. This suggests that the remaining data, when processed effectively, can still convey substantial information about the underlying dependencies.
- Coherence with Prior Knowledge: The BC method naturally incorporates prior beliefs (through hyper-parameters) when data is completely missing, ensuring a coherent estimation process even in extreme cases.
- Marginal Probabilities Remain Stable: Even when the induced model slightly differs from the generating structure due to missing data, the estimated marginal probabilities of individual variables remain remarkably similar. This indicates that the learned models are still highly predictive and useful in practice.
Key Results
- Accurate Structure Induction: The experiments show that the BC-based method successfully induces the correct or a very similar graphical structure to the generating model, even when as little as 20% of the data is available.
- Efficient Execution Time: The run times for learning the BBN structure are consistently low and show little variation across different percentages of missing data. For example, in Table 2, the time taken is consistently around 11-13 seconds for models induced from 20% to 100% of the data.
- Accurate Marginal Probabilities: Tables 3, 7, and 9 demonstrate that the marginal probabilities estimated from the induced networks are very close to those obtained from the complete database, highlighting the robustness of the learned conditional probabilities.
- Model Selection Performance: In cases where the induced model differed slightly from the generating structure, the Bayes factor analysis (e.g., exp(-980 + 985) = 148) indicated that the induced model was significantly more likely than the generating structure given the incomplete data, suggesting the method effectively leverages the available information.
Limitations and Future Work
- Assumed Pattern of Missing Data: While the BC method can incorporate an assumed pattern of missing data, the paper notes that in the general case, it relies on the assumption that data are "missing at random." The robustness to departures from this assumption is highlighted, but a deeper investigation into various missing data mechanisms could be a future direction.
- Greedy Search: The paper uses a greedy search strategy for model induction, which is a common heuristic for the NP-hard problem of structure learning. While efficient, greedy search does not guarantee finding the globally optimal structure. Future work could explore integrating BC with more exhaustive search strategies or meta-heuristics.
- Prior Knowledge Integration: The paper mentions the use of exogenous knowledge in a related work (Ramoni and Sebastiani, 1997b). Further exploration into how BC can be more deeply integrated with external knowledge sources for structure learning could be beneficial.
- Continuous Variables: The current work focuses on discrete variables. Extending the BC method to handle continuous variables in BBNs would be a valuable future research direction.
Summary updated