Monitoring talk: Approximate Restricted Symbolic Variable Elimination (ARSVE)
Hadi Afshar
ARTIFICIAL INTELLIGENCE SEMINARDATE: 2013-12-04
TIME: 11:30:00 - 12:00:00
LOCATION: RSISE Seminar Room, ground floor, building 115, cnr. North and Daley Roads, ANU
CONTACT: JavaScript must be enabled to display this email address.
ABSTRACT:
Recent progress in utilizing extended algebraic decision diagrams (XADD) for the purpose of probabilistic reasoning, has led to a method called symbolic variable elimination (SVE). This method provides the possibility to perform exact, closed-form inference whenever joint distributions are (or can be approximated as) multivariate piecewise polynomial functions. Nonetheless, it is known that after a few iterations, XADD-based exact solutions may grow intractably large. We address this issue by proposing an approximate restricted symbolic variable elimination (ARSVE) algorithm. It is restricted since it requires that in the sum-product algorithm, parents of each factor be processed prior to it, guaranteeing that the intermediate factors always correspond joint probability distributions. Three different XADD approximation / compression methods are proposed and their performance in terms of precision, compression rate and use of resources is tested on three case-study graphical models. Our results show that in terms of the trade of between algorithmic complexity and compression ratio, divisive merge of sibling XADD nodes based on approximation of their corresponding functions via linear regression leads to the best results. The results are quite good, suggesting that XADD structures produced via dynamic programming tasks can efficiently be compressed and consequently utilized on a much greater range of problems. As an instance, an XADD approximation with MSE=1.22E-6 has reached the compression ratio around 1:64. The algorithms running time has been just 418ms.
BIO:
