Semantic Probabilistic Layers for Neuro-Symbolic Learning
Authors: Kareem Ahmed
Stefano Teso
Kai-Wei Chang
Guy Van den Broeck
Antonio Vergari
Venue: NeurIPS 2022 Accept (2022)
Keywords: neuro-symbolic learning
structured-output prediction
structured-output spaces
tractable probabilistic inference
probabilistic reasoning

Abstract: We design a predictive layer for structured-output prediction (SOP) that can be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over a structured output space all while being amenable to end-to-end learning via maximum likelihood.
SPLs combine exact probabilistic inference with logical reasoning in a clean and modular way, learning complex distributions and restricting their support to solutions of the constraint. As such, they can faithfully, and efficiently, model complex SOP tasks beyond the reach of alternative neuro-symbolic approaches. We empirically demonstrate that SPLs outperform these competitors in terms of accuracy on challenging SOP tasks such as hierarchical multi-label classification, pathfinding and preference learning, while retaining perfect constraint satisfaction.

Semantic Probabilistic Layers for Neuro-Symbolic Learning
Kareem Ahmed CS Department
Stefano Teso CIMeC and DISI University of Trento stefano.. tew.@unitn..i
Kai- Wei Chang CS Department UCLA kwchang@cs www..ccacc.coo........... aucla.edu edu
UCLA ahmedk@cs.c acla..edu
Guy Van den Broeck
Antonio Vergari
CS Department
School of Informatics
UCLA guyvdbêcs www..clllaeooooo edu
University of Edinburgh
avergarieen @@dd. ac.uk
Abstract
We design predictive layer for structured-outpic prediction (SOP) that be plugged into any neural network guaranteeing its predictions are consistent with a set of predefined symbolic constraints. Our Semantic Probabilistic Layer (SPL) can model intricate correlations, and hard constraints, over structured output space all while being amenable end-to-end learning via maximum likelihood. SPLs combine exact probabilistic inference with logical reasoning in a clean and modular way, learning complex distributions and restricting their support solutions of the constraint. As such, they can faithfully, and efficiently, model complex SOP tasks beyond the reach of alternative neuro-symbolic approaches. We empirically demonstrate that SPLs outperform these competitors in terms accuracy on challenging SOP tasks including hierarchical multi-label classification, pathfinding and preference learning, while retaining perfect constraint satisfaction. Our code made publicly available Github atthub.com/Kareee Yousrii/SPL.
Introduction
Modularity is among the major factors that propelled the Cambrian explosion of deep learning [35]. By stacking multiple differentiable layers together, practitioners are able to train deep classifiers in an end-to-end fashion with little effort. However, despite its flexibility, this modular approach to learning does not guarantee that the predictions of these models conform to our expectations of what makes sense. On the contrary, unconstrained deep classifiers notorious for leading to predictions that are inconsistent with the logical constraints governing an underlying domain.
This is even more evident in, and crucial for, structured output prediction (SOP) tasks, where classifiers have to predict hundreds mutually constrained labels [73, 8]. Consider for example a classical SOP task such as multi-label classification (MLC) [74]. Learning multi-label classifier that disregards the correlations among labels, e.g., by considering them fully independent given the inputs, yields sub-optimal results [6]. In more challenging tasks such hierarchical MLC (HMLC) [71] pathfinding [60], leveraging the domain's logical constraints (encoding, e.g., the label hierarchy or acyclicity and connectedness of path) at training time improve prediction accuracy [44], but it cannot guarantee that the predictions are always consistent with the constraints at inference time [32]. Fig. illustrates this problem in the context of pathfinding: constraint-unaware neural networks systematically fail to predict label configurations that form a valid path. In many safety-critical
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

GROUND TRUTH
RESNET- 18
SEMANTIC LOSS
SPL (ours)
Neural nets struggle with satisfying validity constraints in complex semantic SOP tasks such as predicting the lowest-cost path from the top-left to the bottom-right corners of a Warcraft map. Even ofte-offtthe-ar neuro-symbolic approaches like the Semantic Loss [80] fail to ensure consistency with hard rules (c). SPLs in contrast guarantees validity while retaining modularity, expressiveness and efficiency. See Sec. 5 for complete experimental details and additional results.
Figure 1:
scenarios such as protein function [63] and interaction prediction [65], and drug discovery [20, 24], predicting inconsistent solutions can not only be harmful but also highly expensive [5, 34].
Unsurprisingly, due to their discrete nature, injecting logical constraints into deep neural networks while retaining modularity and differentiability is extremely challenging, as demonstrated in the neuro- symbolic learning literature [66]. One such attempt has been learn neural networks that satisfy the logical constraints by explicitly minimizing a differentiable loss term encoding the probability that the networks violates the constraint for given prediction. And while successful, such approaches do not guarantee consistency of the predictions at test time. More recently, researchers have proposed predictive layers that do guarantee consistency, but these are restricted to specific kinds of symbolic knowledge [32, 70] or become intractable for even moderately complex logical constraints [38].
Motivated by these observations, we introduce a novel Semantic Probabilistic Layer (SPL) for modeling intricate correlations, and logical constraints on the labels of the output space a modular and probabilistically sound manner. It does by leveraging recent advancements in the literature probabilistic circuits [76, 13]. The key features of SPL are that, on the one hand, it can used as a drop-in in replacement for common predictive layers of deep nets like sigmoid layers, and the other, guarantees the output's 's consistency with any prespecified logical constraints. Importantly, SPL. also supports efficient inference and perhaps surprisingly does not complicate training.
Contributions.
Summarizing, we: (i) Identify six desiderata that neuro-symbolic predictors ought to satisfy to flexibly and reliably support real-world SOP tasks, and show that state-of-the-ar approaches fall short of one more of them (Table 1); (ii) Introduce SPI., novel semantic probabilistic layer that leverages probabilistic circuits to satisfy all six desiderata, i.c., that can be plugged into neural networks ensure predictions to comply retaining efficiency, expressivity, differentiability. and fully probabilistic semantics; (iii) We provide empirical evidence of the effectiveness of SPL in several challenging neuro-symbon such as HMLC and pathfinding, where it outperforms state-of-the the-tht-rtt art neuro- syrbb-yymblic approaches, often by noticeable margin. We implemented SPLs in PyTorch [54], and our code made publicly available on Github at Cacbuu.com/Kareeee Yousrii/PPL.
given logical constraints, while
SOP tasks,
2 Designing a probabilistic layer for neuro-symbolic SOP
Notation. In the following, we denote scalar constants x in lower case, random variables X in upper case, vectors of constants in bold and vectors of random variables X in capital boldface.
1 1(p) denotes the indicator function that evaluates to the statement holds and to 0 otherwise. We denote by + K that the value assignment æ: to variables X satisfies logical formula K.
Neuro-symbolic SOP. instances x E R.D to T. interdependent labels, identified by the vector E (0, 1 We assume that we can abstract any neural classifier into two components: feature extractor f that maps inputs X to -ddimensional embedding Z f(X) and a predictive final layer that outputs the label distribution p( Y Z). For example, the simplest, and yet widely adopted [51, 80, 32], predictive layer in neural classifiers for SOP considers labels Y, to be conditionally independent from each other given Z, i.c., p(Y Y Z) II p(Y, Z). We refer to this as fully independent layer (FIL). In FIL.
We tackle SOP tasks in which neural net classifier must learn to associate

---

X Table 1: SPL is the only approach to satisfy all the desiderata for neuro-symbolic SOP. An in-depth discussion of all competitors can found in Sec. 4.
LOSSES
LAYERS
DESIDERATUM
DL2 [29] SL [80] NESYENT [3] FIL EBM [43] MULTIPLEXNET [38] CCN [33] SPL (ours)
(DI) Probahilistic
X
/
X
(D22) Expressive
X
/
/
(D3) Consistent
X
X
XX
x
/
/
(D4) General
/
/
(D5) Modular
/
J
/
(D6) Efficient
/
V
X
pY; = Vi 2)) is computed as o (w.
T 2) where w, R.M vector of parameters and a (xx) the logistic sigmoid function 1/(1 + e)
We are interested in dependencies between labels that can occur both as correlations, as is the case in MLC [22], and as logical constraints encoded by logical formulas. For example, in a HMLC task [32] one logical constraint can encode the fact that observing label for the class cat and dog, implies observing the label for their superclass animal
(Yat =
Yanimal 1) A (Ydog =
Yanimal 1).
Specifically, assume symbolic knowledge to be supplied in the form of constraints encoded as a logical formula denoted as K and defined over the labels Y and optionally over a subset of the discrete input variables in X. if any (e.g., in experiments, the predicted simple path is constrained to lie within the subset of edges appearing the input graph, see Sec. 5). On the other hand, we expect model to learn the label correlations from data. We call such task neuro-symbolic SOP.
Desiderata for neuro-symbolic SOP. To tackle this setting, we seek an algorithmic strategy for replacing the predictive layer in any neural network classifier with little effort, with the aim of injecting complex symbolic knowledge and allowing for flexible probabilistic reasoning. We formalize these observations into the following six desiderata for our predictive layer:
D1. Probabilistic:
The layer should enjoy sound probabilistic semantics, and deliver normalized probabilistic predictions to facilitate maximun-likelihon learning and sound decision making by virtue of calibrated probabilistic predictions
D2. Expressive: It should be able to compactly encode intricate correlations between labels.
D3. Consistent: It should always output predictions that are consistent with the prespecified symbolic knowledge, i.e., for all and y. if (z, y) ofr K then p(y x)) 0.
D4. General: It should support rich logical constraints over the labels expressed in some formal language, e-g.. propositional logic.
D5. Modular: It should be applicable to any off-the-shelf (and possibly pretrained) neural network in a modular fashion, enabling end-to-end learning and rapid prototyping.
D6. Efficient: The time required by the predictor to compute prediction should be linear in the size of the predictor and of the hard constraint representation.
For example, FIL. clearly probabilistic (D1), modular (D5), and efficient (D6), but at the cost of being incapable of modeling intricate correlations and logical constraints and thus generating inconsistent predictions (D2-D4) (see also Fig. 1). Table summarizes how the other popular and effective approaches to neuro-symbolic SOP nowadays fall short of one of more desiderata as well. We discuss this in detail in Sec. 4. To the best of our knowledge, our proposed semantic probabilistic layers (SPLs) are the first algorithmic solution to satisfy all above desiderata.
SPL. At a high level, SPI. realizes the above desiderata in a single layer that combines exact proba- bilistic inference with logical reasoning clean and modular way, learning complex distributions and restricting their support to solutions of the constraint.
Definition 2.1 (Semantic probabilistic layer (SPL)). Given an input configuration æ, a SPL decom- poses the computation of the probability of label configuration
ply f())) ( f(x)) on 9)/ (ax)
where
Z(x) E, go ()) v). (2)
3

