{'fraction_non_alphanumeric': 0.02687976752633491, 'fraction_numerical': 0.0032691609153650564, 'mean_word_length': 5.611044417767107, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exact Inference on Graphical Models : The Junction Tree Algorithm

Information processing in sensor networks, with many small processors, demands a theory of computation that allows the minimization of processing effort, and the distribution of this effort throughout the network. Graphical model theory provides a probabilistic theory of computation that explicitly addresses complexity and decentralization for optimizing network computation. The junction tree algorithm, for decentralized inference on graphical probability models, can be instantiated in a variety of applications useful for wireless sensor networks, including: sensor validation and fusion; data compression and channel coding; expert systems, with decentralized data structures, and efficient local queries; pattern classification, and machine learning. Graphical models for these applications are sketched, and a model of dynamic sensor validation and fusion is presented in more depth, to illustrate the junction tree algorithm. 1 A Model of Network Computation Graphical model theory is a marriage of probability and graph theory that uses network graphs (with nodes and edges) to represent probability models. Probabilistic propositions are at least as expressive as logical propositions (containing them as extremal cases); the language of probability therefore includes the languages of all Turing computers, with probabilistic conditioning inclusive of logical implication. While Boolean propositions may only be true or false, probabilistic propositions may also assume any intermediate value. A probabilistic theory of analog computation may be more expressive than the Turing model. Representing probability models as graphs has several advantages for wireless sensor networks. Inference, the essential probabilistic operation, is described as an algorithm directly on the probability graph, or on a graph derived from it. The probability graph contains the network hardware graph, so a graphical description of the algorithm facilitates its hardware implementation. Furthermore, the algorithm for exact inference on network graphs, the junction tree algorithm, has the following properties: it is minimum complexity; it is maximally decentralized (requiring only “local” information, in a well-defined sense); and it explicitly provides a communications protocol that specifies the information flows between pairs of nodes, and the order in which these information flows must occur. These properties are useful in network implementations. Broadly, there are three steps to using a graphical model: (1) defining the model; (2) constructing the inference engine; and, (3) using the inference engine. The first step entails: specifying the random variables, as nodes in the graphical model, and assigning probability distributions to these nodes; and, specifying the dependencies between the variables, as edges in the graphical model. This step is described in section 2, with a static sensor fusion example. The second and third steps, constructing and using an inference engine, are accomplished by the junction tree algorithm. The junction tree algorithm performs decentralized, efficient, exact Bayesian inference on any graphical model. Furthermore, the junction tree algorithm can be utilized as a subroutine for higher-order inference – for estimating probability distributions, and for determining structure in graphical models, when these are not known. The junction tree algorithm therefore provides a good introduction to graphical model theory, and is described in section 3 [3, 7-8, 10]. The claim that graphical models provide an expressive theory of network computation is given substantial support in section 4, which provides a variety of graphical models for wireless sensor networks. The suite of applications described is diverse and comprehensive, including: sensor validation and fusion; data compression and channel coding; distributed expert systems; pattern classification, and machine learning [4]. Section 5 develops the examples of graphical models for sensor fusion and validation in greater depth, with the objectives of illustrating the desirable properties of the junction tree algorithm, and describing decentralized network implementations. Despite the computational advantages of the junction tree algorithm, exact inference can still be intractable for many models. Section 6 introduces faster algorithms for approximate inference, and extensions of graphical models and the junction tree algorithm to decision and game networks. 2 Graphical Models Represent How Joint Probability Distributions Factor Constructing a graphical model G = (X, E) entails assigning nodes X to random variables, with a joint probability distribution function p(X), and including edges E to represent probabilistic dependencies between the nodes. If the edges are directed (and the graph has no cycles), the graphical model is known as a Bayesian network. In this type of graphical model, the joint pdf can be factored ( ) ( ) ( ) | X p X X ∈ = ∏ X p X π (1) into a product of conditional distributions, where each node is conditioned on its parent nodes π (X). Equivalently, the edges embody conditional independence assumptions on the local conditional probability distributions, namely that in Bayes nets, each node is conditionally independent of all others, given its parents. Consider the following sensor fusion example. The directed graph in figure 1 represents M sensors Sm observing the same object O.