Regularised Gaussian belief propagation
Date
2018-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH SUMMARY : Belief propagation (BP) has been applied as an approximation tool in a variety
of inference problems. BP does not necessarily converge in loopy graphs
and, even if it does, is not guaranteed to provide exact inference. Even so,
BP is useful in many applications due to its computational tractability. On
a high level this dissertation is concerned with addressing the issues of BP
when applied to loopy graphs. To address these issues we formulate the principle
of node regularisation on Markov graphs (MGs) within the context of
BP. The main contribution of this dissertation is to provide mathematical and
empirical evidence that the principle of node regularisation can achieve convergence
and good inference quality when applied to a MG constructed from a
Gaussian distribution in canonical parameterisation. There is a rich literature
surrounding BP on Gaussian MGs (labelled Gaussian belief propagation or
GaBP), and this is known to suffer from the same problems as general BP on
graphs. GaBP is known to provide the correct marginal means if it converges
(this is not guaranteed), but it does not provide the exact marginal precisions.
We show that our regularised BP will, with sufficient tuning, always converge
while maintaining the exact marginal means. This is true for a graph where
nodes are allowed to have any number of variables. The selection of the degree
of regularisation is addressed through the use of heuristics. Our variant of
GaBP is tested empirically in a variety of settings. We show that our method
outperforms other variants of GaBP available in the literature, both in terms
of convergence speed and quality of inference. These improvements suggest
that the principle of node regularisation in BP should be investigated in other
inference problems. A by-product of GaBP is that it can be used to solve linear
systems of equations; the same is true for our variant and in this context
we make an empirical comparison with the conjugate gradient (CG) method.
AFRIKAANSE OPSOMMING : Geloofspropagasie word in ’n verskeidenheid van inferensie-probleme as ’n benaderings-gereedskap toegepas. Geloofspropagasie konvergeer nie noodwendig in grafieke met sirkelroetes nie, en selfs al doen dit, is dit nie gewaarborg om korrekte inferensie te verskaf nie. Ten spyte hiervan is geloofspropagasie nuttig in baie toepassings as gevolg van die goeie berekenings-aspekte daarvan. Op ’n hoë vlak is hierdie tesis gefokus op die verbetering van geloofspropagasie wanneer dit op grafieke met sirkelroetes toegepas word. Om hierdie verbeteringe te bereik, word die beginsel van nodusregulering in die konteks van Markov-grafieke (MG’e) geformuleer. Die hoof bydrae van hierdie tesis is om wiskundige en empiriese bewyse te verskaf dat die beginsel van nodusregulering konvergensie kan bewerkstellig en goeie inferensie-kwaliteit kan verskaf wanneer die MG saamgestel is uit ’n Gaussiese verdeling in kanoniese vorm. Daar is ’n ryk literatuur rondom hierdie tipe geloofspropagasie (Gaussiese geloofspropagasie of GaBP) en dit is bekend dat GaBP dieselfde probleme as algemene geloofspropagasie ervaar. GaBP verskaf die korrekte marginale gemiddeldes by konvergensie (konvergensie is nie gewaarborg nie), maar verskaf nie noodwendig die korrekte marginale presisies nie. Ons wys dat ons aangepaste geloofspropagasie altyd konvergeer, gegewe voldoende regulering, terwyl dit steeds die korrekte marginale gemiddeldes verskaf. Hierdie is waar vir enige grafiek, ongeag die aantal veranderlikes per nodus. Die keuse van die graad van regulering word deur heuristieke metodes aangespreek. Ons GaBP metode word in ’n verskeidenheid van situasies empiries getoets. In hierdie situasies vaar ons metode beter as ander metodes in die literatuur, beide in terme van konvergensie-spoed en die kwaliteit van die inferensie. Hierdie verbeteringe stel voor dat die beginsel van nodusregulering in geloofspropagasie in ander inferensie-probleme ondersoek moet word. ’n Byproduk van GaBP is dat dit gebruik kan word om stelsels van lineêre vergelykings op te los; dieselfde is waar in die geval van ons metode en ons maak binne hierdie konteks ’n empiriese vergelyking met die toegevoegde gradiënt (CG)-metode.
AFRIKAANSE OPSOMMING : Geloofspropagasie word in ’n verskeidenheid van inferensie-probleme as ’n benaderings-gereedskap toegepas. Geloofspropagasie konvergeer nie noodwendig in grafieke met sirkelroetes nie, en selfs al doen dit, is dit nie gewaarborg om korrekte inferensie te verskaf nie. Ten spyte hiervan is geloofspropagasie nuttig in baie toepassings as gevolg van die goeie berekenings-aspekte daarvan. Op ’n hoë vlak is hierdie tesis gefokus op die verbetering van geloofspropagasie wanneer dit op grafieke met sirkelroetes toegepas word. Om hierdie verbeteringe te bereik, word die beginsel van nodusregulering in die konteks van Markov-grafieke (MG’e) geformuleer. Die hoof bydrae van hierdie tesis is om wiskundige en empiriese bewyse te verskaf dat die beginsel van nodusregulering konvergensie kan bewerkstellig en goeie inferensie-kwaliteit kan verskaf wanneer die MG saamgestel is uit ’n Gaussiese verdeling in kanoniese vorm. Daar is ’n ryk literatuur rondom hierdie tipe geloofspropagasie (Gaussiese geloofspropagasie of GaBP) en dit is bekend dat GaBP dieselfde probleme as algemene geloofspropagasie ervaar. GaBP verskaf die korrekte marginale gemiddeldes by konvergensie (konvergensie is nie gewaarborg nie), maar verskaf nie noodwendig die korrekte marginale presisies nie. Ons wys dat ons aangepaste geloofspropagasie altyd konvergeer, gegewe voldoende regulering, terwyl dit steeds die korrekte marginale gemiddeldes verskaf. Hierdie is waar vir enige grafiek, ongeag die aantal veranderlikes per nodus. Die keuse van die graad van regulering word deur heuristieke metodes aangespreek. Ons GaBP metode word in ’n verskeidenheid van situasies empiries getoets. In hierdie situasies vaar ons metode beter as ander metodes in die literatuur, beide in terme van konvergensie-spoed en die kwaliteit van die inferensie. Hierdie verbeteringe stel voor dat die beginsel van nodusregulering in geloofspropagasie in ander inferensie-probleme ondersoek moet word. ’n Byproduk van GaBP is dat dit gebruik kan word om stelsels van lineêre vergelykings op te los; dieselfde is waar in die geval van ons metode en ons maak binne hierdie konteks ’n empiriese vergelyking met die toegevoegde gradiënt (CG)-metode.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Belief propagation, Gaussian distribution, Linear systems, Inference, UCTD