Data Compression for Learning MRF Parameters

1 Introduction

Markov Random Fields (MRFs) are probabilistic graphical models that have been useful to many fields, including computer vision, bioinformatics, natural language processing, and statistical physics; for example see [Li, 2001; Yanover et al., 2007; Lafferty et al., 2001; Marinari et al., 1997]. An MRF represents a joint probability distribution compactly using a structure populated with parameters. In brief, the structure is an undirected graph defining conditional independence relationships between variables in the graph, whereas the parameters consist of a factor for every maximal clique in the graph; see [Kindermann and Snell, 1980; Koller and Friedman, 2009; Murphy, 2012]. This paper is concerned with learning factors from incomplete data given a fixed structure.

Learning MRF parameters from data is typically reduced to finding the maximum likelihood parameters: ones that maximize the probability of a dataset, due to their attractive statistical properties [Fisher, 1922]. However, due to the complexity of learning maximum likelihood parameters, other simplified methods have also been proposed in literature such as pseudo-likelihood [Besag, 1975], ratio matching [Hyva rinen, 2005], composite maximum likelihood [Varin et al., 2011], contrastive divergence [Hinton, 2000], and more recently the Linear and Parallel algorithm (LAP) [Mizrahi et al., 2014].

A key distinction is commonly drawn between complete and incomplete datasets. In a complete dataset, the value of each variable is known in every example in the dataset, whereas in an incomplete dataset, some variables may have missing values. Computationally, learning from incomplete data can be much harder than learning from complete data, as we discuss next.

If the data is complete, learning maximum likelihood parameters can be formulated as a convex optimization problem. However, evaluating the objective or computing the gradient requires doing inference (i.e. summation over all possible variable instantiations) to compute the partition function, which is #P-hard [Roth, 1996]. Iterative algorithms, such as gradient descent [Russel et al., 1995], conjugate gradient (CG) [Hestenes and Stiefel, 1952], limitedmemory Broyden-Fletcher-Goldfarb-Shanno algorithm (LBFGS) [Liu and Nocedal, 1989], iterative proportional fitting (IPF) [Jirousek and Preucil, 1995], and more recently the edge-deletion maximum-likelihood algorithm (EDML) [Refaat et al., 2013], can be used to get the global optimal solution. Ideally, one inference is required per algorithm iteration, unless line search is used, which may require multiple function evaluations; for more about line search, see Chapter 9 in [Boyd and Vandenberghe, 2004].

On the other hand, if the data is incomplete, the optimization problem is generally non-convex, i.e. has multiple local optima. Iterative algorithms, such as expectation maximization (EM) [Dempster et al., 1977; Lauritzen, 1995] and gradient descent, can be used to get a locally optimal solution; see Chapter 19 in [Murphy, 2012]. Unfortunately, non-convexity is not the only difficulty introduced by the data being incomplete. As pointed out in Koller and Friedman (2009) [Koller and Friedman, 2009], at every iteration, besides doing inference to compute the partition function, we now need to run inference separately conditioned on every unique data example. In this paper, we propose a technique that can significantly decrease the number of required inferences per iteration, without any loss of quality, which we highlight next.

Our goal is to alleviate the need for an inference for each unique data example. We decompose the dataset into smaller datasets each of which is over a subset of the variables, and is associated with some part of the MRF structure. We prove that to compute the objective function or its gradient, one can operate on the decomposed datasets rather than the original dataset. So why can operating on the decomposed datasets be better? We show that our proposed decomposition can create room for compressing the datasets. Accordingly, the decomposed datasets can be much smaller than the original dataset. This leads to decreasing the number of inferences required by the optimization algorithm, and can significantly decrease the learning time.

Our proposed technique exploits variables that are always observed in the dataset, and it can be performed in time that is linear in the MRF structure and dataset size.

The paper is organized as follows. In Section 2, we define our notation and give an introduction to the problem of learning MRF parameters. We motivate the problem we tackle in Section 3. In Section 4, we show how the data decomposition technique works. The experimental results are given in Section 5. We prove that our method is sound in Section 6. We review some of the related work in Section 7, and conclude in Section 8.

2 Learning Parameters

