nips nips2013 nips2013-189 knowledge-graph by maker-knowledge-mining

189 nips-2013-Message Passing Inference with Chemical Reaction Networks

Source: pdf

Author: Nils E. Napp, Ryan P. Adams

Abstract: Recent work on molecular programming has explored new possibilities for computational abstractions with biomolecules, including logic gates, neural networks, and linear systems. In the future such abstractions might enable nanoscale devices that can sense and control the world at a molecular scale. Just as in macroscale robotics, it is critical that such devices can learn about their environment and reason under uncertainty. At this small scale, systems are typically modeled as chemical reaction networks. In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference. In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities. We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations. As with standard sum-product inference, this procedure yields exact results for tree-structured graphs, and approximate solutions for loopy graphs.

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 At this small scale, systems are typically modeled as chemical reaction networks. [sent-8, score-0.932]

2 In this work, we develop a procedure that can take arbitrary probabilistic graphical models, represented as factor graphs over discrete random variables, and compile them into chemical reaction networks that implement inference. [sent-9, score-1.129]

3 In particular, we show that marginalization based on sum-product message passing can be implemented in terms of reactions between chemical species whose concentrations represent probabilities. [sent-10, score-1.12]

4 We show algebraically that the steady state concentration of these species correspond to the marginal distributions of the random variables in the graph and validate the results in simulations. [sent-11, score-0.559]

5 In this work, we develop a chemical reaction network for performing inference in probabilistic graphical models. [sent-19, score-1.023]

6 We show that message passing schemes, such as belief propagation, map relatively straightforwardly onto sets of chemical reactions, which can be thought of as the “assembly language” of both in vitro and in vivo computation at the molecular scale. [sent-20, score-0.569]

7 The long-term possibilities of such technology are myriad: adaptive tissue-sensitive drug delivery, in situ chemical sensing, and identiﬁcation of disease states. [sent-21, score-0.269]

8 Inference can be performed efﬁciently by passing messages (shown as gray arrows) between vertices, see Section 2. [sent-30, score-0.246]

9 Chemical species represent the different components of message vectors. [sent-32, score-0.528]

10 The chemical reaction networks constructed in Section 3 perform the same computation as the sum-product message passing algorithm. [sent-33, score-1.149]

11 A given reaction network can be implemented in different physical systems, e. [sent-35, score-0.727]

12 At the small scales of interest systems are typically modeled as deterministic chemical reaction networks or their stochastic counterparts that explicitly model ﬂuctuations and noise. [sent-38, score-0.983]

13 However, chemical reactions are not only models, but can be thought of as speciﬁcations or abstract computational frameworks themselves. [sent-39, score-0.451]

14 For example, arbitrary reaction networks can be simulated by DNA strand displacement systems [5, 17], where some strands correspond to the chemical species in the specifying reaction network. [sent-40, score-2.14]

15 Reactions rates in these systems can be tuned over many orders of magnitude by adjusting the toehold length of displacement steps, and high order reactions can be approximated by introducing auxiliary species. [sent-41, score-0.236]

16 We take advantage of this abstraction by ”compiling” the sumproduct algorithm for discrete variable factor graphs into a chemical reaction network, where the concentrations of some species represent conditional and marginal distributions of variables in the graph. [sent-42, score-1.592]

17 In some ways, this representation is very natural: while normalization is a constant concern in digital systems, our chemical design conserves species within some subsets and thus implicitly and continuously normalizes its estimates. [sent-43, score-0.672]

18 The computation is complete when the reaction network reaches equilibrium. [sent-44, score-0.727]

19 Variables in the graph can be conditioned upon by adjusting the reaction rates corresponding to unary potentials in the graph. [sent-45, score-0.711]

20 Section 3 introduces notation and concepts for chemical reaction networks. [sent-47, score-0.932]

21 Section 4 shows how inference on factor graphs can be compiled into reaction networks, and in Section 5, we show several example networks and compare the results of molecular simulations to standard digital inference procedures. [sent-48, score-0.973]

22 There are two kinds of messages messages from a factor node to a variable node and messages from a variable node to a factor node. [sent-77, score-0.877]

23 In order to make clear what quantities are represented by chemical species concentrations in Section 4, we use somewhat unconventional notation. [sent-78, score-0.754]

24 The kth entry of the sum (j→n) message from factor node j to variable node n is denoted Sk and the entire Kn -dimensional (j→n) vector is denoted by S . [sent-79, score-0.287]

