A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference

Summary

This paper presents a variational framework for approximating neuro-symbolic inference. It addresses the weighted model counting (WMC) and most probable explanation (MPE) problems by introducing prediction and explanation models. Training techniques, such as output space factorization, regularized Dirichlet prior, and joint matching loss are discussed. To improve training efficiency and ensure logical constraint satisfaction during testing, a symbolic pruner is also proposed . Experimental evaluations demonstrate scalability and performance across three neuro-symbolic tasks.

Strengths

- The paper is well-written and easy to understand, with a clear statement of the problem and methodology. - The framework is simple and scalable, which may inspire further improvements in future work. - Some training techniques are interesting, particularly the joint matching loss, which is related to GFlowNet.

Weaknesses

- The authors have carefully discussed some weaknesses in Section 6. - The motivation behind the prediction model and explanation model needs to be clarified. - It is unclear why the explanation model is necessary. From my understanding, only the prediction model is needed for neuro-symbolic training: we just need to train the prediction model using Eqn. (7), and then train the neural network using Eqn. (4); or repeat these two steps iteratively. - Another issue is the necessity of the prediction model. First, the prediction model is introduced to approximate weighted model counting, but approximate counting or sampling of $\mathbf{w}$ is still required during its training. Second, in Line 192, the authors report that the prediction model cannot perform better than using symbolic prediction. - Some techniques are so specific that they appear to be designed only for the MNISTAdd task. For instance, as mentioned in Appendix G, the symbolic pruner is highly efficient for MNISTAdd task due to its simple mathematical structure. However, for more complex tasks, a SAT solver must be used, and the number of solver calls is proportional to the problem dimension, which is not acceptable.

Questions

- Should $\phi \leftarrow \textbf{Algorithm 2}(\textsf{beliefs}, \phi)$ be changed to $\textbf{Algorithm 1}$? - Does the framework have requirements for background knowledge? For example, should it be presented in the form of CNF? - Is it difficult to design and train the prediction model, given that it involves the approximation of the symbolic reasoning?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Yes, the limitations of the approach have been presented. The work does not have negative social impacts.

Summary

This paper introduces a variant of Probabilistic Neurosymbolic Learning that uses neural networks for approximate inference (vs. prior exponential-time exact inference). The efficacy of this approach is well-supported by various experiments.

Strengths

- The paper is well-written and overall quite clear (i.e., the paper is high-quality in general). The goals are clearly stated. For example, Section 3 starts with "Our goal is to reduce the inference complexity of PNL." - The experiments are described thoughtfully with good visualizations and tables. - Using MNISTAdd as a running example throughout was a great idea. I think it added a lot. - The authors are studying a significant problem -- i.e., that of neurosymbolic learning -- which feels especially timely. - It is a bit harder for me to comment on originality. To the best of my knowledge, this work is rather original, but there might be other related prior works not mentioned by the authors of which I'm unaware.

Weaknesses

My main concerns are about the notation. I think it could be improved, as discussed here and in the Questions section. - See questions below. - Beyond that, some of the notation is a bit clunky, particularly the double subscripts -- e.g., $q_{\phi_p}$. - Relatedly, it seems like some of these subscripts are a bit inconsistent: - there's a p on the RHS of equation (2) but no p on the LHS of equation (3) - why? - in Section 3.3, there's both $\phi$ and $\phi_e$ seemingly inconsistently - more related questions below

Questions

- The subscripts of $\textbf{P}$, the belief, seem a bit odd and not well-defined. Is $\textbf{P}$ a matrix? The subscript notation $_{w_i}$ seems especially odd/undefined. It would be good to make this more precise. - Is it correct that, once you know $\textbf{P}$, you can just read off $p(\textbf{w}|\textbf{P})$ directly from $\textbf{P}$? If so, it seems like $p(\textbf{w}|\textbf{P})$ obscures this. Is there an alternative way of writing that to make it more explicit, like $f_P(w)$? (I don't love that notation, either - but I suspect there's a way to make this clearer. What do you think?) - Is making the $\phi$ explicit in the notation accomplishing that much? My sense right now is that it's just obscuring the notation. Am I missing something? - $k_W$ , $k_Y$ -- "discrete choices" maybe needs a bit more explanation. It's unclear at first whether this is the number of choices *within* $W$ -- i.e., $|W|$ -- or how many choices are drawn from $W$. Maybe specifying $k_W$ in the example -- e.g., $k_W = 2$ in the example -- would be helpful. Same for $k_Y$. Also, maybe this is the right place to introduce the notation $w_i$ for $i \in \{1,\dots,k_W\}$ and specify the spaces that $w_i$ and $y_i$ live in. If for some reason giving these space symbols is not needed or unnecessarily complicated, could you please explain? It seems more grounded to give them symbols. - nit: should equation (5) have an indicator? (dropping it feels a bit too informal) - The symbolic pruner notation feels off to me. Is there a separate $s$ for each $i$? Do $q,s$ depend on $i$ in $q \cdot s$? It seems like it should based on $s = s_i(\cdot)$, but it seems like it shouldn't if they're vectors (i.e., what are the dimensions of $s,q$?). - Is $s_i$ given or learned? - "In our studied tasks, neural prediction cannot perform better than symbolic prediction." But sudoku shows slightly better neural prediction than symbolic prediction. It would be good to comment on this.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The authors do a nice job outlining various limitations of this work. I found the presentation honest and straightforward.

Summary

The paper presents a polynomial time solution to the approximate neurosymbolic inference problem for probabilistic neurosymbolic learning problems. The approach is based on a variant of predictive processing, with a prediction model and an explanation model. The results are interesting, and successfully solve three different non-trivial challenge problems: MNISTAdd, Visual Sudoku, and Warcraft Visual Path Planning.

Strengths

+ The paper is an interesting attempt at bringing predictive processing concepts to neuro symbolic reasoning using probabilistic programs. + The idea of output space factorization is useful, as it helps reduce the complexity of the problem. However, it seems that humane effort may be needed to decompose the output in a helpful manner. + The design of belief priors using high-entropy Dirichlet distributions to cover all possible input scenarios or combinations of the factorized space is an interesting observation. + The pseudocode in Figure 2 is clear and makes the underlying algorithm more easily reproducible.

Weaknesses

- It is unclear how these experiments in controlled settings like MNISTAdd relate to robust neuro symbolic reasoning in more exciting tasks, like image classification or activity recognition. For example, factorization in such settings may not be easy. - The paper has no discussion about how this approach is related to predictive processing. Perhaps, a comparison would be helpful to the readers of the paper. - There are no bounds on the approximations being produced by this approach. How do the various design choices impact the quality of the approximation being obtained?

Questions

- Does this approach lead to an improved algorithm or heuristic for weighted model counting in general? Thanks for the response in the rebuttal.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The limitations listed in the paper are not clear. For example, it is noted that A-NESI did not perfectly train the prediction model in more challenging problems. It would be helpful to make this precise: what is the problem, what makes it challenging, and what was the quantitative performance of A-NESI? If it is one of the problems studied before, perhaps that section can be cited with an explanation. The responses from the authors are interesting. I have updated my score to reflect my view and understanding of the paper.

Summary

This paper introduces A-NeSi, a fast approximate procedure for NeSy architectures based on probabilistic logic. These architectures do not scale gracefully to problems involving many possible worlds, and the goal of A-NeSi is to scale them up. In short, A-NeSi employs a surrogate models (autoregressive neural nets) to replace the most computationally intensive steps. Experiments indicate a sizeable speed-up compared to SOTA probabilistic-logical approaches on a variety of tasks - from multidigit MNIST addition to pathfinding.

Strengths

+ Very clearly written. There's plenty of figures to build intuition, which is good. + Tackles a very prominent problem in neuro-symbolic AI - scalability of MAP inference for probabilistic-logical approaches, a major player in this field. + The idea of using surrogates is simple but very sensible. (What is not simple is ensuring the output satisfies the knowledge.) + All modeling choices are clearly motivated. + Empirical evaluation is both extensive and very promising. + Related work is both compact and comprehensive, well done.

Weaknesses

No major deficiencies that I could find. This is a solid contribution.

Questions

Q1. How strongly does performance of A-NeSi depend on the complexity of the hard constraints/knowledge? Especially when knowledge encodes long-range interactions between variables (or, if you prefer, tree width). I would imagine beam search could choke up in these cases, and I'd appreciate some discussion on the expected behavior.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Limitations are clearly discussed in the conclusion.

Reply

Thanks for answering my question. I would appreciate if the authors could mention their observations re. long-range interactions and low entropy/beam search performance in the paper. I remain of the opinion that this work is well worth accepting.

Reply

Thank you for clarifying my concerns. However, I am still struggling to fully understand the motivation behind the prediction model. I know that $\mathbf{w}$ is sampled from $p(\mathbf{w} | \mathbf{P})$, and that evaluating $c(\mathbf{w})$ is often fast. However, finding a sample $\mathbf{w}$ that satisfies $c(\mathbf{w}) = \mathbf{y}$ can be difficult due to sparsity [1], and I think this is the main efficiency bottleneck. Could the authors elaborate more about how to address this sparsity issue? [1] Li, Q., Huang, S., Hong, Y., Chen, Y., Wu, Y. N., & Zhu, S. C. (2020, November). Closed loop neural-symbolic learning via integrating neural perception, grammar parsing, and symbolic reasoning.