PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Mixed Graphical Models

Jason D. Lee, Trevor J. Hastie

arXiv:1205.5012v3stat.MLcs.CVcs.LGmath.OC

TL;DR

The paper asks how to learn edge structure in graphical models with both continuous and discrete variables, where prior work treated Gaussian and discrete cases separately. It introduces a pairwise mixed model with regression-based conditionals and a symmetric group-lasso structure-learning scheme, and establishes consistency under stated conditions while reporting strong synthetic recovery.

  • Problem

    Structure learning for mixed continuous-discrete graphical models is needed because prior approaches mainly addressed continuous Gaussian and discrete data separately.

  • Method

    The paper introduces a pairwise mixed graphical model whose conditionals are Gaussian linear and multiclass logistic regressions, estimated with computationally efficient pseudolikelihood and symmetric group-lasso penalties.

  • Results

    Under stated conditions, pseudolikelihood and maximum likelihood are model-selection consistent; with n = 1000 samples, pseudolikelihood recovered the correct edge set with probability nearly 1 in synthetic experiments.

  • Takeaways & Limitations

    The unified model extends Gaussian and discrete pairwise graphical-model structure learning to mixed data while retaining convex optimization procedures for edge recovery.

  • Takeaways & Limitations

    Exact maximum-likelihood estimation remains computationally difficult because evaluating the normalizing constant requires a high-dimensional integral, and consistency relies on conditions including restricted strong convexity and an irrepresentable condition.

Abstract

from arXiv · show

We consider the problem of learning the structure of a pairwise graphical model over continuous and discrete variables. We present a new pairwise model for graphical models with both continuous and discrete variables that is amenable to structure learning. In previous work, authors have considered structure learning of Gaussian graphical models and structure learning of discrete models. Our approach is a natural generalization of these two lines of work to the mixed case. The penalization scheme involves a novel symmetric use of the group-lasso norm and follows naturally from a particular parametrization of the model.

1 Introduction

The paper addresses structure learning for graphical models containing both continuous and discrete variables, extending separate Gaussian and discrete-model research paths. It proposes a mixed model intended to support structure learning through a unified formulation.

  • Existing structure-learning methods largely follow separate paths for continuous Gaussian data and discrete-valued data.
  • Many practical datasets combine continuous measurements with discrete attributes, motivating mixed graphical models.Examples include population surveys, genomics, and URL-click data.
  • The proposed model connects continuous and discrete graphical models through conditional Gaussian linear regression and multiclass logistic regression.
  • It reduces to a pairwise Markov random field for exclusively discrete variables and a Gaussian graphical model for exclusively continuous variables.
  • Its structure-learning penalty uses symmetric group-lasso norms for parameter singletons, vectors, and blocks.

2 Mixed Graphical Model

The mixed graphical model represents continuous and discrete variables in a pairwise Markov random field whose conditionals are standard regression models. Its special cases, related-model comparisons, and convex structure-learning formulation define the model’s scope.

  • Mixed Graphical Model: The model is a pairwise Markov random field parametrized by continuous, discrete, and continuous-discrete edge and node potentials.The parameter blocks include βst, αs, ρsj(yj), and φrj(yr,yj).
  • Conditional distributions: Its conditional distributions are Gaussian linear regressions for continuous variables and multiclass logistic regressions for discrete variables.
  • Special cases: The model simplifies to a multivariate Gaussian with only continuous variables and a pairwise discrete Markov random field with only discrete variables.
  • Conditional distributions: Conditional on the discrete variables, the continuous variables are multivariate Gaussian with a common covariance and means that depend additively on discrete-variable values.
  • Related mixed models: Compared with Lauritzen’s more general mixed model, its common-covariance, additive-mean, and pairwise-discrete-factorization assumptions reduce parameter complexity.The more general model requires exponentially many state-specific means and covariance matrices in the binary-discrete case.
  • Estimation and structure learning: The paper uses pseudolikelihood and node-wise regressions that enforce symmetry because exact maximum likelihood is difficult and the primary goal is graph-structure learning.
  • Related mixed models: The work claims to be the first to consider convex optimization procedures for learning edge structure in mixed graphical models.

3 Parameter Estimation: Maximum Likelihood and Pseudolikelihood

The mixed model supports maximum-likelihood and pseudolikelihood estimation, but the high-dimensional normalizing constant makes maximum likelihood computationally difficult. Pseudolikelihood instead uses conditional regressions with shared parameters, yielding a jointly convex objective under β_ss > 0.

  • Maximum Likelihood: Maximum-likelihood estimation minimizes the samples’ negative log-likelihood, but evaluating the high-dimensional normalizing constant Z(Θ) is computationally difficult.The negative log-likelihood remains convex, so the obstacle is computing Z(Θ), not the objective’s convexity.
  • Pseudolikelihood: Pseudolikelihood estimates parameters from the product of all conditional distributions and is computationally efficient and consistent.Each parameter block appears twice, once in each endpoint’s conditional distribution.
  • Conditional Models: Continuous-variable conditionals are Gaussian linear regressions, while discrete-variable conditionals are multinomial logistic regressions.Discrete predictors contribute level-specific additive effects, whereas continuous predictors contribute linear effects.
  • Pseudolikelihood: The negative log pseudolikelihood is jointly convex in all model parameters over the region β_ss > 0.This is stated as Proposition 1 and proved in the appendix.
  • Alternative Estimation: Separate node-wise regressions estimate each conditional independently, using approximately twice as many parameters because they do not enforce parameter sharing.This approach is an asymmetric form of pseudolikelihood and extends neighborhood-selection methods to the mixed setting.

4 Conditional Independence and Penalty Terms

In the mixed graphical model, conditional independence is represented by zero parameter blocks associated with edges. This structure motivates grouping edge parameters and replacing nonconvex sparsity penalties with scalar, vector, and matrix norms.

  • Conditional Independence: An absent edge corresponds to conditional independence between its variables given all other variables.The edge-selection objective penalizes the number of edges to encourage sparse graphs.
  • Parameter Blocks: For continuous–continuous edges, β_st = 0 indicates conditional independence, and β_st is shared across both endpoint conditionals.The coefficient is a scalar appearing in the regressions where either connected continuous variable is the response.
  • Parameter Blocks: For continuous–discrete edges, the entire vector ρ_sj must be zero to represent conditional independence.The vector appears in the conditional distributions for either the continuous or discrete endpoint.
  • Parameter Blocks: For discrete–discrete edges, the entire matrix φ_rj must be zero to represent conditional independence.The matrix has dimensions L_r × L_j and appears in both endpoint conditionals.
  • Penalty Construction: The symmetric parameter matrix places each edge’s parameter block in both corresponding conditional regressions.The figure distinguishes scalar β_st, vector ρ_sj(·), and matrix φ_rj(·, ·) blocks by edge type.
  • Penalty Construction: The nonconvex sparsity objective is relaxed using the l1 norm for scalars, l2 norm for vectors, and Frobenius norm for matrices.Grouping all parameters for the same edge produces a group-lasso formulation.

5 Calibrated regularizers

The calibrated regularizer weights parameter groups to offset differences in group size and dimensionality. The proposed weighting uses covariance-based quantities and is chosen so groups are treated more equitably under an independence model.

  • Motivation: The unweighted regularizer treats parameter groups equally regardless of their sizes, motivating a calibration scheme.The weighting is intended to balance the contribution of different groups.
  • Calibration Target: The weights are selected so parameter sets receive equal treatment under the fully factorized independence model p_F.The calibration is derived using expectations under p_F and can be computed in closed form.
  • Selection Criterion: The KKT-based selection criterion depends on both a parameter group θ_g and its corresponding weight w_g.The gradient is interpreted as a generalized residual whose dimensions differ across scalar, vector, and matrix groups.
  • Calibration Target: Without calibration, larger-dimensional groups may have a greater random chance of appearing non-zero even under independence.The weighting aims to place groups of different dimensions on equal footing.
  • Weight Definition: The proposed edge weight has the form w_uv = tr(cov(z_u))tr(cov(z_v)) for all three parameter types.Here z is a generic variable and cov(z) is its variance-covariance matrix.

6 Model Selection Consistency

The section establishes model-selection consistency for maximum-likelihood and pseudolikelihood estimation under structural assumptions, while addressing non-identifiability through constraints. The theorem requires suitable regularization and sufficiently large samples.

  • Both pseudolikelihood and maximum likelihood are analyzed for selecting the correct edge set and estimating parameters close to the truth.
  • The estimation procedures are formulated as convex optimization problems using a regularizer indexed by continuous-continuous, continuous-discrete, and discrete-discrete edge groups.
  • Non-identifiability prevents direct recovery of the true parameters because likelihood values remain unchanged under shifts of discrete edge potentials.
  • Constraints restore identifiability while preserving the symmetric formulation, and the constrained and unconstrained regularized problems have the same solutions.
  • Consistency analysis assumes restricted strong convexity, Lipschitz regularity, and an irrepresentable condition relating active and inactive groups.
  • Theorem 2 applies when the regularization parameter and sample size satisfy stated conditions, with the same theorem covering both estimation methods.

7 Optimization Algorithms

The section presents proximal gradient and proximal Newton methods for the convex, nonsmooth optimization problem arising in mixed graphical-model estimation. It also discusses acceleration, implementation choices, and regularization-path fitting.

  • The optimization decomposes into a smooth convex loss and a possibly nonsmooth convex group-sparsity penalty.
  • Proximal gradient methods apply because the group penalty has a computable proximal operator with scalar and group soft-thresholding.
  • The accelerated proximal gradient method has O(c^k) convergence for strongly convex objectives and O(1/k^2) for non-strongly convex objectives.
  • The implementation uses the Auslender-Teboulle variant in TFOCS because it exhibited less oscillatory behavior in the framework authors' experiments.
  • Proximal Newton incorporates second-order information through a quadratic model and can use proximal gradient or coordinate descent to solve its subproblems.
  • Proximal Newton methods were empirically faster when n is very large or the gradient is expensive to compute.
  • A decreasing sequence of regularization parameters uses warm starts to reduce the cost of fitting an entire solution path.

8 Conditional Model

The mixed graphical model can be extended to conditional random fields that model p(z|f) rather than the joint distribution p(z,f). The specified parameterization makes node potentials depend linearly on features while keeping pairwise potentials feature-independent.

  • Conditional random fields model the conditional distribution of variables of interest given features, rather than the joint distribution of variables and features.
  • The extension builds a graphical model for p(x,y|f) while retaining x and y as the modeled variables and f as observed features.
  • The proposed parameterization is a special case in which pairwise potentials are independent of feature values.
  • Node potentials depend linearly on feature values, while the specified pairwise potentials remain functions only of the modeled variables.

9 Experimental Results

Experiments on synthetic, survey, and conditional models evaluate structure recovery, model selection, regression comparisons, and likelihood-based estimation. Pseudolikelihood recovers sparse structure effectively and generally performs competitively or better than the compared alternatives.

  • Synthetic Experiments: With n = 1000 samples, pseudolikelihood recovers the correct edge set with probability nearly 1 after a sharp phase transition.The synthetic experiment uses 10 continuous and 10 binary variables, and results are averaged over 100 trials in Figure 2.
  • Survey Experiments: As sample size increases, the optimal survey-data model becomes increasingly dense and requires less regularization.Figure 3 selects the model with the lowest test negative log pseudolikelihood; the saturated model has 55 edges.
  • Comparing against Separate Regressions: Pseudolikelihood performs similarly to separate regressions and sometimes outperforms them while learning the joint distribution rather than only conditional models.Its objective uses half as many parameters because coefficients are shared across two conditional likelihoods, and the joint model supports arbitrary conditionals and marginals.
  • Conditional Model: The conditional model outperforms the full generative model except at the smallest sample size, n = 100.The conditional model predicts log-wage, education, and job class while using the other eight survey variables as features.
  • Maximum Likelihood vs Pseudolikelihood: At n = 10,000, separate regressions and pseudolikelihood perform very similarly, consistent with approaching the asymptotic regime.At n = 100, pseudolikelihood appears to overfit less at low regularization and small training sizes.
  • Maximum Likelihood vs Pseudolikelihood: Pseudolikelihood outperforms maximum likelihood on both negative log pseudolikelihood and negative log likelihood in finite-sample, misspecified experiments.The authors note that asymptotic theory suggests maximum likelihood is more efficient under a well-specified model.

Appendix

The appendix develops computational and optimization properties of the mixed graphical model, including convex pseudolikelihood estimation and sampling-based alternatives to difficult likelihood calculations.

  • Proof of Convexity: The negative log pseudolikelihood is jointly convex in all model parameters when βss > 0.This convexity covers the continuous and discrete conditional parameters together.
  • Proof of Convexity: Convexity follows because the discrete conditional loss is multiclass logistic regression and the continuous conditional loss is convex over βss > 0.The proof establishes the continuous term through a convex composition and an epigraph argument.
  • Sampling: Sampling from the joint model can use p(x,y)=p(y)p(x|y), with MCMC, junction-tree, or exact methods handling the discrete component.The difficult step is sampling y from the discrete Markov random field.
  • Maximum Likelihood: Maximum-likelihood gradients require subtracting expected sufficient statistics from empirical statistics, making expectation computation computationally expensive.Discrete models require summation over states, while continuous models require matrix inversion.
  • Maximum Likelihood: The expectation in maximum likelihood can be approximated with samples from the model, including Gibbs sampling based on discrete-MRF MCMC methods.This approach is efficient when sampling from p(y) is efficient.
Loading 1205.5012v3…