25 The kth entry of the product message from variable n to factor node j (n→j) is denoted by Pk and the entire Kj -dimensional vector is denoted P(n→j) . [sent-80, score-0.273]

26 Product messages are computed by taking the component-wise product of incoming sum messages (n→j) Pk (j ′ →n) Sk = . [sent-83, score-0.456]

27 (4) j ′ ∈ne(n)\j Up to normalization, the marginals can be computed from the product of incoming sum messages (j→n) Sk . [sent-84, score-0.249]

28 The validity of damped asynchronous sum-product is what enables us to frame the computation as a chemical reaction network. [sent-88, score-0.99]

29 The continuous ODE description of species concentrations that represent messages can be thought of as an inﬁnitesimally small version of damped asynchronous update rules. [sent-89, score-0.768]

30 3 Chemical Reaction Networks The following model describes how a set of M chemical species Z = {Z1 , Z2 , · · · , ZM } interact and their concentrations evolve over time. [sent-90, score-0.754]

31 Each reaction has the general form 3 κ r1 Z1 + r2 Z2 + · · · + rM ZM GGGGGGGB p1 Z1 + p2 Z2 + · · · + pM ZM . [sent-91, score-0.681]

32 The species on the left with non-zero coefﬁcients are called reactants and are consumed during the reaction. [sent-93, score-0.401]

33 The species on the right with non-zero entries are called products and are produced during the reaction. [sent-94, score-0.401]

34 They change the dynamics of a particular reaction without being changed themselves. [sent-100, score-0.702]

35 A reaction network over a given set of species consists of a set of Q reactions R = {R1 , R2 , · · · , RQ }, where each reaction is a triple of reaction parameters (6), Rq = (rq , κq , pq ). [sent-101, score-2.721]

36 (7) For example, in a reaction Rq ∈ R where species Z1 and Z3 form a new chemical species Z2 at a rate of κq , the reactant vector rq is zero everywhere except at rq = rq = 1. [sent-102, score-1.93]

37 In the reaction notation where non-participating 2 species are dropped reaction Rq is can be compactly written as κq Z1 + Z3 GGGGGGGB Z2 . [sent-104, score-1.763]

38 1 Mass Action Kinetics The concentration of each chemical species Zm is denoted by [Zm ]. [sent-106, score-0.691]

39 A reaction network describes the evolution of species concentrations as a set of coupled non-linear differential equations. [sent-107, score-1.23]

40 For each species concentration [Zm ] the rate of change is given by mass action kinetics, Q d[Zm ] κq = dt q=1 M q [Zm′ ]rm′ (pq − rq ). [sent-108, score-0.581]

41 For example, if the only reaction in a network were the second order reaction (8), the concentration dynamics of [Z1 ] would be d[Z1 ] = −κq [Z1 ][Z3 ]. [sent-110, score-1.468]

42 dt (10) Similar to [4] we design reaction networks where the equilibrium concentration of some species corresponds to the results we are interested in computing. [sent-111, score-1.206]

43 The reaction networks in the following section conserve mass and do not require ﬂux in or out of the system, and therefore the solutions are guaranteed to be bounded. [sent-112, score-0.8]

44 While we cannot rule out oscillations in general, the message passing methods these reactions are simulating correspond to an energy minimization problem. [sent-113, score-0.386]

45 As such, we suspect that the particular reaction networks presented here always converge to their equilibrium. [sent-114, score-0.732]

46 4 Representing Graphical Models with Reaction Networks In the following compilation procedure, each message and marginal probability is represented by a set of distinct chemical species. [sent-115, score-0.45]

47 We design networks that cause them to interact in such a way that, at steady state, the concentration of some species represent the marginal distributions of the variable nodes in a factor graph. [sent-116, score-0.68]

48 Since messages in the sum-product inference algorithm are computed from other messages, the reaction networks that implement sending messages describe how species from one message catalyze the species of another message. [sent-118, score-2.157]

49 In addition, each k message and marginal probability distribution has a chemical species with a zero subscript that represents unassigned probability mass. [sent-120, score-0.898]

50 Together, the set of species associated with a messages or 4 marginal probability are called a belief species, and the reaction networks presented in the subsequent sections are designed to conserve species – and by extension their concentrations – with each such set. [sent-121, score-1.978]

51 For example, the concentration of belief species P n = {Pn }Kn of Pr(xn ) have a constant k k=0 Kn sum, k=0 [Pn ] , determined by the initial concentrations. [sent-122, score-0.515]

52 These sets belief species are a chemik cal representation of the left hand sides of Equations 3–5. [sent-123, score-0.476]

53 The next few sections present reaction networks whose dynamics implement their right hand sides. [sent-124, score-0.778]

54 1 Belief Recycling Reactions Each set of belief species has an associated set of reactions that recycle assigned probabilities to the unassigned species. [sent-126, score-0.755]

55 By continuously and dynamically reallocating probability mass, the resulting reaction network can adapt to changing potential functions ψj , i. [sent-127, score-0.747]

56 For example, the factor graph shown in Figure 1a has 8 distinct sets of belief species – 2 representing marginal probabilities of x1 and x2 , and 6 (ignoring messages to leaf factor nodes) representing messages. [sent-130, score-0.879]

57 The associate recycling reactions are κr κr G B P(2→3) . [sent-131, score-0.23]

58 quantities will be closer to normalized, however the speed at which the reaction network reaches steady state decreases, see Section 5. [sent-134, score-0.776]

59 2 Sum Messages In the reactions that implement messages from factor to variable nodes, message species of incoming messages catalyze the assignment of message species belonging to outgoing messages. [sent-136, score-1.832]

60 The kth message component from a factor node ψj to the variable node xn is implemented by a reactions of the form (j→n) S0 ψj (xj =kj ) (n′ →j) + n′ ∈ne(j)\n (n′ →j) (j→n) GGGGGGGB Sk + Pkj n′ Pkj n′ ∈ne(j)\n , (12) n′ where the nth component of kj is clamped to k, kj = k. [sent-138, score-0.734]

61 Using the law of mass action, the kinetics n for each sum message species are given by (j→n) d[Sk dt ] = (j→n) ψj (xj = kj )[S0 kj =k n n′ ∈ne(j)\n (j→n) At steady state the concentration of Sk κr (j→n) [Sk ] (j→n) [S0 ] (j→n) where all [Sk (n′ →j) [Pkj ] n′ (j→n) ] − κr [Sk ]. [sent-139, score-0.959]

62 (13) is given by (n′ →j) ψj (xj = kj ) = kj =k n [Pkj n′ ∈ne(j)\n ] species concentrations have the same factor κr (j→n) [S0 ], (14) n′ ] . [sent-140, score-0.788]

63 As κr decreases, the concentration of unassigned probability mass decreases and the concentration normalized by the constant sum of all the related belief species can be interpreted as a probability. [sent-142, score-0.681]

64 For example, the four factor-to-variable messages in Figure 1(a) can be implemented with the following reactions ψ1 (k) (1→1) GGGGGGGB S(1→1) k (2→2) GGGGGGGB S(2→2) k S0 S0 ψ2 (k) GGGGGGGB S(3→1) + P(2→3) k k′ (1→3) GGGGGGGB S(3→2) + P(1→3) . [sent-143, score-0.407]

65 3 Product Messages Reaction networks that implement variable to factor node messages have a similar, but slightly simpler, structure. [sent-163, score-0.395]

66 Again, each components species of the message is catalyzed by all incoming messages species but only of the same component species. [sent-164, score-1.16]

67 The rate constant for all product message reactions is the same κprod resulting in reactions of the following form (n→j) P0 (j ′ →n) + Sk κprod (j ′ →n) (n→j) GGGGGGGB Pk + Sk . [sent-165, score-0.545]

