Response to Reviewer jEuh

Comment 1

The limitations of the approach are not clearly stated.

Response: We have discussed our approach's limitations in the Conclusion and Future Work section. We summarize the limitations below:

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

Comment 2

Runtime evaluation is deferred to the supplementary work

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.

Comment 3

"Without loss of generality, we use binary variables" How is this WLOG? Does the approach seems limited to discrete models.

Response: The current approach can be extended to handle both multi-valued discrete and continuous variables.

For multi-valued discrete variables:

• We can adapt the method by employing a multi-class, multi-output classification head.
• The neural network will have a softmax output node for each query variable, with the softmax acting as soft evidence.

For continuous variables:

• We will use a linear activation function at the output layer.
• The loss function (multi-linear representation of the Probabilistic Model) will be modified to accommodate continuous neural network outputs.
• For example, in Probabilistic Circuits over continuous variables using Gaussian distributions, continuous values can be directly plugged into the loss function for gradient backpropagation.

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

Comment 4

Figure 1: what are the numbers in the contingency tables?

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:

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

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

Comment 5

How often is the approach recovering the true MPE assignment? Why not devising an experiment where ground-truth solutions can be obtained?

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.

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

Comment 6

What is the training time of the proposed approach?

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.

Comment 7

Lines 139-143: is there a difference between the NN relaxation and the PGM/PC?

Response: The neural network (NN) relaxation serves as a continuous approximation of the discrete Probabilistic Model (PM). This approximation is essential because:

1. NN outputs are continuous values in $[0,1]$, which cannot be directly plugged into the discrete PM function.
2. Converting continuous values to binary through thresholding or similar operations may not be differentiable, hindering gradient flow.

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

Propositions 1 and 2 provide further details and theoretical results regarding this approximation.

Comment 8

Figure 2: Shouldn't the caption be "Top - PC, Bottom - NAM"? Also in b), shouldn't it be "GUIDE + ITSELF vs. HC"?

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.

Response to Reviewer 1g2T

Comment 1

It appears that the inference time optimization is doing a lot of the heavy lifting compared to pretraining.

Response: The 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:

1. It directly optimizes neural network parameters on test examples by using a self-supervised loss function.
2. It enables efficient adaptation to diverse query distributions without extensive pre-training.

Despite 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).

In Section 4 (lines 187-200), we also provide detailed information and prior studies supporting this approach, highlighting its effectiveness and theoretical foundation.

This approach offers several key advantages:

1. GUIDE enables the use of more compact network architectures.
2. The number of iterations required at test time decreases.

By leveraging GUIDE's initialization capabilities and ITSELF's adaptive inference, we achieve superior performance among compared methods.

Comment 2

How are the results if evaluating using conditional likelihood $p(q|e)$ instead of $p(q,e)$?

Response: The 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.

Comment 3

The significance of Propositions 1 and 2 is unclear.

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

Comment 4

Can the proposed approach be extended to continuous variables?

Response: Yes, 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.

Comment 5

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?

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.

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

Comment 6

How do the results compare with exact solutions?

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.

Comment 7

How many unique query instances (evidence variables and assignments) were used in the training data? (ie what proportion of all possible instances)

Response:
For 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.

Comment 8

I would suggest adding a diagram showing the components of the proposed method to improve clarity.

Response: We appreciate your suggestion and will include a diagram illustrating the key components of our proposed method.

Comment 9

Figure 2: typos in the percentage difference labels (e.g., $>-10$ and $<10$ should be $>10$ and $<-10$).

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.

Comment 10

Why was this particular input encoding chosen? 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.

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

Comment 11

The current approach is currently limited to binary variables.

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.

Thank you for the detailed response. Most of my comments have been address, but I have a follow up regarding comment 2.

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.

While this is true when $e$ is a single fixed evidence, the data consists of multiple instances with different evidence assignments. In average joint log-likelihood, $\log P(q,e)$ for some evidence $e$ with high probability $P(e)$ could dominate $\log P(q',e')$ for another evidence $e'$ with much lower probability $P(e')$. Average conditional likelihood on the other hand weighs instances equally regardless of the probability of evidence of each instance. The dataset is constructed by sampling from the PM, which is likely to sample evidence assignments with higher probability more often, and average joint likelihood would weigh those instances even more. Thus, comparison by average joint log-likelihood could theoretically hide poor performance on low likely instances.

While the discussion period is closing soon, I would highly encourage the authors to consider also evaluating with average conditional likelihood in the revision.

Response to Reviewer q7PK

Comment 1

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.

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?

Response: Thank 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.

For the reviewer's convenience, we offer concise descriptions of the main text figures:

The sub-figures in Figure 1 present heatmaps comparing the performance of different MPE solvers based on their average log-likelihood scores.

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.

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

Figure 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:

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:

$\text{Percentage Difference} = 100 \times (ll_{nn} - ll_{max}) / |ll_{max}|$

The color gradient spans from dark green (proposed method outperforms) to dark red (baseline surpasses), with lighter shades indicating intermediate performance differences.

Furthermore, 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.

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

Comment 2

Are there any plans to further extend or generalize the proposed method to handle other types of probabilistic inference tasks beyond the MPE problem?

Response: We 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:

1. We will adapt our method to answer Marginal MAP queries over Probabilistic Circuits by modifying the loss function appropriately.

2. Constrained inference tasks: We aim to apply our method to problems such as the Constrained Most Probable Explanation Task.

However, 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.