On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models

Authors: boyao  li
alexandar j thomson
houssam  nassif
matthew m engelhard
david  page
alexander j thomson
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 07:02:25

Abstract: Deep neural networks (DNNs) lack the precise semantics and definitive probabilistic interpretation of probabilistic graphical models (PGMs). In this paper, we propose an innovative solution by constructing infinite tree-structured PGMs that correspond exactly to neural networks. Our research reveals that DNNs, during forward propagation, indeed perform approximations of PGM inference that are precise in this alternative PGM structure. Not only does our research complement existing studies that describe neural networks as kernel machines or infinite-sized Gaussian processes, it also elucidates a more direct approximation that DNNs make to exact inference in PGMs. Potential benefits include improved pedagogy and interpretation of DNNs, and algorithms that can merge the strengths of PGMs and DNNs.

Main paper: 
 introduction: 
 Deep neural networks (DNNs), including large language models, offer state-of-the-art performance on many tasks, but they are difficult to interpret due to their complex structure, large number of latent variables, and the presence of nonlinear activation functions [Buhrmester et al., 2021] . To gain a precise statistical interpretation for DNNs, much progress has been made in linking them to probabilistic graphical models (PGMs). Variational autoencoders (VAEs) [Kingma and Welling, 2014] are an early example; more recent examples include probabilistic dependency graphs [Richardson, 2022] as well as work that relates recurrent neural networks (RNNs) with hidden Markov models (HMMs) [Choe et al., 2017] and convolutional neural networks (CNNs) with Gaussian processes (GPs) [Garriga-Alonso et al., 2018] . When such a connection is possible, potential benefits include:• Clear statistical semantics for a trained DNN model, beyond merely providing the conditional distribution over output variables given input variables. Instead, PGMs provide a joint distribution over all variables including the latent variables.• Ability to import any PGM algorithm into DNNs, such as belief propagation or MCMC, for example to reverse any DNN to use output variables as evidence and variables anywhere earlier as query variables.• Improved calibration, i.e., improved predictions of probabilities at the output nodes by incorporation of PGM algorithms.In this paper, we establish such a correspondence between DNNs of any structure and PGMs. Given an arbitrary DNN architecture, we first construct an infinite-width tree-structured PGM. We then demonstrate that during training, the DNN executes approximations of precise inference in the PGM during the forward propagation step. We prove our result exactly in the case of sigmoid activations. We indicate how it can be extended to ReLU activations by building on a prior result of Nair and Hinton [2010] . Because the PGM in our result is a Markov network, the construction can extend even further, to all nonnegative activation functions provided that proper normalization is employed. We argue that modified variants of layer normalization and batch normalization could be viewed as approximations to proper MN normalization in this context, although formal analyses of such approximations are left for future work. Finally, in the context of sigmoid activations we empirically evaluate how the second and third benefits listed above follow from the result, as motivated and summarized now in the next paragraph.A neural network of any architecture with only sigmoid activations satisfies the definition of a Bayesian network over binary variables-it is a directed acyclic graph with a conditional probability distribution at each node, conditional on the values of the node's parents-and thus is sometimes called a Bayesian belief network (BBN). Nevertheless, it can be shown that the standard gradient used in neural network training (whether using cross-entropy or other common error functions) is inconsistent with the BBN semantics, that is, with the probability distribution defined by this BBN.On the other hand, Gibbs sampling is a training method consistent with the BBN semantics, and hence effective for calibration and for reversing any neural network, but it is woefully inefficient for training. Hamiltonian Monte Carlo (HMC) is more efficient than Gibbs and better fits BBN semantics than SGD. We demonstrate empirically that after training a network quickly using SGD, calibration can be improved by fine-tuning using HMC. The specific HMC algorithm employed here follows directly from the theoretical result, being designed to approximate Gibbs-sampling in the theoretical, infinite-width tree structured Markov network. The degree of approximation is controlled by the value of a single hyperparameter that is also defined based on the theoretical result.The present paper stands apart from many other theoretical analyses of DNNs that view DNNs purely as function approximators and prove theorems about the quality of function approximation. Here we instead show that DNNs may be viewed as statistical models, specifically PGMs. This work is also different from the field of Bayesian neural networks, where the goal is to seek and model a probability distribution over neural network parameters. In our work, the neural network itself defines a joint probability distribution over its variables (nodes). Our work therefore is synergistic with Bayesian neural networks but more closely related to older work on learning stochastic neural networks via expectation maximization (EM) [Amari, 1995] or approximate EM [Song et al., 2016] .Although the approach is different, our motivation is similar to that of Dutordoir et al. [2021] and Sun et al. [2020] in their work to link DNNs to deep Gaussian processes (GPs) [Damianou and Lawrence, 2013] . By identifying the forward pass of a DNN with the mean of a deep GP layer, they aim to augment DNNs with advantages of GPs, notably the ability to quantify uncertainty over both output and latent nodes. What distinguishes our work from theirs is that we make the DNN-PGM approximation explicit and include all sigmoid DNNs, not just unsupervised belief networks or other specific cases.All code needed to reproduce our experimental results may be found at https://github.com/ engelhard-lab/DNN_TreePGM.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?[Yes] Justification: We provide the theorem, proof (in supplement), and empirical results promised in the abstract and introduction. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: comparison to bayesian networks and markov networks: 
 Syntactically a Bayesian network (BN) is a directed acyclic graph, like a neural network, whose nodes are random variables. Here we use capital letters to stand for random variables, and following Russell and Norvig [Russell and Norvig, 2020] and others, we take a statement written using such variables to be a claim for all specific settings of those variables. Semantically, a BN represents a full joint probability distribution over its variables as P ( ⃗ V ) = i P (V i |pa(V i )), where pa(V i ) denotes the parents of variable V i . If the conditional probability distributions (CPDs) P (V i |pa(V i )) are all logistic regression models, we refer to the network as a sigmoid BN.It is well known that given sigmoid activation and a cross-entropy error, training a single neuron by gradient descent is identical to training a logistic regression model. Hence, a neural network under such conditions can be viewed as a "stacked logistic regression model", and also as a Bayesian network with logistic regression CPDs at the nodes. Technically, the sigmoid BN has a distribution over the input variables (variables without parents), whereas the neural network does not, and all nodes are treated as random variables. These distributions are easily added, and distributions of the input variables can be viewed as represented by the joint sample over them in our training set.A Markov network (MN) syntactically is an undirected graph with potentials ϕ i on its cliques, where each potential gives the relative probabilities of the various settings for its variables (the variables in the clique). Semantically, it defines the full joint distribution on the variables asP ( ⃗ V ) = 1 Z i ϕ i ( ⃗ V ) where the partition function Z is defined as ⃗ V i ϕ i ( ⃗ V ).It is common to use a loglinear form of the same MN, which can be obtained by treating a setting of the variables in a clique as a binary feature f i , and the natural log of the corresponding entry for that setting in the potential for that clique as a weight w i on that feature; the equivalent definition of the full joint is thenP ( ⃗ V ) = 1 Z e i wifi( ⃗ V ) .For training and prediction at this point the original graph itself is superfluous.The potentials of an MN may be on subsets of cliques; in that case we simply multiply all potentials on subsets of a clique to derive the potential on the clique itself. If the MN can be expressed entirely as potentials on edges or individual nodes, we call it a "pairwise" MN. An MN whose variables are all binary is a binary MN.A DNN of any architecture is, like a Bayesian network, a directed acyclic graph. A sigmoid activation can be understood as a logistic model, thus giving a conditional probability distribution for a binary variable given its parents. Thus, there is a natural interpretation of a DNN with sigmoid activations as a Bayesian network (e.g., Bayesian belief network). Note, however, that when the DNN has multiple, stacked hidden nodes, the values calculated for those nodes in the DNN by its forward pass do not match the values of the corresponding hidden nodes in a Bayesian network. Instead, for the remainder of this paper, we adopt the view that the DNN's forward pass might serve as an approximation to an underlying PGM and explore how said approximation can be precisely characterized. As reviewed in Appendix A, this Bayes net in turn is equivalent to (represents the same probability distribution) as a Markov network where every edge of weight w from variable A to variable B has a potential of the following form:B ¬B A e w 1 ¬A 1 1For space reasons, we assume the reader is already familiar with the Variable Elimination (VE) algorithm for computing the probability distribution over any query variable(s) given evidence (known values) at other variables in the network. This algorithm is identical for Bayes nets and Markov nets. It repeatedly multiplies together all the potentials (in a Bayes net, conditional probability distributions) involving the variable to be eliminated, and then sums that variable out of the resulting table, until only the query variable(s) remain. Normalization of the resulting table yields the final answer. VE is an exact inference algorithm, meaning its answers are exactly correct.Question: Does the paper discuss the limitations of the work performed by the authors?[Yes] Justification: The introduction, theorem, and last section ("Conclusion, Limitations...") note that the theorem and experiments are limited to sigmoid activations and that formal results for other activations are left for future work. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
