Factor Graphs and Comparing Graphical Model Types

Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science 6.438 Algorithms for Inference Fall 2014 4 Factor graphs and Comparing Graphical Model Types We now introduce a third type of graphical model. Beforehand, let us summarize some key perspectives on our first two. First, for some ordering of variables, we can write any probability distribution as px (x1 , . . . , xn ) = px1 (x1 )px2 |x1 (x2 , x1 ) · · · pxn |x1 ,...,xn−1 (xn |x1 , . . . , xn−1 ), which can be expressed as a fully connected directed graphical model. When the conditional distributions involved do not depend on all the indicated conditioning variables, then some of the edges in the directed graphical model can be removed. This reduces the complexity of inference, since the associated conditional probability tables have a more compact description. By contrast, undirected graphical models express distributions of the form px (x1 , . . . , xn ) = 1� Φc (xc ), Z c∈C where the potential functions Φc are non-negative and C is the set of maximal cliques on an undirected graph G. Remember that the Hammersley-Clifford theorem says that any distribution that factors in this way satisfies the Markov property on the graph and conversely that if p is strictly positive and satisfies the Markov property for G then it factors as above. Evidently, any distribution can be expressed using fully connected undirected graphical model, since this corresponds to a single potential involving all the variables—i.e., a joint probability distribution. Undirected graphical models efficiently represent conditional independencies in the distribution of interest, which are expressed by the removal of edges, and which similarly reduces the complexity of inference. 4.1 Factor graphs Factor graphs are capable of capturing structure that the traditional directed and undirected graphical models above are not capable of capturing. A factor graph consists of a vector of random variables x = (x1 , . . . , xN ) and a graph G = (V, E, F), which in addition to normal nodes also has factor nodes F. Furthermore, the graph is constrained to be a bipartite graph between variable nodes and factor nodes. The joint probability distribution associated to a factor graph is given by m 1� p(x1 , . . . , xN ) = fj (xfj ). Z j=1 x1 f1 fN xN Figure 1: A general factor graph. For example, in Figure 1, f1 is a function of x1 and x2 . What constraints are imposed on the factors? The factors must be non­ negative, but otherwise we’re free to choose them. We could of course roll the partition function Z into one of the factors and that would constrain one of the factors. The factor graph is not constrained to have factors only for maximal cliques, so we can more explicitly represent the factorization of the joint probability distribution. It is very easy to encode certain kinds of (especially algebraic) constraints in the factor graph. One example is the Hamming code example from the first day of class, which you will see more of later in the subject. As a more basic example, consider the following. Example 1. Suppose we have random variables representing taxes (x1 ), social secu­ rity (x2 ), medicare (x3 ), and foreign aid (x4 ) with constraints x1 x2 x3 x4 ≤3 ≤ 0.5 ≤ 0.25 ≤ 0.01 and finally we need to decrease spending by 1, so x1 + x2 + x3 + x4 ≥ 1. If we were interested in picking uniformly among the assignments that satisfy the constraints, we could encode this distribution conveniently with a factor graph in Figure 2. The resulting distribution is given by px (x) ∝ 1x1 ≤3 1x2 ≤0.5 1x3 ≤0.25 1x4 ≤0.01 1x1 +x2 +x3 +x4 ≥1 2 x1 px1 (x1 ) 1{x1 3} x2 px2 (x2 ) 1{x2 0.5} px3 (x3 ) 1{x3 0.25} px4 (x4 ) 1{x4 0.01} x3 x4 Figure 2: Factor graph encoding constraints on budget. 4.2 4.2.1 Converting Between Graphical Models Types Converting Undirected Models to Factor Graphs We can write down the probability distribution associated to the undirected graph px (x) ∝ f134 (x1 , x3 , x4 )f234 (x2 , x3 , x4 ) which naturally gives a factor graph representation using the potentials as factor nodes (Figure 3). In general, we can convert an undirected graphical model into a factor graph by defining a factor node for each maximal clique. How many maximal cliques could an undirected graph have? We can construct an example where the number of maximal cliques scales like n2 where n is the number of nodes in the undirected graph. Consider a complete bipartite graph where the nodes are evenly split. Given any 3 nodes, 2 of the nodes must lie on the same side and hence be disconnected. Thus, there can’t be any 3 node cliques, so all of the edges are maximal cliques, and there are O(n2 ) edges. In general there can be exponentially many maximal cliques in an undirected graph (See Problem Set 2). 4.2.2 Converting Factor Graphs to Directed Models Take a topological ordering of the nodes say x1 , . . . , xn . For each node in turn, find a minimal set U ⊂ {x1 , . . . , xi−1 } such that xi ⊥ ⊥ {x1 , . . . xi−1 } − U |U is satisfied and set xi ’s parents to be the nodes in U . This amounts to reducing in turn each p(xi |x1 , . . . , xi−1 ) as much as possible using the conditional independencies implied by the factor graph. An example is done in Figure 5. 3 x1 x1 x2 x2 x3 x4 x3 x4 Figure 3: Representing an undirected graph as a factor graph. Figure 4: Complete bipartite graph has O(n2 ) maximal cliques. 4 x1 x2 x3 x4 x3 x1 x4 x2 x3 x1 x4 x2 Figure 5: Converting a factor graph into a directed graph and then into an undirected graph. 4.2.3 Converting from Directed to Undirected Models This is done through moralization, which says to completely connect the parents of each node and then remove the direction of arrows. Moralization “marries” the parents by connecting them together. See Figure 5 for an example. The important thing to recognize is that the conversion process is not lossless. In these constructions, any conditional independence implied by the converted graph is satisfied by the original graph. However, in general, some of the conditional indepen­ dences implied in the original graph are not implied by the converted graph. How do we know that we’ve come up with “good” conversions. We want the converted graph to be close to the original graph for some definition of closeness. We’ll explore these notions through I-maps, D-maps, and P-maps. 4.3 4.3.1 Measuring Goodness of Graphical Representations I-map Consider a probability distribution D and a graphical model G. Let CI(D) denote the set of conditional independencies satisfied by D and let CI(G) denote the set of all conditional independencies implied by G. Definition 1 (I-map). We say G is an independence map or I-map for D if CI(G) ⊂ CI(D). In other words, every conditional independence implied by G is satisfied by 5 Figure 6: Both graphs are I-maps for the distribution that completely factorizes (i.e. px,y = px py ). A B w y x y x z z Figure 7: Two example graphs D if G is an I-map for D. The complete graph is always an example of an I-map for any distribution because it implies no conditional independencies. 4.3.2 D-map Definition 2 (D-map). We say G is a dependence map or D-map for D if CI(G) ⊃ CI(D) that is every conditional independence that D satisfies is implied by G. The graph with no edges is an example of a D-map for any distribution because it implies every conditional independence. 4.3.3 P-map Definition 3 (P-map). We say G is a perfect map or P-map for D if CI(G) = CI(D), i.e., if every conditional independence implied by G is satisfied by D and vice versa. Example 2. Consider three distributions that factor as follows p 1 = p x py pz p2 = pz|x,y px py p3 = pz|x,y px|y py 6 Then the graph in Figure 7(a) is an I-map for p1 , a D-map for p3 and a P-map for p2 . The graph in Figure 7(b) is an I-map for p(x, y, w, z) = 1 f1 (x, w)f2 (w, y)f3 (z, y)f4 (x, z) Z by the Hammersley-Clifford theorem. 7