In this section, we define our notation, and review how parameter estimation for MRFs is formulated as an optimization problem. We use upper case letters (X) to denote variables and lower case letters (x) to denote their values. Variable sets are denoted by bold-face upper case letters (X) and their instantiations by bold-face lower case letters (x). The set of all parameters of the MRF is denoted by θ. Variables and their instantiations are used as subscripts for θ to denote a subset of the parameters. Namely, the network parameters are given by the vector θ = (. . . , θXf , . . . ). Component θXf is a parameter set for a factor f, assigning a number θxf > 0 for each instantiation xf of variable set Xf .

We say that an instantiation x and a data example d are compatible, denoted by x ∼ d, iff they agree on the state of their common variables. For example x = a, b, ¯ c is compatible with d1 = a, ¯ c but not with d2 = a, c as c ̸= ¯ c.

The negative log-likelihood of a dataset D = {. . . , di, . . . } is denoted by -ℓℓ(θ|D), and given by:

where N is the number of data examples, and Zθ is the partition function. The partition function is given by Zθ = ∑x ∏f θxf , where ∑x is a summation over all possible instantiations of x, which determines an instantiation xf for each factor f. Similarly, logZθ(di) = ∑x∼di ∏f θxf is the partition function conditioned on example di, i.e. the summation is over the instantiations that agree with the observed values of di. For simplicity, we assume, throughout the paper, a tabular representation as given in [Refaat et al., 2013], as opposed to an exponential representation as given in Chapter 19 in [Murphy, 2012]. In our experiments, however, we use the exponential representation, to avoid the need for explicit non-negativity constraints.

The first term in Equation 1 is called the data term, whereas the second term is called the model term. If the data is complete, Equation 1 is convex, if the exponential representation is used; and the data term becomes trivial to evaluate. Thus, in every optimization iteration, a single inference is typically needed to evaluate the model term.

However, when the data is incomplete, the data term is nontrivial to evaluate as it requires running inference conditioned on every data example di. Thus, the number of inferences needed per iteration would be N + 1 1 . An efficient package would however detect identical data examples, and do inference for every distinct data example. However, the number of distinct data examples can still be substantially large. In this paper, we propose a technique that decomposes the data term and compresses the dataset. As a result, the number of inferences required to evaluate the data term can decrease leading to high speed-ups. We next give a motivation and explain how the technique works.

3 Motivation

We highlight the proposed technique by taking a closer look at the underlying optimization problem. When learning maximum likelihood parameters, the objective function consists of the data term and the model term, as explained in Section 2. Unlike the data term, the model term does not depend on the dataset. In case of complete data, the data term evaluation is trivial during optimization. Thus, only one inference per iteration is required for the model term. However, when the data is incomplete, evaluation of the data term requires a number of inferences equal to the number of distinct data examples in the dataset. In this paper, we exploit variables that are always observed in the dataset, and decompose the data term into independent terms, each of which is over a possibly much smaller dataset.

When inference is done conditioned on a data example, the graph can be pruned using the observed values, to make inference more efficient; see Chapter 6 in [Darwiche, 2009]. Most learning packages, that use efficient inference engines, use such techniques that date back to Shachter [Shachter, 1986; 1990]. Namely, the graph is pruned given every data example, before doing inference. The key observation that we exploit is that the pruned graphs, given all the data examples, share something in common, if some variables are always observed. This commonality is the heart of the proposed method.

To capture this commonality, we decompose the graph conditioned only on the variables that are always observed in the dataset. As a result, the graph is decomposed into a number of sub-graphs each of which is over a subset of the variables. We then project the dataset onto the variables of each sub-graph, by discarding the variables not in the sub-graph. We prove that evaluating the data term or computing its gradient can now be computed by doing inference in the sub-graphs and their projected datasets independently. This begs the question: Why is this decomposition useful?

Now, the number of variables and, therefore, unique data examples in each projected dataset is much smaller than in the original dataset. As a result, each projected dataset can be compressed significantly by detecting repetitions, and accordingly, the number of inferences required in each iteration decreases. We show empirically that the proposed method can lead to orders-of-magnitude speed-ups. In fact, data compression becomes particularly useful as the size of the dataset grows, and as the number of observed variables increases.

Not surprisingly, in today's world, with the growing use of low-cost computers and sensors for data collection [Cherkassky and Mulier, 2007], large datasets are widely available. Furthermore, it is not uncommon to have a significant number of variables that are always observed. For example, in the UCI repository: the internet advertisements database has 1558 variables, only 3 of which have missing values; the Automobile database has 26 variables, where 7 have missing values; the Dermatology database has 34 variables, where only age can be missing; the Mushroom dataset has 22 variables, where only one variable has missing values; and so on [Bache and Lichman, 2013]. Thus, data compression can potentially benefit a non-trivial spectrum of problems in different fields.

1N iterations are needed for doing inference conditioned on each data example, and one inference is needed for the model term.

4 Data Decomposition

In this section, we explain how the data term is decomposed and, accordingly, the dataset is compressed. The proof will be given in Section 6. Figure 1 (top) shows a 3 × 3 grid MRF that we use as a running example. Factors in the grid are binary, i.e. involves two variables, and variables can take 2 states: true (t) or false (f). Suppose that Variables 1, 6, and 8 have missing values in the dataset (denoted by ?), whereas Variables 2, 3, 4, 5, 7, and 9 are always observed (cannot take ?). The dataset takes the form:

Firstly, we create a factor graph, as given in Figure 1 (middle), which has a node for every factor in the original MRF. An edge between two factors exists if and only if they share a common variable. For example, f12 and f25 share Variable 2, and therefore has an edge between them in the factor graph. The decomposition will be performed on the created factor graph as shown next.

Secondly, we delete any edge, in the factor graph, if the common variables between its nodes are always observed in the dataset. For example, the edge between f12 and f25 is deleted as the common Variable 2 is always observed in the dataset. On the other hand, f58 and f89 remains intact as the common Variable 8 has missing values in the dataset. The result of this decomposition is given in Figure 1 (bottom).

Now, the decomposed factor graph in Figure 1 (bottom) decomposes the MRF into multiple sub-networks, each of which is over a subset of factors. For example, factors f12 and f14 forms a sub-network. As we will prove in Section 6, the data term decomposes into a summation of independent terms corresponding to each sub-network.

Thirdly, we project the dataset onto the variables of each sub-network, by discarding the variables not in the subnetwork. For example, we project the dataset onto the variables of the sub-network, f12-f14, by discarding all variables except 1, 2, and 4. Thus, this projected dataset will have only 3 columns, and will take the form:

Now, we have a projected dataset for each sub-network. Finally, we will compress every projected dataset by detecting repetitions and adding a count field to every distinct data example. For example, the compressed dataset for f12 - f14 may take the form:

where the count keeps record of how many times the distinct data example was repeated in the dataset. The key observation here is that the number of repetitions increases in the projected datasets. By a simple counting argument, one can show that the maximum number of possible distinct data examples that can appear in the original dataset is 26 × 33 = 1728. 2 On the other hand, the maximum number of distinct data examples in the projected dataset of f12 -f14, for instance, can be at most only 22 × 31 = 12.

2 Note that a variable with missing values can take true, false, or be missing.

Every sub-network with its own projected, and potentially compressed, dataset now induces an independent data term, defined exactly as the original data term, as we will show in Section 6. We will prove that the original data term is equivalent to the summation of all the independent sub-network data terms. Thus, to evaluate or compute the gradient of the original data term, one needs to evaluate or compute the gradient of the data term of each sub-network independently, and then combine them by addition.

The decomposition above suggests that as more variables are always observed, the MRF is decomposed into much smaller sub-networks leading to more repetitions. Moreover, as the dataset size gets larger, the difference between the data before and after decomposition is magnified. Now, we will show that, experimentally, data decomposition works as expected and can achieve orders-of-magnitude savings in time.

5 Experimental Results

We compare the time taken by the gradient method if data decomposition is used, versus if the original dataset is used. In particular, using a fixed network structure, we simulate a dataset, then make the data incomplete by randomly selecting a certain percentage of variables to have missing values. After that, we learn the parameters from the data using the gradient method with and without data decomposition, to obtain a local optimum.

For 11 different networks, 3 and with hiding 20% of the variables, Table 1 shows the time taken by the gradient method without data decomposition tgrad, and with data decomposition td-grad, together with the speed-up achieved by data decomposition, computed as tgrad td-grad . In all cases, the same learned parameters were returned by both techniques, which we do not show in the table.

One can see that data decomposition achieved one-to-two orders-of-magnitude speed-up in learning time in most cases. The decomposition technique has almost left the dataset of network 54.wcsp without much decomposition leading to little speed-up.