---

x
Pla x)
ply
2.
9 4
X
re.
B
piy x]
X
y
SPL
Figure 2: A high level view of SPLs. The predictive layer of a neural network for neuro-symbolic SOP, e.g., FIL (left), can be readily replaced by SPL (middle). SPLs are implemented (right) by multiplying together a probabilistic circuit qe ye(Y (Y) f(X)) parameterized by (a function g of) the network's s embeddings s(X). and a constraint circuit ox (X, Y) embodying the symbolic knowledge. The result is normalized by efficiently marginalizing over the product circuit re.k. so as to guarantee fully probabilistic semantics and end-to-end differentiable learning by maximum likelihood.
Here, ( | fz)) is a module to perform probabilistic reasoning by encoding an expressive distribution over the labels parameterized by θ (x, y) is a module to ensure consistency of the predictions by encoding logical constraints K and being non-zero only when K is satisfied, i.c.. y) = (x; y) = KJ; and ((x) is a renormalization term, also called the partition function. It worth noting that this amounts taking a product of experts [37] which is, in general, hard.
Fig. 2 illustrates the computational graph of our SPL at training time. In order to satisfy all D1-D6, we will realize both ge and CK as circuits [76, 13], constrained computational graphs that enable tractable computations. Differently from FILs, qe in SPLs can encode an expressive joint distributions over the labels and therefore attain full expressiveness by scaling the number of parameters O (D2). Consistency is guaranteed by the component ok: by multiplying it to the joint probability of label configuration the resulting product distribution re, (y æ) ge (y (x)) (x, y) will have its support effectively cut by K, and thus cannot allocate any probability mass inconsistent predictions (D3). Additionally, ok will allow to encode general propositional logical constraints in compact computational graph (D4). Lastly, the product re,k K (æ: y) is fully differentiable and allows SPL to be an off-the-shelf replacement for other predictive layers (see Fig. 2) and enables end-to-end learning (D5). By renormalizing re. K (x, y) and outputting normalized probabilities, SPL enables the exact computation of gradients for θ which can therefore be trained by maximum likelihood (D1).
Thanks to recent advancements the literature on circuits, we can compute the partition function ((x) efficiently in time linear in the size of re.k. thus preserving efficiency (D6) and not com- promising on the other desiderata. This will also yield correct (and consistent) predictions at test time, when an SPL computes the MAP state y" = argmax, K ky x)/ Σ, re.k(y. y, æ). The next section clarifies how to implement the modules of SPL as circuits while satisfying these desiderata.
3 Realizing SPLs with tractable circuit representations
The components of SPLs are circuits, a large class of computational graphs that can represent both functions and distributions [13, 18J. Circuits subsume many tractable generative and discriminative probabilistic models-from Chow-Liu and latent tree models [14, 11], to hidden Markov models (HMMs) [62], sum-produce networks (SPNs) [61], decision trees [41, 15], and deep regressors [40]- well many compact representations of logical formulas, such as (ordered) binary decision diagrams [4], sentential decision diagrams (SDDs) [17] and others [18].
The key idea behind SPLs is to leverage this single formalism to represent both an expressive joint distribution for ge (y fx)) and compact encoding of the logical constraints for (x, y), while ensuring the exact and efficient evaluation of Eq. (2). This can be achieved by ensuring that these computational graphs abide certain structural properties: smoothness, decompovabiliiy. determinism and computibility [18, 75]. Next, we introduce probabilistic circuits for modeling ye (Sec. 3.1) and constraint circuits for ok (Sec. 3.2), while in Sec. 3.4 we propose a more efficient implementation of SPL utilizing single circuit.

---

31%
TE%
KEG 1
q
Figure 3: Examples of circuits in SPL. Left: a neural conditional probabilistic circuit ge. Red lines indicate how the output of parameterizes the imput distribution parameters À and the sum unit parameters wa q. both indicated as red dots. Right: constraint eircuit encoding the logical constraint of Eq. (1) where labels are Y; E (Yeat, Ydog: Yanimal). Note that g and c are smooth, decomposable (Def. 3.3) and compatible (Def. 3.7) and e deterministic (Def. 3.6). By parameterizing e via g we can obtain single-cireuit SPL (Sec. 3.4). Both: circuits q and e are compatible, as product units with the same scope decompose in the same way. E.g., consider the first two product units of y and c, right to left and top to bottom. Both units decompose (Ys, Y2, Y1 into Y3 and Y2, Yi.
3.1 Representing expressive distributions with probabilistic circuits
We start by introducing circuits for joint probability distributions, and then extend the discussion to conditional distributions, which we use to implement qe Y f(X)) in SPLs.
Definition 3.1 (Circuits). circuit h over variables Y is a computational graph encoding a pa- rameterized function (Y) by combining three kinds of computational units: input functional units, sum units, and product units. An input functional n represents a base parametric function hn (sc(n): X) over some variables sc(n) C Y, called its scope, and it is parameterized by A. Sum and product units n elaborate the output of other units, denoted in(n). Sum units are parameterized by w and compute the weighted sum of their inputs Decin(n) (sh)(s while product units compute ]ecin(n)) he (s))) The parameters O circuit encompass the parameters of all input functionals (A) and the parameters of sum units (w).
For any input y. the value of (y) can be evaluated by propagating the output of the input units through the computational graph and reading out the value of the last unit. The support of h is the set of all states y of Y for which the output is non-zero, i.e., supp(h) = { h(y) + 40).
Definition 3.2 (Probabilistic circuits (PCs)). circuit ş is if encodes a (possibly unnormalized)
probability distribution, i.e., ge (y) is non-negative for all configurations y of Y.
From here on, will assume PCs to have positive sum parameters and whose input units model valid distributions, c.g., Bernoullis, as these conditions are sufficient for satisfying Def. 3.2. Moreover, w.l.o.g. we will assume the and product units to be organized into alternating layers, and that every product unit n receives only two inputs C1, C22 i.e., qn (X) Je, (Y) Jo, (Y). These conditions easily be enforced in polynomial time [77, 78]. We are specifically interested in smooth and decomposable PCs, as they will be enabling efficient inference in SPL (Sec. 3.3).
Definition 3.3 (Smoothness & Decomposability). A circuit is smooth if for every sum unit n, its inputs depend on the same variables: C1, C2 E in(n).sc(c.) every product unit depend on disjoint sets of variables: in(n)) {ci, 02), sc(ci) ) O sc((c2) 0.
sc(c)) sc(c2). It is decomposable the inputs of
Smooth and decomposable PCs are both expressive and efficient: they can encode distributions with hundred millions of parameters and be effectively learned by gradient ascent [58]. The structure of their computational graph can be either specified manually [61, 58, 56] or acquired automatically from data [77, 64, 16), e.g., by first learning a latent tree model and then compiling the latter into circuit [46]. These circuits are competitive with intractable models such as variational autoencoders and normalizing flows scores on several benchmarks [45].
As proposed by Shao et al. [68], any (smooth and decomposable) PC ge (Y) encoding joint distribution over the labels Y can be turned into (smooth and decomposable) conditional circuit, conditioned by input variables X, by letting its parameters be a function of X.
Definition 3.4 (Neural conditional circuits [67]). A conditional circuit (Y; θ gx))) models the conditional distribution p(Y) X) via a differentiable function that maps every input configuration to the set of parameters of e of p. also called the gating function.
5

