Robust Max-Product Belief Propagation

Details Robust Max-Product Belief Propagation Robust Max-Product Belief Propagation

2011-11-27

arxiv.org/abs/1111.6214v1

Computer Science

Computational Engineering, Finance, and Science

7 pages, 4 figures

Scientific paper

We study the problem of optimizing a graph-structured objective function under \emph{adversarial} uncertainty. This problem can be modeled as a two-persons zero-sum game between an Engineer and Nature. The Engineer controls a subset of the variables (nodes in the graph), and tries to assign their values to maximize an objective function. Nature controls the complementary subset of variables and tries to minimize the same objective. This setting encompasses estimation and optimization problems under model uncertainty, and strategic problems with a graph structure. Von Neumann's minimax theorem guarantees the existence of a (minimax) pair of randomized strategies that provide optimal robustness for each player against its adversary. We prove several structural properties of this strategy pair in the case of graph-structured payoff function. In particular, the randomized minimax strategies (distributions over variable assignments) can be chosen in such a way to satisfy the Markov property with respect to the graph. This significantly reduces the problem dimensionality. Finally we introduce a message passing algorithm to solve this minimax problem. The algorithm generalizes max-product belief propagation to this new domain.

Affiliated with

Also associated with

No associations

Rating

Robust Max-Product Belief Propagation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Robust Max-Product Belief Propagation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Max-Product Belief Propagation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-686724