Browsing by Author "Fu, Qiang"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Efficient inference algorithms for some probabilistic graphical models
    (2014-02) Fu, Qiang
    The probabilistic graphical model framework provides an essential tool to reason coherently from limited and noisy observations. The framework has been used in an enormous range of application domains, which include: natural language processing, computer vision, bioinformatic, robot navigation and many more. We propose several inference algorithms for some probabilistic graphical models. For Bayesian network graphical models, we focus on the problem of overlapping clustering, where a data point is allowed to belong to multiple clusters. We present an overlapping clustering algo- rithm based on multiplicative mixture models. We analyze a general setting where each component of the multiplicative mixture is from an exponential family, and present an efficient alternating maximization algorithm to learn the model and infer overlap- ping clusters. We also propose a Bayesian Overlapping Subspace Clustering (BOSC) model which is a hierarchical generative model for matrices with potentially overlapping uniform sub-block structures. The BOSC model can also handle matrices with missing entries. We propose an EM-style algorithm based on approximate inference using Gibbs sampling and parameter estimation using coordinate descent for the BOSC model. We propose an EM-style algorithm based on approximate inference using Gibbs sampling and parameter estimation using coordinate descent for the BOSC model. We also consider Markov random field graphical models and address the problem of maximum a posteriori (MAP) inference. We first show that the drought detection problem from the climate science domain can be formulated as a MAP inference problem and propose an automatic drought detection problem. We then present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based proximal function, which makes each subproblem in ADMM easy to solve in parallel using the sum-product algorithm. We rigorously prove global convergence of Bethe-ADMM. The proposed algorithm is extensively evaluated on both synthetic and real datasets to illustrate its effectiveness. Further, the parallel Bethe-ADMM is shown to scale almost linearly with increasing number of cores.
  • Thumbnail Image
    Item
    MAP Inference on Million Node Graphical Models: KL-divergence based Alternating Directions Method
    (2012-02-27) Fu, Qiang; Wang, Huahua; Banerjee, Arindam; Liess, Stefan; Snyder, Peter K.
    Motivated by a problem in large scale climate data analysis, we consider the problem of maximum a posteriori (MAP) inference in graphical models with millions of nodes. While progress has been made in recent years, existing MAP inference algorithms are inherently sequential and hence do not scale well. In this paper, we present a parallel MAP inference algorithm called KL-ADM based on two ideas: tree-decomposition of a graph, and the alternating directions method (ADM). However, unlike standard ADM, we use an inexact ADM augmented with a Kullback-Leibler (KL) divergence based regularization. The unusual modification leads to an efficient iterative algorithm while avoiding double-loops. We rigorously prove global convergence of KL-ADM. We illustrate the effectiveness of KL-ADM through extensive experiments on large synthetic and real datasets. The application on real world precipitation data finds all major droughts in the last century.