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

Van Tonder, Ruan (2022-04)

Thesis (MEng)--Stellenbosch University, 2022.

Thesis

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.

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/124652
This item appears in the following collections: