A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models
Authors: Shivvrat Arya
Tahrima Rahman
Vibhav Giridhar Gogate
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Most Probable Explanation
Probabilistic Graphical Models
Probabilistic Circuits
Neural Autoregressive Model
Primary area: probabilistic_methods
TL;DR: A novel neural-based method for efficiently answering arbitrary Most Probable Explanation (any-MPE) queries in large probabilistic models.

Abstract: We propose a novel neural networks based approach to efficiently answer arbitrary Most Probable Explanation (MPE) queries—a well-known NP-hard task—in large probabilistic models such as 
Bayesian and Markov networks, probabilistic circuits, and neural auto-regressive models. By arbitrary MPE queries, we mean that there is no predefined partition of variables into evidence and non-evidence variables. The key idea is to distill all MPE queries over a given probabilistic model into a neural network and then use the latter for answering queries, eliminating the need for time-consuming inference algorithms that operate directly on the probabilistic model. We improve upon this idea by incorporating inference-time optimization with self-supervised loss to iteratively improve the solutions and employ a teacher-student framework that provides a better initial network, which in turn, helps reduce the number of inference-time optimization steps. The teacher network utilizes a self-supervised loss function optimized for getting the exact MPE solution, while the student network learns from the teacher's near-optimal outputs through supervised loss. We demonstrate the efficacy and scalability of our approach on various datasets and a broad class of probabilistic models, showcasing its practical effectiveness.

A Neural Network Approach for Efficiently Answering Most Probable Explanation Queries in Probabilistic Models
Shiyvrat Arya
Tahrima Rahman
Department of Computer Science The University of Texas at Dallas shivvrat arya@ut edu
Department of Computer Science
The University of Texas at Dallas tahr mharimm... rahman@ut Buleaattaall edu
Vibhav Gogate
Department of Computer Science
The University of Texas at Dallas vibhav, wow.goeeeeteeeeeeeeeeee.oo. edu
Abstract
We propose a novel neural networks based approach to efficiently answer arbitrary Most Probable Explanation (MPE) queries well-known NP-hard task large probabilistic models such as Bayesian and Markov networks, probabilistic circuits, and neural regressveeee models. By arbitrary MPE queries, mean that there is no predefined partition of variables into evidence and non-evidence variables. given probabilistic model into
The key idea is to distill all MPE queries neural network and then use the latter for answering queries, eliminating the need for time-gonsuming inference algorithms that operate directly on the probabilistic model. We improve upon this idea by incorporating inference-time optimization with self-supervised loss iteratively improve the solutions and employ teacher- student framework that provides a better initial network, which in turn, helps reduce the number of inference-time optimization steps. The teacher network utilizes a self- supervieed loss function optimized for getting the exact MPE solution, while the student network learns from the teacher's near-optimal outputs through supervised loss. We demonstrate the efficacy and scalability of our approach on various datasets and a broad class of probabilistic models, showcasing practical effectiveness.
Introduction
Probabilistic representations such as Probabilistic Circuits (PCs) [8. graphical models [26 such as Bayesian Networks (BNs) and Markov Networks (MNs), and Neural Autoregressive Models (NAMs) [50] widely used to model large, multi-dimensional probability distributions. However, they face a significant challenge: as the complexity of these distributions increases, solving practically relevant NP-hard inference tasks such finding the Most Probable Explanation (MPE) via exact inference techniques [39 40) becomes increasingly difficult and time-consuming. In particular, although various exact and approximate solvers exist for the MPE task in PCs, BNs and MNs, exact solvers are often too slow for practical use, and approximate solvers tend to lack the necessary accuracy, particularly in autoregressive models that currently rely slow hill-climbing/beam search methods.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In recent work, Arya et al. 4 proposed a method to overcome the limitations of existing approximate methods by using neural networks (NNs) solve the MPE task
P Their method draws Given a PC and predefined partition of variables into query and evidence sets, the core idea is to train a NN that takes an assignment to the evidence variables as input and outputs the most likely assignment to the query variables w.r.t. the distribution defined by the PC. Arya et al. suggest using either supervised or self-supervised learning techniques to train the NN; the former requires access to exact inference schemes, while the latter does not and is therefore more practical.
inspiration from the learning to optimize literature [12 15 29
42
55
In this paper, we address a more general and complex version of the MPE task than the one considered by Arya al. Specifically, we assume that there is no predefined partition of the variables into evidence and query sets, which we refer to as the any-MPE task. The complexity of the any-MPE task arises from the exponential increase in the number of input configurations, compounded by the exponential number of possible divisions of variables into evidence and query sets. Furthermore, our method applies to a broad class of probabilistic models, including BNs, MNs and NAMs, whereas Arya et al.' 's method is limited to PCs. In addition, Arya et al.'s method does not fully exploit the capabilities of self-supervision, and the benefits of combining supervised and self-supervised loss functions.
This paper presents novel approach that uses a NN for solving the any-MPE task in broad class of probabilistic models (PMs) and achieves technical advancements in three key aspects:
1. Efficient MPE Inference via Encoding Scheme and Loss Function: We introduce new encoding scheme that tailors the NN architecture to the specific structure of the input PM. This scheme not only delineates the input and output nodes for the NN but also establishes methodology for setting input values and extracting the MPE solution from the NN's outputs. Furthermore, we propose a tractable, and differentiable self-supervised loss function, enabling efficient training.
2. Inference Time Optimization with ITSELF: We introduce a novel inference technique called Inference Time Self Supervised Training (ITSELF). This technique iteratively refines the MPE solution during the inference process itself. It utilizes gradient descent paakk-rropggation) to update the NN's parameters using our proposed self-supervised loss, leading to continual (anytime) improvement towards near-optimal solutions. ITSELF fully utilizes the power of our self-supervised loss, it does not require labeled data an external MPE solver.
3. Two-Phase Pre-training with Teacher-Student Architecture: To address challenges associated with self-supervised learning and ITSELF, we propose a two-phase pre-training strategy that leverages a teacher-student architecture. Self-supervised learning can suffer from overfitting and requires careful regularization. Additionally, ITSELF, especially with random initializations, might necessitate substantial number of gradient updates to converge on optimal solutions. Our approach addresses these issues using the following methodology: (i) The teacher network first overfits the training data using ITSELF and (ii) The student network is then trained using supervised loss functions (c.g.. binary cross-entropy) by treating the teacher network's output as pscudo-labels. This supervised training phase improves and regularizes the parameter learning process of the student network. It also provides robust starting point for ITSELF, significantly reducing the required optimization steps and leading to substantial performance gains.
Finally, we conduct detailed experimental comparison of our method with existing approaches on several types of PMs such as PCs, PGMs and NAMs. Our results demonstrate that our method surpasses of-te-of-thearr approximate inference techniques in terms of both accuracy and speed.
2 Background and Motivation
Without loss of generality, we binary variables which take values from the set (0, 1). We denote a random variable by an uppercase letter (e.g., X), and a value assigned to it by the corresponding lowercase letter (e.g., 2). We denote set of random variables by bold uppercase letter (e.g., X) and an assignment of values to all variables in the set by the corresponding bold lowercase letter (e.g., x).
'Arya et al. developed NN-based method for solving the marginal maximum-dl -a a-posteriori (MMAP) task in PCs. In this paper, we focus on the MPE task, also sometimes referred to as the full MAP task, which is a special case of MMAP. Our method can be easily extended for solving the MMAP problem in PCs and tractable graphical models. For simplicity of exposition, concentrate on the MPE task in this paper.

---

Throughout the paper when we use the term probabilistic models (PMs), we are referring to broad class of probabilistic models in which computing the likelihood of an assignment to all variables in the model can be done in polynomial (preferably linear) time in the size of the model. This class includes, among others, Bayesian and Markov networks collectively called Probabilistic Graphical Models (PGMs) [26], smooth and decomposable Probabilistic Circuits (PCs) [8] and
Neural Autoregressive Models (NAMs) such as NADE [50] and MADE [17]
We are interested in solving the most probable explanation (MPE) task in PMs, namely the task of finding the most likely assignment to all unobserved (non-evidence) variables given observations (evidence). Formally, let M denote a probabilistic model defined over set of variables X that represents the distribution PMr (x). We categorize the variables X into evidence C X and query
Q S X groups, ensuring that E n Q = 0 and E DUQ = X. Then, given an assignment e to the set of evidence variables E, the MPE task can be formulated as:
MPB Q argmax argmax {log P. e)}
(1)
It is known that the MPE task is NP-hard in general and even hard to approximate (9
36
The goal of this paper develop method that trains a NN for given PM and, at test time, serves as an approximate MPE solver for any-MPE query posed over the PM. By any-MPE, we mean that the NN can take an assignment to an arbitrary subset of variables (evidence) input and output the most likely assignments to the remaining (query) variables. Recently, Arya et al. 4 proposed a NN-based solution for solving the MPE task PCs under the constraint that the partition of the variables into evidence and query sets is known before training the NN. This constraint is highly restrictive because, for generative models, is unlikely that such a partition of variables known in advance. In such cases, one would typically train discriminative model rather than generative one. Unlike Arya et al.'s method, our approach yields an any-MPF solver. Additionally, Arya al.'s approach has several limitations in that it does not fully exploit the benefits of self-suuprvision during inference time and requires the use of relatively large NNs to achieve good performance in practice. Our proposed approach, described next, addresses these limitations.
Motivation:
3 A Self-Supervised Neural Approximator for any-MPE
In this section, we develop a neural network (NN) based approach for solving the any-MPE task. Specifically, given PM, we develop input encoding (see Section 3.1] that determines the number of input nodes of the NN and sets their values for the given MPE query. Additionally, we develop an output encoding scheme that specifies the number of NN output nodes required for the given PM and enables the recovery of the MPE solution from the outputs. For training the NN, we introduce tractable and differentiable self-supervised loss function (see Section 3.2 whose global minima aligns with the MPE solutions to efficiently learn the parameters of the NN given unlabeled data.
3.1 An Encoding For any-MPE Instances
Since NNs require fixed-sized inputs and outputs, we introduce input and output encodings that generate fixed-length input and output vectors for each PM from a given MPE problem instance MPE(Q. e). To encode the input, for each variable X, E X, we associate two input nodes in the NN, denoted by X; and X, Thus for PM having (namely, |X| = n)) variables, the corresponding NN has 2n input nodes. Given a query MPE QQ e), we set the values of the input nodes as follows: (1) If X, E E and X,- = 0 is in then we set X, = O and X, = 1; (2) If X; E E and X, = 1 is in e, then we set X. = and X; = 0: and (3) If X, E Q then we set X; = 0 and X; = 0. (The assignment X, = and X; 1 is not used.) It is easy to see that the input encoding described above yields an injective mapping between the set of all possible MPE queries over the given PM and the set {0. 1)2". This means that each unique MPE query (Q,e) e) will yield unique 0-1 input vector of size 2n.
The output of the neural network comprises of nodes with sigmoid activation, where each output node is associated with a variable X; E X. We ignore the outputs corresponding to the evidence variables and define a loss function over the outputs corresponding to the query variables in the set Q. The MPE solution can be reconstructed from the output nodes of the NN by thresholding the
For value proportional to it such the unnormalized probability in Markov networks.
3

---

output nodes corresponding to the query variables appropriately (e.g., ., if the value of the output node greater than 0.5, then the query variable assigned the value 1; otherwise it is assigned to 0).
3.2 A Self-Supervised Loss Function for any-MPE
Since the output nodes of our proposed NN use sigmoid activation, each output is continuous and lies in the range [0. 1]. Given an MPE query (Q, e), let q E [o. 1] QI denote the (continuous) Most Probable Explanation (MPE) assignment predicted by the NN. In MPE inference, given e, want to find an assignment q such that log P. . (q. e) is maximized, namely, - Thus, natural loss function that we can use is log P.g (q. e). Unfortunately, the NN outputs continuous vector qe and as a result (q e) is not defined.
log P.M (q, e) is minimized.
(q
Next, we describe how to solve the above problem by leveraging the following property of the class of PMs that we consider in this paper- paper-specifficllly BNs, MNs, PCs and NAMs. In these PMs, the function f(q e) - log P.M. (M,(e, q), which is function from {0, 1 + IR is either multi-linear polynomial or a neural network, and can be computed in linear time in the size of the PMM To facilitate the use of continuous outputs.
define loss function (q e) [0, 1]" - IR such that l" coincides with on {0, 1}"" For PGMs and PCs, is a multi-lineat function and is obtained by substituting each occurrence of a discrete variable 9; with the corresponding continuous variable of E q" where of E [o, 1]. In NAMs, f is a NN and we can perform a similar substitution substitute each binary input 9; in the NN with continuous variable of E [0, 1]. This substitution transforms the discrete NN into a continuous function while preserving its functional form.
An important property of l is that it can be evaluated and differentiated in polynomial time. Moreover, when ε is defined by either a neural network (in NAMs) or a multilinear function (in BNs, MNs and PCs), the minimum value of e over the domain (0, 1J"h is less than or equal to the minimum value of the original function over the discrete domain {0, 1]" Formally,
Proposition 1. Let l(q, e) : {0, 13Th + IR be either a neural network multilinear function, and lei (q e) : [o, 1]" + R be its continuous extension obtained by substituting each binary input qa with continuous variable of [0, 1]. Then,
min ()) S min f(q,e) q'E
qE(0.1)"
Following Arya et al.
(4. we propose to improve the quality of the loss function by tightening the lower bound given in proposition ] with an entropy-based penalty (fx), governed by a > 0.
lE a)
of log(d)) + (1 - 1,) log(1 -
This penalty encourages discrete solutions by preferring of values close to 0 or I, where modulates the trade-off. Setting a to yields the continuous approximation; conversely, an a value of oo results exclusively in discrete outcomes. From proposition [ and by using the theory of Lagrange multipliers, we can show that for any a > O, the use of the entropy penalty yields a tighter lower bound: Proposition 2.
min (q T
min l +) +EE( S min f(q. e) q'0
qE(0.1)
How to use the Loss Function: Given PM defined over variables, we use the self-supervised (g(g", oz) (treating a as a hyper-parameter) to train any neural network (NN) architecture that has 2n input nodes and output nodes. This trained NN can then be used to answer any arbitrary MPE query posed over the PM. The training data for the neural network consists of assignments (evidence e) subset of the variables. Each training example can be generated using the following three-step process. We first sample a full assignment x to all variables in the PM using techniques like Gibbs sampling or perfect sampling for tractable distributions such as PCs and BNs. Second, we choose an integer k uniformly at random from the range (1....,7) n) and designate randomly selected variables as evidence variables E, and the remaining n as query variables Q Finally, we project the full assignment x on E. The primary advantage of using the self- eelf-supervised loss function that it eliminates the need for access to dedicated MPE solver to provide supervision during training: gradient- basee training of the neural network provides the necessary supervision.
loss function (q e) +

---

Computation
ITSELF Training and Forward Pass
( e))+
Towcer Network
q
Upshate Q).Q)
pre- trained)
D
Train Student Network
Gradient Computation and Update NN
Converged
Test Example
MiniBlatch
Student Network
4
Update with
Yes
(9, 9)
D
qº
Figure 1: ITSELF Training Procedure
Figure One Training Epoch for GUIDE
3.3 Inference-Time Neural Optimization using Self-Supervised Loss
At a high level, assuming that the NN is wver-parameterize, if we use self-supervised loss and repeatedly (stochastic) gradient updates over the NN for given dataset, theoretical results 2 as well as prior experimental work [46] [66] suggest that the parameters the NN will converge to point near the global minimum of the self-supervised loss function. This means that through gradient updates, the network will find npar-optimal MPE assignment for each training example. the NN can also be used during inference (test)
This strategy of performing gradient updates time to iteratively improve the MPE solution, thereby maximizing the benefits of self-supervision.
Specifically, at test time, given a test dataset (or example), we initialize the NN either randomly or using pre-trained model and then run gradient-based updates over the NN iteratively until convergence. The gradient is computed w.r.t. the self-supervised loss function 8 (g e) + ( a). We call the resulting algorithm ITSELF (Inference Time Optimization using SELF- SupeeSupe Loss), detailed in Figure The performance of ITSELF typically improves with each iteration until the loss converges.
Our proposed method, ITSELF, is closely related to test-time training approaches which are widely used solve problems in deep learning [ these previous approaches in that the global minima of our proposed self-supervised loss correspond to the MPE solutions, provided that the penalty a is sufficiently large.
19 30
51 (57. Our method differs from
Supervised Knowledge Transfer from ITSELF
A drawback of self-supe sulf-supervised loss function is that, unlike supervised loss functions such binary cross entropy, it a non-convex function of the NN outputs As a result, has a significantly larger number of local minima compared to the supervised loss function, but also potentially exponential number of global minima, because an MPE problem can have multiple optimal solutions (35). all of which have the same loss function value. Thus, optimizing and regularizing using the self-supervised loss is difficult compared to supervised loss, especially when the number of training examples is large.
Moreover, our experiments show that large datasets necessitate large, ever-parameterized neural networks (NNs) achieve near-optimal MPE solutions for all examples. However, when the training data is limited and the NN is sufficiently over-paramett paramerraeteriized our preliminary findings, along with theoretical and empirical results from prior studies [3] 6 23 27 28), suggest that the NN is more likely to approach the global optima. Specifically, with a reasonably sized NN and small dataset, the algorithm ITSELF tends yield near-optimal MPE solutions. A further challenge with ITSELF that even for small datasets, achieving convergence from a random initialization requires numerous iterations of gradient descent, rendering the training process inefficient and slow.
Note that referring convexity with respect the outputs, not the parameters of the NN.
5

---

Algorithm GUided Iterative Dual LEarning with Self-supervised Teacher (GUIDE)
1: Input: Training data D, teacher T and student S having the same structure
2: Output: Trained student network S
3:
>> Database DB stores the best MPE assignment and loss value for each example in D
4: Initialize: Randomly initialize T. S, and DB
5: for each epoch do
6: Sample a mini-batch D' from
7: Update the parameters of 'T using the algorithm ITSELF (self-supervised loss) with Dataset 'D'
8: for each example e; D' do
9: Make a forward-pass over T to get MPE assignment qi for e;
10: Update the entry DB for e, with qi it has lower loss value than the current entry
11: end for
12: Update the parameters of using the mini-batch D' and labels from DB and supervised loss
13:
T S
> Initialize T with S for the next epoch
14: end for
4.1 Teacher-Student Strategy
To address these challenges (using small datasets with ITSELF; designing better initialization for it; and using non-convex loss functions for training), we propose a two-network ceacher-studen
(22 54], where we have two networks with the same structure that are trained via mini-batch gradient updates. The teacher network overfitted to the mini-batch using our self-supervised loss via the ITSELF algorithm, and the student network is subsequently trained with a supervised loss function such as binary cross entropy. By overfitting the teacher network via ITSELF on the mini-batch, we ensure that it finds near-optimal MPE assignments for all (unlabeled) examples in the mini-batch and eventually over the whole training dataset.
strategy (7 16 20 24 37
47
The student network then learns from the teacher's outputs, using them as soft labels in a supervised learning framework. This transfer of knowledge mitigates the optimization difficulties associated with the non-conver self- seff-super loss, allowing the student network to achieve faster convergence and better generalization with a more manageable model size. Additionally, this strategy reduces the need for severe parameterization and extensive training iterations for the teacher network because is operating on a smaller dataset. It also helps achieve better initialization for ITSELF.
4.2 Training Procedure
Our proposed training procedure, which we call GUIDE, is detailed in Algorithm 1 The algorithm trains two-network system comprising teacher network (T) and student network (S) with the same structure. The goal is to train the student network using a combination of self-supervised and supervised learning strategies. The algorithm takes as input the training data D. along with the teacher and student networks, T and S, respectively and outputs a trained network S. A database (DB) is utilized to store the best MPE assignment and corresponding loss value for each example in D. The parameters of T and S, and the entries in DB, are randomly initialized at the start.
In each epoch, mani-batch D' is sampled from the training data D. The parameters of the teacher network T are then updated using the ITSELF algorithm (which uses a self-supervised loss), applied to the mini-batch D' (the mini-batch helps address large data issues associated with ITSELF). For each example e; in D', we perform a forward-pass over T to obtain an MPE assignment q. The database DB is subsequently updated with q, if it has lower loss value than the current entry for e,
Following this, the parameters of the student network S are updated using the mini-batch D', the labels from DB, and a supervised loss function (Esup) such as Binary Cross Entropy or L2 loss. Finally, the parameters of the teacher network T are reinitialized with the updated parameters of the student network S to prepare for the next epoch (addressing the initialization issue associated with ITSELF). Figure 2 illlstrates a single training epoch of GUIDE.
Thus, at high level, Algorithm I leverages the strengths of both self-supervised and supervised learning to improve training efficiency and reduce the model complexity, yielding student network S. Moreover, at test time, the student network can serve an initialization for ITSELF.

---

Experiments
This section evaluates the ITSELF method (see section 3.3 the GUIDE teacher-student training method (see section and the method that uses only self-supervised training, which we call SSMP (see section 3.2) We benchmark these against various baselines, including neural network-based and traditional polynomial-tmme algorithms that directly operate on the probabilistic model. We begin by detailing our experimental framework, including competing methods, evaluation metries, neural network architectures, and datasets.
5.1
Datasets and Graphical Models
We used twenty binary datasets extensively used in tractable probabilistic models literature S 18
34 50 referred to as TPM datasets- for evaluating PCs and NAMs. For the purpose of evaluating
PGMs, we utilized high treewidth models from previous UAI inference competitions [14]
To train Sum Product Networks (SPNs), our choice of PCs, employed the DeeProb-kit library 33 with SPN sizes ranging from 46 to 9666 nodes. For NAMs, we trained Masked Autoencoder
for Distribution Estimation (MADE) models using PyTorcc, following the approach in Germain et al. [17]. For Markov Networks (MNs), a specific type of PGM, we applied Gibbs sampling to generate 8,000, 1,000, and 1,000 samples for the training, testing, and validation sets, respectively. The query ratio (qr), defined as the fraction of variables in the query set, was varied across the set {0.1, 0.3, 0.5, 0.7, 0.8, 0.9} for each probabilistic model (PM).
5.2 Baseline Methods and Evaluation Criteria
PCs We used three polynomial-time baseline methods from the probabilistic circuits and probabilis- tic graphical models literature as benchmarks 41 45).
MAX Approximation (MAX) 45 transforms sum nodes into max nodes. During the upward pass, max nodes output the highest weighted value from their children. The downward pass, starting from the root, selects the child with the highest value each max node and includes all children of product nodes.
Maximum Likelihood Approximation (ML) 41 computes the marginal distribution P. for each variable Q; Q, setting Q; to its most likely value.
Sequential Approximation (Seq) [41 iteratively assigns query variables according to order o. At each step j. it selects the j-th query variable Qj in and assigns to it a value qj such that PMM(1) (gy e, y) is maximized, where y is assignment of values all query variables from 1 to j-1.
We further evaluated the impact of initializing stochastic hill climbing searches using solutions from all baseline approaches and our proposed methods for MPE inference, conducting 60-second searches for each MPE problem in our experiments, detailed in Park and Darwiche 41
NAMs As a baseline, we used the stochastic hill-climbing search (HC) algorithm. Following
procedure similar to that used for PCs, we conducted 60-second hill-climbing search for each test example, with query variables initialized randomly and setting evidence variables according to the values in the given example.
PGMs We employed the distributed AND/OR Branch and Bound (AOBB) method (39 baseline, using the implementation outlined in Otten [4).. Since AOBB is an anytime algorithm, we set 60-second time limit for inference per test example.
Neural Baselines Arya et al. 4 introduced Self-Super learning based MMAP solver for PCs (SSMP), training neural network to handle queries a fixed variable partition within PCs. We extend this approach to address the any-MPE task in PMs (see Section 3.2), using a single network to answer any-MPE queries as additional neural baseline.
Evaluation Criteria We evaluated competing approaches based on log-likelihood (LL.) scores, calculated as In P. q), and inference times for given evidence and query output q. Higher log-likelihood scores indicate better performance, while shorter inference times are preferable.
5.3 Neural Network-Ran -asee Approaches
7

---

We implemented two neural network training protocols for each PM and query ratio: SSMP and GUIDE. Each model was trained for 20 epochs following the training procedure outlined by Arya et 4 for SSMP. Both protocols employed two dis- tinct inference strategies, thus forming four neural-based variants. In the first strategy, we performed a single forward pass through the network to estimate the values of query variable, specified by Arya et al. The second strategy utilized our novel test- time optimization- ITSELF optimization terminates after 100 iterations or upon loss convergence for both PCs and PGMs. For NAMs, we in- crease the limit to 1,000 iterations while keeping the convergence criterion.
MAX
P9
G4
22
73
30
12
M.
41
43
25
40
25
Seg
26
64
44
43
20
SSMP
30
26
24
49
71
27
22
ITSELF approach for inference. The
SSMP ITSEET
305
104
104
GUIDEE ITSELT
304
335
113
IUT
SUT
64
SSMP GUIIRE
ITSELF ITSELF
(a) PCs: Initial Solutions
We standardized network architectures for PMs across all experi- ments. For PCs, used fully connected Neural Networks (NN) with three hidden layers (128, 256, 512 nodes). For NAMs and PGMs, single hidden layer of 512 nodes was employed. All hidden layers featured ReLU activation, while the output layers used sigmoid functions with dropout for regularization [48]. We optimized all models using Adam (25] and implemented them in py PyTorch 43 on an NVIDIA A40 GPU.
ML
Seg
J5
S3MP
three polynomial-time baselines, neural network-based SSMP, and our ITSELF and GUIDE methods- on 20 TPM datasets as shown in the contingency table in figure (detailed results in the sup- plementary materials). We generated 120 test datasets for the MPE task using 20 PCs across 6 query ratios (gr). Each cell (i.j) in the table represents how often (out of 120) the method in row i outperformed the method in column based average log- oigllikllhoodd scores. Any difference between 120 and the com- bined frequencies of cells (i,j) and (j, indicates cases where the compared methods achieved similar scores. We present sim- ilar contingency tables for Hill Climbing Search over PCs (Fig. 3b). NAMs (Fig. (3c). and PGMs (Fig. 3d) to benchmark the proposed methods against the baselines.
Results for PCs: We compare methods-incline
MAX
M.
Scz
SSMP
(WIDE
SEMP Gar2ne
(b) PCs: Hill Climbing
IIC
12
SSMP
34
42
66
34
16
SSMP
GUAZEE ITSPLF
68
The contingency table for PC (Fig. 3a shows that methods incor- porating ITSELF consistently outperform both polynomial-time and traditional neural baselines, as indicated by the dark blue cells in the corresponding rows. Notably, GUIDE ITSELF is superior to all the other methods in almost two-thirds of the 120 cases, while SSMP + ITSELF is better than both SSMP and GUIDE. In contrast, the polynomial-tine better than both SSMP and GUIDE (as used in Arya et al. 4)). highlighting ITSELL'' significant role in boosting model performance for the complex any-MPE task.
HC
5SMP
SSMP ITSELF
GUZPE ITSELF
(c) NAMs
AOBB
0
5
baseline MAX
SSMP
0
4
0
GUIDE
SSMP ITSELF
10
We compare MAX and GUIDE + ITSELF using a heatmap in Figure 4al The y-axis presents datasets by variable count and the x-axis represents query ratio. Each cell displays the percentage difference in mean LL scores between the methods, calculated %Diff. = 100 x (M0m max |/ ml The heatmap shows that GUIDE + ITSELF achieves performance comparable MAX for small query sets. As the problem complexity increases with an increase in query set size, our method consistently outper- forms MAX across all datasets, except for NLTCS and Tretail, highlighted by the green cells. In the 12 cases where GUIDE + ITSELF underperforms, the performance gap remains minimal, as indicated by the limited number of red cells in the heatmap.
GUIDE ITSELF
11
16
12
13
0
NOBB
55MP
QUIDE ITSELF ITSELF
(d) PGMs
Figure 3: MPE method compari- son across PMs. Blue shows row superiority, red shows column su- periority; darker shades indicate larger values.
8

---

Figure 3b further analyzes the performance of our proposed meth- ods against various baselines initialization strategies for Hill Climbing Search. This comparison evaluates the effectiveness of ITSELF and GUTDE in enhancing anytime methods compared to conventional heuristic initialization approaches. Notably, meth- ods incorporating ITSELF provide superior initialization for local search-based algorithms.
NETCS
MSNaC
XDDCup2k
Plants
Jestor
Audio
The contingeney table Figure 3c presents our evaluation of several methods for NAMs, including HC and two neural network approaches, SSMP and GUIDE, each tested with two inference schemes. We evaluated these methods on 20
Results for NAMs:
Accidents
Percentage Ditrerescce (S6
Dataset Name
mahrms
Retail
TPM datasets, creating 80 test sets for the MPE task using 20 MADEs across four query ratios (gr).
RUV-1
DNA
The GUIDE + ITSELF approach demonstrates superior perfor- mance compared to both baseline methods and other neural in- ference schemes, aligning with observations from PC. While HC outperforms SSMP, both GUIDE and the combination of SSMP-based training with ITSELF-basee inference surpass HC, highlighting their advantages over the baseline.
Book
WibKB
Reuters 52
-4
NGrP
BBC
The heatmaps in Figure 4b further highlight the superior perfor- mance of GUIDD ITSELF for NAMs, particularly in larger datasets where it outperforms the HC baseline by over 50% in most cases, as indicated by the dark green cells. The combi- nation of GUIDE consistently outperforms the baseline across most datasets, with exceptions only in the Mushrooms, Connect 4, and Retail. Over- all. the GUIDE + ITSELF approach significantly enhances the quality of the MPE solutions NAM models.
Query Ratio
(a) PC: GUIDE ITSELF F vs. MAX
learning with ITSELF-based inference
MSNBC
KDDCup2k
Plants
Netflxx
28
Results for PGMs: The contingency table in 3d compares the performance of AOBB and four setrral-etwwor-bassee methods on PGMs across four high-treewidth networks. For this evalua- tion, generated 16 test datasets for the MPE task using four PGMs across four query ratios (qr).
Jester
Audio
17
Accidents
Peroentage Differ ence (X
Name
mehmms
Connect
Consistent with results from previous PMs, methods using IT- SELF for inference consistently outperform the baseline methods AOBB and SSMP across most scenarios. Both GUIDD and SSMP outperform AOBB in at least 50 percent the tests. The supplementary material presents comparisons against exact lutions, conducted on less complex probabilistic models where ground truth computation remains tractable.
Rotzil
RCV-1
-17
WebKB
Reuters-52
Does a teacher-student based network outperform a single network trained with the self-supervised loss? (GUIDE vs. SSMP):
20 NGrp-
-39
BBC-
Ad
This analysis aims to evaluate the performance of GUIDE against traditional neural network training methods used in SSMP across different PMs and inference schemes. Using traditional inference scheme (i.e., one forward pass through the network), GUIDDE consistently outperforms SSMP, demonstrating its superiority in 60% of scenarios for PCs, more than 80% for NAM models, and 75% for PGM models. When employing ITSELF-based inference, GUIDE maintains this advantage, achieving higher quality solutions in more than 75%, 85%, and 80% of cases for PCs, NAMs, and PGMs, respectively. Therefore, models trained using GUIDE are consistently superior to those trained with SSMP for the any-MPE task.
<.50
Query Ratio
(b) NAM: GUIDE ITSELF HC
Figure 4: Heatmaps showing LL % Differences. Top: PC; Bottom: NAM. Green cells: our method is better. Darker shades indicate larger values.

---

Does inference time optimization improve performance? (One-Pass vs. Multi-Pass):
In this analysis, compare the performance of the single-pass inference method that of the proposed multi-pass inference method (ITSELF). ITSELF combined with SSMP training outperforms the other methods in over 85% cases for PC, and more than 75% for NAM and PGM models. When used on models trained with GUIDE, ITSELF demonstrates even better results, achieving superior performance nearly 90% of PC cases and 75% for both NAMs and PGMs. Overall, GUIDE with ITSELF inference emerges as the most effective method across all experiments. Empirical evidence consistently demonstrates ITSELF's superiority over single-pass pass inference across PMs.
The inference time analysis, detailed in the supplementary material, compares computational ef- ficiency across methods using the natural logarithm of execution time in microseconds. Neural network-based approaches with traditional inference demonstrate the fastest performance across all PMs, as they only require single forward pass compute query variable values. For MADE, models trained with GUTDE and ITSELF are the next most efficient. In PGMs, GUTDE + ITSELF ranks third, followed by SSMP ITSELF. For PCs, MAX marginally faster than both GUIDE ITSELF and SSMP + ITSELF, while ML and Seq have the longest computational times. In general, models trained with GUZDE achieve shorter inference times than those trained with the self-supervised loss (SSMP), as they require fewer ITSELF iterations due to more effective initial training.
Summary: Our experiments demonstrate that GUIDE + ITSELF outperforms both polynomial time and based baselines across various PMs, as evidenced by higher ligeliiiddood scores. Notably, ITSELF demonstrates significant advantages complex any-MPE query task within probabilistic models, emphasizing the importance of Inference Time Optimization. Furthermore, the superior performance of models trained with GUIDE compared to SSMP highlights the effectiveness of the dual network approach, which improves initial model quality and establishes an optimal starting point for ITSELF.
traditional single-pass inference in addressing the
Conclusion and Future Work
We introduced novel methods for answering Most Probable Explanation (MPE) queries in probabilistic models. Our approach employs self-supervised loss functions to represent MPE objectives, enabling tractable loss and gradient computations during neural network training. We also proposed new inference time optimization technique, ITSELF, which iteratively improves the solution to the MPE problem via gradient updates. Additionally, we introduced a dual-nctworkkbaaed combines supervised and unsupervised training which we call GUIDE to provide better initialization for ITSELF and addressing various challenges associated with self-supervised training. Our method was tested on various benchmarks, including probabilistic circuits, neural autoregressive models, and probabilistic graphical models, using 20 binary datasets and high ree-width networks. It outperformed polytime baselines and other neural methods, substantially in some cases. Additionally, it improved the effectiveness of stochastic hill climbing (local) search strategies.
strategy that
Future work includes solving complex queries in probabilistic models with constraints; training neural networks with losses from multiple probabilistic models to embed their inference mechanisms; boosting performance by developing advanced encoding strategies for similar tasks; implementing sophisticated neural architectures tailored to probabilistic models; etc.
Acknowledgements
This work was supported in part by the DARPA Perceptually-Enaable Task Guidance (PTG) Program under contract number HR001 12220005, the DARPA Assured Neuro Symbolic Learning and Rea- soning (ANSR) Program under contract number AIR001122S0021 the National Science Foundation grant IIS- 165283,, and the AFOSR award FA9550-23-1-0229,
References
[1] Ferran Alet, Maria Bauza, Kenji Kawaguchi, Nurullah Giray Kuru, Tomás Lozano-Pérez, and Leslie Kaelbling. Tailoring: Encoding inductive biases by optimizing unsupervised objectives at prediction time. Advances Neural Information Processing Systems, volume 34, pages 29206-29211 Curran Associates, Inc., 2021.
10

---

[2] Zeyuan Allen-Zhu Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-pan wwrrpparameterizatoon. Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMIR, 09-15 Jun 2019.
[3] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang, Fine-grained analysis of optimization and generalization for overparameterived two-layer neural networks. In Pro- ceedings of the 36th International Conference on Machine Learning, ICML, 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 122-332. PMLR, 2019.
[4] Shivvrat Arya, Tahrima Rahman, and Vibhav Gogate. Neural Network Approximators for Marginal MAP in Probabilistic Circuits. Proceedings of the AAAI Conference on Artificial Intelligence, 38(10):10915 (8110)10918-19900 10926, March 2024. ISSN 2374-3468. doi: 10.1609/aaii.v33 v38i 28966.
[5] Jessa Bekker, Jesse Davis, Arthur Choi, Adnan Darwiche, and Guy Van den Broeck. Tractable learning for complex probability queries. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[6] Lénaïc Chizat and Francis R. Bach. On the global convergence of gradient descent for over- parameterized models using optimal transport. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3040-3050, 2018.
[7] Jang Hyun Cho and Bharath Hariharan. On the Efficacy of Knowledge Distillation. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 4793-4801, October 2019. doi: 10.1109/CCV.201190 09.0499
[8] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Technical report. University of California, Los Angeles, 2020.
[9] Gregory F. Cooper. The computational complexity of probabilistic inference using bayesian belief networks. Artificial Intelligence, 42(2-3):393-405 March 1990. ISSN 00043702. doi: (00006/0004437022999990000000000
[10] Mohammad Zalbagi Darestani, Jiayu Liu, and Reinhard Heckel. Test-time training can close the natural distribution shift performance gap in deep learning based compressed sensing. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 4754-4776. PMLR, 17-23 Jul 2022.
[11] Cassio de Campos. New Complexity Results for MAP in Bayesian Networks. IJCAI International Joint Conference on Artificial Intelligence, pages 2100-2106, 01 2011. doi: 10.5591/978- 1-71:988--11777----1-1111AA-
[12] Priya I.. Donti, David Rolnick, and J. Zico Kolter. DC3: A learning method for optimization with hard constraints. In International Conference on Learning Representations, October 2020.
[13] S. Du, Xiyu Zhai, B. Póezos, and Aarti Singh. Gradient descent provably optimizes parameterized neural networks. International Conference on Learning Representations, 2018.
[14] G. Elidan and A. Globerson. The 2010 UAI Approximate Inference Challenge. 2010.
[15] Ferdinando Fioretto, Terrence W. K. Mak, and Pascal Van Hentenryck. Predicting AC Optimal Power Flows: Combining Deep Learning and Lagrangian Dual Methods. Proceedings of the AAAI Conference on Artificial Intelligence, 34(01))630-637, April 2020. ISSN 2374-3468, doi:
10. 10.1609/uaai.v34i0...44
[16] Tommaso Furlanello, Zachary Chase Lipton, M. Tschannen, L. Itti, and Anima Anandkumar. Born Again Neural Networks. In International Conference Machine Learning, May 2018.

---

[17] Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. Made: Masked autoencoder for distribution estimation. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 881 881-889, Lille, France, 07-09 Jul 2015. PMIR.
[18] Jan Van Haaren and Jesse Davis. Markov Network Structure Learning: A Randomized Feature Generation Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1): 1 1148- 1154, 2012. ISSN 2374-3468. doi: 16099/aai.v2661.....
[19] Moritz Hardt and Yu Sun. Test-time training on nearest neighbors for large language models. In The Twelfth International Conference on Learning Representations, 2024.
[20] Byeongho Heo, Jeesoo Kim, Sangdoo Yun, Hyojin Park, Nojun Kwak, and Jin Young Choi. A Comprehensive Overhaul of Feature Distillation. 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1921-1930. October 2019, doi: 10. 10.110//0C.22001..0000
[21] Byeongho Heo, Minsik Lee, Sangdoo Yun, and Jin Young Choi. Knowledge Transfer via Distillation of Activation Boundaries Formed by Hidden Neurons. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3779-3787, July 2019. doi: 10. 00.1609/aaai.v333 wtt......111.3113777
[22] Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. CoRR, abs/1503.02531, 2015.
[23] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 8580-8589, 2018.
[24] Jangho Kim, Seonguk Park, and Nojun Kwak. Paraphrasing Complex Network: Network Compression via Factor Transfer. ArXiv, February 2018
[25] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
[26] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[27] Jaehoon Lee, S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Narain Sohl-Dickstein. Finite versus infinite neural networks: an empirical study. Neural Information Processing Systems, 2020.
[28] Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent. Journal of Statistical Mechanics: Theory and Experiment, 2020(12): December 2020. ISSN 1742-5468. doi: 11.1088/1742-5448/abbaae
[29] Ke Li and Jitendra Malik. Learning to optimize. International Conference on Learning Representutions, 2016.
[30] Yushu Li, Xun Xu, Yongyi Su, and Kui Jia. On the Robustness of Open-Worde Test-Time Training: Self-Training with Dynamic Prototype Expansion. In 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pages 1 11802-11812, Paris, France, October 2023.
IEEE. ISBN 9798350307184. doi: 10. 10.10000C1110100022...0000
[31] Huan Liu, Zijum WU, Liangyan Li, Sadaf Salchkalaibar, Jun Chen, and Keyan Wang. Towards Multi-domain Single Image Dehazing via Test-time Training. In 2022 IEÉE/CV Conference on Computer Vision and Pattern Recognition (CVPR), pages 5821-5830, New Orleans, LA, USA, June 2022. IEEE. ISBN 778-1-66546-946-3 doi: 10. /00////V222888.2222...00
[32] Yuejiang Liu, Parth Kothari, Bastien van Delfi, Baptiste Bellot-Gurlet, Taylor Mordan, and Alexandre Alahi. TTT++: When Does Suff-Super Test-Time Training Fail or Thrive? In Advances in Neural Information Processing Systems, volume 34, pages 21808 21808-21820 Curran Associates, Inc., 1.21.
12

---

[33] Lorenzo Loconte and Gennaro Gala. DeeProb-kit: a python library for deep probabilistic modelling. 2022. URL https://githuu: httpa///ww.o...eepppooo/o/////pa
[34] Daniel Lowd and Jesse Davis. Learning Markov Network Structure with Decision Trees. In 2010 IEEE International Conference on Data Mining, pages 334-343. IEEE, 2010. ISBN 978-1-4244-9131-5. doi: 10.1 00.110//CDD222000.10
[35] Radu Marinescu and Rina Dechter. Counting the optimal solutions in graphical models. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
URL hwLLattoes//prcceedng....eee cctpape.ppppppeeeeeeeeeeeee htapppeer__feeeeppeeeeeee Files//aaper/20199EEee
pdf
[36] Denis Deratani Mauá and Cassio P. de Campos. Approximation complexity of maximum A posteriori inference in sum-product networks. CoRR, abs/1703.00045,, 2017.
[37] Seyed Iman Mirzadeh, Mehrdad Farajtabar, Ang Li, Nir Levine, Akihiro Matsukawa, and Hassan Ghasemzadeh. Improved Knowledge Distillation via Teacher Assistant. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5191-5198, April 2020. doi: 10. 11119//aai.334444.55..
[38] David Osowiechi, G. A. V. Hakim, Mehrdad Noori, Milad Cheraghalikhani Ismail Ben Ayed, and Christian Desrosiers. Tuflow: Unsupervised test-time training with normalizing flow. IEEE Workshop/Winter Conference Applications of Computer Vision, 2022. doi: 10.48550/arXiv. 2210.11389.
[39] L. Otten and R. Dechter. case study in complexity estimation: Towards parallel branch-and- bound over graphical models. Conference on Uncertainty in Artificial Intelligence, 2012.
[40] Lars Otten. DAOOPT: distirtte AND/OR branch and bound for MPE problems. 2012. URL
daoopt
[41] James D. Park and Adnan Darwiche. Complexity results and approximation strategies for map explanations. Artif. Int. Res., 21(1):101-133, feb 2004. ISSN 1076-9757.
[42] Seonho Park and Pascal Van Hentenryck. Self-Supervised Primal-Dual Learning for Constrained Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4):45524406) June 2023. ISSN 2374-3468. doi: 11l166//aai.v337444.
[43] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Ginelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[44] Robert Peharz. Foundations of Sun-Product Networks for Probabilistic Modeling. PhD thesis, PhD thesis, Medical University of Graz, 2015.
[45] Hoifung Poon and Pedro Domingos. Sum-Product Networks: New Deep Architecture. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 337-346. AUAI Press, 2011.
[46] Tiancheng Qin, S. Rasoul Etesami, and Cesar A Uribe. Faster convergence of local SGD for over-parameterized models. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
[47] Adriana Romero, Nicolas Ballas, Samira Ebrahimi Kahou, Antoine Chassang, C. Gatta, and Yoshua Bengio. FitNets: Hints for Thin Deep Nets. CoRR, December 2014.
[48] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: Simple Way to Prevent Neural Networks from Overfitting. Journal of Machine Learning Research, 1999-199 2014. ISSN 1533-7928.
13

---

[49] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt. Test-Time Training with Supervisssi for Generalization under Distribution Shifts. In Proceedings of the 37th International Conference on Machine Learning, pages 9229-9248. PMLR, November 2020.
[50] Benigno Uria, Maee-Ale Côté, Karol Gregor, lain Murray, and Hugo Larochelle. Neural autoregressive distribution estimation. Journal of Machine Learning Research, 17(205):1-77, 2016.
[51] Dequan Wang, Evan Shelhamer, Shaoteng Liu, B. Olshausen, and Trevor Darrell. Tent: Fully test-time adaptation by entropy minimization. International Conference Learning Representations, 2021.
[52] Chenglin Yang, Lingxi Xie, Chi Su, and Alan L. Yuille. Snapshot Distillation: Teacher-Studee Optimization in One Generation. 2019 JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 2863, June 2019. doi: 10. 109/CVPR.2009.000229
[53] Junho Yim, Donggyu Joo, Jihoon Bac, and Junmo Kim. A Gift from Knowledge Distillation: Fast Optimization, Network Minimization and Transfer Learning. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 7130-7138, July 2017. doi:
10.1109/CVPR.201..755.
[54] Sergey Zagoruyko and N. Komodakis. Paying More Attention to Attention: Improving the Performance of Convolutional Neural Networks via Attention Transfer. ArXiv, November 2016.
[55] Ahmed Zamzam and Kyri Baker. Learning Optimal Solutions for Extremely Fast AC Optimal Power Flow. In 2020 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmartGridComm), pages 1-6, November 2020.
doi: 10.1 0..10095maarGGdCCm44788555500000 20000000000088.
[56] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: /6/ 1.03530, 2016.
[57] Wentao Zhu, Yufang Huang. Daguang Xu, Zhen Qian, Wei Fan, and Xiaohui Xie. Test-time training for deformable multi-scal. image registration. IEEE International Conference Robotics and Automation, 2021.
14

---

A Experimental Setup
A.1 Datasets and Models
Table T summarizes the datasets and the probabilistic circuits trained them. We the same datasets for both PCs [8] and NAMs [17] The selection includes both smaller datasets, such as NLTCS and MSNBC, and larger datasets with over 1000 nodes.
For Markov networks, we utilize high treewidth grid networks, specifically grid40x40.F wrapp.. grid40x40.f5 wrap, grid40x40.f10 wrap, and grid40x40.f15.o www................... Each model contains 4800 vari- ables and 1600 factors.
Table I: Summary of datasets used with their respective numbers of variables and nodes in proba- bilistic circuits.
Dataset NLTCS MSNBC
Number Variables
Number of Nodes PC
16
125
17
46
KDDCup2k
64
274
Plants
69
3737
Audio
100
348
Jester
100
274
Netflix
100
400
Accidents
111
1178
Mushrooms
112
902
Connect 4
126
2128
Retail
135
359
RCV-1
150
519
DNA
180
1855
Book
500
1628
WebKB
839
3154
Reuters-52
889
7348
20 NewsGroup
910
2467
Movie reviews
1001
2567
BBC
1058
3399
Ad
1556
9666
A.2 Hyperparameters Details
Our experimental framework was designed to ensure consistency and efficiency across all conducted experiments. For NAM's, we used MADE, training the model with hidden layers of 512 and 1024 units, respectively, using the hyperparameters from Germain et al. [17]
For neural network- based solvers, the bati- size set to 512 samples, and learning rate decay strategy, reducing the rate by 0.9 upon loss plateauing, was implemented to improve training efficiency. Optimal hyperparameters were identified via extensive 5-fold cross-validation.
In discrete loss scenarios, the hyperparameter a played pivotal role. We systematically explored the optimal a value across the range 0.001, 0.01, 1, 10, 100, 1000 for neural- hased models, including ITSELF and GUIDE. Notably, higher a values better constrain outputs to binary, thereby facilitating near-optimal results.
B Extending the Current Approach to Other Data Types and Inference Tasks
The current approach can be extended support both multi-valued discrete and continuous variables, broadening its utility in diverse scenarios.
For multi-valued discrete variables, the method can be adapted by implementing a multi-class, multi- output classification head. Each query variable is represented by a softmax output node, which provides soft evidence by generating probabilistic distributions across multiple discrete values.
15

---

To incorporate continuous variables, we introduce a linear activation function in the output layer. The loss function, specifically the multi-linear representation of the PM, is modified to accommodate continuous neural network outputs. For example, in Probabilistic Circuits that use Gaussian distribu- tions, continuous values can be directly integrated into the loss function, facilitating gradient-baset backpropagation.
These extensions primarily involve adjusting the network's output layer and refining the self- supervised loss function represented by the PM. Notably, other elements of our approach, including the ITSELF and GUIDE procedures, remain unchanged.
Our approach further extends to additional inference tasks over probabilistic models. including marginal MAP and constrained most probable explanation (CMPE) tasks. However, the scalability of this approach depends on the computational efficiency of evaluating the loss function for each infer- ence task. When this evaluation becomes computationally infeasible, the proposed method-trainin a neural network to answer queries over probabilistic models-man mmy itself become infeasible. For example, performing marginal MAP inference over NAMs and PGMs requires repeated evaluations of the loss function associated with the marginal MAP task and its gradient during training. This iterative process, essential for updating the neural network's 's parameters, can become prohibitively resource-intensivee due to the high computational demands of evaluating the marginal MAP loss over these probabilistic models.
C A Comparative Analysis of Performance of ITSELF for Different Pre- Pre-Training Methods
This section evaluates the performance of models initialized through various techniques-raan randdom initialization, SSMP, and GUIDE. Each plot represents the loss for distinct test example, with the x-axis denoting the number of ITSELF iterations and the y-axis showing the Negative Log Likelihood (NLL) scores. Lower NLL values signify better solutions. Through this empirical assessment, we compare the impact of different pre-training methods on model performance.
Figures 5 to 28 present the plots for NAMs. The plots for PCs are shown in Figures 29 to 67 Figures t8 to illlustrte the plots for PGMs. We selected the following datasets for PCs and NAMs: DNA, RCV-1, Reuters-52, Netflix, WebKB, Audio, Moviereview, and Jester. For PGMs, we used all the datasets presented in the main paper. Each plot consists of two sections. The left section presents the Negative Lige-Lieldhood Loss for 1000 iterations for all methods. The right section contains two sub-plots: the top sub-plot displays the zoomed-in losses for the first 200 iterations, while the bottom sub-pla plot shows the zoomed-in in losses for the last 200 iterations.
We randomly initialize the parameters for the random model and perform 1000 iterations of ITSELF for inference. For the two pre-trained models (SSMP and GUTDE), we update the top N layers, where N is the number of layers corresponding to that loss curve, and fix the remaining bottom layers. We extract features by passing the input through these fixed layers and then train the parameters of the top N layers. We again perform 1000 iterations of ITSELF for inference. For NAMs and PGMs. we use neural networks with up to one hidden layer, while for PCs, we employ models with up to three hidden layers.
From the plots for the three Probabilistic Modelss (PMs), we observe that models pre-trained using the proposed GUIDE training scheme generally have better starting point for ITSELF, indicated by a lower loss, compared to all other models. Across a wide array of datasets, PGMs, and query percentages, the GUIDE method consistently converges to lower or equivalent loss compared to other models. Remarkably, it sometimes achieves a loss value that is less than half of the nearest competing model. Furthermore, the losses for GUIDE are typically more stable than those of other initialization. In some scenarios, all models achieve a similar final loss, although models initialized with SSMP and those randomly initialized may experience oscillations their loss values.
Models pre-trained using the traditional supervseee loss (SSMP) typically have better or similar starting points than randomly initialized models. However, models pre-trained using the SSMP method might converge to a worse loss than their GUIDE pre-trained counterparts.
In most cases, convergence is rapid, even with reduced learning rate of 10-1 compared to the experiments shown in the main paper. Most methods converge within 200 to 300 iterations, although some may still oscillate during the later iterations of ITSELF.
16

---

Drtaset: UNA Piroetiogn:
140
140
1.30
Negatin Licbbod (N14
1.0
100
310
100
74-
701
100
400
000
800
1000
Figure 5: Analysis of ITSELF Loss Across Various Pre- Trained Models for NAMs on the DNA Dataset at a Query Ratio of 0.5.
Ditastt UIN Query Prroriagg:
165
150
142
120
140-
100
100)
200
Segatee Lag
100
74
200
400
000
5000
1000
Berskeen
Figure 6: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs the DNA Dataset at a Query Ratio of 0.7.
Dozawet: DNA, Query Perorttgg::
150
150
Augatte Lung tubicood (NL4)Suve
160
2.00
1(4)
300
500
200
400
600
1000
1000
Beraice
Figure 7: Analysis of ITSELF Loss Across Various Trained Models for NAMs the DNA Dataset at a Query Ratio of 0.9.
17

---

Dalooct: RCV-,
Pereetage
100
30-
Sugate Lang Ubclood (N14)
100
210
400
0000
800
1000
Figure 8: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the RCV-1 Dataset at a Query Ratio of 0.5.
Dutioet: RCV-L J. Quay Pecceslag:: 0.7
12
100
Degpttre Lng boue
100
60%
20
900
1000
Figure 9: Analysis of ITSELF Loss Across Various Fre-Traind Models for NAMs on the RCV-1 Dataset at Query Ratio of 0.7.
Query
401
1.0
(MA2
100
55
25-
Supptre
10
20-
1000
400
Bentikea
Figure 10: Analysis ITSELF Loss Across Various Prained Models for NAMs on the RCV-1 Dataset at Query Ratio of 0.9.
18

---

Bestens-
2000
000-
Stre
600
400
600
100
800
260
Degarte Log
300
200
200-
150
100
200
400
020
500
1000
Figure 11: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs the Reuters-52 Dataset at Query Ratio of 0.5.
Pationn: Barreme
Penercage 0.7
1000
1000
0537 20
0015
750
600
5.0
Segitee Let (MtA))00
100
500
400
200
200
500
1000
Figure 12: Analysis of ITSELF Loss Across Various Pre- Pre-Traneed Models for NAMs on the Reuters-52 Dataset at Query Ratio of 0.7.
Iatoont: BumteneS Quey Pemaccpee 0.9
1000
Augatre Lubttood DMta)
1000
500
500
210
170
200
100
200
400
800
1000
Devikkon
Figure 13: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Reuters-52 Dataset at a Query Ratio of 0.9.
19

---

Dutleeet Nettle Query Pececstage: 11
70
60
50
100.
200
Sugatee Lag
60-
Aadhan www.
ND /
www. 7/
50-
203
600
600
800
1000
Darisoe
Figure 14: Analysis ITSELF Loss Across Various Pre-Trained Models for NAMs on the Netflix Dataset at Query Ratio of 0.5.
Ditnent Netfle, Query Phrenstage 07
0009
0009 In
70-
60
Stpata log Libibodd
60-
60-
40
1000
200
1000
Figure 15: Analysis of ITSELF Loss Across Various Pre- Trained Models for NAMs on the Netflix Dataset at a Query Ratio of 0.7.
Netfla, Proecatage
80-
Mr.
0009 Wr.
Negatii (hL))
60-
60
40
31
140
1000
Brastinn
Figure 16: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Netflix Dataset at Query Ratio of 0.9.
20

---

Dersect Welki,
Porertige
000
6:0
Lunden 201
600
300
300
Stgate Leg Luklboo (M12)
202
100
210
225-
200
172
700
400
0000
800
1000
Figure 17: Analysis of ITSELF Loss Across Various Trainee Models for NAMs on the WebKB Dataset at a Query Ratio of 0.5.
Dernsct WiLBB Quey Porcntige:
700
600
400
Sode
600
800
Degatrr Leg
300
900
1000
Figure 18: Analysis of ITSELF Loss Across Various Pre- Pre-Trained Models for NAMs on the WebKB Dataset at Query Ratio of 0.7.
WarkS Quey Pementinge:
800-
000
700
Supatre Log Lukedooo 1MA2
800
500
2002
1800
200
100
100
1000
400
Bertikea
Figure 19: Analysis of ITSELF Loss Across Various Pre- Preined Models for NAMs on the WebKB Dataset at Query Ratio of 0.9.
21

---

Ditleeet Audi, Ujery Pereentage 0.5
70
60-
00-
100
200
Sugatte Lagg
80-
30-
114
20
16
203
600
600
800
1000
Darisee
Figure 20: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Audio Dataset at Query Ratio of 0.5.
Dotovet: Autie, Query Precestage
50-
80
0009
0009 In
60
70-
Sugatte log Libibedd
30-
25
20-
1050
200
200
5.0
1000
Figure 21: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Audio Dataset at a Query Ratio of 0.7.
Dollect Andio,
0009 Wr.
70-
Negatre Law (NL1)
60.
410
30+
25
140
1000
Brastin
Figure 22: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Audio Dataset at Query Ratio of 0.9.
22

---

Didtart:: Moric Quay Ponastinge: 0.5
700
2000
000
Prgazto Exg (MLL)
600
420
600
110)
800
277
1850
300
200
400
000
800
1000
Figure 23: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs the Movie reviews Dataset at Query Ratio of 0.5.
Quay Persuttgg::
800-
800
600
Sove
-00
600
600
33.
Deppatve Lng
800
1750
200
180
900
1000
Benaliee
Figure 24: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Movic reviews Dataset at Query Ratio of 0.7.
2450
Quee
800-
800
Pegatre Log Libtttoe Sours
300
200
200
600
800
160
300
150
1000
Figure 25: Analysis of ITSELF Loss Across Various Pre-Trained Models for NAMs on the Movie reviews Dataset at Query Ratio of 0.9.
23

---

Dillace: Juster, Query Percentage: 0.5
75
70
700
65
70-
60
55-
65-
100
200
35,17
Suporee Lag
80
55.5
35-
203
600
600
800
1000
Darisoe
Figure 26: Analysis of ITSELF Loss Across Various Pre- Pre-Trained Models for NAMs on the Jester Dataset at Query Ratio of 0.5.
Dastowt: Juster, Query Prrcntage
70
0009
0009 In
70-
60
70-
Segatmn log (N1
35
30
1030
202
400
1000
Figure 27: Analysis of ITSELF Loss Across Various Pre-Traines Models for NAMs on the Jester Dataset at a Query Ratio of 0.7.
Perecstage
80-
Mr.
0009 Wr.
20-
Nepatie Lag (NL1)
101
60-
60-
35
30-
140
1000
Brastion
Figure 28: Analysis of ITSELF Loss Across Various Pre-Traine Pre-Trained Models for NAMs on the Jester Dataset at Query Ratio of 0.9.
24

---

Daboue:: Peronstage 81
96-
0000
91
00-
Stpatre Leng
88.5
900
1000
Beratien
Figure 29: Analysis ITSELF Loss Across Various Pre- Trainee Models for PCs on the DNA Dataset at Query Ratio of 0.I.
DNA, Quay Peresstoge: M005
100
Nepatze log Sear
70.00
70.75
75.50
00.05
1000
Desaiion
Figure 30: Analysis ITSELF Loss Across Various Pre-Trained Models for PCs on the DNA Dataset at Query Ratio of 0.3.
25

---

Ditaset: UNA, Upery Perceriogn:
1.30
100
1:20
1.30-
100
200
50-
100
400
00.0
800
1000
Figure 31: Analysis of ITSELF Loss Across Various Pre Trained Models for PCs the DNA Dataset at a Query Ratio of 0.5.
Detaaet: DNA, Quey Perousiage: 0.7
140
64020 Jamm
125
Digpttre Lng Soue
1.50
100
1.00
1.30
900
1000
Figure 32: Analysis of ITSELF Loss Across Various Fre-Trained Models for PCs on the DNA Dataset Query Ratio of 0.7.
Tozawet: Query
4011
1.00
30501.00
125
Supttre takdbood SMA4
100
80-
1.0
150
74
1000
400
020
Bertikca
Figure 33: Analysis ITSELF Loss Across Various Pre-Traines Models for PCs on the DNA Dataset at a Query Ratio of 0.9.
26

---

Difeect. RUV-1, Queryy Mereersage U.1
75.0
100
200
00.001
Sugatee Lag
20-
65.96
05.00
203
600
600
3.0
1000
Darissee
Figure 34: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the RCV-1 Dataset at Query Ratio of 0.1.
Ditteet: RCV-1 Query Arrercage 03
00796
70-
Segatme log Libibood (N1A)
60x
60-
80
21.550
$1.358
30-
1000
200
1000
Figure 35: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the RCV-1 Dataset at a Query Ratio of 0.3.
BCV-J. Perccttage
0009 1o-
13
50
611
Negatie (NL1)/500
10-
2075
23.2050
30-
23.3025
73.9000
20
140
1000
Figure 36: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the RCV-1 Dataset at Query Ratio of 0.5.
27

---

Dalourt: RCV-1 Peecesaage
100
100
60
Segatee Lag (N14)
100
210
20-
200
400
000
800
1000
Figure 37: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the RCV-1 Dataset at a Query Ratio of 0.7.
Dutioet: RCV-1, Query Peecestiag:: 0.9
100
Jamm
100
60-
Depptrr Lng Lodtted
31.0
33.5
33.02
900
1000
Figure 38: Analysis of ITSELF Loss Across Various Pre- Pre-Trined Models for PCs on the RCV-1 Dataset at Query Ratio of 0.9.
Queey
4011
160
30551.00
Aupptre Lig Laddbro (MA4
140
60
27.0
20
1000
400
Bentieea
Figure 39: Analysis of ITSELF Loss Across Various Pre-Traae Pre-Trained Models for PC's on the Reuters-52 Dataset at Query Ratio of 0.1.
28

---

Dicaset Reatern 50, Upery Percerloge:
300
30100 05
300
320
300
100
Sugatoe Ukchadd
100
210
150
100
100
400
0000
800
1000
Figure 40: Analysis of ITSELF Loss Across Various Models for PCs on the Reuters-52 Dataset at a Query Ratio of 0.3.
Ditaset: Beaters- 5Q. Quec Peroniagge: 0.5
020
Jamm
Degatrre Lng bove
1000
400
300-
100
90
900
1000
Figure 41: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Reuters-52 Dataset at Query Ratio of 0.5.
Dacaset Beatan-S Queey
800
4011
700
Sugptte L/g Lukddood 1MA2)
470
600
300
200
400
1000
400
Bentike
Figure 42: Analysis of ITSELF Loss Across Various Pre-Traines Models for PC's on the Reuters-52 Dataset at Query Ratio of 0.7.
29

---

Danaset: Beaten 12, Queyy Parsastope:
800
1040 9o-
030
300
1000
110
400
Depates Log
80-
250
400
0000
800
1000
Figure 43: Analysis of ITSELF Loss Across Various Models for PCs on the Reuters-52 Dataset at a Query Ratio of 0.9.
Detaset Nettlie, Query Peroentagg: 0.1
57.0
Degattve Leg (NAA) Sere
06.5
62.5
3000
55.0-
58.12
51.-
63.5
1020
200
414)
Figure 44: Analysis of ITSELF Loss Across Various Pre-Treined Models for PCs on the Netflix Dataset at Query Ratio of 0.1.
Dutowst: Notfle, Query Phrorstage 03
60
0000
58
Sugatn Log Ubsbooo
16-
50-
100
200
St
40.2
1000
900
Bandiee
Figure 45: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Netflix Dataset at Query Ratio of 0.3.
30

---

Detaset: Netlin Query Presentage: 6.5
72.5
76.0
Lubebad 900m
67.5
67.0
100
200
02.5
00.0
07.5
33.04
500
1050
Figure 46: Analysis of ITSELF Loss Across Various Pre- TreiTeeeee Models for PCs on the Netflix Dataset at Query Ratio of 0.5.
Netfles Query
60
60
kamm
55-
Degative (MLL) Store
50
45-
65-
60-
01.50
1400
1000
Figure 47: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Netflix Dataset at Query Ratio of 0.7.
Datowst: Netfle, Query Peroestage
70
1000
60-
Ler (NLL) Saee
85
Supatra Lodttod
100
200
45
1000
200
Bandiee
Figure 48: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Netflix Dataset at Query Ratio of 0.9.
31

---

Dersect Welki Porertigg
250
10000.00 05
240
260
270
210
Stptoo Leg Lucbbed
260
100
210
1012
100
400
000
800
1000
Bembbes
Figure 49: Analysis of ITSELF Loss Across Various Praineeined Models for PCs the WebKB Dataset at a Query Ratio of 0.1.
Durssct WiLKB Quey Porcuttage: 0.2
000
6.120 Jamm
300-
1000
300
Deggtt Leg
250
200
180
900
1000
Figure 50: Analysis of ITSELF Loss Across Various Fre-Trained Models for PCs on the WebKB Dataset at Query Ratio of 0.3.
Quey Pencentoge::
4011
800
30501.00
300
Sugatre Luk tukebooo (MA)
420
300
450
165
300
163-
164
160
150
1000
400
Bentikca
Figure 51: Analysis of ITSELF Loss Across Various Pre-Traines Models for PCs on the WebKB Dataset at Query Ratio of 0.5.
32

---

Deraect Welki, Porertige
10100 05
600
100
210
800
Degatan Lag
360
1.30
170
100
200
400
000
800
1000
Figure 52: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs the WebKB Dataset at a Query Ratio of 0.7.
Exrrset WiRBB Quey Poreuttage:
805
700
000
Degabte Aog Sea
1000
110
800
300
45-
200
400
600
500
1000
Berskkon
Figure 53: Analysis of ITSELF Loss Across Various Pre- FraiTrained Models for PCs the WebKB Dataset at a Query Ratio of 0.9.
Dotzuet: Andio, Query Paeombagge:
02.5
60.5
60.5
58.44
28.5
35.00
58.2
26.56
1020
100
110
Donsikae
Figure 54: Analysis of ITSELF Loss Across Various Pre- Trained Models for PCs on the Audio Dataset at Query Ratio of 0.1.
33

---

Ditzaet: Audio, Query Preoentage: 0.3
80.0
100
210
Lag
62.5
36.0-
900
1050
Figure 55: Analysis of ITSELF Loss Across Various Pre-Traines Trained Models for PCs on the Audio Dataset at Query Ratio of 0.3.
Audio,
70
Degativ Hataand (MLA) Stoe
50
60-
64-
60-
50
50-
1400
1000
Figure 56: Analysis of ITSELF Loss Across Various Pre- Trained Models for PCs on the Audio Dataset at Query Ratio of 0.5.
Detoont: Autle, Preoestage
70-
1980
DE
70
70-
Aupptrr (M
80
40-
100
200
50
30
000
1000
200
Bandiee
Figure 57: Analysis ITSELF Loss Across Various Pre-Trained Models for PCs on the Audio Dataset at Query Ratio of 0.7.
34

---

Extoent: Audio, Query Pacorstage
0000
80
Pepaaae Low (HL))
60-
10
1000
200
1020
Beratten
Figure 58: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Audio Dataset at Query Ratio of 0.9.
Dilisct Movic pedjes, Quey Percunnng:: 0.1
355-
350
363-
Negitte Lug (Latteed/Ma))
450
315
110
200
331.000
300
533.75
340
330
400
020
M000
1000
Figure 59: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Movie reviews Dataset at Query Ratio of 0.I.
Quee Pereuttgg:
000
320
900
Soaben
450
Degpire Undeood Sture
500
105
354
1000
400
Figure 60: Analysis ITSELF Loss Across Various Pre-Trained Models for PCs on the Movie reviews Dataset at Query Ratio of 0.3.
35

---

Dudtact:: Mirii mecanee Quary Penseringg: 0.5
630
020
500
402
600
110)
420
Pegazto Exp
800
925
277
250
200
400
000
800
1000
Figure 61: Analysis of ITSELF Loss Across Various Pre- Tre-Trained Models for PCs the Movie reviews Dataset at Query Ratio of 0.5.
Diliset: Movic zeGiesa Queyy Perceinng:: 0.7
030
-30
600
200
800
100
200
Negate leg
800
212.5
200
400
600
500
1000
Bersikon
Figure 62: Analysis of ITSELF Loss Across Various Pre- Fre-Trained Models for PCs on the Movic reviews Dataset at Query Ratio of 0.7.
Duttsct.
Quey Perenttoge
800
31122
700
Zayn
030
Nepetre Uobtted Som
800
500
105.0
200
115:0
1000
Bertikca
Figure 63: Analysis ITSELF Loss Across Various Pre-Trained Models for PCs on the Movie reviews Dataset at Query Ratio of 0.9.
36

---

Dotrert: Jester, Precestoge: 0.1
201
70
100
300
76.0-
76.05
Seggts lag
74.70
1020
200
410
620
1000
Figure 64: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Jester Dataset at a Query Ratio of 0.1.
Datowt: Juster, Query Prrcntagee
65 2lym
00096
64-
62-
68
Negatae log
66-
1030
.00
200
5.0
1000
Figure 65: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Jester Dataset at a Query Ratio of 0.3.
Dotrant: Jahs, Query Prroettage: 0.5
70-
75.0
06066 at.
00
Unbitadd Scar
65.0
65.0
63.0
1000
1500
(10)
Dontika
Figure 66: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Jester Dataset at Query Ratio of 0.5.
37

---

Datowe: Juster, Queny Prrcetaage
0007
00096
70-
85-
80-
Supatte log
.00
200
1000
Figure 67: Analysis of ITSELF Loss Across Various Pre-Trained Models for PCs on the Jester Dataset at a Query Ratio of 0.7.
38

---

Dottad:: grodkts00.10 210 Queny Peveesioo:: 0.7
2500
-1400
Lag Soor
-0000
103
-9000
-11000
10000
12000
-12000
500
Figure 68: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the grid40x40.f10. wrap Dataset a Query Ratio 0.7.
Esteadd grililo 180 waag Querr Pereeslagg: 0.9
-2000
2000
4000
Trigatin leg Lundbod
103
230
-000
10001
10000
11500
500
1000
Figure 69: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the trid40x40.f10.o wrap Dataset at a Query Ratio of 0.9.
39

---

Esteads Sil Quey Perteslage: 0.5
-10000)
8000
-1500
10000
103
230
13000
Iripatre leg
12000
1900
-10000
-1900
-19050
(40)
1000
2001
Sueatica
Figure 70: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the grid40x40.f15 wrap Dataset at a Query Ratio 0.5.
-3000
BATIC
GATH
-3400
-1:000
0000
17000
-900
100
200
12000
-15000
10000
17000
118000
2001
-13
900
1000
Figure 71: Analysis of ITSELF Loss Across Various Pre-Trie Pre-Trained Models for PGMs the Shd400400ff5..wray Dataset a Query Ratio of 0.7.
Dat satt gno-dtsttiii wnap Query Pevestage:
-300)
2300
-10000
Ang (MLA)
-17000
-7660
10000
13500
-1500)
17000
900
5000
Figure 72: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the fri440x40.f1..wmr Dataset a Query Ratio of 0.9.
40

---

Purtech graleteei vita, Quicy Prrcostage: 0.
- 1000
1907
Degatin (MtA)
1020
1250
2903
100
-532
1750
2000
2000
5430
-2500
900
1000
Figure 73: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the 1od440x40.22.wrzg Dataset at Query Ratio of 0.5.
gralitteii snup, Quecy Peocaloge: 0.7
-000
200
1820
Segitee Log
2000
-2003
2000
900
1000
Figure 74: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the grid40x40.f2.oo wrap Dataset at Query Ratio of 0.7.
DNrret Mi winp, Quey Peocslage: 0.
-000-
Degatre Unbiaadd Soee
2003
1000
1800
-000
-2003
-200-
2500
230
000
100
210
1000
Figure 75: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs the grid40x40.f2. (2..0.222..w.. wrap Dataset at Query Ratio of 0.9.
41

---

aralMioeii NIED, Quicy Pepcestage:
2000
-3000
hrpate leg Sovee
100)
210
4000
50000
5500
5000
-0750
(000)
900
1000
Rewaloon
Figure 76: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the grid40x40.f5.ww wrap Dataset at Query Ratio of 0.5.
wmpp,
000
13 prmte
2200
Sugate (M
2000
-300
1100
10005
-000
5090
1000
0032
900
1000
Figure 77: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the hid40xx00ff.wrag Dataset at Query Ratio of 0.7.
Diteset Br wmrp, Quecy Preeologe: 0.
-2000-
1100
Deggene (NLA)
-0000
-1000
5807
-0000
230
-00
1000
210
1000
Figure 78: Analysis of ITSELF Loss Across Various Pre-Trained Models for PGMs on the grid40x40.f5.wraa. Dataset at Query Ratio of 0.9.
42

---

D Inference Time Comparison
Execution Time Comparison
NLTCS
17.91
5.72
5.60
11.28
9.95
17-91
5.65
10.26
Plants
17.91
5.69
5.61
11:10
10.03
5.48
10.35
Jester
17 91
5.67
5.00
11.15
9.86
Netfix
17.91
5.29
5.23
10.79
9.88
Log Excoition Tine
Dataset
Accidents
17.91
5.08
4.97
10.92
9:99
12
Mushrooms
17.91
5.02
4.97
10.01
9.86
5.25
Retail
17.9
4.97
4.89
10.70
10.12
8
DNA
17.91
5.29
5.17
10.84
9.68
6
Book
17.91
4.48
4.28
10.95
9.92
WebKR
17:91
4.53
4.21
10.79
9.68
BBC
HC
SSMP
GITTDE
SSMP ITSELF
GUEDDE ITSELF
Approach
Figure 79: Heatmap depicting the inference time for MADE on a logarithmic microsecond scale, where lighter color denotes shorter (more favorable) durations.
Execution
Time Comparison
NLTCS
12.80
12:13
13:90
5.76
5.52
13:35
12:21
MSNBC
12:26
11.23
12:94
5.75
5.50
12.65
11.56
Plants
15.03
16.88
17.77
6.18
5.36
16.62
15.
Audio
12.70
15.05
17.61
6.01
5.37
14.13
12.96
12.81
5.38
Netflx
12.80
14.96 96
17.62
6.06
5.40
14.33
12. 84
Log Excction Time
Dataset
Accidents
13.84
Mushroams
13.71
16.01
17.76
6.11
5.36
15. 05
1:4 044
Ad
16.04
17.92
17.92
6.39
5.40
17.66
16 06.53
DNA
14.24
16.94
17.65
6.11
5.39
15.
14.62
Book
6.21
WebKR
14.74
85
17.91
6.27
5.40
16. 45
15.
BBC
14.86
17.91
17.92
6:24
5.39
16.50
15.13
MAX
ML
Seq
SSMP
GUIDE
SSMP ITSELF
GUIDE ITSELF
Approach
Figure Heatmap depicting the inference time for on logarithmic microsecond scale, where lighter color denotes shorter (more favorable) durations.
present the inference times for all baselines and proposed methods Figures 79 to 81 Figure 79
details the inference times for MADE, while Figures 80 and 81 respectively illustrate the times for PCs and PGMs. This comparison facilitates direct evaluation of the computational efficiency across different models.
43

---

Execution Time Comparison
grd40-40 115
17.91
5.59
5.24
12.28
11:28
grid40x40
5.06
12.
14
Dataset
12
grid0040..5
17:91
5.25
5.06
12:11
10.56
0pic400400FF
AOBB
SSMP
GUIDE
SSMP ITSELF
QUIDE
Approach
Figure 81: Heatmap depicting the inference time for PGM logarithmic microsecond scale, where a lighter color denotes shorter (more favorable) durations.
Each cell displays the natural logarithm of the time, measured in microseconds, for each method and dataset. Lighter colors indicate lower values. Notably, inferences using SSMP and GUZDE require the shortest time, as these methods necessitate only a single forward pass through the neural network to obtain the values for the query variables.
For MADE, the subsequent fastest method employs a model trained with GUIDE and conducts inference using ITSELF, outperforming the approach that uses SSMP for training. This advantage stems from the reduced number of ITSELF iterations required by GUIDE, benefiting from a more effectively trained model. In PGMs, a similar pattern emerges with GUIDE ITSELF as the next fastest method, followed by SSMP + ITSELF. For PCs, MAX ranks as the next fastest, closely followed by the GUIDE ITSELF and SSMP ITSELF methods. Finally, the ML and Seq methods display the highest inference times.
Thus, if you require highly efficient method capable of performing inference in fraction of millisecond, GUIDE is the optimal choice. outperforms the baseline for both MADE and PGMs. However, if higher log-likelihood scores are necessary, GUIDE ITSELF would be suitable, generally surpasses the baselines in speed and performance across various scenarios.
E
Gap Analysis For PGM
Table 2 presents presents the log-likelihood score gap between the neural network methods (SSMP, GUIDE, SSMP ITSELF, GUZDE + ITSELF) and exact solutions. These exact solutions are obtained using AOBB, which provides near-optimal results for smaller datasets. For each approach M, the gap is calculated as the relative difference between the score of the ncar-optimal solution (determined by AOBB) and the score achieved by M. This approach is feasible due to the use of small datasets, allowing identification of exact solutions.
The final column highlights the neural- based approach achieving the best performance for each dataset and query ratio combination. Notably, GUIID and ITSELF consistently surpass other neural baselines across almost all dataset-query pairs. This analysis provides comprehensive assessment of the proposed methods relative exact solutions on small datasets, enabling a direct comparison of their effectiveness.
44

---

Table 2: Gap Between AOBB And Other Methods.
Method
Query Ratio
SSMP
GUIDE
SSMP + ITSELF
GUIZDE ITSELF
Best Method
Grids-17
0,900
0.082
0.060
0.069
0.075
GUIDE
Grids-17
0.800
0.051
0.038
0.040
0.035
GUIDE ITSELF
Grids-17
0.700
0.042
0.030
0.034
0.016
GUIDE ITSELF
Grids-17
0,500
0.026
0.024
0.024
0,007
GUIDE ITSELF GUIDE
Grids-18
0.900
0.081
0.062
0.071
0,102
Grids-18
0,700
0.033
0.027
0.024
0.015
GUTDE + ITSELF
Grids-18
0.500
0.018
0.018
0.006
GUIDE ITSELF
Grids-18
0.800
0.054
0.035
0.045
0.037
GUIDE
Segmentation-14 14
0,500
0.032
0.032
0.032
0.004
GUTDE + ITSELF
Segmentation-Ie 14
0,900
0.045
0.014
0.014
0.005
GUIDE + ITSELF
Segmentation-
0,800
0.051
0.024
0.024
GUITE +
Segmentation-14
0.700
0.029
0.029
0.005
GUIDE ITSELF
Segmentation-15
15
0,800
0.046
0.002
0.002
0.002
GUIDE ITSELF
Segmentation-15
0.500
0.003
0.003
0.003
0.000
GUTDE ITSELF
Segmentation-15
0.900
0.675
0.255
0.433
0.305
GUIDE
Segmentation-15
0.700
0.003
0.003
0.002
GUIDE
Log Likelihood Scores Comparison
This section compares log-like likelihoodd scores across baselines, SSMP. SSMP + ITSELF, GUIDE and GUTDE + ITSELF for all datasets and PMs. The log likelihood plots for NAMs are depicted Figures 82 to 1OT, while those for PCs are illustrated Figures T02 to 121 Each bar represents the mean log likelihood score of the corresponding method, with tick marks indicating the mean standard deviation. Higher values in these scores signify better performance by the method, considering they represent log likelihood scores.
F11 Scores for NAM
82 10T present the log likelihood scores for NAMs, illustrating the performance of ITSELF inference and GUIDE training relative to other baselines. The heatmaps and contingency tables discussed in the main paper corroborate the superior performance of GUTDE + ITSELF. These visual representations allow for comprehensive understanding of the performance of our methods and baseline approaches, including HC and SSMP, across various datasets and query ratios.
Figures
Figure 82: Log-Likelihool Scores on NLTCS for NAM. Higher Scores Indicate Better Performance.
F.2 Scores for PCs
Analyzing Figures 102 to 121 which focuses on PCs, reveals similar patterns. The neural-based methods significantly outperform the MAX baseline. Among these, GUIDE + ITSELF surpasses all other polynomial-tine time baselines and neural methods in over 80 percent of the experiments. This demonstrates that ITSELF substantially enhances the chances of approaching optimal solutions by performing test-time optimization. When comparing traditional inference with ITSELF, ITSELF consistently proves superior. Moreover, GUIDD outperforms the other neural-based training methods (SSMP).
45

---

Figure 83: Log-Likelihood Scores on for NAM. Higher Scores Indicate Better Performance.
ICC
SIMP
Gany Kaw
Duro Kala
Oery Saw
Figure 84: Log-Likelihood Scores on KDDCup2k for NAM. Higher Scores Indicate Better Perfor- mance.
DATIN
Kates
Cary Rare
Figure 85: Log- Lokeeiicld Scores on Plants for NAM. Higher Scores Indicate Better Performance.
46

---

Cary
Dery Tade
Figure 86: Likeliiod Scores on Audio for NAM. Higher Scores Indicate Better Performance.
SAMP
Cany Hala
Qurry
Figure 87: Likelloood Scores on Jester for NAM. Higher Scores Indicate Better Performance.
Figure 88: Log-Likelihood Scores on Netflix for NAM. Higher Scores Indicate Better Performance.
47

---

Figure 89: Log-Likelihood Scores on Accidents for NAM. Higher Scores Indicate Better Perfor- mance.
ICC
SIMT
Cany Kata
Kallr
Figure 90: Log-Likelihood Scores on Mushrooms for NAM. Higher Scores Indicate Better Perfor- mance.
CVTT
Cany Ratie
Sade
Figure 91: Log-Likelihood Scores on Connect 4 for NAM. Higher Scores Indicate Better Perfor- mance.
48

---

Cary
Paro
Deny Tadeo
Figure 92: Likeliiel Scores on RCV-1 for NAM. Higher Scores Indicate Better Performance.
SAMP
Cary Para
Durry
Figure 93: Log-Likeliben Scores Retail for NAM. Higher Scores Indicate Better Performance.
Figure 94: Log-Likelihood Scores on DNA for NAM. Higher Scores Indicate Better Performance.
49

---

Figure 95: Log-Likelihood Scores on Movie reviews for NAM. Higher Scores Indicate Better Performance.
ITSE7
Tedo
Cary
Figure 96: Log- Likelliod Scores on Book for NAM. Higher Scores Indicate Better Performance.
DXTIV'
Dery Kales
Cany Rer 07
Dirr Pal
Figure 97: Log-Likelihood Scores on WebKB for NAM. Higher Scores Indicate Better Performance.
50

---

Cany Raree
Query Ka
Figure 98: Log-Likelihood Scores on Reuters-52 for NAM. Higher Scores Indicate Better Perfor- mance.
SOMT
OUNN
Qery Aale
Cany
Query
Qery Mat
Figure 99: Log-Likelihood Scores on 20 NewsGroup for NAM. Higher Scores Indicate Better Performance.
Todo
Casy Patle
Qury Ca
Dery
Figure 100: Log- LikeLikeli Scores on Ad for NAM. Higher Scores Indicate Better Performance.
51

---

Tado
Casy Parte
Parou
Dery
Figure 101: Log-Likelihone Scores on BBC for NAM. Higher Scores Indicate Better Performance.
GIN
S2MP
Cany/
Corry
Quen
Figure 102: Log-Likeldhood Scores NLTCS for PCs. Higher Scores Indicate Better Performance.
Figure 103: Log-Liiellhhod Scores on for PCs. Higher Scores Indicate Better Performance.
52

---

Figure 104: Log-Likelihood Scores on KDDCup2k for PCs. Higher Scores Indicate Better Perfor- mance.
ITSLF
ITSEL
Figure 105: Log-Like Likeliodd Scores on Plants for PCs. Higher Scores Indicate Better Performance.
MAX
Ceyyee 01
Kdm
Mare
Duen Kale
Que Mar
Figure 106: Log-Likelihood Scores Audio for PCs. Higher Scores Indicate Better Performance.
53

---

Figure 107: Log-Likelihood Scores on Jester for PCs. Higher Scores Indicate Better Performance.
MAX
SOVP
waleo
Query Koles
Quio
Figure 108: Log-Likelihood Scores on Netflix for PCs. Higher Scores Indicate Better Performance.
Figure 109: Log-Likelihood Scores on Accidents for PCs. Higher Scores Indicate Better Perfor- mance.
54

---

Cay
Quar Kola
Corry
Quee Kale
Qutp
Figure 110: Log-Likelihood Scores on Mushrooms for PCs. Higher Scores Indicate Better Perfor- mance.
ITSC_
Casyy Mam
Qurr Kate
Qurr
Camry Hala
Quen Maler
Ges
Figure 111: Log-Likeld Scores Connect 4 for PCs. Higher Scores Indicate Better Perfor- mance.
Figure 112: Log- Likellood Scores on RCV-1 for PCs. Higher Scores Indicate Better Performance.
55

---

Figure 113: Log-Likelhhodd Scores on Retail for PCs. Higher Scores Indicate Better Performance.
MAX
Uurr Kdiin
Carry Hine
Query Kades
Quio
Figure 114: Log-Likelihood Scores on DNA for PCs. Higher Scores Indicate Better Performance.
Figure 115: Log-Likelihood Scores on Movie reviews for PCs. Higher Scores Indicate Better Performance.
56

---

Figure 116: Log-Likelihood Scores on Book for PCs. Higher Scores Indicate Better Performance.
MAX
SAVP
AGN
Kdie
Corry Mile
Qut
Figure 117: Log-Likelihood Scores WebKB for PCs. Higher Scores Indicate Better Performance.
Figure 118: Log-Likelihood Scores on Reuters-52 for PCs. Higher Scores Indicate Better Perfor- mance.
57

---

Figure 119: Log-Likelihood Scores on 20 NewsGroup for PCs. Higher Scores Indicate Better Performance.
ITSEF
ITSEL
Figure 120: LikeLiieli Scores on Ad for PCs. Higher Scores Indicate Better Performance.
MAX
Cayyee 01
Oim Kdie
Mony Mare
Oues Kale
Figure 121: Log-Likelihood Scores on BBC for PCs. Higher Scores Indicate Better Performance.
58

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on 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 images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an 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 set of assumptions and complete (and correct) proof?
Answer: [Yes]
59

---

Justification: [NA]
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 referenced in 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 to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: [NA]
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 a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make 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 can also be provided via detailed 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, or other means that are appropriate to the research performed.
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) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, 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 to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
60

---

Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips... cc/
publ / guides Codeeubmie ss ssionns cisionnoliic
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" 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 NeurIPS code and data submission guidelines (https //nips. cc/ wwwpiicgguiiiooooooo / /eddiddee/Cdeeeeeeee CooeeeoeeeSeeeeeee SodeSuumiieee Submiss wwwsssssiiiggoooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If 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 possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: [NA]
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
61

---

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 enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does 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 compute required for each of individual experimental runs as 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:////..aaa.....oooooo/////aa
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances 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 their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Our paper improves the speed, accuracy and scalability of MPE inference algorithms. Since algorithms already exist for solving MPE tasks, do not perceive any negative or positive societal impacts beyond what currently exists.
Justification:
Guidelines:
The answer NA means that there is 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 or 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.
62

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 out 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 being used 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: 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?
Answer: [Yes]
Justification: [NA]
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers thcode com dataaetteett 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.
63

---

If this information is not available online, the authors are 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: [NA]
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
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: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsoureing 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 the NeurIPS Code of Ethies, 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: [NA]
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
64


Reviews:
[{"review_id": "zn9Yk0hLxZ", "reviewer": "Reviewer_q7PK", "summary": "This paper proposes a novel neural network-based method to solve the computationally challenging task of finding the Most Probable Explanation (MPE), which is known to be NP-hard. The proposed method involves an inference-time optimization process with a self-supervised loss function to iteratively improve the solutions. It also employs a teacher-student framework that provides a better initial network, which in turn helps reduce the number of inference-time optimization steps. Experiments demonstrate the efficacy and scalability of the proposed method compared to various baselines across different datasets.", "questions": "1. Could the authors provide more detailed explanations or visualizations to help the reader better understand the experimental setup and the interpretation of the results presented in Figures 1 and 2?\n2. Are there any plans to further extend or generalize the proposed method to handle other types of probabilistic inference tasks beyond the MPE problem?", "limitations": "N.A", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper presents a series of innovative methods, including inference-time optimization, a teacher-student framework, and self-supervised learning, to effectively address the MPE task.\nThe experimental results comprehensively evaluate the performance of the proposed approach and provide strong support for the claims made in the paper.\nThe paper is well-organized and clearly explains the details of the different modules and techniques used in the proposed solution.", "weaknesses": "The presentation of the main experimental results could be improved. The captions of Figure 1 and Figure 2 are quite simple and do not provide enough details about the information conveyed in the figures. It would be better to include more descriptive captions that explain the meaning of the rows, columns, and color schemes used in the visualizations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer q7PK\n\n### Comment 1\n> The presentation of the main experimental results could be improved. The captions of Figure 1 and Figure 2 are quite simple and do not provide enough details about the information conveyed in the figures. It would be better to include more descriptive captions that explain the meaning of the rows, columns, and color schemes used in the visualizations. \n>\n> Could the authors provide more detailed explanations or visualizations to help the reader better understand the experimental setup and the interpretation of the results presented in Figures 1 and 2?\n\n**Response:** \nThank you for your suggestion. We apologize for not providing detailed captions for the figures due to space limitations. However, we have included the necessary information in the main text (except the color scale description). Figure 1's heatmaps are explained in lines 301-305, while Figure 2's details are provided in lines 315-319, coinciding with their initial references.\n\nFor the reviewer's convenience, we offer concise descriptions of the main text figures:\n\nThe sub-figures in Figure 1 present heatmaps comparing the performance of different MPE solvers based on their average log-likelihood scores. \n\n> Each cell $(i,j)$ in the table represents how often the method in row $i$ outperformed the method in column $j$ based on average log-likelihood scores. Any difference between the total number of experiments and the combined frequencies of cells $(i,j)$ and $(j,i)$ indicates cases where the compared methods achieved similar scores.\n\nThe color scale ranges from dark blue (higher values) to dark red (lower values), with lighter shades representing intermediate scores. To enhance clarity, we will provide a more detailed description of the color scale in the figure caption.\n\nFigure 2 displays heatmaps comparing the proposed method to the baseline using percentage differences in mean LL scores (numbers on the gradient axis showcase this value). We have provided the description of the comparison in the main text:\n\n> The y-axis presents datasets sorted by variable count and the x-axis by query ratio. Each cell displays the percentage difference in mean LL scores between the methods, calculated as: \n\n\n$$\\text{Percentage Difference} = 100 \\times (ll_{nn} - ll_{max}) / |ll_{max}|$$ \n\nThe color gradient spans from dark green (proposed method outperforms) to dark red (baseline surpasses), with lighter shades indicating intermediate performance differences.\n\nFurthermore, sections 5.1 and 5.2 describe the experimental setup in detail, including information about the datasets, graphical models used for MPE inference, baseline methods, and evaluation criteria. To ensure reproducibility, we have included detailed log-likelihood scores for all experiments in the supplementary material.\n\nWe appreciate the reviewer's recommendation and concur that additional details about the color scales in the heatmaps will enhance the clarity and interpretability of Figures 1 and 2. Upon acceptance, we will incorporate these color scale descriptions into the main text. Other relevant details are already present in the main text or appendix, and we will emphasize these points as needed to improve overall comprehension.  \n\n### Comment 2\n> Are there any plans to further extend or generalize the proposed method to handle other types of probabilistic inference tasks beyond the MPE problem?\n\n**Response:** \nWe plan to extend the proposed method to various inference tasks beyond MPE, contingent on the feasibility of loss function computation. Our future research directions include:\n\n1. We will adapt our method to answer Marginal MAP queries over Probabilistic Circuits by modifying the loss function appropriately. \n\n2. Constrained inference tasks: We aim to apply our method to problems such as the Constrained Most Probable Explanation Task.\n\nHowever, it is important to note that the scalability of the proposed method is dependent on the efficiency of evaluating the loss function for the given inference task. In cases where the evaluation of the loss function becomes computationally infeasible, the applicability of the proposed method (to train a neural network to answer queries over probabilistic models) may be limited. One such example is performing marginal MAP inference over Neural Autoregressive Models and Probabilistic Graphical Models. In these scenarios, the repeated computation of the loss function value and its gradient during the training phase, which is necessary for updating the parameters of the neural network, can become prohibitively expensive.", "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": "Beqksic0eQ", "reviewer": "Reviewer_1g2T", "summary": "This paper proposes a neural network-based approach to approximate the most probable explanations (MPE) on probabilistic models. The basic idea is to train a neural network that takes as input an encoding of an assignment to an arbitrary subset of evidence variables and outputs an assignment to the remaining query variables, with the objective to maximize the likelihood given the predicted assignment. This is feasible on probabilistic models that support tractable likelihood and gradient computations such as PGMs, PCs, and NAMs. The authors present two key strategies to enhance the basic architecture. First, they employ a teacher-student architecture (GUIDE) that trains a student network by supervised learning with the teacher network’s MPE solutions as labels. In addition, they introduce inference time optimization to further refine the pre-trained models given specific MPE queries. The proposed methods are evaluated empirically on benchmark datasets and compared against baseline approximation methods.", "questions": "1. Can the proposed approach be extended to continuous variables?\n\n2. In each iteration of GUIDE, the teacher network is reinitialized with the student network. Could this result in the network being stuck at a local minimum?\n\n3. How do the results compare with exact solutions (on model and problem instances that can be solved exactly)?\n\n4. How are the results if evaluating using conditional likelihood p(q|e) instead of p(q,e)?\n\n5. How many unique query instances (evidence variables and assignments) were used in the training data? (ie what proportion of all possible instances)\n\nOther comments:\n- I would suggest adding a diagram showing the components of the proposed method to improve clarity.\n- Figure 2: typos in the percentage difference labels (e.g., >-10 and <10 should be >10 and <-10).\n- Why was this particular input encoding chosen? For example, a natural alternative using an input node to indicate whether a variable $X_i \\in \\mathbf{E}$ and another input node to denote its value $x_i$.", "limitations": "The current approach is currently limited to binary variables.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The proposed approach can answer any-MPE without a priori fixing the query/evidence variables, addressing a major limitation of prior work using neural networks to compute MPE / marginal MAP queries. The improvements using teacher-student architecture and inference tim optimization are also interesting and effective as demonstrated by experiments.\n\n+ The paper is overall well-written and easy to follow (minus some minor comments below).\n\n+ The experiments are thorough, and the results convincingly show that GUIDE+ITSELF outperforms baseline approximation methods across datasets and types of probabilistic models.", "weaknesses": "- It appears that the inference time optimization is doing a lot of the heavy lifting compared to pretraining. On experiments on PCs, the simple baseline MAX, which is a popular method for PCs, seems to outperform both SSMP and GUIDE without inference time training. The same is true, albeit to a lesser degree, for MADE.\n\n- Evaluation based on average joint likelihood p(q,e) may be biased towards the neural-network based approaches, compared to evaluating using average conditional likelihood p(q|e). Because the loss function is based on joint likelihood, it will bias the network training to perform better on evidence e with larger probability p(e) than those with smaller probability. Average joint log-likelihood could easily hide poor results on instances with low probability evidence.\n\n\n- The significance of Propositions 1 & 2 is unclear. More useful in motivating the training objective might be showing that the chosen loss function upper-bounds the target loss (negative log-likelihood) that we want to minimize.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer 1g2T\n### Comment 1\n> It appears that the inference time optimization is doing a lot of the heavy lifting compared to pretraining.\n\n**Response:** \nThe any-MPE task is challenging due to exponential input configurations and variable divisions. Training a single network for all queries is difficult due to distribution shifts. Traditionally, this would require large networks to accommodate all possibilities. ITSELF addresses these issues through novel inference time optimization, enabling superior results in any-MPE task:\n\n1. It directly optimizes neural network parameters on test examples by using a self-supervised loss function.\n2. It enables efficient adaptation to diverse query distributions without extensive pre-training.\n\nDespite the dependence on ITSELF, GUIDE provides a superior initialization for ITSELF among various pre-training methods, leading to faster convergence, improved output quality, and reduced inference time (Sections B and C, supplementary material). \n\nIn Section 4 (lines 187-200), we also provide detailed information and prior studies supporting this approach, highlighting its effectiveness and theoretical foundation. \n\nThis approach offers several key advantages:\n\n1. GUIDE enables the use of more compact network architectures.\n2. The number of iterations required at test time decreases.\n\nBy leveraging GUIDE's initialization capabilities and ITSELF's adaptive inference, we achieve superior performance among compared methods. \n### Comment 2\n> How are the results if evaluating using conditional likelihood $p(q|e)$ instead of $p(q,e)$?\n\n**Response:** \nThe log-conditional likelihood evaluation will not alter the ranking of query variable Q assignments because $$\\max_q \\log P(q|e) = \\max_q \\log P(q,e) - \\log P(e)$$ The term $\\log P(e)$ remains constant for all solutions for a given query instance. Furthermore, using the conditional likelihood $P(q|e)$ as the loss function would be identical to using the likelihood since $\\log P(e)$ does not contribute gradients to the loss. \n### Comment 3\n> The significance of Propositions 1 and 2 is unclear.\n\n**Response:** Thank you for the comment. We will rephrase the propositions to highlight their bounding properties, emphasizing that our chosen loss function is a valid surrogate for the target negative log-likelihood (NLL). \n### Comment 4\n> Can the proposed approach be extended to continuous variables?\n\n**Response:** \nYes, the approach can be easily adapted to continuous variables by using a linear output activation function. The loss function (PM) also needs to be modified to allow the use of continuous neural network outputs. For instance, PCs over continuous variables use Gaussian distributions for each variable. The continuous NN output can be inserted into the modified loss function, allowing gradient backpropagation.\n### Comment 5\n> In each iteration of GUIDE, the teacher network is reinitialized with the student network. Could this result in the network being stuck at local minimum?\n\n**Response:** Theoretically and empirically, a sufficiently large teacher network should approach the global optimum, as discussed in Section 4, lines 194-197. Updating the teacher network with multiple MPE query instances per iteration mitigates the risk of local minima, even when initialized from the student network.\n\nThe student-based teacher initialization aims to improve ITSELF's starting point for updating the teacher network. This approach accelerates convergence to near-optimal batch solutions.\n\n### Comment 6\n> How do the results compare with exact solutions?\n\n**Response:** Due to space limitations in the main paper, we have included a detailed evaluation in Section D of the supplementary material. This section examines the performance gap between solutions provided by our neural-based method and exact solutions. We specifically selected GMs with low treewidth for this comparison, enabling the computation of exact solutions. \n### Comment 7\n> How many unique query instances (evidence variables and assignments) were used in the training data? (ie what proportion of all possible instances)\n\n**Response:**  \nFor training the model, we extract the evidence values from the instances in the training dataset by randomly partitioning each example into query and evidence subsets. Consequently, as long as the model is trained, it will encounter new randomly generated query instances. Therefore, more epochs imply exposure to more unique instances. \n### Comment 8\n> I would suggest adding a diagram showing the components of the proposed method to improve clarity.\n\n**Response:** We appreciate your suggestion and will include a diagram illustrating the key components of our proposed method.\n### Comment 9\n> Figure 2: typos in the percentage difference labels (e.g., $>-10$ and $<10$ should be $>10$ and $<-10$).\n\n**Response:** We appreciate you bringing up the inconsistency in the percentage difference labels in Figure 2. We will update these labels in the revised manuscript.\n### Comment 10\n> Why was this particular input encoding chosen? \n**Response:** We can employ any injective mapping from the set of all possible MPE queries over the given PM to the set $\\\\{0,1\\\\}^{2n}$. Your suggested mapping is valid. However, for variables in the query set, we must assign a value to the second node representing the variable's unknown value. \n\nWe chose the specific encoding because it allows for an extension to an encoding suitable for training the neural network for the marginal MAP task, where the assignment (1,1) can be used for unobserved variables.\n\n### Comment 11\n> The current approach is currently limited to binary variables.\n\n**Response:** Our approach extends to both multi-valued discrete and continuous variables. For multi-valued discrete variables, we can employ multi-class multi-output classification, using softmax output nodes for each query variable as soft evidence. The extension to continuous variables is in response to comment 4.", "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": "Tp3tjUEkFg", "reviewer": "Reviewer_jEuh", "summary": "This paper proposes an approximate MPE inference scheme for multiple ***discrete*** probabilistic models that guarantee efficient log-likelihood computations. The approach is based on training a carefully-designed neural network to answer these queries, building upon three key ideas:\n1) self-supervised learning, in order to avoid labelling via expensive MPE oracles\n2) ITSELF: iterative optimization of the NN parameters at prediction time, resulting in both anytime inference and continual learning\n3) GUIDE: a teacher-student training scheme for mitigating overfitting\n\nThe approach is evaluated on multiple binary benchmarks from the TPM and PGM literature.\n\n**update after rebuttal**\n\nThe authors effectively addressed the concerns on the paper. Overall, I think that this is solid work and I hope that the authors consider adding their explanation on generalizing the approach to continuous variables and the runtime results in the main text.", "questions": "1) \"Without loss of generality, we use binary variables\" How is this WLOG? Does the approach seems limited to discrete models. If that's the case, I would be more upfront about that.\n2) Figure 1: what are the numbers in the contingency tables?\n3) How often is the approach recovering the true MPE assignment? Why not devising an experiment where ground-truth solutions can be obtained?\n4) What is the training time of the proposed approach?\n\n---\n\n### Minors:\n\nLines 139-143: is there a difference between the NN relaxation and the PGM/PC? It looks identical on a first glance.\n\nFigure 2: Shouldn't the caption be \"Top - PC, Bottom - ***NAM***\"? Also in b), shouldn't it be \"GUIDE + ITSELF ***vs.*** HC\"?", "limitations": "The limitations of the approach are not clearly stated in the text.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper is overall well-written\n- The key contributions are sensible and (to the best of my knowledge) novel\n- Extensive empirical evaluation", "weaknesses": "- The limitations of the approach are not clearly stated.\n- Some experimental details are unclear\n- Runtime evaluation, a crucial aspect of any approximate algorithm, is deferred to the supplementary work", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Response to Reviewer jEuh\n### Comment 1\n> The limitations of the approach are not clearly stated.\n\n**Response:** We have discussed our approach's limitations in the Conclusion and Future Work section. We summarize the limitations below:\n\nThe primary limitations are the inability to answer complex queries with constraints and the current lack of support for training a single neural network with losses from multiple PMs to embed their inference mechanisms. Employing a more advanced encoding scheme could significantly improve the proposed method's performance. Addressing these limitations will be the focus of our future research.\n\n### Comment 2\n> Runtime evaluation is deferred to the supplementary work\n\n**Response:** Due to space constraints, we were unable to include the figure for runtime evaluation in the main paper. However, we have provided a detailed comparison of the methods' inference times in lines 374-378 of the manuscript. Upon acceptance, we will incorporate the relevant figures into the final version of the paper as well. \n\n### Comment 3\n> \"Without loss of generality, we use binary variables\" How is this WLOG? Does the approach seems limited to discrete models.\n\n**Response:** The current approach can be extended to handle both multi-valued discrete and continuous variables. \n\nFor multi-valued discrete variables: \n\n- We can adapt the method by employing a multi-class, multi-output classification head.  \n- The neural network will have a softmax output node for each query variable, with the softmax acting as soft evidence. \n\nFor continuous variables:\n\n- We will use a linear activation function at the output layer. \n- The loss function (multi-linear representation of the Probabilistic Model) will be modified to accommodate continuous neural network outputs.\n- For example, in Probabilistic Circuits over continuous variables using Gaussian distributions, continuous values can be directly plugged into the loss function for gradient backpropagation.\n\nThis extension primarily requires adjusting the network's output layer and the self-supervised loss function (defined based on the PM). All other aspects of our method, including the ITSELF and GUIDE procedures, remain unchanged. \n\n### Comment 4\n> Figure 1: what are the numbers in the contingency tables?\n\n**Response:** We kindly refer the reviewer to lines 301-305 in Section 5 for the interpretation of the numbers in the contingency tables. For clarity, we reiterate the explanation here: \n\n> \"Each cell $(i,j)$ in the table represents the frequency with which the method in row $i$ outperformed the method in column $j$ based on average log-likelihood scores. Any discrepancy between the total number of experiments and the combined frequencies of cells $(i,j)$ and $(j,i)$ indicates instances where the compared methods achieved similar scores.\" \n\nFor example, in Figure 1a, the value 108 (bottom left corner) indicates that GUIDE+ITSELF (row) outperforms the MAX approximation (column) in 108 out of 120 instances for Probabilistic Circuits.\n\n### Comment 5\n> How often is the approach recovering the true MPE assignment? Why not devising an experiment where ground-truth solutions can be obtained?\n\n**Response:** We present the experiments on smaller models in Section D of the supplementary material and compare the solutions provided by the proposed method with the exact solutions. We specifically examine the gap between the scores of exact solutions and all neural-based methods. The graphical models used in this comparison have low treewidth, allowing the computation of exact solutions for these datasets.\n\nAnswering MPE queries over probabilistic models is an NP-Hard task, limiting the availability of ground truth solutions to models with few variables and simple structures (small treewidth). Consequently, our main evaluations on larger, more complex datasets do not include direct comparisons to ground truth. But recall that higher the likelihood of the solution, the better the solution, and therefore, we can always compare solutions output by multiple methods even though the ground truth is not available.\n\n\n\n### Comment 6\n> What is the training time of the proposed approach?\n\n**Response:** The training duration for our models varies based on model complexity and dataset size, typically ranging from 10 minutes to 2.5 hours. Notably, our ITSELF algorithm offers a significant advantage in this regard. By initializing the network with random weights (no training time), ITSELF can achieve near-optimal solutions, thus requiring zero training time. \n\n### Comment 7\n> Lines 139-143: is there a difference between the NN relaxation and the PGM/PC? \n\n**Response:** The neural network (NN) relaxation serves as a continuous approximation of the discrete Probabilistic Model (PM). This approximation is essential because:\n\n1. NN outputs are continuous values in $[0,1]$, which cannot be directly plugged into the discrete PM function.\n2. Converting continuous values to binary through thresholding or similar operations may not be differentiable, hindering gradient flow.\n\nTo address this, we define a continuous loss function $\\ell^c(\\mathbf{q}^c,\\mathbf{e}): [0,1]^n \\rightarrow \\mathbb{R}$ that coincides with the discrete loss $\\ell$ on $\\\\{0,1\\\\}^n$. While we explored alternatives like the Straight Through Estimator, our proposed loss with penalty demonstrated superior performance.\n\nPropositions 1 and 2 provide further details and theoretical results regarding this approximation.\n\n### Comment 8\n> Figure 2: Shouldn't the caption be \"Top - PC, Bottom - NAM\"? Also in b), shouldn't it be \"GUIDE + ITSELF vs. HC\"?\n\n**Response:** MADE is the NAM model selected for our experiments, which explains why we used the term \"Bottom - MADE\" instead of \"Bottom - NAM.\" You are correct in noting that the caption for Figure 2b should be \"GUIDE + ITSELF vs. HC.\" We will update the caption accordingly in the revised manuscript.", "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:
# Author Response to Reviews for Paper #12727
We appreciate the reviewers' constructive feedback, which will enhance our paper's quality. We have addressed all points raised and additionally provide the following responses to common questions and concerns below:

## Presentation of experimental results:
We acknowledge the need for improved clarity in presenting our experimental results. While the main paper contains most details about the figures, we will enhance the presentation by:

1. Adding color descriptions for the heatmaps in Figures 1 and 2.
2. Relocating descriptions from the main text to figure captions for easier comprehension.
   
These changes will facilitate a more thorough understanding of our empirical evaluation.

## Adaptation to other data types and inference tasks:

Although our experiments focus on binary variables, our proposed approach is adaptable to various scenarios. Continuous variables and multi-valued (discrete) variables can be accommodated by modifying the neural network's output layer and utilizing the corresponding PM as the loss function.

The method can also be extended to other inference tasks over PMs, such as marginal MAP and constrained most probable explanation problem.

## Comparison with exact solutions:
We recognize the importance of comparing our neural-based methods with exact solutions. However, due to the NP-hardness of MPE, computing exact solutions is infeasible for larger datasets. Nonetheless, as higher likelihoods indicate better solutions, we can still compare outputs from various methods, even in the absence of ground truth.

Our approach to this issue is twofold:
   
1. For main experiments using large datasets and probabilistic models, we compare our method against state-of-the-art approximate methods using likelihood scores.
2. In the supplementary material, we compare log-likelihood scores between our proposed method and exact solutions on smaller datasets.

Meta-review: There is agreement among the reviewers that the paper addresses an interesting and important problem and proposes an entirely new approach to answering MPE queries. Some concerns have been adequately addressed during the rebuttal.
Decision: Accept (spotlight)