Message Passing Inference with Chemical Reaction Networks
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.
Summary: The authors present a compilation 
      procedure for implementing message passing for factor graphs over discrete 
      random variables in a chemical reaction network. A chemical reaction 
      network consists of a set of reactions, comprised of reactants, products 
      and reaction rates. They use mass action kinetics to design and 
      implement specific information flows through chemical species. The 
      authors show how the sum-product algorithm can be mapped onto a set of 
      reactions for computation of sum messages, product messages and belief 
      recycling reactions. Furthermore, it is discussed how global equilibrium 
      states can be achieved and how these correspond to the states BP would 
      achieve in a graphical model. The paper is very well written, 
      with very minor occasional typos or missing prepositions. However, the 
      notation for the chemical reaction networks is unusual to the machine 
      learning community and takes significant effort to read comfortably. As 
      this is a byproduyct of the unusual topic, it is not a mistake of the 
      authors, but needs to be kept in mind if targeting ML communities. Still, 
      the authors try to find mathematical abstractions for chemical reactions 
      and explain them cleanly. Content-wise, this is an unusual 
      paper for the machine learning community. the mapping of a fundamental 
      inference algorithm to chemical reaction networks is presented in a lot of 
      detail, but can be confusing in terms of certain aspects: it is a bit 
      unclear how exactly damped BP corresponds to what the authors are doing as 
      they are stating and I would have appreciated a little more elaboration on 
      it. Furthermore, the mentioned problem of unassigned probability mass in 
      case of high reaction speeds is a recurrent topic in the paper and could 
      use a dedicated paragraph where it is theoretically explained in one 
      concentrated place to reduce confusion about it. The authors make the 
      strong statement that arbitrary factor graphs can be implemented, but only 
      show experiments for very low dimensional variables and comparably small 
      graphs. A larger scale implementation of a complicated model and a more 
      detailed quantitative comparison compared to the shown experiments would 
      be welcome. The proposed experiments underline the suggested contribution, 
      but are not very extensive or deep. Considering this is work at an early 
      stage, it is reasonable that the authors suggest exploring noisy and 
      uncertain settings. It would be exciting to see a non-toy experiment (i.e. 
      labeling in an mrf) implemented through chemical reaction networks and 
      compare it to real BP solutions, probably this should happen with the 
      introduction of the Max-Product algorithm the authors suggest for the 
      future. In total, the paper is meticulous in suggesting the framework 
      of chemical reaction networks and mapping belief propagation to it, but 
      the experiments appear a little lacking in real scope. Suggestions: 
      a)more and more convincing experiments with more complicated and/or 
      bigger graphs b)better theoretical explanation of damped BP in 
      relation to this work c) discuss how reaction speeds can be 
      implemented in reality with different kappas. I expect them to be 
      regulated through chemical compounds, which would most likely lead to 
      discrete subsampling of the speed-space. Would this lead to local minima 
      or other problems during inference? Are the assumptions of the 'perfect 
      chemical reaction network' based on arbitrary species realistic? Where's 
      the catch if graphs get bigger and have largewr state spaces and 
      hundreds/thousands of chemical species are needed to implement a problem. 
      Does it scale? d) Discussions of more models. MaxProduct, continuous 
      variables etc.... I found the paper to be highly original 
      for the ML-community. While biological computation is a vibrant field with 
      many recent contributions by Erik Winfree, Luca Cardelli, Andrew Phillips 
      and more researchers stuydying multiple aspects of DNA computing and 
      Biological Programming, the particular focus of this work in implementing 
      a standard ML inference algorithm and mapping it cleanly to a chemical 
      implementation is new to the best of my knowledge and highly significant. 
      It will be of great value to the field of biological computation and 
      computation in general if well-established and theoretically studied 
      inference algorithms can be mapped to biological/hardware implementations, 
      especially considering the possibilities of microscopic computation in the 
      future.