2807:, or loops. The initialization and scheduling of message updates must be adjusted slightly (compared with the previously described schedule for acyclic graphs) because graphs might not contain any leaves. Instead, one initializes all variable messages to 1 and uses the same message definitions above, updating all messages at every iteration (although messages coming from known leaves or tree-structured subgraphs may no longer need updating after sufficient iterations). It is easy to show that in a tree, the message definitions of this modified procedure will converge to the set of message definitions given above within a number of iterations equal to the
27:
3917:). Later, Su and Wu established the necessary and sufficient convergence conditions for synchronous GaBP and damped GaBP, as well as another sufficient convergence condition for asynchronous GaBP. For each case, the convergence condition involves verifying 1) a set (determined by A) being non-empty, 2) the spectral radius of a certain matrix being smaller than one, and 3) the singularity issue (when converting BP message into belief) does not occur.
4721:
2202:
3322:
It can then be shown that the points of convergence of the sum-product algorithm represent the points where the free energy in such a system is minimized. Similarly, it can be shown that a fixed point of the iterative belief propagation algorithm in graphs with cycles is a stationary point of a free
2814:
The precise conditions under which loopy belief propagation will converge are still not well understood; it is known that on graphs containing a single loop it converges in most cases, but the probabilities obtained might be incorrect. Several sufficient (but not necessary) conditions for convergence
2779:
In the first step, messages are passed inwards: starting at the leaves, each node passes a message along the (unique) edge towards the root node. The tree structure guarantees that it is possible to obtain messages from all other adjoining nodes before passing the message on. This continues until the
4442:
2473:
In a typical run, each message will be updated iteratively from the previous value of the neighboring messages. Different scheduling can be used for updating the messages. In the case where the graphical model is a tree, an optimal scheduling converges after computing each message exactly once (see
4380:
3317:
1970:
3671:
2740:
5390:
3796:
Convergence of the GaBP algorithm is easier to analyze (relatively to the general BP case) and there are two known sufficient convergence conditions. The first one was formulated by Weiss et al. in the year 2000, when the information matrix
3525:
1625:
416:
2765:, the belief propagation algorithm will compute the exact marginals. Furthermore, with proper scheduling of the message updates, it will terminate after two full passes through the tree. This optimal scheduling can be described as follows:
2849:, but also known as a special case of the max-product or min-sum algorithm, which solves the related problem of maximization, or most probable explanation. Instead of attempting to solve the marginal, the goal here is to find the values
1389:. These messages contain the "influence" that one variable exerts on another. The messages are computed differently depending on whether the node receiving the message is a variable node or a factor node. Keeping the same notation:
6357:
Linear
Detection via Belief Propagation. Danny Bickson, Danny Dolev, Ori Shental, Paul H. Siegel and Jack K. Wolf. In the 45th Annual Allerton Conference on Communication, Control, and Computing, Allerton House, Illinois, 7 Sept..
5219:
2461:
As shown by the previous formula: the complete marginalization is reduced to a sum of products of simpler terms than the ones appearing in the full joint distribution. This is the reason that belief propagation is sometimes called
4716:{\displaystyle \forall x_{v}\in Dom(v),\;\mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\delta ({\text{syndrome}}({\mathbf {x} }'_{v})={\mathbf {s} })\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}}).}
3347:
Improvements in the performance of belief propagation algorithms are also achievable by breaking the replicas symmetry in the distributions of the fields (messages). This generalization leads to a new kind of algorithm called
1335:
3331:
Belief propagation algorithms are normally presented as message update equations on a factor graph, involving messages between variable nodes and their neighboring factor nodes and vice versa. Considering messages between
2591:
5083:
4963:
2938:
3753:
3085:
5510:
984:
1905:
1450:
490:
3184:
6337:
Gaussian belief propagation solver for systems of linear equations. By O. Shental, D. Bickson, P. H. Siegel, J. K. Wolf, and D. Dolev, IEEE Int. Symp. on Inform. Theory (ISIT), Toronto, Canada, July 2008.
4190:
5608:
3336:
in a graph is one way of generalizing the belief propagation algorithm. There are several ways of defining the set of regions in a graph that can exchange messages. One method uses ideas introduced by
2477:
Upon convergence (if convergence happened), the estimated marginal distribution of each node is proportional to the product of all messages from adjoining factors (missing the normalization constant):
3195:
2815:
of loopy belief propagation to a unique fixed point exist. There exist graphs which will fail to converge, or which will oscillate between multiple states over repeated iterations. Techniques like
2783:
The second step involves passing the messages back out: starting at the root, messages are passed in the reverse direction. The algorithm is completed when all leaves have received their messages.
2745:
In the case where the factor graph is acyclic (i.e. is a tree or a forest), these estimated marginal actually converge to the true marginals in a finite number of iterations. This can be shown by
573:
3904:
2415:
2247:
1670:
792:
3920:
The GaBP algorithm was linked to the linear algebra domain, and it was shown that the GaBP algorithm can be viewed as an iterative algorithm for solving the linear system of equations
3559:
1495:
2602:
2596:
Likewise, the estimated joint marginal distribution of the set of variables belonging to one factor is proportional to the product of the factor and the messages from the variables:
1841:
1387:
5930:
6377:
Distributed large scale network utility maximization. D. Bickson, Y. Tock, A. Zymnis, S. Boyd and D. Dolev. In the
International symposium on information theory (ISIT), July 2009.
699:
3368:
1809:
5227:
2474:
next sub-section). When the factor graph has cycles, such an optimal scheduling does not exist, and a typical choice is to update all messages simultaneously at each iteration.
2337:
2197:{\displaystyle \mu _{a\to v}(x_{v})=\sum _{\mathbf {x} '_{a}:x'_{v}=x_{v}}\left(f_{a}(\mathbf {x} '_{a})\prod _{v^{*}\in N(a)\setminus \{v\}}\mu _{v^{*}\to a}(x'_{v^{*}})\right)}
1760:
211:
4840:
819:
600:
4772:
1016:
4726:
This syndrome-based decoder doesn't require information on the received bits, thus can be adapted to quantum codes, where the only information is the measurement syndrome.
1217:
1144:
4182:
2869:
2455:
3392:
4418:
3341:
4047:
3990:
4139:
3791:
726:
647:
517:
295:
268:
2276:
1699:
2837:, which is simply belief propagation on a modified graph guaranteed to be a tree. The basic premise is to eliminate cycles by clustering them into single nodes.
6397:
Dave, Maulik A. (1 December 2006). "Review of "Information Theory, Inference, and
Learning Algorithms by David J. C. MacKay", Cambridge University Press, 2003".
4438:
4107:
4087:
4067:
4010:
2296:
1965:
1945:
1925:
1719:
1490:
1470:
1355:
1257:
1237:
1184:
1164:
1111:
1091:
1071:
1036:
903:
883:
839:
746:
620:
237:
6565:
5091:
3349:
6533:
1262:
652:
Computing marginal distributions using this formula quickly becomes computationally prohibitive as the number of variables grows. For example, given 100
303:
3337:
2483:
1046:
can be represented as a factor graph by using a factor for each node with its parents or a factor for each node with its neighborhood respectively.
4968:
4848:
2881:
3682:
3936:
is the shift vector. Empirically, the GaBP algorithm is shown to converge faster than classical iterative methods like the Jacobi method, the
3003:
1947:
is defined to be the product of the factor with messages from all other nodes, marginalized over all variables except the one associated with
5399:
911:
1851:
1396:
6206:
Weiss, Yair; Freeman, William T. (October 2001). "Correctness of Belief
Propagation in Gaussian Graphical Models of Arbitrary Topology".
3100:
3955:
The previous description of BP algorithm is called the codeword-based decoding, which calculates the approximate marginal probability
2943:
An algorithm that solves this problem is nearly identical to belief propagation, with the sums replaced by maxima in the definitions.
4375:{\displaystyle \forall x_{v}\in Dom(v),\;\mu _{v\to a}(x_{v})=P(X_{v})\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v}).}
3367:
The cluster variational method and the survey propagation algorithms are two different improvements to belief propagation. The name
6611:
6681:
5982:
5883:
3312:{\displaystyle F=U-H=\sum _{\mathbf {X} }P(\mathbf {X} )E(\mathbf {X} )+\sum _{\mathbf {X} }P(\mathbf {X} )\log P(\mathbf {X} ).}
114:
for each unobserved node (or variable), conditional on any observed nodes (or variables). Belief propagation is commonly used in
5518:
3549:
Equivalently, it can be shown that using the
Gaussian model, the solution of the marginalization problem is equivalent to the
6658:
6635:
6548:
5790:
5761:
6381:
6362:
6342:
6267:
2871:
that maximizes the global function (i.e. most probable values in a probabilistic setting), and it can be defined using the
424:
3815:
2819:
can provide an approximate visualization of the progress of belief propagation and an approximate test for convergence.
2342:
2207:
1630:
751:
162:
70:
48:
6145:
Pelizzola, Alessandro (2005). "Cluster variation method in statistical physics and probabilistic graphical models".
41:
6458:
Liu, Ye-Hua; Poulin, David (22 May 2019). "Neural Belief-Propagation
Decoders for Quantum Error-Correcting Codes".
2994:
3666:{\displaystyle {\underset {x}{\operatorname {argmax} }}\ P(x)={\frac {1}{Z}}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x).}
3944:, and others. Additionally, the GaBP algorithm is shown to be immune to numerical problems of the preconditioned
2735:{\displaystyle p_{X_{a}}(\mathbf {x} _{a})\propto f_{a}(\mathbf {x} _{a})\prod _{v\in N(a)}\mu _{v\to a}(x_{v}).}
522:
123:
153:. While the algorithm is not exact on general graphs, it has been shown to be a useful approximate algorithm.
1814:
1360:
5385:{\displaystyle a\to v:L_{a}=(-1)^{s_{a}}2\tanh ^{-1}\prod _{v^{*}\in N(a)\setminus \{v\}}\tanh(l_{v^{*}}/2)}
6208:
5838:
2823:
2796:
905:, with edges between variables and the factors in which they appear. We can write the joint mass function:
841:
factors in a convenient way, belief propagation allows the marginals to be computed much more efficiently.
658:
1765:
6625:
6296:
2301:
1724:
170:
5629:
Braunstein, A.; MĂ©zard, M.; Zecchina, R. (2005). "Survey propagation: An algorithm for satisfiability".
4777:
3941:
6294:
Su, Qinliang; Wu, Yik-Chung (March 2015). "On convergence conditions of
Gaussian belief propagation".
4732:
992:
6734:
6729:
6441:
3945:
2982:
217:
131:
5836:
Weiss, Yair (2000). "Correctness of Local
Probability Propagation in Graphical Models with Loops".
3535:
1189:
1116:
797:
578:
35:
6695:
6222:
5996:
5881:
Mooij, J; Kappen, H (2007). "Sufficient
Conditions for Convergence of the Sum–Product Algorithm".
4144:
3520:{\displaystyle P(x_{i})={\frac {1}{Z}}\int _{j\neq i}\exp(-{\tfrac {1}{2}}x^{T}Ax+b^{T}x)\,dx_{j}}
2852:
1620:{\displaystyle \mu _{v\to a}(x_{v})=\prod _{a^{*}\in N(v)\setminus \{a\}}\mu _{a^{*}\to v}(x_{v})}
3937:
3379:
Gaussian belief propagation is a variant of the belief propagation algorithm when the underlying
2834:
2808:
2420:
115:
6739:
6690:
6217:
5991:
2792:
2746:
52:
6071:"A Theory of Cooperative Phenomena. III. Detailed Discussions of the Cluster Variation Method"
4387:
3676:
This problem is also equivalent to the following minimization problem of the quadratic form:
1337:, whose domain is the set of values that can be taken by the random variable associated with
240:
111:
95:
4015:
3958:
6583:
6304:
6164:
6119:
6110:
Kikuchi, Ryoichi; Brush, Stephen G. (1967). "Improvement of the
Cluster-Variation Method".
6082:
6043:
5939:
4112:
3764:
3550:
2804:
854:
704:
625:
495:
273:
246:
3383:. The first work analyzing this special model was the seminal work of Weiss and Freeman.
2252:
1675:
849:
Variants of the belief propagation algorithm exist for several types of graphical models (
8:
5717:"A computational model for combined causal and diagnostic reasoning in inference systems"
3802:
3380:
2955:
2762:
1043:
146:
107:
6587:
6308:
6262:
6168:
6123:
6086:
6047:
5943:
5214:{\displaystyle v\to a:l_{v}=l_{v}^{(0)}+\sum _{a^{*}\in N(v)\setminus \{a\}}(L_{a^{*}})}
6708:
6677:"Constructing free-energy approximations and generalized belief propagation algorithms"
6599:
6501:
6467:
6422:
6320:
6243:
6188:
6154:
6009:
5978:"Constructing free-energy approximations and generalized belief propagation algorithms"
5955:
5910:
5892:
5863:
5716:
5678:
5656:
5638:
4423:
4092:
4072:
4052:
3995:
2827:
2281:
1950:
1930:
1910:
1704:
1475:
1455:
1340:
1242:
1222:
1169:
1149:
1096:
1076:
1056:
1021:
888:
868:
824:
731:
605:
222:
214:
119:
6176:
5689:
3805:. The second convergence condition was formulated by Johnson et al. in 2006, when the
2958:) in a graphical model. More precisely, the marginalization problem defined above is
6654:
6631:
6544:
6493:
6485:
6414:
6235:
6180:
5855:
5786:
5757:
2846:
850:
6712:
6505:
6426:
6324:
6247:
6013:
5867:
5813:
Wainwright, M. J.; Jordan, M. I. (2007). "2.1 Probability Distributions on Graphs".
6700:
6603:
6591:
6481:
6477:
6406:
6312:
6227:
6172:
6127:
6090:
6051:
6001:
5959:
5947:
5902:
5847:
5818:
5724:
Proceedings of the Eighth International Joint Conference on Artificial Intelligence
5660:
5648:
3539:
3371:(GSP) is waiting to be assigned to the algorithm that merges both generalizations.
2970:
2959:
1330:{\displaystyle \mu _{v\to a},\mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }
1039:
411:{\displaystyle p_{X_{i}}(x_{i})=\sum _{\mathbf {x} ':x'_{i}=x_{i}}p(\mathbf {x} ')}
103:
6523:
6385:
6366:
6346:
5914:
3806:
3091:
862:
165:
99:
6378:
6359:
6339:
6676:
6646:
6231:
6192:
5977:
5851:
5778:
5754:
Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
3361:
3357:
2986:
2586:{\displaystyle p_{X_{v}}(x_{v})\propto \prod _{a\in N(v)}\mu _{a\to v}(x_{v}).}
135:
6723:
6616:
6595:
6489:
6418:
6316:
6184:
5951:
5078:{\displaystyle L_{a}=\log {\frac {u_{a\to v}(x_{v}=0)}{u_{a\to v}(x_{v}=1)}}}
4958:{\displaystyle l_{v}=\log {\frac {u_{v\to a}(x_{v}=0)}{u_{v\to a}(x_{v}=1)}}}
2969:
The memory usage of belief propagation can be reduced through the use of the
2933:{\displaystyle \operatorname {*} {\arg \max }_{\mathbf {x} }g(\mathbf {x} ).}
122:, and has demonstrated empirical success in numerous applications, including
6704:
6410:
6005:
5906:
6497:
6239:
6055:
5859:
3090:(as per the factor graph representation) can be viewed as a measure of the
2758:
858:
6261:
Malioutov, Dmitry M.; Johnson, Jason K.; Willsky, Alan S. (October 2006).
5727:
5679:"Reverend Bayes on inference engines: A distributed hierarchical approach"
2795:
graphical models, the Belief Propagation algorithm can be used in general
2772:; any non-root node which is connected to only one other node is called a
6159:
5817:. Foundations and Trends in Machine Learning. Vol. 1. pp. 5–9.
5749:
5712:
5674:
3748:{\displaystyle {\underset {x}{\operatorname {min} }}\ 1/2x^{T}Ax-b^{T}x.}
3353:
2963:
653:
142:
127:
5686:
Proceedings of the Second National Conference on Artificial Intelligence
4774:, those messages can be simplified to cause an exponential reduction of
3080:{\displaystyle P(\mathbf {X} )={\frac {1}{Z}}\prod _{f_{j}}f_{j}(x_{j})}
6034:
Kikuchi, Ryoichi (15 March 1951). "A Theory of Cooperative Phenomena".
5822:
2816:
6528:—Webpage containing recent publications as well as Matlab source code.
6131:
6095:
6070:
5652:
5505:{\displaystyle l_{v}^{(0)}=\log(P(x_{v}=0)/P(x_{v}=1))={\text{const}}}
4141:. This variation only changes the interpretation of the mass function
2768:
Before starting, the graph is oriented by designating one node as the
979:{\displaystyle p(\mathbf {x} )=\prod _{a\in F}f_{a}(\mathbf {x} _{a})}
2947:
1900:{\displaystyle \mu _{a\to v}:\operatorname {Dom} (v)\to \mathbb {R} }
1445:{\displaystyle \mu _{v\to a}:\operatorname {Dom} (v)\to \mathbb {R} }
91:
2833:
One method of exact marginalization in general graphs is called the
6472:
5897:
5643:
150:
2822:
There are other approximate methods for marginalization including
6574:
Löliger, Hans-Andrea (2004). "An Introduction to Factor Graphs".
5928:
Löliger, Hans-Andrea (2004). "An Introduction to Factor Graphs".
5815:
Graphical Models, Exponential Families, and Variational Inference
3386:
The GaBP algorithm solves the following marginalization problem:
3179:{\displaystyle E(\mathbf {X} )=-\log \prod _{f_{j}}f_{j}(x_{j}).}
2951:
2872:
857:
in particular). We describe here the variant that operates on a
6263:"Walk-sums and belief propagation in Gaussian graphical models"
1018:
is the vector of neighboring variable nodes to the factor node
145:
in 1982, who formulated it as an exact inference algorithm on
1053:
along the edges between the hidden nodes. More precisely, if
2780:
root has obtained messages from all of its adjoining nodes.
1049:
The algorithm works by passing real valued functions called
3758:
Which is also equivalent to the linear system of equations
2981:
The sum-product algorithm is related to the calculation of
2786:
844:
6647:"Understanding Belief Propagation and Its Generalizations"
6069:
Kurata, Michio; Kikuchi, Ryoichi; Watari, Tatsuro (1953).
5779:"Understanding Belief Propagation and Its Generalizations"
5603:{\displaystyle l_{v}=l_{v}^{(0)}+\sum _{a\in N(v)}(L_{a})}
2840:
5976:
Yedidia, J.S.; Freeman, W.T.; Weiss, Y.; Y. (July 2005).
6645:
Yedidia, J.S.; Freeman, W.T.; Weiss, Y. (January 2003).
5628:
6651:
Exploring Artificial Intelligence in the New Millennium
6260:
5783:
Exploring Artificial Intelligence in the New Millennium
5515:
The posterior log-likelihood ratio can be estimated as
3326:
16:
Algorithm for statistical inference on graphical models
5692:. Menlo Park, California: AAAI Press. pp. 133–136
3614:
3457:
6675:
Yedidia, J.S.; Freeman, W.T.; Weiss, Y. (July 2005).
5975:
5521:
5402:
5230:
5094:
4971:
4851:
4780:
4735:
4445:
4426:
4390:
4193:
4147:
4115:
4095:
4075:
4055:
4018:
3998:
3961:
3818:
3767:
3685:
3562:
3395:
3374:
3340:
in the physics literature, and is known as Kikuchi's
3198:
3103:
3006:
2884:
2855:
2605:
2486:
2423:
2345:
2304:
2284:
2255:
2210:
1973:
1953:
1933:
1913:
1854:
1817:
1768:
1727:
1707:
1678:
1633:
1498:
1478:
1458:
1399:
1363:
1343:
1265:
1245:
1225:
1192:
1172:
1152:
1119:
1099:
1079:
1059:
1024:
995:
914:
891:
871:
827:
800:
754:
734:
707:
661:
628:
608:
581:
525:
498:
485:{\displaystyle \mathbf {x} '=(x'_{1},\ldots ,x'_{n})}
427:
306:
276:
249:
225:
173:
6442:"Simplification of the Belief propagation algorithm"
5756:(2nd ed.). San Francisco, CA: Morgan Kaufmann.
821:. If it is known that the probability mass function
6674:
6644:
6068:
3899:{\displaystyle \rho (I-|D^{-1/2}AD^{-1/2}|)<1\,}
2950:problems like marginalization and maximization are
2845:A similar algorithm is commonly referred to as the
5602:
5504:
5384:
5213:
5077:
4957:
4834:
4766:
4715:
4432:
4412:
4374:
4176:
4133:
4109:is the decoded error. The decoded input vector is
4101:
4081:
4061:
4041:
4004:
3984:
3898:
3785:
3747:
3665:
3519:
3311:
3178:
3079:
2932:
2863:
2734:
2585:
2449:
2409:
2331:
2290:
2270:
2241:
2196:
1959:
1939:
1919:
1899:
1835:
1803:
1754:
1713:
1693:
1664:
1619:
1484:
1464:
1444:
1381:
1349:
1329:
1251:
1231:
1211:
1178:
1158:
1138:
1105:
1085:
1065:
1030:
1010:
978:
897:
877:
833:
813:
786:
740:
720:
693:
641:
614:
594:
567:
511:
484:
410:
289:
262:
231:
205:
6649:. In Lakemeyer, Gerhard; Nebel, Bernhard (eds.).
6620:. 9 July 2005. Issue 2507 (Registration required)
5781:. In Lakemeyer, Gerhard; Nebel, Bernhard (eds.).
5777:Yedidia, J.S.; Freeman, W.T.; Y. (January 2003).
2954:to solve exactly and approximately (at least for
2410:{\displaystyle \mu _{a\to v}(x_{v})=f_{a}(x_{v})}
748:and the above formula would involve summing over
6721:
5812:
5776:
3352:(SP), which have proved to be very efficient in
2901:
2242:{\displaystyle x_{v}\in \operatorname {Dom} (v)}
1665:{\displaystyle x_{v}\in \operatorname {Dom} (v)}
787:{\displaystyle 2^{99}\approx 6.34\times 10^{29}}
5710:
4012:. There is an equivalent form, which calculate
6147:Journal of Physics A: Mathematical and General
2278:is the set of neighboring (variable) nodes to
6567:A Tutorial Introduction to Belief Propagation
6379:http://www.cs.huji.ac.il/labs/danss/p2p/gabp/
6360:http://www.cs.huji.ac.il/labs/danss/p2p/gabp/
6340:http://www.cs.huji.ac.il/labs/danss/p2p/gabp/
5806:
3950:
6205:
6109:
5704:
5340:
5334:
5183:
5177:
4797:
4791:
4761:
4749:
4656:
4650:
4325:
4319:
2752:
2326:
2320:
2135:
2129:
1749:
1743:
1573:
1567:
865:containing nodes corresponding to variables
6612:Communication Speed Nears Terminal Velocity
5971:
5969:
5880:
4420:is the prior error probability on variable
5770:
4483:
4231:
2976:
1701:is the set of neighboring factor nodes of
568:{\displaystyle \mathbf {x} ':x'_{i}=x_{i}}
6694:
6623:
6525:Gaussian Belief Propagation Resource Page
6471:
6457:
6287:
6221:
6158:
6144:
6094:
5995:
5896:
5667:
5642:
4069:is the syndrome of the received codeword
3895:
3503:
2799:. The algorithm is then sometimes called
1893:
1438:
1323:
71:Learn how and when to remove this message
6541:Pattern Recognition and Machine Learning
6371:
6351:
5966:
2791:Although it was originally designed for
2787:Approximate algorithm for general graphs
1811:is set to the uniform distribution over
845:Description of the sum-product algorithm
34:This article includes a list of general
6682:IEEE Transactions on Information Theory
6573:
6331:
6254:
6033:
5983:IEEE Transactions on Information Theory
5927:
5884:IEEE Transactions on Information Theory
5742:
2841:Related algorithm and complexity issues
1836:{\displaystyle \operatorname {Dom} (v)}
1382:{\displaystyle \operatorname {Dom} (v)}
1113:in the factor graph, then the messages
575:means that the sum is taken over those
492:is a vector of possible values for the
6722:
6531:
6439:
3189:The free energy of the system is then
2973:(at a small cost in time complexity).
6653:. Morgan Kaufmann. pp. 239–269.
5835:
5785:. Morgan Kaufmann. pp. 239–236.
5748:
5673:
5624:
5622:
3530:where Z is a normalization constant,
694:{\displaystyle X_{1},\ldots ,X_{100}}
6396:
6293:
6268:Journal of Machine Learning Research
6199:
3327:Generalized belief propagation (GBP)
1804:{\displaystyle \mu _{v\to a}(x_{v})}
141:The algorithm was first proposed by
20:
2803:, because graphs typically contain
2332:{\displaystyle N(a)\setminus \{v\}}
1755:{\displaystyle N(v)\setminus \{a\}}
206:{\displaystyle X_{1},\ldots ,X_{n}}
13:
6516:
6440:Filler, Tomas (17 November 2009).
5631:Random Structures & Algorithms
5619:
4835:{\displaystyle 2^{|\{v\}|+|N(v)|}}
4446:
4194:
3538:(inverse covariance matrix a.k.a.
3375:Gaussian belief propagation (GaBP)
239:, a common task is to compute the
40:it lacks sufficient corresponding
14:
6751:
5331:
5174:
4647:
4316:
3094:present in a system, computed as
2317:
2126:
1740:
1564:
4767:{\displaystyle x_{i}\in \{0,1\}}
4609:
4587:
4526:
3299:
3279:
3266:
3250:
3236:
3223:
3111:
3014:
2920:
2907:
2857:
2659:
2628:
2080:
2016:
1011:{\displaystyle \mathbf {x} _{a}}
998:
963:
922:
803:
584:
528:
430:
397:
350:
25:
6576:IEEE Signal Processing Magazine
6532:Bishop, Christopher M. (2006).
6451:
6433:
6390:
6138:
6112:The Journal of Chemical Physics
6103:
6075:The Journal of Chemical Physics
6062:
6027:
5931:IEEE Signal Processing Magazine
5730:. Vol. 1. pp. 190–193
4184:. Explicitly, the messages are
6630:. Cambridge University Press.
6543:. Springer. pp. 359–418.
6482:10.1103/physrevlett.122.200501
5921:
5874:
5829:
5597:
5584:
5579:
5573:
5551:
5545:
5491:
5488:
5469:
5458:
5439:
5433:
5419:
5413:
5379:
5351:
5328:
5322:
5266:
5256:
5234:
5208:
5188:
5171:
5165:
5136:
5130:
5098:
5069:
5050:
5042:
5029:
5010:
5002:
4949:
4930:
4922:
4909:
4890:
4882:
4826:
4822:
4816:
4809:
4801:
4787:
4707:
4684:
4676:
4644:
4638:
4614:
4601:
4581:
4573:
4513:
4500:
4492:
4477:
4471:
4407:
4394:
4366:
4353:
4345:
4313:
4307:
4283:
4270:
4261:
4248:
4240:
4225:
4219:
4171:
4158:
4036:
4029:
4022:
3979:
3972:
3965:
3932:is the information matrix and
3886:
3882:
3832:
3822:
3657:
3607:
3585:
3579:
3500:
3450:
3412:
3399:
3369:generalized survey propagation
3303:
3295:
3283:
3275:
3254:
3246:
3240:
3232:
3170:
3157:
3115:
3107:
3074:
3061:
3018:
3010:
2924:
2916:
2726:
2713:
2705:
2692:
2686:
2669:
2654:
2638:
2623:
2577:
2564:
2556:
2543:
2537:
2517:
2504:
2404:
2391:
2375:
2362:
2354:
2314:
2308:
2265:
2259:
2236:
2230:
2186:
2163:
2155:
2123:
2117:
2093:
2075:
2003:
1990:
1982:
1889:
1886:
1880:
1863:
1830:
1824:
1798:
1785:
1777:
1737:
1731:
1688:
1682:
1659:
1653:
1614:
1601:
1593:
1561:
1555:
1528:
1515:
1507:
1434:
1431:
1425:
1408:
1376:
1370:
1319:
1316:
1310:
1293:
1274:
1201:
1128:
1093:is a factor node connected to
973:
958:
926:
918:
701:, computing a single marginal
479:
441:
405:
392:
337:
324:
124:low-density parity-check codes
1:
6534:"Chapter 8: Graphical models"
5612:
2997:. A probability distribution
1212:{\displaystyle \mu _{a\to v}}
1139:{\displaystyle \mu _{v\to a}}
814:{\displaystyle \mathbf {x} '}
595:{\displaystyle \mathbf {x} '}
156:
5728:IJCAI-83: Karlsruhe, Germany
4845:Define log-likelihood ratio
4177:{\displaystyle f_{a}(X_{a})}
2864:{\displaystyle \mathbf {x} }
7:
6297:IEEE Trans. Signal Process.
6177:10.1088/0305-4470/38/33/R01
2464:sum-product message passing
2450:{\displaystyle x_{v}=x_{a}}
270:. The marginal of a single
88:sum–product message passing
10:
6756:
6232:10.1162/089976601750541769
5852:10.1162/089976600300015880
3992:, given received codeword
3951:Syndrome-based BP decoding
3942:successive over-relaxation
3381:distributions are Gaussian
1259:are real-valued functions
622:th coordinate is equal to
6627:Iterative Receiver Design
6610:Mackenzie, Dana (2005). "
6564:Coughlan, James. (2009).
3946:conjugate gradient method
3938:Gauss–Seidel method
2753:Exact algorithm for trees
218:probability mass function
6624:Wymeersch, Henk (2007).
6596:10.1109/MSP.2004.1267047
6522:Bickson, Danny. (2009).
6317:10.1109/TSP.2015.2389755
5952:10.1109/msp.2004.1267047
4413:{\displaystyle P(X_{v})}
3536:positive definite matrix
3342:cluster variation method
2946:It is worth noting that
2801:loopy belief propagation
6705:10.1109/TIT.2005.850085
6460:Physical Review Letters
6411:10.1145/1189056.1189063
6006:10.1109/TIT.2005.850085
5907:10.1109/TIT.2007.909166
5690:AAAI-82: Pittsburgh, PA
2977:Relation to free energy
2835:junction tree algorithm
1073:is a variable node and
116:artificial intelligence
90:, is a message-passing
55:more precise citations.
6056:10.1103/PhysRev.81.988
5604:
5506:
5386:
5215:
5079:
4959:
4836:
4768:
4717:
4434:
4414:
4376:
4178:
4135:
4103:
4083:
4063:
4043:
4042:{\displaystyle P(e|s)}
4006:
3986:
3985:{\displaystyle P(x|X)}
3900:
3787:
3749:
3667:
3521:
3323:energy approximation.
3313:
3180:
3081:
2934:
2865:
2747:mathematical induction
2736:
2587:
2451:
2411:
2333:
2292:
2272:
2243:
2198:
1961:
1941:
1921:
1901:
1837:
1805:
1756:
1715:
1695:
1666:
1621:
1486:
1466:
1446:
1383:
1351:
1331:
1253:
1233:
1213:
1180:
1160:
1140:
1107:
1087:
1067:
1032:
1012:
980:
899:
879:
861:. A factor graph is a
835:
815:
788:
742:
722:
695:
643:
616:
596:
569:
513:
486:
412:
291:
264:
241:marginal distributions
233:
207:
161:Given a finite set of
5605:
5507:
5387:
5216:
5080:
4960:
4837:
4769:
4718:
4435:
4415:
4377:
4179:
4136:
4134:{\displaystyle x=X+e}
4104:
4084:
4064:
4044:
4007:
3987:
3901:
3788:
3786:{\displaystyle Ax=b.}
3750:
3668:
3546:is the shift vector.
3522:
3314:
3181:
3082:
2935:
2866:
2757:In the case when the
2737:
2588:
2468:sum-product algorithm
2452:
2417:, since in this case
2412:
2334:
2293:
2273:
2244:
2199:
1962:
1942:
1922:
1902:
1838:
1806:
1757:
1716:
1696:
1667:
1622:
1487:
1467:
1452:from a variable node
1447:
1384:
1352:
1332:
1254:
1234:
1214:
1181:
1161:
1141:
1108:
1088:
1068:
1033:
1013:
981:
900:
880:
836:
816:
789:
743:
723:
721:{\displaystyle X_{i}}
696:
644:
642:{\displaystyle x_{i}}
617:
597:
570:
514:
512:{\displaystyle X_{i}}
487:
413:
292:
290:{\displaystyle X_{i}}
265:
263:{\displaystyle X_{i}}
234:
208:
112:marginal distribution
6384:14 June 2011 at the
6365:14 June 2011 at the
6345:14 June 2011 at the
5519:
5400:
5228:
5092:
4969:
4849:
4778:
4733:
4729:In the binary case,
4443:
4424:
4388:
4191:
4145:
4113:
4093:
4073:
4053:
4016:
3996:
3959:
3816:
3765:
3683:
3560:
3553:assignment problem:
3393:
3196:
3101:
3004:
2962:and maximization is
2882:
2853:
2603:
2484:
2421:
2343:
2302:
2282:
2271:{\displaystyle N(a)}
2253:
2208:
1971:
1951:
1931:
1911:
1852:
1815:
1766:
1725:
1705:
1694:{\displaystyle N(v)}
1676:
1631:
1496:
1476:
1456:
1397:
1361:
1341:
1263:
1243:
1223:
1190:
1170:
1150:
1117:
1097:
1077:
1057:
1022:
993:
912:
889:
869:
855:Markov random fields
825:
798:
794:possible values for
752:
732:
705:
659:
626:
606:
579:
523:
496:
425:
304:
274:
247:
223:
171:
149:, later extended to
110:. It calculates the
108:Markov random fields
6588:2004ISPM...21...28L
6309:2015ITSP...63.1144S
6169:2005JPhA...38R.309P
6124:1967JChPh..47..195K
6087:1953JChPh..21..434K
6048:1951PhRv...81..988K
5944:2004ISPM...21...28L
5555:
5423:
5140:
4706:
4600:
4554:
4538:
3803:diagonally dominant
2828:Monte Carlo methods
2824:variational methods
2185:
2092:
2044:
2028:
1927:to a variable node
1907:from a factor node
1044:Markov random field
551:
519:, and the notation
478:
456:
373:
134:approximation, and
6209:Neural Computation
5839:Neural Computation
5823:10.1561/2200000001
5600:
5583:
5535:
5502:
5403:
5382:
5344:
5211:
5187:
5120:
5075:
4955:
4842:in the complexity
4832:
4764:
4713:
4687:
4660:
4584:
4569:
4542:
4524:
4430:
4410:
4372:
4329:
4174:
4131:
4099:
4079:
4059:
4039:
4002:
3982:
3896:
3783:
3745:
3694:
3663:
3623:
3571:
3517:
3466:
3350:survey propagation
3309:
3271:
3228:
3176:
3146:
3077:
3050:
2995:partition function
2930:
2861:
2732:
2696:
2583:
2547:
2447:
2407:
2329:
2288:
2268:
2239:
2194:
2166:
2139:
2078:
2059:
2032:
2014:
1957:
1937:
1917:
1897:
1833:
1801:
1752:
1711:
1691:
1662:
1617:
1577:
1482:
1462:
1442:
1379:
1347:
1327:
1249:
1229:
1209:
1176:
1156:
1136:
1103:
1083:
1063:
1028:
1008:
976:
947:
895:
875:
831:
811:
784:
738:
718:
691:
639:
612:
592:
565:
539:
509:
482:
466:
444:
408:
388:
361:
287:
260:
229:
203:
120:information theory
84:Belief propagation
6660:978-1-55860-811-5
6637:978-0-521-87315-4
6550:978-0-387-31073-2
6216:(10): 2173–2200.
6153:(33): R309–R339.
6132:10.1063/1.1711845
6096:10.1063/1.1698926
5891:(12): 4422–4437.
5792:978-1-55860-811-5
5763:978-1-55860-479-7
5653:10.1002/rsa.20057
5559:
5500:
5301:
5144:
5073:
4953:
4617:
4579:
4519:
4433:{\displaystyle v}
4286:
4102:{\displaystyle e}
4082:{\displaystyle X}
4062:{\displaystyle s}
4005:{\displaystyle X}
3698:
3687:
3622:
3599:
3575:
3564:
3465:
3426:
3260:
3217:
3130:
3034:
3032:
2888:
2847:Viterbi algorithm
2672:
2523:
2291:{\displaystyle a}
2096:
2009:
1960:{\displaystyle v}
1940:{\displaystyle v}
1920:{\displaystyle a}
1714:{\displaystyle v}
1534:
1485:{\displaystyle a}
1472:to a factor node
1465:{\displaystyle v}
1350:{\displaystyle v}
1252:{\displaystyle v}
1232:{\displaystyle a}
1186:and the messages
1179:{\displaystyle a}
1159:{\displaystyle v}
1106:{\displaystyle v}
1086:{\displaystyle a}
1066:{\displaystyle v}
1031:{\displaystyle a}
932:
898:{\displaystyle F}
878:{\displaystyle V}
851:Bayesian networks
834:{\displaystyle p}
741:{\displaystyle p}
615:{\displaystyle i}
343:
297:is defined to be
232:{\displaystyle p}
104:Bayesian networks
81:
80:
73:
6747:
6735:Graphical models
6730:Graph algorithms
6716:
6698:
6689:(7): 2282–2312.
6671:
6669:
6667:
6641:
6607:
6561:
6559:
6557:
6538:
6510:
6509:
6475:
6455:
6449:
6448:
6446:
6437:
6431:
6430:
6394:
6388:
6375:
6369:
6355:
6349:
6335:
6329:
6328:
6303:(5): 1144–1155.
6291:
6285:
6284:
6282:
6280:
6258:
6252:
6251:
6225:
6203:
6197:
6196:
6162:
6160:cond-mat/0508216
6142:
6136:
6135:
6107:
6101:
6100:
6098:
6066:
6060:
6059:
6031:
6025:
6024:
6022:
6020:
5999:
5990:(7): 2282–2312.
5973:
5964:
5963:
5925:
5919:
5918:
5900:
5878:
5872:
5871:
5833:
5827:
5826:
5810:
5804:
5803:
5801:
5799:
5774:
5768:
5767:
5746:
5740:
5739:
5737:
5735:
5721:
5708:
5702:
5701:
5699:
5697:
5683:
5671:
5665:
5664:
5646:
5626:
5609:
5607:
5606:
5601:
5596:
5595:
5582:
5554:
5543:
5531:
5530:
5511:
5509:
5508:
5503:
5501:
5498:
5481:
5480:
5465:
5451:
5450:
5422:
5411:
5391:
5389:
5388:
5383:
5375:
5370:
5369:
5368:
5367:
5343:
5315:
5314:
5297:
5296:
5281:
5280:
5279:
5278:
5252:
5251:
5220:
5218:
5217:
5212:
5207:
5206:
5205:
5204:
5186:
5158:
5157:
5139:
5128:
5116:
5115:
5084:
5082:
5081:
5076:
5074:
5072:
5062:
5061:
5049:
5048:
5032:
5022:
5021:
5009:
5008:
4992:
4981:
4980:
4964:
4962:
4961:
4956:
4954:
4952:
4942:
4941:
4929:
4928:
4912:
4902:
4901:
4889:
4888:
4872:
4861:
4860:
4841:
4839:
4838:
4833:
4831:
4830:
4829:
4812:
4804:
4790:
4773:
4771:
4770:
4765:
4745:
4744:
4722:
4720:
4719:
4714:
4702:
4701:
4700:
4683:
4682:
4675:
4674:
4659:
4631:
4630:
4613:
4612:
4596:
4591:
4590:
4580:
4577:
4568:
4567:
4566:
4550:
4534:
4529:
4512:
4511:
4499:
4498:
4458:
4457:
4439:
4437:
4436:
4431:
4419:
4417:
4416:
4411:
4406:
4405:
4381:
4379:
4378:
4373:
4365:
4364:
4352:
4351:
4344:
4343:
4328:
4300:
4299:
4282:
4281:
4260:
4259:
4247:
4246:
4206:
4205:
4183:
4181:
4180:
4175:
4170:
4169:
4157:
4156:
4140:
4138:
4137:
4132:
4108:
4106:
4105:
4100:
4088:
4086:
4085:
4080:
4068:
4066:
4065:
4060:
4048:
4046:
4045:
4040:
4032:
4011:
4009:
4008:
4003:
3991:
3989:
3988:
3983:
3975:
3905:
3903:
3902:
3897:
3885:
3880:
3879:
3875:
3856:
3855:
3851:
3835:
3792:
3790:
3789:
3784:
3754:
3752:
3751:
3746:
3738:
3737:
3719:
3718:
3706:
3696:
3695:
3672:
3670:
3669:
3664:
3653:
3652:
3634:
3633:
3624:
3615:
3600:
3592:
3573:
3572:
3540:precision matrix
3526:
3524:
3523:
3518:
3516:
3515:
3496:
3495:
3477:
3476:
3467:
3458:
3443:
3442:
3427:
3419:
3411:
3410:
3318:
3316:
3315:
3310:
3302:
3282:
3270:
3269:
3253:
3239:
3227:
3226:
3185:
3183:
3182:
3177:
3169:
3168:
3156:
3155:
3145:
3144:
3143:
3114:
3086:
3084:
3083:
3078:
3073:
3072:
3060:
3059:
3049:
3048:
3047:
3033:
3025:
3017:
2971:Island algorithm
2939:
2937:
2936:
2931:
2923:
2912:
2911:
2910:
2904:
2889:
2886:
2870:
2868:
2867:
2862:
2860:
2741:
2739:
2738:
2733:
2725:
2724:
2712:
2711:
2695:
2668:
2667:
2662:
2653:
2652:
2637:
2636:
2631:
2622:
2621:
2620:
2619:
2592:
2590:
2589:
2584:
2576:
2575:
2563:
2562:
2546:
2516:
2515:
2503:
2502:
2501:
2500:
2456:
2454:
2453:
2448:
2446:
2445:
2433:
2432:
2416:
2414:
2413:
2408:
2403:
2402:
2390:
2389:
2374:
2373:
2361:
2360:
2338:
2336:
2335:
2330:
2297:
2295:
2294:
2289:
2277:
2275:
2274:
2269:
2248:
2246:
2245:
2240:
2220:
2219:
2203:
2201:
2200:
2195:
2193:
2189:
2181:
2180:
2179:
2162:
2161:
2154:
2153:
2138:
2110:
2109:
2088:
2083:
2074:
2073:
2058:
2057:
2056:
2040:
2024:
2019:
2002:
2001:
1989:
1988:
1966:
1964:
1963:
1958:
1946:
1944:
1943:
1938:
1926:
1924:
1923:
1918:
1906:
1904:
1903:
1898:
1896:
1870:
1869:
1842:
1840:
1839:
1834:
1810:
1808:
1807:
1802:
1797:
1796:
1784:
1783:
1761:
1759:
1758:
1753:
1720:
1718:
1717:
1712:
1700:
1698:
1697:
1692:
1671:
1669:
1668:
1663:
1643:
1642:
1626:
1624:
1623:
1618:
1613:
1612:
1600:
1599:
1592:
1591:
1576:
1548:
1547:
1527:
1526:
1514:
1513:
1491:
1489:
1488:
1483:
1471:
1469:
1468:
1463:
1451:
1449:
1448:
1443:
1441:
1415:
1414:
1388:
1386:
1385:
1380:
1356:
1354:
1353:
1348:
1336:
1334:
1333:
1328:
1326:
1300:
1299:
1281:
1280:
1258:
1256:
1255:
1250:
1238:
1236:
1235:
1230:
1218:
1216:
1215:
1210:
1208:
1207:
1185:
1183:
1182:
1177:
1165:
1163:
1162:
1157:
1145:
1143:
1142:
1137:
1135:
1134:
1112:
1110:
1109:
1104:
1092:
1090:
1089:
1084:
1072:
1070:
1069:
1064:
1040:Bayesian network
1037:
1035:
1034:
1029:
1017:
1015:
1014:
1009:
1007:
1006:
1001:
985:
983:
982:
977:
972:
971:
966:
957:
956:
946:
925:
904:
902:
901:
896:
884:
882:
881:
876:
840:
838:
837:
832:
820:
818:
817:
812:
810:
806:
793:
791:
790:
785:
783:
782:
764:
763:
747:
745:
744:
739:
727:
725:
724:
719:
717:
716:
700:
698:
697:
692:
690:
689:
671:
670:
654:binary variables
648:
646:
645:
640:
638:
637:
621:
619:
618:
613:
601:
599:
598:
593:
591:
587:
574:
572:
571:
566:
564:
563:
547:
535:
531:
518:
516:
515:
510:
508:
507:
491:
489:
488:
483:
474:
452:
437:
433:
417:
415:
414:
409:
404:
400:
387:
386:
385:
369:
357:
353:
336:
335:
323:
322:
321:
320:
296:
294:
293:
288:
286:
285:
269:
267:
266:
261:
259:
258:
238:
236:
235:
230:
212:
210:
209:
204:
202:
201:
183:
182:
166:random variables
100:graphical models
86:, also known as
76:
69:
65:
62:
56:
51:this article by
42:inline citations
29:
28:
21:
6755:
6754:
6750:
6749:
6748:
6746:
6745:
6744:
6720:
6719:
6665:
6663:
6661:
6638:
6555:
6553:
6551:
6536:
6519:
6517:Further reading
6514:
6513:
6456:
6452:
6444:
6438:
6434:
6399:ACM SIGACT News
6395:
6391:
6386:Wayback Machine
6376:
6372:
6367:Wayback Machine
6356:
6352:
6347:Wayback Machine
6336:
6332:
6292:
6288:
6278:
6276:
6259:
6255:
6204:
6200:
6143:
6139:
6108:
6104:
6067:
6063:
6042:(6): 988–1003.
6036:Physical Review
6032:
6028:
6018:
6016:
5974:
5967:
5926:
5922:
5879:
5875:
5834:
5830:
5811:
5807:
5797:
5795:
5793:
5775:
5771:
5764:
5747:
5743:
5733:
5731:
5719:
5709:
5705:
5695:
5693:
5681:
5672:
5668:
5627:
5620:
5615:
5591:
5587:
5563:
5544:
5539:
5526:
5522:
5520:
5517:
5516:
5497:
5476:
5472:
5461:
5446:
5442:
5412:
5407:
5401:
5398:
5397:
5371:
5363:
5359:
5358:
5354:
5310:
5306:
5305:
5289:
5285:
5274:
5270:
5269:
5265:
5247:
5243:
5229:
5226:
5225:
5200:
5196:
5195:
5191:
5153:
5149:
5148:
5129:
5124:
5111:
5107:
5093:
5090:
5089:
5057:
5053:
5038:
5034:
5033:
5017:
5013:
4998:
4994:
4993:
4991:
4976:
4972:
4970:
4967:
4966:
4937:
4933:
4918:
4914:
4913:
4897:
4893:
4878:
4874:
4873:
4871:
4856:
4852:
4850:
4847:
4846:
4825:
4808:
4800:
4786:
4785:
4781:
4779:
4776:
4775:
4740:
4736:
4734:
4731:
4730:
4696:
4692:
4691:
4670:
4666:
4665:
4661:
4626:
4622:
4621:
4608:
4607:
4592:
4586:
4585:
4576:
4562:
4558:
4546:
4530:
4525:
4523:
4507:
4503:
4488:
4484:
4453:
4449:
4444:
4441:
4440:
4425:
4422:
4421:
4401:
4397:
4389:
4386:
4385:
4360:
4356:
4339:
4335:
4334:
4330:
4295:
4291:
4290:
4277:
4273:
4255:
4251:
4236:
4232:
4201:
4197:
4192:
4189:
4188:
4165:
4161:
4152:
4148:
4146:
4143:
4142:
4114:
4111:
4110:
4094:
4091:
4090:
4074:
4071:
4070:
4054:
4051:
4050:
4028:
4017:
4014:
4013:
3997:
3994:
3993:
3971:
3960:
3957:
3956:
3953:
3881:
3871:
3864:
3860:
3847:
3840:
3836:
3831:
3817:
3814:
3813:
3807:spectral radius
3766:
3763:
3762:
3733:
3729:
3714:
3710:
3702:
3686:
3684:
3681:
3680:
3648:
3644:
3629:
3625:
3613:
3591:
3563:
3561:
3558:
3557:
3534:is a symmetric
3511:
3507:
3491:
3487:
3472:
3468:
3456:
3432:
3428:
3418:
3406:
3402:
3394:
3391:
3390:
3377:
3329:
3298:
3278:
3265:
3264:
3249:
3235:
3222:
3221:
3197:
3194:
3193:
3164:
3160:
3151:
3147:
3139:
3135:
3134:
3110:
3102:
3099:
3098:
3092:internal energy
3068:
3064:
3055:
3051:
3043:
3039:
3038:
3024:
3013:
3005:
3002:
3001:
2979:
2919:
2906:
2905:
2894:
2893:
2885:
2883:
2880:
2879:
2856:
2854:
2851:
2850:
2843:
2789:
2755:
2720:
2716:
2701:
2697:
2676:
2663:
2658:
2657:
2648:
2644:
2632:
2627:
2626:
2615:
2611:
2610:
2606:
2604:
2601:
2600:
2571:
2567:
2552:
2548:
2527:
2511:
2507:
2496:
2492:
2491:
2487:
2485:
2482:
2481:
2441:
2437:
2428:
2424:
2422:
2419:
2418:
2398:
2394:
2385:
2381:
2369:
2365:
2350:
2346:
2344:
2341:
2340:
2339:is empty, then
2303:
2300:
2299:
2283:
2280:
2279:
2254:
2251:
2250:
2215:
2211:
2209:
2206:
2205:
2175:
2171:
2170:
2149:
2145:
2144:
2140:
2105:
2101:
2100:
2084:
2079:
2069:
2065:
2064:
2060:
2052:
2048:
2036:
2020:
2015:
2013:
1997:
1993:
1978:
1974:
1972:
1969:
1968:
1952:
1949:
1948:
1932:
1929:
1928:
1912:
1909:
1908:
1892:
1859:
1855:
1853:
1850:
1849:
1816:
1813:
1812:
1792:
1788:
1773:
1769:
1767:
1764:
1763:
1726:
1723:
1722:
1706:
1703:
1702:
1677:
1674:
1673:
1638:
1634:
1632:
1629:
1628:
1608:
1604:
1587:
1583:
1582:
1578:
1543:
1539:
1538:
1522:
1518:
1503:
1499:
1497:
1494:
1493:
1477:
1474:
1473:
1457:
1454:
1453:
1437:
1404:
1400:
1398:
1395:
1394:
1362:
1359:
1358:
1342:
1339:
1338:
1322:
1289:
1285:
1270:
1266:
1264:
1261:
1260:
1244:
1241:
1240:
1224:
1221:
1220:
1197:
1193:
1191:
1188:
1187:
1171:
1168:
1167:
1151:
1148:
1147:
1124:
1120:
1118:
1115:
1114:
1098:
1095:
1094:
1078:
1075:
1074:
1058:
1055:
1054:
1023:
1020:
1019:
1002:
997:
996:
994:
991:
990:
967:
962:
961:
952:
948:
936:
921:
913:
910:
909:
890:
887:
886:
870:
867:
866:
863:bipartite graph
847:
826:
823:
822:
802:
801:
799:
796:
795:
778:
774:
759:
755:
753:
750:
749:
733:
730:
729:
712:
708:
706:
703:
702:
685:
681:
666:
662:
660:
657:
656:
633:
629:
627:
624:
623:
607:
604:
603:
583:
582:
580:
577:
576:
559:
555:
543:
527:
526:
524:
521:
520:
503:
499:
497:
494:
493:
470:
448:
429:
428:
426:
423:
422:
396:
395:
381:
377:
365:
349:
348:
347:
331:
327:
316:
312:
311:
307:
305:
302:
301:
281:
277:
275:
272:
271:
254:
250:
248:
245:
244:
224:
221:
220:
197:
193:
178:
174:
172:
169:
168:
159:
94:for performing
77:
66:
60:
57:
47:Please help to
46:
30:
26:
17:
12:
11:
5:
6753:
6743:
6742:
6737:
6732:
6718:
6717:
6672:
6659:
6642:
6636:
6621:
6608:
6571:
6562:
6549:
6529:
6518:
6515:
6512:
6511:
6466:(20): 200501.
6450:
6432:
6389:
6370:
6350:
6330:
6286:
6253:
6198:
6137:
6118:(1): 195–203.
6102:
6081:(3): 434–448.
6061:
6026:
5965:
5920:
5873:
5828:
5805:
5791:
5769:
5762:
5741:
5703:
5666:
5637:(2): 201–226.
5617:
5616:
5614:
5611:
5599:
5594:
5590:
5586:
5581:
5578:
5575:
5572:
5569:
5566:
5562:
5558:
5553:
5550:
5547:
5542:
5538:
5534:
5529:
5525:
5513:
5512:
5496:
5493:
5490:
5487:
5484:
5479:
5475:
5471:
5468:
5464:
5460:
5457:
5454:
5449:
5445:
5441:
5438:
5435:
5432:
5429:
5426:
5421:
5418:
5415:
5410:
5406:
5393:
5392:
5381:
5378:
5374:
5366:
5362:
5357:
5353:
5350:
5347:
5342:
5339:
5336:
5333:
5330:
5327:
5324:
5321:
5318:
5313:
5309:
5304:
5300:
5295:
5292:
5288:
5284:
5277:
5273:
5268:
5264:
5261:
5258:
5255:
5250:
5246:
5242:
5239:
5236:
5233:
5222:
5221:
5210:
5203:
5199:
5194:
5190:
5185:
5182:
5179:
5176:
5173:
5170:
5167:
5164:
5161:
5156:
5152:
5147:
5143:
5138:
5135:
5132:
5127:
5123:
5119:
5114:
5110:
5106:
5103:
5100:
5097:
5071:
5068:
5065:
5060:
5056:
5052:
5047:
5044:
5041:
5037:
5031:
5028:
5025:
5020:
5016:
5012:
5007:
5004:
5001:
4997:
4990:
4987:
4984:
4979:
4975:
4951:
4948:
4945:
4940:
4936:
4932:
4927:
4924:
4921:
4917:
4911:
4908:
4905:
4900:
4896:
4892:
4887:
4884:
4881:
4877:
4870:
4867:
4864:
4859:
4855:
4828:
4824:
4821:
4818:
4815:
4811:
4807:
4803:
4799:
4796:
4793:
4789:
4784:
4763:
4760:
4757:
4754:
4751:
4748:
4743:
4739:
4724:
4723:
4712:
4709:
4705:
4699:
4695:
4690:
4686:
4681:
4678:
4673:
4669:
4664:
4658:
4655:
4652:
4649:
4646:
4643:
4640:
4637:
4634:
4629:
4625:
4620:
4616:
4611:
4606:
4603:
4599:
4595:
4589:
4583:
4575:
4572:
4565:
4561:
4557:
4553:
4549:
4545:
4541:
4537:
4533:
4528:
4522:
4518:
4515:
4510:
4506:
4502:
4497:
4494:
4491:
4487:
4482:
4479:
4476:
4473:
4470:
4467:
4464:
4461:
4456:
4452:
4448:
4429:
4409:
4404:
4400:
4396:
4393:
4382:
4371:
4368:
4363:
4359:
4355:
4350:
4347:
4342:
4338:
4333:
4327:
4324:
4321:
4318:
4315:
4312:
4309:
4306:
4303:
4298:
4294:
4289:
4285:
4280:
4276:
4272:
4269:
4266:
4263:
4258:
4254:
4250:
4245:
4242:
4239:
4235:
4230:
4227:
4224:
4221:
4218:
4215:
4212:
4209:
4204:
4200:
4196:
4173:
4168:
4164:
4160:
4155:
4151:
4130:
4127:
4124:
4121:
4118:
4098:
4078:
4058:
4038:
4035:
4031:
4027:
4024:
4021:
4001:
3981:
3978:
3974:
3970:
3967:
3964:
3952:
3949:
3907:
3906:
3894:
3891:
3888:
3884:
3878:
3874:
3870:
3867:
3863:
3859:
3854:
3850:
3846:
3843:
3839:
3834:
3830:
3827:
3824:
3821:
3809:of the matrix
3794:
3793:
3782:
3779:
3776:
3773:
3770:
3756:
3755:
3744:
3741:
3736:
3732:
3728:
3725:
3722:
3717:
3713:
3709:
3705:
3701:
3693:
3690:
3674:
3673:
3662:
3659:
3656:
3651:
3647:
3643:
3640:
3637:
3632:
3628:
3621:
3618:
3612:
3609:
3606:
3603:
3598:
3595:
3590:
3587:
3584:
3581:
3578:
3570:
3567:
3528:
3527:
3514:
3510:
3506:
3502:
3499:
3494:
3490:
3486:
3483:
3480:
3475:
3471:
3464:
3461:
3455:
3452:
3449:
3446:
3441:
3438:
3435:
3431:
3425:
3422:
3417:
3414:
3409:
3405:
3401:
3398:
3376:
3373:
3362:graph coloring
3358:satisfiability
3356:problems like
3328:
3325:
3320:
3319:
3308:
3305:
3301:
3297:
3294:
3291:
3288:
3285:
3281:
3277:
3274:
3268:
3263:
3259:
3256:
3252:
3248:
3245:
3242:
3238:
3234:
3231:
3225:
3220:
3216:
3213:
3210:
3207:
3204:
3201:
3187:
3186:
3175:
3172:
3167:
3163:
3159:
3154:
3150:
3142:
3138:
3133:
3129:
3126:
3123:
3120:
3117:
3113:
3109:
3106:
3088:
3087:
3076:
3071:
3067:
3063:
3058:
3054:
3046:
3042:
3037:
3031:
3028:
3023:
3020:
3016:
3012:
3009:
2987:thermodynamics
2978:
2975:
2956:relative error
2941:
2940:
2929:
2926:
2922:
2918:
2915:
2909:
2903:
2900:
2897:
2892:
2859:
2842:
2839:
2788:
2785:
2754:
2751:
2743:
2742:
2731:
2728:
2723:
2719:
2715:
2710:
2707:
2704:
2700:
2694:
2691:
2688:
2685:
2682:
2679:
2675:
2671:
2666:
2661:
2656:
2651:
2647:
2643:
2640:
2635:
2630:
2625:
2618:
2614:
2609:
2594:
2593:
2582:
2579:
2574:
2570:
2566:
2561:
2558:
2555:
2551:
2545:
2542:
2539:
2536:
2533:
2530:
2526:
2522:
2519:
2514:
2510:
2506:
2499:
2495:
2490:
2459:
2458:
2444:
2440:
2436:
2431:
2427:
2406:
2401:
2397:
2393:
2388:
2384:
2380:
2377:
2372:
2368:
2364:
2359:
2356:
2353:
2349:
2328:
2325:
2322:
2319:
2316:
2313:
2310:
2307:
2287:
2267:
2264:
2261:
2258:
2238:
2235:
2232:
2229:
2226:
2223:
2218:
2214:
2192:
2188:
2184:
2178:
2174:
2169:
2165:
2160:
2157:
2152:
2148:
2143:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2108:
2104:
2099:
2095:
2091:
2087:
2082:
2077:
2072:
2068:
2063:
2055:
2051:
2047:
2043:
2039:
2035:
2031:
2027:
2023:
2018:
2012:
2008:
2005:
2000:
1996:
1992:
1987:
1984:
1981:
1977:
1956:
1936:
1916:
1895:
1891:
1888:
1885:
1882:
1879:
1876:
1873:
1868:
1865:
1862:
1858:
1845:
1844:
1832:
1829:
1826:
1823:
1820:
1800:
1795:
1791:
1787:
1782:
1779:
1776:
1772:
1762:is empty then
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1710:
1690:
1687:
1684:
1681:
1661:
1658:
1655:
1652:
1649:
1646:
1641:
1637:
1616:
1611:
1607:
1603:
1598:
1595:
1590:
1586:
1581:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1554:
1551:
1546:
1542:
1537:
1533:
1530:
1525:
1521:
1517:
1512:
1509:
1506:
1502:
1492:is defined by
1481:
1461:
1440:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1413:
1410:
1407:
1403:
1378:
1375:
1372:
1369:
1366:
1346:
1325:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1298:
1295:
1292:
1288:
1284:
1279:
1276:
1273:
1269:
1248:
1228:
1206:
1203:
1200:
1196:
1175:
1155:
1133:
1130:
1127:
1123:
1102:
1082:
1062:
1027:
1005:
1000:
987:
986:
975:
970:
965:
960:
955:
951:
945:
942:
939:
935:
931:
928:
924:
920:
917:
894:
874:
846:
843:
830:
809:
805:
781:
777:
773:
770:
767:
762:
758:
737:
715:
711:
688:
684:
680:
677:
674:
669:
665:
636:
632:
611:
590:
586:
562:
558:
554:
550:
546:
542:
538:
534:
530:
506:
502:
481:
477:
473:
469:
465:
462:
459:
455:
451:
447:
443:
440:
436:
432:
419:
418:
407:
403:
399:
394:
391:
384:
380:
376:
372:
368:
364:
360:
356:
352:
346:
342:
339:
334:
330:
326:
319:
315:
310:
284:
280:
257:
253:
228:
200:
196:
192:
189:
186:
181:
177:
158:
155:
136:satisfiability
79:
78:
33:
31:
24:
15:
9:
6:
4:
3:
2:
6752:
6741:
6740:Coding theory
6738:
6736:
6733:
6731:
6728:
6727:
6725:
6714:
6710:
6706:
6702:
6697:
6696:10.1.1.3.5650
6692:
6688:
6684:
6683:
6678:
6673:
6662:
6656:
6652:
6648:
6643:
6639:
6633:
6629:
6628:
6622:
6619:
6618:
6617:New Scientist
6613:
6609:
6605:
6601:
6597:
6593:
6589:
6585:
6581:
6577:
6572:
6569:
6568:
6563:
6552:
6546:
6542:
6535:
6530:
6527:
6526:
6521:
6520:
6507:
6503:
6499:
6495:
6491:
6487:
6483:
6479:
6474:
6469:
6465:
6461:
6454:
6443:
6436:
6428:
6424:
6420:
6416:
6412:
6408:
6404:
6400:
6393:
6387:
6383:
6380:
6374:
6368:
6364:
6361:
6354:
6348:
6344:
6341:
6334:
6326:
6322:
6318:
6314:
6310:
6306:
6302:
6299:
6298:
6290:
6274:
6270:
6269:
6264:
6257:
6249:
6245:
6241:
6237:
6233:
6229:
6224:
6223:10.1.1.44.794
6219:
6215:
6211:
6210:
6202:
6194:
6190:
6186:
6182:
6178:
6174:
6170:
6166:
6161:
6156:
6152:
6148:
6141:
6133:
6129:
6125:
6121:
6117:
6113:
6106:
6097:
6092:
6088:
6084:
6080:
6076:
6072:
6065:
6057:
6053:
6049:
6045:
6041:
6037:
6030:
6015:
6011:
6007:
6003:
5998:
5997:10.1.1.3.5650
5993:
5989:
5985:
5984:
5979:
5972:
5970:
5961:
5957:
5953:
5949:
5945:
5941:
5937:
5933:
5932:
5924:
5916:
5912:
5908:
5904:
5899:
5894:
5890:
5886:
5885:
5877:
5869:
5865:
5861:
5857:
5853:
5849:
5845:
5841:
5840:
5832:
5824:
5820:
5816:
5809:
5794:
5788:
5784:
5780:
5773:
5765:
5759:
5755:
5751:
5745:
5729:
5725:
5718:
5714:
5711:Kim, Jin H.;
5707:
5691:
5687:
5680:
5676:
5670:
5662:
5658:
5654:
5650:
5645:
5640:
5636:
5632:
5625:
5623:
5618:
5610:
5592:
5588:
5576:
5570:
5567:
5564:
5560:
5556:
5548:
5540:
5536:
5532:
5527:
5523:
5494:
5485:
5482:
5477:
5473:
5466:
5462:
5455:
5452:
5447:
5443:
5436:
5430:
5427:
5424:
5416:
5408:
5404:
5395:
5394:
5376:
5372:
5364:
5360:
5355:
5348:
5345:
5337:
5325:
5319:
5316:
5311:
5307:
5302:
5298:
5293:
5290:
5286:
5282:
5275:
5271:
5262:
5259:
5253:
5248:
5244:
5240:
5237:
5231:
5224:
5223:
5201:
5197:
5192:
5180:
5168:
5162:
5159:
5154:
5150:
5145:
5141:
5133:
5125:
5121:
5117:
5112:
5108:
5104:
5101:
5095:
5088:
5087:
5086:
5066:
5063:
5058:
5054:
5045:
5039:
5035:
5026:
5023:
5018:
5014:
5005:
4999:
4995:
4988:
4985:
4982:
4977:
4973:
4946:
4943:
4938:
4934:
4925:
4919:
4915:
4906:
4903:
4898:
4894:
4885:
4879:
4875:
4868:
4865:
4862:
4857:
4853:
4843:
4819:
4813:
4805:
4794:
4782:
4758:
4755:
4752:
4746:
4741:
4737:
4727:
4710:
4703:
4697:
4693:
4688:
4679:
4671:
4667:
4662:
4653:
4641:
4635:
4632:
4627:
4623:
4618:
4604:
4597:
4593:
4570:
4563:
4559:
4555:
4551:
4547:
4543:
4539:
4535:
4531:
4520:
4516:
4508:
4504:
4495:
4489:
4485:
4480:
4474:
4468:
4465:
4462:
4459:
4454:
4450:
4427:
4402:
4398:
4391:
4383:
4369:
4361:
4357:
4348:
4340:
4336:
4331:
4322:
4310:
4304:
4301:
4296:
4292:
4287:
4278:
4274:
4267:
4264:
4256:
4252:
4243:
4237:
4233:
4228:
4222:
4216:
4213:
4210:
4207:
4202:
4198:
4187:
4186:
4185:
4166:
4162:
4153:
4149:
4128:
4125:
4122:
4119:
4116:
4096:
4076:
4056:
4033:
4025:
4019:
3999:
3976:
3968:
3962:
3948:
3947:
3943:
3939:
3935:
3931:
3927:
3923:
3918:
3916:
3912:
3892:
3889:
3876:
3872:
3868:
3865:
3861:
3857:
3852:
3848:
3844:
3841:
3837:
3828:
3825:
3819:
3812:
3811:
3810:
3808:
3804:
3800:
3780:
3777:
3774:
3771:
3768:
3761:
3760:
3759:
3742:
3739:
3734:
3730:
3726:
3723:
3720:
3715:
3711:
3707:
3703:
3699:
3691:
3688:
3679:
3678:
3677:
3660:
3654:
3649:
3645:
3641:
3638:
3635:
3630:
3626:
3619:
3616:
3610:
3604:
3601:
3596:
3593:
3588:
3582:
3576:
3568:
3565:
3556:
3555:
3554:
3552:
3547:
3545:
3541:
3537:
3533:
3512:
3508:
3504:
3497:
3492:
3488:
3484:
3481:
3478:
3473:
3469:
3462:
3459:
3453:
3447:
3444:
3439:
3436:
3433:
3429:
3423:
3420:
3415:
3407:
3403:
3396:
3389:
3388:
3387:
3384:
3382:
3372:
3370:
3365:
3363:
3359:
3355:
3351:
3345:
3343:
3339:
3335:
3324:
3306:
3292:
3289:
3286:
3272:
3261:
3257:
3243:
3229:
3218:
3214:
3211:
3208:
3205:
3202:
3199:
3192:
3191:
3190:
3173:
3165:
3161:
3152:
3148:
3140:
3136:
3131:
3127:
3124:
3121:
3118:
3104:
3097:
3096:
3095:
3093:
3069:
3065:
3056:
3052:
3044:
3040:
3035:
3029:
3026:
3021:
3007:
3000:
2999:
2998:
2996:
2992:
2988:
2984:
2974:
2972:
2967:
2965:
2961:
2957:
2953:
2949:
2944:
2927:
2913:
2898:
2895:
2890:
2878:
2877:
2876:
2874:
2848:
2838:
2836:
2831:
2829:
2825:
2820:
2818:
2812:
2811:of the tree.
2810:
2806:
2802:
2798:
2794:
2784:
2781:
2777:
2775:
2771:
2766:
2764:
2760:
2750:
2748:
2729:
2721:
2717:
2708:
2702:
2698:
2689:
2683:
2680:
2677:
2673:
2664:
2649:
2645:
2641:
2633:
2616:
2612:
2607:
2599:
2598:
2597:
2580:
2572:
2568:
2559:
2553:
2549:
2540:
2534:
2531:
2528:
2524:
2520:
2512:
2508:
2497:
2493:
2488:
2480:
2479:
2478:
2475:
2471:
2469:
2465:
2442:
2438:
2434:
2429:
2425:
2399:
2395:
2386:
2382:
2378:
2370:
2366:
2357:
2351:
2347:
2323:
2311:
2305:
2285:
2262:
2256:
2233:
2227:
2224:
2221:
2216:
2212:
2190:
2182:
2176:
2172:
2167:
2158:
2150:
2146:
2141:
2132:
2120:
2114:
2111:
2106:
2102:
2097:
2089:
2085:
2070:
2066:
2061:
2053:
2049:
2045:
2041:
2037:
2033:
2029:
2025:
2021:
2010:
2006:
1998:
1994:
1985:
1979:
1975:
1954:
1934:
1914:
1883:
1877:
1874:
1871:
1866:
1860:
1856:
1847:
1846:
1827:
1821:
1818:
1793:
1789:
1780:
1774:
1770:
1746:
1734:
1728:
1708:
1685:
1679:
1656:
1650:
1647:
1644:
1639:
1635:
1609:
1605:
1596:
1588:
1584:
1579:
1570:
1558:
1552:
1549:
1544:
1540:
1535:
1531:
1523:
1519:
1510:
1504:
1500:
1479:
1459:
1428:
1422:
1419:
1416:
1411:
1405:
1401:
1392:
1391:
1390:
1373:
1367:
1364:
1344:
1313:
1307:
1304:
1301:
1296:
1290:
1286:
1282:
1277:
1271:
1267:
1246:
1226:
1204:
1198:
1194:
1173:
1153:
1131:
1125:
1121:
1100:
1080:
1060:
1052:
1047:
1045:
1041:
1025:
1003:
968:
953:
949:
943:
940:
937:
933:
929:
915:
908:
907:
906:
892:
872:
864:
860:
856:
852:
842:
828:
807:
779:
775:
771:
768:
765:
760:
756:
735:
713:
709:
686:
682:
678:
675:
672:
667:
663:
655:
650:
634:
630:
609:
588:
560:
556:
552:
548:
544:
540:
536:
532:
504:
500:
475:
471:
467:
463:
460:
457:
453:
449:
445:
438:
434:
401:
389:
382:
378:
374:
370:
366:
362:
358:
354:
344:
340:
332:
328:
317:
313:
308:
300:
299:
298:
282:
278:
255:
251:
242:
226:
219:
216:
198:
194:
190:
187:
184:
179:
175:
167:
164:
154:
152:
148:
144:
139:
137:
133:
129:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
75:
72:
64:
54:
50:
44:
43:
37:
32:
23:
22:
19:
6686:
6680:
6664:. Retrieved
6650:
6626:
6615:
6582:(1): 28–41.
6579:
6575:
6566:
6554:. Retrieved
6540:
6524:
6463:
6459:
6453:
6435:
6405:(4): 34–36.
6402:
6398:
6392:
6373:
6353:
6333:
6300:
6295:
6289:
6277:. Retrieved
6272:
6266:
6256:
6213:
6207:
6201:
6150:
6146:
6140:
6115:
6111:
6105:
6078:
6074:
6064:
6039:
6035:
6029:
6017:. Retrieved
5987:
5981:
5938:(1): 28–41.
5935:
5929:
5923:
5888:
5882:
5876:
5843:
5837:
5831:
5814:
5808:
5796:. Retrieved
5782:
5772:
5753:
5750:Pearl, Judea
5744:
5732:. Retrieved
5723:
5713:Pearl, Judea
5706:
5694:. Retrieved
5685:
5675:Pearl, Judea
5669:
5634:
5630:
5514:
4844:
4728:
4725:
3954:
3933:
3929:
3925:
3921:
3919:
3914:
3910:
3908:
3798:
3795:
3757:
3675:
3548:
3543:
3531:
3529:
3385:
3378:
3366:
3346:
3333:
3330:
3321:
3188:
3089:
2990:
2980:
2968:
2945:
2942:
2844:
2832:
2821:
2813:
2800:
2790:
2782:
2778:
2773:
2769:
2767:
2759:factor graph
2756:
2744:
2595:
2476:
2472:
2467:
2463:
2460:
1050:
1048:
988:
885:and factors
859:factor graph
848:
651:
420:
160:
140:
87:
83:
82:
67:
58:
39:
18:
6275:: 2031–2064
5846:(1): 1–41.
3354:NP-complete
2983:free energy
2964:NP-complete
2960:#P-complete
2817:EXIT charts
143:Judea Pearl
132:free energy
128:turbo codes
53:introducing
6724:Categories
6556:2 December
6473:1811.07835
5898:cs/0504030
5644:cs/0212002
5613:References
1848:A message
1393:A message
1357:, denoted
157:Motivation
102:, such as
61:April 2009
36:references
6691:CiteSeerX
6490:0031-9007
6419:0163-5700
6218:CiteSeerX
6185:0305-4470
5992:CiteSeerX
5568:∈
5561:∑
5431:
5365:∗
5349:
5332:∖
5317:∈
5312:∗
5303:∏
5299:
5291:−
5260:−
5235:→
5202:∗
5175:∖
5160:∈
5155:∗
5146:∑
5099:→
5043:→
5003:→
4989:
4923:→
4883:→
4869:
4747:∈
4698:∗
4677:→
4672:∗
4663:μ
4648:∖
4633:∈
4628:∗
4619:∏
4571:δ
4521:∑
4493:→
4486:μ
4460:∈
4447:∀
4346:→
4341:∗
4332:μ
4317:∖
4302:∈
4297:∗
4288:∏
4241:→
4234:μ
4208:∈
4195:∀
3866:−
3842:−
3829:−
3820:ρ
3727:−
3611:−
3605:
3454:−
3448:
3437:≠
3430:∫
3290:
3262:∑
3219:∑
3209:−
3132:∏
3128:
3122:−
3036:∏
2948:inference
2899:
2891:
2706:→
2699:μ
2681:∈
2674:∏
2642:∝
2557:→
2550:μ
2532:∈
2525:∏
2521:∝
2466:, or the
2355:→
2348:μ
2318:∖
2228:
2222:∈
2177:∗
2156:→
2151:∗
2142:μ
2127:∖
2112:∈
2107:∗
2098:∏
2011:∑
1983:→
1976:μ
1890:→
1878:
1864:→
1857:μ
1822:
1778:→
1771:μ
1741:∖
1651:
1645:∈
1594:→
1589:∗
1580:μ
1565:∖
1550:∈
1545:∗
1536:∏
1508:→
1501:μ
1435:→
1423:
1409:→
1402:μ
1368:
1320:→
1308:
1294:→
1287:μ
1275:→
1268:μ
1202:→
1195:μ
1129:→
1122:μ
941:∈
934:∏
772:×
766:≈
676:…
461:…
345:∑
188:…
151:polytrees
96:inference
92:algorithm
6713:52835993
6666:30 March
6506:53959182
6498:31172756
6427:10570465
6382:Archived
6363:Archived
6343:Archived
6325:12055229
6279:28 March
6248:10624764
6240:11570995
6019:28 March
6014:52835993
5868:15402308
5860:10636932
5798:30 March
5752:(1988).
5734:20 March
5715:(1983).
5696:28 March
5677:(1982).
4704:′
4598:′
4578:syndrome
4552:′
4536:′
4049:, where
2809:diameter
2249:, where
2183:′
2090:′
2042:′
2026:′
1672:, where
1051:messages
808:′
589:′
549:′
533:′
476:′
454:′
435:′
402:′
371:′
355:′
163:discrete
6604:7722934
6584:Bibcode
6305:Bibcode
6165:Bibcode
6120:Bibcode
6083:Bibcode
6044:Bibcode
5960:7722934
5940:Bibcode
5661:6601396
5085:, then
4384:where
3913:= diag(
3338:Kikuchi
3334:regions
2993:be the
2952:NP-hard
2873:arg max
2793:acyclic
243:of the
49:improve
6711:
6693:
6657:
6634:
6602:
6547:
6504:
6496:
6488:
6425:
6417:
6323:
6246:
6238:
6220:
6191:
6183:
6012:
5994:
5958:
5913:
5866:
5858:
5789:
5760:
5659:
5396:where
3928:where
3909:where
3697:
3574:
3566:argmax
3542:) and
2989:. Let
2805:cycles
2797:graphs
1038:. Any
989:where
728:using
602:whose
421:where
38:, but
6709:S2CID
6600:S2CID
6537:(PDF)
6502:S2CID
6468:arXiv
6445:(PDF)
6423:S2CID
6321:S2CID
6244:S2CID
6189:S2CID
6155:arXiv
6010:S2CID
5956:S2CID
5915:57228
5911:S2CID
5893:arXiv
5864:S2CID
5720:(PDF)
5682:(PDF)
5657:S2CID
5639:arXiv
5499:const
2761:is a
2298:. If
1721:. If
1219:from
1146:from
215:joint
213:with
147:trees
6668:2009
6655:ISBN
6632:ISBN
6558:2023
6545:ISBN
6494:PMID
6486:ISSN
6415:ISSN
6281:2009
6236:PMID
6181:ISSN
6021:2009
5856:PMID
5800:2009
5787:ISBN
5758:ISBN
5736:2016
5698:2009
5346:tanh
5287:tanh
4089:and
3890:<
3360:and
2826:and
2774:leaf
2770:root
2763:tree
2204:for
1627:for
853:and
769:6.34
118:and
106:and
6701:doi
6614:",
6592:doi
6478:doi
6464:122
6407:doi
6313:doi
6228:doi
6193:942
6173:doi
6128:doi
6091:doi
6052:doi
6002:doi
5948:doi
5903:doi
5848:doi
5819:doi
5649:doi
5428:log
4986:log
4866:log
3801:is
3689:min
3602:exp
3551:MAP
3445:exp
3287:log
3125:log
2985:in
2902:max
2896:arg
2225:Dom
1875:Dom
1819:Dom
1648:Dom
1420:Dom
1365:Dom
1305:Dom
1239:to
1166:to
1042:or
687:100
98:on
6726::
6707:.
6699:.
6687:51
6685:.
6679:.
6598:.
6590:.
6580:21
6578:.
6539:.
6500:.
6492:.
6484:.
6476:.
6462:.
6421:.
6413:.
6403:37
6401:.
6319:.
6311:.
6301:63
6271:.
6265:.
6242:.
6234:.
6226:.
6214:13
6212:.
6187:.
6179:.
6171:.
6163:.
6151:38
6149:.
6126:.
6116:47
6114:.
6089:.
6079:21
6077:.
6073:.
6050:.
6040:81
6038:.
6008:.
6000:.
5988:51
5986:.
5980:.
5968:^
5954:.
5946:.
5936:21
5934:.
5909:.
5901:.
5889:53
5887:.
5862:.
5854:.
5844:12
5842:.
5726:.
5722:.
5688:.
5684:.
5655:.
5647:.
5635:27
5633:.
5621:^
4965:,
3940:,
3924:=
3922:Ax
3364:.
3344:.
2966:.
2875::
2830:.
2776:.
2749:.
2470:.
780:29
776:10
761:99
649:.
138:.
130:,
126:,
6715:.
6703::
6670:.
6640:.
6606:.
6594::
6586::
6570:.
6560:.
6508:.
6480::
6470::
6447:.
6429:.
6409::
6327:.
6315::
6307::
6283:.
6273:7
6250:.
6230::
6195:.
6175::
6167::
6157::
6134:.
6130::
6122::
6099:.
6093::
6085::
6058:.
6054::
6046::
6023:.
6004::
5962:.
5950::
5942::
5917:.
5905::
5895::
5870:.
5850::
5825:.
5821::
5802:.
5766:.
5738:.
5700:.
5663:.
5651::
5641::
5598:)
5593:a
5589:L
5585:(
5580:)
5577:v
5574:(
5571:N
5565:a
5557:+
5552:)
5549:0
5546:(
5541:v
5537:l
5533:=
5528:v
5524:l
5495:=
5492:)
5489:)
5486:1
5483:=
5478:v
5474:x
5470:(
5467:P
5463:/
5459:)
5456:0
5453:=
5448:v
5444:x
5440:(
5437:P
5434:(
5425:=
5420:)
5417:0
5414:(
5409:v
5405:l
5380:)
5377:2
5373:/
5361:v
5356:l
5352:(
5341:}
5338:v
5335:{
5329:)
5326:a
5323:(
5320:N
5308:v
5294:1
5283:2
5276:a
5272:s
5267:)
5263:1
5257:(
5254:=
5249:a
5245:L
5241::
5238:v
5232:a
5209:)
5198:a
5193:L
5189:(
5184:}
5181:a
5178:{
5172:)
5169:v
5166:(
5163:N
5151:a
5142:+
5137:)
5134:0
5131:(
5126:v
5122:l
5118:=
5113:v
5109:l
5105::
5102:a
5096:v
5070:)
5067:1
5064:=
5059:v
5055:x
5051:(
5046:v
5040:a
5036:u
5030:)
5027:0
5024:=
5019:v
5015:x
5011:(
5006:v
5000:a
4996:u
4983:=
4978:a
4974:L
4950:)
4947:1
4944:=
4939:v
4935:x
4931:(
4926:a
4920:v
4916:u
4910:)
4907:0
4904:=
4899:v
4895:x
4891:(
4886:a
4880:v
4876:u
4863:=
4858:v
4854:l
4827:|
4823:)
4820:v
4817:(
4814:N
4810:|
4806:+
4802:|
4798:}
4795:v
4792:{
4788:|
4783:2
4762:}
4759:1
4756:,
4753:0
4750:{
4742:i
4738:x
4711:.
4708:)
4694:v
4689:x
4685:(
4680:a
4668:v
4657:}
4654:v
4651:{
4645:)
4642:a
4639:(
4636:N
4624:v
4615:)
4610:s
4605:=
4602:)
4594:v
4588:x
4582:(
4574:(
4564:v
4560:x
4556:=
4548:v
4544:x
4540::
4532:a
4527:x
4517:=
4514:)
4509:v
4505:x
4501:(
4496:v
4490:a
4481:,
4478:)
4475:v
4472:(
4469:m
4466:o
4463:D
4455:v
4451:x
4428:v
4408:)
4403:v
4399:X
4395:(
4392:P
4370:.
4367:)
4362:v
4358:x
4354:(
4349:v
4337:a
4326:}
4323:a
4320:{
4314:)
4311:v
4308:(
4305:N
4293:a
4284:)
4279:v
4275:X
4271:(
4268:P
4265:=
4262:)
4257:v
4253:x
4249:(
4244:a
4238:v
4229:,
4226:)
4223:v
4220:(
4217:m
4214:o
4211:D
4203:v
4199:x
4172:)
4167:a
4163:X
4159:(
4154:a
4150:f
4129:e
4126:+
4123:X
4120:=
4117:x
4097:e
4077:X
4057:s
4037:)
4034:s
4030:|
4026:e
4023:(
4020:P
4000:X
3980:)
3977:X
3973:|
3969:x
3966:(
3963:P
3934:b
3930:A
3926:b
3915:A
3911:D
3893:1
3887:)
3883:|
3877:2
3873:/
3869:1
3862:D
3858:A
3853:2
3849:/
3845:1
3838:D
3833:|
3826:I
3823:(
3799:A
3781:.
3778:b
3775:=
3772:x
3769:A
3743:.
3740:x
3735:T
3731:b
3724:x
3721:A
3716:T
3712:x
3708:2
3704:/
3700:1
3692:x
3661:.
3658:)
3655:x
3650:T
3646:b
3642:+
3639:x
3636:A
3631:T
3627:x
3620:2
3617:1
3608:(
3597:Z
3594:1
3589:=
3586:)
3583:x
3580:(
3577:P
3569:x
3544:b
3532:A
3513:j
3509:x
3505:d
3501:)
3498:x
3493:T
3489:b
3485:+
3482:x
3479:A
3474:T
3470:x
3463:2
3460:1
3451:(
3440:i
3434:j
3424:Z
3421:1
3416:=
3413:)
3408:i
3404:x
3400:(
3397:P
3307:.
3304:)
3300:X
3296:(
3293:P
3284:)
3280:X
3276:(
3273:P
3267:X
3258:+
3255:)
3251:X
3247:(
3244:E
3241:)
3237:X
3233:(
3230:P
3224:X
3215:=
3212:H
3206:U
3203:=
3200:F
3174:.
3171:)
3166:j
3162:x
3158:(
3153:j
3149:f
3141:j
3137:f
3119:=
3116:)
3112:X
3108:(
3105:E
3075:)
3070:j
3066:x
3062:(
3057:j
3053:f
3045:j
3041:f
3030:Z
3027:1
3022:=
3019:)
3015:X
3011:(
3008:P
2991:Z
2928:.
2925:)
2921:x
2917:(
2914:g
2908:x
2887:*
2858:x
2730:.
2727:)
2722:v
2718:x
2714:(
2709:a
2703:v
2693:)
2690:a
2687:(
2684:N
2678:v
2670:)
2665:a
2660:x
2655:(
2650:a
2646:f
2639:)
2634:a
2629:x
2624:(
2617:a
2613:X
2608:p
2581:.
2578:)
2573:v
2569:x
2565:(
2560:v
2554:a
2544:)
2541:v
2538:(
2535:N
2529:a
2518:)
2513:v
2509:x
2505:(
2498:v
2494:X
2489:p
2457:.
2443:a
2439:x
2435:=
2430:v
2426:x
2405:)
2400:v
2396:x
2392:(
2387:a
2383:f
2379:=
2376:)
2371:v
2367:x
2363:(
2358:v
2352:a
2327:}
2324:v
2321:{
2315:)
2312:a
2309:(
2306:N
2286:a
2266:)
2263:a
2260:(
2257:N
2237:)
2234:v
2231:(
2217:v
2213:x
2191:)
2187:)
2173:v
2168:x
2164:(
2159:a
2147:v
2136:}
2133:v
2130:{
2124:)
2121:a
2118:(
2115:N
2103:v
2094:)
2086:a
2081:x
2076:(
2071:a
2067:f
2062:(
2054:v
2050:x
2046:=
2038:v
2034:x
2030::
2022:a
2017:x
2007:=
2004:)
1999:v
1995:x
1991:(
1986:v
1980:a
1967:,
1955:v
1935:v
1915:a
1894:R
1887:)
1884:v
1881:(
1872::
1867:v
1861:a
1843:.
1831:)
1828:v
1825:(
1799:)
1794:v
1790:x
1786:(
1781:a
1775:v
1750:}
1747:a
1744:{
1738:)
1735:v
1732:(
1729:N
1709:v
1689:)
1686:v
1683:(
1680:N
1660:)
1657:v
1654:(
1640:v
1636:x
1615:)
1610:v
1606:x
1602:(
1597:v
1585:a
1574:}
1571:a
1568:{
1562:)
1559:v
1556:(
1553:N
1541:a
1532:=
1529:)
1524:v
1520:x
1516:(
1511:a
1505:v
1480:a
1460:v
1439:R
1432:)
1429:v
1426:(
1417::
1412:a
1406:v
1377:)
1374:v
1371:(
1345:v
1324:R
1317:)
1314:v
1311:(
1302::
1297:v
1291:a
1283:,
1278:a
1272:v
1247:v
1227:a
1205:v
1199:a
1174:a
1154:v
1132:a
1126:v
1101:v
1081:a
1061:v
1026:a
1004:a
999:x
974:)
969:a
964:x
959:(
954:a
950:f
944:F
938:a
930:=
927:)
923:x
919:(
916:p
893:F
873:V
829:p
804:x
757:2
736:p
714:i
710:X
683:X
679:,
673:,
668:1
664:X
635:i
631:x
610:i
585:x
561:i
557:x
553:=
545:i
541:x
537::
529:x
505:i
501:X
480:)
472:n
468:x
464:,
458:,
450:1
446:x
442:(
439:=
431:x
406:)
398:x
393:(
390:p
383:i
379:x
375:=
367:i
363:x
359::
351:x
341:=
338:)
333:i
329:x
325:(
318:i
314:X
309:p
283:i
279:X
256:i
252:X
227:p
199:n
195:X
191:,
185:,
180:1
176:X
74:)
68:(
63:)
59:(
45:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.