---

An example of a smooth and decomposable conditional circuit is shown in Fig. 3. This design immediately allows us implement qe f(X) in SPL as a conditional PC whose gating function
maps the feature embedding space IK to the parameter space R! realizing q(Y; O = (x)).. As such, the gating function g creates a clean interface between any pre-trained feature extractor I' and the PC y (Fig. 3). While one can devise in several ways, we strive for simplicity in our experiments and adopt vanilla multi-layer perceptrons (MLPs) whose final activations are either sigmoids, if they have to predict the parameters X of the Bernoulli input distributions of g, or softmax, they output the sum unit parameters w (Def. 3.1).
3.2 Encoding logical formulas with constraint circuits
The next step is to translate a logical constraint K into smooth and decomposable circuit cx( y). To this end, we employ a special type of PCs, defined as follows.
Definition 3.5 (Constraint circuits). A PC over variables X U Y is a constraint circuit encoding prior knowledge if it computes 1 (ax y) + K} for every configuration (ar, y).
As a practical way to realize such a circuit, we will consider constraint circuits that have all sum unit parameters equal to I and input functionals that are indicator functions over their scope, c.g.. en (z) = 1 -= ((n)} where Z is the scope of the input and (n()) a constraint over it. Furthermore, we require each sum unit in it to be deterministic.
Definition 3.6 (Determinism). A sum unit n is deterministic if its inputs have disjoint supports, i.e., VC,. C2 E in(n), c1 + C2 = supp(ci) n supp(e2)) = 0.
Fig. 3 shows an example of a deterministic constraint circuit. Thanks to determinism, we can readily translate classical compact representations for logical formulas such as (ordered) binary decision diagrams [4, 9] and sentential decision diagrams (SDDs) [17] into constraint circuits as defined above. This becomes evident when they are written in the language of negation normal form [18] and their and gates (resp. gates) are replaced with product units (resp. sum units) [13]. A logic constraint can therefore represented as a constraint circuit for SPLs,, by utilizing any of the many tools
available for OBDDs [72] SDDs [10, 53]. Sec. B illustrates in detail how to compile the example constraint of Eq. (1) into the constraint circuit of Fig. in this way.
The worst-case size of the constraint circuit depends on a) the algorithm employed for compilation and, b) the local structure of the constraints, rather than the number of labels. For example, in our Warcraft experiment (see Sec. 5), we have a label configuration space over edges in a 12 x 12 grid, yielding 2 = 2 ss 1043 states. However, only 10 configurations satisfy the constraint that these edge labels form a valid path in the grid. If our compilation algorithm were to simply enumerate these configurations, putting them in a logical OR (as done in some neuro-symbolic learners such as MultiplexNet [38]) the size of the constraint circuit, denoted as |c], would be 10 However, by using recent advancements in compiling logical formulas into constraints circuits, reduce the circuit size. For example, compiler we use [1] generates circuits whose size is worst-case exponential in the treewidth of the CNF representation of the logical formula, but typically much smaller. See Sec. 5 and Sec. F for details.
can greatly
3.3 Efficient inference in SPLs
As discussed above, PCs can be expressive (D2) and are modular (D5), while constraint circuits ensure consistency (D3) for general constraints (D4). What remains to be shown to complete SPLs is that the product supports efficient normalization (D1) and inference (D6), specifically that allows for the efficient evaluation of the normalization constant of re.k. and its MAP state. To this end, we need to introduce the notion of compatibility between the two circuits [75].
Definition 3.7 (Compatible circuits in SPLs). A smooth and decomposabl conditional PC q( Y; +)
compatible over variables Y with a smooth and decomposable constraint circuit okl ck(Y (Y, X) if any pair of product units n E and m E OK with the same scope over Y can be rearranged to be mutually compatible and decompose in the same way: (sc(n) = sc(m)) = (sc(n,) sc(m,,, n, and m, are compatible) for some rearrangement of the inputs of n (resp. m) into n1, n2 (resp. m1, m2). The two circuits q and shown in Fig. 3 are compatible.

---

Table 2: SPLs outperform all loss-based competitors in the neuro-symbolic benchmarks of [80].
SIMPLE PATH
PREFERENCE LEARNING
ARCHITECTURE
EXACT HAMMING CONSISTENT
EXACT
llАМMING
CONSISTENT
MLP++II.
5.6
85.9
7.0
1.0
75.8
MLP+CCL
28.5
83.1
75.2
15.0
72.4
69.8
MLP+NESYENT
30.1
83,0
91.6
18.2
71.5
96.0
MLP+SPL. (ours)
37.6
88.5
100.0
20.8
72.4
100.0
Theorem 3.1 (Efficient inference in SPLs). IY; ) and ok
ck(Y (Y, X) are smooth, decomposable and compatible circuits, then computing Eq. (2) can be done in O(qql]e)) time. Furthermore, if they are also deterministic, then computing the MAP state can be done in O [e]) time.
The proof can be found in Sec. A. How do we come up with compatible circuits? One option is to have PC q that is compatible with every possible smooth and decomposable circuit c. To do so, we can represent y as mixtures of M fully-independent models; i.e., Σ wi II, <(y;; O.). This additional sum unit can be enough to be more expressive than a FIl. and already delivers more accurate predictions than any competitor, as our experiments in pathfinding show (Sec. 5). An example of such circuit is shown in Fig. 3, Another sufficient condition for compatibility is that both g and e share the exact same hierarchical scope partitioning [75], sometimes called a vtree or variable ordering [13, 59].
This can be done easily if one first compiles logical constraints into OBDDs or SDDs and then uses a mechanized algorithm to build 9 as in [58] to create a compatible structure. Additionally, to ensure a deterministic PC, we could exploit the mechanized construction proposed in Shih and Ermon [69]. Computing the exact MAP state, however, is of less concern approximate inference algorithms, e.g., beam search decoding [79] or iterative pruning [12]. are nowadays commodity deep learning frameworks. For non-deterministic PCs, we compute the MAP state with a faster approximation by replacing non-deterministic sum units with max units [55]. This runs in time linear in the size of and yet delivers state-of-the-an accuracies in our experiments Sec. 5.
3.4
A single-circuit SPL
The two-cireuit design we proposed for SPLs provides clear and theoreticalll-bbckel interface between neural networks and probabilistic and symbolic reasoning. This setup, however, can sometimes be wasteful, it requires to compute the product of two circuits and renormalize. We circumvent this issue by designing single-circuit implementation of SPL.
Definition 3.8 (Single-circuit SPL). Given input configuration
single-circuit SPL computes p(y x) = ck (Y, X2 = (X))) where CK is a neural conditional constraint circuit whose sum-unit parameters Ω are non-unitary values parameterized via gating function g-
In a nutshell, can directly realize SPL by compiling complex logical constraints (D4) into deterministic constraint circuit as before, and then parameterizing it with a gating function of the network embeddings f(X), i..., allowing its sum units to be non-unitary and input dependent. Since the support of сk is already restricted to exactly match the constraint K (D3), parameterizing Ω induces an expressive probability distribution over the label configurations that are consistent with K (D2). We can further guarantee that the circuit's 's output are normalized probabilities (D1, D6) by enforeing the parameters of each sum unit to form a convex combination [57]. This can easily done by utilizing a softmax activation function for g.
One of the advantages of the two-cireuit implementation of SPLs that the size of the circuit ge can be casily increased to improve the capacity of the model (Sec. 3.1). The single-circuit implementation
not flexible, normally the number of parameters determined by the complexity of the constraint circuit, which depends entirely on the compilation step. In this case, one option is to overparameterize the neural conditional eircuit by introducing additional sum units, hence allowing it to capture more modes in the distribution. We detail this process is Sec. C. A side that it relaxes determinism, meaning that MAP inference needs to
effect of overparameterization be approximated, as described in Sec. 3.3. Additionally, training a gating function to map relatively small embeddings to large parameter vectors in overparameterized circuits, can slow down training. In such cases, two-cireuit implementation of SPL is to be preferred.
7

---

4 Related works
In this section, we position SPLs against state-of-the-art approaches for enforcing constraints on neural network predictions. In-depth surveys on this topic can be found in [19] and [34].
Energy-based models. Deep energy-based models (EBMs) replace FILS with unnormalized factor graph [42] that captures higher-order label dependencies [43] (D2) but at the cost of foregoing probabilistic semanties (DI) and efficiency (D6). EBMs are typically unconcerned with hard con- straints (D3). Neural approaches for segmentation [47] and parsing [28, 82, 83] remedy to this by replacing the factor graph with full-fledged intractable (discriminative) graphical model [42]. To gain efficiency, one can restrict EBMs to simpler graphical models (c.g., chains, trees), compromising expressiveness (D2) and the ability model non-trivial logical constraints (D3, D4).
Loss-based methods. A prominent strategy consists of penalizing the network for producing incon- sistent predictions using an auxiliary loss [19, 34]. While popular, loss- bass-based methods, however cannot guarantee that the predictions will be consistent at test time. Common losses include translat- ing logical constraints into a differentiable fuzzy logic [25, 26], exemplified by DL2 [29]. Although efficient (D6), this solution is not probabilistically sound (D1) and crucially is not syntax-invariant: different encadings of the same formula (e.g., conjunctive vs. disjunctive normal form) yield different losses [31, 24]. Closer to our SPI,, the Semantic Loss (SI.) [80] avoids this issue by penalizing the the probability 02 associated to the i-th label by the neural network via the loss term
Lsl < Σ II O, II (1 - =- Σ II P(Y, Φ) = EI (Y::0)) (x(x,)). D
DFK
When K is compiled into a constraint circuit OK one retrieves - -(x) for a two-cireuit version of SPL that is expressive as FII it assumes independent labels via conditional PC II, (Y;;; The neuro-symbolic entropy (NESYENT) [3] extends by an entropy term that improves (but still does not guarantee) consistency. It still makes the same independence assumptions over labels (D2).
Consistency layers. Approaches ensuring consistency by embedding the constraints into the pre- dictive layer in SPLs include MultiplexNet [38] and HMCCN [32]. MultiplexNet is able to encode only constraints in disjunctive normal form, which is problematic for generality (D4) and efficiency (D6) seuro-symbooli SOP tasks involve intractably large number of clauses e.g. pathfinding experiments involves billions of clauses. HMCCN encodes label dependencies as fuzzy relaxation and is the current of-te----th--rr model for HMLC [32]. HMCCN and even its recent extension [33] are restricted to only certain constraints that can be exactly encoded with fuzzy logic easily. SPLs instead can express constraints encoded arbitrary propositional logical formulas (D4).
Other approaches. Other common approaches to neuro-symbolic SOP require to invoke a solver to either obtain the MAP state to compute (often only approximately) the gradient of the loss [23, 60, 52]. SPLs have no such requirement. Some neuro-symbolic approaches [66] constrain the outputs of neural networks within complex logical reasoning pipelines to solve tasks harder than neuro-symbolic SOP. For instance, DeepProblog [48] uses Prolog's ' backward chaining algorithm for first order logical rules whose probabilistic weights predicted by the network. In modern implementations of Problog, grounding a first order program and then compiling it into constraint circuits [27] produces conditional circuit akin those we use in SPLs, but in which (i) only input distributions parameterized and (ii) increasing the parameter count is not considered a straightforward operation. Scallop [39] provides more scalable approach to deepproblog by considering only the top-k proofs. We leave to future work how we could quickly compile only a specific query as DeepProblog/Scallo, do, deal with first-order representations efficiently.
5 Experiments
We evaluate SPLs on standard neuro-symbolic SOP benchmarks such as simple path prediction, preference learning [80], shortest path finding in Warcraft [60] and HMLC [32]. We compare SPLs against several state-of-the th--th--rtttttt art loss- and layer-based approaches (Sec. 4) by applying them to the same base neural network architecture as feature extractor f. As we are interested in measuring how close to the ground truth and how safe the predictions of all models are, we report the percentage of EXACT matches of the predicted labels, also called subset accuracy [74], and the percentage of CONSISTENT predictions, also called "Constraint" [80]. Note that, like other consistency layers,
8

---

Table 3: SPLs outperform competitors in pathfinding in Warcraft. Predicted paths that do not exactly match the ground truth are still valid paths and yield very close costs to the ground truth. Competitors' predictions can have higher Hamming scores but be invalid. More examples in Sec. D.3.
ARCHITECTURE
EXACT
HAMMING
CONSISTENT
ResNet-18+FIL
55.0
97.7
56.9
RESNET-18+Csi
59.4
97.7
61.2
RESNET-18+SPL (owrs)
78.2
96.3
100.0
GROUND TRUTH
FIL
SPL
SPLs are guaranteed to always output 100% consistent predictions. Additionally, we report the HAMMING score [74], mainly to maintain compatibility with previous experimental settings [80, 3].
This metric does not consider consistency of predictions and naturally favors competitors that assume label independence and thus can minimize the per-label cross- [22] (Table 3). Sec. D collects all experimental details such as architectures and hyperparameters used for each experiment.
In Sec. F we provide the average timings for compiling logical formulas into circuits- carried out once, and reused in all subsequent experiments, for parameterizing the conditional circuits, computing the MAP-state of SPL and the loss function at training time (including the cost of computing the product circuit r and its normalization). All these timings, compilation excluded, are reported per batch. We compare to the timings of baselines such as semantic loss and neuro-symbolic entropy. where applicable, to which SPL is highly competitive.
Simple path prediction & preference learning. We start by comparing SPLs against loss-based approaches, reproducing the neuro-symbolic benchmarks of Xu et al. [80] for simple path prediction and preference learning. In the first experiment, given source and destination node in an unweighted
grid G (V, E), the neural net needs to find the shortest unweighted path connecting them. We consider a 4 x 4 grid. The input (x, y) is a binary vector of length [V] + EE. with the first [V] variables indicating the source and destination nodes, and the subsequent |E variables indicating subgraph G" S G. Each label is a binary vector of length [E] encoding the unique shortest path in G'. For each example, we obtain G" by dropping one third of the edges in the graph G uniformly at random, filter out the connected components with fewer than 5 nodes, to reduce degenerate cases, and then sample source and destination node uniformly at random from G'. The dataset consists of 1600 such examples, with a 60/20/20 vrain/validationttee split.
In the preference learning task, given user's ranking over subset of items, the network has to predict the user's ranking over the remaining items. We encode an ordering over n items as a binary matrix Y.j. where for each i, E I,..., n. Y. indicates whether item i is the jth element in the ordering. The input æ consist of the user's preference over 6 sushi types, and the model has to predict the user's preferences (a strict total order) over the remaining 4. We use preference ranking data over 10 types of sushi for 5, 000 individuals, taken from [49], and a 60/20/20 split.
We employ 5-layer and 3-layer MLP as baseline for the simple path prediction, and prefer- ence learning, respectively, equipped with FIL layer and additionally with the Semantic Loss [80] (MLP+L5I) or its entropic extension [3] (MLP+NESYENT) We compile the logical constraints into an SDD [17] and then turn into a the same constraint circuit ck that is used for LSL, NESYENT (Sec. 4) and our 1-circuit implementation of SPL.s. Table 2 clearly shows that the increased expres- siveness of SPL, coming from overparameterizing OK. allows to outperform all competitors while guaranteeing consistent predictions, as expected.
Warcraft Shortest Path. Next, evaluate SPL the more challenging task of predicting the minimum cost path in a weighted 12 x 12 grid imposed over terrain maps of Warcraft II [60]. Each vertex is assigned cost corresponding the type of the underlying terrain (c.g., earth has lower cost than water). The minimum cost path between the top left and the bottom right vertices of the grid is encoded an indicator matrix, and serves as a label. As in [60] we use ResNet18 [36] with FIL optionally with LsL as a baseline. Given the largest size of the compiled constraint circuit CK in this case 10 we use a two-cireuit implementation of SPL. Results in Fig. and Table 3 are striking: not only SPL outperforms competitors by a large margin- approx. +23% over FIL and +19% over the SL- but also consistently delivers meaningful paths that are very close to the ground truth in terms of cost, even when they encode very different routes. See Sec. D.3 for gallery of these examples. Concerning times, SPLs are able to compute the likelihood a mere 14 seconds per batch even on a 10 valid configuration space (Sec. F).

---

Table 4: Comparison between SPI. and HMCNN [32] on twelve HMLC datasets averaged over 10 runs. Best results for each dataset are in bold. Results which are not significantly worse than the compe- tition, determined using paired Wilcoxon test, are marked in boldface. Consistency is always 100% for both approaches.
DALASET
EXACI MATCH
HAMMING SCORE
HMCNN
MLP-SPL
HMCNN
MLP-SPL
Cyera
3.05 0.11
3.79 + 0.18
0.00
97.84 0.06
DERIST
1.39 0.477
2.28 1 0.23
96.32 = 0.32
97.70 1: 0.07
BISEN
5.40 0.15
6.18 0.33
98.09
0.01
97.30 + 0.04
5.54
97.87 0.02
GAScHl
3.48 - 0.96
4.65 0.30
98.37
0.31
97.39
0.05
GASCH2
0.05
3.9520.22
98.27 = 0.00
97.94 4 0.07
SEQ
5.24 121::00
7.08 0.28
96.31 0.01
97.86 0.03
0.03
DIATOMS
48.21 - 0.67
58.
0.68
99.75 0.00
99.64 0.01
ESRON
5.97 0.55
8.18 0.68
94.10
0.04
93.19 1 0.13
IMCLERO7A
79.75
0.33
86.08
0.45
99.40 0.01
99.35 0.03
INCLEPOTO
76.47
0.35
0.68
98.07 0.08
Hierarchical Multi-Labe Classification. Lastly, we follow the experimental setup Giunchiglia and Lukasiewicz [32] and evaluate SPL on 12 real-world HMLC tasks spanning four different do- mains: functional genomics, 2 medical images, microalgea classification, and text categorization. Fig. 3 shows an example of hierarchy of classes. These tasks are especially challenging due to the limited number of training samples, the large number of output classes, ranging from 56 to 499, as well as the sparsity of the output space. The larger datasets yield a label space of 199 configurations, but we can compile them in seconds into compact constraints circuits of size R 108KB (Sec. F).
For numeric features we replaced missing values by their mean, and for categorical features by vector of zeros, and standardized all features. We used the validation splits to determine the number of layers in the gating function as well as the overparameterization keeping all other hyperparameters fixed. The final models were obtained by training using batch size of 128 and early stopping on the validation set. We compare our single-circuit SPL against HMCNN which was shown to outperform several other state-of-the-ar HMLC approaches in Giunchiglia and Lukasiewicz [32]. We study the effect of increasing the expressivenss of SPL via overparameterization in Sec. D.4. The results in Table 5 highlight that SPL significantly outperforms HMCNN terms of exact match on data sets performing comparably on 1,
Conclusion
SPLs offer the first clear interface for integrating complex probabilitistic reasoning and logical constraints on top of any neural network classifier while retaining efficient inference and training. They improve by a noticeable margin the current state-of-the-an on challenging neuro-symbolic SOP benchmarks such as pathfinding and HMLC. This opens up number of interesting research directions. First, SPLs can be extended to incorporate logical constraints over multiple networks and representable by first-order formulas [48], which we plan to explore in future works, making the circuit construction pipeline totally transparent to users [2] while possibly automatically learning constraints from data [21, 50). Second, are interested in leveraging SPLs to inject scalable logical constraints into large language models [7] thus equipping them with probabilistic reasoning [30, 81].
Acknowledgments and Disclosure of Funding
The authors would like to thank Arthur Choi for helpful discussions compiling the constraints for the Warcraft Shortest Path task, and Andreas Grivas for proofreading a draft manuscript. The research of ST was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under GA No 952215. This work was funded in part by the DARPA Pereeptually-enant Task Guidance (PTG) Program under contract number HR001 12220005,, NSF grants #IIS- 1943641, #115-1956441, 1837129,, Samsung, CISCO, and Sloan Fellowship.
References
[1] (2017). Pysdd. Recent Trends in Knowledge Compilation, Report from Dagstuhl Seminar 17381.
[2] Ahmed, K., Li, T., Ton, T. Guo, Q. Chang, K.-.., Kordjamshidi, P., Srikumar, V., Van den Broeck, G., and Singh, (2022a). Pylon: A pytorch framework for learning with constraints. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (Demo Track).
10

---

[3] Ahmed, K., Wang, E.. Chang, K.-W., and den Broeck, G. V. (2022b). Neuro-symbolic entropy regularization. In The 38th Conference on Uncertainty Artificial Intelligence.
[4] Akers, B. (1978). Binary decision diagrams. IEEE Transactions on computers, 27(06):509- 516.
[5] Amodei, D., Olah, C., Steinhardt, J., Christiano, P., Schulman, J., and Mané, D. (2016). Concrete problems in AI safety, arXiv preprint arXiv:1606.06533 06560.
[6] Bielza, C., Li, G., and Larranaga, P. (2011). Multi-dimensional classification with bayesian networks. International Journal of Approximate Reasoning, 52(6):705-727.
[7] Bommasani, R., Hudson, D. A., Adeli, E., Altman, R., Arora, S., von Arx, S.,, Bernstein, M. S., Bohg, J., Bosselut, A., Brunskill, E., et al. (2021). On the opportumities and risks of foundation models. arXiv preprint Stf:::2001.0255555
[8] Borchani, H., Varando, G., Bielza, C.,, and Larranaga, P. (2015). A survey multi-output regression. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 5(5):216 233.
[9] Bryant, R. E. and Meinel, C. (2002). Ordered binary decision diagrams. In Logic synthesis and verification, pages 285-307. Springer.
[10] Choi, A. and Darwiche, A. (2013). Dynamic minimization of sentential decision diagrams. In desJardins, M. and Littman, M. L., editors, Proceedings of the Ewenty-Seventy AAAI Conference on Artificial Intelligence, July 14-18, 2013, Bellevue, Washington, USA. AAAI Press.
[11] Choi, M. J., Tan, V. Y., Anandkumar, A., and Willsky, A. S. (2011). Learning latent tree graphical models. Journal of Machine Learning Research, 12:1771-1812.
[12] Choi, Y., Friedman, T., and Van den Broeck, G. (2022). Solving marginal map exactly by probabilistic circuit transformations. In International Conference on Artificial Intelligence and Statistics, pages 10196- 10208. PMLR.
[13] Choi, Y., Vergari, A., and Van den Broeck, G. (2020). Probabilistic circuits: A unifying framework for tractable probabilistic modeling.
[14] Chow, C. and Liu, C. (1968). Approximating discrete probability distributions with dependence trees. IEEE transactions on Information Theory, 14(3):462-467.
[15] Correia, A. H. C., Peharz, R., and de Campos, C. P. (2020). Joints in random forests. In NeurIPS.
[16] Dang, M., Vergari, A., and Van den Broeck, G. (2022). Strudel: A fast and accurate learner of structured-des deceuuedddecoompsabblee probabilistic circuits. International Journal of Approximate Reasoning, 140:92-115.
[17] Darwiche, A. (2011). SDD: A new canonical representation of propositional knowledge bases. In Twenty-Second International Joint Conference on Artificial Intelligence.
[18] Darwiche, A. and Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research. 17:229-264.
[19] Dash, T., Chitlangia, S.. Ahuja, A., and Srinivasan, (2022). A review of some techniques for inclusion of Hommiin-knowleee into deep neural networks. Scientific Reports, 12(1):1-15.
[20] De Cao, N. and Kipf, T. (2018). MolGAN: An implicit generative model for small molecular graphs. ICML 2018 workshop Theoretical Foundations and Applications of Deep Generative Models.
[21] De Raedt, L., Passerini, A., and Teso, S. (2018). Learning constraints from examples. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
[22] Dembezyíski, K., Waegeman, W., Cheng, W., and Hüllermeier, (2012). On label dependence and loss minimization in multi-label classification. Machine Learning, 88(1-2):5-45.
11

---

[23] Deshwal, A., Doppa, J. R., and Roth, D. (2019), Learning and inference for structured prediction: A unifying perspective. In Proceedings of the Twenty-Eightg International Joint Conference on Artificial Intelligence (IJCAI-19).
[24] Di Liello, L., Ardino, P. Gobbi, J., Morettin, P.. Teso, S., and Passerini, A. (2020). Efficient generation of structured objects with constrained adversarial networks. Advances neural information processing systems, 33: 43:11466344674
[25] Diligenti,, M., Gori, M., Maggini, M., and Rigutini, L. (2012). Bridging logic and kernel machines. Machine learning. 86(1):57-88.
[26] Diligenti, M., Gori, M., and Sacca, C. (2017). Semantic-based regularization for learning and inference. Artificial Intelligence, 244: 144-165-
[27] Dries, A., Kimmig, A., Meert, W., Renkens. J., Broeck, G. V. V.d., Vlasselaer, J., and Raedt, L, D. (2015). Problog2: Probabilistic logic programming. Joint european conference on machine learning and knowledge discovery in databases, pages 312-315. Springer.
[28] Durrett, G. and Klein, D. (2015). Neural CRF parsing. In Proceedings of the 53rd Annual Meet- ing of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, pages 302-312. The Association for Computer Linguistics.
[29] Fischer, M., Balunovic, M., Drachsler- Cohen, D., Gehr, T., Zhang, C., and Vechev, M. (2019). D12: Training and querying neural networks with logic. In International Conference Machine Learning, pages 1931-1941. PMLR.
[30] Geva, M., Gupta, A., and Berant, (2020). Injecting numerical reasoning skills into language models. arXiv preprint 200.4770
[31] Giannini, F., Diligenti, M., Gori, M., and Maggini, M. (2018). On convex logic fragment for learning and reasoning. IEEE Transactions on Fuzzy Systems, 27(7): 140--1416.
[32] Giunchiglia, E. and Lukasiewicz, T. (2020). Coherent hierarchical multi-label classification networks. Advances in Neural Information Processing Systems, 33:9662-9673.
[33] Giunchiglia, E. and Lukasiewicz, T. (2021). Multi-label classification neural networks with hard logical constraints. Journal of Artificial Intelligence Research, 72:759-818.
[34] Giunchiglia, E., Stoian, M. C., and Lukasiewicz, T. (2022). Deep learning with logical con- straints. arXiv preprint ar arXiv:2205.00522
[35] Goodfellow, I., Bengio, Y., and Courville, A. (2016). Deep learning. MIT press.
[36] He, K., Zhang, X., Ren, S., and Sun, J. (2016). Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778.
[37] Hinton, G. E. (1999). Products of experts. In Proceedings of the Ninth International Conference on Artificial Neural Networks.
[38] Hoernle, N., Karampatsis, R.-M., Belle, V., and Gal, Y. (2022). Multiplexnet: Towards fully satisfied logical constraints in neural networks. In AAAI.
[39] Huang, J., Li, Z., Chen, B., Samel, K., Naik, M., Song, L.,, and Si, X. (2021). Scallop: From probabilistic deductive databases to scalable differentiable reasoning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, W., editors, Advances Neural Information Processing Systems, volume 34, pages 25134-25145. Curran Associates, Inc
[40] Khosravi, P., Choi, Y., Liang, Y., Vergari, A., and Van den Broeck, G. (2019). On tractable computation of expected predictions. In Advances in Neural Information Processing Systems, pages 11169-11180.
[41] Khosravi, P., Vergari, A., Choi, Y., Liang, Y., and den Broeck, G. V. (2020). Handling missing data in decision trees: A probabilistic approach. In Proceedings of The Art of Learning with Missing Values, Workshop at ICML.
12

---

[42] Koller, D. and Friedman, N. (2009), Probabilistic graphical models: principles and techniques. MIT press.
[43] LeCun, Y., Chopra, S., Hadsell, R., Ranzato, M., and Huang, F. (2006). A tutorial on energy- based learning. Predicting structured data, 1(0).
[44] Levatić, J., Kocev, D., and Džeroski, S. (2015). The importance of the label hierarchy in hierarchical multi-label classification. Journal of Intelligent Information Systems, 45(2):247-271.
[45] Liu, A., Mandt, S., and Van den Broeck, G. (2022). Lossless compression with probabilistic circuits. International Conference of Learning Representations.
[46] Liu, A. and Van den Broeck, G. (2021). Tractable regularization of probabilistic circuits. Advances in Neural Information Processing Systems, 34.
[47] Liu, F., Lin, G., and Shen, C. (2015). Crf learning with cnn features for image segmentation. Pattern Recognition, 48(10))2983-299
[48] Manhaeve, R., Dumancic, S., Kimmig, A., Demeester, T., and De Raedt, I.. (2018). Deepproblog: Neural probabilistic logie programming. Advances in Neural Information Processing Systems, 31.
[49] Mattei, N. and Walsh, T. (2013). PrefLib: A library for preferences. In International conference on algorithmic decision theory, pages 259-270. Springer.
[50] Morettin, P., Kolb, S., Teso, S., and Passerini, A. (2020). Learning weighted model integration distributions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5224-5231.
[51] Mullenbach, J., Wiegreffe, S., Duke, J., Sun, J., and Eisenstein, J. (2018). Explainable prediction medical codes from clinical text. arXiv preprint arXiv.1802.05695.
[52] Niepert, M., Minervini, P., and Franceschi, L. (2021), Implicit MLE: Backpropagating through discrete exponential family distributions. Advances in Neural Information Processing Systems, 34.
[53] Oztok, U. and Darwiche, A. (2015). A top-down compiler for sentential decision diagrams. In Yang, Q. and Wooldridge, M. J., editors, Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pages 3 3141-3148. AAAI Press.
[54] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., Vito. Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., and Chintala, S. (2019). Pytorch: An imperative style, perfommerf deep learning library. In Wallach, H., Larochelle, H., Beygelzimer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
[55] Peharz, R., Gens, R., Pernkoff, F., and Domingos, P. (2016). On the latent variable interpretation in sum-product networks. IEEE transactions pattern analysis and machine intelligence, 39010):0030-2444
[56) Peharz, R., Lang, S., Vergari, A., Stelzner, K., Molina, A., Trapp, M., Broeck, G. V. d., Kersting, K., and Ghahramani, Z. (2020a). Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In International Conference of Machine Learning.
[57] Peharz, R., Tschiatschek. S., Pernkopf, F., and Domingos, P. (2015). On theoretical properties of sum-product networks. In Artificial Intelligence and Statistics, pages 744-752. PMLR.
[58] Peharz, R., Vergari, A., Stelzner, K., Molina, A., Shao. X., Trapp, M.. Kersting, K., and Ghahramani, Z. (2020b). Random sum-product networks: A simple and effective approach to probabilistic deep learning. In Uncertainty in Artificial Intelligence, pages 334-344 PMLR.
[59] Pipatsrisawat, K. and Darwiche, A. (2008). New compilation languages based on structured decomposability. In AAAI, volume 8, pages 517-522.
13

---

[60] Pogančić, M. V., Paulus, A., Musil, V., Martius, G., and Rolinek, M. (2019). Differentiation of blackbox combinatorial solvers. In International Conference on Learning Representations.
[61] Poon, H. and Domingos, P. (2011). Sum-product networks: A new deep architecture. In 2011 / IEEE International Conference Computer Vision Workshops (ICCV Workshops), pages 689-690. IEEE.
[62] Rabiner, L. and Juang, B. (1986). An introduction to hidden markov models, ieee assp magazine, 3(1):-16.
[63] Radivojac, P., Clark, W. T., Oron, T. R., Schnoes, A. M., Wittkop, T., Sokolov, A., Graim, K., Funk, C.. Verspoor, K., Ben-Hur, A., al. (2013). A large-scale evaluation of computational protein function prediction. Nature methods, 10(3):221227..
[64] Rahman, T., Kothalkar, P., and Gogate, V. (2014). Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Joint European conference on machine learning and knowledge discovery in databases, pages 630-644 645. Springer.
[65] Sacca, C., Teso, S., Diligenti, M., and Passerini, A. (2014). Improved multi-level protein-protee interaction prediction with semantic-based regularization. BMC bioinformatics, 15(1):1-18.
[66] Sarker, M. K., Zhou, L., Eberhart, A., and Hitzler, P. (2021). Neuro-symbolic artificial intelli- gence: Current trends. arXiv preprint arXiv:2105.05332
[67] Shao, X., Molina, A., Vergari, A., Stelzner, K., Peharz, R., Liebig, T., and Kersting, K. (2020). Conditional sum- nun-product networks: Imposing structure on deep probabilistic architectures. In International Conference on Probabilistic Graphical Models, pages 401 401-412. PMLR.
[68] Shao, X., Molina, A., Vergari, A., Stelzner, K., Peharz, R., Liebig, T., and Kersting, K. (2022). Conditional sum-product networks: Modular probabilistic circuits via gate functions. International Journal of Approximate Reasoning, 140:298-313.
[69] Shih, A. and Ermon, S. (2020). Probabilistic circuits for variational inference in discrete graphical models. Advances in Neural Information Processing Systems, 1444635-6445
[70] Sivaraman, A., Farnadi, G., Millstein, T., and Van den Broeck, G. (2020). Counterexample- guided learning of monotonic neural networks. Advances Neural Information Processing Systems, 33:1 1936-1198..
[71] Sorower, M. S. (2010). A literature survey on algorithms for multi-label learning. Oregon State University, Corvallis, 18:1-25.
[72] Toda, T. and Soh, T. (2016). Implementing efficient all solutions SAT solvers. ACM J. Exp- Algorithmics, 21())11.1:1-11112244
[73] Tsochantaridis, I., Hofmann, T., Joachims, T., and Altun, Y. (2004). Support vector machine learning for interdependent and structured output spaces. In Proceedings of the twenty-first international conference Machine learning, page 104.
[74] Tsoumakas, G. and Katakis, I. (2007). Multi-label classification: An overview. International Journal of Data Warehousing and Mining (IJDWM), 3-3):1-13.
[75] Vergari, A., Choi, Y., Liu, A., Teso, S., and Van den Broeck, G. (2021). A compositional atlas of tractable circuit operations for probabilistic inference. Advances in Neural Information Processing Systems, 34.
[76] Vergari, A., Choi, Y., Peharz, R., and Van den Broeck, G. (2020). Probabilistic circuits: Representations, inference, learning and applications. In Tutorial at the The 34th AAAI Conference on Artificial Intelligence.
[77] Vergari, A., Di Mauro, N., and Esposito, F. (2015). Simplifying, regularizing and strengthening sum-product network structure learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 343-358. Springer.
14

