Parameter and Structure Learning in Nested Markov Models

Ilya Shpitser, Thomas S. Richardson, James M. Robins, Robin J. EvansarXiv 2012 · DOI · arXiv

Abstract

The constraints arising from DAG models with latent variables can be naturally represented by means of acyclic directed mixed graphs (ADMGs). Such graphs contain directed and bidirected arrows, and contain no directed cycles. DAGs with latent variables imply independence constraints in the distribution resulting from a 'fixing' operation, in which a joint distribution is divided by a conditional. This operation generalizes marginalizing and conditioning. Some of these constraints correspond to identifiable 'dormant' independence constraints, with the well known 'Verma constraint' as one example. Recently, models defined by a set of the constraints arising after fixing from a DAG with latents, were characterized via a recursive factorization and a nested Markov property. In addition, a parameterization was given in the discrete case. In this paper we use this parameterization to describe a parameter fitting algorithm, and a search and score structure learning algorithm for these nested Markov models. We apply our algorithms to a variety of datasets.

Introduction

In causal inference, Directed Acyclic Graphs (DAGs) are standard tools for representing variable influences. However, real-world data often lacks key variables, which are "latent" or unobserved. Standard tools like conditional independence tests frequently fail to distinguish between different causal structures when variables are hidden, leading to large equivalence classes and uninformative results.

Latent variable models often imply deeper constraints, such as the Verma constraint, which are not simple conditional independences. These "dormant" independences emerge only after a "fixing" operation—dividing the distribution by a conditional density. While the theory for "Nested Markov Models" (models defined by these constraints) has been established, practical algorithms for parameter fitting and automated structure discovery have been missing. This paper introduces the first such algorithms.

Methods

The authors bridge the gap between theory and practice with two main contributions:

Parameter Fitting (Q-FIT)

To find the Maximum Likelihood Estimate (MLE) for a given graph, the authors utilize a specific parameterization for discrete data. They developed the Q-FIT algorithm, which iteratively cycles through each vertex in the graph and uses gradient ascent to optimize parameters. The algorithm ensures that resulting values remain "coherent" (representing valid probabilities) through a system of linear constraints.

Structure Learning

To discover the optimal graph for a dataset, a Search and Score approach is employed:

  • Score: The Bayesian Information Criterion (BIC) is used to balance model fit against complexity.
  • Search: Given the vast space of Acyclic Directed Mixed Graphs (ADMGs), the authors use a greedy local search augmented with a tabu search meta-heuristic. This helps the algorithm escape local optima and explore the score surface more effectively.
Comparison of a DAG with latent variables (a) and its corresponding Acyclic Directed Mixed Graph (ADMG) representation (b).

Key Insights: Implicit Latents and Shrinking Equivalence Classes

A major advantage of this approach is that it represents latent variables implicitly using ADMGs. As shown in Figure 1, the bidirected edges in an ADMG capture the influence of hidden variables without requiring the researcher to specify their number or state space.

By utilizing nested constraints, the number of models that appear observationally equivalent drops significantly. For 4-node graphs, the number of equivalence classes shrinks from 248 under standard logic to just 84. This makes causal discovery much more precise by leveraging "post-truncation" independences that standard methods ignore.

Key Results

The algorithms were evaluated using simulated datasets where the ground truth causal structure was known, specifically a 4-node model (containing a Verma constraint) and a more complex 5-node model.

Probability of correctly learning the true 4-node and 5-node models as a function of sample size.

As shown in Figure 2, the search-and-score algorithm demonstrated strong performance that improved with sample size. With 5,000 samples, the algorithm correctly recovered the 4-node model approximately 67% of the time and the 5-node model approximately 76% of the time.

Additionally, the authors found that "exotic" nested constraints occur in about 25% of 4-node mixed graph equivalence classes, suggesting they are a common and valuable feature in latent variable modeling rather than a theoretical rarity.

Limitations and Future Work

Despite these advances, challenges remain. The search space for ADMGs grows exponentially, making structure discovery for models with dozens of variables computationally demanding. Furthermore, the current Q-FIT algorithm assumes strictly positive counts; sparse data with many zeros requires more complex statistical handling. Finally, while the paper provides a conjecture for 4-node equivalence, a general theory of observational equivalence for nested Markov models across any number of nodes remains an open research question.

Summary updated

Abstract

The constraints arising from DAG models with latent variables can be naturally represented by means of acyclic directed mixed graphs (ADMGs). Such graphs contain directed and bidirected arrows, and contain no directed cycles. DAGs with latent variables imply independence constraints in the distribution resulting from a 'fixing' operation, in which a joint distribution is divided by a conditional. This operation generalizes marginalizing and conditioning. Some of these constraints correspond to identifiable 'dormant' independence constraints, with the well known 'Verma constraint' as one example. Recently, models defined by a set of the constraints arising after fixing from a DAG with latents, were characterized via a recursive factorization and a nested Markov property. In addition, a parameterization was given in the discrete case. In this paper we use this parameterization to describe a parameter fitting algorithm, and a search and score structure learning algorithm for these nested Markov models. We apply our algorithms to a variety of datasets.
BibTeX
@misc{shpitser2012parameter,
  author = {Ilya Shpitser and Thomas S. Richardson and James M. Robins and Robin J. Evans},
  title = {{Parameter and Structure Learning in Nested Markov Models}},
  year = {2012},
  eprint = {1207.5058},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1207.5058},
}
Figure