Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
An improved message-passing scheme for approximate inference using cluster graphs
Thesis (MEng)--Stellenbosch University, 2022.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2022
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614096684220416 |
|---|---|
| access_status_str | Open Access |
| author | Van Tonder, Ruan |
| author2 | Van Daalen, Corne E. |
| author_browse | Van Daalen, Corne E. Van Tonder, Ruan |
| author_facet | Van Daalen, Corne E. Van Tonder, Ruan |
| author_sort | Van Tonder, Ruan |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MEng)--Stellenbosch University, 2022. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/124652 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:36.532Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/124652 An improved message-passing scheme for approximate inference using cluster graphs Van Tonder, Ruan Van Daalen, Corne E. Du Preez, Johan Stellenbosch University. Faculty of Engineering. Dept. of Electrical and Electronic Engineering. Improved message-passing scheme UCTD Probabilistic inference Cluster graphs Kalman filtering Thesis (MEng)--Stellenbosch University, 2022. 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. Masters 2022-03-07T07:33:07Z 2022-04-29T09:24:35Z 2022-03-07T07:33:07Z 2022-04-29T09:24:35Z 2022-04 Thesis http://hdl.handle.net/10019.1/124652 en_ZA Stellenbosch University 91 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Improved message-passing scheme UCTD Probabilistic inference Cluster graphs Kalman filtering Van Tonder, Ruan An improved message-passing scheme for approximate inference using cluster graphs |
| title | An improved message-passing scheme for approximate inference using cluster graphs |
| title_full | An improved message-passing scheme for approximate inference using cluster graphs |
| title_fullStr | An improved message-passing scheme for approximate inference using cluster graphs |
| title_full_unstemmed | An improved message-passing scheme for approximate inference using cluster graphs |
| title_short | An improved message-passing scheme for approximate inference using cluster graphs |
| title_sort | improved message passing scheme for approximate inference using cluster graphs |
| topic | Improved message-passing scheme UCTD Probabilistic inference Cluster graphs Kalman filtering |
| url | http://hdl.handle.net/10019.1/124652 |
| work_keys_str_mv | AT vantonderruan animprovedmessagepassingschemeforapproximateinferenceusingclustergraphs AT vantonderruan improvedmessagepassingschemeforapproximateinferenceusingclustergraphs |