Fraunhofer-Gesellschaft

Publica

Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Reduce and re-lift: Bootstrapped lifted likelihood maximization for MAP

 
: Hadiji, F.

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence and the Twenty-Fifth Innovative Applications of Artificial Intelligence Conference, the Fourth Symposium on Educational Advances in Artificial Intelligence : 14–18 July 2013, Bellevue, Washington, USA
Palo Alto: AAAI Press, 2013
ISBN: 978-1-57735-615-8
S.394-400
AAAI Conference on Artificial Intelligence <27, 2013, Bellevue/Wash.>
Englisch
Konferenzbeitrag
Fraunhofer IAIS ()

Abstract
By handling whole sets of indistinguishable objects together, lifted belief propagation approaches have rendered large, previously intractable, probabilistic inference problems quickly solvable. In this paper, we show that Kumar and Zilberstein's likelihood maximization (LM) approach to MAP inference is liftable, too, and actually provides additional structure for optimization. Specifically, it has been recognized that some pseudo marginals may converge quickly, turning intuitively into pseudo evidence. This additional evidence typically changes the structure of the lifted network: it may expand or reduce it. The current lifted network, however, can be viewed as an upper bound on the size of the lifted network required to finish likelihood maximization. Consequently, we re-lift the network only if the pseudo evidence yields a reduced network, which can efficiently be computed on the current lifted network. Our experimental results on Ising models, image segmentation and relational entity resolution demonstrate that this bootstrapped LM via "reduce and re-lift" finds MAP assignments comparable to those found by the original LM approach, but in a fraction of the time.

: http://publica.fraunhofer.de/dokumente/N-300697.html