Optimization by max-propagation using {Kikuchi approximations}

Download: PDF.

“Optimization by max-propagation using {Kikuchi approximations}” by R. Höns, Roberto Santana, P. Larrañaga, and J. A. Lozano, Department of Computer Science and Artificial Intelligence. University of the Basque Country technical report EHU-KZAA-IK-2/07, Nov. 2007.


In this paper we address the problem of using region-based approximations to find the optimal points of a given function. Our approach combines the use of Kikuchi approximations with the application of generalized belief propagation (GBP) using maximization instead of marginalization. The relationship between the fixed points of maximum GBP and the free energy is elucidated. A straightforward connection between the function to be optimized and the Kikuchi approximation (which holds only for maximum GBP, not for marginal GBP) is proven. Later, we show that maximum GBP can be combined with a dynamic programming algorithm to find the most probable configurations of a f graphical model. We then analyze the dynamics of the procedure proposed and show how its different steps can be manipulated to influence the search for optimal solutions.

Download: PDF.

BibTeX entry:

   author = {R. H{\"o}ns and Roberto Santana and P. Larra{\~n}aga and J.
	A. Lozano},
   title = {{Optimization by max-propagation using {K}ikuchi approximations}},
   institution = {Department of Computer Science and Artificial
	Intelligence, University of the Basque Country},
   number = {EHU-KZAA-IK-2/07},
   month = nov,
   year = {2007}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.