NDLI: Robust max-product belief propagation

Content Provider	IEEE Xplore Digital Library
Author	Ibrahimi, M. Javanmard, A. Kanoria, Y. Montanari, A.
Copyright Year	2011
Description	Author affiliation: Department of Electrical Engineering, Stanford University, USA (Ibrahimi, M.; Javanmard, A.; Kanoria, Y.; Montanari, A.)
Abstract	We study the problem of optimizing a graph-structured objective function under 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.
Starting Page	43
Ending Page	49
File Size	185042
Page Count	7
File Format	PDF
ISBN	9781467303217
ISSN	10586393
e-ISBN	9781467303231
DOI	10.1109/ACSSC.2011.6189951
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-11-06
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Robustness Optimization Graphical models Vectors Game theory Games Convergence
Content Type	Text
Resource Type	Article
Subject	Signal Processing Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Sparsity-based face recognition using discriminative graphical models

Maximum weight matching via max-product belief propagation

Convergence Analysis of the Variance in Gaussian Belief Propagation

A robust AMSE-minimization game in multicell multiuser wireless system

Convergence of Gaussian belief propagation over a ring-type graphical model

Computationally efficient sparse bayesian learning via belief propagation

Stochastic belief propagation: Low-complexity message-passing with guarantees

Modeling noisy feedback in decentralized self-configuring networks

Inference in wireless sensor networks based on information structure optimization

Robust max-product belief propagation

Similar Documents

Sparsity-based face recognition using discriminative graphical models

Maximum weight matching via max-product belief propagation

Convergence Analysis of the Variance in Gaussian Belief Propagation

A robust AMSE-minimization game in multicell multiuser wireless system

Convergence of Gaussian belief propagation over a ring-type graphical model

Computationally efficient sparse bayesian learning via belief propagation

Stochastic belief propagation: Low-complexity message-passing with guarantees

Modeling noisy feedback in decentralized self-configuring networks

Inference in wireless sensor networks based on information structure optimization

Robust max-product belief propagation