Parameter learning of Markov random field

Question

Given a Markov random field $\mathcal{G} = (\mathcal{V},\mathcal{E})$, the corresponding density function to which is expressed by

$f(x) \propto \prod_{x\in\mathcal{V}} \psi_u(x) \prod_{(x_i,x_j)\in\mathcal{E}} \psi_p(x_i,x_j; \theta)$

where $\psi_u$ is the unary potential and $\psi_p$ is the pairwise potential.

Now assume $\psi_u$ is known, the structure of the MRF and the functional form of $\psi_p$ (which is Gaussian) are also given, is there any efficient method to estimate the common hyper-parameter $\theta$ for all the pairwise potentials?

MCMC is a good option, however, it's too costly in my case. I prefer some methods of computing the point-estimate of $\theta$.

Answer 1

Firstly, I don't know why you use the term hyperparameter as this is heavily used in Bayesian statistics.

Nonetheless, If $\Theta$ represents the parameters of a Gaussian MRF model (Covariance), then since you know its structure you can simply use the ML method as described in section 17.3.1 of book "The Elements of Statistical Learning: Data Mining, Inference, and Prediction" by Hastie et al. The problem is posed as a convex optimization one, in notation $$logdet\Theta-trace(S\Theta)$$ $$ s.t. \quad \Theta \ge 0 \quad (property \ of \ covariance \ matrix)$$

The trick is to partition the sample covariance matrix $S$ into a $p-1 \times p-1$ matrix and a row, also leverage the known zeros in the Inverse Covariance $\Theta^{-1}$ since conditional independence implies zero entries in $\Theta^{-1}$.

The algorithm is described in section 17.1 p634. Computational cost is negligible, $\hat{\Theta}$ is calculated in $p$ rounds as it does not involve matrix inversions.

If you find this information relevant to your problem and you do not have access to the referred book, let me know i can provide you the algorithm.

Alternatively another method, known as Iterative Proportional Scaling, is described in the book of Lauritzen. I can't tell you much about this approach I find it personally way too difficult to digest it, not to mention implementing it.

Hope that helps.