---

[78] Vergari, A., Di Mauro, N., and Esposito, F. (2019). Visualizing and understanding sum- cum-product networks. Machine Learning. 108(4):551-573.
[79] Vijayakumar, A. K., Cogswell, M., Selvaraju, R. R., Sun, Q., Lee, S., Crandall, D., and Batra, D. (2016). Diverse beam search: Decoding diverse solutions from neural sequence models. arXiv preprini 1610v0261..02444
[80] Xu, J., Zhang, Z.., Friedman, T., Liang, Y., and Van den Broeck, G. (2018). semantic loss function for deep learning with symbolic knowledge. In International conference machine learning, pages 5502-5511, PMLR.
[81] Zhang, X., Bosselut, A., Yasunaga, M., Ren, H., Liang, P., Manning, C. D., and Leskovee, J. (2021). Greaselm: Graph reasoning enhanced language models. In International Conference Learning Representations.
[82] Zhang, Y., Li, Z., and Zhang, M. (2020a). Efficient Second-Ordes TreeCRF for Neural Depen- dency Parsing. In Jurafsky, D.., Chai, J., Schluter, N., and Tetreault, J. R., editors, Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL. 2020, Online, July 5-10, 2020, pages 3295-3305, Association for Computational Linguisties.
[83] Zhang, Y., Zhou, H., and Li, Z. (2020b). Fast and accurate neural CRF constituency parsing. In Bessiere, C., editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages 4046-4055.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Please see section for summary of our contributions
(b) Did you describe the limitations of your work? [Yes] Please see Supplementary
(c) Did you discuss any potential negative societal impacts your work? [Yes] Please see Supplementary
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either the supplemental material or as a URL)? [Yes] Please see supplementary material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please see section for details regarding the dataset splits. All other details are included in the supplementary.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] We reported error bars and significance testing for the hierarchical multi-label classification experiment, please see
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Please supplementary material
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
15

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
16