68 (17) j ′ ∈ne(n)\j j ′ ∈ne(n)\j The dynamics of the message component species is given by (n→j) d[Pk dt ] (n→j) = κprod [P0 (j ′ →n) [Sk ] (n→j) ] − κr [Pk j ′ ∈ne(n)\j (n→j) At steady state the concentration of Pk κr is given by (n→j) [Pk ] (n→j) κprod [P0 ] (j ′ →n) [Sk = ]. [sent-167, score-0.654]

69 (18) j ′ ∈ne(n)\j Since all component species of product messages have the same multiplier (n→j) κr ], (n→j) [Pk κprod [P0 ] the steady state species concentrations compute the correct message according to Equation 4. [sent-168, score-1.323]

70 For example, the two different sets of variable to factor messages in Figure 1a are (1→3) (1→1) κprod (1→3) (1→1) (2→3) (2→2) κprod (2→3) (2→2) G B Pk GGG G B Pk GGG + Sk . [sent-169, score-0.287]

71 + Sk P0 + Sk P0 + Sk Similarly, the reactions to compute the marginal probabilities of x1 and x2 in Figure 1a are (3→1) P1 + Sk 0 (1→1) + Sk (19) κprod G B P1 + S(3→1) + S(1→1) GGG k k k (20) κprod (3→2) (2→2) (3→2) (2→2) G B P2 + Sk GGG + Sk . [sent-170, score-0.24]

72 Together, reactions for recycling probability mass, implementing sum-product messages, and implementing product messages deﬁne a reaction network whose equilibrium computes the messages and marginal probabilities via the sum-product algorithm. [sent-173, score-1.446]

73 As probability mass is continuously recycled, messages computed on partial information will readjust and settle to the correct value. [sent-174, score-0.309]

74 Sum messages from leaf nodes do not depend on any other messages. [sent-176, score-0.227]

75 the reactions have equilibrated, the message species continue to catalyze the next set of messages until they have reached the the correct value, etc. [sent-179, score-0.986]

76 Colored boxes show the trajectories of a belief species set in a simulated reaction network. [sent-210, score-1.157]

77 5 Simulation Experiments This section presents simulation results of factor graphs that have been compiled into reaction networks via the procedure in Section 4. [sent-216, score-0.905]

78 The conserved concentrations for all sets of belief species were set to 1, so plots of concentrations can be directly interpreted as probabilities. [sent-218, score-0.702]

79 1 Tree-Structured Factor Graphs To demonstrate the functionality and features of the compilation procedure described in Section 4, we compiled the 4 variable factor graph shown in Figure 2a into a reaction network. [sent-221, score-0.872]

80 When x1 , x2 , x3 and x4 have discrete states K1 = K2 = K4 = 2 and K3 = 3, the resulting network has 64 chemical species and 105 reactions. [sent-222, score-0.698]

81 The largest reaction is of 5th order to compute the marginal distribution of x2 . [sent-223, score-0.721]

82 We instantiated the factors as shown in Figure 2c and initialized all message and marginal species to be uniform. [sent-224, score-0.59]

83 In a biological reaction network, such a change could be induced by up-regulating, or activating a catalyst due to a new chemical signal. [sent-228, score-0.932]

84 Small values of κr results in better approximation as less of the probability mass in each belief species set is in an unassigned state. [sent-232, score-0.603]

85 When replacing the two ′ of the binary factors ψ5 and ψ6 in Figure 2a with a new tertiary factor ψ5 that is connected to x2 ,x3 , and x4 the compiled reaction network has 58 species and 115 reactions. [sent-237, score-1.262]

86 Larger factors can reduce the number of species since there are fewer edges and associated messages to represent, however, the domain sizes Kj of the individual factors grows exponentially and in the number of neighbors and thus require more reactions to implement. [sent-239, score-0.868]

87 Figure 2b shows a cyclic graph which we compiled to reactions and simulated. [sent-248, score-0.279]

88 When Kn = 2 for all variables the resulting reaction network has 54 species and 84 reactions. [sent-249, score-1.128]

89 Figure 4 shows the results of performing both loopy belief propagation and simulation results for the compiled reaction network. [sent-251, score-0.889]

90 Since the reaction network is essentially performing damped loopy belief propagation with an inﬁnitesimal time step, the reaction network implementation should always converge. [sent-253, score-1.628]

91 6 Conclusion We present a compilation procedure for taking arbitrary factor graphs over discrete random variables and construct a reaction network that performs the sum-product message passing algorithm for computing marginal distributions. [sent-254, score-1.065]

92 These reaction networks exploit the fact that the message structure of the sum-product algorithm maps neatly onto the model of mass action kinetics. [sent-255, score-0.925]

93 By construction, conserved sets of belief species in the network perform implicit and continuous normalization of all messages and marginal distributions. [sent-256, score-0.791]

94 The correct behavior of the network implementation relies on higher order reactions to implement multiplicative operations. [sent-257, score-0.289]

95 However, physically high order reaction are exceedingly unlikely to proceed in a single step. [sent-258, score-0.681]

96 along the lines of [17] with intermediate species of binary reactions. [sent-261, score-0.401]

97 One aspect that this paper did not address, but we believe is important, is how parameter uncertainty and noise affect the reaction network implementations of inference algorithms. [sent-262, score-0.751]

98 To address the latter, we plan to look at other semantic interpretations of chemical reaction networks, such as the linear noise approximation or the stochastic chemical kinetics model. [sent-265, score-1.239]

99 max-product, parameter learning, and dynamic state estimation, as reaction networks. [sent-268, score-0.681]

100 We believe that statistical inference provides the right tools for tackling noise and uncertainty at a microscopic level, and that reaction networks are the right language for specifying systems at that scale. [sent-269, score-0.778]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('reaction', 0.681), ('species', 0.401), ('chemical', 0.251), ('messages', 0.207), ('reactions', 0.2), ('ggg', 0.156), ('sk', 0.136), ('message', 0.127), ('kj', 0.111), ('prod', 0.109), ('concentrations', 0.102), ('gggggggb', 0.089), ('unassigned', 0.079), ('pk', 0.079), ('belief', 0.075), ('dna', 0.063), ('factor', 0.063), ('rq', 0.058), ('pr', 0.056), ('kinetics', 0.056), ('networks', 0.051), ('zm', 0.05), ('steady', 0.049), ('erik', 0.049), ('compiled', 0.049), ('mass', 0.048), ('network', 0.046), ('georg', 0.045), ('soloveichik', 0.045), ('molecular', 0.044), ('marginal', 0.04), ('strand', 0.039), ('damped', 0.039), ('pkj', 0.039), ('passing', 0.039), ('concentration', 0.039), ('loopy', 0.038), ('graphs', 0.037), ('kn', 0.036), ('displacement', 0.036), ('abstractions', 0.036), ('biomolecular', 0.033), ('catalyze', 0.033), ('vitro', 0.033), ('winfree', 0.033), ('compilation', 0.032), ('node', 0.032), ('pq', 0.031), ('graph', 0.03), ('recycling', 0.03), ('xn', 0.025), ('implement', 0.025), ('devices', 0.025), ('xj', 0.025), ('simulation', 0.024), ('logic', 0.024), ('incoming', 0.024), ('inference', 0.024), ('propagation', 0.022), ('microscopic', 0.022), ('cardelli', 0.022), ('conserved', 0.022), ('equilibrates', 0.022), ('gggggg', 0.022), ('jehoshua', 0.022), ('nanoscale', 0.022), ('reactant', 0.022), ('seelig', 0.022), ('transcriptional', 0.022), ('wyss', 0.022), ('heidelberg', 0.022), ('factors', 0.022), ('david', 0.022), ('dynamics', 0.021), ('harvard', 0.021), ('graphical', 0.021), ('oscillations', 0.02), ('continuously', 0.02), ('nodes', 0.02), ('conserve', 0.02), ('oscillators', 0.02), ('asynchronous', 0.019), ('product', 0.018), ('correct', 0.018), ('berlin', 0.018), ('assembly', 0.018), ('sec', 0.018), ('possibilities', 0.018), ('action', 0.018), ('equilibrium', 0.017), ('turing', 0.017), ('dt', 0.017), ('variable', 0.017), ('pm', 0.017), ('neighbors', 0.016), ('luca', 0.016), ('gates', 0.016), ('kth', 0.016), ('rm', 0.016), ('settle', 0.016)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999964 189 nips-2013-Message Passing Inference with Chemical Reaction Networks

Author: Nils E. Napp, Ryan P. Adams

2 0.14357582 168 nips-2013-Learning to Pass Expectation Propagation Messages

Author: Nicolas Heess, Daniel Tarlow, John Winn

Abstract: Expectation Propagation (EP) is a popular approximate posterior inference algorithm that often provides a fast and accurate alternative to sampling-based methods. However, while the EP framework in theory allows for complex nonGaussian factors, there is still a signiﬁcant practical barrier to using them within EP, because doing so requires the implementation of message update operators, which can be difﬁcult and require hand-crafted approximations. In this work, we study the question of whether it is possible to automatically derive fast and accurate EP updates by learning a discriminative model (e.g., a neural network or random forest) to map EP message inputs to EP message outputs. We address the practical concerns that arise in the process, and we provide empirical analysis on several challenging and diverse factors, indicating that there is a space of factors where this approach appears promising. 1

3 0.070006296 318 nips-2013-Structured Learning via Logistic Regression

Author: Justin Domke

Abstract: A successful approach to structured learning is to write the learning objective as a joint function of linear parameters and inference messages, and iterate between updates to each. This paper observes that if the inference problem is “smoothed” through the addition of entropy terms, for ﬁxed messages, the learning objective reduces to a traditional (non-structured) logistic regression problem with respect to parameters. In these logistic regression problems, each training example has a bias term determined by the current set of messages. Based on this insight, the structured energy function can be extended from linear factors to any function class where an “oracle” exists to minimize a logistic loss.

4 0.062455408 142 nips-2013-Information-theoretic lower bounds for distributed statistical estimation with communication constraints

Author: Yuchen Zhang, John Duchi, Michael Jordan, Martin J. Wainwright

Abstract: We establish lower bounds on minimax risks for distributed statistical estimation under a communication budget. Such lower bounds reveal the minimum amount of communication required by any procedure to achieve the centralized minimax-optimal rates for statistical estimation. We study two classes of protocols: one in which machines send messages independently, and a second allowing for interactive communication. We establish lower bounds for several problems, including various types of location models, as well as for parameter estimation in regression models. 1

5 0.059541605 110 nips-2013-Estimating the Unseen: Improved Estimators for Entropy and other Properties

Author: Paul Valiant, Gregory Valiant

Abstract: Recently, Valiant and Valiant [1, 2] showed that a class of distributional properties, which includes such practically relevant properties as entropy, the number of distinct elements, and distance metrics between pairs of distributions, can be estimated given a sublinear sized sample. Speciﬁcally, given a sample consisting of independent draws from any distribution over at most n distinct elements, these properties can be estimated accurately using a sample of size O(n/ log n). We propose a novel modiﬁcation of this approach and show: 1) theoretically, this estimator is optimal (to constant factors, over worst-case instances), and 2) in practice, it performs exceptionally well for a variety of estimation tasks, on a variety of natural distributions, for a wide range of parameters. Perhaps unsurprisingly, the key step in our approach is to ﬁrst use the sample to characterize the “unseen” portion of the distribution. This goes beyond such tools as the Good-Turing frequency estimation scheme, which estimates the total probability mass of the unobserved portion of the distribution: we seek to estimate the shape of the unobserved portion of the distribution. This approach is robust, general, and theoretically principled; we expect that it may be fruitfully used as a component within larger machine learning and data analysis systems. 1

