Treffer: Message-Passing Algorithms: Reparameterizations and Splittings

Title:
Message-Passing Algorithms: Reparameterizations and Splittings
Authors:
RUOZZI, Nicholas, TATIKONDA, Sekhar
Source:
IEEE transactions on information theory. 59(9):5860-5881
Publisher Information:
New York, NY: Institute of Electrical and Electronics Engineers, 2013.
Publication Year:
2013
Physical Description:
print, 45 ref
Original Material:
INIST-CNRS
Subject Terms:
Telecommunications, Télécommunications, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Intelligence artificielle, Artificial intelligence, Reconnaissance des formes. Traitement numérique des images. Géométrie algorithmique, Pattern recognition. Digital image processing. Computational geometry, Telecommunications et theorie de l'information, Telecommunications and information theory, Théorie de l'information, du signal et des communications, Information, signal and communications theory, Théorie de l'information, Information theory, Théorie du signal et des communications, Signal and communications theory, Codage, codes, Coding, codes, Algorithme, Algorithm, Algoritmo, Approche crédibiliste, Credal approach, Enfoque credal, Approche probabiliste, Probabilistic approach, Enfoque probabilista, Codage, Coding, Codificación, Condition suffisante, Sufficient condition, Condición suficiente, Envoi message, Message passing, Estimation a posteriori, A posteriori estimation, Estimación a posteriori, Intelligence artificielle, Artificial intelligence, Inteligencia artificial, Loi probabilité, Probability distribution, Ley probabilidad, Méthode combinatoire, Combinatorial method, Método combinatorio, Optimum global, Global optimum, Optimo global, Problème direct, Direct problem, Problema directo, Vision ordinateur, Computer vision, Visión ordenador, Belief propagation, graphical models, inference algorithms, maximum a posteriori estimation, message passing
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
Communication Theory Laboratory, Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Department of Electrical Engineering, Yale University, New Haven, CT 06520, United States
ISSN:
0018-9448
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=27677298
Rights:
Copyright 2014 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Telecommunications and information theory
Accession Number:
edscal.27677298
Database:
PASCAL Archive

Weitere Informationen

The max-product algorithm, a local message-passing scheme that attempts to compute the most probable assignment (MAP) of a given probability distribution, has been successfully employed as a method of approximate inference for applications arising in coding theory, computer vision, and machine learning. However, the max-product algorithm is not guaranteed to converge, and if it does, it is not guaranteed to recover the MAP assignment. Alternative convergent message-passing schemes have been proposed to overcome these difficulties. This paper provides a systematic study of such message-passing algorithms that extends the known results by exhibiting new sufficient conditions for convergence to local and/or global optima, providing a combinatorial characterization of these optima based on graph covers, and describing a new convergent and correct message-passing algorithm whose derivation unifies many of the known convergent message-passing algorithms. While convergent and correct message-passing algorithms represent a step forward in the analysis of max-product style message-passing algorithms, the conditions needed to guarantee convergence to a global optimum can be too restrictive in both theory and practice. This limitation of convergent and correct message-passing schemes is characterized by graph covers and illustrated by example.