The Lauritzen-Chen Likelihood For Graphical Models

Ilya Shpitser

TL;DR

This paper introduces the Lauritzen-Chen (L-C) likelihood, a novel mathematical framework that provides a consistent, non-redundant, and flexible way to specify likelihoods for both undirected and directed graphical models. Its most significant impact is providing a general likelihood for Bayesian networks that remains identical across an entire Markov equivalence class, preventing researchers from making "unwarranted assumptions" about edge directions during model selection.

What Problem Does This Paper Address?

Graphical models, like Markov Random Fields (MRFs) and Bayesian Networks (BNs), are the bread and butter of probabilistic modeling. However, they face a "consistency" crisis when moving beyond simple Gaussian or categorical data into complex semi-parametric settings.

Two major issues plague current methods:

  1. Incongeniality and Redundancy: In MRFs, specifying "clique potentials" (the functions that describe how groups of variables interact) is tricky. If you aren't careful, different parts of your model might contradict each other (incongeniality) or provide overlapping information (redundancy), making the model unidentifiable or impossible to optimize.
  2. The Equivalence Class Problem: In Bayesian Networks (DAGs), many different graph structures can represent the exact same set of conditional independences (a Markov equivalence class). Standard likelihoods often change depending on which specific graph you pick, even if they are equivalent. This forces researchers to make arbitrary choices about edge orientations that aren't actually supported by the data.

Methods

The author, Ilya Shpitser, synthesizes two previously separate mathematical ideas to create a new "L-C" factorization:

  • Chen’s Density Decomposition: A method from 2007 that uses conditional odds ratios to break down a joint distribution into independent pieces.
  • Lauritzen’s Clique Factorization: A classic 1996 approach that uses Möbius inversion to define potentials over cliques in a graph.

The Innovation: The paper proves that these two decompositions are deeply related. By linking them, the author derives a likelihood composed of variationally independent terms. This means you can change one parameter of the model without needing to adjust the others to keep the total probability distribution valid.

To solve the Bayesian Network problem, the author applies this new likelihood to essential graphs (mixed graphs that represent an entire equivalence class of DAGs). This ensures that the likelihood is mathematically identical for every valid graph in that class.

Datasets

Not discussed in the paper. This is a theoretical statistics paper. Rather than benchmarking on specific datasets, the author provides illustrative examples using:

  • Lattice Graphs: Common in computer vision (image pixels) and physics (spin states).
  • Phylogenetic Trees: Used in computational biology to model evolutionary relationships.

Key Insights and Ideas

  • Variational Independence is King: In many models, if you change one parameter, the "allowable" range for other parameters changes. The L-C likelihood avoids this, making it much easier to use standard optimization tools like gradient descent.
  • Closing the "Sneaking In" Loophole: When performing causal discovery, researchers often pick a specific DAG. If the likelihood depends on edge direction, the software might "prefer" one direction over another for purely mathematical reasons, not because the data actually suggests a causal direction. The L-C likelihood removes this bias.
  • Generalization of Log-Linear Models: The proposed likelihood can be seen as a massive generalization of hierarchical log-linear models. It treats univariate conditionals as "main effects" and generalized odds ratios as "higher-order interactions."

Key Results

  • Theorem 2 & Corollary 1: These establish the formal equivalence between Chen and Lauritzen's work, proving that the resulting terms are non-redundant and variationally independent.
  • The L-C Factorization (Eq. 14): The paper provides a concrete closed-form functional for the likelihood of a Conditional MRF.
  • MEC Invariance: The paper successfully demonstrates that for any Directed Acyclic Graph (DAG), the L-C likelihood based on its "essential graph" is a valid and coherent likelihood that represents the entire Markov equivalence class.

Limitations and Future Work

  • The Normalizing Constant ($Z$): Like most MRF models, the L-C likelihood involves a normalizing constant (or function) that is often computationally "intractable" (NP-hard to compute exactly for complex graphs).
  • Practical Estimators: While the paper provides the mathematical form of the likelihood, it does not provide a "plug-and-play" software implementation. The author notes that future work is needed to integrate this with approximation methods like variational inference or sum-product algorithms.
  • Semi-parametric Implementation: The paper suggests using kernel regressions for the univariate terms, but the practical performance of such a hybrid model remains to be tested in large-scale applications.

Summary updated

Abstract

Graphical models such as Markov random fields (MRFs) that are associated with undirected graphs, and Bayesian networks (BNs) that are associated with directed acyclic graphs, have proven to be a very popular approach for reasoning under uncertainty, prediction problems and causal inference. Parametric MRF likelihoods are well-studied for Gaussian and categorical data. However, in more complicated parametric and semi-parametric settings, likelihoods specified via clique potential functions are generally not known to be congenial {(jointly well-specified)} or non-redundant. Congenial and non-redundant DAG likelihoods are far simpler to specify in both parametric and semi-parametric settings by modeling Markov factors in the DAG factorization. However, DAG likelihoods specified in this way are not guaranteed to coincide in distinct DAGs within the same Markov equivalence class. This complicates likelihoods based model selection procedures for DAGs by ``sneaking in'' potentially unwarranted assumptions about edge orientations. In this paper we link a density function decomposition due to Chen with the clique factorization of MRFs described by Lauritzen to provide a general likelihood for MRF models. The proposed likelihood is composed of variationally independent, and non-redundant closed form functionals of the observed data distribution, and is sufficiently general to apply to arbitrary parametric and semi-parametric models. We use an extension of our developments to give a general likelihood for DAG models that is guaranteed to coincide for all members of a Markov equivalence class. Our results have direct applications for model selection and semi-parametric inference.
BibTeX
@inproceedings{shpitser2023lauritzen,
  author = {Ilya Shpitser},
  title = {{The Lauritzen-Chen Likelihood For Graphical Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
}
Figure