6 0.056654327 88 nips-2013-Designed Measurements for Vector Count Data

7 0.052192885 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

8 0.051324286 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

9 0.040854651 16 nips-2013-A message-passing algorithm for multi-agent trajectory planning

10 0.039043799 52 nips-2013-Bayesian inference as iterated random functions with applications to sequential inference in graphical models

11 0.038687952 267 nips-2013-Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems

12 0.037837006 248 nips-2013-Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs

13 0.034997668 301 nips-2013-Sparse Additive Text Models with Low Rank Background

14 0.032673094 210 nips-2013-Noise-Enhanced Associative Memories

15 0.0326191 289 nips-2013-Scalable kernels for graphs with continuous attributes

16 0.032224603 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

17 0.031755932 187 nips-2013-Memoized Online Variational Inference for Dirichlet Process Mixture Models

18 0.031735688 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

19 0.031280577 66 nips-2013-Computing the Stationary Distribution Locally

20 0.030827967 218 nips-2013-On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.086), (1, 0.02), (2, -0.026), (3, -0.007), (4, 0.008), (5, 0.035), (6, 0.042), (7, -0.032), (8, 0.011), (9, 0.014), (10, 0.059), (11, -0.007), (12, 0.064), (13, -0.011), (14, -0.05), (15, 0.018), (16, 0.003), (17, 0.014), (18, 0.002), (19, 0.005), (20, -0.036), (21, -0.027), (22, -0.004), (23, -0.029), (24, 0.014), (25, 0.019), (26, 0.047), (27, 0.055), (28, 0.061), (29, -0.02), (30, 0.005), (31, 0.024), (32, -0.009), (33, 0.065), (34, 0.088), (35, -0.011), (36, -0.072), (37, 0.051), (38, 0.053), (39, -0.011), (40, -0.062), (41, -0.05), (42, -0.077), (43, -0.059), (44, 0.093), (45, 0.025), (46, 0.089), (47, -0.066), (48, 0.041), (49, 0.048)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.93220186 189 nips-2013-Message Passing Inference with Chemical Reaction Networks

