  We study the problem of combining neural networks with symbolic reasoning.
Recently introduced frameworks for Probabilistic Neurosymbolic Learning (PNL),
such as DeepProbLog, perform exponential-time exact inference, limiting the
scalability of PNL solutions. We introduce Approximate Neurosymbolic Inference
(A-NeSI): a new framework for PNL that uses neural networks for scalable
approximate inference. A-NeSI 1) performs approximate inference in polynomial
time without changing the semantics of probabilistic logics; 2) is trained
using data generated by the background knowledge; 3) can generate symbolic
explanations of predictions; and 4) can guarantee the satisfaction of logical
constraints at test time, which is vital in safety-critical applications. Our
experiments show that A-NeSI is the first end-to-end method to solve three
neurosymbolic tasks with exponential combinatorial scaling. Finally, our
experiments show that A-NeSI achieves explainability and safety without a
penalty in performance.