the construction of tree-structured pgms: 
 Although both a binary pairwise Markov network (MN) and a Bayesian network (BN) share the same sigmoid functional structure as a DNN with sigmoid activations, it can be shown that the DNN does not in general define the same probability for the output variables given the input variables: forward propagation in the DNN is very fast but yields a different result than VE in the MN or BN, which can be much slower because the inference task is NP-complete. Therefore, if we take the distribution D defined by the BN or MN to be the correct meaning of the DNN, the DNN must be using an approximation D ′ to D. Procedurally, the approximation can be shown to be exactly the following: the DNN repeatedly treats the expectation of a variable V , given the values of V 's parents, as if it were the actual value of V . Thus previously binary variables in the Bayesian network view and binary features in the Markov network view become continuous. This procedural characterization of the approximation of D ′ to D yields exactly the forward pass in the neural network within the space of a similarly structured PGM, yet, on its own, does not yield a precise joint distribution for said PGM. We instead prefer in the PGM literature to characterize approximate distributions such as D ′ with an alternative PGM that precisely corresponds to D ′ ; for example, in some variational methods we may remove edges from a PGM to obtain a simpler PGM in which inference is more efficient. Treewidth-1 (tree-structured or forest-structured) PGMs are among the most desirable because in those models, exact inference by VE or other algorithms becomes efficient. We seek to so characterize the DNN approximation here.This approach aligns somewhat with the idea of the computation tree that has been used to explore the properties of belief propagation by expressing the relevant message passing operations in the form of a tree [Tatikonda and Jordan, 2002 , Ihler et al., 2005 , Weitz, 2006] . Naturally the design of the tree structured PGM proposed here differs from the computation trees for belief propagation as we instead aim to capture the behavior of the forward pass of the neural network. Nonetheless, both methods share similar general approaches, the construction of a simpler approximate PGM, and aims, to better understand the theoretical behavior of an approximation to a separate original PGM.To begin, we consider the Bayesian network view of the DNN. Our first step in this construction is to copy the shared parents in the network into separate nodes whose values are not tied. The algorithm for this step is as follows:a. Consider the observed nodes in the Bayesian network that correspond to the input of the neural network and their outgoing edges. b. At each node, for each outgoing edge, create a copy of the current node that is only connected to one of the original node's children with that edge. Since these nodes are observed at this step, these copies do all share the same values. The weights on these edges remain the same. c. Consider then the children of these nodes. Again, for each outgoing edge, make a copy of this node that is only connected to one child with that edge. In this step, for each copied node, we then also copy the entire subgraph formed by all ancestor nodes of the current node. Note that while weights across copies are tied, the values of the copies of any node are not tied. However, since we also copy the subtree of all input and intermediary hidden nodes relevant to a forward pass up to each copy, the probability of any of these copied nodes being true remains the same across copies (ignoring the influence of any information passed back from their children). d. We repeat this process across each layer until we have separate trees for each output node in the original deep neural network graph.This process ultimately creates a graph whose undirected structure is a tree or forest. In the directed structure, trees converge at the output nodes. The probability of any copy of a latent node given the observed input (and ignoring any information passed back through a node's descendant) is the same across all the copies, but when sampling, their values may not be.The preceding step alone is still not sufficient to accurately express the deep neural network as a PGM. Recall that in the probabilistic graphical model view of the approximation made by the DNN's forward pass, the neural network effectively takes a local average, in place of its actual value, from the immediately previous nodes and passes that information only forward. The following additional step in the construction yields this same behavior. This next step of the construction creates L copies of every non-output node in the network (starting at the output and moving backward) while also copying the entire ancestor subtrees of each of these nodes, as was done in step 1. The weight of a copied edges is then set to its original value divided by L. Note that this step results in a number of total copies that grows exponentially in the number of layers (i.e. L copies in the 2nd to last layer, L 2 copies in the layer before, etc). Detailed algorithms for the two steps in the construction of the infinite tree-structured PGM are presented in Appendix B. As L approaches infinity, we show that both inference and the gradient in this PGM construction matches the forward pass and gradient in the neural network exactly.This second step in the construction can be thought of intuitively by considering the behavior of sampling in the Bayesian network view. Since we make L copies of each node while also copying the subgraph of its ancestors, these copied nodes all share the same probabilities. As L grows large, even if we sampled every copied node only once, we would expect the average value across these L copies to match the probability of an individual copied node being true. Given that we set the new weights between these copies and their parents as the original weights divided by L, the sum of products (new weights times parent values) yields the average parent value multiplied by the original weight. As L goes to infinity, we remove sampling bias and the result exactly matches the value of the sigmoid activation function of the neural network, where this expectation in the PGM view is passed repeatedly to the subsequent neurons. The formal proof of this result, based on variable elimination, is found in Appendix C. There, we show the following:Theorem 1. In the PGM construction, as L → ∞, P (H = 1|⃗ x) → σ( M j=1 w j g j + N i θ i σ(p i )), for an arbitrary latent node H in the DNN that has observed parents g 1 , ..., g M and latent parents h 1 , ..., h N that are true with probabilities σ(p 1 ), ..., σ(p N ). Here, σ(•) is the logistic sigmoid function and w 1 , ..., w M and θ 1 , ..., θ N are the weights on edges between these nodes and H.The PGM of our construction is a Markov network that always has evidence at the nodes ⃗ X corresponding to the input nodes of the neural network. As such, it is more specifically a conditional random field (CRF). Theorem 1 states the probability that a given node anywhere in the CRF is true given ⃗ X equals the output of that same node in the neural network given input ⃗ X. The CRF may also have evidence at the nodes ⃗ Y that correspond to the output nodes of the neural network. Given the form of its potentials, as illustrated at the end of Section 2, the features in the CRF's loglinear form correspond exactly to the edges and are true if and only if the nodes on each end of the edge are true. It follows that the gradient of this CRF can be written as a vector with one entry for each feature f corresponding to each weight w of the neural network, of the form P (f | ⃗ X) -P (f | ⃗ X, ⃗ Y ). Building on Theorem 1, this gradient of the CRF can be shown to be identical to the gradient of the cross-entropy loss in the neural network: the partial derivative of the cross-entropy loss with respect to the weight w on an edge, or feature f of the CRF, is P(f | ⃗ X) -P (f | ⃗ X, ⃗ Y ).This result is more precisely stated below in Theorem 2 below, which is proven in Appendix D.Theorem 2. In the PGM construction, as L → ∞, the derivative of the marginal log-likelihood, where all hidden nodes have been summed out, with respect to a given weight exactly matches the derivative of the cross entropy loss in the neural network with respect to the equivalent weight in its structure.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: Yes, the data and code are all available. We provide the link for them at the end of the introduction.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
implications and extensions: 
 We are not claiming that one should actually carry out the PGM construction used in the preceding section, since that PGM is infinite. Rather, its contribution is to give precise semantics to an entire neural network, as a joint probability distribution over all its variables, not merely as a machine computing the probability of its output variables given the input variables. Any Markov network, including any CRF, precisely defines a joint probability distribution over all its variables, hidden or observed, in a standard, well-known fashion. The particular CRF we constructed is the right one in the very specific sense that it agrees with the neural network exactly in the gradients both use for training (Theorem 2). While the CRF is infinite, it is built using the original neural network as a template in a straightforward fashion and is tree-structured, and hence it is easy to understand. Beyond these contributions to pedagogy and comprehensibility, are there other applications of the theoretical results?One application is an ability to use standard PGM algorithms such as Markov chain Monte Carlo (MCMC) to sample latent variables given observed values of input and output variables, such as for producing confidence intervals or understanding relationships among variables. One could already do so using Gibbs sampling in the BN or MN directly represented by the DNN itself (which we will call the "direct PGM"), but then one wouldn't be using the BN or MN with respect to which SGD training in the DNN is correct. For that, our result has shown that one instead needs to use Gibbs sampling in the infinite tree-structured PGM, which is impractical. Nevertheless, for any variable V in the original DNN, on each iteration a Gibbs sampler takes infinitely many samples of V given infinitely many samples of each of the members of V 's Markov blanket in the original DNN. By treating the variables of the original DNN as continuous, with their values approximating their sampled probabilities in the Gibbs sampler, we can instead apply Hamiltonian Monte Carlo or other MCMC methods for continuous variables in the much smaller DNN structure. We explore this approach empirically rather than theoretically in the next section. Another, related application of our result is that one could further fine-tune the trained DNN using other PGM algorithms, such as contrastive divergence. We also explore this use in the next section.One might object that most results in this paper use sigmoid activation functions. Nair and Hinton showed that rectified linear units (ReLU) might be thought of as a combination of infinitely many sigmoid units with varying biases [Nair and Hinton, 2010] . Hence our result in the previous section can be extended to ReLU activations by the same argument. More generally, with any non-negative activation function that can yield values greater than one, while our BN argument no longer holds, the MN version of the argument can be extended. An MN already requires normalization to represent a probability distribution. While Batch Normalization and Layer Normalization typically are motivated procedurally, to keep nodes from "saturating," and consequently to keep gradients from "exploding" or "vanishing," as the names suggest, they might also be used to bring variables into the range [0, 1] and hence to being considered as probabilities. Consider an idealized variant of these that begins by normalizing all the values coming from a node h of a neural network, over a given minibatch, to sum to 1.0; the argument can be extended to a set of h and all its siblings in a layer (or other portion of the network structure) assumed to share their properties. It is easily shown that if the parents of any node h in the neural network provide to h approximate probabilities that those parent variables are true in the distribution defined by the Markov network given the inputs, then h in turn provides to its children an approximate probability that h is true in the distribution defined by the Markov network given the inputs. Use of a modified Batch or Layer Normalization still would be only approximate and hence adds an additional source of approximation to the result of the preceding section. Detailed consideration of other activation functions is left for further work; in the next section we return to the sigmoid case. 
application of the theory: a new hamiltonian monte carlo algorithm: 
 To illustrate the potential utility of the infinite tree-structured PGM view of a DNN, in this section we pursue one of its implications in greater depth; other implications for further study are summarized in the Conclusion. We have already noted we can view forward propagation in an all-sigmoid DNN as exact inference in a tree-structured PGM, such that the CPD of each hidden variable is a logistic regression. In other words, each hidden node is a Bernoulli random variable, with parameter λ being a sigmoid activation (i.e. logistic function) applied to a linear function of the parent nodes. This view suggests alternative learning or fine-tuning algorithms such as contrastive divergence (CD) [Carreira-Perpinan and Hinton, 2005 , Bengio and Delalleau, 2009 , Sutskever and Tieleman, 2010] . CD in a CRF uses MCMC inference with many MCMC chains to estimate the joint probability over the hidden variables given the evidence (the input and output variables in a standard DNN), and then takes a gradient step based on the results of this inference. But to increase speed, CD-n advances each MCMC chain only n steps before the next gradient step, with CD-1 often being employed. CD has a natural advantage over SGD, which samples the values of the hidden variables using only the evidence at the input values; instead, MCMC in CD uses all the available evidence, both at input and output variables. Unfortunately, if the MCMC algorithm employed is Gibbs sampling on the many hidden variables found in a typical neural network, then it suffers from high cost in computational resources. MCMC has now advanced far beyond Gibbs sampling with methods such as Hamiltonian Monte Carlo (HMC), but HMC samples values in [0, 1] rather than {0, 1}. Our theoretical results for the first time justify the use of HMC rather than Gibbs sampling in a DNN, as follows.Recall that the DNN is itself a BN with sigmoid CPDs, but if we take the values of the hidden variables to be binary then DNN training is not correct with respect to this BN. Instead, based on the correctness of our infinite tree-structured PGM, the probabilistic behavior of one hidden node in the BN is the result of sampling values across its L copies in the PGM. Within any copy, the value of the hidden node follows the Bernoulli distribution with the same probability distribution as the other copies, determined by the parent nodes. Since all the copies share the same parent nodes by the construction and are sampled independently, the sample average follows a normal distribution as the asymptotic distribution when L → ∞ by the central limit theorem. In practice, L is finite and this normal distribution is a reasonable approximation to the distribution of the hidden node. Thus in the BN, whose variables correspond exactly with those of the DNN, the variables have domain [0,1] rather than {0, 1}, as desired. We precisely define this BN and resulting HMC algorithm next.Consider a Bayesian network composed of input variables x = h 0 , a sequence of layers of hidden variables h 1 , ..., h K , and output variables y. Each pair of consecutive layers forms a bipartite subgraph of the network as a whole, and the variables h i = (h i1 , ..., h iMi ) follow a multivariate normal distribution with parameters p i = (p i1 , ..., p iMi ) that depend on variables in the previous layer h i-1 as follows:EQUATIONwhere σ : R → (0, 1) is a non-linearity -here the logistic function -that is applied element-wise, and θ i = (W i , b i ) are parameters to be learned. The distribution in equation ( 1) is motivated by supposing that h ij is the average of L copies of the corresponding node in the PGM, each of which is 1 with probability p ij and zero otherwise, then applying the normal approximation to the binomial distribution. Importantly, this approximation is valid only for large L.For a complete setting of the variables {x, h, y}, where h = {h 1 , ..., h K }, and parameters θ = {θ i } K i=0 , the likelihood p(y, h|x; θ) may be decomposed as:EQUATIONwhere p N (•|•) denotes the normal density, and a specific form for p(y|h K ; θ K ) has been omitted to allow variability in the output variables. In our experiments, y is a Bernoulli(binary) or categorical random variable parameterized via the logistic(sigmoid) or softmax function, respectively.Let h (0) , h (1) , h (2) , ... denote a chain of MCMC samples of the complete setting of hidden variables in the neural network. As previously noted, we allow hidden variables h ij ∈ (0, 1) for i ∈ {1, ..., K} and j ∈ {1, ..., M i }, and use Hamiltonian Monte Carlo (HMC) to generate the next state due to its fast convergence. Since HMC samples are unbounded, we sample the logit associated with h ij ∈ (0, 1), i.e. σ -1 (h ij ) ∈ (-∞, ∞), rather than sampling the h ij directly.The HMC trajectories are defined by Hamilton's Equations:dρ i dt = ∂H ∂µ i dµ i dt = - ∂H ∂ρ i (3)where ρ i , µ i are the ith component of the position and momentum vector. They are intermediate variables used to generate a new state for the MCMC chain. The Hamiltonian H isH = H(ρ, µ) = U (ρ) + 1 2 µ T M -1 µ (4)where M -1 is a positive definite convariance matrix and acts as a metric to rotate and scale the target distribution, which is usually set to identity matrix in practice. Defining the position ρ = h, the complete set of hidden variables of the network, we have that the potential energy U is the negative log-likelihood associated with equation ( 2):U (h) = -log p(y, h|x; θ) = -log p(y|h K ; θ K ) - K i=1 Mi j=1 log p N (h ij |p ij (h i-1 ; θ i-1 )). (5)We set the leap frog size l > 0, step size ∆t > 0. A description of the HMC trajectories (i.e., evolution of h) is provided in Appendix E.The initial state of the chain h (0) is drawn with a simple forward pass through the network, ignoring the output variables; in other words, we have hEQUATIONi-1 ) j ) for i ∈ {1, ...K}, where h 0 = x are the input variables, and the values of W (0) i and b (0) i are manually set or drawn from a standard normal or uniform distribution. We update h through a number of burn-in steps before beginning to update our parameters to ensure that h is first consistent with evidence from the output variables. After k steps, corresponding to CD-k, we define the loss based on equation (2):EQUATION)We then apply the following gradients to update the parameters {W(n) i } K i=0 and {b (n) i } K i=0 : W (n+1) i = W (n) i -η ∂L ∂W (n) i b (n+1) i = b (n) i -η ∂L ∂b (n) i (7)where η is the learning rate. Algorithm 3 (see Appendix F) summarizes this procedure.The previous section discussed the modeling of the HMC learning algorithm inspired by the construction of tree-structured PGMs. This section compares the proposed algorithm to Gibbs sampling and SGD training with DNNs in both the synthetic experiments and experiments on Covertype dataset [Blackard, 1998] , which is a real-world dataset for classification. They are designed to illustrate how the HMC-based algorithm could fine-tune and improve the calibration of DNNs. The experimental setup and additional experiments are described in Appendix. An internal cluster of GPUs was employed for all experiments, and part of run-times are provided in the appendix; as anticipated, SGD is faster than HMC, which is faster than Gibbs.The synthetic datasets are generated by simple BNs and MNs with their weights in different ranges, which are used to define the conditional probabilistic distributions for BNs and potentials for MNs. Each dataset contains 1000 data points {(X i , y i )}, i = 1, 2, ..., 1000, where each input X i ∈ {0, 1} n is a binary vector with n dimension and each output y i ∈ {0, 1} is a binary value. The true probabilistic distribution P (y|X) of the corresponding BN/MN is calculated by sampling or applying the VE algorithm on it.To explore how the proposed algorithm performs in model calibration, a DNN is first trained with SGD for 100 or 1000 epochs, and then fine-tuned by Gibbs or HMC with different L's for 20 epochs based on the trained DNN model. Here L defines the normal distribution for hidden nodes in Eqn. 1 and is explored across the set of values: {10, 100, 1000}. The calibration is assessed by mean absolute error (MAE) in all the synthetic experiments and compared between non-extra fine-tuning (shown in the "DNN" column in Table 1 ) and fine-tuning with Gibbs or HMC. Since the ground truth of P (y|X) in the synthetic dataset can be achieved from the BN/MN, the MAE is calculated by comparing the predicted P (y|X) from the finetuned network and the true probability. Similar experiments are also run on the Covertype dataset to compare the calibration of SGD in DNNs, Gibbs and the HMC-based algorithm. Since the ground truth for the distribution of P (y|X) cannot be found, the metric for the calibration used in this experiment is the expected calibration error (ECE), which is a common metric for model calibration. To simplify the classification task, we choose the data with label 1 and 2 and build two binary subsets, each of which contains 1000 data points. Similarly, the number of training epochs is also 100 or 1000, while the fine-tuning epochs shown in Table 2 is 20.Table 2 shows that HMC with L = 10 fine-tuning generally performs better than DNN results, and HMC with L = 1000 has the similar ECE as that in DNN. It meets the conclusion made in the synthetic experiments. Gibbs sampling, however, could perform worse than just using DNN. It could be because Gibbs may be too far removed from the DNN, whereas our proposed HMC is more in the middle. This suggests perhaps future work testing the gradual shift from DNN to HMC to Gibbs. We note that the large treewidth-1 PGM is a substantial approximation to the direct PGM of a DNN -in other words, the PGM whose structure exactly matches that of the DNN. In future work, we will explore other DNN fine-tuning methods, perhaps based on loopy belief propagation or other approximate algorithms often used in PGMs, that may allow us to more closely approximate inference in this direct PGM.Another direction for further work is in the original motivation for this work. Both DNNs and PGMs are often used to model different components of very large systems, such as the entire gene regulatory network in humans. For example, in the National Human Genome Research Institute (NHGRI) program Impact of Genetic Variation on Function (IGVF), different groups are building models of different parts of gene regulation, from genotypic variants or CRISPRi perturbations of the genome, to resulting changes in transcription factor binding or chromatin remodeling, to post-translational modifications, all the way to phenotypes characterized by changes in the expression of genes in other parts of the genome IGVF Consortium [2024] . Some of these component models are DNNs and others are PGMs. As a community we know from years of experience with PGMs that passing the outputs of one model to the inputs of another model is typically less effective than concatenating them into a larger model and fine-tuning and using this resulting model. But this concatenation and fine-tuning and usage could not be done with a mixture of PGM and DNN components until now. Having an understanding of DNN components as PGMs enables their combination with PGM components, and then performing fine-tuning and inference in the larger models using algorithms such as the new HMC algorithm theoretically justified, developed, and then evaluated in this paper. Furthermore, the same HMC approach can be employed to reason just as easily from desired gene expression changes at the output nodes back to variants or perturbations at the input nodes that are predictive of the desired changes. Ordinarily, to reason in reverse in this way in a DNN would require special invertible architectures or training of DNNs that operate only in the other direction such as diffusion. Experiments evaluating all these uses of HMC (or other approximate algorithms in PGMs such as loopy belief propagation or other message passing methods) are left for future work.We don't claim the following theorem is new, but we provide a proof because it captures several components of common knowledge to which we couldn't find a single reference.Theorem 3. Let N be a Bayesian belief network whose underlying undirected graph has treewidth 1, and let w AB denote the coefficient of variable A in the logistic CPD for its child B. Let M be a binary pairwise Markov random field with the same nodes and edges (now undirected) as N . Let M 's potentials all have the value e w AB if the nodes A and B on either side of edge AB are true, and the value 1 otherwise. M and N represent the same joint probability distribution over their nodes.Proof. According to M the probability of a setting ⃗ V of its variables is1 Z Π i ϕ i ( ⃗ V )where ϕ i are the potentials in M , and Z is the partition function, defined asZ = Σ ⃗ V Π i ϕ i ( ⃗ V )We use DOM (ϕ) to designate the variables in a potential ϕ. Because the nodes and structures of M and N agree, we will refer to the parents, children, ancestors, and descendants of any node in M to designate the corresponding nodes in N . Likewise we will refer to the input and output variables of M as those nodes of N that have no parents and no children, respectively. Because M has treewidth 1, each node of M d-separates its set of ancestors from its set of descendants and indeed from all other nodes in M . As a result, it is known that the partition function can be computed efficiently in treewidth-1 Markov networks, for example by the following recursive procedure f defined below. Let V 0 be the empty set of variables, and let V 1 be the input variables of M . Let Ch(V ) denote the children of any set V of variables in M , and similarly let P a(V ) denote the parents of V . For convenience, when V is a singleton we drop the set notation and let V denote the variable itself. For all natural numbers i ≥ 0:f (V i ) = Π N ∈Ch(Vi) Σ N =0,1 Π ϕj :DOM (ϕj )⊆Vi,DOM (ϕj )̸ ⊆Vi-1 ϕ j (V i ) f (V m+1 ) = 1where V m is not the full set of variable in M but V m+1 is the full set. Then Z = f (V 1 ).For each variable v ∈ ⃗ V , we can multiply the potentials on the edges between v and its parents, to get a single potential ϕ {v,P a(v)} over {v, P a(v)}. For a given setting of the parents of v in ⃗ V , let ϕ v|P a(v) denote the result of conditioning on this setting of the parents, and let ϕ v,¬v|P a(v) denote the result of summing out variable v. Using these product potentials of M , and given the method above for computing Z for a tree-structured Markov network, we can define the probability of a particular setting ⃗ V asP ( ⃗ V ) = Π v∈ ⃗ V ϕ v|P a(v) ϕ v,¬v|P a(v)These terms are exactly the terms of the logistic conditional probabilities of the Bayesian belief network N :P ( ⃗ V ) = Π v∈ ⃗ V P (v|P a(v))Note that in general when converting a Bayes net structure to a Markov net structure, to empower the Markov net to represent any probability distribution representable by the Bayes net we have to moralize. A corollary of the above theorem is that in the special case where the Bayes net uses only sigmoid activations, and its underlying undirected graph is tree-structured, moralization is not required.In the following, calls to add to sets V or E (or to check if either set contains a vertex or edge) immediately edits/checks the respective set object that they reference.Require: A list H of the output vertices of the DNN's DAG G Ensure: A set of vertices V and edges E of the DNN's original DAG transformed to a tree structured graph, as shown in Figure 1 1: let V be an empty set of vertices 2: let E be an empty set of edges 3: V, E ← DNN_TREE(H, G, V , E, ' ') 4: procedure DNN_TREE(H, G, V , E,Require: A graph G of the vertices and edges created in Step 1, a list H of the DNN's output vertices, an integer l Ensure: Vertices V and edges E of the final tree structure graph with l copies of each parent node from Step 1 1: let V be an empty set of vertices 2: let E be an empty set of edges 3: for each vertex in H do 4:V ′ , E ′ ← DNN_COPY(vertex, G, vertex, V , E, l) 5: V ← V .union(V ′ ), E ← E.union(E ′ ) 6: end for 7: procedure DNN_COPY(current, G, copy, V , E, l) 8:V .add(copy) 9:for each parent in G.parents(current) do 10:weight ← G.getWeight(parent, current) 11:for i ← 1 to l do 12:n ← parent + '-' + i ▷ create the ith copy in the current subtree 13:while n in V do ▷ create a unique label so the graph retains its tree-structure 14:n ← n + '′' 15:end while 16:let e be an edge between copy and n ▷ connect this new copied node to the previous 17:E.add(e), E.addWeight(e, weight/l) 18:DNN_COPY(parent,G,n,V ,E,l) ▷ create copies in the remaining subtrees 19:end for 20:end for 21: return V , E 22: end procedureIn order to prove that as L goes to infinity, this PGM construction does indeed match the neural network's forward propagation, we consider an arbitrary latent node H with N unobserved parents h 1 , ..., h N , and M observed parents g 1 , ..., g M . The edges between these parents and H then have weights θ i , 1 ≤ i ≤ N , for the unobserved nodes, and weights w j , 1 ≤ j ≤ M , for the observed nodes. The network as a whole has observed evidence ⃗ x. For the rest of this problem we use a Markov network view of the neural network. The relevant potential passed from the unobserved parent nodes of H, ϕ(h i ) (as per the directed version of the graph) forward to H have the following form:h i ¬h i e pi 1Since g j are observed, their values are found in ⃗ x. Finally, the potentials between each of these nodes and the central node H are as follows:H ¬H h i e θi 1 ¬h i 1 1 H ¬H g j e wj 1 ¬g j 1 1Suppose, then, using the second step of our construction, we make L copies of all the nodes that were parents of H in the directed version of the tree, h 1 1 , ..., h L 1 , ..., h 1 N , ..., h L N and g 1 1 , ..., g L 1 , ..., g 1 M , ..., g L M with weights θ 1 /L, ..., θ N /L and w 1 /L, ..., w M /L respectively. The potentials between H and these copied nodes is then:H ¬H h k i e θi/L 1 ¬h k i 1 1 H ¬H g k j e wj /L 1 ¬g k j 1 1where 1 ≤ i ≤ N , 1 ≤ j ≤ M , and 1 ≤ k ≤ L. The relevant potentials for each of the copied nodes to be passed forward are the same as the nodes they were originally copied from. We then have that,ϕ(H, h 1 1 , ..., h L 1 , ..., h 1 N , ..., h L N , g 1 1 , ..., g L 1 , ..., g 1 M , ..., g L M |⃗ x) = M j=1 L k=1 e (w j /L)H×g k j × N i=1 L k=1 e (θ i /L)H×h k i ϕ(h k i ) = e M j=1 w j g j ×H × N i=1 L k=1 e (θ i /L)H×h k i ϕ(h k i ).Summing out an arbitrary, copied latent node, h β α :h β α ,¬h β α ϕ(H, h 1 1 , ..., h L 1 , ..., h 1 N , ..., h L N |⃗ x) = e M j=1 wj gj ×H × h β α ,¬h β α N i=1 L k=1 e (θi/L)H×h k i ϕ(h k i ) = e M j=1 wj gj ×H ×     e pα e (θα/L)H × i=1,..,N (i,k)̸ =(α,β) k=1,...L e (θi/L)H×h k i ϕ(h k i ) + i=1,..,N (i,k)̸ =(α,β) k=1,...L e (θi/L)H×h k i ϕ(h k i )     = e M j=1 wj gj ×H × (e pα e (θα/L)H + 1) ×     i=1,..,N (i,k)̸ =(α,β) k=1,...L e (θi/L)H×h k i ϕ(h k i )     .Summing out all L copies of h α : ϕ(H = 1|⃗ x) = e M j=1 w j g j ×1 × N i (e p i e (θ i /L)×1 + 1) L e M j=1 w j g j ×0 × N i (e p i e (θ i /L)×0 + 1) L = e M j=1 w j g j × N i (e p i e (θ i /L) + 1) L N i (e p i + 1) L .We then consider: L × log(e pi e (θi/L) + 1) , and the logarithm of this limit is,lim L→∞ M j=1 wjgj - N i=1L × log(e p i + 1)+ N i=1 L × log(e p i e (θ i /L) + 1) = M j=1 wjgj + lim L→∞ N i=1log(e p i e (θ i /L) + 1) -log(e p i + 1) 1/L .The limit in the previous expression clearly has the indeterminate form of 0 0 . Let G = M j=1 w j g j and consider the following change of variables, S = 1/L, and subsequent use of l'Hôspital's rule. w j g j + N i σ(p i )θ i ),The collected potential at node H from summing out its ancestors (from the directed view) then has the form:h i ¬h i exp( M j=1 w j g j + N i σ(p i )θ i ) 1This is exactly the form of messages that we assumed were originally passed to node H. Suppose then that z is a hidden node whose parents in the original deep neural network's DAG are all observed. By our PGM construction, we have that node z collects potential e x∈⃗ x wzxx for z true and 1 for z false from our initial forward step. Here w zx is the weight between nodes z and x. Consider, then, the nodes whose parents in the DNN's DAG are either one of these first layer hidden nodes, or an observed node. By our PGM construction, we have shown that so long as the nodes in the previous layer are either observed or have this exponential message product, as is the case here, the message product of the nodes that immediately follow will have the same form.Note that in order to calculate probability, P (H|⃗ x), we must also consider the influence that the child of node H, call this C, has on node H itself (this would be information passed through and collected at later nodes in the tree network that are then passed back through this node C to node H) or may not exist at all in the case of output nodes. Suppose the weight between this child C and node H is γ. Suppose also that the message coming from node C to H has the following form, where c is a non-negative real value that can be arbitrarily large.C ¬C c 1Finally, note that with the L copies made in this graph, the potential between node H and C has the form:H ¬H C e γ/L 1 ¬C 1 1Using the potential collected at H from the forward pass and this addition information from C, we can then calculate the probability of node H given the input evidence ⃗ x:P (H|⃗ x) = 1 Z × e ( M j=1 wj gj + N i σ(pi)θi)×H × C e γ/L×C×H ϕ(C) = 1 Z × e ( M j=1 wj gj + N i σ(pi)θi)×H × (ce γ/L×H + 1)From this we have that:P (H = 1|⃗ x) = e ( M j=1 wj gj + N i σ(pi)θi)×1 × (ce γ/L×C×1 + 1) e ( M j=1 wj gj + N i σ(pi)θi)×1 × (ce γ/L×C×1 + 1) + e 0 × (ce 0 + 1) = e M j=1 wj gj + N i σ(pi)θi × (ce γ/L×C×1 + 1) e M j=1 wj gj + N i σ(pi)θi × (ce γ/L×C×1 + 1) + (c + 1) = e M j=1 wj gj + N i σ(pi)θi e M j=1 wj gj + N i σ(pi)θi + (c + 1)/(ce γ/L×C×1 + 1).Note that lim L→∞ (c + 1)/(ce γ/L×C×1 + 1) = 1, i.e. as L grows increasingly large the information passed through this child node becomes negligible. We therefore have thatP (H = 1|⃗ x) = σ( M j=1 w j g j + N i σ(p i )θ i ), which is exactly the sigmoid activation value found in the forward pass of the neural network. Since every node in this network have the same form of incoming messages from their parents and child, we have that the conditional probability in this PGM construction and the activation values of the DNN match for any node in any layer of the DNN/PGM.From An Introduction to Conditional Random Fields Sutton and McCallum [2012] we have the gradient of weight w pk for this form of CRF can be written as:∂l ∂w pk = Ψc∈Cp h ′ c P (h ′ c |y, x)f k (y c , x c , h ′ c ) - Ψc∈Cp h ′ c ,y ′ c P (h ′ c , y ′ c |x)f k (y ′ c , x c , h ′ c ).Since the features on the cliques of the proposed infinite width-PGM structure are non-zero (1/L, which is a minor change from instead dividing each weight by L) only when the two adjacent nodes are both 1 (true), this expression simplifies. The update on a specific edge in the PGM then takes the following form and the complete weight update would be the summation over the updates on each edge the weight of interest appears.(1/L)[P (h n = 1, h n+1 = 1|x, y) -P (h n = 1, h n+1 = 1|x)],where h n and h n+1 are the nodes that the edge connects.Consider a single branch in the infinite width PGM structure. Let h n be the node closer to the output node and let it be exactly n nodes separated from said output (node h n+1 is then naturally the next node in this branch). Due to the infinite-width structure of the proposed PGM there are L n+1 copies of this exact path ending in the weight of interest. These copied paths are entirely equivalent to one another.Suppose now we sum out the influence output y has on the weight update of these paths. Note that this could be written equivalently as summing out node h 0 .P (h n = 1, h n+1 = 1|x, y) -P (h n = 1, h n+1 = 1|x) = P (h n = 1, h n+1 = 1|x, y) - y P (h n = 1, h n+1 = 1, y|x) = P (h n = 1, h n+1 = 1|x, y) - y P (h n = 1, h n+1 = 1|x, y)P (y|x) = yP (h n = 1, h n+1 = 1|x, y = 1) + (1 -y)P (h n = 1, h n+1 = 1|x, y = 0) -P (h n = 1, h n+1 = 1|x, y = 1)P (y = 1|x) -P (h n = 1, h n+1 = 1|x, y = 0)P (y = 0|x) = (y -ŷ)P (h n = 1, h n+1 = 1|x, y = 1) + (1 -y -(1 -ŷ))P (h n = 1, h n+1 = 1|x, y = 0) = (y -ŷ)[P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0)]Note that if we are considering the weight update on the connections between the output and its neighbors, this update can be used immediately as y would be h 0 . The update across all L copies would then have the form:L k=1 (1/L)(y -ŷ)[P (h 0 = 1, h 1 = 1|x, h 0 = 1) -P (h 0 = 1, h 1 = 1|x, h 0 = 0)] = L k=1 (1/L)(y -ŷ)P (h 1 = 1|x, h 0 = 1) = (y -ŷ)P (h 1 = 1|x, h 0 = 1)We can easily calculate P (h 1 = 1|x, h 0 = 1) used in this update as follows. Let node h i have conditional probability σ(S hi ), which corresponds to a forward product of messages of the form:h i ¬h i e S h i 1Let the weight between nodes h i and h i-1 in the path of interest be w i-1 . The product of messages at h i then including the fact that we know h i-1 = 1, then has the form:h i ¬h i e S h i +wi-1/L 1From this, we can then calculate:P (h i = 1|h i-1 = 1) = σ(S hi + w i-1 /L). (D.1)For the update of the weights surrounding the output, the overall update must then have the form (1/L)(y -ŷ)σ(S h1 + w 0 /L). Note that there are L such copies of this update and L is infinitely large.The overall update of w 0 is then finally, limL→∞ L k=1 (1/L)(y-ŷ)σ(S h1 +w 0 /L) = (y-ŷ)σ(S h1). This exactly matches the update of w 0 in the gradient descent step of the neural network.We now consider the updates of weights with further depth away from the output. This update take the form(1/L)(y -ŷ)[P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0)].For the remainder of this proof we focus on this difference of probabilities. Note however, the complete update does include this (1/L)(y -ŷ) term.P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0) = h1 [P (h n = 1, h n+1 = 1, h 1 |x, y = 1) -P (h n = 1, h n+1 = 1, h 1 |x, y = 0)] = P (h n = 1, h n+1 = 1, h 1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1, h 1 = 1|x, y = 0) + P (h n = 1, h n+1 = 1, h 1 = 0|x, y = 1) -P (h n = 1, h n+1 = 1, h 1 = 0|x, y = 0) = P (h n = 1, h n+1 = 1|x, y = 1, h 1 = 1)P (h 1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0, h 1 = 1)P (h 1 = 1|x, y = 0) + P (h n = 1, h n+1 = 1|x, y = 1, h 1 = 0)P (h 1 = 0|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0, h 1 = 0)P (h 1 = 0|x, y = 0) (Since h n , h n+1 ⊥ y|h 1 ) = P (h n = 1, h n+1 = 1|x, h 1 = 1)P (h 1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, h 1 = 1)P (h 1 = 1|x, y = 0) + P (h n = 1, h n+1 = 1|x, h 1 = 0)P (h 1 = 0|x, y = 1) -P (h n = 1, h n+1 = 1|x, h 1 = 0)P (h 1 = 0|x, y = 0) = P (h n = 1, h n+1 = 1|x, h 1 = 1)(P (h 1 = 1|x, y = 1) -P (h 1 = 1|x, y = 0)) + P (h n = 1, h n+1 = 1|x, h 1 = 0)(P (h 1 = 0|x, y = 1) -P (h 1 = 0|x, y = 0)) = [P (h n = 1, h n+1 = 1|x, h 1 = 1) × (P (h 1 = 1|x, y = 1) -P (h 1 = 1|x, y = 0))] + [P (h n = 1, h n+1 = 1|x, h 1 = 0) × (1 -P (h 1 = 1|x, y = 1) -(1 -P (h 1 = 1|x, y = 0)))] = (P (h 1 = 1|x, y = 1) -P (h 1 = 1|x, y = 0))× [P (h n = 1, h n+1 = 1|x, h 1 = 1) -P (h n = 1, h n+1 = 1|x, h 1 = 0)] Note that P (h n = 1, h n+1 = 1|x, h 1 = 1) -P (h n = 1, h n+1 = 1|x, h 1 = 0)has the exact same form as the difference we started with, but y (or written equivalently h 0 ) has been effectively replaced with h 1 . Due to the tree structure of the PGM, the conditional independence relationships are also entirely equivalent. If h 2 then also existed in this branch and preceded h n , we could then apply the exact same operations to 'sum out' h 1 in this expression and replace it with h 2 . This can be repeated until h n itself is reached and we condition on the node one position closer to the output h n+1 . Note that at for step we must multiply the entire expression by (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0)) terms.Suppose, for the sake of induction,P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0) = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k = 1) -P (h n = 1, h n+1 = 1|x, h k = 0)],where n > k. We have already shown that this holds for the base case of k = 1. We then consider the case of (k + 1):P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0) (By the inductive hypothesis) = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k = 1) -P (h n = 1, h n+1 = 1|x, h k = 0)] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × h k+1 [P (h n = 1, h n+1 = 1, h k+1 |x, h k = 1) -P (h n = 1, h n+1 = 1, h k+1 |x, h k = 0)] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × h k+1 [P (h n = 1, h n+1 = 1|x, h k = 1, h k+1 )P (h k+1 |x, h k = 1) -P (h n = 1, h n+1 = 1|x, h k = 0, h k+1 )P (h k+1 |x, h k = 0)] (Since h n , h n+1 ⊥ h k |h k+1 ) = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × h k+1 [P (h n = 1, h n+1 = 1|x, h k+1 )P (h k+1 |x, h k = 1) -P (h n = 1, h n+1 = 1|x, h k+1 )P (h k+1 |x, h k = 0)] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × h k+1 [P (h n = 1, h n+1 = 1|x, h k+1 )(P (h k+1 |x, h k = 1) -P (h k+1 |x, h k = 0))] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k+1 = 1)(P (h k+1 = 1|x, h k = 1) -P (h k+1 = 1|x, h k = 0)) + P (h n = 1, h n+1 = 1|x, h k+1 = 0)(P (h k+1 = 0|x, h k = 1) -P (h k+1 = 0|x, h k = 0))] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k+1 = 1)(P (h k+1 = 1|x, h k = 1) -P (h k+1 = 1|x, h k = 0)) + P (h n = 1, h n+1 = 1|x, h k+1 = 0) × (1 -P (h k+1 = 1|x, h k = 1) -1 + P (h k+1 = 1|x, h k = 0))] = [ k i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k+1 = 1)(P (h k+1 = 1|x, h k = 1) -P (h k+1 = 1|x, h k = 0)) -P (h n = 1, h n+1 = 1|x, h k+1 = 0)(P (h k+1 = 1|x, h k = 1) -P (h k+1 = 1|x, h k = 0))] = [ k+1 i=1 (P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0))] × [P (h n = 1, h n+1 = 1|x, h k+1 = 1) -P (h n = 1, h n+1 = 1|x, h k+1 = 0)].We therefore have that P (h n = 1, h n+1 = 1|x, y = 1) -P (h n = 1, h n+1 = 1|x, y = 0) can be written as a product of the differences P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0) multiplied by the differenceP (h n = 1, h n+1 = 1|x, h k = 1) -P (h n = 1, h n+1 = 1|x, h k = 0), for any k < n.Note that from D.1 we have that P (h i = 1|x, h i-1 = 1) = σ(S hi + w i-1 /L) where w i-1 is the weight between the two nodes and S hi is the internal summation at h i from the forward pass of the neural network prior to applying the sigmoid activation function σ(•). It similarly follows that P (h i = 1|x, h i-1 = 0) = σ(S hi ). We then divide and multiply this difference by w i-1 /L.P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0)) = (w i-1 /L) P (h i = 1|x, h i-1 = 1) -P (h i = 1|x, h i-1 = 0)) w i-1 /L = (w i-1 /L) σ(S hi + w i-1 /L) -σ(S hi ) w i-1 /LNote that the right hand term of the above expression has the same form as the definition of a derivative when placed within the limit as L approaches infinity, i.e.:lim L→∞ σ(S hi + w i-1 /L) -σ(S hi ) w i-1 /L = ∂ ∂S hi σ(S hi ).At each step away from the output of the network along this branch, we are therefore multiplying by derivative of the local sigmoid per step (this exactly matches the behaviour of the backward pass of the neural network) multiplied by the relevant weight. There is naturally the concern of the remaining 1 L term both per step and in the (y -ŷ)/L term. Recall that there are L n+1 copies of the weight of interest in branches with the exact same structure. We sum over these equivalent weight updates and so haveL n+1 i=1 1 L n+1 = 1.The summation of all these equivalent weight updates effectively cancels this repeated division (note that this is including the 1/L term shown in the final step of this proof).We finally consider the difference involving nodes n and n + 1 conditioned on node n -1.P (h n = 1, h n+1 = 1|x, h n-1 = 1) -P (h n = 1, h n+1 = 1|x, h n-1 = 0) = P (h n+1 = 1|x, h n-1 = 1, h n = 1)P (h n = 1|x, h n-1 = 1) -P (h n+1 = 1|x, h n-1 = 0, h n = 1)P (h n = 1|x, h n-1 = 0) (Since h n+1 ⊥ h n-1 |h n ) = P (h n+1 = 1|x, h n = 1)P (h n = 1|x, h n-1 = 1) -P (h n+1 = 1|x, h n = 1)P (h n = 1|x, h n-1 = 0) = σ(S n+1 + w n /L) × (P (h n = 1|x, h n-1 = 1) -P (h n = 1|x, h n-1 = 0)) = σ(S n+1 + w n /L) × (w n-1 /L)( σ(S hn + w n-1 /L) -σ(S hn ) w n-1 /L )The right hand term becomes the derivative of σ(S hn ) as in earlier steps and the left σ(•) term becomes σ(S n+1 ) i.e. the forward pass value at node n + 1, the last node relevant to this weight calculation on this branch.The entire weight update then has the form:(y -ŷ) × [ n i=1 w i-1 ∂ ∂S hi σ(S hi )] × σ(S n+1 )This is exactly the gradient update in the neural network when considering a specific path/weight combination in the network. The infinite width PGM naturally has branches for each possible path in the neural network and as such the complete weight updates of both views will align.Suppose the current chain state is h (n) = ρ n (0). We then draw a momentum µ n (0) ∼ N (0, M ).The HMC trajectories imply that after ∆t, we have:µ n (t + ∆t 2 ) = µ n (t) - ∆t 2 ∇U (ρ) ρ=ρn(t) ρ n (t + ∆t) = ρ n (t) + ∆tM -1 µ n (t + ∆t 2 ) µ n (t + ∆t) = µ n (t + ∆t 2 ) - ∆t 2 ∇U (ρ) ρ=ρn(t+∆t).(E.1)We may then apply these equations to ρ n (0) and µ n (0) L times to get ρ n (L∆t) and µ n (L∆t). Thus, the transition from h (n) = ρ n to the next state h (n+1) is given by: h (n+1) (h (n) = ρ n (0)) = ρ n (L∆t) with probability α(ρ n (0), ρ n (L∆t)) ρ n (0) otherwise (E.for i ← 0 to N -1 do 3: h (i+1) ← Sampling(h (i) , W (0) ,b (0) ) 4:end for 5: end procedure 6: procedure TRAINING(M ) 7:for i ← 0 to M -1 do 8: W (i+1) , b (i+1) ← Weight-updating(h (N +ik) , W (i) , b (i) ) 9:for j ← 0 to k -1 do 10:h (N +ik+j+1) ← Sampling(h (N +ik+j) , W (i+1) , b (i+1) ) 11:end for 12:end for 13: end procedureIn our experiments, k = 1, i.e. we do one sampling step before weight updating. We mainly use HMC sampling method for the sampling step, where the detailed trajectories are defined in Appendix E. The weight-updating step is defined in equations ( 2), ( 6) and ( 7). 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: All details are in the paper, appendix, or code link.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: We conducted each individual synthetic experiment 100 times and performed paired t-tests to assess statistical significance. The p-values are reported in the results section.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes] Justification: We say the work was on an internal GPU cluster, and that all experiments are reported. The precise individual run-times are in Appendix H; in the text we simply summarize that SGD is the fastest, Gibbs is the slowest, and HMC is in between.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We read the Code, and the research here conforms fully.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The most important motivation and selling point for this work is the ability to better understand a trained neural network as a proper statistical model. This ability is key to trustworthy AI.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
new assets: 
 Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?Answer: [Yes] Justification: Only assets are algorithms, theoretical results, and code. The first two are described in detail, and code is available (currently anonymized for double-blind review).Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?Answer: [NA] Justification: No human subjects or crowdsourcing.Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?Answer: [NA] Justification: see above justification Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: This paper shows how to re-interpret deep neural networks with sigmoid activations as Bayesian networks.  The reviewers have rather mixed opinions. One reviewer points out some (potential) flaws in the DNN interpretation in terms of discrete versus continuous RVs. The rebuttal clarified quite some of the issues raised. However, the DNN interepretation seems not to be highgly novel as it is very much related to learning message-passing inference, as e.g. considered by Ross et al. (Learning message-passing inference machines for structured prediction, CVPR 2011); this should be clarified. INdeed, this is starting from a BN, but it also suggest that there is a tight connection. Anyhow, the paper is not just about the DNN interpretation but also about the new sampling approach derived via the interpretation. This also addresses to some extend another point raised by one reviewer, namely that the "practical utility of going from the DNN function space to the PGM space is yet unknown"; the development of new algorithm is definitely something interesting. So overall, reducing the weight of the negatgive review (as the rebuttal addressed many of the points), the connection between PGMs and DNNs is beneficial and worth exploring and revisiting (including connections to some of the older works that other reviewers have mentioned).

Reviews: review: paper_summary: paper_summary: This paper re-interprets deep neural networks (with sigmoid activations) as probabilistic models.  The authors give a construction that converts a DNN to an infinite tree-structured PGM, which has the benefit of yielding probabilstic information about its internal nodes.  The key step is to copy input nodes so that they are only used once, and that their expectation functions as their value. The authors then prove that, in a certain infinite limit, the semantics are the same as of the original DNN.  They then set up synthetic experiments using Hamiltonian Monte Carlo sampling on an approximation to this PGM, and report that their results help to reduce overfitting in small synthetic datasets.
strength_weakness: strength_weakness: The paper has major weaknesses in both the theoretical and the experimental parts.  On the theoretical side, the constructions  are imprecisely presented, and it is not at all clear to me that the main theoretical contribution of the paper (Theorem 1) delivers on the promises made on the introduction, nor that it is pedagogically useful.  At a lower level, it seems there are a lot of minor bugs and ambiguities and undefined symboles that have been swept under the rug.  At a minimum, I think the theoretical part of this paper needs a major rewrite with an eye towards precision and detail. 

On the empirical side, I'm afraid the experiments are not totally convincing either.  My biggest problem is the lack of standard baselines. Why go all the way to HMC?  The setup seems a bit rigged: by training a DNN with SGD on such a small number of samples, you are bound to see overfitting, and the new methods get to start from the maximum likelihood solution found by SGD. Why is the "cold-start" version, which does not train with SGD at all not reported? What about regularized approaches, or ones in which the samples are not fixed? These numbers would really help to contextualize the preformance of the new system.  Overall, it seems that the authors have managed to "make the system work", but have not invested very much time in verifying that it works better than simple alternatives. 

I appreciate that the authors added additional experiments in the appendix, but they are not flattering.  The HMC for the real world data works best for the smallest L (which seems antithetical to the main story showing that $L=\infty$ is appropriate), and in one case (=1/4), the new methods are significantly worse than the original DNN performance. In addition, the newly proposed methods are 2-3 orders of magnitude slower than the baseline. 

-----
minor line-by-line comments:
-  I disagree that VAEs are a "link between graphical models and deep neural networks" (line 17). The "graphical models" part of VAEs is relatively tenuous; it's really just a way to emphasize a data generating process by which samples are drawn from a prior and then decoded.  To make the connection to PGMs you'll probably need a much more expressive variant, such as a PDG (https://arxiv.org/abs/2202.11862).
- The notation in lines 74-75 is a bit slopy; is $v_i$ a variable, or a setting of a variable? If the former, then the equation $p(\vec v) = $... doesn't typecheck; if the latter, then it shouldn't be the argument to $pa(v_i)$. I suggest just using $pa_i$ for a quick and dirty solution.
- I found the natural language description of steps b and c (lines 132-141) confusing, imprecise, and unnecessarily verbose. I do not feel I could implement it based on the description given, although Figure 1 helps. Pseudocode, or adding mathematical symbols to refer to nodes and edges, could make things far less ambiguous. 
- Similarly, the discussion in lines 146-164 is also difficult to follow, and feels imprecise. I would like to see a more formal mathematical description of this.  
- The usage of "mean-field approximation" on lines 148-149 is non-standard and seems like a  false connection to me. 
- I disagree that this doubly exponentially large tree-structured graphical model is "easier to understand" than the original forward pass of the network (lines 181-184).  I also do not see why the training procedure of SGD is relevant to the discussion; how have you broken the symmetry between SGD and any other local optimization procedure? SGD certainly does not appear in Theorem 1.
- the notation $\sigma$ was not defined. Based on the appendix and standard symbols I gather it's the standard sigmoid curve, but this usage of $\sigma$ should be mentioned in the formal statement of the theorem or in the preliminaries.
questions: questions: What happens if you don't do many epochs on the same fixed dataset, but rather draw fresh samples from the ground truth distribution that you're looking for?  It seems that the main benefit shown in the experiments is that it can mitigate overfitting.  But at a high level, it's unsurprising that a strong structural "prior" about the data, which happens to be correct in the synthetic setting, can help overfit to this setting. What happens if the number of datapoints grows far larger, but we reduce the number of epochs?

Why is Hamiltonian Monte Carlo a particularly natural fit for this setting?


LOW-LEVEL QUESTIONS AND COMMENTS:

(Lines 96-99): Is the interpretation of a DNN with sigmoid activations really a coherent interpretation?  Yes, it defines a distribution over a binary variable given values of its parents---but in order for that cpd to typecheck, the parents need to take on real values, not binary ones. It would seem that this makes the interpetation inconsistent for networks deeper than one layer. ~~Am I missing something?~~
Edit: this is a confusing presentation, and the confusion deepens in lines 112-114. But the resolution in lines 116-119 is clear, and that should have been present from the beginning.  There's no reason to give a high-level overview of an interpretation that is confusing (because it is technically wrong) before pointing out that it is technically wrong.  The authors define this to be "the direct PGM" far later in the paper (line 190), 

In line 121, the autors say that this "approximation of $\cal D'$ to $\cal D$ is precise", but is it? What is the distribution $\cal D'$? Over what variables? Are they continuous or binary? It still seems inconsistent to me. I would like to see this spelled out precisely. If it is meant as only a rough analogy, then you must say so when you introduce it. 

Clarification about the "second step" of the construction: it seems to me it must be done backwards, so the second-to-last layer (after the "first step") has $L$ copies, the one before that has $L^2$ copies, and the first one has $L^n$ copies.  Is this correct?  Or are there overall $L$ copies of each layer of the "post-first-step" transformation?

Why is the variance $p_{ij} (1-p_{ij})/L$ in equation 1?  Is this shown in the appendix, or do you have a reference?

Is there some relation between the $M^{-1}$ covariance and the weight $\mathbf W$? Where do you get the esimtate of $M^{-1}$? 

Shouldn't $\boldsymbol \mu$ factor into the update in equation (7) somewhere?

How are the procedures "Weight-updating" and "Sampling" in Algorithm 1 defined? Does this have to do with equation 7? I feel some details are missing. 

The results in lines 334-337 are compelling, but it seems the opposite is true of the MN rows of the table.  Why is this?
limitations: limitations: The authors do discuss limitations a reasonable extent.
paper_summary: paper_summary: This work bridges the gap between Deep Neural Networks (DNNs) and Probabilistic Graphical Models (PGMs). The authors do so by viewing DNNs as defining a joint distribution over the values of their nodes and showing that forward pass on a DNN is equivalent to exact probabilistic inference on a corresponding infinite tree-structured PGM. 
The authors describe an algorithm to construct a tree-structured PGM corresponding to a given DNN by unrolling it into a tree and making L copies of each non-output node (corresponding to an L-sample approximation of the expected value at the node). As L tends to infinity, the constructed PGM becomes equivalent to the DNN.  

A key implication of this result is that PGM algorithms can now be used to train DNNs. Specifically, the authors observe that the Stochastic Gradient Descent (SGD) approach to training DNNs differs from the contrastive divergence (CD) algorithm since SGD ignores the values of the output variables when computing the expected values of the latent variables. Using this observation, the authors propose a CD-based learning algorithm for DNNs that uses Hamiltonian Monte Carlo (HMC) sampling to approximate the expectations instead of Gibbs sampling which would be computationally inefficient given the large number of variables in the DNN.

The authors evaluate the proposed HMC-based learning algorithm using synthetic data sets and the Covertype data set from the UCI Machine Learning repository. They compare their approach against SGD and Gibbs sampling-based learning. They measure the calibration of the models learned on the synthetic data sets using Mean Absolute Error (MAE) from the true distribution and they measure the calibration for the Covertype data set using Expected Calibration Error (ECE). The evaluation shows that the proposed HMC-based algorithm (1) is equivalent to SGD for large values of L and (2) yields highly calibrated models for small values of L (such as 10)
strength_weakness: strength_weakness: While the paper makes important contributions, the presentation makes it hard to read in some places
1) Lines 127-143 would be clearer if presented in an algorithm environment with appropriate notation.
2) LineD- 245 says "our previous C1 algorithm" but CD-k and CD-1 are explained in lines 264-266
3) The description of a BN in lines 270-281 seems out of place and should probably be in Section 5.1
4) The Experimental Results section should be reorganized for readability by explicitly discussing research questions, metrics, baselines, and data sets before presenting results and answering research questions. 