Author: Nils E. Napp, Ryan P. Adams

2 0.72917962 168 nips-2013-Learning to Pass Expectation Propagation Messages

Author: Nicolas Heess, Daniel Tarlow, John Winn

3 0.55165493 184 nips-2013-Marginals-to-Models Reducibility

Author: Tim Roughgarden, Michael Kearns

Abstract: We consider a number of classical and new computational problems regarding marginal distributions, and inference in models specifying a full joint distribution. We prove general and efﬁcient reductions between a number of these problems, which demonstrate that algorithmic progress in inference automatically yields progress for “pure data” problems. Our main technique involves formulating the problems as linear programs, and proving that the dual separation oracle required by the ellipsoid method is provided by the target problem. This technique may be of independent interest in probabilistic inference. 1

4 0.54224533 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances

Author: Daniel S. Levine, Jonathan P. How

Abstract: We consider the sensor selection problem on multivariate Gaussian distributions where only a subset of latent variables is of inferential interest. For pairs of vertices connected by a unique path in the graph, we show that there exist decompositions of nonlocal mutual information into local information measures that can be computed efﬁciently from the output of message passing algorithms. We integrate these decompositions into a computationally efﬁcient greedy selector where the computational expense of quantiﬁcation can be distributed across nodes in the network. Experimental results demonstrate the comparative efﬁciency of our algorithms for sensor selection in high-dimensional distributions. We additionally derive an online-computable performance bound based on augmentations of the relevant latent variable set that, when such a valid augmentation exists, is applicable for any distribution with nuisances. 1

