Local approximate inference algorithms
| dc.creator | Jung, Kyomin | |
| dc.creator | Shah, Devavrat | |
| dc.date | 2006-10-18 | |
| dc.date | 2007-10-03 | |
| dc.date.accessioned | 2026-07-07T08:33:37Z | |
| dc.date.available | 2026-07-07T08:33:37Z | |
| dc.description | We present a new local approximation algorithm for computing Maximum a Posteriori (MAP) and log-partition function for arbitrary exponential family distribution represented by a finite-valued pair-wise Markov random field (MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\em appropriately} chosen small components; then computing estimates locally in each of these components and then producing a {\em good} global solution. We show that if the underlying graph $G$ either excludes some finite-sized graph as its minor (e.g. Planar graph) or has low doubling dimension (e.g. any graph with {\em geometry}), then our algorithm will produce solution for both questions within {\em arbitrary accuracy}. We present a message-passing implementation of our algorithm for MAP computation using self-avoiding walk of graph. In order to evaluate the computational cost of this implementation, we derive novel tight bounds on the size of self-avoiding walk tree for arbitrary graph. As a consequence of our algorithmic result, we show that the normalized log-partition function (also known as free-energy) for a class of {\em regular} MRFs will converge to a limit, that is computable to an arbitrary accuracy. | |
| dc.description | 21 pages, 10 figures | |
| dc.identifier | https://arxiv.org/abs/cs/0610111 | |
| dc.identifier | http://arxiv.org/abs/cs/0610111 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/139194 | |
| dc.subject | Artificial Intelligence | |
| dc.title | Local approximate inference algorithms | |
| dc.type | text |