Constrained likelihood for a graph
Section of Graphical models, part of Statistical learning
Constrained likelihood for a graph
| Type | Section |
| Taught in | Graphical models |
| Part | Statistical learning |
For iid observations x_1,\ldots,x_n from \operatorname{N}_p(\mu, K^{-1}) the likelihood is
L=\prod_{i=1}^{n} \frac{|K|^{1/2}}{(2\pi)^{p/2}} \exp\Bigl(-\tfrac12(x_i-\mu)^\top K(x_i-\mu)\Bigr) =\frac{|K|^{n/2}}{(2\pi)^{np/2}} \exp\Biggl(-\tfrac12\sum_{i=1}^{n}(x_i-\mu)^\top K(x_i-\mu)\Biggr),
and the log-likelihood is
\ell=\frac{n}{2}\log|K|-\frac{np}{2}\log(2\pi) -\frac12\sum_{i=1}^{n}(x_i-\mu)^\top K(x_i-\mu).
Maximise it subject to constraints on K: edges missing from the graph correspond to zeros in K. If E is the edge set then k_{jk}=0 for j\neq k with (j,k)\notin E. The domain is K\succ 0. Diagonal entries are not constrained to zero. The second term is not a function of the parameters, and the likelihood is maximised for \mu at \hat\mu=\bar x regardless of K. Divide by n/2 without affecting the maximisation, so that one maximises \log|K|-\frac1n\sum_i(x_i-\bar x)^\top K(x_i-\bar x).
To simplify the later notation, let
S=\frac1n\sum_{i=1}^{n}(x_i-\bar x)(x_i-\bar x)^\top,
the covariance with divisor n. The unbiased matrix uses divisor n-1. In this section the symbol S means the 1/n version. Since a scalar equals its trace, and by the cyclic property of the trace,
\frac1n\sum_i(x_i-\bar x)^\top K(x_i-\bar x) =\operatorname{tr}\Biggl(\frac1n\sum_i(x_i-\bar x)(x_i-\bar x)^\top K\Biggr) =\operatorname{tr}(SK).
The problem is to maximise
g(K)=\log|K|-\operatorname{tr}(SK)
subject to the fixed zeros of K. With Lagrange multipliers \gamma_{jk} for the constraints,
g_C(K,\Gamma)=\log|K|-\operatorname{tr}(SK)-\sum_{j\neq k,\,(j,k)\notin E}\gamma_{jk} k_{jk}.
Here \Gamma is symmetric, zero on the diagonal and on allowed edges, and potentially nonzero on missing edges. A full-matrix trace inner product is used, so each off-diagonal pair appears twice. The symmetric multiplier convention absorbs that factor consistently. The derivatives with respect to symmetric K are K^{-1}=\Sigma for the log determinant and S for the trace term, giving \nabla g_C=\Sigma-S-\Gamma.
Using W for the estimate of \Sigma and \Theta for the estimate of K, so W\Theta=I, the estimating equations are
W-S-\Gamma=0.
Reading this entrywise: for every edge (j,k)\in E and for the diagonal, \gamma_{jk}=0 and so w_{jk}=s_{jk}. The maximum-likelihood estimate of the covariance reproduces the sample covariances on the edges and the diagonal exactly. For non-edges, w_{jk} is whatever value makes (W^{-1})_{jk}=0.
Used in
See also
Undirected graph · Hammersley–Clifford · A zero precision entry is conditional independence · Maximum likelihood for a known graph · Graphical lasso · Markov graphs · Graph terminology · Conditional independence