Reviews:
[{"review_id": "wlfhbrj-jgO", "reviewer": "Reviewer_KRqF", "summary": "This study proposed a differentiable Semantic Probabilistic Layer (SPL) for structure prediction problems. The SPL can be used together with any off-the-shelf neural networks to model conditional distributions p(y|x) where there is additional hard constraints imposed on y. Since the SPL is built upon smooth and decomposable probabilistic circuits, it can be used to compute the probability p(y|x) efficiently in linear time. Such property enables the maximum-likelihood learning of the model parameters. The SPL is empirically demonstrated to outperform its alternatives (mainly semantic loss methods) on several structure prediction benchmarks.", "questions": "See *Weaknesses* section for questions.", "limitations": "See *Weaknesses* section for limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThis paper provided a **generic** and **novel** solution to bridge between neural networks and structure prediction problems. The proposed SPLs can be used to model conditional distributions p(y|x) with logical constraints imposed on y. Backed by smooth and decomposable probabilistic circuits, these SPLs can be used to do exact inference **efficiently**, which enables maximum-likelihood learning over model parameters. The paper provided **theoretical guarantees** for the proposed SPLs and empirically justified them by showing their superior performance over existing methods with semantic loss. \n\nWeaknesses:\n\nThe paper is not very self-contained, and it is hard to follow by readers without the background of probabilistic circuits (PCs). In particular the writing of the paper can be improved in the following places:\n- \"gating function\" used without defined in Definition 3.4. Is it similar to the gating functions in RNNs? Why would we want such functions here?\n- \"... if any pair of product units n\\in p and m\\in m ...\" in Definition 3.7. What is p and m here? How to intuitively understand the compatibility defined here?\n- Figure 3 is very difficult to comprehend without furture explanation. What are the inputs and outputs of each unit? What do the red lines refer to? What are the meanings of the conjuctions between the red lines and the black lines? Why are these two circuits compatible?\n\nThe computation of the partition function Z(x) in Equation (2) seems to be a time-consuming process. For a different y, we need to compute its c_K(x, y) and use it to weight q_\\theta(y | f(x)). This suggest that we need to enumerate over all possible ys in order to compute the normalization term. However, line 122 suggests that we can compute Z(x) in time linea in the size of r_\\theta,K. Correct me if I am wrong, if y \\in {0,1}^d, isn't that |r_\\theta,K| = O(2^d)? Can we still claim that this is efficient?\n\nRegarding the evaluation, the size of the experiment somehow suggests that the proposed approach is not very scalable (e,g, 4x4 path finding experiments). The HMLC experiment seems to be an experiment with decent difficulty, but the baselines are not comprehensive. It could provide a stronger evidence if the authors can compare their method with more methods listed in Table 1 in the experiments.\n\nSuggestions for larger scale evaluation tasks with hard constraints:\n1. Sudoku experiment in SATnet[1].\n2. Common sense VQA experiment in Scallop[2].\n3. RNA Secondary Structure Prediction experiment[3].\n\nIn particular, Scallop[2] is a related work which makes deepproblog more scalable.\n\n\n[1] Wang, Po-Wei, et al. \"Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver.\" International Conference on Machine Learning. PMLR, 2019.\n\n[2] Huang, Jiani, et al. \"Scallop: From probabilistic deductive databases to scalable differentiable reasoning.\" Advances in Neural Information Processing Systems 34 (2021): 25134-25145.\n\n[3] Chen, Xinshi, et al. \"RNA Secondary Structure Prediction By Learning Unrolled Algorithms.\" International Conference on Learning Representations. 2019.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0Oh9skogmbN", "reviewer": "Reviewer_V2bR", "summary": "This paper targets the problem of neural models trained with logical constraints, while performing well in downstream tasks, still lack of proper interface to put hard constraint such that outputs are strictly consistent. To this end, this paper puts a list of 6 ideal necessities for a constrained neural models and proposed semantic probabilistic layer (SPL) that does efficient training and inference. Experiment results span across synthetic tasks and realistic ones, showing strong task performances while guarantee output space structural consistency.", "questions": "1. What is the take on the metric of Hamming score. Is this paper suggesting it is a rough metric that does not reflect structural recall of the ground truth and should be avoided in future?", "limitations": "I do not see big limitation that could offset the contributions of this work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. A theoretical discussion on ideal necessities for constrained neural models.\n\n2. Naturally SPL is a marginal inference layer that is capable of differentiable learning and outputing perfectly consistent structure. The convesion to circuits can be a general add-on to many other tasks. This could give broad impact. Being able to guarantee output consistency in a general way is a big bonus. \n\n3. Extensive datapoints in experiment show a reliable observation on strong performances on exact path matching.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "0G_xavoYrvY", "reviewer": "Reviewer_o1Rk", "summary": "The paper introduces the semantic probabilistic layer (SPL), a replacement for the predictive layer of neural networks that is composed of probabilistic circuits and ensures the outputs satisfy given logical constraints. Then it is shown that the layer satisfies more desires than the competitors. Finally, SPLs are evaluated on simple path prediction, preference learning, shortest path finding, and hierarchical multi-label classification.", "questions": "Nothing to comment.", "limitations": "Nothing to report.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is really well written and the results are clearly presented. Despite that I don’t have a background on probabilistic circuits, I can still enjoy reading the paper.\n\nThe claims on the paper are well-supported through discussions and experimental sections. The authors compare SPL to the state-of-the-art methods through extensive experiments. So overall, I think the result is solid.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0-RpBn-D99U", "reviewer": "Reviewer_MBwP", "summary": "This paper presents a method for structured-output prediction that allows for encoding of hard constraints, and learning of soft constraints. Specifically, the distribution p(y|f(x)) is explicitly modelled as a product, where one term of the product is parameterized by a neural network, and the other term is set to 0 when the label configuration fails the hard constraints. To make predictions tractable, circuits are used. Authors experiment in path prediction and hierarchical multi-label classification settings.", "questions": "What are the computational considerations in using this approach? A lot of emphasis is put on making sure that tractable learning and inference, so computational comparisons would be helpful.\n", "limitations": "Author mentions that limitations and ethical discussions are in the supplementary materials, but I couldn’t find it there.\n", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea is new to the best of my knowledge, and structured output prediction is a topic of interest to the NeurIPS community.\n\nThe submission appears technically sound and grounded theoretically---although I am not an expert in this area and could be missing something.\n\nThe submission was easy to follow, though I do have a few minor concerns:\n\n- In section 2, the terms “Expressive” and “General” were not defined in a way I expected. I’m still not confident that I understood the author’s intentions, but my guess is that “Expressive” means “allows soft constraints” or learned patterns in the output labels, and that “General” means “allows hard constraints”. I’m not quite sure what the difference is between “General” and “Consistent”?\n- A bit nitpicky but the Figure 1 and the Table 3 figure do not print well in grayscale.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept