التفاصيل البيبلوغرافية
| العنوان: |
Faster Algorithms for Max-Product Message-Passing. |
| المؤلفون: |
McAuley, Julian J.1 JULIAN.MCAULEY@NICTA.COM.AU, Caetano, Tibério S.1 TIBERIO.CAETANO@NICTA.COM.AU |
| المصدر: |
Journal of Machine Learning Research. Apr2011, Vol. 12 Issue 4, p1349-1388. 40p. 13 Diagrams, 3 Charts, 11 Graphs. |
| مصطلحات موضوعية: |
*GRAPHIC methods, *APPROXIMATION theory, *MATHEMATICAL models, *PROBLEM solving, MESSAGE passing (Computer science), MATRICES (Mathematics), MULTIPLICATION |
| مستخلص: |
Maximum A Posteriori inference in graphical models is often solved via message-passing algorithms, such as the junction-tree algorithm or loopy belief-propagation. The exact solution to this problem is well-known to be exponential in the size of the maximal cliques of the triangulated model, while approximate inference is typically exponential in the size of the model's factors. In this paper, we take advantage of the fact that many models have maximal cliques that are larger than their constituent factors, and also of the fact that many factors consist only of latent variables (i.e., they do not depend on an observation). This is a common case in a wide variety of applications that deal with grid-, tree-, and ring-structured models. In such cases, we are able to decrease the exponent of complexity for message-passing by 0.5 for both exact and approximate inference. We demonstrate that message-passing operations in such models are equivalent to some variant of matrix multiplication in the tropical semiring, for which we offer an O(N2.5) expected-case solution. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Machine Learning Research is the property of Microtome Publishing and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
Full Text Finder