An improved message-passing scheme for approximate inference using cluster graphs

Simple item page
dc.contributor.advisorVan Daalen, Corne E.en_ZA
dc.contributor.advisorDu Preez, Johanen_ZA
dc.contributor.authorVan Tonder, Ruanen_ZA
dc.contributor.otherStellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering.en_ZA
dc.date.accessioned2022-03-07T07:33:07Z
dc.date.accessioned2022-04-29T09:24:35Z
dc.date.available2022-03-07T07:33:07Z
dc.date.available2022-04-29T09:24:35Z
dc.date.issued2022-04
dc.descriptionThesis (MEng)--Stellenbosch University, 2022.en_ZA
dc.description.abstractENGLISH 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.en_ZA
dc.description.abstractAFRIKAANSE 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.af_ZA
dc.description.versionMastersen_ZA
dc.format.extent91 pagesen_ZA
dc.identifier.urihttp://hdl.handle.net/10019.1/124652
dc.language.isoen_ZAen_ZA
dc.publisherStellenbosch : Stellenbosch Universityen_ZA
dc.rights.holderStellenbosch Universityen_ZA
dc.subjectImproved message-passing schemeen_ZA
dc.subjectUCTDen_ZA
dc.subjectProbabilistic inferenceen_ZA
dc.subjectCluster graphsen_ZA
dc.subjectKalman filteringen_ZA
dc.titleAn improved message-passing scheme for approximate inference using cluster graphsen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
vantonder_improved_2022.pdf
Size:
1.62 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters Degrees (Electrical and Electronic Engineering)