On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models
Authors: Boyao Li
Alexander Joseph Thomson
Houssam Nassif
Matthew M. Engelhard
David Page
Venue: NeurIPS 2024 poster (2024)
Keywords: probabilistic graphical model; neural network; hamiltonian monte carlo; calibration
Primary area: probabilistic_methods

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.

On Neural Networks as Infinite Tree-Structured Probabilistic Graphical Models
Boyao Li"
Alexander J. Thomson"
Department of Biostatistics and Bioinformatics Duke University boyao. li@duke. edu
Department of Computer Science
Duke University
alexander thomsondduke. edu
Houssam Nassif
Matthew M. Engelhard
Meta Inc.
Department of Biostatistics and Bioinformatics
houssaam@metta.cmm com
Duke University
m. engelharddduke....o edu
David Page
Department of Biostatistics and Bioinformatics
Duke University
david. pagedukee edu
Abstract
Deep neural networks (DNNs) lack the precise semantics and definitive proba- bilistic interpretation of probabilistic graphical models (PGMs). In this paper, we propose 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 precise in this alternative PGM structure. Not only does our research complement existing studies that describe neural networks kernel machines infinite-sized Gaussian processes, it also elucidates a more direct approximation that DNNs make exact inference in PGMs. Potential benefits include improved pedagogy and interpretation of DNNs, and algorithms that can merge the strengths of PGMs and DNNs.
1 Introduction
Deep neural networks (DNNs), including large language models, offer state-of-the-arr 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 2021] To gain 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-AAlnso et al. 2018). When such a connection possible, potential benefits include:
Boyao and Alexander Thomson contributed equally this work. Matthew M. Engelhard and David Page jointly supervised this work.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Clear statistical semantics for a trained DNN model, beyond merely providing the conditional distribution over output variables given input variables. Instead, PGMs provide 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 reverse any DNN use output variables as evidence and variables anywhere earlier as query variables.
Improved calibration, i.c., improved predictions of probabilities 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 affnite-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 prior result of Nair and Hinton [010]] 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 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 Bayesian network over binary variables-it is directed acyelic 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 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 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 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 (HM) Amari 1995 or approximate EM [Song et al., 2016).
motivation is similar to that of Dutordoir et al. (22 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 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 make the DNN-PGM approximation explicit and include all sigmoid DNNs, not just unsupervised belief networks or other specific cases.
Although the approach is different,
All code needed to reproduce our experimental results may be found at https: htt/t//ttttttttt com/ engelhard 1ab/DNN_ TreePGM

---

2 Background: Comparison to Bayesian Networks and Markov Networks
Syntactically Bayesian network (BN) is directed acyclic graph, like 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 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) = II, P(V))po(V))) where pa(V.) denotes the parents of variable Vi. If the conditional probability distributions (CPDs) P(V[ppa(V)) are all logistic regression models, we refer to the network as sigmoid BN.
It is well known that given sigmoid activation and 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 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 represented by the joint sample over them in our training set.
Bayesian
Markov network (MN) syntactically is an undirected graph with potentials d, 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 the variables as P(V) 1 II, (V) where the partition function Z is defined as Σy II, @; It is common to use a loglinear form of the same MN, which can be obtained by treating setting of the variables in clique binary feature St. and the natural log of the corresponding entry for that setting in the potential for that clique weight we on that feature; the equivalent definition of the full joint is then P(V) Je wis((V) For training and prediction at this point the original graph itself is superfluous.
The potentials of an MN may be 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 "pairwise" MN. An MN whose variables are all binary 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 a Bayesian network. Instead, for the remainder of this paper, we adopt the view that the DNN's forward pass might serve 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 Markov network where every edge of weight w from variable A to variable has a potential of the following form:
B
B
A
A
1
For 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 exactly correct.
3

---

3 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 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 NPccompee Therefore, if we take the distribution DD 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 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 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 remove edges from a PGM to obtain a simpler PGM in which inference is more efficient. Treewidth- (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.
may
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 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 '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 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 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 the probabilistic graphical model view of the approximation made by the DNN's forward pass, the neural network effectively takes 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 I. 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

---

H1
w7
WS
4 w1
w5
H3
666
W7
w10
4
H2
H4
w10
W2
4
H4
3.
(a) The neural network's graphical structure before applying the first step of this PGM construction.
(b) The neural network's graphical structure after applying the first step of this PGM construction.
The first step of the PGM construction where shared latent parents separated into copies along with the subtree of their ancestors. Copies of nodes H1 and H2 are made in this example.
Figure 1:
copied edges is then set to its original value divided by L. Note that this step results in number of total copies that grows exponentially the number of layers (i.e. L copies in the 2nd to last layer, L 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 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 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, show the following:
Theorem 3.1 (Matching Probabilities). the PGM construction, as L - oc, P(H 1|7)
N (po():)) for an arbitrary latent node H in the DNN that has observed parents (E Wygj + E
91..... 9M and latent parents hi, by that are true with probabilities a (pp1),.., (pNN), Here, a--) the logistic sigmoid function and Wi...., WM and o1...., N are the weights edges between these nodes and H.
The PGM of our construction is Markov network that always has evidence at the nodes X cor- responding to the input nodes of the neural network. As such, is more specifically a conditional random field (CRF). Theorem 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 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 the edges and 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 vector with one entry for each feature f corresponding to each weight of the neural network, of the form P( P(J F). Building on Theorem 1, this gradient 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 coos-entroppy loss with respect
5

---

to the weight w on an edge, or feature f of the CRF, is P( Y). This result is more precisely stated below in Theorem 2 below, which is proven Appendix D
Theorem 3.2 (Matching Gradients). In the PGM construction, L + oc, the derivative of the marginal log- oog-likelhhood, 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.
4 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 semanties to an entire neural network, as a joint probability distribution over all its variables, not merely as machine computing the probability of its output variables given the input variables. Any Markov network, including any CRF, precisely defines joint probability distribution over all its variables, hidden or observed, in a standard, well-known fashion. The particular CRF we constructed 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 template in 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 '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 Gibbs sampler takes infinitely many samples of V given infinitely many samples of each of the members of V's 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 appreach 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 result in the previous section can be extended to ReLU activations by the same argument. More generally, with any non- 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 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 given minibatch, to sum to 1.0; the argument can be extended to 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 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 the sigmoid case.

---

5 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 tree-structured PGM, such that the CPD of each hidden variable is logistic regression. In other words, each hidden node 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-Perpinn
and Hinton 2005 [Bngiio 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 hidden variable values using only evidence in 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 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, rather than {0, 1]. Neal [2012) first applied HMC to neural nets to sample the weights in a Bayesian approach, but still used Gibbs sampling on the hidden variables. Our theoretical results for the first time justify the use of HMC over the hidden variables rather than Gibbs sampling in DNN, as follows.
Recall that the DNN is itself 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-structuree 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 sampled independently, the sample average follows normal distribution the asymptotic distribution when L + oo by the central limit theorem. In practice, L is finite and this normal distribution is reasonable approximation to the distribution of the hidden node. Thus in the BN, whose variables correspond exactly to those of the DNN, the variables have domain [0,1] rather than (0, 1}, as desired. We next precisely define this BN and the resulting HMC algorithm.
5.1 Learning via Contrastive Divergence with Hamiltonian Monte Carlo Sampling
Consider a Bayesian network composed of input variables x = hg, a sequence of layers of hidden variables hi. hk. and output variables y. Each pair of consecutive layers forms bipartite subgraph of the network as a whole, and the variables h; = (ha1.... haM.) ) follow a multivariate normal distribution with parameters p. (P...... P.M.) that depend variables in the previous layer h;-1 as follows:
hig N N (1 - pt;)/ L), where p. = a oW, 1 b;-1);
where o: : R + (0, 1) is a non-linearity - here the logistic function - that is applied element-wise, and 0. (W,, b;) are parameters be learned. The distribution in equation (I) is motivated by supposing that his is the average of L copies of the corresponding node in the PGM, each of which is I with probability Pij and zero otherwise, then applying the normal approximation to the binomial distribution. Importantly, this approximation is valid only for large L.
For complete setting of the variables {x, h, y). where h {hr, .... hx), and parameters 0 (0, o the likelihood p(y, h |x 0) may be decomposed as:
K M. phr lp. (h;-;;1 0,-1)),
ply. h l 0) = p(y 0x)
-IIIII =11==1
where (-l(-)) denotes the normal density, and a specific form for p(y] 0x) has been omitted to allow variability in the output variables. our experiments, y is a Bernoull(bbnarry) or categorical random variable parameterized via the logistic(sigmoid) or softmax function, respectively.
7

---

Let h ,, h :... denote a chain of MCMC samples of the complete setting of hidden variables in the neural network. As previously noted, we allow hidden variables hig E (0, 1) for E {l.... K} and j E (1,.... M. and use Hamiltonian Monte Carlo (HMC) to generate the next state due to its fast convergence. Since HMC samples are unbounded, we sample the logis associated with hag E (0. 1), i.c. o- (ba) (-00, oz), rather than sampling the hij directly.
The HMC trajectories are defined by Hamilton's 's Equations:
dp: 0H
dp4
OH
dt
0p:
dt Op:
where Pt. M4 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 is
H =(p
_u' M
where -1 is a positive definite convariance matrix and acts as metric to rotate and scale the target distribution, which usually set to identity matrix in practice. Defining the position p = h, the complete set of hidden variables of the network, we have that the potential energy U is the negative log-likelihnn lileliiiihood associated with equation (
K M.
(hh = - log ply. 11/z: 0) = log log kk; 0k)
log Px Par(hulll
(1y(1 (h4-1:0,-1)) (5)
1=1
We the leap frog size 0, step size A 0. A description of the HMC trajectories (i.e., evolution of h) is provided in Appendix E
The initial state of the chain (0) drawn with a simple forward pass through the network, ignoring (0) ;- h
the output variables; in other words, we have h ~ ~N(aa
+ bb for E {},
where hu = are the input variables, and the values of w! and b,0h are manually set or drawn from 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 steps, corresponding CD-k, we define the loss based on equation
(((())) llo ply, h//;; e())).
(6)
We then apply the following gradients to update the parameters
(w((n)
) and (b. (b("))
=i=0
ac
dL
W (n+1)
w(n))
b
(n+1) blTh 0b!") m)
@w(")
where 77 is the learning rate. Algorithm 3
(see Appendix F) summarizes this procedure.
5.2 Experimental Results
The previous section discussed the modeling of the HMC learning algorithm inspired by the construc- tion 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
Covertype dataset [Blackard [998), 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.
5.2.1 Synthetic experiments
The synthetic datasets are generated by simple BNs and MNs with their weights different ranges, which are used to define the conditional probabilistic distributions for BNs and potentials for MNs. Each dataset contains 1000 data points ((X,, 3/ );)), i = 1,2, ..., 1000, where each input X; E {0. 1)"
is binary vector with dimension and each output y E {0, 1} is binary value. The true

---

probabilistic distribution 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 I.s for 20 epochs based on the trained DNN model. Here L defines the normal distribution for hidden nodes in Eqn. I and is explored across the set of values: {10, 100, 10003. 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 D and ane-tuning with Gibbs or HMC. Since the ground truth of P(y) XX) 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.
Table shows that in general, DNN results tend to get worse with additional training, particularly with smaller weights, and the HMC-based fine-tuning approaches can mitigate this negative impact of additional training on the model calibration. Across all the HMC with different L/s, HMC (I:=10) performs better than the others and DNN training itself for BNs and MNs with smaller weights. Additionally, the MAE of HMC (L=10) tends to be similar to Gibbs but runs much faster, especially in the BN simulations, whereas HMC (L=1000) is more similar to the NN. This is consistent with what we have argued in the theory that when L goes smaller, the number of the sampled copies for each hidden node decreases in our tree-PGM construction and HMC sampling performs more similar to Gibbs sampling: and as L increases, the probability of each hidden node given the input approaches the result of the DNN forward propagation and thus HMC performs more similar to DNN training.
Table I: Calibration performance on synthetic datasets. Experiments are run on each dataset 100 times to avoid randomness. T-tests are used to test whether Gibbs and HMC have smaller MAE than SGD, and highlighted cells mean that it is statistically significant to support the hypothesis.
Average Mean Absolute Errr (x10-9) (p-value)
Duta (Weight)
Train Epochs
DNN
Gibbs
HMC-10
HMC-100
HMC-1000
BN (0.3)
100
6.593
16.09 (1.0000)
5,300 (c0.0001)
6.864 (0.9982)
6.658 (1.0000)
1000
34.44
36.69 (0.9916)
23.53 (c0.0001)
34.96 (1 (1.0000)
34.55 (1.0000)
100
22.90
20.84 (0.0011)
22.48 (<0.0001)
24.17 (1.0000)
22.95 (0.9928)
BN (1)
1000
42.59
33.64 (<0.0001)
33.07 (<0,0001)
43.03 (1.0000)
42.63 (0.9995)
100
72.76
76.12 (1.0000)
76.54 (1.0000)
72.62 (<0.0001)
72.63 (<0.0001)
BN (3)
1000
28.28
32.59 (1.0000)
32.98 (1.0000)
28.8t (L.0000)
28.40 (1-0000)
100
186.0
192.8 (1.0000)
196.1 (1.0000)
184.6 (<0.0001)
184.8 (40.0001)
BN (10)
1000
54.89
79.69 (1.0000)
72.64 (1.0000)
54.81 (0. (266)
54.63 (40.0001)
100
6.031
14.03 (1.0000)
4,515 (<0.0001)
6.382 (1 0000)
6,070 (1.0000)
MN (0.3)
1000
38.11
34,83 (<0,0001)
26.54 (<0.0001)
38.71 (1 (1.0000)
38.22 (1,0000)
MN (1)
100
9.671
17,81 (1.0000)
8,887 (<0.0001)
9.018 (<0,0001)
9,284 (<U. (c0.0U01)
1000
27.80
32.44 (1,0000)
19.92 (<0.0001)
27.98 (0.9994)
27.73 (<0.0001)
100
8.677
23.60 (1.0000)
5.685 (<0.0001)
5,912 (<0.0001)
5,964 (<0.0001)
MN (3)
1000
5.413
28.03 (1.0000)
5.792 (0.9957)
5.671 (1.0000)
5.443 (1.0000)
5.2.2
Covertype Experiments
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(yl X) cannot be found, the metric for the calibration used in this experiment is the expected calibration error (ECE), which is 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 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.
9

---

Table 2: Calibration performance on Covertype datasets. Highlighted cells show the best calibrations among each row.
Test Expected Calibration Error (x10-2)
Data
# Train Epochs
DNN
Gibbs
HMC-10
HMC-100
HMC-1000
100
4.207
4.229
2.352
3.893
3.987
Covertype (label 1)
1000
10.85
8.513
6,875
7.730
11.60
100
4.268
7.796
7.719
4.913
4.354
Covertype (label 2)
1000
6.634
14.67
5.233
5.394
7.713
6 Conclusion, Limitations, and Future Work
In this work, we have established new connection between DNNs and PGMs by constructing an infinite-width tree-structured PGM corresponding to any given DNN architecture, then showing that inference in this PGM corresponds exactly to forward propagation in the DNN given sigmoid activation functions. This theoretical result is valuable in its own right, as it provides new perspective that may help us understand and explain relationships between PGMs and DNNs. Moreover, we anticipate will inspire new algorithms that merge strengths of PGMs and DNNs. We have explored one such algorithm, a novel HMC-based algorithm for DNN training or fine tuning motivated by our PGM construction, and we illustrated how it can be used improve to improve DNN calibration.
I Limitations of the present work and directions for future work include establishing formal results about how closely batch- and nover-normalizatonn can be modified to approximate Markov network normalization when using non-sigmoid activations, establishing theoretical results relating HMC in the neural network to Gibbs sampling in the large treewidth-1 Markov network, and obtaining empirical results for HMC with non-sigmoid activations. Also great interest is comparing HMC and other PGM algorithms to Shapley values, Integrated Gradients, and other approaches for assessing the relationship of some latent variables to each other or to inputs and/or outputs in a neural network. We note that the large treewidth-1 PGM is a substantial approximation to the direct PGM of 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 other approximate al 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, 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 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 tuning and usage could not be done with 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 reverse 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 other message passing methods) are left for future work.
10

---

Acknowledgements
The authors would like to thank Sayan Mukherjee, Samuel I. Berchuck, Youngsoo Back, David B. Dunson, Andrew S. Allen, William H. Majoros, Jude W. Shavlik, Sriraam Natarajan, David E. Carlson, Kouros Owzar, and Juan Restrepo for their helpful discussion about the theoretical work. We are also grateful to Mengyue Han and Jinyi Zhou for their technical support.
This project is in part supported by Impact of Genomic Variation on Function (IGVF) Consortium of the National Institutes of Health via grant U01HG011967.
References
Vanessa Buhrmester, David Münch, and Michael Arens. Analysis of explainers black box deep neural networks for computer vision: A survey, Machine Learning and Knowledge Extraction, (4):966-989, 2021.
Diederik P. Kingma and Max Welling. Auto-Encoding Variational Bayes. In 2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Oliver E Richardson. Loss as the inconsistency of prwbabillisiiccceeee.o.oeoee depeedency graph: Choose your 22tp//2222..11222222
model, not your loss function, 2022.
Yo Joong Choe, Jaehyeok Shin, and Neil Spencer. Probabilistic interpretations of recurrent neural networks. Probabilistic Graphical Models, 2017.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional networks as shallow gaussian processes. arXiv preprint arXiv: 180.005877 2018.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Proceedings of the 27th international conference on machine learning (ICML-10), pages 807-814, 2010.
Shun-ichi Amari. Information geometry of the em and algorithms for neural networks. Neural 1995.
networks,
Zhao Song, Ricardo Henao, David Carlson, and Lawrence Carin. Learning sigmoid belief networks via monte carlo expectation maximization. In Artificial Intelligence and Statistics, pages 1347- 1355. PMLR, 2016.
Vincent Dutordoir, James Hensman, Mark van der Wilk, Carl Henrik Ek, Zoubin Ghahramani, and Nicolas Durrande. Deep neural networks as point estimates for deep gaussian processes. Advances in Neural Information Processing Systems, 34, 2021.
Shengyang Sun, Jiaxin Shi, and Roger Baker Grosse. Neural networks as inter-domain inducing points. In Third Symposium on Advances in Approximate Bayesian Inference, 2020.
Andreas Damianou and Neil D Lawrence. Deep gaussian processes. In Artificial intelligence and statistics, pages 207-215. PMLR, 2013.
Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach Apprach (4th Edition). Pearson, 2020. ISBN 978013461099 URL httpt:tttt//aaaata cs. berkeley..ee.....
Sekhar C. Tatikonda and Michael Jordan. Loopy belief propagation and gibbs measures. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence, UAI'02, page 493-500, San Francisco, CA, USA, 2002. Morgan Kaufmann Publishers Inc. ISBN 1558608974.
Alexander T. Ihler, John W. Fisher III, and Alan S. Willsky. Loopy belief propagation: Convergence and effects message errors. Journal of Machine Learning Research, 6(31):905-99) 2005. URI. org/ arg/papers/v6. http:///v//hhll...ee ihwereha.a.... html html

---

Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the Thihty-Eighth Annual ACM Symposium on Theory of Computing. STOC '06. page 140-149, New York, NY, USA. 2006. Association for Computing Machinery. ISBN 1595931341. doi: URL http::ttps//.oorrreeeeee 10. 1145/11335511 1132538
Miguel A Carreira- Perppna and Geoffrey E Hinton. On contrastive divergence learning. In Aistats,
volume 10, pages 33 40. Citeseer, 2005.
Yoshua Bengio and Olivier Delalleau. Justifying and generalizing contrastive divergence. Neural computation, (116):601-16211 2009.
Ilya Sutskever and Tijmen Tieleman. On the convergence properties of contrastive divergence. In Yee Whye Teh and Mike Titterington, editors, Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, volume 9, pages 789-795 JMLR Workshop and Conference Proceedings, 2010. /ttpp:ppppprrooeaannss mlr. www.pressssve sutskever10a
html
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
Jock Blackard. Covertype.
UCI
Machine Learning Repository, 1998.
DOI:
IGVF Consortium. Deciphering the impact of genomic variation on function. Nature, 633(8028):
47-57,2022 2024.
Charles Sutton and Andrew McCallum. An introduction to conditional random fields. Found. Trends Mach. Learn., 4(4):267-373, April 2012. ISSN 1935-8237. doi: 10.1561/2200000013. URL
12

---

A Bayesian Belief Net and Markov Net Equivalence
We don't I claim the following theorem is new, but we provide proof because it captures several components of common knowledge which we couldn't 't find single reference.
Theorem A.I. Let be a Bayesian belief network whose underlying undirected graph has treewidth I, and let WAB denole the coefficient of variable A in the logistic CPD for its child B. Let M be binary pairwise Markov random field with the same nodes and edges (now undirected) as N. Let M' 's potentials all have the value e A if the nodes A and B on either side of edge AB are true, and the value 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 is
Z (V)
where 6; are the potentials in M, and Z is the partition function, defined as
Z = ==EIILØ;(V))
We use (Ø) to designate the variables in potential ø. Because the nodes and structures of M and N agree, we will refer to the parents, children, ancestors, and descendants of any node 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 M. As a result, 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 V0 be the empty set variables, and let Vi be the input variables of M. Let Ch(V) denote the children of any set V of variables in M, and similarly let Pa(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 2 0:
S(V)) INECHY) -N Do.
f(Vm+1) =
where Vn is not the full set of variable in M but Vm+1 is the full set. Then Z f(V1).
For each variable V. get single potential ((v,Pa())) over (v, Pa(r)). For given setting of the parents of in V. let @x(Pa(v) denote the result of conditioning on this setting of the parents, and let de, w/Pa(r) 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 particular setting V as
multiply the potentials the edges between and its parents, to
Pu)Pa(u)
P(V) = II DEV do, o|Pa(w)
These terms are exactly the terms of the logistic conditional probabilities of the Bayesian belief network N:
P(V) = II DEV P(uPPat)
Note that in general when converting Bayes net structure to 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 stre-structured, moralization not required.
13

---

end for B Step 1 and Step Construction Algorithms
In the following, calls to add to sets V or (or to check if either set contains a vertex or edge) immediately edits/checks the respective set object that they reference.
Algorithm Step of the PGM Construction
Require: A list H of the output vertices of the DNN's DAG G
Ensure: set vertices V and edges the DNN's original DAG transformed to tree structured graph, as
shown Figure
I: let V be an empty set of vertices
2: let E. he empty set of edges
3: V, É DNN TREECH. G. V. E.
procedure DNN TREE(H, G. child)
& unroll the DNN graph into tree(s) layerwise
5: for each verlex in H. do
6: new & verfex
7: while new in V do
create copy of this vertex
new + new + '/' character
end while
10:
V a.dd(nee))
11:
if child is labelled then
D ie child is not get child's original vertex l an edge between new and child an edge between parent copy and the child
12:
weight +- G.getEgge(vertez; child.removeAll(())
14:
E.add(e), EaddWWightte,, weight)
15:
end
16:
G, V, E, new)
create unrolled subtrees for each parent
18:
return V.E
19:
end procedure
Algorithm Step of the PGM Construction
Require: graph of the vertices and edges created in Step I, list H of the DNN's output vertices, an integer
Ensure: Vertices V and edges E of the final tree structure graph with copies of each parent node from Step
I: Jet V be an emply set of vertices
2: let E be empty of edges
for each vertex H
4: V',E" + DNN CoPY(verter, G, vertex, V, E. I)
5: V V.unio((V') +- (.union(EE)
6: end for
7: procedure DNN DNN_COPY (OPY(eurrent,, G. copy, V, F,,
V Viaddccopy)
9:
for each parent in G. ((urren) do
10:
weight G.getWeigh(purend, current) for i +- to do < parent + +
11:
12:
create the ith copy in the current subtree > create a unique label so the graph retains its trec-structure
13:
while n do
14:
n +
15:
end while
16:
let be edge between copy and E.ad((e), E.addWeight(e, weight/l) DNN MWNN_COPY(parent..oo V.....
connect this copied node the previous
18:
D create copies in the remaining subtrees
19:
end for end for
20:
21:
return V, F
22:
end procedure
C A Proof Using Variable Elimination
In order to prove that as T. 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
14

---

hi...., hy, and M observed parents 91...., 9MM. The edges between these parents and H then have weights 0, S N,, for the unobserved nodes, and weights Wj, S J M, for the observed whole has observed evidence Ë. For the rest of this problem we use a Markov
nodes. The network network view of the neural network. The relevant potential passed from the unobserved parent nodes of H, ((h+) (as the directed version of the graph) forward to H have the following form:
h4 @
-4
Since 9j are observed, their values are found in ž. Finally, the potentials between each of these nodes and the central node H are as follows:
h -/
9j
1
99
1
Suppose, then, using the second step our construction, we make L copies of all the nodes that were parents of H in the directed version of the tree, hi....,hi hi .... h....., .... hl and gi...., gi' Ihr...., g&e with weights O,/L,..., 0 L and wi/L,... WM respectively. The potentials between H. and these copied nodes is then:
H
H
h
01/L
9 y
11
11
where <i < N. < M, and < 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,
6(H, b.... 1 J ..., N Di
91 9M: gM (+)
= IIII
IIII
xL ((h
j=1k=1
N (L/LL)Hx ((h.)).
Summing out arbitrary, copied latent node, hg
15

---

Σ 6(H, 11
Ny 1x(1))
No h 2
N L
EM Wjgg XH
Σ
IIII
(0/L1 6(h))
Na. i=1
@ (0/(00/1)11
II k= (1,)))((
II
(0./L))x ((1))
II
II
(011))HK33((1) ((1))
k=1,...L (1,))((a
Eho,N
EN wa (c
e (Qa/L)H
II
x
i=l...N I=I.... (6.)))((.9))
Summing out all I, copies of ha:
DN XI x (ePo (0./T)) + 11) x
II
II N k= I.....
(0./L) ((h)))
Then summing out the copies each latent parent:
N EM Wy x
I
(e ee 10,/L)H 1)²
Normalizing this message locally, 6(H 1| becomes = (Hz) = and o(H 0).²) becomes 1. This then gives us:
@(H = 1[z)
EM mygj [T (0//xx +1)2 / DM 15 I (e e (0. +1)²
MM 2998 X II (0/2) 1)²
11, (emi + 1)
We then consider:
16

---

- wss
x xII; N
(e% +1
lim
1-000
I1: (e +1)
M
N
lim exp 1,000
Σ
W59s
L x log(e" + Σ
-=1
N
L x log c e 20011)) +1)
1=1
and the logarithm of this limit is,
N L log(e" +1)
lim
W,gs
Σ
10000
1=1
Σ L x log(e (ic111) + 1)
Σ
(og(e + 1)
log(e?i + +1)
Mgg
lim L
1/L
The limit in the previous expression clearly has the indeterminate form of 0. Let G = Σ/= wagj and consider the following change of variables, S L/L, and subsequent use of I'Hôspitallss 's rule.
Σ (1og(e") + +1 log(e"* + +1))
G+ lim S-40+
5
8 EN (log(c +) log(e? + 1))
05
-G+ lim
8-0+
03
S
e x 0,
G + lim
8-0+
1
e 0 0:
G + lim
8-00
8 +1
N G
8 +1 8,
Σ Uygs +
(p.)
Therefore,
MM wsss
N (ct + 1)2
lim
T.500
11 (cpt +1)-
U99J + Σ (p.))..)
exp
The collected potential at node H from summing out its ancestors (from the directed view) then has the form:
17

---

hi expl # + Σi o (p:))..)
This is exactly the form of messages that we assumed were originally passed 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 2 collects potential eDvee "os for z true and for false from our initial forward step. Here Wzz is the weight between nodes and Consider, then, the nodes whose parents 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 P(H)e Ø we must also consider the influence that the child of node H, call this C, has 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 all in the case of output nodes. Suppose the weight between this child C' and node H is y. 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
Finally, note that with the L copies made in this graph, the potential between node H and C has the form:
H e3/2
H
C -C
1
Using the potential collected H from the forward pass and this addition information from C, we can then calculate the probability of node H given the input evidence at:
T(
1 e Ef dp)0)xH
Σ eeILCCHHb(C)
7
1
e
EM + d(J8))H x (c67/LXH +1)
Z
From this we have that:
P(H 1/7)
EE mgg + EN a(x))0)xx (ce7/LXXX) +1)
EE Nggs (p.) (CET/LXCXI + 1) + e0 (ce 1)
E wgg a(p X (007/LXOXI +1)
Ex W op. (LE7/LXXX1 + 1) (c+1)
Iy #3g EN o(p)),
(0. 18. (c 1)/(0e/ G W.B+
Note that lim (c 1) /ce7 1) i.e. as L grows increasingly large the informa- tion passed through this child node becomes negligible. We therefore have that P(H = 1 = o "E Wygj + Er (p.)0:), 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 mes- sages from their parents and child, we have that the conditional probability this PGM construction and the activation values of the DNN match for any node in any layer of the DNN/PGM.
18

---

D A Proof of the Gradient
From An Introduction to Conditional Random Fields Sutton and McCallum 2012 have the gradient of weight upk for this form of CRF can be written as:
01
Σ P(hd,,
Los Tey
ΣEN P(K vd fu te, h().
pwik
V.ECP
V,EC, RL.V'
Since the features on the cliques of the proposed infinite width-PGM structure are non-zero (1/ L, which is minor change from instead dividing each weight by I.) only when the adjacent nodes are both (true), this expression simplifies. The update on 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)(((ha = 1, h,+t1 = 1|,, v) P(hn = 1, hn+1 = 1|x)1,
where h, and 1n+1 are the nodes that the edge connects.
Consider single branch in the infinite width PGM structure. Let h. be the node closer the output node and let it be exactly n nodes separated from said output (node hn+1 is then naturally the next node in this branch). Due to the infinite-width structure of the proposed PGM there are L 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 summing out node hg.
P(hn 1, 1/r,,) P(hn 1, 1/x:)
= P(h,, = 1,,n+1 = 1 Σ P(hn 1, = 1,
-Phh, = 1, 1, = 1 1|,, v) Σ P(h, 1,,1441 = 1|,,, (ar P(yla:)
yPhh, 1, hnt1 |,r, y 1) (1 y) P(hn 1, 1, 1 1 = 0)
P(hn 1, 1,11411 = 1/x, P) = 1/x)
P(hn 1, 1,hn+1 = 11x, P)y 0)z))
= (y ÿ) P(hn = 1,11n-1 = 1/2, = =1)
+ (1 y (1 ()), = 1, 1 =0
= (y [Phn = 1,h,+1= 1|x,y= P(h, = 1, hnt1 = 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 would be hg. The update across all L copies would then have the form:
Σ -1) 1, 1|x, ho P(ho h, 1|2, ho = 0)]
= -0/T)) - P(h1 = 1/r, ho =
= (y P(h1 = 1|2, ho = 1)
We can easily caleulate P(h 1|x, ho 1) used in this update as follows. Let node h4 have conditional probubility o(S,,), which corresponds to forward product of messages of the form:
14
-1
5h
19

---

Let the weight between nodes h2 and h4-1 in the path of interest be w;-1- The product of messages h, then including the fact that we know h 1, then has the form:
h4 e 1/1
h2
From this, we can then calculate:
P(hy 1 = +
ww-1/L)
(D.I)
For the update of the weights surrounding the output, the overall update must then have the form (Sn, + L.. Note that there are I. such copies of this update and L infinitely large. The overall update wo is then finally, lim Σ (V-)))(-))(((,, +wo/ L) = (v- (Sh,) This exactly matches the update of wo 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) (h, = 1, hn+1 = 1/2 y 1) P(hn = 1, ha+1 1|2, y = 0)]. For the remainder of this proof we focus on this difference of probabilities. Note however, the complete update does include this (1/ - D) term.
P(hn- = 1, = 1/1, = 1) - P(hn = 1, hn+1 = 1|2, = 0)
Σ P(hn = =1, = /1 [r, = P(hn = 1, 1,1n-1 = 1, hy Jr 0)
h1
P(hn = =1, 1,1411 = 1, h1 = 1|,, y = 1)
-Phh, 1, 1,h 1, h1 1/r, // = 0)
+ P(hn = 1, 1,hxt1 = 1, h1 = 0|r,y=1]
P(h,, 1, 1, 1, 1, 0|r, = 0)
P(hn = 1, hn+1 = 1|2, y = 1, h1 = P), = 1/2, y = 1)
-Phh, 1, 1|2, y = 0, h1 1) 1|r, y 0)
+ P(hn = 1, 1,1111 = 1 1 y = 1, 11 = P = 0Jz, y 1)
P(h, 1, hx+1 1 y 0, h1 0 0|r,y 0)
(Since hns hnt1 (22)
P(hn = 1, hn+1 = 1|z, h1 = 1) P(h, = 1 y = 1)
P(hn, 1, h 1|z, h 1) 1|x, y 0)
+ P(hn = 1, h,411 = 1 h1 = 0)P(h = 0|r, = 1)
P(h,, = 1, h 1|2, h 0) 0|r,y 0)
P(hn = 1, hn+1 = 1|z, h1 = l)(p(h; = 1|z,y= 1) - P(h = 1|z,y= 0))
P(hn, 1, 1/z, h1 (P 0|,,y = P(h 0|z, y 0))
[P(hn = 1, hb+1 = 1|x, h1 = 1)
x (P(h) = 1|z,,y= - P(h: = 1|,,y= 0))]
+ [P(hn = 1, =1,hm41=
= 1 h1 = =0)
x (1 P(h, = 1|2,8 1) (1 P(hi 1|2, y = 0)))
(P(h) = 1)
-cl)-P((4 P(h = 1|x,3 = 0))x
[P(h, 1,1141 1/,, h1 = 1) P(hn, 1, 11411 1/2, h1 = 0)]
Note that P(h, hu+1 -|x h1 1) P(h,
hn+1 1|x, fr = 0) has the exact same form as the difference we started with, but y (or written equivalently ho) has been effectively replaced with hy. Due the tree structure of the PGM, the conditional independence relationships are also entirely equivalent. If h2 then also existed in this branch and preceded hn, we could then apply the exact same operations to 'sum out' h this expression and replace with h22- This can be repeated until hn, itself is reached and we condition on the node one position closer to the output h Note that at for step we must multiply the entire expression by (P(h; = 1|x, h;-1 = 1) P(h: = 1 1|z, h 0)) terms.
20

---

Suppose, for the sake of induction,
P(hn = 1, 1,1411 = 111, 1) P(hn = 1,4,+1 = 1/2, y1 0)
k
-[[[(P(h: 1/2,, Mi-1 = P(1 1 14-1 0))
am1
x [P(h = h, = 1/,, h2 = 1) - P(hn = 1, An41 = 1/2 his = 0)],
where n >> k. We have already shown that this holds for the base case of is = 1. We then consider the case of (k: + 1):
1/ = Phhn 1, h,h 1/2, y 1) P(hn 1,
(By the inductive hypothesis)
(P(h; = 1/2, hi-1 = 1) - P(h; = 1/2, h4-1 =0]]
x [P(nn 1,4n+1 1/x, h4 = 1) - P(hn 1, 1|x, h4 = 0)]
(P(h: - P(h: = 111,,411110 =0]]
[P(hn = 1, hx41 1, hy = 1) - P(hn 1, hn+1 1, h..itiile 12, his = 0)]
h
= 111 P(h: = 14 0)]]
Σ
[P(hn = hx+1 1/,, h4 1, hx+1)++))))) P hx 1)
1
P(hn 1, 1,1tt11 1/x, he = 0, hx+ P(hs+1 ha 0)] (Since hn: An+1 1 halhet1)
(P(h, 1|r,hi-1 = - P(h+ 1 h4-1 0))
x
PP(n, = 1, hn+1 1/,, (1 104444)
1)
he-1
P(hn 1,,n41 = (
= =)]
(P(h: 1| 11 P(h: = - 11-1 0))
= 1, hn+1 = 11 = 1) Plux+1l2, = -0)]
(P(h: = 1|x, - - 0))
x [P(hn 1, 1,1 1 Ir, h4+1 1)(P(hu+) 1|2, h4 1) P(h+t1 1/x, h4 = 0))
+ P(hn = 1,, = 1/2, het1 () =Ojo, h = 1) P(h++1 = -O,r, hy = 0))
[ (P(h: 1/,, hi- = 1) P(h+ 1/2,, h4- 0))
X [P(hn 1, 1/2, h4+1 1)(P(1241 1/2, h1 = 1) - P(ha41 1/2, hv 0))
+ P(hn = 1, 1,1441 = 111,,4411000 0)
(1 - P(bx+1 1/2, = + P(h++1 1/2, h4 0))
21

---

(P(h: 11, = 1) - P(h; = 1|2, 1 = 0))
x (P(hn 1, 1,11 lr, hx 1)(p(1 = 1/ hi 1) P(hR+1 1/2,, hy = 0))
PPhhn = 1,1,41 = 1/,, h6+1 ()(P(h -1|2, ha = 1) - P(h++1 112, hN: 0))]
I++1
(P(h) 1 -i P(h+ 1/,, 14-1 O]]]
x [P(hn 1, 1,11 = 1/x, hu+1 1) Phhn = 1, hn+1 = hx41, 0)].
We therefore have that P(hn = 1, 1n = 1 x = 1) P(hp = 1, hn+1 1|., = 0) can be
written product of the differences P(h = 1/,, hi-1 = =1 - P((h = 1/2, 0) multiplied
by the difference P(h, = 1, hn++ = 1|z, hg = 1) P(hn 1, hn-1 1|x, hy = 0), for any k
Note that from D.1 we have that P(h; = lr 1) + w; where wi-1 is the weight between the two nodes and Sh. is the internal summation at h, from the forward pass of the neural network prior to applying the sigmoid activation function (-)). It similarly follows that P(h; 12, -1 0) (SSh)). We then divide and multiply this difference by wi-1/L.
P(h: 1/2, hi-1 1) - P(h: 1 |r, hi- = 0])
-ww;-1/L P(1+- = 1/2, /i-1 1/-1/LL
P(1++ = 1/2,, h4-1 0))
= (w)-1/L) (Sh. + +wi-1/L) - o (Sh..
wi-1/L
Note that the right hand term of the above expression has the same form the definition of derivative when placed within the limit as L approaches infinity, i.e.:
o (Sh, + w, -(())
a
lim 4
ash (Sh.).
Wi-1/L
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 7, term both per step and in the (y /)/L term. Recall that there are - copies of the weight of interest in branches with the exact same structure. We sum over these equivalent weight updates and I1+1
so have Li=1 T
The summation of all these equivalent weight updates effectively cancels this repeated division (note that this is including the I/L term shown in the final step of this proof).
We finally consider the difference involving nodes n and n + conditioned on node
P(hn = 1, hn = 1/2, h, = 1) Phh, 1, hnt1 1/2, hn-1 0) = P(hn+1 = 1|2, hn-1 = 1, hn = P(,, = 1 h1, 1)
P(hn+1 = 1|,, hn = h, 1) 1/2,, hn-1 0)
(Since hat1 1 hn-1lha)
P(hn+1 = 1|2, hn = 1), = 1|x, An-1 = 1)
P(hnnt = 111,,,, hn 1h) 1/2, hn-1 0)
= o(Sa41 + w//L) x (P(h, = 1 11-1 = - P(h,, = 1 k(-1
= =o(S,41 + wr/ L, (wn- (Sh, + Wn-1/L) oSSp..)
Wn-1/T.
The right hand term becomes the derivative of (SS..) ) as in earlier steps and the left a(:) term becomes (Sa+1) i.e. the forward pass value node n + 1, the last node relevant to this weight calculation on this branch.
22

---

The entire weight update then has the form:
a 0) Wi oSh.
(Sh.)) (Sn+1)
This is exactly the gradient update in the neural network when considering 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.
E
HMC Sampling Trajectories
Suppose the current chain state is (n()) = Pm. (0). We then draw a momentum (0) N/ M). The HMC trajectories imply that after At, we have:
At
At
(n + 2
= (n(())
(U(P)
2
p=
Al
Pa At) Pn(() AtM
Mn
(t+
(E.1)
2
At
At
(t At) pn (t
(U(
p= (1++AA)
We may then apply these equations Pa (0) and ph, (0) T. times get Pm (T.tt) and pan (I.A).. Thus, the transition from (((z) Pn, to the next state h (n+1) is given by:
(nn(Ltt) h h (h( pr, (p,(0)
with probability ((P,(
(E.2)
otherwise
where
(o) min (1,exp (H)( Mn, (0)) (L (LA())) (L.(t)))
(E.3)
F
CD-k Algorithm
Algorithm CD-k Learning for the Deep Belief Network
Input: Initialized (0),, (0) ( = 1,2, K}, ( {b:0) 1, 2..,, K}
Output: (n)) b6o) when loss converges.
1: procedure BURN-IN(N)
2: for 0 N
do 3: (i+1) + Sampling(h ((0)
4: end for
5: end procedure
6: procedure TRAINING(M)
7: for + 0 M - do
8: (((11) b(++) +- Weight-updating(/bbe (N W b(0)
9: for j - 0 to h do
+(+++++++1) <- Sampling(h (N+ik+)) w(++1), (((+1)
11: end for
12: end for
13:
end procedure
In our experiments, A: = 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
The weight-updating step is defined in equations 2 and
23

---

We also run Gibbs method for comparison, where results are shown in Table Both Gibbs and HMC are sampling methods to generate new states for all the hidden nodes and they both apply CD-1 or CD-k to learn the weight. While HMC samples real values in the range of [0, 1] under the normal distribution, Gibbs samples values in {0, 1) under Bernoulli distribution. For node haj, i.e, the jth node in h2 layer, the Bernoulli distribution used to sample its new state is determined by its Markov blanket, which includes all the nodes h h; and h in this case. It could be calculated by normalizing the joint probability distribution of the blanket when hij versus hig = 0, which is written as following:
p(hy 1[h:-1) p(h:+1 1h, (hag) hij 1) phh; = 1) p(h, 0/h--1) - p(h. (high,, = 0) + p(h,, = 1|h:-1) - oo Whey hig
We then sample new state for by from Bern(p(ha 1)). In Gibbs sampling, the node is sampled one by one since newly sampled node will affect sampling of subsequent nodes its Markov blanket. After sampling new values for all the hidden nodes, the weight is similarly updated using equations 6
and The Gibbs sampling does not depend on L.
G Experimental Setup
For all the experiments, the train-test split ratio is 80:20. For the training and finetuning, Adam optimizer used with learning rate being 1 x 10-1 To get the predicted probabilities for fine-tuned network, 1000 output probabilities sampled and averaged. In synthetic experiments, both BNs and MNs have the structure with the input dimension being 4, two latent layers with 4 nodes in each one, and one binary output.
H Running time
Running time of one BN experiment in the main text are shown in Table 3
Table 3: Average running time of different methods synthetic datasets. For DNN, it shows the time of the training for 100 and 1000 epochs. For Gibbs and HMC, shows the time of the finetuning for 20 epochs.
Average Running Time (s)
Data (Weight)
# Train Epochs
DNN
Gibbs
HMC-10
HMC-100
HMC-1000
100
7.07
2769.81
666.33
650.10
758.37
BN (0.3)
1000
60.31
2741.30
634.20
626.79
728.57
100
7.22
28T1.77
640.68
661.12
757.21
BN (I)
1000
65.25
2784.53
617.21
643.96
730.81
100
5.09
2616.04
615.96
615.05
636.93
BN (3)
1000
44.83
2602.65
596.23
594.62
608.02
100
6.87
2686.98
638,80
665.14
661.82
BN (10)
1000
48.98
2666.23
617.72
646.08
646.06
100
7.26
2703.71
645.57
635,42
129.60
MN (0.3)
1000
62.38
2669.61
625.38
618.07
701.31
100
4.94
2508.05
578.88
582.59
610.07
MN (1)
1000
44.39
2474.70
559.11
560.54
584.33
100
10.84
2610.14
591.43
579.26
605.13
MN (3)
1000
52.82
2578.81
570.23
558.98
585.22
24

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
[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 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 is clear that these goals attained by the paper.
2. Limitations
Question: [Yes]
Does the paper discuss the limitations the work performed by the authors?
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.
Justification:
Guidelines:
The answer NA means that the paper has 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 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 the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or 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 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
25

---

Answer: [Yes]
Note that for space reasons, the detailed proof had to be moved to the supple- ment.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Note that a reader will have to download our provided software and data to reproduce experiments, although as much detail was included in the paper space permits.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
26

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: Yes, the data and code are all available. We provide the link for them the end of the introduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
cablic//uuddes/Codeuubbsss cosssiionllyyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttps/cccppclcccuui.eeeeeeccc
Stteee///ooSSSeeissSioi.a www.ssssiicgcyo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
All details are 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, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
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 emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
27

---

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 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 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 figures symmetric error bars that would yield results that are out 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.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed 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 simply summarize that SGD is the fastest, Gibbs is the slowest, and HMC is 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, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well 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).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We read the Code, and the research here conforms fully.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal 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 proper statistical model. This ability is key to trustworthy AI.
28

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The data and models do not have high risk of misuse. The data are either synthetic, themselves from synthetic target models, or are publicly available.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All software and dataq sets are described and cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
29

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperssi thood cww datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 encouraged to reach out to the asset's 's creators.
13. 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 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 anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. 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 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 contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS 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.
15. 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 crowdsoureing nor research with human subjects.
30

---

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.
31


Reviews:
[{"review_id": "3rRWknluDb", "reviewer": "Reviewer_zi4w", "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.", "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?\n\nWhy is Hamiltonian Monte Carlo a particularly natural fit for this setting?\n\n\nLOW-LEVEL QUESTIONS AND COMMENTS:\n\n(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?~~\nEdit: 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), \n\nIn 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. \n\nClarification 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?\n\nWhy is the variance $p_{ij} (1-p_{ij})/L$ in equation 1?  Is this shown in the appendix, or do you have a reference?\n\nIs there some relation between the $M^{-1}$ covariance and the weight $\\mathbf W$? Where do you get the esimtate of $M^{-1}$? \n\nShouldn't $\\boldsymbol \\mu$ factor into the update in equation (7) somewhere?\n\nHow 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. \n\nThe 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": "The authors do discuss limitations a reasonable extent.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The approach to understanding the internals of a DNN probabilistically are novel, and it seems like an approach worth pursuing at a high level.  The introduction is well written, modulo a few techincal gripes.  The biggest case to be made in favor of this construction (perhaps augmented with HMC) is that it might help reinterpret a trained network in probabilistic terms, avoiding pitfalls with maximum likelihood in \"post-processing\".  The authors set up experiments that seem to show this to a small degree in a synthetic setting.  The approach is creative and interesting.", "weaknesses": "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. \n\nOn 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. \n\nI 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. \n\n-----\nminor line-by-line comments:\n-  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).\n- 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.\n- 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. \n- 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.  \n- The usage of \"mean-field approximation\" on lines 148-149 is non-standard and seems like a  false connection to me. \n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and constructive review. We take the comments and questions in order, except that the first criticism of the theory is general and leaves the specifics for later, so we take those later, in the order they are given.\n\n- *\"Lack of standard baselines\"* The baselines are SGD and Gibbs; the first is exactly correct with respect to the DNN and the second is exactly correct with respect to a direct PGM intepretation of the DNN as a Bayesian belief network.  Since Gibbs is excessively slow in this setting, we begin with SGD and then refine with Gibbs for the Gibbs baseline.\n\n- *On comparison to regularized approaches or use of larger/unlimited datasets.* Early stopping is the most commonly used, successful regularizer in SGD, so in every case we compare 100 epochs of SGD against 1000 epochs.  In most cases the message is similar for both 100 and 1000 epochs, with the exception when we get to the largest weights in the ground truth Markov network; here regularization *hurts* rather than *helps* the baseline of SGD.\n\n- *\"The HMC for the real world data works best for the smallest L...\"* The updated results (attached) with repeated training runs now agree exactly with what the theory predicts, suggesting that previous inconsistencies were due to random variability. As L gets small, HMC gets close to Gibbs (Bayesian belief net as ground truth), and as L gets large, HMC gets close to the DNN forward pass (infinite-width tree-structured PGM as ground truth).  When the ground-truth DNN weights are large, this difference is great, and it is more critical to agree with the infinite-width tree-structured PGM; here HMC1000 wins, although it doesn't beat SGD provided SGD gets sufficient epochs (1000 rather than 100).  When the ground truth DNN weights are small, Gibbs and the faster HMC10 win.\n\n- *\"I disagree that VAEs\"*  VAEs are still commonly regarded as among the first works in the progression linking DNNs and PGMs, so we prefer to retain this citation, but we will certainly cite the suggested reference as an important step in this progression.\n\n- *\"The notation in lines 74-75\"* It is common to write $P(X_1,\\cdots,X_n) = \\prod_i P(X_i|Pa(X_i))$ to stand as holding over all the possible different settings of $X_1,\\cdots,X_n$ in defining the joint distribution represented by a Bayesian network (see Russell and Norvig textbook for example). But we see how our use of lower-case variable names here might have confused matters, so we will use upper-case variables names and clarify our meaning beforehand, also with a citation.\n\n- *\"mean-field approximation on lines 148-149\"* The term mean field approximation was used in that section due how the forward pass of the neural network might be viewed as using the expectation of the nodes of the previous layer to calculate their their value, which aligns somewhat with the mean field approximation described in: Jun Zhang, \"The Mean Field Theory In EM Procedures For Markov Random Fields,\" \\textit{Proceedings of the Seventh Workshop on Multidimensional Signal Processing}, Lake Placid, NY, USA, 1991, pp. 9.1-9.1, doi: 10.1109/MDSP.1991.639423. That said, the connection is indeed underexplored in this paper and differs notably in how the neural network only ever passes information forward. A more precise description, that the neural network effectively takes a local average from the immediately previous nodes and passes that information only forward, is more apt and we will revise.\n\n- *\"I disagree that this doubly exponentially large tree-structured graphical model is `easier to understand'...\"*  We meant specifically that the tree-structured graphical model represents a full joint probability distribution over all the nodes in the neural network under the standard semantics of all Markov networks. We will tighten the language to clarify.\n\n- *\"I also do not see why ... SGD is relevant to the discussion\"* Our MN is well-defined regardless of SGD. But the point of the theorem is that for every node, the probability it is true in the MN equals its output in the DNN.  As a result, the MN interpretation gives the same gradient that SGD uses.  So SGD training is correct with respect to this MN, and this MN is correct with respect to SGD training.  We wanted the MN to not be just some representation of the DNN, but the joint probability distribution with respect to which SGD in the DNN is correct.\n\n- *\"(Lines 96-99)\"* Thank you for the catch, the DNN indeed does not align with Bayesian networks or Markov networks outside of the case where a single hidden node is fully surrounded by observed evidence. We will clarify in this section how the DNN might be viewed as an approximation and that the probabilities calculated otherwise would not align.\n\n- *\"In line 121, ... this 'approximation of $\\cal D'$ to $\\cal D$' is precise\"* We stated that the approximation of $\\cal D'$ to $\\cal D$ is precise because, given a weighted acyclic graph with binary input variables, the neural network's forward pass can be used to calculate an 'approximate' conditional probability for any unobserved node. The values provided by that forward pass would not match the exact conditional probabilities of a similarly structured Bayesian network, but even without the PGM construction, they are well defined and could be used as a poor approximation.\n\n- *\"Why is the variance $p_{ij} (1-p_{ij})/L$ in equation 1?\"* This follows from the normal approximation to the binomial and the fact that $\\text{Var}(X/L) = \\text{Var}(X)/L^2$ for constant $L$. We will clarify.\n\n- *Details of Section 5.1.* In the final version, we will clarify the relationship between $M^{-1}$ and $\\mathbf{W}$ and role of $\\mu$ in equation (7).\n\n- *\"How are the procedures 'Weight-updating' and 'Sampling' in Algorithm 1 defined?\"* Equation 7 does indeed define the weight update step of the proposed algorithm. The sampling step is done using an MCMC chain (specifically HMC) as described in section 5.1 and Appendix C.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WstItq7AWz", "reviewer": "Reviewer_7PML", "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. \nThe 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.  \n\nA 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.\n\nThe 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)", "questions": "Can you elaborate on the working of the Gibbs sampling baseline in the experimental evaluation? Does it also depend on L?\nAlso, how many samples were used for each of the experiments?", "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.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "1. The work establishes a formal connection between DNNs and (infinite tree-structured) PGMs. Apart from being a new perspective on DNNs, this allows access to PGM theory and algorithms for learning and inference.\n2. The authors show that the DNN forward pass is not equivalent to exact probabilistic inference on the same structure but it is equivalent to exact inference on a separate infinite tree-structured PGM that can be constructed from the DNN. This allows us to characterize the approximation made by forward pass-based inference in DNNs.\n3. The authors use the infinite tree-structured PGM equivalence result to develop an HMC-based learning algorithm for DNNs and empirically show that the algorithm yields more calibrated models.", "weaknesses": "While the paper makes important contributions, the presentation makes it hard to read in some places\n1) Lines 127-143 would be clearer if presented in an algorithm environment with appropriate notation.\n2) LineD- 245 says \"our previous C1 algorithm\" but CD-k and CD-1 are explained in lines 264-266\n3) The description of a BN in lines 270-281 seems out of place and should probably be in Section 5.1\n4) 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. \n\nWhile 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your detailed review, great comments on the paper presentation and questions about the experiments. The first weakness about the PGM-DNN construction is addressed in the general response, and we also agree that some rearrangements in Section 5 would be helpful to make the presentation more clear as you mentioned in the other weaknesses. We will include an explanation to CD-1 and CD-k when we mentioned contrastive divergence in the first paragraph of Section 5, and move the description of a BN in lines 270-281 to the beginning of section 5.1 in the revision. \n\nFor the fourth weakness about the result section, the discussions on research questions and baseline are mentioned at the beginning of Section 5.2, and the descriptions about datasets and metrics are at the beginning of Section 5.2.1 and 5.2.2 since we are using different types of datasets in our experiments. Thank you for pointing out that the results should be put after the discussion and we will modify the position setting of Table 1 and move it to the end of Section 5.2.1.\n    \nFor the first question about Gibbs sampling in the experimental evaluation, both Gibbs and HMC are sampling methods to generate new states for all the hidden nodes and they both apply CD-1 or CD-k to learn the weight. While HMC samples real values in the range of $[0, 1]$ under the normal distribution, Gibbs samples values in {0,1} under Bernoulli distribution. For node $h_{ij}$, i.e., the $j$th node in $h_i$ layer, the Bernoulli distribution used to sample its new state is determined by its Markov blanket, which includes all the nodes in layer $h_{i-1}$, $h_i$, and $h_{i+1}$ in this case. It could be calculated by normalizing the joint probability distribution of the blanket when $h_{ij}=1$ versus $h_{ij}=0$, which is written as following: \n$$\nP(h_{ij}=1)=\\frac{P(h_{ij}=1|h_{i-1})\\cdot P(h_{i+1}|h_i\\setminus\\\\{h_{ij}\\\\},h_{ij}=1)}{P(h_{ij}=0|h_{i-1})\\cdot P(h_{i+1}|h_i\\setminus\\\\{h_{ij}\\\\},h_{ij}=0)+P(h_{ij}=1|h_{i-1})\\cdot P(h_{i+1}|h_i\\setminus\\\\{h_{ij}\\\\},h_{ij}=1)}\n$$\n\nWe then sample a new state for $h_{ij}$ from $\\text{Bern}(P(h_{ij}=1))$. In Gibbs sampling, the node is sampled one by one since a newly sampled node will affect the sampling of subsequent nodes in its Markov blanket. After sampling new values for all the hidden nodes, the weight is similarly updated using Equation (5)(6)(7) (line 302). So, the Gibbs sampling we used does not depend on $L$.\n\nFor the second question about the number of samples, we use 1000 samples for each experiment, and train-test split ratio is 80:20. These are also explained at the beginning of Section 5.2.1, 5.2.2 and Appendix E.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nEUKUqamXe", "reviewer": "Reviewer_BE6o", "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", "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 are identified and adequately discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper presents a nice connection between exact inference in PGMs with DNN propagation (for sigmoid units) which seems to be previously unknown\n- There could be many foundational results that may be possible with the proposed connection (e.g. approximate inference in PGMs, etc.)\n- The paper is well written and makes its contributions and limitations very clear", "weaknesses": "- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the great comment and question. The weakness is addressed in the general response. Regarding your question, we suspect that deep neural network miscalibration may arise from the non-standard infinite width structure of the proposed probabilistic graphical model (PGM). While inference in the infinite width PGM matches the forward operations of the neural network, it is itself, a remarkably unwieldy structure. This can be seen perhaps most easily by thinking of the flow of information across the neural network during its forward pass, how, if the value of a hidden neuron is observed, i.e. no longer hidden, that information does not affect earlier neurons (unlike in more traditional PGM structures where that information might be passed backward). The infinite copies of each node in the PGM construction of the neural network also effectively passes a local average value of each parent node forward, which is itself quite restrictive. \n\nTherefore, it seem possible that graphs more closely aligned to traditional Markov Random Fields (MRFs) or Bayesian networks might be less prone to the same types of miscalibration found in neural networks when the relationship between the inputs/outputs is less deterministic. The experiments with smaller choices of $L$ were done with the aim of potentially bridging the gap between the infinite width model and a less extreme tree structured PGM. Clearly when the input/output relationship is largely deterministic, the neural network can simply match its input/output predictions to high confidence values due to being a universal function approximator, but in settings with a more probabilistic nature this disconnect between the underlying infinite-width tree structure PGM that represents the DNN's operations and a, perhaps, more plausible, traditional PGMs could be a source of under/over-confidence.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "piHc1KRxTD", "reviewer": "Reviewer_ymC3", "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.\nWhile 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:\n•\tSekhar 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.\n•\tAlexander 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.\n•\tDror 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.\nThe 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.\nComputational tree-based approaches have previously been associated with both variational and MCMC techniques, though they were not developed into practical algorithms.\nI 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.", "questions": "see summary", "limitations": "see summary", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "see summary", "weaknesses": "see summary", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for this very interesting comment about the computation tree and loopy BP.   While the computation tree is certainly a useful tool for precisely characterizing the approximation made by loopy belief propagation, we do not believe that the construction presented in this work is a trivial extension of that idea. Whereas belief propagation is exact in tree structured (non-loopy) graphs, the forward pass of the neural network when compared to conditional probability values of the Markov network with the potentials described in this work will not match even in the simple case of several hidden nodes connected in a line. Unlike loopy belief propagation then, which is well defined probabilistically in these simple cases, the neural network's forward operation must be captured by the infinite copies defined by the second step of our construction. This already differs rather notably from the use of the computation tree to characterize loopy belief propagation's approximation as that theoretical approach involves designing a tree whose values when computed are ordered correctly such that the influence of the loopy updates of belief propagation in non-tree structured graphs on nodes updated later are properly captured. \n\nSince the neural network's forward pass does not pass information backward, or in loops, the ordering of the nodes in our construction (ignoring the copies at this point) is wholly different from the computation tree that would be derived from using loopy belief propagation in a similarly structured starting graph. For example, in Figure 1 (page 3) of Loopy Belief Propagation and Gibbs Measures by Tatikonda and Jordan, it can be seen that when calculating the probability of node $a$ using the computation tree, an earlier belief about node $a$ is used earlier in the tree. For the neural network forward pass, however, information is never passed from a node back to itself. As such, the corresponding construction only ever creates copies of nodes in order to create a tree structure and account for how a local expectation is passed forward. It never creates a reordering of said nodes (as they would be ordered within the layers of the neural network). Belief propagation will naturally provide the same conditional probability as the forward pass of the neural network when it is applied within the infinite-width tree structured PGM, but that is simply a result of belief propagation being exact in tree structured graphs and said construction matching the operations of the neural network. When applied to the initial, loopy, graph defined by the neural network's structure, the relevant computation tree would not properly capture the neural network's operations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for the thoughtful and thought-provoking reviews. Here we list concerns raised by multiple reviewers and describe our plans to address them. *If a change recommended by reviewers is not explicitly addressed, this implies that we will follow the reviewer's recommendation.*

**1. Clarity of PGM Construction.** Several reviewers raised concerns about the clarity of the plain language description of the construction of the probabilistic graphical model whose conditional probability exactly matches the forward pass of the neural network. We acknowledge the need to complement these descriptions with a more precise presentation. To do this, we now use the algorithm environment to precisely define (a) Step 1 of our construction, in which we unroll the initial, likely loopy, neural network graph into a tree structure [Algorithm 1], and (b) Step 2 of our construction, in which we create infinite copies of each node and subtree necessary to exactly match the forward pass [Algorithm 2]. These two Algorithms may be found in the 1-page attachment to our response. We also intend to refine the existing plain language descriptions in the final version. By combining these two approaches, our hope is to provide a mathematically precise, reproducible description while still retaining the intuition that we believe the plain language description provides.

**2. Strength of Experimental Results.** Several reviewers also noted that they would like to see more thorough experimental results for the proposed HMC algorithm. We agree that this is key, and we have been working to provide a more comprehensive set of results that include repeated training runs and thereby allow us to determine whether differences between each training method and the baseline approach (DNN trained via SGD) are statistically significant. These results now clearly illustrate settings in which HMC-10 is favorable compared to the DNN. Specifically, HMC-10 performs best in settings where the relationship between inputs and outputs tends to be more random (lower valued weights). The results also show that HMC-10 succeeds in some of the settings where Gibbs fails. Finally, results underscore the similarity between DNN performance and HMC-100/1000 performance, suggesting that HMC-L more closely approximates DNN training as L increases, as predicted by our theoretical results.

**3. Real-World Applications.** While we agree that highlighting real-world applications will be important as we work to establish the practical benefits of this new connection between PGMs and DNNs, the current work is primarily theoretical in nature, with complementary experimental results that (a) corroborate the theory, and (b) illustrate a possible direction suggested by this new connection. Moreoever, from a practical perspective, we require much larger sample sizes to demonstrate benefit in a real-world binary classification setting, because in such settings -- in contrast to our simulations -- the true event probabilities are not known. In future work, we do plan to explore benefits of our HMC approach in real-world datasets, and we also hope to establish other practical, applications-oriented benefits of this new PGM view of DNNs.

Meta-review: 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).
Decision: Accept (poster)