An improved message-passing scheme for approximate inference using cluster graphs
Date
2022-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: This thesis presents a novel message-passing scheme for probabilistic inference using general
cluster graphs. By relaxing the running intersection property as a constraint on the structure of
cluster graphs, it is possible to create a message-passing scheme that generally produces better
approximations than that of standard message passing. With this method, which will be referred to
as conditional message passing, cluster graphs can be created that produce approximations similar
to those produced by the region graph method. This includes the cluster variation method, which
is known to produce better approximate marginal distributions than standard message passing on
cluster graphs. An algorithm will be presented that allows for automatically constructing cluster
graphs and performing conditional message passing for inference. Conditional message passing
is compared to standard message passing (cluster graphs) as well as the parent-to-child method
(region graphs) by measuring the Kullback-Leibler divergence between the approximate marginal
distributions produced by these methods and the true marginal distributions. The methods are
tested on a wide variety of joint distributions including the Ising model, which is notoriously
difficult for message-passing algorithms to solve. Conditional message passing produced approxi mate marginals distributions which where closer to the true marginal distributions for 78.75% and
99% of discrete and continuous tests performed respectively. The tests also show that conditional
message passing produces approximations on par with parent-to-child message passing while
having an execution time that is up to 4 times faster. The improvement in execution time is due
to the messages used in conditional message passing, specifically the messages based on the
belief update variant, being less computationally expensive to compute. Conditional message
passing is derived from the point of view of loop-correction while the region graph method is
derived from maximizing an approximate energy functional. Therefore, conditional message
passing provides a new interpretation for the cluster variation method as one of loop-correction
that opens the door for future investigation into general loop-correction algorithms for cluster
graphs.
AFRIKAANSE OPSOMMING: Hierdie tesis dra voor ’n oorspronklike inferensie algoritme vir toepassing op algemene trosgra fieke (cluster graphs). Hierdie nuwe metode vorm deel van bootskap-oordag (message-passing) algoritmes en spreek die huidige beperkings van trosgrafieke aan deur om die ‘running intersection property’ the verslap. Ons wys dat hierdie metode, genoemd voorwaardelike boodskap-oordrag (conditional message passing), bewerkstellig benaderde marginale verspreidings wat nader is aan die egte verspreidings in vergelyking met standaard inferensie op trosgrafieke. Ons verskaf ’n algoritme waarmee trosgrafieke vir die gebruik van voorwaardelike boodskap-oordrag outoma ties bepaal kan word. Die inferensie algoritmes is toegepas op ’n verskeidenheid van digtheids funksies. Dit sluit die Ising model in, wat dikwels as ’n maatstaf vir inferenie algoritmes gebruik word. Alhoewel die resultate van die nuwe metode soortgelyk is aan die van die ‘region graph method’, wat die ‘cluster variation method’ insluit, het dit ’n korter uitvoer tyd. Die nuwe metode is hoofsaaklik ’n vorm van lus korreksie, terwyl bestaande metodes vanuit ’n optimeerings perspektief afgelei is. Voorwaardelike boodskap-oordrag verkaf daarom ’n nuwe lens waardeur toekomstige verbeteringe in bootskap-oordag algoritmes vorendag gebring kan word.
AFRIKAANSE OPSOMMING: Hierdie tesis dra voor ’n oorspronklike inferensie algoritme vir toepassing op algemene trosgra fieke (cluster graphs). Hierdie nuwe metode vorm deel van bootskap-oordag (message-passing) algoritmes en spreek die huidige beperkings van trosgrafieke aan deur om die ‘running intersection property’ the verslap. Ons wys dat hierdie metode, genoemd voorwaardelike boodskap-oordrag (conditional message passing), bewerkstellig benaderde marginale verspreidings wat nader is aan die egte verspreidings in vergelyking met standaard inferensie op trosgrafieke. Ons verskaf ’n algoritme waarmee trosgrafieke vir die gebruik van voorwaardelike boodskap-oordrag outoma ties bepaal kan word. Die inferensie algoritmes is toegepas op ’n verskeidenheid van digtheids funksies. Dit sluit die Ising model in, wat dikwels as ’n maatstaf vir inferenie algoritmes gebruik word. Alhoewel die resultate van die nuwe metode soortgelyk is aan die van die ‘region graph method’, wat die ‘cluster variation method’ insluit, het dit ’n korter uitvoer tyd. Die nuwe metode is hoofsaaklik ’n vorm van lus korreksie, terwyl bestaande metodes vanuit ’n optimeerings perspektief afgelei is. Voorwaardelike boodskap-oordrag verkaf daarom ’n nuwe lens waardeur toekomstige verbeteringe in bootskap-oordag algoritmes vorendag gebring kan word.
Description
Thesis (MEng)--Stellenbosch University, 2022.
Keywords
Improved message-passing scheme, UCTD, Probabilistic inference, Cluster graphs, Kalman filtering