Skip navigation
Skip navigation

Faster algorithms for max-product message-passing

McAuley, Julian; Caetano, Tiberio

Description

Maximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm or loopy belief-propagation. The exact solution to this problem is well-known to be exponential in the size of the maximal cliques of the triangulated model, while approximate inference is typically exponential in the size of the model's factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their...[Show more]

dc.contributor.authorMcAuley, Julian
dc.contributor.authorCaetano, Tiberio
dc.date.accessioned2015-12-10T23:33:12Z
dc.identifier.issn1532-4435
dc.identifier.urihttp://hdl.handle.net/1885/69177
dc.description.abstractMaximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm or loopy belief-propagation. The exact solution to this problem is well-known to be exponential in the size of the maximal cliques of the triangulated model, while approximate inference is typically exponential in the size of the model's factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their constituent factors, and also of the fact that many factors consist only of latent variables (i.e., they do not depend on an observation). This is a common case in a wide variety of applications that deal with grid-, tree-, and ring-structured models. In such cases, we are able to decrease the exponent of complexity for message-passing by 0.5 for both exact and approximate inference. We demonstrate that message-passing operations in such models are equivalent to some variant of matrix multiplication in the tropical semiring, for which we offer an 0(N2.5) expected-case solution.
dc.publisherMIT Press
dc.rightsAuthor/s retain copyright
dc.sourceJournal of Machine Learning Research
dc.source.urihttp://www.jmlr.org/papers/v12/
dc.subjectKeywords: Approximate inference; Belief-propagation; Exact solution; GraphicaL model; Latent variable; MAtrix multiplication; Max-product; Maximal clique; Maximum a posteriori; Message passing algorithm; Semi-ring; Tropical matrix multiplication; Algorithms; Graphi Belief-propagation; Graphical models; Tropical matrix multiplication
dc.titleFaster algorithms for max-product message-passing
dc.typeJournal article
local.description.notesImported from ARIES
local.identifier.citationvolume12
dc.date.issued2011
local.identifier.absfor080109 - Pattern Recognition and Data Mining
local.identifier.ariespublicationf2965xPUB1944
local.type.statusPublished Version
local.contributor.affiliationMcAuley, Julian, College of Engineering and Computer Science, ANU
local.contributor.affiliationCaetano, Tiberio, College of Engineering and Computer Science, ANU
local.bibliographicCitation.startpage1349
local.bibliographicCitation.lastpage1388
local.identifier.absseo890299 - Computer Software and Services not elsewhere classified
dc.date.updated2016-02-24T08:20:13Z
local.identifier.scopusID2-s2.0-79955823916
local.identifier.thomsonID000290096100006
dcterms.accessRightsOpen Access
CollectionsANU Research Publications

Download

File Description SizeFormat Image
01_McAuley_Faster_algorithms_for_2011.pdf1.09 MBAdobe PDF


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator