nips nips2006 nips2006-69 knowledge-graph by maker-knowledge-mining

69 nips-2006-Distributed Inference in Dynamical Systems

Source: pdf

Author: Stanislav Funiak, Carlos Guestrin, Rahul Sukthankar, Mark A. Paskin

Abstract: We present a robust distributed algorithm for approximate probabilistic inference in dynamical systems, such as sensor networks and teams of mobile robots. Using assumed density ﬁltering, the network nodes maintain a tractable representation of the belief state in a distributed fashion. At each time step, the nodes coordinate to condition this distribution on the observations made throughout the network, and to advance this estimate to the next time step. In addition, we identify a signiﬁcant challenge for probabilistic inference in dynamical systems: message losses or network partitions can cause nodes to have inconsistent beliefs about the current state of the system. We address this problem by developing distributed algorithms that guarantee that nodes will reach an informative consistent distribution when communication is re-established. We present a suite of experimental results on real-world sensor data for two real sensor network deployments: one with 25 cameras and another with 54 temperature sensors. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 Using assumed density ﬁltering, the network nodes maintain a tractable representation of the belief state in a distributed fashion. [sent-2, score-0.613]

2 At each time step, the nodes coordinate to condition this distribution on the observations made throughout the network, and to advance this estimate to the next time step. [sent-3, score-0.325]

3 In addition, we identify a signiﬁcant challenge for probabilistic inference in dynamical systems: message losses or network partitions can cause nodes to have inconsistent beliefs about the current state of the system. [sent-4, score-0.709]

4 We address this problem by developing distributed algorithms that guarantee that nodes will reach an informative consistent distribution when communication is re-established. [sent-5, score-0.613]

5 We present a suite of experimental results on real-world sensor data for two real sensor network deployments: one with 25 cameras and another with 54 temperature sensors. [sent-6, score-0.546]

6 Often, nodes in these networks need to perform probabilistic dynamic inference to combine a sequence of local, noisy observations into a global, joint estimate of the system state. [sent-8, score-0.407]

7 For example, robots in a team may combine local laser range scans, collected over time, to obtain a global map of the environment; nodes in a camera network may combine a set of image sequences to recognize moving objects in a heavily cluttered scene. [sent-9, score-0.52]

8 Instead, the nodes need to collaborate, to solve the inference task in a distributed manner. [sent-12, score-0.479]

9 Such distributed inference techniques are also necessary in online control applications, where nodes of the network need estimates of the state in order to make decisions. [sent-13, score-0.662]

10 Since the observations are distributed across the network, nodes must coordinate to incorporate each others’ observations and propagate their estimates from one time step to the next. [sent-19, score-0.635]

11 Furthermore, the algorithm needs to robustly address node failures and interference that may partition the communication network into several disconnected components. [sent-21, score-0.626]

12 We present an efﬁcient distributed algorithm for dynamic inference that works on a large family of processes modeled by dynamic Bayesian networks. [sent-22, score-0.404]

13 In our algorithm, each node maintains a (possibly approximate) marginal distribution over a subset of state variables, conditioned on the measurements made by the nodes in the network. [sent-23, score-0.595]

14 At each time step, the nodes condition on the observations, using a modiﬁcation of the robust (static) distributed inference algorithm [7], and then advance their estimates to the next time step locally. [sent-24, score-0.655]

15 The algorithm guarantees that, with sufﬁcient communication at each time step, the nodes obtain the same solution as the corresponding centralized algorithm [2]. [sent-25, score-0.459]

16 Before convergence, the algorithm introduces principled approximations in the form of independence assertions in the node estimates and in the transition model. [sent-26, score-0.433]

17 In the presence of unreliable communication or high latency, the nodes may not be able to condition their estimates on all the observations in the network, e. [sent-27, score-0.453]

18 Hence, the beliefs at the nodes may be conditioned on different evidence and no longer form a consistent global probability distribution over the state space. [sent-31, score-0.325]

19 We propose an online algorithm, optimized conditional alignment (OCA), that obtains the global distribution as a product of conditionals from local estimates and optimizes over different orderings to select a global distribution of minimal entropy. [sent-34, score-0.506]

20 We present experimental results on real-world sensor data, covering sensor calibration [7] and distributed camera localization [5]. [sent-36, score-0.625]

21 2 The distributed dynamic inference problem Following [7], we assume a network model where each node can perform local computations and communicate with other nodes over some channel. [sent-44, score-0.975]

22 The nodes of the network may change over time: existing nodes can fail, and new nodes may be introduced. [sent-45, score-0.74]

23 In the distributed dynamic inference problem, each node n is associated with a set of processes Qn ⊆ X; these are the processes about which node n wishes to reason. [sent-64, score-0.883]

24 The nodes need to collab(t) orate so that each node can obtain (an approximation to) the posterior distribution over Qn given (t) (1:t) all measurements made in the network up to the current time step t: p(Qi | z ). [sent-65, score-0.758]

25 An effective approach, proposed by Boyen and Koller [2], hereby denoted “B & K 98”, is to periodically project the exact posterior to a distribution that satisﬁes independence assertions encoded in a junction tree [3]. [sent-79, score-0.388]

26 4 Approximate distributed ﬁltering In principle, the centralized ﬁltering approach described in the previous section could be applied to a distributed system, e. [sent-83, score-0.491]

27 , by communicating the observations made in the network to a central location that performs all computations, and distributing the answer to every node in the network. [sent-85, score-0.448]

28 While conceptually simple, this approach has substantial drawbacks, including the high communication bandwidth, the introduction of a single point of failure to the system, and the fact that nodes do not have valid estimates when the network is partitioned. [sent-86, score-0.559]

29 In this section, we present a distributed ﬁltering algorithm where each node obtains an approximation to the posterior distribution over subset of the state variables. [sent-87, score-0.598]

30 Our estimation step builds on the robust distributed inference algorithm of Paskin et al. [sent-88, score-0.362]

31 1 Estimation as a robust distributed probabilistic inference In the distributed inference approach of Paskin et al. [sent-91, score-0.588]

32 [8], the nodes collaborate so that each node n can obtain the posterior distribution over some set of variables Qn given all measurements made throughout the network. [sent-92, score-0.651]

33 We refer to this tree as the network junction tree, and, for clarity, we refer to the junction tree used for the assumed density as the external junction tree. [sent-95, score-0.899]

34 Using this architecture, Paskin and Guestrin developed a robust distributed probabilistic inference algorithm, RDPI [7], for static inference settings, where nodes compute the posterior distribution p(Qn | z) over Qn given all measurements throughout the network z. [sent-96, score-0.838]

35 In RDPI, each node n maintains the current belief βn of p(Qn | z). [sent-98, score-0.333]

36 Initially, node n knows only the marginals of the prior distribution {p(Ci ) : i ∈ Ln } for a subset of cliques Ln in the external junction tree, and its local observation model p(zn | Pa[Zn ]) for each of its sensors. [sent-99, score-0.801]

37 Then the cliques in βn form a subtree of an external junction tree that covers Qn . [sent-110, score-0.55]

38 At convergence, each node n obtains the calibrated marginals ˜ (Ci | z(1:t) ), for i ∈ p Ln . [sent-113, score-0.485]

39 In order to advance to the next time step, each node must perform prediction and roll-up, (t+1) obtaining the marginals ˜ (Ci p | z(1:t) ). [sent-114, score-0.454]

40 Due to the conditional independencies encoded in p ˜ (X(t) | z(1:t) ), it is sufﬁcient to obtain a subtree of the external junction tree that covers the parents p (t+1) (t+1) Pa[Ci ] of all variables in the clique. [sent-116, score-0.56]

41 Instead, we propose a simple approach that performs both steps at once: run the distributed inference algorithm, described in the previous section, to obtain the posterior distribution over the parents of each clique maintained at the node. [sent-120, score-0.603]

42 This task can be accomplished by ensuring that these (t+1) parent variables are included in the query variables of node n: Pa[Ci ] ⊆ Qn , ∀i ∈ Ln . [sent-121, score-0.368]

43 When the estimation step cannot be run to convergence within the allotted time, the variables Scope[βn ] covered by the distribution βn that node n obtains may not cover the entire parent set (t+1) Pa[Ci ]. [sent-122, score-0.531]

44 3 Summary of the algorithm Our distributed approximate ﬁltering algorithm can be summarized as follows: • Using the architecture in [8], construct a network junction tree s. [sent-131, score-0.572]

45 p Using the convergence properties of the RDPI algorithm, we prove that, given sufﬁcient communication, our distributed algorithm obtains the same solution as the centralized B & K 98 algorithm: Theorem 1. [sent-138, score-0.41]

46 1 2 3 4 (a) BK solution 1 2 3 4 1 2 3 4 (b) alignment rooted at 1 (c) alignment rooted at 4 1 2 3 4 (d) min. [sent-140, score-0.496]

47 5 Robust distributed ﬁltering In the previous section, we introduced an algorithm for distributed ﬁltering with dynamic Bayesian networks that, with sufﬁcient communication, converges to the centralized B & K 98 algorithm. [sent-147, score-0.556]

48 In some settings, for example when interference causes a network partition, messages may not be propagated long enough to guarantee convergence before nodes must roll-up to the next time step. [sent-148, score-0.519]

49 Each camera i carries a clique marginal over the location of the object M (t) , its own camera pose variable C i , and the pose of one of its neighboring cameras: π1 (C 1,2 , M (t) ), π2 (C 2,3 , M (t) ), and π3 (C 3,4 , M (t) ). [sent-150, score-0.696]

50 Suppose communication were interrupted due to a network partition: observations would not propagate, and the marginals carried by the nodes would no longer form a consistent distribution, in the sense that π1 ,π2 ,π3 might not agree on their marginals, e. [sent-151, score-0.714]

51 The goal of alignment is to obtain a consistent distribution ˜ (X(t) | z(1:t−1) ) from marginals π1 , π2 , π3 that is close to the true posterior p(X(t) | z(1:t−1) ) (as p measured, for example, by the root-mean-square error of the estimates). [sent-154, score-0.456]

52 1 Optimized conditional alignment One way to deﬁne a consistent distribution ˜ is to start from a root node r, e. [sent-157, score-0.801]

53 , 1, and allow each p clique marginal to decide the conditional density of Ci given its parent, e. [sent-159, score-0.337]

54 p This density ˜1 forms a coherent distribution over C 1:4 , M , and we say that ˜1 is rooted at node 1. [sent-162, score-0.408]

55 If node 3 were the root, then node 1 would only contribute π1 (C 1 | C 2 , M ), and we would obtain a different approximate distribution. [sent-164, score-0.544]

56 The choice of the root r often crucially determines how well the aligned distribution ˜r approxp imates the true prior. [sent-166, score-0.327]

57 Suppose that, in the example in Figure 1, the nodes on the left side of the partition do not observe the person while the communication is interrupted, and the prior marginals π1 , π2 are uncertain about M . [sent-167, score-0.552]

58 If we were to align the distribution from π2 , multiplying π3 (C 4 | C 3 , M ) into the marginal π2 (C 2,3 , M ) would result in a distribution that is uncertain in both M and C 4 (Figure 1(b)), while a better choice of root could provide a much better estimate (Figure 1(c)). [sent-168, score-0.376]

59 One possible metric to optimize when choosing the root r for the alignment is the entropy of the resulting distribution ˜r . [sent-169, score-0.491]

60 A na¨ve algorithm for obtaining p ı the best root would exploit this decomposition to compute the entropy of each ˜2 , and pick the root p that leads to a lowest total entropy; the running time of this algorithm is O(|NT |2 ). [sent-171, score-0.512]

61 Comparing Equation 3 with the entropy of the distribution rooted at a neighboring node 3, we see that they share a common term Hπ1 (C 1 | C 2 , M ), and H˜3 (C 1:4 , M ) − H˜2 (C 1:4 , M ) = Hπ3 (S2,3 ) − Hπ2 (S2,3 ) 2,3 . [sent-173, score-0.427]

62 If p p 2,3 is positive, node 2 is a better root than 3, 2,3 is negative, we have the reverse situation. [sent-174, score-0.486]

63 Thus, when comparing neighboring nodes as root candidates, the difference in entropy of the resulting distribution is simply the difference in entropy their local distributions assign to their separator. [sent-175, score-0.564]

64 Intuitively, the message mi→j represents the loss (entropy) with root node j, compared to the best root on i’s side of the tree. [sent-178, score-0.799]

65 2 Distributed optimized conditional alignment In the absence of an additional procedure, RDPI can be viewed as performing conditional alignment. [sent-181, score-0.389]

66 However, the alignment is applied to the local belief at each node, rather than the global distribution, and the nodes may not agree on the choice of the root r. [sent-182, score-0.665]

67 By Property 1, at convergence, the priors at each node form a subtree of an external junction tree for the assumed density. [sent-185, score-0.672]

68 Conceptually, if we were to apply OCA to this subtree, the node would have an aligned distribution, but nodes may not be consistent with each other. [sent-186, score-0.593]

69 In RDPI, node n’s belief βn includes a collection of (potentially inconsistent) priors {πi (Ci )}. [sent-188, score-0.333]

70 In the standard sum-product inference algorithm, an inference message µm→n from node m to node ψm × k=n µk→m n is computed by marginalizing out some variables from the factor µ+ m→n that combines the messages received from node m’s other neighbors with node m’s local belief. [sent-189, score-1.5]

71 The inference message in RDPI involves a similar marginalization, which corresponds to pruning some cliques from µ+ m→n [7]. [sent-190, score-0.338]

72 Our distributed OCA algorithm piggy-backs on this pruning, computing an optimization message mi→j , which is stored in clique j. [sent-192, score-0.493]

73 ) At convergence, the nodes will not only have a subtree of an external tree, but also the incoming optimization messages that result from pruning of all other cliques of the external tree. [sent-194, score-0.639]

74 In order to determine the globally optimal root, each node (locally) selects a root for its subtree. [sent-195, score-0.486]

75 If this root is one of the initial cliques associated with n, then n, and in particular this clique, is the root of the conditional alignment. [sent-196, score-0.593]

76 If the optimal root is determined to be a clique that came from a message received from a neighbor, then the neighbor (or another node upstream) is the root, and node n aligns itself with respect to the neighbor’s message. [sent-198, score-1.136]

77 Given sufﬁcient communication and in the absence of network partitions, nodes running distributed OCA reach a globally consistent belief based on conditional alignment, selecting the root clique that leads to the joint distribution of minimal entropy. [sent-200, score-1.33]

78 3 Jointly optimized alignment While conceptually simple, there are situations where such a rooted alignment will not provide a good aligned distribution. [sent-203, score-0.614]

79 For example, if in the example in Figure 1, cameras 2 and 3 carry marginals π2 (C 2,3 , M ) and π2 (C 2,3 , M ), respectively, and both observe the person, node 2 will have a better estimate of C 2 , while node 3’s estimate of C 3 will be more accurate. [sent-204, score-0.822]

80 If either node is chosen as the root, the aligned distribution will have a worse estimate of the pose of one of the cameras, because performing rooted alignment from either direction effectively overwrites the marginal of the other node. [sent-205, score-0.712]

81 2 0 20 40 epochs per time step 60 (a) 25-camera testbed (b) Convergence, cameras (c) Convergence, temperature Figure 2: (a) Testbed of 25 cameras used for the SLAT experiments. [sent-217, score-0.395]

82 (c) Convergence versus amount of communication for a temperature network of 54 real sensors. [sent-220, score-0.359]

83 The former problem can be solved in a distributed manner using distributed linear regression [6], while the latter can be solved using a distributed version of an iterative methods, such as conjugate gradient descent [1]. [sent-227, score-0.564]

84 6 Experimental results We evaluated our approach on two applications: a camera localization problem [5] (SLAT), in which a set of cameras simultaneously localizes itself by tracking a moving object, and temperature monitoring application, analogous to the one presented in [7]. [sent-228, score-0.5]

85 We implemented our distributed algorithm in a network simulator that incorporates message loss and used data from these real sensors as our observations. [sent-230, score-0.412]

86 In Figure 3(a), the network is split into four components; in each component, the nodes communicate fully, and we evaluate the solution if the communication were to be restored after a given number of time steps. [sent-236, score-0.555]

87 The results show that, in the absence of optimized alignment, inconsistencies can degrade the solution: observations collected after the communication is restored may not make up for the errors introduced by the partition. [sent-239, score-0.393]

88 Figures 3(b) shows the importance of aligning from the correct node: the difference between the optimized root and an arbitrarily chosen root is signiﬁcant, particularly when the network becomes more and more fractured. [sent-243, score-0.662]

89 2 lower bound 0 0 50 100 Duration of the partition (a) camera localization 0 0 2 4 6 8 Number of partitions (b) camera localization upper bound 0. [sent-258, score-0.598]

90 4 RMS error fixed root optimized root unaligned RMS error RMS error 0. [sent-259, score-0.629]

91 KL unaligned 5 Number of partitions 10 (c) temperature monitoring Figure 3: Comparison of the alignment methods. [sent-261, score-0.48]

92 For the unaligned solution, the plot shows bounds on the error: given the (unknown) camera locations, we select the best and worst estimates available in the network for each camera’s pose. [sent-264, score-0.463]

93 In camera localization (b), the difference between the optimized alignment and the alignment from an arbitrarily chosen ﬁxed root is signiﬁcant. [sent-268, score-0.896]

94 Finally, 3(c) shows the alignment results on the temperature monitoring application. [sent-271, score-0.322]

95 One contributing factor is that every node in a partition is making local temperature observations, and the approximate transition model for temperatures in each partition is quite accurate, hence all the nodes continue to adjust their estimates meaningfully while the partition is in progress. [sent-273, score-0.849]

96 7 Conclusions This paper presents a new distributed approach to approximate dynamic ﬁltering based on a distributed representation of the assumed density in the network. [sent-274, score-0.475]

97 Distributed ﬁltering is performed by ﬁrst conditioning on evidence using a robust distributed inference algorithm [7], and then advancing to the next time step locally. [sent-275, score-0.362]

98 With sufﬁcient communication in each time step, our distributed algorithm converges to the centralized B & K 98 solution. [sent-276, score-0.442]

99 In addition, we identify a signiﬁcant challenge for probabilistic inference in dynamical systems: nodes can have inconsistent beliefs about the current state of the system, and an ineffective handling of this situation can lead to very poor estimates of the global state. [sent-277, score-0.475]

100 We address this problem by developing a distributed algorithm that obtains an informative consistent distribution, optimizing over various choices of the root node, and an alternative joint optimization approach that minimizes a KL divergence-based criterion. [sent-278, score-0.505]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('ci', 0.284), ('node', 0.272), ('rdpi', 0.225), ('root', 0.214), ('clique', 0.206), ('nodes', 0.205), ('camera', 0.19), ('pa', 0.189), ('distributed', 0.188), ('alignment', 0.185), ('junction', 0.158), ('qn', 0.153), ('marginals', 0.152), ('communication', 0.139), ('paskin', 0.135), ('nt', 0.132), ('cameras', 0.126), ('network', 0.125), ('cliques', 0.116), ('centralized', 0.115), ('oca', 0.104), ('zk', 0.102), ('rms', 0.101), ('tree', 0.101), ('sensor', 0.1), ('message', 0.099), ('temperature', 0.095), ('ltering', 0.092), ('unaligned', 0.09), ('inference', 0.086), ('guestrin', 0.08), ('subtree', 0.077), ('messages', 0.076), ('ln', 0.075), ('optimized', 0.075), ('aligned', 0.074), ('funiak', 0.069), ('partitions', 0.068), ('dynamic', 0.065), ('external', 0.064), ('rooted', 0.063), ('belief', 0.061), ('obtains', 0.061), ('estimates', 0.058), ('partition', 0.056), ('entropy', 0.053), ('assertions', 0.052), ('restored', 0.052), ('slat', 0.052), ('observations', 0.051), ('inconsistent', 0.051), ('kl', 0.051), ('transition', 0.051), ('conditional', 0.049), ('step', 0.048), ('marginal', 0.048), ('localization', 0.047), ('convergence', 0.046), ('parents', 0.046), ('inconsistencies', 0.045), ('consistent', 0.042), ('monitoring', 0.042), ('robust', 0.04), ('beliefs', 0.039), ('neighbor', 0.039), ('distribution', 0.039), ('dbn', 0.038), ('posterior', 0.038), ('pruning', 0.037), ('mk', 0.037), ('fixed', 0.036), ('dynamical', 0.036), ('multiplying', 0.036), ('uai', 0.035), ('measurement', 0.035), ('boyen', 0.035), ('collaborate', 0.035), ('ipsn', 0.035), ('pfeffer', 0.035), ('pfs', 0.035), ('rosencrantz', 0.035), ('separator', 0.035), ('teams', 0.035), ('aligning', 0.034), ('wx', 0.034), ('interference', 0.034), ('communicate', 0.034), ('covers', 0.034), ('propagate', 0.034), ('density', 0.034), ('received', 0.034), ('parent', 0.034), ('propagated', 0.033), ('conceptually', 0.032), ('variables', 0.031), ('absence', 0.031), ('running', 0.031), ('pose', 0.031), ('measurements', 0.031), ('advance', 0.03)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999958 69 nips-2006-Distributed Inference in Dynamical Systems

Author: Stanislav Funiak, Carlos Guestrin, Rahul Sukthankar, Mark A. Paskin

2 0.1388462 74 nips-2006-Efficient Structure Learning of Markov Networks using $L 1$-Regularization

Author: Su-in Lee, Varun Ganapathi, Daphne Koller

Abstract: Markov networks are commonly used in a wide variety of applications, ranging from computer vision, to natural language, to computational biology. In most current applications, even those that rely heavily on learned models, the structure of the Markov network is constructed by hand, due to the lack of effective algorithms for learning Markov network structure from data. In this paper, we provide a computationally efﬁcient method for learning Markov network structure from data. Our method is based on the use of L1 regularization on the weights of the log-linear model, which has the effect of biasing the model towards solutions where many of the parameters are zero. This formulation converts the Markov network learning problem into a convex optimization problem in a continuous space, which can be solved using efﬁcient gradient methods. A key issue in this setting is the (unavoidable) use of approximate inference, which can lead to errors in the gradient computation when the network structure is dense. Thus, we explore the use of different feature introduction schemes and compare their performance. We provide results for our method on synthetic data, and on two real world data sets: pixel values in the MNIST data, and genetic sequence variations in the human HapMap data. We show that our L1 -based method achieves considerably higher generalization performance than the more standard L2 -based method (a Gaussian parameter prior) or pure maximum-likelihood learning. We also show that we can learn MRF network structure at a computational cost that is not much greater than learning parameters alone, demonstrating the existence of a feasible method for this important problem.

3 0.13185406 139 nips-2006-Multi-dynamic Bayesian Networks

Author: Karim Filali, Jeff A. Bilmes

Abstract: We present a generalization of dynamic Bayesian networks to concisely describe complex probability distributions such as in problems with multiple interacting variable-length streams of random variables. Our framework incorporates recent graphical model constructs to account for existence uncertainty, value-speciﬁc independence, aggregation relationships, and local and global constraints, while still retaining a Bayesian network interpretation and efﬁcient inference and learning techniques. We introduce one such general technique, which is an extension of Value Elimination, a backtracking search inference algorithm. Multi-dynamic Bayesian networks are motivated by our work on Statistical Machine Translation (MT). We present results on MT word alignment in support of our claim that MDBNs are a promising framework for the rapid prototyping of new MT systems. 1 INTRODUCTION The description of factorization properties of families of probabilities using graphs (i.e., graphical models, or GMs), has proven very useful in modeling a wide variety of statistical and machine learning domains such as expert systems, medical diagnosis, decision making, speech recognition, and natural language processing. There are many different types of graphical model, each with its own properties and beneﬁts, including Bayesian networks, undirected Markov random ﬁelds, and factor graphs. Moreover, for different types of scientiﬁc modeling, different types of graphs are more or less appropriate. For example, static Bayesian networks are quite useful when the size of set of random variables in the domain does not grow or shrink for all data instances and queries of interest. Hidden Markov models (HMMs), on the other hand, are such that the number of underlying random variables changes depending on the desired length (which can be a random variable), and HMMs are applicable even without knowing this length as they can be extended indeﬁnitely using online inference. HMMs have been generalized to dynamic Bayesian networks (DBNs) and temporal conditional random ﬁelds (CRFs), where an underlying set of variables gets repeated as needed to ﬁll any ﬁnite but unbounded length. Probabilistic relational models (PRMs) [5] allow for a more complex template that can be expanded in multiple dimensions simultaneously. An attribute common to all of the above cases is that the speciﬁcation of rules for expanding any particular instance of a model is ﬁnite. In other words, these forms of GM allow the speciﬁcation of models with an unlimited number of random variables (RVs) using a ﬁnite description. This is achieved using parameter tying, so while the number of RVs increases without bound, the number of parameters does not. In this paper, we introduce a new class of model we call multi-dynamic Bayesian networks. MDBNs are motivated by our research into the application of graphical models to the domain of statistical machine translation (MT) and they have two key attributes from the graphical modeling perspective. First, an MDBN generalizes a DBN in that there are multiple “streams” of variables that can get unrolled, but where each stream may be unrolled by a differing amount. In the most general case, connecting these different streams together would require the speciﬁcation of conditional probabil- ity tables with a varying and potentially unlimited number of parents. To avoid this problem and retain the template’s ﬁnite description length, we utilize a switching parent functionality (also called value-speciﬁc independence). Second, in order to capture the notion of fertility in MT-systems (deﬁned later in the text), we employ a form of existence uncertainty [7] (that we call switching existence), whereby the existence of a given random variable might depend on the value of other random variables in the network. Being fully propositional, MDBNs lie between DBNs and PRMs in terms of expressiveness. While PRMs are capable of describing any MDBN, there are, in general, advantages to restricting ourselves to a more speciﬁc class of model. For example, in the DBN case, it is possible to provide a bound on inference costs just by looking at attributes of the DBN template only (e.g., the left or right interfaces [12, 2]). Restricting the model can also make it simpler to use in practice. MDBNs are still relatively simple, while at the same time making possible the easy expression of MT systems, and opening doors to novel forms of probabilistic inference as we show below. In section 2, we introduce MDBNs, and describe their application to machine translation showing how it is possible to represent even complex MT systems. In section 3, we describe MDBN learning and decoding algorithms. In section 4, we present experimental results in the area of statistical machine translation, and future work is discussed in section 5. 2 MDBNs A standard DBN [4] template consists of a directed acyclic graph G = (V, E) = (V1 ∪ V2 , E1 ∪ → E2 ∪ E2 ) with node set V and edge set E. For t ∈ {1, 2}, the sets Vt are the nodes at slice t, Et → are the intra-slice edges between nodes in Vt , and Et are the inter-slice edges between nodes in V1 and V2 . To unroll a DBN to length T , the nodes V2 along with the edges adjacent to any node in V2 are cloned T − 1 times (where parameters of cloned variables are constrained to be the same as the template) and re-connected at the corresponding places. An MDBN with K streams consists of the union of K DBN templates along with a template structure specifying rules to connect the various streams together. An MDBN template is a directed graph (k) G = (V, E) = ( V (k) , E (k) ∪ E ) k (k) (k) th k (k) where (V , E ) is the k DBN, and the edges E are rules specifying how to connect stream k to the other streams. These rules are general in that they specify the set of edges for all values of Tk . There can be arbitrary nesting of the streams such as, for example, it is possible to specify a model that can grow along several dimensions simultaneously. An MDBN also utilizes “switching existence”, meaning some subset of the variables in V bestow existence onto other variables in the network. We call these variables existence bestowing (or ebnodes). The idea of bestowing existence is well deﬁned over a discrete space, and is not dissimilar to a variable length DBN. For example, we may have a joint distribution over lengths as follows: p(X1 , . . . , XN , N ) = p(X1 , . . . , Xn |N = n)p(N = n) where here N is an eb-node that determines the number of other random variables in the DGM. Our notion of eb-nodes allows us to model certain characteristics found within machine translation systems, such as “fertility” [3], where a given English word is cloned a random number of times in the generative process that explains a translation from French into English. This random cloning might happen simultaneously at all points along a given MDBN stream. This means that even for a given ﬁxed stream length Ti = ti , each stream could have a randomly varying number of random variables. Our graphical notation for eb-nodes consists of the eb-node as a square box containing variables whose existence is determined by the eb-node. We start by providing a simple example of an expanded MDBN for three well known MT systems, namely the IBM models 1 and 2 [3], and the “HMM” model [15].1 We adopt the convention in [3] that our goal is to translate from a string of French words F = f of length M = m into a string of English words E = e of length L = l — of course these can be any two languages. The basic generative (noisy channel) approach when translating from French to English is to represent the joint 1 We will refer to it as M-HMM to avoid confusion with regular HMMs. distribution P (f , e) = P (f |e)P (e). P (e) is a language model specifying the prior over the word string e. The key goal is to produce a ﬁnite-description length representation for P (f |e) where f and e are of arbitrary length. A hidden alignment string, a, speciﬁes how the English words align to the French word, leading to P (f |e) = a P (f , a|e). Figure 1(a) is a 2-stream MDBN expanded representation of the three models, in this case ℓ = 4 and m = 3. As shown, it appears that the fan-in to node fi will be ℓ and thus will grow without bound. However, a switching mechanism whereby P (fi |e, ai ) = P (fi |eai ) limits the number of parameters regardless of L. This means that the alignment variable ai indicates the English word eai that should be aligned to French word fi . The variable e0 is a null word that connects to French words not explained by any of e1 , . . . , eℓ . The graph expresses all three models — the difference is that, in Models 1 and 2, there are no edges between aj and aj+1 . In Model 1, p(aj = ℓ) is uniform on the set {1, . . . , L}; in Model 2, the distribution over aj is a function only of its position j, and on the English and French lengths ℓ and m respectively. In the M-HMM model, the ai variables form a ﬁrst order Markov chain. l e0 ℓ e1 e3 e2 e1 e4 e2 e3 φ1 φ2 φ3 m’ φ0 τ01 a1 f2 a2 f3 a3 m (a) Models 1,2 and M-HMM τ12 τ13 τ21 π02 π11 π12 π13 π21 f2 f3 f4 f5 f6 a1 u v τ11 f1 f1 τ02 a2 a3 a4 a5 a6 π01 w y x m (b) Expanded M3 graph Figure 1: Expanded 2-stream MDBN description of IBM Models 1 and 2, and the M-HMM model for MT; and the expanded MDBN description of IBM Model 3 with fertility assignment φ0 = 2, φ1 = 3, φ2 = 1, φ3 = 0. From the above, we see that it would be difﬁcult to express this model graphically using a standard DBN since L and M are unequal random variables. Indeed, there are two DBNs in operation, one consisting of the English string, and the other consisting of the French string and its alignment. Moreover, the fully connected structure of the graph in the ﬁgure can represent the appropriate family of model, but it also represents models whose parameter space grows without bound — the switching function allows the model template to stay ﬁnite regardless of L and M . With our MDBN descriptive abilities complete, it is now possible to describe the more complex IBM models 3, and 4[3] (an MDBN for Model3 is depicted in ﬁg. 1(b)). The top most random variable, ℓ, is a hidden switching existence variable corresponding to the length of the English string. The box abutting ℓ includes all the nodes whose existence depends on the value of ℓ. In the ﬁgure, ℓ = 3, thus resulting in three English words e1 , e2 , and e3 connected using a second-order Markov chain. To each English word ei corresponds a conditionally dependent fertility eb-node φi , which indicates how many times ei is used by words in the French string. Each φi in turn controls the existence of a set of variables under it. Given the fertilities (the ﬁgure depicts the case φ1 = 3, φ2 = 1, φ3 = 0), for each word ei , φi French word variables are granted existence and are denoted by τi1 , τi2 , . . . , τiφi , what is called the tablet [3] of ei . The values taken by the τ variables need to match the actual observed French sequence f1 , . . . , fm . This is represented as a shared constraint between all the f , π, and τ variables which have incoming edges into the observed variable v. v’s conditional probability table is such that it is one only when the associated constraint is satisﬁed2 . The variable 2 This type of encoding of constraints corresponds to the standard mechanism used by Pearl [14]. A naive implementation, however, would enumerate a number of conﬁgurations exponential in the number of constrained variables, while typically only a small fraction of the conﬁgurations would have positive probability. πi,k ∈ {1, . . . , m} is a switching dependency parent with respect to the constraint variable v and determines which fj participates in an equality constraint with τi,k . The bottom variable m is a switching existence node (observed to be 6 in the ﬁgure) with corresponding French word sequence and alignment variables. The French sequence participates in the v constraint described above, while the alignment variables aj ∈ {1, . . . , ℓ}, j ∈ 1, . . . , m constrain the fertilities to take their unique allowable values (for the given alignment). Alignments also restrict the domain of permutation variables, π, using the constraint variable x. Finally, the domain size of each aj has to lie in the interval [0, ℓ] and that is enforced by the variable u. The dashed edges connecting the alignment a variables represent an extension to implement an M3/M-HMM hybrid. ℓ The null submodel involving the deterministic node m′ (= i=1 φi ) and eb-node φ0 accounts for French words that are not explained by any of the English words e1 , . . . , eℓ . In this submodel, successive permutation variables are ordered and this constraint is implemented using the observed child w of π0i and π0(i+1) . Model 4 [3] is similar to Model 3 except that the former is based on a more elaborate distortion model that uses relative instead of absolute positions both within and between tablets. 3 Inference, Parameter Estimation and MPE Multi-dynamic Bayesian Networks are amenable to any type of inference that is applicable to regular Bayesian networks as long as switching existence relationships are respected and all the constraints (aggregation for example) are satisﬁed. Unfortunately DBN inference procedures that take advantage of the repeatable template and can preprocess it ofﬂine, are not easy to apply to MDBNs. A case in point is the Junction Tree algorithm [11]. Triangulation algorithms exist that create an ofﬂine triangulated version of the input graph and do not re-triangulate it for each different instance of the input data [12, 2]. In MDBNs, due to the ﬂexibility to unroll templates in several dimensions and to specify dependencies and constraints spanning the entire unrolled graph, it is not obvious how we can exploit any repetitive patterns in a Junction Tree-style ofﬂine triangulation of the graph template. In section 4, we discuss sampling inference methods we have used. Here we discuss our extension to a backtracking search algorithm with the same performance guarantees as the JT algorithm, but with the advantage of easily handling determinism, existence uncertainty, and constraints, both learned and explicitly stated. Value Elimination (VE) ([1]), is a backtracking Bayesian network inference technique that caches factors associated with portions of the search tree and uses them to avoid iterating again over the same subtrees. We follow the notation introduced in [1] and refer the reader to that paper for details about VE inference. We have extended the VE inference approach to handle explicitly encoded constraints, existence uncertainty, and to perform approximate local domain pruning (see section 4). We omit these details as well as others in the original paper and brieﬂy describe the main data structure required by VE and sketch the algorithm we refer to as FirstPass (ﬁg. 1) since it constitutes the ﬁrst step of the learning procedure, our main contribution in this section. A VE factor, F , is such that we can write the following marginal of the joint distribution P (X = x, Y = y, Z) = F.val × f (Z) X=x such that (X∪Y)∩Z = ∅, F.val is a constant, and f (Z) a function of Z only. Y is a set of variables previously instantiated in the current branch of search tree to the value vector y. The pair (Y, y) is referred to as a dependency set (F.Dset). X is referred to as a subsumed set (F.Sset). By caching the tuple (F.Dset, F.Sset, F.val), we avoid recomputing the marginal again whenever (1) F.Dset is active, meaning all nodes stored in F.Dset are assigned their cached values in the current branch of the search tree; and (2) none of the variables in F.Sset are assigned yet. FirstPass (alg. 1) visits nodes in the graph in Depth First fashion. In line 7, we get the values of all Newly Single-valued (NSV) CPTs i.e., CPTs that involve the current node, V , and in which all We use a general directed domain pruning constraint. Deterministic relationships then become a special case of our constraint whereby the domain of the child variable is constrained to a single value with probability one. Variable traversal order: A, B, C, and D. Factors are numbered by order of creation. *Fi denotes the activation of factor i. Tau values propagated recursively F7: Dset={} Sset={A,B,C,D} val=P(E=e) F7.tau = 1.0 = P(Evidence)/F7.val A F5: Dset={A=0} Sset={B,C,D} F2 D *F1 *F2 Factor values needed for c(A=0) and c(C=0,B=0) computation: F5.val=P(B=0|A=0)*F3.val+P(B=1|A=0)*F4.val F3.val=P(C=0|B=0)*F1.val+P(C=1|B=0)*F2.val F4.val=P(C=0|B=1)*F1.val+P(C=1|B=1)*F2.val F1.val=P(D=0|C=0)P(E=e|D=0)+P(D=1|C=0)P(E=e|D=1) F2.val=P(D=0|C=1)P(E=e|D=0)+P(D=1|C=1)P(E=e|D=1) First pass C *F3 *F4 Second pass D B F4 C F6.tau = F7.tau * P(A=1) 1 B F3: Dset={B=0} Sset={C,D} F1 F5.tau = F7.tau * P(A=0) F6 0 F3.tau = F5.tau * P(B=0|A=0) + F6.tau * P(B=0|A=1) = P(B=0) F4.tau = F5.tau * P(B=1|A=0) + F6.tau * P(B=1|A=1) = P(B=1) F1.tau = F3.tau * P(C=0|B=0) + F4.tau * P(C=0|B=1) = P(C=0) F2.tau = F3.tau * P(C=1|B=0) + F4.tau * P(C=1|B=1) = P(C=1) c(A=0)=(1/P(e))*(F7.tau*P(A=0)*F5.val)=(1/P(e))(P(A=0)*P(E=e|A=0))=P(A=0|E=e) c(C=0,B=0)=(1/P(e))*F3.tau*P(C=0|B=0)*F1.val =(1/P(e) * (P(A=0,B=0)+P(A=1,B=0)) * P(C=0|B=0) * F1.val =(1/P(e)) * P(B=0) * P(C=0|B=0) * F1.val =(1/P(e)) * P(B=0) * P(C=0|B=0) * F1.val =(1/P(e)) * P(C=0,B=0) * F1.val =P(C=0,B=0,E=e)/P(e)=P(C=0,B=0|E=e) Figure 2: Learning example using the Markov chain A → B → C → D → E, where E is observed. In the ﬁrst pass, factors (Dset, Sset and val) are learned in a bottom up fashion. Also, the normalization constant P (E = e) (probability of evidence) is obtained. In the second pass, tau values are updated in a top-down fashion and used to calculate expected counts c(F.head, pa(F.head)) corresponding to each F.head (the ﬁgure shows the derivations for (A=0) and (C=0,B=0), but all counts are updated in the same pass). other variables are already assigned (these variables and their values are accumulated into Dset). We also check for factors that are active, multiply their values in, and accumulate subsumed vars in Sset (to avoid branching on them). In line 10, we add V to the Sset. In line 11, we cache a new factor F with value F.val = sum. We store V into F.head, a pointer to the last variable to be inserted into F.Sset, and needed for parameter estimation described below. F.Dset consists of all the variables, except V , that appeared in any NSV CPT or the Dset of an activated factor at line 6. Regular Value Elimination is query-based, similar to variable elimination and recursive conditioning—what this means is that to answer a query of the type P (Q|E = e), where Q is query variable and E a set of evidence nodes, we force Q to be at the top of the search tree, run the backtracking algorithm and then read the answers to the queries P (Q = q|E = e), q ∈ Dom[Q], along each of the outgoing edges of Q. Parameter estimation would require running a number of queries on the order of the number of parameters to estimate. We extend VE into an algorithm that allows us to obtain Expectation Maximization sufﬁcient statistics in a single run of Value Elimination plus a second pass, which can never take longer than the ﬁrst one (and in practice is much faster). This two-pass procedure is analogous to the collect-distribute evidence procedure in the Junction Tree algorithm, but here we do this via a search tree. Let θX=x|pa(X)=y be a parameter associated with variable X with value x and parents Y = pa(X) when they have value y. Assuming a maximum likelihood learning scenario3 , to estimate θX=x|pa(X)=y , we need to compute f (X = x, pa(X) = y, E = e) = P (W, X = x, pa(X) = y, E = e) W\{X,pa(X)} which is a sum of joint probabilities of all conﬁgurations that are consistent with the assignment {X = x, pa(X) = y}. If we were to turn off factor caching, we would enumerate all such variable conﬁgurations and could compute the sum. When standard VE factors are used, however, this is no longer possible whenever X or any of its parents becomes subsumed. Fig. 2 illustrates an example of a VE tree and the factors that are learned in the case of a Markov chain with an evidence node at the end. We can readily estimate the parameters associated with variables A and B as they are not subsumed along any branch. C and D become subsumed, however, and we cannot obtain the correct counts along all the branches that would lead to C and D in the full enumeration case. To address this issue, we store a special value, F.tau, in each factor. F.tau holds the sum over all path probabilities from the ﬁrst level of the search tree to the level at which the factor F was 3 For Bayesian networks the likelihood function decomposes such that maximizing the expectation of the complete likelihood is equivalent to maximizing the “local likelihood” of each variable in the network. either created or activated. For example, F 6.tau in ﬁg. 2 is simply P (A = 1). Although we can compute F 3.tau directly, we can also compute it recursively using F 5.tau and F 6.tau as shown in the ﬁgure. This is because both F 5 and F 6 subsume F 3: in the context {F 5.Dset}, there exists a (unique) value dsub of F 5.head4 s.t. F 3 becomes activable. Likewise for F 6. We cannot compute F 1.tau directly, but we can, recursively, from F 3.tau and F 4.tau by taking advantage of a similar subsumption relationship. In general, we can show that the following recursive relationship holds: F pa .tau × N SVF pa .head=dsub × F.tau ← F pa ∈F pa Fact .val F.val Fact ∈Fact (1) where F pa is the set of factors that subsume F , Fact is the set of all factors (including F ) that become active in the context of {F pa .Dset, F pa .head = dsub } and N SVF pa .head=dsub is the product of all newly single valued CPTs under the same context. For top-level factors (not subsumed by any factor), F.tau = Pevidence /F.val, which is 1.0 when there is a unique top-level factor. Alg. 2 is a simple recursive computation of eq. 1 for each factor. We visit learned factors in the reverse order in which they were learned to ensure that, for any factor F ′ , F ′ .tau is incremented (line 13) by any F that might have activated F ′ (line 12). For example, in ﬁg. 2, F 4 uses F 1 and F 2, so F 4.tau needs to be updated before F 1.tau and F 2.tau. In line 11, we can increment the counts for any NSV CPT entries since F.tau will account for the possible ways of reaching the conﬁguration {F.Dset, F.head = d} in an equivalent full enumeration tree. Algorithm 1: FirstPass(level) 1 2 3 4 5 6 7 8 9 10 Input: Graph G Output: A list of learned factors and Pevidence Select var V to branch on if V ==NONE then return Sset={}, Dset={} for d ∈ Dom[V ] do V ←d prod = productOfAllNSVsAndActiveFactors(Dset, Sset) if prod != 0 then FirstPass(level+1) sum += prod Sset = Sset ∪ {V } cacheNewFactor(F.head ← V ,F.val ← sum, F.Sset ← Sset, F.Dset ← Dset); Algorithm 2: SecondPass() 1 2 3 4 5 6 7 8 9 10 11 12 13 Input: F : List of factors in the reverse order learned in the ﬁrst pass and Pevidence . Result: Updated counts foreach F ∈ F do if F.Dset = {} then F.tau ← Pevidence /F.val else F.tau ← 0.0 Assign vars in F.Dset to their values V ← F.head (last node to have been subsumed in this factor) foreach d ∈ Dom[V ] do prod = productOfAllNSVsAndActiveFactors() prod∗ = F.tau foreach newly single-valued CPT C do count(C.child,C.parents)+=prod/Pevidence F ′ =getListOfActiveFactors() for F ′ ∈ F ′ do F ′ .tau+ = prod/F ′ .val Most Probable Explanation We compute MPE using a very similar two-pass algorithm. In the ﬁrst pass, factors are used to store a maximum instead of a summation over variables in the Sset. We also keep track of the value of F.head at which the maximum is achieved. In the second pass, we recursively ﬁnd the optimal variable conﬁguration by following the trail of factors that are activated when we assign each F.head variable to its maximum value starting from the last learned factor. 4 Recall, F.head is the last variable to be added to a newly created factor in line 10 of alg. 1 4 MACHINE TRANSLATION WORD ALIGNMENT EXPERIMENTS A major motivation for pursuing the type of representation and inference described above is to make it possible to solve computationally-intensive real-world problems using large amounts of data, while retaining the full generality and expressiveness afforded by the MDBN modeling language. In the experiments below we compare running times of MDBNs to GIZA++ on IBM Models 1 through 4 and the M-HMM model. GIZA++ is a special-purpose optimized MT word alignment C++ tool that is widely used in current state-of-the-art phrase-based MT systems [10] and at the time of this writing is the only publicly available software that implements all of the IBM Models. We test on French-English 107 hand-aligned sentences5 from a corpus of the European parliament proceedings (Europarl [9]) and train on 10000 sentence pairs from the same corpus and of maximum number of words 40. The Alignment Error Rate (AER) [13] evaluation metric quantiﬁes how well the MPE assignment to the hidden alignment variables matches human-generated alignments. Several pruning and smoothing techniques are used by GIZA and MDBNs. GIZA prunes low lexical (P (f |e)) probability values and uses a default small value for unseen (or pruned) probability table entries. For models 3 and 4, for which there is no known polynomial time algorithm to perform the full E-step or compute MPE, GIZA generates a set of high probability alignments using an MHMM and hill-climbing and collects EM counts over these alignments using M3 or M4. For MDBN models we use the following pruning strategy: at each level of the search tree we prune values which, together, account for the lowest speciﬁed percentage of the total probability mass of the product of all newly active CPTs in line 6 of alg. 1. This is a more effective pruning than simply removing low-probability values of each CPD because it factors in the joint contribution of multiple active variables. Table 1 shows a comparison of timing numbers obtained GIZA++ and MDBNs. The runtime numbers shown are for the combined tasks of training and decoding; however, training time dominates given the difference in size between train and test sets. For models 1 and 2 neither GIZA nor MDBNs perform any pruning. For the M-HMM, we prune 60% of probability mass at each level and use a Dirichlet prior over the alignment variables such that long-range transitions are exponentially less likely than shorter ones.6 This model achieves similar times and AER to GIZA’s. Interestingly, without any pruning, the MDBN M-HMM takes 160 minutes to complete while only marginally improving upon the pruned model. Experimenting with several pruning thresholds, we found that AER would worsen much more slowly than runtime decreases. Models 3 and 4 have treewidth equal to the number of alignment variables (because of the global constraints tying them) and therefore require approximate inference. Using Model 3, and a drastic pruning threshold that only keeps the value with the top probability at each level, we were able to achieve an AER not much higher than GIZA’s. For M4, it achieves a best AER of 31.7% while we do not improve upon Model3, most likely because a too restrictive pruning. Nevertheless, a simple variation on Model3 in the MDBN framework achieves a lower AER than our regular M3 (with pruning still the same). The M3-HMM hybrid model combines the Markov alignment dependencies from the M-HMM model with the fertility model of M3. MCMC Inference Sampling is widely used for inference in high-treewidth models. Although MDBNs support Likelihood Weighing, it is very inefﬁcient when the probability of evidence is very small, as is the case in our MT models. Besides being slow, Markov chain Monte Carlo can be problematic when the joint distribution is not positive everywhere, in particular in the presence of determinism and hard constraints. Techniques such as blocking Gibbs sampling [8] try to address the problem. Often, however, one has to carefully choose a problem-dependent proposal distribution. We used MCMC to improve training of the M3-HMM model. We were able to achieve an AER of 32.8% (down from 39.1%) but using 400 minutes of uniprocessor time. 5 CONCLUSION The existing classes of graphical models are not ideally suited for representing SMT models because “natural” semantics for specifying the latter combine ﬂavors of different GM types on top of standard directed Bayesian network semantics: switching parents found in Bayesian Multinets [6], aggregation relationships such as in Probabilistic Relational Models [5], and existence uncertainty [7]. We 5 Available at http://www.cs.washington.edu/homes/karim French and English have similar word orders. On a different language pair, a different prior might be more appropriate. With a uniform prior, the MDBN M-HMM has 36.0% AER. 6 Model Init M1 M2 M-HMM M3 M4 M3-HMM GIZA++ M1 M-HMM 1m45s (47.7%) N/A 2m02s (41.3%) N/A 4m05s (35.0%) N/A 2m50 (45%) 5m20s (38.5%) 5m20s (34.8%) 7m45s (31.7%) N/A MDBN M1 3m20s (48.0%) 5m30s (41.0%) 4m15s (33.0%) 12m (43.6%) 25m (43.6%) 9m30 (41.0%) M-HMM N/A N/A N/A 9m (42.5%) 23m (42.6%) 9m15s (39.1%) MCMC 400m (32.8%) Table 1: MDBN VE-based learning versus GIZA++ timings and %AER using 5 EM iterations. The columns M1 and M-HMM correspond to the model that is used to initialize the model in the corresponding row. The last row is a hybrid Model3-HMM model that we implemented using MDBNs and is not expressible using GIZA. have introduced a generalization of dynamic Bayesian networks to easily and concisely build models consisting of varying-length parallel asynchronous and interacting data streams. We have shown that our framework is useful for expressing various statistical machine translation models. We have also introduced new parameter estimation and decoding algorithms using exact and approximate searchbased probability computation. While our timing results are not yet as fast as a hand-optimized C++ program on the equivalent model, we have shown that even in this general-purpose framework of MDBNs, our timing numbers are competitive and usable. Our framework can of course do much more than the IBM and HMM models. One of our goals is to use this framework to rapidly prototype novel MT systems and develop methods to statistically induce an interlingua. We also intend to use MDBNs in other domains such as multi-party social interaction analysis. References [1] F. Bacchus, S. Dalmao, and T. Pitassi. Value elimination: Bayesian inference via backtracking search. In UAI-03, pages 20–28, San Francisco, CA, 2003. Morgan Kaufmann. [2] J. Bilmes and C. Bartels. On triangulating dynamic graphical models. In Uncertainty in Artiﬁcial Intelligence: Proceedings of the 19th Conference, pages 47–56. Morgan Kaufmann, 2003. [3] P. F. Brown, J. Cocke, S. A. Della Piettra, V. J. Della Piettra, F. Jelinek, J. D. Lafferty, R. L. Mercer, and P. S. Roossin. A statistical approach to machine translation. Computational Linguistics, 16(2):79–85, June 1990. [4] T. Dean and K. Kanazawa. Probabilistic temporal reasoning. AAAI, pages 524–528, 1988. [5] N. Friedman, L. Getoor, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In IJCAI, pages 1300–1309, 1999. [6] D. Geiger and D. Heckerman. Knowledge representation and inference in similarity networks and Bayesian multinets. Artif. Intell., 82(1-2):45–74, 1996. [7] L. Getoor, N. Friedman, D. Koller, and B. Taskar. Learning probabilistic models of link structure. Journal of Machine Learning Research, 3(4-5):697–707, May 2003. [8] C. Jensen, A. Kong, and U. Kjaerulff. Blocking Gibbs sampling in very large probabilistic expert systems. In International Journal of Human Computer Studies. Special Issue on Real-World Applications of Uncertain Reasoning., 1995. [9] P. Koehn. Europarl: A multilingual corpus for evaluation of machine http://www.isi.edu/koehn/publications/europarl, 2002. translation. [10] P. Koehn, F. Och, and D. Marcu. Statistical phrase-based translation. In NAACL/HLT 2003, 2003. [11] S. Lauritzen. Graphical Models. Oxford Science Publications, 1996. [12] K. Murphy. Dynamic Bayesian Networks: Representation, Inference and Learning. PhD thesis, U.C. Berkeley, Dept. of EECS, CS Division, 2002. [13] F. J. Och and H. Ney. Improved statistical alignment models. In ACL, pages 440–447, Oct 2000. [14] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 2nd printing edition, 1988. [15] S. Vogel, H. Ney, and C. Tillmann. HMM-based word alignment in statistical translation. In Proceedings of the 16th conference on Computational linguistics, pages 836–841, Morristown, NJ, USA, 1996.

4 0.12858744 92 nips-2006-High-Dimensional Graphical Model Selection Using $\ell 1$-Regularized Logistic Regression

Author: Martin J. Wainwright, John D. Lafferty, Pradeep K. Ravikumar

Abstract: We focus on the problem of estimating the graph structure associated with a discrete Markov random ﬁeld. We describe a method based on 1 regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an 1 -constraint. Our framework applies to the high-dimensional setting, in which both the number of nodes p and maximum neighborhood sizes d are allowed to grow as a function of the number of observations n. Our main result is to establish suﬃcient conditions on the triple (n, p, d) for the method to succeed in consistently estimating the neighborhood of every node in the graph simultaneously. Under certain mutual incoherence conditions analogous to those imposed in previous work on linear regression, we prove that consistent neighborhood selection can be obtained as long as the number of observations n grows more quickly than 6d6 log d + 2d5 log p, thereby establishing that logarithmic growth in the number of samples n relative to graph size p is suﬃcient to achieve neighborhood consistency. Keywords: Graphical models; Markov random ﬁelds; structure learning; 1 -regularization; model selection; convex risk minimization; high-dimensional asymptotics; concentration. 1

5 0.11141638 115 nips-2006-Learning annotated hierarchies from relational data

Author: Daniel M. Roy, Charles Kemp, Vikash K. Mansinghka, Joshua B. Tenenbaum

Abstract: The objects in many real-world domains can be organized into hierarchies, where each internal node picks out a category of objects. Given a collection of features and relations deﬁned over a set of objects, an annotated hierarchy includes a speciﬁcation of the categories that are most useful for describing each individual feature and relation. We deﬁne a generative model for annotated hierarchies and the features and relations that they describe, and develop a Markov chain Monte Carlo scheme for learning annotated hierarchies. We show that our model discovers interpretable structure in several real-world data sets.

6 0.11041591 87 nips-2006-Graph Laplacian Regularization for Large-Scale Semidefinite Programming

7 0.1077008 40 nips-2006-Bayesian Detection of Infrequent Differences in Sets of Time Series with Shared Structure

8 0.10634274 201 nips-2006-Using Combinatorial Optimization within Max-Product Belief Propagation

9 0.10522375 3 nips-2006-A Complexity-Distortion Approach to Joint Pattern Alignment

10 0.1026308 172 nips-2006-Scalable Discriminative Learning for Natural Language Parsing and Translation

11 0.096315317 14 nips-2006-A Small World Threshold for Economic Network Formation

12 0.092611551 67 nips-2006-Differential Entropic Clustering of Multivariate Gaussians

13 0.089422189 35 nips-2006-Approximate inference using planar graph decomposition

14 0.089036748 38 nips-2006-Automated Hierarchy Discovery for Planning in Partially Observable Environments

15 0.087861657 200 nips-2006-Unsupervised Regression with Applications to Nonlinear System Identification

16 0.08671578 57 nips-2006-Conditional mean field

17 0.0807124 20 nips-2006-Active learning for misspecified generalized linear models

18 0.079138756 96 nips-2006-In-Network PCA and Anomaly Detection

19 0.0780598 41 nips-2006-Bayesian Ensemble Learning

20 0.075747289 98 nips-2006-Inferring Network Structure from Co-Occurrences

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.226), (1, 0.015), (2, 0.018), (3, -0.109), (4, 0.135), (5, 0.006), (6, 0.1), (7, 0.034), (8, -0.012), (9, -0.111), (10, -0.03), (11, -0.13), (12, 0.098), (13, 0.126), (14, -0.035), (15, -0.177), (16, -0.008), (17, 0.135), (18, 0.101), (19, 0.222), (20, -0.075), (21, 0.053), (22, -0.082), (23, -0.033), (24, -0.157), (25, -0.04), (26, -0.026), (27, -0.052), (28, -0.031), (29, 0.094), (30, -0.065), (31, 0.062), (32, 0.013), (33, -0.083), (34, 0.028), (35, 0.136), (36, 0.067), (37, -0.031), (38, -0.009), (39, -0.021), (40, 0.076), (41, 0.003), (42, 0.169), (43, -0.033), (44, -0.049), (45, -0.037), (46, 0.093), (47, -0.026), (48, -0.127), (49, -0.097)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97861147 69 nips-2006-Distributed Inference in Dynamical Systems

Author: Stanislav Funiak, Carlos Guestrin, Rahul Sukthankar, Mark A. Paskin

2 0.68551332 139 nips-2006-Multi-dynamic Bayesian Networks

Author: Karim Filali, Jeff A. Bilmes

3 0.50456136 92 nips-2006-High-Dimensional Graphical Model Selection Using $\ell 1$-Regularized Logistic Regression

Author: Martin J. Wainwright, John D. Lafferty, Pradeep K. Ravikumar

4 0.50134176 190 nips-2006-The Neurodynamics of Belief Propagation on Binary Markov Random Fields

Author: Thomas Ott, Ruedi Stoop

Abstract: We rigorously establish a close relationship between message passing algorithms and models of neurodynamics by showing that the equations of a continuous Hopﬁeld network can be derived from the equations of belief propagation on a binary Markov random ﬁeld. As Hopﬁeld networks are equipped with a Lyapunov function, convergence is guaranteed. As a consequence, in the limit of many weak connections per neuron, Hopﬁeld networks exactly implement a continuous-time variant of belief propagation starting from message initialisations that prevent from running into convergence problems. Our results lead to a better understanding of the role of message passing algorithms in real biological neural networks.

5 0.48291114 201 nips-2006-Using Combinatorial Optimization within Max-Product Belief Propagation

Author: Daniel Tarlow, Gal Elidan, Daphne Koller, John C. Duchi

Abstract: In general, the problem of computing a maximum a posteriori (MAP) assignment in a Markov random ﬁeld (MRF) is computationally intractable. However, in certain subclasses of MRF, an optimal or close-to-optimal assignment can be found very efﬁciently using combinatorial optimization algorithms: certain MRFs with mutual exclusion constraints can be solved using bipartite matching, and MRFs with regular potentials can be solved using minimum cut methods. However, these solutions do not apply to the many MRFs that contain such tractable components as sub-networks, but also other non-complying potentials. In this paper, we present a new method, called C OMPOSE, for exploiting combinatorial optimization for sub-networks within the context of a max-product belief propagation algorithm. C OMPOSE uses combinatorial optimization for computing exact maxmarginals for an entire sub-network; these can then be used for inference in the context of the network as a whole. We describe highly efﬁcient methods for computing max-marginals for subnetworks corresponding both to bipartite matchings and to regular networks. We present results on both synthetic and real networks encoding correspondence problems between images, which involve both matching constraints and pairwise geometric constraints. We compare to a range of current methods, showing that the ability of C OMPOSE to transmit information globally across the network leads to improved convergence, decreased running time, and higher-scoring assignments.

6 0.46089476 172 nips-2006-Scalable Discriminative Learning for Natural Language Parsing and Translation

7 0.455235 74 nips-2006-Efficient Structure Learning of Markov Networks using $L 1$-Regularization

8 0.4483996 40 nips-2006-Bayesian Detection of Infrequent Differences in Sets of Time Series with Shared Structure

9 0.44612026 98 nips-2006-Inferring Network Structure from Co-Occurrences

10 0.44414496 115 nips-2006-Learning annotated hierarchies from relational data

11 0.43960589 87 nips-2006-Graph Laplacian Regularization for Large-Scale Semidefinite Programming

12 0.42111483 41 nips-2006-Bayesian Ensemble Learning

13 0.41699237 180 nips-2006-Speakers optimize information density through syntactic reduction

14 0.36870873 112 nips-2006-Learning Nonparametric Models for Probabilistic Imitation

15 0.36559513 3 nips-2006-A Complexity-Distortion Approach to Joint Pattern Alignment

16 0.35941902 96 nips-2006-In-Network PCA and Anomaly Detection

17 0.35847199 200 nips-2006-Unsupervised Regression with Applications to Nonlinear System Identification

18 0.35513183 57 nips-2006-Conditional mean field

19 0.35220331 67 nips-2006-Differential Entropic Clustering of Multivariate Gaussians

20 0.33725539 199 nips-2006-Unsupervised Learning of a Probabilistic Grammar for Object Detection and Parsing

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(1, 0.055), (3, 0.026), (7, 0.048), (9, 0.023), (20, 0.014), (22, 0.045), (44, 0.59), (57, 0.053), (65, 0.033), (69, 0.028), (71, 0.014)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9853915 69 nips-2006-Distributed Inference in Dynamical Systems

Author: Stanislav Funiak, Carlos Guestrin, Rahul Sukthankar, Mark A. Paskin

2 0.94315624 96 nips-2006-In-Network PCA and Anomaly Detection

Author: Ling Huang, Xuanlong Nguyen, Minos Garofalakis, Michael I. Jordan, Anthony Joseph, Nina Taft

Abstract: We consider the problem of network anomaly detection in large distributed systems. In this setting, Principal Component Analysis (PCA) has been proposed as a method for discovering anomalies by continuously tracking the projection of the data onto a residual subspace. This method was shown to work well empirically in highly aggregated networks, that is, those with a limited number of large nodes and at coarse time scales. This approach, however, has scalability limitations. To overcome these limitations, we develop a PCA-based anomaly detector in which adaptive local data ﬁlters send to a coordinator just enough data to enable accurate global detection. Our method is based on a stochastic matrix perturbation analysis that characterizes the tradeoff between the accuracy of anomaly detection and the amount of data communicated over the network.

3 0.93983448 116 nips-2006-Learning from Multiple Sources

Author: Koby Crammer, Michael Kearns, Jennifer Wortman

Abstract: We consider the problem of learning accurate models from multiple sources of “nearby” data. Given distinct samples from multiple data sources and estimates of the dissimilarities between these sources, we provide a general theory of which samples should be used to learn models for each source. This theory is applicable in a broad decision-theoretic learning framework, and yields results for classiﬁcation and regression generally, and for density estimation within the exponential family. A key component of our approach is the development of approximate triangle inequalities for expected loss, which may be of independent interest. 1

4 0.90696985 57 nips-2006-Conditional mean field

Author: Peter Carbonetto, Nando D. Freitas

Abstract: Despite all the attention paid to variational methods based on sum-product message passing (loopy belief propagation, tree-reweighted sum-product), these methods are still bound to inference on a small set of probabilistic models. Mean ﬁeld approximations have been applied to a broader set of problems, but the solutions are often poor. We propose a new class of conditionally-speciﬁed variational approximations based on mean ﬁeld theory. While not usable on their own, combined with sequential Monte Carlo they produce guaranteed improvements over conventional mean ﬁeld. Moreover, experiments on a well-studied problem— inferring the stable conﬁgurations of the Ising spin glass—show that the solutions can be signiﬁcantly better than those obtained using sum-product-based methods. 1

5 0.84339482 139 nips-2006-Multi-dynamic Bayesian Networks

Author: Karim Filali, Jeff A. Bilmes

6 0.68243396 159 nips-2006-Parameter Expanded Variational Bayesian Methods

7 0.67876583 157 nips-2006-PAC-Bayes Bounds for the Risk of the Majority Vote and the Variance of the Gibbs Classifier

8 0.63836467 40 nips-2006-Bayesian Detection of Infrequent Differences in Sets of Time Series with Shared Structure

9 0.62895149 11 nips-2006-A PAC-Bayes Risk Bound for General Loss Functions

10 0.62478036 98 nips-2006-Inferring Network Structure from Co-Occurrences

11 0.62406725 19 nips-2006-Accelerated Variational Dirichlet Process Mixtures

12 0.61234546 85 nips-2006-Geometric entropy minimization (GEM) for anomaly detection and localization

13 0.61144036 125 nips-2006-Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning

14 0.60571998 121 nips-2006-Learning to be Bayesian without Supervision

15 0.59725654 171 nips-2006-Sample Complexity of Policy Search with Known Dynamics

16 0.59162903 109 nips-2006-Learnability and the doubling dimension

17 0.59071863 192 nips-2006-Theory and Dynamics of Perceptual Bistability

18 0.58385485 134 nips-2006-Modeling Human Motion Using Binary Latent Variables

19 0.58276659 193 nips-2006-Tighter PAC-Bayes Bounds

20 0.57422 175 nips-2006-Simplifying Mixture Models through Function Approximation