Regularised Gaussian belief propagation
| dc.contributor.advisor | Steel, S. J. | en_ZA |
| dc.contributor.advisor | Du Preez, J. A. | en_ZA |
| dc.contributor.author | Kamper, Francois | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Economic and Management Sciences. Dept. of Statistics and Actuarial Science. | en_ZA |
| dc.date.accessioned | 2018-11-26T12:31:07Z | |
| dc.date.accessioned | 2018-12-07T06:52:05Z | |
| dc.date.available | 2018-11-26T12:31:07Z | |
| dc.date.available | 2018-12-07T06:52:05Z | |
| dc.date.issued | 2018-12 | |
| dc.description | Thesis (PhD)--Stellenbosch University, 2018. | en_ZA |
| dc.description.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. | en_ZA |
| dc.description.abstract | 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. | af_ZA |
| dc.format.extent | xiv, 133 pages ; illustrations | |
| dc.identifier.uri | http://hdl.handle.net/10019.1/104954 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University | |
| dc.rights.holder | Stellenbosch University | |
| dc.subject | Belief propagation | en_ZA |
| dc.subject | Gaussian distribution | en_ZA |
| dc.subject | Linear systems | en_ZA |
| dc.subject | Inference | en_ZA |
| dc.subject | UCTD | |
| dc.title | Regularised Gaussian belief propagation | en_ZA |
| dc.type | Thesis | en_ZA |