5 0.51812708 8 nips-2013-A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles

Author: Jinwoo Shin, Andrew E. Gelfand, Misha Chertkov

Abstract: Max-product ‘belief propagation’ (BP) is a popular distributed heuristic for ﬁnding the Maximum A Posteriori (MAP) assignment in a joint probability distribution represented by a Graphical Model (GM). It was recently shown that BP converges to the correct MAP assignment for a class of loopy GMs with the following common feature: the Linear Programming (LP) relaxation to the MAP problem is tight (has no integrality gap). Unfortunately, tightness of the LP relaxation does not, in general, guarantee convergence and correctness of the BP algorithm. The failure of BP in such cases motivates reverse engineering a solution – namely, given a tight LP, can we design a ‘good’ BP algorithm. In this paper, we design a BP algorithm for the Maximum Weight Matching (MWM) problem over general graphs. We prove that the algorithm converges to the correct optimum if the respective LP relaxation, which may include inequalities associated with non-intersecting odd-sized cycles, is tight. The most signiﬁcant part of our approach is the introduction of a novel graph transformation designed to force convergence of BP. Our theoretical result suggests an efﬁcient BP-based heuristic for the MWM problem, which consists of making sequential, “cutting plane”, modiﬁcations to the underlying GM. Our experiments show that this heuristic performs as well as traditional cutting-plane algorithms using LP solvers on MWM problems. 1

6 0.48520809 318 nips-2013-Structured Learning via Logistic Regression

7 0.48413178 61 nips-2013-Capacity of strong attractor patterns to model behavioural and cognitive prototypes

8 0.46153814 340 nips-2013-Understanding variable importances in forests of randomized trees

9 0.44881952 52 nips-2013-Bayesian inference as iterated random functions with applications to sequential inference in graphical models

10 0.43491963 196 nips-2013-Modeling Overlapping Communities with Node Popularities

11 0.43105045 267 nips-2013-Recurrent networks of coupled Winner-Take-All oscillators for solving constraint satisfaction problems

12 0.42465451 13 nips-2013-A Scalable Approach to Probabilistic Latent Space Inference of Large-Scale Networks

13 0.42445982 94 nips-2013-Distributed $k$-means and $k$-median Clustering on General Topologies

14 0.42422867 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

15 0.4208295 104 nips-2013-Efficient Online Inference for Bayesian Nonparametric Relational Models

16 0.42077181 142 nips-2013-Information-theoretic lower bounds for distributed statistical estimation with communication constraints

17 0.40803957 332 nips-2013-Tracking Time-varying Graphical Structure

18 0.40207729 134 nips-2013-Graphical Models for Inference with Missing Data

19 0.3976064 343 nips-2013-Unsupervised Structure Learning of Stochastic And-Or Grammars