While the authors contrast their work against Bayesian Neural Networks, they should also contrast it with Probabilistic Circuits such as sum-product networks which are computational graphs that define a joint distribution over a set of input variables.
questions: questions: Can you elaborate on the working of the Gibbs sampling baseline in the experimental evaluation? Does it also depend on L?
Also, how many samples were used for each of the experiments?
limitations: limitations: The authors clearly state the limitations of the work such as applicability to non-sigmoid DNNs and describe ways in which future work could address them.
paper_summary: paper_summary: The paper proposes a novel connection between DNNs and PGMs. Specifically, the idea s to unroll the DNN computation graph in the form of a PGM. The main formal result that is shown is that DNN forward propagation corresponds to exact inference in the encoded PGM. More practically, since the PGM is infinite, it should not be expected to replace DNN-based operations, but rather to understand the working of a DNN from a PGM perspective. Further, a new HMC algorithm is developed using this view and the resulting approach can be used model calibration. Experiments are performed on synthetic data from a known distribution to measure the calibration error. Another set of experiments are performed with Covertype datasets
strength_weakness: strength_weakness: - The main weakness is perhaps in that the practical utility of going from the DNN function space to the PGM space is yet unknown. The experiments on calibration seem to show some promise but maybe stronger real-world studies could have demonstrated the need for the connection.
questions: questions: If inference in a PGM corresponds to DNN propagation, then what is the likely source of miscalibration in the DNN models, I was wondering there is some way of knowing this using the proposed connection.
limitations: limitations: Limitations are identified and adequately discussed.
paper_summary: paper_summary: The paper "On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models" introduces a framework that constructs infinite tree-structured probabilistic graphical models (PGMs) corresponding to deep neural networks (DNNs), demonstrating that DNNs perform precise approximations of PGM inference during forward propagation.
While this claim, along with others in the paper, sounds plausible, it also seems well-known within the field. The transition from Fig. 1a (Neural Network represented graphically) to the tree-like graphical model shown in Fig. 1b appears to simply construct what is called a computational tree in the graphical model literature. For reference, see several earlier papers discussing the topic:
•	Sekhar C. Tatikonda and Michael I. Jordan. "Loopy belief propagation and Gibbs measures." Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, UAI’02, page 493–500, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc.
•	Alexander T. Ihler, John W. Fisher III, and Alan S. Willsky. "Loopy belief propagation: Convergence and effects of message errors." Journal of Machine Learning Research, 6(31):905–936, 2005.
•	Dror Weitz. "Counting independent sets up to the tree threshold." Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’06, page 140–149, New York, NY, USA, 2006. Association for Computing Machinery.
The last paper suggests an exact map of a finite loopy graphical model of the Markov Random field type into a large but finite loopless graphical model (tree). The infinite graphical model (computational tree) is linked to approximate inference (with belief propagation) in the original graphical model.
Computational tree-based approaches have previously been associated with both variational and MCMC techniques, though they were not developed into practical algorithms.
I find the Hamiltonian Monte Carlo algorithm developed in the paper, along with the reported experiments, quite interesting. However, I believe that more experiments and exploration are needed, as well as improved references to prior work in graphical models, before the paper is ready for publication.
strength_weakness: strength_weakness: see summary
questions: questions: see summary
limitations: limitations: see summary

Comments: comment: (1) 'SGD':

You are right our result applies to gradient descent.  We will clarify this.  The stochastic part of SGD comes entirely from which subset of examples (mini-batch) we use to compute this gradient at any step, so it applies to SGD as well.  We will clarify that the point is about gradient descent generally, not SGD in particular.

Yes, MN learning is also by gradient descent.  And yes, our result only applies to cross entropy error, since cross entropy is a function of $P(y|X)$ for any setting of the inputs $X$.  Our result is that these probabilities $P(y|X)$ agree between NN and MN for any node y anywhere in the NN, not just output nodes.  We will make sure this limitation to cross entropy error is extremely clear; thank you for bringing to our attention the need for more clarity and emphasis on that point.

(2) 'coherent joint distribution $\mathcal D'$':

Thank you for bringing attention to this detail. You are correct that despite it being possible for the neural network's standard operation to be viewed as an 'approximate' marginal $p(y|X)$ for the output or $p(h|X)$ for a hidden node, that view (and less exact connections with probabilistic graphical models) does not immediately lend itself to a distribution over multiple nodes (or the full joint distribution), $p(y, h_1, h_2, h_3 |X)$ for example. In the traditional neural network structure, those hidden neurons are not well-defined unobserved nodes of a PGM and we therefore require the infinite PGM view. The infinite width tree structured PGM view should then be able to connect the neural network's forward pass and these 'approximate' values with an exact probabilistic structure where queries on multiple nodes, jointly, is possible. We will make sure to clarify that point in the final version of the paper. 

(3) '"weight updating" and "sampling" in your algorithm pseudocode':

Thank you for catching that detail. We will make sure to clarify the weight updating and sampling steps of Algorithm 1 in the final version of the paper.
Thank you for the response. I understand the work more clearly now. After going through other reviews and the discussion, I have updated my rating to Accept
Thank you for answering my questions, and running additional experiment. This rebuttal has allayed some of my concerns, and I now am more on board with the empirical evaluation.

Still, I'm not fully convinced.  A few responses:

 - SGD: I was trying to point out that SGD is an optimization procedure. The "stochastic" part is just to speed things up computationally; the theory seems to me only to interact with the "gradient descent" part--- and even then, I believe you are referring to gradient descent with respect to a specific loss function (cross entropy, presumably).  I'm not sure what it means to say *"the MN interpretation gives the same gradient that SGD uses."*  Why does the MN have a gradient, and with respect to what? I'm lost. 

 - line 121:  you still have not given a coherent joint distribution $\mathcal D'$. Just because the DNN gives "approximate" answers to certain queries in some sense does not mean there is a joint distribution $\mathcal D'$ that coincides with those answers. 

- If you are going to have "weight updating" and "sampling" in your algorithm pseudocode, you should make sure to define those terms eslewhere.  Alternatively, write "update weights according to (7)" or something like this, so that a reader who is less intimate with the material can follow the references.
Thanks for your response. I think the connection between PGMs and DNNs can be beneficial in several ways. I think this area is worth exploring and revisiting (including connections to some of the older works that other reviewers have mentioned). I am in general positive about this work.
Thank you for the clarification. We agree that the work that has been done using computation trees warrants mentioning in reference to the proposed construction and we will include a corresponding discussion in the final version of the paper.