In this experiment, we did not vary the percentage of observed variables nor the dataset size. We selected the dataset in each case to be as small as possible without making computing the data term much easier than the model term. We next analyze the behavior of the decomposition technique when the percentage of observed variables or the dataset size changes.

As the motivating example in Section 4 suggests, we expect that data decomposition will behave favorably as the dataset gets larger, and as more variables are always observed in the dataset.

Figure 2 shows the speed-up achieved with a dataset of 212 examples, while always observing different percentages of variables, using 4 different structures. As expected, as less nodes have missing values, the speed-up increases.

3 Among the used structures are randomly generated chains (Chain-50 and Chain-100), and randomly generated binary trees (Tree-63, Tree-127, Tree-225). Grid9x9 and Grid10x10 are grid networks. Network 54.wcsp is a weighted CSP problem, whereas Network win95pts is an expert system for printer troubleshooting in Windows 95. Network smokers is a relational Markov network.

Figure 3 shows the speed-up achieved while using a hiding percentage of 20%, for different dataset sizes, in log-scale. Indeed, the speed-up is directly proportional to the dataset size. In this case, orders-of-magnitude speed-up was achieved starting from 214 examples.

Given the difficulty of the problem, the speed-up achieved by data decomposition can be indispensable. For example, for a 9 × 9 Grid, 216 data examples, and 20% hiding percentage, the gradient method took about 3 minutes by data decomposition versus about 17 hours by detecting repetitions in the original dataset.

Decomposition can also make learning feasible in large problems. For example, we were able to learn the parameters of a network from the field of genetics (Family2Recessive), that has 385 factors, from 212 examples with 20% hiding, in about 55 minutes, by data decomposition. However, we were not able to get results, in less than a day, without data decomposition, for this network.

We next show that an existing prominent package (FastInf)

does not appear to use the proposed data decomposition. We compare the speed-up obtained of our basic implementation of gradient descent and EM, that use data decomposition, against FastInf [Jaimovich et al., 2010]. We provided our system and FastInf with the same initial parameters, same incomplete datasets (hiding 20%), and the same MRF structure.

Figure 4 shows the speed-up obtained by our Gradient and EM methods, that use data decomposition (allowed 100 iterations), over FastInf EM (with the gradient option allowed only 2 iterations), for different dataset sizes in log-scale. One can see that as the data increases, more speed-up is achieved. We were able to get a better likelihood too as we run our system for more iterations, and still achieve high speed-ups.

In Figure 5, we fix the dataset size to 212 and show the speed-up obtained by our technique over FastInf EM with different algorithm options: 0-FR, 1-PR, 2-BFGS, 3-STEEP, 4NEWTON 4 . Newton method was not successful and, therefore, not shown in the figure.

4 For details about different algorithm options in FastInf,

Although FastInf uses approximate inference, and our implementation is based on exact inference, we were still able to realize orders-of-magnitude speed-ups over FastInf, as the dataset size increases.

We note too that data decomposition is done once and can be performed in time that is linear in the MRF structure size and dataset size. The execution time of our methods used to compute the speed-ups did involve the time needed to decompose the graph and decompose the data. In the next section, we prove that data decomposition is exact, and does not compromise quality.

6 Soundness

In this section, we prove that our decomposition technique is sound. Before we give our decomposition theorem, we review the notion of parameter terms, initially introduced in the context of Bayesian networks in [Refaat et al., 2014].

6.1 Parameter Terms

Two parameters are compatible, denoted by θxf ∼ θxf′ , iff they agree on the state of their common variables. For example, parameters θxf=xy and θxf′=zy are compatible, but parameters θxf=xy and θxf′=zy are not compatible, as y ̸= y.

Moreover, a parameter is compatible with an example iff they agree on the state of their common variables. For example, parameter θxf=xy is compatible with example x, y, z, v, but not with example x, y, z, v. The definition of a parameter term is given as follows:

Definition 1 (Parameter Term) Let F be a set of network factors and let d be a data example. A parameter term for F and d, denoted ΘdF, is a product of compatible network parameters, one for each factor in F, that are also compatible with example d.

For example, consider an MRF with 3 factors {θXf1 =X, θXf2 =XY , θXf3 =YZ}; and let F be the subset of factors {θXf1 =X, θXf2 =XY } and d = x, z. Then, ΘdF will denote either θxf1 =x.θxf2 =xy or θxf1 =x.θxf2 =x.y.

