Determining the Number of Non-Spurious Arcs in a Learned DAG Model: Investigation of a Bayesian and a Frequentist Approach

Jennifer Listgarten, David HeckermanUAI 2007 · OpenReview

TL;DR

This paper tackles the crucial problem of identifying "real" relationships (non-spurious arcs) within complex graphical models learned from data, particularly in the context of understanding HIV vaccine design. The authors propose and compare both Bayesian and frequentist approaches, finding that the frequentist method, based on controlling the False Discovery Rate, is computationally efficient and performs well, especially in scenarios where learned models might not perfectly represent the data.

What Problem Does This Paper Address?

When building graphical models (like Bayesian Networks or DAGs) from data, the primary goal isn't always prediction. Often, we want to understand the underlying causal or correlational structure – essentially, which variables directly influence or are related to others. This is especially true in fields like computational biology, where researchers want to discover protein interactions or, as in this paper's motivating example, which parts of the HIV virus (peptides) interact with the human immune system's HLA molecules.

The challenge arises because structure learning algorithms can identify many "arcs" (relationships) in a model, but not all of them are truly meaningful or "non-spurious." Some might be artifacts of the learning process or coincidental correlations in the specific dataset. Determining how many of the learned arcs are genuinely significant is critical for guiding further research, experimental validation, and making informed decisions, especially when resources for testing are limited. This paper aims to provide robust methods for quantifying this number.

Methods

The paper presents two main approaches to estimate the number of non-spurious arcs in a learned Directed Acyclic Graph (DAG) model:

  • Bayesian Approach: This method leverages the posterior distribution over all possible model structures. It computes the expected number of true arcs by averaging over these structures, weighted by their posterior probability given the data. The core idea is to integrate out uncertainty about the true model structure.
  • Frequentist Approach: This approach focuses on controlling the False Discovery Rate (FDR). The FDR is the expected proportion of identified "true" hypotheses (in this case, arcs) that are actually false. The authors develop a method that estimates the FDR for a set of learned arcs. This involves generating "null distributions" by permuting the data, which ensures that any arcs found in these permuted datasets are considered false. The observed FDR is then estimated by comparing the number of arcs found in the real data to the number found in these null distributions.

The frequentist approach is highlighted as being non-parametric and computationally more efficient, especially when compared to exact Bayesian calculations which can be intractable for complex models.

Datasets

  • Synthetic CPT-based Alarm Network Data: Used for evaluating the Bayesian and frequentist approaches. Data was generated from the Alarm network (a standard benchmark for Bayesian networks) with varying sample sizes (100 and 1000).
  • Synthetic Noisy-OR HIV Data: Generated from a synthetic model mimicking the structure learned from real HIV data, also used for evaluating the frequentist approach.
  • Real HIV Peptide-HLA Data: The motivating dataset, consisting of observed interactions between 140 peptides and 102 patients with specific HLA molecules. This data was used to train a model and then apply the frequentist approach for real-world prediction.

Key Insights and Ideas

  • The Importance of "Real" Arcs: The paper strongly emphasizes that for many applications, understanding the true underlying structure (non-spurious arcs) is more important than pure predictive accuracy.
  • FDR as a Practical Metric: Controlling the False Discovery Rate is presented as a more practical and less conservative approach than controlling the Family-Wise Error Rate (FWER) when dealing with a large number of hypotheses (arcs).
  • Computational Trade-offs: The Bayesian approach, while theoretically elegant, can be computationally expensive. The frequentist FDR approach offers a more scalable alternative.
  • Non-Parametric Robustness: The frequentist approach's non-parametric nature (relying on data permutations rather than strong distributional assumptions) makes it potentially more robust when the learned model structure doesn't perfectly match the true data-generating process.
  • Bayesian Over-Confidence: In experiments, the Bayesian approach tended to be slightly over-confident, assigning more belief to arcs than warranted, while the frequentist approach was more conservative, especially at higher FDR levels.
  • Prior Sensitivity in Bayesian Methods: The Bayesian method's results can be sensitive to the choice of prior hyperparameters, and the optimal priors for prediction might not be the same as those yielding the most accurate count of non-spurious arcs.

Key Results

  • Both Bayesian and frequentist approaches yielded accurate estimates of the number of non-spurious arcs on synthetic data, particularly at lower FDR levels (higher Positive Predictive Value - PPV).
  • The frequentist approach was found to be significantly more computationally efficient than the Bayesian approach.
  • On synthetic HIV data, the frequentist approach provided accurate PPV estimates in the high PPV range (low FDR), which is crucial for practical applications.
  • When applied to real HIV peptide-HLA data, the frequentist approach identified 168 peptide-HLA relationships with an estimated FDR of approximately 0.3.
  • Experimental validation of eight selected relationships from the real data confirmed their biological relevance.

Limitations and Future Work

  • Bayesian Computational Cost: The exact Bayesian computation of the marginal likelihood can be intractable, often requiring approximations like BIC, which can be slower.
  • Frequentist Conservatism: The frequentist FDR estimation can be overly conservative for larger FDR values (lower PPVs). The authors suggest a sequential permutation approach to potentially mitigate this.
  • Focus on False Positives: The frequentist FDR approach primarily focuses on controlling false positives (spurious arcs) and does not explicitly quantify false negatives (missed arcs).
  • Future Work: The authors suggest investigating the FDR approach with other parameterizations (e.g., logistic regression, decision trees), exploring methods that don't assume a fixed variable ordering, and further developing the sequential permutation approach to address conservatism.

Summary updated

Abstract

In many application domains, such as computational biology, the goal of graphical model structure learning is to uncover discrete relationships between entities. For example, in our problem of interest concerning HIV vaccine design, we want to infer which HIV peptides interact with which immune system molecules (HLA molecules). For problems of this nature, we are interested in determining the number of nonspurious arcs in a learned graphical model. We describe both a Bayesian and frequentist approach to this problem. In the Bayesian approach, we use the posterior distribution over model structures to compute the expected number of true arcs in a learned model. In the frequentist approach, we develop a method based on the concept of the False Discovery Rate. On synthetic data sets generated from models similar to the ones learned, we find that both the Bayesian and frequentist approaches yield accurate estimates of the number of non-spurious arcs. In addition, we speculate that the frequentist approach, which is non-parametric, may outperform the parametric Bayesian approach in situations where the models learned are less representative of the data. Finally, we apply the frequentist approach to our problem of HIV vaccine design.
BibTeX
@inproceedings{listgarten2007determining,
  author = {Jennifer Listgarten and David Heckerman},
  title = {{Determining the Number of Non-Spurious Arcs in a Learned DAG Model: Investigation of a Bayesian and a Frequentist Approach}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=49zt6EbF6sW},
}
Figure