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$.


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.

  • $\begingroup$ Thanks a lot for answering the question! I'm sorry that I was not clear enough. $\theta$ is the same for all the pairwise potential functions, so I don't want to solve the inverse covariance estimation problem. I think there is a simple way. What's more, the unary potential $\psi_u$ may not be Gaussian. $\endgroup$ – Hugo Sep 26 '13 at 12:54
  • 1
    $\begingroup$ The Element of Statistical learning by Hastie et al. is freely available (by the authors): stanford.edu/~hastie/local.ftp/Springer/OLD/ESLII_print4.pdf $\endgroup$ – bdeonovic Feb 24 '14 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.