(1) The structure of the candidate tree and factors are fixed, which certainly aligns with how copies of nodes are added in the computation tree, even if the ordering of those nodes differs. 

(2) The truncated tree presented in Dror Weitz's work certainly appears most similar to the first step of our PGM construction due to its finite nature and perhaps an easier way to present that first step would be to describe it as consisting of several paths (walks) that follow the direction of the arrows in the initial neural network DAG that are copied in such a way that they do not overlap (and where copies of a node never appear as ancestors to the same node). That said, we would be cautious to very closely align the two as the first step of our construction follows this directed/layer-by-layer ordering while the graph presented in Weitz's paper is undirected. 

We thank the reviewer again for bringing our attention to this interesting connection.
In response to the authors' rebuttal, I want to clarify that I am not suggesting their work is a trivial extension of the computational tree framework. However, the computational tree serves as a significant reference point that should be discussed in the final version, should the paper be accepted.

To further clarify my comments:

1) My observations regarding the relationship to the computational tree specifically pertain to the forward propagation aspect of the algorithm, where, as I understand it, the structure of the candidate tree and factors is fixed.

2) The approach introduced by Dror Weitz (as mentioned in my original review) constructs not an infinite but a specifically truncated portion of the computational tree. This construction provides exact, rather than approximate, inference for the known Graphical Model, particularly in the forward part of the algorithm discussed by the authors.
Thanks again to all reviewers for your constructive comments. We believe the additional empirical results (see attached pdf) serve to strengthen our claims, and that other changes we've outlined will substantially improve the presentation of this work. If any reviewers have follow-up questions or comments, please let us know.