Bayesian Estimation of Latently-grouped Parameters in Undirected Graphical Models
In large-scale applications of undirected graphical models, such as social networks and biological networks, similar patterns occur frequently and give rise to similar parameters. In this situation, it is beneficial to group the parameters for more efficient learning. We show that even when the grouping is unknown, we can infer these parameter groups during learning via a Bayesian approach. We impose a Dirichlet process prior on the parameters. Posterior inference usually involves calculating intractable terms, and we propose two approximation algorithms, namely a Metropolis-Hastings algorithm with auxiliary variables and a Gibbs sampling algorithm with "stripped" Beta approximation (Gibbs SBA). Simulations show that both algorithms outperform conventional maximum likelihood estimation (MLE). Gibbs SBA's performance is close to Gibbs sampling with exact likelihood calculation. Models learned with Gibbs SBA also generalize better than the models learned by MLE on real-world Senate voting data.
This paper proposes a Bayesian approach to learning 
      binary pairwise MRFs with latently tied parameters. A DP prior is used to 
      model the grouping of parameters, and two approximate inference methods 
      are compared with MLE. Doing Bayesian inference on MRFs is 
      difficult, known as doubly intractable. The first algorithm, M-H with 
      auxiliary variables, is based on the paper of Moller et.al. 2006. It is 
      technically sound (except for the sample generated by Gibbs sampling), but 
      could be slow, hard to mix, and therefore not feasible for real 
      medium-sized applications. The second algorithm, Gibbs_SBA, is novel to my 
      knowledge and seems to be a good candidate for approximate inference. The 
      experiments show that the approximate methods are much faster than the 
      exact method and obtain similar performance on small problems. It would be 
      a meaningful contribution to Bayesian approach to MRFs. My concern 
      is on the usage of the Stripped Beta Approximation. The derivation of the 
      method is lack of clarity. It is based on two approximations: (1) line 
      215: the distribution of all variables other than u and v is independent 
      on the value of \theta_i; (2) line 228: approximate the contribution of 
      \theta_i in (5) with a Beta distribution. I don’t understand how the 
      second approximation is adopted. Apparently Equation 5 is a Beta function 
      of \lambda, which is a complicated function of \theta. The authors don’t 
      provide sufficient explanation for the beta approximation or the usage of 
      the MLE of \theta in the Beta parameters. While the experiments show the 
      overall performance of Gibbs_SBA is similar to the exact method in terms 
      of the two first metrics, a figure or a paragraph of discussion on the 
      accuracy of the approximation on one single step of sampling would be very 
      useful. In the experiment of the real problem, the output of the 
      parameters does not show any hard grouping because the Bayesian approach 
      assumes a posterior distribution. So is the latent grouping prior useful 
      only as regularization to prevent over-fitting, or you can make more 
      meanings out of it? The improvement on the pseudo-likelihood is not very 
      significant. I guess that is because the sampling procedure is initialized 
      on the result of PCD. My last concern is about the speed. The 
      computation burden is known as a serious problem for Bayesian inference. 
      The authors compared the speed of the two approximate methods with the 
      exact method. But how are they compared with the MLE algorithm based on 
      PCD? It seems that for the fastest method for Bayesian inference, 
      Gibbs_SBA, one has to run MLE (PCD) for every parameter on every 
      iteration. Would it be applicable for any large problem in the real world? 
      Some minor questions and typos: 1. The binary pairwise MRF in 
      the paper has pairwise potentials only. Would Gibbs_SBA still applies for 
      an MRF with unary bias? 2. For M-H algorithm in section 3.1.1, do you 
      also need to integrate over \theta when a new group is created? 3. 
      Line 126: Section 3.2.2 -> 3.1.2