20 0.3962245 107 nips-2013-Embed and Project: Discrete Sampling with Universal Hashing

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(16, 0.024), (33, 0.067), (34, 0.092), (41, 0.453), (49, 0.023), (56, 0.054), (70, 0.059), (85, 0.078), (89, 0.016), (93, 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.84249967 257 nips-2013-Projected Natural Actor-Critic

Author: Philip S. Thomas, William C. Dabney, Stephen Giguere, Sridhar Mahadevan

Abstract: Natural actor-critics form a popular class of policy search algorithms for ﬁnding locally optimal policies for Markov decision processes. In this paper we address a drawback of natural actor-critics that limits their real-world applicability—their lack of safety guarantees. We present a principled algorithm for performing natural gradient descent over a constrained domain. In the context of reinforcement learning, this allows for natural actor-critic algorithms that are guaranteed to remain within a known safe region of policy space. While deriving our class of constrained natural actor-critic algorithms, which we call Projected Natural ActorCritics (PNACs), we also elucidate the relationship between natural gradient descent and mirror descent. 1

same-paper 2 0.82033515 189 nips-2013-Message Passing Inference with Chemical Reaction Networks

Author: Nils E. Napp, Ryan P. Adams

3 0.72973466 193 nips-2013-Mixed Optimization for Smooth Functions

Author: Mehrdad Mahdavi, Lijun Zhang, Rong Jin

Abstract: It is well known that the optimal convergence rate for stochastic optimization of √ smooth functions is O(1/ T ), which is same as stochastic optimization of Lipschitz continuous convex functions. This is in contrast to optimizing smooth functions using full gradients, which yields a convergence rate of O(1/T 2 ). In this work, we consider a new setup for optimizing smooth functions, termed as Mixed Optimization, which allows to access both a stochastic oracle and a full gradient oracle. Our goal is to signiﬁcantly improve the convergence rate of stochastic optimization of smooth functions by having an additional small number of accesses to the full gradient oracle. We show that, with an O(ln T ) calls to the full gradient oracle and an O(T ) calls to the stochastic oracle, the proposed mixed optimization algorithm is able to achieve an optimization error of O(1/T ). 1

4 0.70200217 258 nips-2013-Projecting Ising Model Parameters for Fast Mixing

Author: Justin Domke, Xianghang Liu

Abstract: Inference in general Ising models is difﬁcult, due to high treewidth making treebased algorithms intractable. Moreover, when interactions are strong, Gibbs sampling may take exponential time to converge to the stationary distribution. We present an algorithm to project Ising model parameters onto a parameter set that is guaranteed to be fast mixing, under several divergences. We ﬁnd that Gibbs sampling using the projected parameters is more accurate than with the original parameters when interaction strengths are strong and when limited time is available for sampling.

5 0.66362876 62 nips-2013-Causal Inference on Time Series using Restricted Structural Equation Models

Author: Jonas Peters, Dominik Janzing, Bernhard Schölkopf

Abstract: Causal inference uses observational data to infer the causal structure of the data generating system. We study a class of restricted Structural Equation Models for time series that we call Time Series Models with Independent Noise (TiMINo). These models require independent residual time series, whereas traditional methods like Granger causality exploit the variance of residuals. This work contains two main contributions: (1) Theoretical: By restricting the model class (e.g. to additive noise) we provide general identiﬁability results. They cover lagged and instantaneous effects that can be nonlinear and unfaithful, and non-instantaneous feedbacks between the time series. (2) Practical: If there are no feedback loops between time series, we propose an algorithm based on non-linear independence tests of time series. We show empirically that when the data are causally insufﬁcient or the model is misspeciﬁed, the method avoids incorrect answers. We extend the theoretical and the algorithmic part to situations in which the time series have been measured with different time delays. TiMINo is applied to artiﬁcial and real data and code is provided. 1

6 0.6199863 180 nips-2013-Low-rank matrix reconstruction and clustering via approximate message passing

7 0.61672187 175 nips-2013-Linear Convergence with Condition Number Independent Access of Full Gradients

8 0.60229748 77 nips-2013-Correlations strike back (again): the case of associative memory retrieval

9 0.55233169 11 nips-2013-A New Convex Relaxation for Tensor Completion

10 0.44380459 20 nips-2013-Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

11 0.44328868 239 nips-2013-Optimistic policy iteration and natural actor-critic: A unifying view and a non-optimality result

12 0.44326821 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives

13 0.43139374 184 nips-2013-Marginals-to-Models Reducibility

14 0.42655489 54 nips-2013-Bayesian optimization explains human active search

15 0.4078387 282 nips-2013-Robust Multimodal Graph Matching: Sparse Coding Meets Graph Matching

16 0.40722468 196 nips-2013-Modeling Overlapping Communities with Node Popularities

17 0.40069732 301 nips-2013-Sparse Additive Text Models with Low Rank Background

18 0.39949003 236 nips-2013-Optimal Neural Population Codes for High-dimensional Stimulus Variables

19 0.39586037 59 nips-2013-Blind Calibration in Compressed Sensing using Message Passing Algorithms

20 0.39552861 250 nips-2013-Policy Shaping: Integrating Human Feedback with Reinforcement Learning