When F has all the MRF factors, i.e. F = {θXf1 =X, θXf2 =XY , θXf3 =YZ}, then ΘdF will denote either θxf1 =x.θxf2 =xy.θxf3 =yz or θxf1 =x.θxf2 =x y.θxf3 =yz; in this

see [Jaimovich et al., 2010]

case Zθ(d) = ∑ΘdF ΘdF. Armed with parameter terms, we are now ready to state our decomposition theorem.

Theorem 1 The data term is decomposed into a number of smaller functions corresponding to sub-networks. The loglikelihood takes the form:

where nsi is the number of times that distinct di appears in the projected dataset of Sub-network s, N s is the total number of distinct data examples in the projected dataset of Sub-network s, and Z s θ (di) is the partition function of Subnetwork s conditioned on example di.

Proof We will proceed by induction, decomposing one subnetwork, and operating inductively on the rest of the network to decompose all the sub-networks.

We note that the data term in the log-likelihood function, ∑Ni=1 log Zθ(di), can be written as:

Where N is the number of data points in the dataset 5 , and F is the set of all factors in the MRF. Let Fs be the set of factors in Sub-network s, and Fs′ be the set of all the rest of the factors. By definition of parameter terms, the data term can be re-written as:

where the fourth summation is over all Θdi Fs′ that agree on the state of their common variables with Θdi Fs, which is denoted by the compatibility: Θdi Fs′ ∼ Θdi Fs .

By the decomposition procedure, the common variables between Sub-network s and the rest of the network are always observed. Otherwise, the sub-network would not have been separated from the rest. Therefore, Θdi Fs′ and Θdi Fs always agree on the common variables, which are determined by di. Thus, there is no need to ensure compatibility, and the data term can be written as:

Now the distinct data points with respect to Sub-network s can be detected, to get:

5 In this case, not necessarily distinct.

By observing that ∑Θdi Fs Θdi Fs is equivalent to the partition function of Sub-network s conditioned on di, we get:

We continue inductively on the rest of the network to decompose all the sub-networks. □

7 RelatedWork

Some work on decomposing MRFs and Bayesian networks (BNs) exist in literature. In the context of inference in BNs, pruning Barren nodes and edges outgoing from observed variables was initially proposed in [Shachter, 1986; 1990] 6 .

In the context of parameter learning from incomplete data, decomposing the BN optimization problem was proposed in [Refaat et al., 2014], where the notion of parameter terms was introduced. Namely, it was shown that fully observed variables may be exploited to decompose the optimization problem into independent problems, leading to both data decomposition and independent convergence. In this paper, we migrate this concept to the context of MRFs. While the partition function makes decomposing the optimization problem exactly, as in [Refaat et al., 2014], hard, we showed here that similar decomposition techniques can be used to decompose the data term, leading to decomposing, and potentially, compressing the dataset.

For MRFs, the LAP algorithm [Mizrahi et al., 2014] deals with approximately decomposing MRFs in the case of complete data, where they showed that LAP behaves similarly to pseudo-likelihood and maximum likelihood, for large sample sizes, while being more efficient. A similar method was independently introduced by [Meng et al., 2013] in the context of Gaussian graphical models. Our work stands out from the LAP algorithm in dealing with incomplete data, and in being equivalent to maximizing the likelihood. However, our proposed technique does not help in the case of complete data, as the data term becomes trivial.

8 Conclusion

We proposed a technique for decomposing the dataset to learn MRF parameters from incomplete data. The technique works by decomposing the MRF to sub-networks based on variables that are always observed in the incomplete dataset. The dataset is then projected on each sub-network, and compressed by detecting repetitions.

The key observation, that data compression relies on, is that sub-networks typically have a small number of variables. Thus, it is likely that more repetitions, and, accordingly, compression can take place. Our empirical results suggest that orders-of-magnitude speed-ups may be obtained using data decomposition.

The decomposition process incurs very little overhead as it can be performed in time that is linear in the MRF structure size and dataset size. Hence, given the potential savings it may lead to, it appears that one must always try to decompose the incomplete dataset before learning maximum likelihood MRF parameters.

6 Pruning edges migrates to MRFs.

Acknowledgments

This work was supported by ONR grant #N00014-12-1-0423 and NSF grant #IIS-1118122.