MAP Inference on Million Node Graphical Models: KL-divergence based Alternating Directions Method
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
MAP Inference on Million Node Graphical Models: KL-divergence based Alternating Directions Method
Published Date
2012-02-27
Publisher
Type
Report
Abstract
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Fu, Qiang; Wang, Huahua; Banerjee, Arindam; Liess, Stefan; Snyder, Peter K.. (2012). MAP Inference on Million Node Graphical Models: KL-divergence based Alternating Directions Method. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215885.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.