betaFeedback

WorksComputer Science

Scallop: A Language for Neurosymbolic Programming

Abstract

We present Scallop, a language which combines the benefits of deep learning and logical reasoning. Scallop enables users to write a wide range of neurosymbolic applications and train them in a data- and compute-efficient manner. It achieves these goals through three key features: 1) a flexible symbolic representation that is based on the relational data model; 2) a declarative logic programming language that is based on Datalog and supports recursion, aggregation, and negation; and 3) a framework for automatic and efficient differentiable reasoning that is based on the theory of provenance semirings. We evaluate Scallop on a suite of eight neurosymbolic applications from the literature. Our evaluation demonstrates that Scallop is capable of expressing algorithmic reasoning in diverse and challenging AI tasks, provides a succinct interface for machine learning programmers to integrate logical domain knowledge, and yields solutions that are comparable or superior to state-of-the-art models in terms of accuracy. Furthermore, Scallop's solutions outperform these models in aspects such as runtime and data efficiency, interpretability, and generalizability.

Introduction

Classical algorithms and deep learning embody two prevalent paradigms of modern programming. Classical algorithms are well suited for exactly-defined tasks, such as sorting a list of numbers or finding a shortest path in a graph. Deep learning, on the other hand, is well suited for tasks that are not tractable or feasible to perform using classical algorithms, such as detecting objects in an image or parsing natural language text. These tasks are typically specified using a set of input-output training data, and solving them involves learning the parameters of a deep neural network to fit the data using gradient-based methods.

The two paradigms are complementary in nature. For instance, a classical algorithm such as the logic program PP depicted in Figure 1a is interpretable but operates on limited (e.g., structured) input rr. In contrast, a deep neural network such as MθM_\theta depicted in Figure 1b can operate on rich (e.g., unstructured) input xx but is not interpretable. Modern applications demand the capabilities of both paradigms. Examples include question answering [48], code completion [11], and mathematical problem solving [38], among many others. For instance, code completion requires deep learning to comprehend programmer intent from the code context, and classical algorithms to ensure that the generated code is correct. A natural and fundamental question then is how to program such applications by integrating the two paradigms.

Comparison of logic program, neural model, and basic neurosymbolic program

Figure 1. Comparison of different paradigms. Logic program PP accepts only structured input rr whereas neural model MθM_{\theta} with parameter θ\theta can operate on unstructured input xx. Supervision is provided on data indicated in double boxes. Under algorithmic supervision, a neurosymbolic program must learn θ\theta without supervision on rr.

Neurosymbolic programming is an emerging paradigm that aims to fulfill this goal [10]. It seeks to integrate symbolic knowledge and reasoning with neural architectures for better efficiency, interpretability, and generalizability than the neural or symbolic counterparts alone. Consider the task of handwritten formula evaluation [39], which takes as input a formula as an image, and outputs a number corresponding to the result of evaluating it. A neurosymbolic program for this task, such as the one depicted in Figure 1c, might first apply a convolutional neural network MθM_\theta to the input image to obtain a structured intermediate form rr as a sequence of symbols [‘1’,‘+’,‘3’,‘/’,‘5’][‘1’, ‘+’, ‘3’, ‘/’, ‘5’], followed by a classical algorithm PP to parse the sequence, evaluate the parsed formula, and output the final result 1.6.

Authors’ addresses: Ziyang Li, University of Pennsylvania, [email protected]; Jiani Huang, University of Pennsylvania, [email protected]; Mayur Naik, University of Pennsylvania, [email protected].

Despite significant strides in individual neurosymbolic applications [13, 39, 44, 45, 59, 63], there is a lack of a language with compiler support to make the benefits of the neurosymbolic paradigm more widely accessible. We set out to develop such a language and identified five key criteria that it should satisfy in order to be practical. These criteria, annotated by the components of the neurosymbolic program in Figure 1c, are as follows:

  1. A symbolic data representation for rr that supports diverse kinds of data, such as image, video, natural language text, tabular data, and their combinations.

  1. A symbolic reasoning language for PP that allows to express common reasoning patterns such as recursion, negation, and aggregation.

  1. An automatic and efficient differentiable reasoning engine for learning (∂y∂r)\left(\frac{\partial y}{\partial r}\right) under algorithmic supervision, i.e., supervision on observable input-output data (x,y)(x, y) but not rr.

  1. The ability to tailor learning (∂y∂r)\left(\frac{\partial y}{\partial r}\right) to individual applications’ characteristics, since non-continuous loss landscapes of logic programs hinder learning using a one-size-fits-all method.

  1. A mechanism to leverage and integrate with existing training pipelines (∂r∂θ)\left(\frac{\partial r}{\partial\theta}\right), implementations of neural architectures and models MθM_{\theta}, and hardware (e.g., GPU) optimizations.

In this paper, we present Scallop, a language which satisfies the above criteria. The key insight underlying Scallop is its choice of three inter-dependent design decisions: a relational model for symbolic data representation, a declarative language for symbolic reasoning, and a provenance framework for differentiable reasoning. We elaborate upon each of these decisions.

Relations can represent arbitrary graphs and are therefore well suited for representing symbolic data in Scallop applications. For instance, they can represent scene graphs, a canonical symbolic representation of images [35], or abstract syntax trees, a symbolic representation of natural language text. Further, they can be combined in a relational database to represent multi-modal data. Relations are also a natural fit for probabilistic reasoning [21], which is necessary since symbols in rr produced by neural model MθM_{\theta} can have associated probabilities.

Next, the symbolic reasoning program PP in Scallop is specified in a declarative logic programming language. The language extends Datalog [2] and is expressive enough for programmers to specify complex domain knowledge patterns that the neural model MθM_{\theta} would struggle with. Datalog implementations can take advantage of optimizations from the literature on relational database systems. This in turn enables efficient inference and learning since the logical domain knowledge specifications of the task at hand help reduce the burden of MθM_{\theta}, whose responsibilities are now less complex and more modular. Finally, Datalog is rule-based, which makes programs easier to write, debug, and verify. It also facilitates inferring them by leveraging techniques from program synthesis [29] and ILP [17].

While symbolic reasoning offers many aforementioned benefits, it poses a fundamental challenge for learning parameter θ\theta. Deep learning relies on gradient-based methods, enabled by the differentiable nature of the low-level activation functions that comprise MθM_{\theta}, to obtain ∂r∂θ\frac{\partial r}{\partial\theta}. The key challenge then concerns how to support automatic and efficient differentiation of the high-level logic program PP to obtain ∂y∂r\frac{\partial y}{\partial r}, which can be used in conjunction with ∂r∂θ\frac{\partial r}{\partial\theta} to compute ∂y∂θ\frac{\partial y}{\partial\theta}. Scallop addresses this problem by leveraging the framework of provenance semirings [26]. The framework proposes a common algebraic structure for applications that define annotations (i.e., tags) for tuples and propagate the annotations from inputs to outputs of relational algebra (RA) queries. One of our primary contributions is a novel adaptation of the framework for differentiable reasoning for an extended fragment of RA that includes recursion, negation, and aggregation. Scallop implements an extensible library of provenance structures including the extended max-min semiring and the top-kk proofs semiring [31]. We further demonstrate that different provenance structures enable different heuristics for the gradient calculations, providing an effective mechanism to tailor the learning process to individual applications’ characteristics.

We have implemented a comprehensive and open-source toolchain for Scallop in 45K LoC of Rust. It includes a compiler, an interpreter, and PyTorch bindings to integrate Scallop programs with existing machine learning pipelines. We evaluate Scallop using a suite of eight neurosymbolic applications that span the domains of image and video processing, natural language processing, planning, and knowledge graph querying, in a variety of learning settings such as supervised learning, reinforcement learning, rule learning, and contrastive learning. Our evaluation demonstrates that Scallop is expressive and yields solutions of comparable, and often times superior, accuracy than state-of-the-art models. We show additional benefits of Scallop’s solutions in terms of runtime and data efficiency, interpretability, and generalizability.

Any programming language treatise would be remiss without acknowledging the language’s lineage. TensorLog [16] and DeepProbLog (DPL) [43] pioneered the idea of extending probabilistic logic programming languages (e.g., ProbLog [21]) with differentiable reasoning. Scallop was originally proposed in [31] to improve the scalability of DPL by using Datalog instead of Prolog and relaxing its exact probabilistic semantics. We build upon [31] by extending its expressiveness, formalizing the semantics, developing a customizable provenance framework, and providing a practical toolchain.

The rest of the paper is organized as follows. § 2 presents an illustrative overview of Scallop. § 3 describes Scallop’s language for symbolic reasoning. § 4 presents the differentiable reasoning framework. § 5 describes our implementation of Scallop. § 6 empirically evaluates Scallop on a benchmark suite. § 7 surveys related work and § 8 concludes.

Illustrative Overview

We illustrate Scallop using a reinforcement learning (RL) based planning application which we call PacMan-Maze. The application, depicted in Figure 2a, concerns an intelligent agent realizing a sequence of actions in a simplified version of the PacMan maze game. The maze is an implicit 5×55 \times5 grid of cells. Each cell is either empty or has an entity, which can be either the actor (PacMan), the goal (flag), or an enemy (ghost). At each step, the agent moves the actor in one of four directions: up, down, right, or left. The game ends when the actor reaches the goal or hits an enemy. The maze is provided to the agent as a raw image that is updated at each step, requiring the agent to process sensory inputs, extract relevant features, and logically plan the path to take. Additionally, each session of the game has randomized initial positions of the actor, the goal, and the enemies.

Illustration of a planning application PacMan-Maze in Scallop

Figure 2. Illustration of a planning application PacMan-Maze in Scallop.

Concretely, the game is modeled as a sequence of interactions between the agent and an environment, as depicted in Figure 2b. The game state si∈Ss_i \in S at step ii is a 200×200200 \times200 colored image (S=R200×200×3S = \mathbb{R}^{200 \times200 \times3}). The agent proposes an action ai∈A={up,down,right,left}a_i \in A = \{\text{up}, \text{down}, \text{right}, \text{left}\} to the environment, which generates a new image si+1s_{i+1} as the next state. The environment also returns a reward rir_i to the agent: 1 upon reaching the goal, and 0 otherwise. This procedure repeats until the game ends or reaches a predefined limit on the number of steps.

A popular RL method to realize our application is QQ-Learning. Its goal is to learn a function Q:S×A→RQ:S \times A \to\mathbb{R} that returns the expected reward of taking action aia_i in state sis_i.2 Since the game states are images, we employ Deep QQ-Learning [46], which approximates the QQ function using a convolutional neural network (CNN) model with learned parameter θ\theta. An end-to-end deep learning based approach for our application involves training the model to predict the QQ-value of each action for a given game state. This approach takes 50K training episodes to achieve a 84.9% test success rate, where a single episode is one gameplay session from start to end.

In contrast, a neurosymbolic solution using Scallop only needs 50 training episodes to attain a 99.4% test success rate. Scallop enables to realize these benefits of the neurosymbolic paradigm by decomposing the agent’s task into separate neural and symbolic components, as shown in Figure 2b. These components perform sub-tasks that are ideally suited for their respective paradigms: the neural component perceives pixels of individual cells of the image at each step to identify the entities in them, while the symbolic component reasons about enemy-free paths from the actor to the goal to determine the optimal next action. Figure 2c shows an outline of this architecture’s implementation using the popular PyTorch framework.

Concretely, the neural component is still a CNN, but it now takes the pixels of a single cell in the input image at a time, and classifies the entity in it. The implementation of the neural component (EntityExtractor) is standard and elided for brevity. It is invoked on lines 14-15 with input game_state_image, a tensor in R200×200×3\mathbb{R}^{200 \times200 \times3}, and returns three R5×5\mathbb{R}^{5 \times5} tensors of entities. For example, actor is an R5×5\mathbb{R}^{5 \times5} tensor and actorijactor_{ij} is the probability of the actor being in cell (i,j)(i,j). A representation of the entities is then passed to the symbolic component on lines 16-17, which derives the QQ-value of each action. The symbolic component, which is configured on lines 6-11, comprises the Scallop program shown in Figure 3. We next illustrate the three key design decisions of Scallop outlined in § 1 with respect to this program.

// File path_planner.scl
type actor(x: i32, y: i32), goal(x: i32, y: i32), enemy(x: i32, y: i32)

const UP = 0, DOWN = 1, RIGHT = 2, LEFT = 3
rel safe_cell(x, y) = range(0, 5, x), range(0, 5, y), not enemy(x, y)
rel edge(x, y, xp, yp, UP) = safe_cell(x, y), safe_cell(xp, yp), yp == y + 1
// Rules for DOWN, RIGHT, and LEFT edges are omitted...

rel next_pos(p, q, a) = actor(x, y), edge(x, y, p, q, a)
rel path(x, y, x, y) = next_pos(x, y, _)
rel path(x1, y1, x3, y3) = path(x1, y1, x2, y2), edge(x2, y2, x3, y3, _)
rel next_action(a) = next_pos(p, q, a), path(p, q, r, s), goal(r, s)

Figure 3. The logic program of the PacMan-Maze application in Scallop.

Relational Model. In Scallop, the primary data structure for representing symbols is a relation. In our example, the game state can be symbolically described by the kinds of entities that occur in the discrete cells of a 5×55 \times5 grid. We can therefore represent the input to the symbolic component using binary relations for the three kinds of entities: actor, goal, and enemy. For instance, the fact actor(2, 3) indicates that the actor is in cell (2, 3). Likewise, since there are four possible actions, the output of the symbolic component is represented by a unary relation next_action.

Symbols extracted from unstructured inputs by neural networks have associated probabilities, such as the R5×5\mathbb{R}^{5 \times5} tensor actor produced by the neural component in our example (line 14 of Figure 2c). Scallop therefore allows to associate tuples with probabilities, e.g. 0.96 :: actor(2, 3), to indicate that the actor is in cell (2, 3) with probability 0.96. More generally, Scallop enables the conversion of tensors in the neural component to and from relations in the symbolic component via input-output mappings (lines 9-11 in Figure 2c), allowing the two components to exchange information seamlessly.

Declarative Language. Another key consideration in a neurosymbolic language concerns what constructs to provide for symbolic reasoning. Scallop uses a declarative language based on Datalog, which we present in § 3 and illustrate here using the program in Figure 3. The program realizes the symbolic component of our example using a set of logic rules. Following Datalog syntax, they are “if-then” rules, read right to left, with commas denoting conjunction.

Recall that we wish to determine an action aa (up, down, right, or left) to a cell (p,q)(p, q) that is adjacent to the actor’s cell (x,y)(x, y) such that there is an enemy-free path from (p,q)(p, q) to the goal’s cell (r,s)(r, s). The nine depicted rules succinctly compute this sophisticated reasoning pattern by building successively complex relations, with the final rule (on line 14) computing all such actions.3

The arguably most complex concept is the path relation which is recursively defined (on lines 10-11). Recursion allows to define the pattern succinctly, enables the trained application to generalize to grids arbitrarily larger than 5×55 \times5 unlike the purely neural version, and makes the pattern more amenable to synthesis from input-output examples. Besides recursion, Scallop also supports negation and aggregation; together, these features render the language adequate for specifying common high-level reasoning patterns in practice.

Differentiable Reasoning. With the neural and symbolic components defined, the last major consideration concerns how to train the neural component using only end-to-end supervision. In our example, supervision is provided in the form of a reward of 1 or 0 per gameplay session, depending upon whether or not the sequence of actions by the agent successfully led the actor to the goal without hitting any enemy. This form of supervision, called algorithmic or weak supervision, alleviates the need to label intermediate relations at the interface of the neural and symbolic components, such as the actor, goal, and enemy relations. However, this also makes it challenging to learn the gradients for the tensors of these relations, which in turn are needed to train the neural component using gradient-descent techniques.

The key insight in Scallop is to exploit the structure of the logic program to guide the gradient calculations. The best heuristic for such calculations depends on several application characteristics such as the amount of available data, reasoning patterns, and the learning setup. Scallop provides a convenient interface for the user to select from a library of built-in heuristics. Furthermore, since all of these heuristics follow the structure of the logic program, Scallop implements them uniformly as instances of a general and extensible provenance framework, described in § 4. For our example, line 8 in Figure 2c specifies diff-top-k-proofs with k=1k=1 as the heuristic to use, which is the default in Scallop that works best for many applications, as we demonstrate in § 6.

Language

We provide an overview of Scallop’s language for symbolic reasoning which we previously illustrated in the program shown in Figure 3. Appendix A provides the formal syntax of the language. Here, we illustrate each of the key constructs using examples of inferring kinship relations.

Data Types

The fundamental data type in Scallop is set-valued relations comprising tuples of statically-typed primitive values. The primitive data types include signed and unsigned integers of various sizes (e.g. i32, usize), single- and double-precision floating point numbers (f32, f64), boolean (bool), character (char), and string (String). The following example declares two binary relations, mother and father:

type mother(c: String, m: String), father(c: String, f: String)

Values of relations can be specified via individual tuples or a set of tuples of constant literals:

rel mother("Bob", "Christine") // Christine is Bob's mother
rel father = {("Alice", "Bob"), ("John", "Bob")} // Bob is father of two kids

As a shorthand, primitive values can be named and used as constant variables:

const FATHER = 0, MOTHER = 1, GRANDMOTHER = 2, ... // other relationships
rel composition(FATHER, MOTHER, GRANDMOTHER) // father's mother is grandmother

Type declarations are optional since Scallop supports type inference. The type of the composition relation is inferred as (usize, usize, usize) since the default type of unsigned integers is usize.

(Horn) Rules

Since Scallop’s language is based on Datalog, it supports “if-then” rule-like Horn clauses. Each rule is composed of a head atom and a body, connected by the symbol :- or =. The following code shows two rules defining the grandmother relation. Conjunction is specified using “,”-separated atoms within the rule body whereas disjunction is specified by multiple rules with the same head predicate. Each variable appearing in the head must also appear in some positive atom in the body (we introduce negative atoms below).

rel grandmother(a, c) :- father(a, b), mother(b, c) // father's mother
rel grandmother(a, c) :- mother(a, b), mother(b, c) // mother's mother

Conjunctions and disjunctions can also be expressed using logical connectives like and, or, and implies. For instance, the following rule is equivalent to the above two rules combined.

rel grandmother(a, c) = (mother(a, b) or father(a, b)) and mother(b, c)

Scallop supports value creation by means of foreign functions (FFs). FFs are polymorphic and include arithmetic operators such as + and -, comparison operators such as != and >=, type conversions such as [i32] as String, and built-in functions like hashandhash andstring_concat. They only operate on primitive values but not relational tuples or atoms. The following example shows how strings are concatenated together using FF, producing the result full_name("Alice Lee").

rel first_name("Alice"), last_name("Lee")
rel full_name($string_concat(x, " ", y)) = first_name(x), last_name(y)

Note that FFs can fail due to runtime errors such as division-by-zero and integer overflow, in which case the computation for that single fact is omitted. In the example below, when dividing 6 by denominator, the result is not computed for denominator 0 since it causes a FF failure:

rel denominator = {0, 1, 2}
rel result(6 / x) = denominator(x) // result contains only integers 3 and 6

The purpose of this semantics is to support probabilistic extensions (§ 3.3) rather than silent suppression of runtime errors. When dealing with floating-point numbers, tuples with NaN (not-a-number) are also discarded.

Recursion. A relation rr is dependent on ss if an atom ss appears in the body of a rule with head atom rr. A recursive relation is one that depends on itself, directly or transitively. The following rule derives additional kinship facts by composing existing kinship facts using the composition relation.

rel kinship(r3, a, c) = kinship(r1, a, b), kinship(r2, b, c), composition(r1, r2, r3)

Negation. Scallop supports stratified negation using the not operator on atoms in the rule body. The following example shows a rule defining the has_no_children relation as any person p who is neither a father nor a mother. Note that we need to bound p by a positive atom person in order for the rule to be well-formed.

rel person = {"Alice", "Bob", "Christine"} // can omit () since arity is 1
rel has_no_children(p) = person(p) and not father(_, p) and not mother(_, p)

A relation rr is negatively dependent on ss if a negated atom ss appears in the body of a rule with head atom rr. In the above example, has_no_children negatively depends on father. A relation cannot be negatively dependent on itself, directly or transitively, as Scallop supports only stratified negation. The following rule is rejected by the compiler, as the negation is not stratified:

rel something_is_true() = not something_is_true() // compilation error!

Aggregation. Scallop also supports stratified aggregation. The set of built-in aggregators include common ones such as count, sum, max, and first-order quantifiers for all and exists. Besides the operator, the aggregation specifies the binding variables, the aggregation body to bound those variables, and the result variable(s) to assign the result. The aggregation in the example below reads, “variable n is assigned the count of p, such that p is a person”:

rel num_people(n) = n := count(p: person(p))

In the rule, p is the binding variable and n is the result variable. Depending on the aggregator, there could be multiple binding variables or multiple result variables. Further, Scallop supports SQL-style group-by using a where clause in the aggregation. In the following example, we compute the number of children of each person p, which serves as the group-by variable.

Figure 4. Algebraic interface for provenance.

rel parent(a, b) = father(a, b) or mother(a, b)
rel num_child(p, n) = n := count(c: parent(c, p) where p: person(p))

Finally, quantifier aggregators such as forall and exists return one boolean variable. For instance, in the aggregation below, variable sat is assigned the truthfulness (true or false) of the following statement: “for all a and b, if b is a’s father, then a is b’s son or daughter”.

rel integrity_constraint(sat) =
    sat := forall(a, b: father(a, b) implies (son(b, a) or daughter(b, a)))

There are a couple of syntactic checks on aggregations. First, similar to negation, aggregation also needs to be stratified—a relation cannot be dependent on itself through an aggregation. Second, the binding variables must be bounded by a positive atom in the body of the aggregation.

Probabilistic Extensions

Although Scallop is designed primarily for neurosymbolic programming, its syntax also supports probabilistic programming. This is especially useful when debugging Scallop code before integrating it with a neural network. Consider a machine learning programmer who wishes to extract structured relations from a natural language sentence “Bob takes his daughter Alice to the beach”. The programmer could imitate a neural network producing a probability distribution of kinship relations between Alice (A) and Bob (B) as follows:

rel kinship = {0.95::(FATHER, A, B); 0.01::(MOTHER, A, B); ...}

Here, we list out all possible kinship relations between Alice and Bob. For each of them, we use the syntax [PROB]::[TUPLE] to tag the kinship tuples with probabilities. The semicolon “;” separating them specifies that they are mutually exclusive—Bob cannot be both the mother and father of Alice.

Scallop also supports operators to sample from probability distributions. They share the same surface syntax as aggregations, allowing sampling with group-by. The following rule deterministically picks the most likely kinship relation between a given pair of people a and b, which are implicit group-by variables in this aggregation. As the end, only one fact, 0.95::top_1_kinship(FATHER, A, B), will be derived according to the above probabilities.

rel top_1_kinship(r, a, b) = r := top<1>(rp: kinship(rp, a, b))

Other types of sampling are also supported, including categorical sampling (categorical<K>) and uniform sampling (uniform<K>), where a static constant K denotes the number of trials.

Finally, rules can also be tagged by probabilities which can reflect their confidence. The following rule states that a grandmother’s daughter is one’s mother with 90% confidence.

rel 0.9::mother(a, c) = grandmother(a, b) and daughter(b, c)

Probabilistic rules are syntactic sugar. They are implemented by introducing in the rule’s body an auxiliary 0-ary (i.e., boolean) fact that is regarded true with the tagged probability.

(Constant)C∋c::=int∣bool∣str∣⋯(Tuples)U∈U ≜ P(U)(Tuple)U∋u::=c∣(u1,…,un)(Tagged-Tuples)UT∈UT ≜ P(UT)(Tagged-Tuple)UT∋ut::=t::u(Facts)F∈F ≜ P(F)(Fact)F∋f::=p(u)(Database)FT∈FT ≜ P(FT)(Tagged-Fact)FT∋ft::=t::p(u)\begin{aligned} (\mathrm{Constant})\quad\mathcal{C} &\ni c ::= \mathrm{int}\mid\mathrm{bool}\mid\mathrm{str}\mid\cdots& (\mathrm{Tuples})\quad U &\in\mathcal{U}\ \triangleq\ \mathcal{P}(\mathcal{U})\\ (\mathrm{Tuple})\quad U &\ni u ::= c\mid(u_1,\ldots,u_n) & (\mathrm{Tagged\text{-}Tuples})\quad U_T &\in\mathcal{U}_T\ \triangleq\ \mathcal{P}(\mathcal{U}_T)\\ (\mathrm{Tagged\text{-}Tuple})\quad U_T &\ni u_t ::= t::u & (\mathrm{Facts})\quad F &\in\mathcal{F}\ \triangleq\ \mathcal{P}(\mathcal{F})\\ (\mathrm{Fact})\quad F &\ni f ::= p(u) & (\mathrm{Database})\quad F_T &\in\mathcal{F}_T\ \triangleq\ \mathcal{P}(\mathcal{F}_T)\\ (\mathrm{Tagged\text{-}Fact})\quad F_T &\ni f_t ::= t::p(u) \end{aligned}

fig:6. Semantic domains for SclRam.

Reasoning Framework

The preceding section presented Scallop’s surface language for use by programmers to express discrete reasoning. However, the language must also support differentiable reasoning to enable end-to-end training. In this section, we formally define the semantics of the language by means of a provenance framework. We show how Scallop uniformly supports different reasoning modes—discrete, probabilistic, and differentiable—simply by defining different provenances.

We start by presenting the basics of our provenance framework (§ 4.1). We then present a low-level representation SclRam, its operational semantics, and its interface to the rest of a Scallop application (§ 4.2–§ 4.7). We next present differentiation and three different provenances for differentiable reasoning (§ 4.8). Lastly, we discuss practical considerations (§ 4.9).

Provenance Framework

Scallop’s provenance framework enables to tag and propagate additional information alongside relational tuples in the logic program’s execution. The framework is based on the theory of provenance semirings [26]. Fig. 4 defines Scallop’s algebraic interface for provenance. We call the additional information a tag tt from a tag space TT. There are two distinguished tags, 00 and 11, representing unconditionally false and true tags. Tags are propagated through operations of binary disjunction ⊕\oplus, binary conjunction ⊗\otimes, and unary negation ⊖\ominus resembling logical or, and, and not. Lastly, a saturation check ∘=\mathrel{\circ}= serves as a customizable stopping mechanism for fixed-point iteration.

All of the above components combined form a 7-tuple (T,0,1,⊕,⊗,⊖,∘=)(T,0,1,\oplus,\otimes,\ominus,\mathrel{\circ}=) which we call a provenance TT. Scallop provides a built-in library of provenances and users can add custom provenances simply by implementing this interface.

Example 4.1. max-min-prob (mmp) ≜([0,1],0,1,max⁡,min⁡,λx.(1−x),==)\triangleq([0,1],0,1,\max,\min,\lambda x.(1-x),==), is a built-in probabilistic provenance, where tags are numbers between 0 and 1 that are propagated with max and min. The tags do not represent true probabilities but are merely an approximation. We discuss richer provenances for more accurate probability calculations later in this section.

A provenance must satisfy a few properties. First, the 5-tuple (T,0,1,⊕,⊗)(T,0,1,\oplus,\otimes) should form a semiring. That is, 00 is the additive identity and annihilates under multiplication, 11 is the multiplicative identity, ⊕\oplus and ⊗\otimes are associative and commutative, and ⊗\otimes distributes over ⊕\oplus. To guarantee the existence of fixed points (which are discussed in § 4.3), it must also be absorptive, i.e., t1⊕(t1⊗t2)=t1t_1\oplus(t_1\otimes t_2)=t_1 [18]. Moreover, we need ⊖0=1\ominus0=1, ⊖1=0\ominus1=0, ⊖0=0\ominus0=0, and 1⊖1=11\ominus1=1. A provenance which violates an individual property (e.g. absorptive) is still useful to applications that do not use the affected features (e.g. recursion) or if the user simply wishes to bypass the restrictions.

SclRam Intermediate Language

Scallop programs are compiled to a low-level representation called SclRam. Figure 5 shows the abstract syntax of a core fragment of SclRam. Expressions resemble queries in an extended relational algebra. They operate over relational predicates (pp) using unary operations for aggregation (γg\gamma_g with aggregator gg), projection (πα\pi_\alpha with mapping α\alpha), and selection (σβ\sigma_\beta with condition β\beta), and binary operations union (∪\cup), product (×\times), and difference (−-).

Figure 5. Abstract syntax of core fragment of ScLRAM.

A rule rr in SclRam is denoted p←ep \leftarrow e, where predicate pp is the rule head and expression ee is the rule body. An unordered set of rules combined form a stratum ss, and a sequence of strata s1;…;sns_1; \ldots;s_n constitutes a SclRam program. Rules in the same stratum have distinct head predicates. Denoting the set of head predicates in stratum ss by PsP_s, we also require Psi∩Psj=∅P_{s_i} \cap P_{s_j} = \emptyset forall i≠ji \ne j in a program. Stratified negation and aggregation from the surface language is enforced as syntax restrictions in SclRam: within a rule in stratum sis_i, if a relational predicate pp is used under aggregation (γ\gamma) or right-hand-side of difference (−-), that predicate pp cannot appear in PsjP_{s_j} if j≥ij \ge i.

We next define the semantic domains in Fig. 6 which are used subsequently to define the semantics of SclRam. A tuple uu is either a constant or a sequence of tuples. A fact p(u)∈Fp(u) \in\mathbb{F} is a tuple uu named under a relational predicate pp. Tuples and facts can be tagged, forming tagged tuples (t::u)(t :: u) and tagged facts (t::p(u))(t :: p(u)). Given a set of tagged tuples UTU_T, we say UT⊨uU_T \models u iff there exists a tt such that t::u∈UTt :: u \in U_T. A set of tagged facts form a database FTF_T. We use bracket notation FT[p]F_T[p] to denote the set of tagged facts in FTF_T under predicate pp.

Operational Semantics of SclRam

We now present the operational semantics for our core fragment of SclRam in Figure 7. A SclRam program sˉ\bar{s} takes as input an extensional database (EDB) FTF_T, and returns an intentional database (IDB) FT′=⟦sˉ⟧(FT)F'_T = \llbracket\bar{s} \rrbracket(F_T). The semantics is conditioned on the underlying provenance TT. We call this tagged semantics, as opposed to the untagged semantics found in traditional Datalog.

Operational semantics of core fragment of SclRam

Figure 7. Operational semantics of core fragment of SclRam.

Basic Relational Algebra. Evaluating an expression in SclRam yields a set of tagged tuples according to the rules defined at the top of Figure 7. A predicate pp evaluates to all facts under that predicate in the database. Selection filters tuples that satisfy condition β\beta, and projection transforms tuples according to mapping α\alpha. The mapping function α\alpha is partial: it may fail since it can apply foreign functions to values. A tuple in a union e1∪e2e_1 \cup e_2 can come from either e1e_1 or e2e_2. In (cartesian) product, each pair of incoming tuples combine and we use ⊗\otimes to compute the tag conjunction.

Difference and Negation. To evaluate a difference expression e1−e2e_1 - e_2, there are two cases depending on whether a tuple uu evaluated from e1e_1 appears in the result of e2e_2. If it does not, we simply propagate the tuple and its tag to the result (Diff-1); otherwise, we get t1::ut_1 :: u from e1e_1 and t2::ut_2 :: u from e2e_2. Instead of erasing the tuple uu from the result as in untagged semantics, we propagate a tag t1⊗(¬t2)t_1 \otimes(\neg t_2) with uu (Diff-2). In this manner, information is not lost during negation. Figure 8 compares the evaluations of an example difference expression under different semantics. While the tuple (2,3)(2, 3) is removed in the outcome with untagged semantics, it remains with the tagged semantics.

Example rule under untagged, tagged, and max-min-prob semantics

Figure 8. An example rule adapted from § 2 is compiled to a SclRam rule with difference. g and e are abbreviated relation names. The graphs illustrate the evaluation of expression g − e under different semantics.

Aggregation. Aggregators in SclRam are discrete functions gg operating on set of (untagged) tuples U∈UU \in\mathcal{U}. They return a set of aggregated tuples to account for aggregators like argmax which can produce multiple outcomes. For example, we have count⁡(U)=∣U∣\operatorname{count}(U) = \lvert U \rvert. However, in the probabilistic domain, discrete symbols do not suffice. Given nn tagged tuples to aggregate over, each tagged tuple can be turned on or off, resulting in 2n2^n distinct worlds. Each world is a partition of the input set UTU_T (∣UT∣=n\lvert U_T \rvert= n). Denoting the positive part as XTX_T and the negative part as X‾T=UT−XT\overline{X}_T = U_T - X_T, the tag associated with this world is a conjunction of tags in XTX_T and negated tags in X‾T\overline{X}_T. Aggregating on this world then involves applying aggregator gg on tuples in the positive part XTX_T. This is inherently exponential if we enumerate all worlds. However, we can optimize over each aggregator and each provenance to achieve better performance. For instance, counting over max–min–prob tagged tuples can be implemented by an O(nlog⁡(n))O(n \log(n)) algorithm, much faster than exponential. Figure 9 demonstrates a running example and an evaluation of a counting expression under max–min–prob provenance. The resulting count can be 00–99, each derivable by multiple worlds.

Example counting enemies in a PacMan maze

Figure 9. An example counting enemies in a PacMan maze. Shown above are the Scallop rule and compiled SclRam rule with aggregation. (a) and (b) visualize the maze and the content of a probabilistic enemy relation. For example, we have tB2::enemy⁡(B,2)t_{\mathrm{B2}}\mathbin{::}\operatorname{enemy}(\mathrm{B},2) where tB2=0.8t_{\mathrm{B2}}=0.8. In (c), we show two normalized (⟨.⟩\langle.\rangle defined in Figure 7) evaluation results under abstract tagged semantics and with max–min-prob provenance. Each symbol such as □\boxed{\square} represents a world corresponding to our arena (■: enemy; □: no enemy). A world is a conjunction of 9 tags, e.g., ■□□□□□□□□=tA3⊗(⊖tA2)⊗⋯⊗(⊖tC1)\boxed{\blacksquare\Box\Box\Box\Box\Box\Box\Box\Box}=t_{\mathrm{A3}}\otimes(\ominus t_{\mathrm{A2}})\otimes\cdots\otimes(\ominus t_{\mathrm{C1}}). We mark the correct world □□□□□□□□□\boxed{\Box\Box\Box\Box\Box\Box\Box\Box\Box} which yields the answer 2.

Rules and Fixed-Point Iteration. Evaluating a rule p←ep \leftarrow e on database FTF_T concerns evaluating the expression ee and merging the result with the existing facts under predicate pp in FTF_T. The result of evaluating ee may contain duplicated tuples tagged by distinct tags, owing to expressions such as

Expression semantics

α:U⇀U,β:U→Bool,g:U→U,⟦e⟧:FT→UT\alpha: U \rightharpoonup U,\quad\beta: U \to\mathrm{Bool},\quad g : U \to U,\quad\llbracket e \rrbracket: F_T \to U_T
t::p(u)∈FTt::u∈⟦p⟧(FT)(Predicate)\frac{t :: p(u) \in F_T}{t :: u \in\llbracket p \rrbracket(F_T)} \qquad\text{(Predicate)}
t::u∈⟦e⟧(FT)β(u)=truet::u∈⟦σβ(e)⟧(FT)(Select)\frac{t :: u \in\llbracket e \rrbracket(F_T)\qquad\beta(u)=\mathrm{true}}{t :: u \in\llbracket\sigma_\beta(e) \rrbracket(F_T)} \qquad\text{(Select)}
t::u∈⟦e⟧(FT)u′=α(u)t::u′∈⟦πα(e)⟧(FT)(Project)\frac{t :: u \in\llbracket e \rrbracket(F_T)\qquad u'=\alpha(u)}{t :: u' \in\llbracket\pi_\alpha(e) \rrbracket(F_T)} \qquad\text{(Project)}
t::u∈⟦e1⟧(FT)∪⟦e2⟧(FT)t::u∈⟦e1∪e2⟧(FT)(Union)\frac{t :: u \in\llbracket e_1 \rrbracket(F_T)\cup\llbracket e_2 \rrbracket(F_T)}{t :: u \in\llbracket e_1\cup e_2 \rrbracket(F_T)} \qquad\text{(Union)}
t1::u1∈⟦e1⟧(FT)t2::u2∈⟦e2⟧(FT)(t1⊗t2)::(u1,u2)∈⟦e1×e2⟧(FT)(Product)\frac{t_1 :: u_1 \in\llbracket e_1 \rrbracket(F_T)\qquad t_2 :: u_2 \in\llbracket e_2 \rrbracket(F_T)} {(t_1\otimes t_2) :: (u_1,u_2) \in\llbracket e_1\times e_2 \rrbracket(F_T)} \qquad\text{(Product)}
t::u∈⟦e1⟧(FT)⟦e2⟧(FT)⊭ut::u∈⟦e1−e2⟧(FT)(Diff-1)\frac{t :: u \in\llbracket e_1 \rrbracket(F_T)\qquad\llbracket e_2 \rrbracket(F_T)\not\models u} {t :: u \in\llbracket e_1-e_2 \rrbracket(F_T)} \qquad\text{(Diff-1)}
t1::u∈⟦e1⟧(FT)t2::u∈⟦e2⟧(FT)(t1⊗(⊖t2))::u∈⟦e1−e2⟧(FT)(Diff-2)\frac{t_1 :: u \in\llbracket e_1 \rrbracket(F_T)\qquad t_2 :: u \in\llbracket e_2 \rrbracket(F_T)} {(t_1\otimes(\ominus t_2)) :: u \in\llbracket e_1-e_2 \rrbracket(F_T)} \qquad\text{(Diff-2)}
XT⊆⟦e⟧(FT){ti::ui}i=1n=XT{tj::uj}j=1m=⟦e⟧(FT)−XTu∈g({ui}ti)(⨂i=1nti)⊗(⨂j=1m(⊖tj))::u∈⟦γg(e)⟧(FT)(Aggregate)\frac{X_T\subseteq\llbracket e\rrbracket(F_T)\qquad\{t_i::u_i\}_{i=1}^{n}=X_T\qquad\{t_j::u_j\}_{j=1}^{m}=\llbracket e\rrbracket(F_T)-X_T\qquad u\in g(\{u_i\}_{t_i}) } {(\bigotimes_{i=1}^{n}t_i)\otimes(\bigotimes_{j=1}^{m}(\ominus t_j)) :: u \in\llbracket\gamma_g(e)\rrbracket(F_T)} \qquad\text{(Aggregate)}

Rule semantics

⟨⋅⟩:UT→UT,⟦r⟧:FT→FT\langle\cdot\rangle:U_T\to U_T,\qquad\llbracket r\rrbracket:F_T\to F_T
⟨UT⟩={(⨁i=1nti)::u∣t1::u,…,tn::u are all tagged-tuples in UT with the same tuple u}(Normalize)\langle U_T\rangle=\{(\bigoplus_{i=1}^{n}t_i)::u\mid t_1::u,\ldots,t_n::u\text{ are all tagged-tuples in }U_T\text{ with the same tuple }u\} \qquad\text{(Normalize)}
told::u∈⟦p⟧(FT)⟦e⟧(FT)⊭utold::p(u)∈⟦p←e⟧(FT)(Rule-1)\frac{t^{\mathrm{old}}::u\in\llbracket p\rrbracket(F_T)\qquad\llbracket e\rrbracket(F_T)\not\models u} {t^{\mathrm{old}}::p(u)\in\llbracket p\leftarrow e\rrbracket(F_T)} \qquad\text{(Rule-1)}
tnew::u∈⟦e⟧(FT)⟦p⟧(FT)⊭utnew::p(u)∈⟦p←e⟧(FT)(Rule-2)\frac{t^{\mathrm{new}}::u\in\llbracket e\rrbracket(F_T)\qquad\llbracket p\rrbracket(F_T)\not\models u} {t^{\mathrm{new}}::p(u)\in\llbracket p\leftarrow e\rrbracket(F_T)} \qquad\text{(Rule-2)}
told::u∈⟦p⟧(FT)tnew::u∈⟦e⟧(FT)(told⊕tnew)::p(u)∈⟦p←e⟧(FT)(Rule-3)\frac{t^{\mathrm{old}}::u\in\llbracket p\rrbracket(F_T)\qquad t^{\mathrm{new}}::u\in\llbracket e\rrbracket(F_T)} {(t^{\mathrm{old}}\oplus t^{\mathrm{new}})::p(u)\in\llbracket p\leftarrow e\rrbracket(F_T)} \qquad\text{(Rule-3)}

Stratum and Program semantics

lfp⁡∘:(FT→FT)→(FT→FT),⟦s⟧,⟦s⟧:FT→FT\operatorname{lfp}^{\circ}:(F_T\to F_T)\to(F_T\to F_T),\qquad\llbracket s\rrbracket,\llbracket s\rrbracket:F_T\to F_T
FTold⊆FTnew  ⟺  ∀t::p(u)∈FTnew, ∃t′::p(u)∈FTold such that told⊕tnew(Saturation)F_T^{\mathrm{old}}\subseteq F_T^{\mathrm{new}}\iff\forall t::p(u)\in F_T^{\mathrm{new}},\ \exists t'::p(u)\in F_T^{\mathrm{old}}\text{ such that }t^{\mathrm{old}}\oplus t^{\mathrm{new}} \qquad\text{(Saturation)}
lfp⁡∘(h)=h∘⋯∘h=hn if there exists a minimum n>0, such that hn(FT)≡hn+1(FT)(Fixpoint)\operatorname{lfp}^{\circ}(h)=h\circ\cdots\circ h=h^n\text{ if there exists a minimum }n>0\text{, such that }h^n(F_T)\equiv h^{n+1}(F_T) \qquad\text{(Fixpoint)}
⟦s⟧=lfp⁡∘(λFT.(FT−⋃p∈PsFT[p])∪(⋃r∈s⟦r⟧(FT)))(Stratum)\llbracket s\rrbracket=\operatorname{lfp}^{\circ}\left(\lambda F_T.\left(F_T-\bigcup_{p\in P_s}F_T[p]\right)\cup\left(\bigcup_{r\in s}\llbracket r\rrbracket(F_T)\right)\right) \qquad\text{(Stratum)}
⟦s⟧=⟦sn⟧∘⋯∘⟦s1⟧, where s=s1;…;sn.(Program)\llbracket s\rrbracket=\llbracket s_n\rrbracket\circ\cdots\circ\llbracket s_1\rrbracket,\text{ where }s=s_1;\ldots;s_n. \qquad\text{(Program)}

union, projection, or aggregation. Therefore, we perform normalization on the set to join (⊕\oplus) the distinct tags. From here, there are three cases to merge the newly derived tuples (⟨⟦e⟧(FT)⟩\langle\llbracket e\rrbracket(F_T)\rangle) with the previously derived tuples (⟦p⟧(FT)\llbracket p\rrbracket(F_T)). If a fact is present only in the old or the new, we simply propagate the fact to the output. When a tuple uu appears in both the old and the new, we propagate the disjunction of the old and new tag (told⊕tnewt^{\mathrm{old}}\oplus t^{\mathrm{new}}). Combining all cases, we obtain a set of newly tagged facts under predicate pp.

Recursion in SclRam is realized similar to least fixed point iteration in Datalog [2]. The iteration happens on a per-stratum basis to enforce stratified negation and aggregation. Evaluating a single step of stratum ss means evaluating all the rules in ss and returning the updated

rel⁡ num_enemies⁡(n)=n≔count⁡(x,y:enemy⁡(x,y))→num_enemies⁡←πλn.(n)(γcount⁡(enemy⁡))\operatorname{rel}\ \operatorname{num\_enemies}(n)=n\coloneqq\operatorname{count}(x,y:\operatorname{enemy}(x,y)) \quad\to\quad\operatorname{num\_enemies}\gets\pi_{\lambda n.(n)}(\gamma_{\operatorname{count}}(\operatorname{enemy}))
rel⁡ path⁡(x1,y1,x3,y3)=(edge⁡(x1,y1,x3,y3) or⁡ path⁡(x1,y1,x2,y2) and⁡ edge⁡(x2,y2,x3,y3)) and⁡ not⁡ enemy⁡(x3,y3)\operatorname{rel}\ \operatorname{path}(x_1,y_1,x_3,y_3)=(\operatorname{edge}(x_1,y_1,x_3,y_3)\ \operatorname{or}\ \operatorname{path}(x_1,y_1,x_2,y_2)\ \operatorname{and}\ \operatorname{edge}(x_2,y_2,x_3,y_3))\ \operatorname{and}\ \operatorname{not}\ \operatorname{enemy}(x_3,y_3)
Iteration count ii1234567
tC1−C3(i)t_{\mathrm{C1-C3}}^{(i)} in F(i)F^{(i)}–↑\boxed{\uparrow}(same)→⊕→⊕⋯⊕↑\boxed{\rightarrow}\oplus\boxed{\rightarrow}\oplus\cdots\oplus\boxed{\uparrow}(same)→⊕→⊕⋯⊕↑\boxed{\rightarrow}\oplus\boxed{\rightarrow}\oplus\cdots\oplus\boxed{\uparrow}(same)
tC1−C3(i)t_{\mathrm{C1-C3}}^{(i)} in FmmpF_{\mathrm{mmp}}–0.10.10.20.20.90.9
tC1−C3(i)t_{\mathrm{C1-C3}}^{(i)} saturated?–falsetruefalsetruefalsetrue
Fmmp(i)F_{\mathrm{mmp}}^{(i)} saturated?falsefalsefalsefalsefalsefalsetrue

Table 10. A demonstration of the fixed-point iteration to check whether actor at C1 can reach C3 without hitting an enemy (Figure 9a). The Scallop rule to derive this is defined on the top, and we assume bidirectional edges are populated and tagged by 1. Let tC1−C3t_{\mathrm{C1-C3}} be the tag associated with path⁡(C,1,C,3)\operatorname{path}(\mathrm{C},1,\mathrm{C},3). We use a symbol like ↑\boxed{\uparrow} to represent a conjunction of negated tags of enemy along the illustrated path, e.g. ↑=(⊖tC2)⊗(⊖tC3)\boxed{\uparrow}=(\ominus t_{\mathrm{C2}})\otimes(\ominus t_{\mathrm{C3}}). 2nd iter is the first time tC1−C3t_{\mathrm{C1-C3}} is derived, but the path ↑\boxed{\uparrow} is blocked by an enemy. On 6th iter, the best path →\boxed{\rightarrow} is derived in the tag. After that, under the max–min-prob provenance, both the tag tC1−C3t_{\mathrm{C1-C3}} and the database FmmpF_{\mathrm{mmp}} are saturated, causing the iteration to stop. Compared to untagged semantics in Datalog which will stop after 4 iterations, SclRam with mmp saturates slower but allowing to explore better reasoning chains.

database. Note that we define a specialized least fixed point operator lfp⁡∘\operatorname{lfp}^{\circ}, which stops the iteration once the whole database is saturated. Fig. 10 illustrates an evaluation involving recursion and database saturation. The whole database saturates on the 7th iteration, and finds the tag representing the optimal path for the PacMan to reach the goal. Termination is not universally guaranteed in SclRam due to the presence features such as value creation. But its existence can be proven in a per-provenance basis. For example, it is easy to show that if a program terminates under untagged semantics, then it terminates under tagged semantics with max–min-prob provenance.

External Interface and Execution Pipeline

Thus far, we have only illustrated the max–min-prob provenance, in which the tags are approximated probabilities. There are other probabilistic provenances with more complex tags such as proof trees or boolean formulae. We therefore introduce, for each provenance TT, an input tag space II, an output tag space OO, a tagging function τ:I→T\tau:I\to T, and a recover function ρ:T→O\rho:T\to O. For instance, all probabilistic provenances share the same input and output tag spaces I=O=[0,1]I=O=[0,1] for a unified interface, while the internal tag spaces TT could be different. We call the 4-tuple (I,O,τ,ρ)(I,O,\tau,\rho) the

ProvenanceTT0011t1⊕t2t_1 \oplus t_2t1⊗t2t_1 \otimes t_2⊖t\ominus tt1=?t2t_1 \mathrel{\overset{?}{=}} t_2τ(ri)\tau(r_i)ρ(t)\rho(t)
diff-max-min-probD\mathbb{D}0^\hat{0}1^\hat{1}max⁡(t1,t2)\max(t_1,t_2)min⁡(t1,t2)\min(t_1,t_2)1−t^1-\hat{t}t1fst=t2fstt_1^{\mathrm{fst}}=t_2^{\mathrm{fst}}(ri,e⃗i)(r_i,\vec{e}_i)tt
diff-add-mult-probD\mathbb{D}0^\hat{0}1^\hat{1}clamp⁡(t1+t2)\operatorname{clamp}(t_1+t_2)t1⋅t2t_1\cdot t_21−t^1-\hat{t}true\mathrm{true}(ri,e⃗i)(r_i,\vec{e}_i)tt
diff-top-k-proofsΦ\Phi∅\varnothing{∅}\{\varnothing\}t1∨kt2t_1\lor_k t_2t1∧kt2t_1\land_k t_2¬kt\neg_k tt1==t2t_1==t_2{{pos⁡(i)}}\{\{\operatorname{pos}(i)\}\}WMC⁡(t,Γ)\operatorname{WMC}(t,\Gamma)

Table 11. Definitions of three differentiable provenances.

a^i=(ai,∇ai)∈D\hat{a}_i=(a_i,\nabla a_i)\in\mathbb{D}
0^=(0,0⃗)\hat{0}=(0,\vec{0})
1^=(1,0⃗)\hat{1}=(1,\vec{0})
a^1+a^2=(a1+a2,∇a1+∇a2)\hat{a}_1+\hat{a}_2=(a_1+a_2,\nabla a_1+\nabla a_2)
a^1⋅a^2=(a1⋅a2,a2⋅∇a1+a1⋅∇a2)\hat{a}_1\cdot\hat{a}_2=(a_1\cdot a_2,a_2\cdot\nabla a_1+a_1\cdot\nabla a_2)
−a^1=(−a1,−∇a1)-\hat{a}_1=(-a_1,-\nabla a_1)
min⁡(a^1,a^2)=a^i, where i=arg⁡min⁡i(ai)\min(\hat{a}_1,\hat{a}_2)=\hat{a}_i,\ \text{where }i=\arg\min_i(a_i)
max⁡(a^1,a^2)=a^i, where i=arg⁡max⁡i(ai)\max(\hat{a}_1,\hat{a}_2)=\hat{a}_i,\ \text{where }i=\arg\max_i(a_i)
clamp⁡(a^1)=(clamp⁡01(a1),∇a1)\operatorname{clamp}(\hat{a}_1)=(\operatorname{clamp}_0^1(a_1),\nabla a_1)

fig:12. Operations on dual-number D≔[0,1]×Rn\mathbb{D}\coloneqq[0,1]\times\mathbb{R}^n, where nn is the number of input probabilities.

(Variable)i∈1…n(Literal)ν::=pos⁡(i)∣neg⁡(i)(Proof)η::={ν1,ν2,…}(Formula)Φ∋φ::={η1,η2,…}\begin{aligned} &\text{(Variable)}\quad i\in1\ldots n\\ &\text{(Literal)}\quad\nu::=\operatorname{pos}(i)\mid\operatorname{neg}(i)\\ &\text{(Proof)}\quad\eta::=\{\nu_1,\nu_2,\ldots\}\\ &\text{(Formula)}\quad\Phi\ni\varphi::=\{\eta_1,\eta_2,\ldots\} \end{aligned}
φ1∨kφ2=top⁡k(φ1∪φ2)\varphi_1\lor_k\varphi_2=\operatorname{top}_k(\varphi_1\cup\varphi_2)
φ1∧kφ2=top⁡k({η∣(η1,η2)∈φ1×φ2, η=η1∪η2, η no conflict})\varphi_1\land_k\varphi_2=\operatorname{top}_k(\{\eta\mid(\eta_1,\eta_2)\in\varphi_1\times\varphi_2,\ \eta=\eta_1\cup\eta_2,\ \eta\text{ no conflict}\})
¬kφ=top⁡k(cnf2dnf⁡({{¬ν∣ν∈η}∣η∈φ}))\neg_k\varphi=\operatorname{top}_k(\operatorname{cnf2dnf}(\{\{\neg\nu\mid\nu\in\eta\}\mid\eta\in\varphi\}))
Γ(i)=(ri,e⃗i)\Gamma(i)=(r_i,\vec{e}_i)

fig:13. Definitions used for diff-top-k-proofs provenance.

external interface for a provenance TT. The whole execution pipeline is then illustrated below:

Foption⁡<I>→τFT→SclRam program, sˉFT′→ρFOF_{\operatorname{option}<I>}\xrightarrow{\tau}F_T\xrightarrow{\text{SclRam program},\ \bar{s}}F'_T\xrightarrow{\rho}F_O

In the context of a Scallop application, an EDB is provided in the form Foption⁡<I>F_{\operatorname{option}<I>}. During the tagging phase, τ\tau is applied to each input tag to obtain FTF_T, following which the SclRam program operates on FTF_T. For convenience, not all input facts need to be tagged—untagged input facts are simply associated by the tag 11 in FTF_T. In the recovery phase, ρ\rho is applied to obtain FOF_O, the IDB that the whole pipeline returns. Scallop allows the user to specify a set of output relations and ρ\rho is only applied to tags under such relations to avoid redundant computations.

Differentiable Reasoning with Provenance

We now elucidate how provenance also supports differentiable reasoning. Let all the probabilities in the EDB form a vector r⃗∈Rn\vec{r}\in\mathbb{R}^n, and the probabilities in the resulting IDB form a vector y⃗∈Rm\vec{y}\in\mathbb{R}^m. Differentiation concerns deriving output probabilities y⃗\vec{y} as well as the derivative ∇y⃗=∂y⃗∂r⃗\nabla\vec{y}=\frac{\partial\vec{y}}{\partial\vec{r}}.

In Scallop, one can obtain these using a differentiable provenance (DP). DPs share the same external interface—let the input tag space I=[0,1]I=[0,1] and output tag space OO be the space of dual-numbers D\mathbb{D} (Fig. 12). Now, each input tag ri∈[0,1]r_i\in[0,1] is a probability, and each output tag y^j=(yj,∇yj)\hat{y}_j=(y_j,\nabla y_j) encapsulates the output probability yjy_j and its derivative w.r.t. inputs, ∇yj\nabla y_j. From here, we can obtain our expected output y⃗\vec{y} and ∇y⃗\nabla\vec{y} by stacking together yjy_j's and ∇yj\nabla y_j's respectively.

Scallop provides 8 configurable built-in DPs with different empirical advantages in terms of runtime efficiency, reasoning granularity, and performance. In this section, we elaborate upon 3 simple but versatile DPs, whose definitions are shown in fig:11. In the following discussion, we use rir_i to denote the ii-th element of r⃗\vec{r}, where ii is called a variable (ID). Vector e⃗i∈Rn\vec{e}_i\in\mathbb{R}^n is the standard basis vector where all entries are 0 except the ii-th entry.

diff-max-min-prob (dmmp).

This provenance is the differentiable version of mmp. When obtaining rir_i from an input tag, we transform it into a dual-number by attaching e⃗i\vec{e}_i as its derivative. Note that throughout the execution, the derivative will always have at most one entry being non-zero and, specifically, 1 or −1. The saturation check is based on equality of the probability part only, so that the derivative does not affect termination. All of its operations can be implemented by algorithms with time complexity O(1)O(1), making it extremely runtime-efficient.

diff-add-mult-prob (damp)

This provenance has the same internal tag space, tagging function, and recover function as dmmp. As suggested by its name, its disjunction and conjunction operations are just + and · for dual-numbers. When performing disjunction, we clamp the real part of the dual-number obtained from performing +, while keeping the derivative the same. The saturation function for damp is designed to always returns true to avoid non-termination. But this decision makes it less suitable for complex recursive programs. The time complexity of operations in damp is O(n)O(n), which is slower than dmmp but still very efficient in practice.

diff-top-k-proofs (dtkp)

This provenance extends the top-k proofs semiring originally proposed in [31] to additionally support negation and aggregation. Shown in Fig. 11 and Fig. 13, the tags of dtkp are boolean formulas φ∈Φ\varphi\in\Phi in disjunctive normal form (DNF). Each conjunctive clause in the DNF is called a proof η\eta. A formula can contain at most kk proofs, where kk is a tunable hyper-parameter. Throughout execution, boolean formulas are propagated with ∨k\lor_k, ∧k\land_k, and ¬k\lnot_k, which resemble or, and, and not on DNF formulas. At the end of these computations, top⁡k\operatorname{top}_k is applied to keep only kk proofs with the highest proof probability:

Pr⁡(η)=∏ν∈ηPr⁡(ν),Pr⁡(pos⁡(i))=ri,Pr⁡(neg⁡(i))=1−ri.(1)\Pr(\eta) = \prod_{\nu\in\eta} \Pr(\nu), \qquad\Pr(\operatorname{pos}(i)) = r_i, \qquad\Pr(\operatorname{neg}(i)) = 1-r_i. \tag*{(1)}

When merging two proofs during ∧k\land_k, there might be conflicting literals, e.g. pos⁡(i)\operatorname{pos}(i) and neg⁡(i)\operatorname{neg}(i), in which case we remove the whole proof. To take negation ¬k\lnot_k on φ\varphi, we first negate all the literals to obtain a conjunctive normal form (CNF) equivalent to ¬φ\lnot\varphi. Then we perform cnf2dnf operation (conflict check included) to convert it back to a DNF. To obtain the output dual-number y^j\hat{y}_j from a DNF formula φj\varphi_j, the tag for jj-th output tuple, we adopt a differentiable weighted-model-counting (WMC) procedure [43]. WMC computes the weight of a boolean formula φj\varphi_j given the weights of individual variables. Concretely, y^j=WMC⁡(φj,Γ)\hat{y}_j = \operatorname{WMC}(\varphi_j,\Gamma) where Γ(i)=(ri,e⃗i)\Gamma(i) = (r_i,\vec{e}_i) is the mapping from variables to their dual-numbers. Note that WMC is #P-complete, and is the main contributor to the runtime when using this provenance. The tunable kk enables the user to balance between runtime and reasoning granularity. Detailed runtime analysis is shown in Appendix B.

Practical Considerations

We finally discuss some practical aspects concerning SclRAM extensions and provenance selection.

Additional Features. We only presented the syntax and semantics of the core fragment of SclRAM. SclRAM additionally supports the following useful features: 1) sampling operations, and the provenance extension supporting them, 2) group-by aggregations, 3) tag-based early removal and its extension in provenance, and 4) mutually exclusive tags in dtkp. We formalize these in Appendix B.

Provenance Selection. A natural question is how to select a differentiable provenance for a given Scallop application. Based on our empirical evaluation in § 6, dtkp is often the best performing one, and setting k=3k = 3 is usually a good choice for both runtime efficiency and learning performance. This suggests that a user can start with dtkp as the default. In general, the provenance selection process is similar to the process of hyperparameter tuning common in machine learning.

Implementation

We implemented the core Scallop system in 45K LoC of Rust. The LoC of individual modules is shown in Table 1. Within the compiler, there are two levels of intermediate representations, front-IR and back-IR, between the surface language and the ScLRAМ language. In front-IR, we perform analyses such as type inference and transformations such as desugaring. In back-IR, we generate query plans and apply optimizations. The runtime operates directly on ScLRAM and is based on semi-naive evaluation specialized for tagged

ModuleLoC
Compiler19K
Runtime16K
Interpreter2K
scallopy4K

Table 1. LoC of core Scallop modules.

semantics. There are dynamic and static runtimes for interpreted and compiled SclRam programs. Currently, all computation is on CPU only, but can be parallelized per-batch for machine learning.

Scallop can be used through different interfaces such as interpreter, compiler, and interactive terminal. It also provides language bindings such as scallopy for Python and scallop-wasm for WebAssembly and JavaScript. With scallopy, Scallop can be seamlessly integrated with machine learning frameworks such as PyTorch, wherein the scallopy module is treated just like any other PyTorch module. When jit is specified in scallopy, Scallop programs can be just-in-time (JIT) compiled to Rust, turned into binaries, and dynamically loaded into the Python environment.

Scallop provides 18 built-in provenances (4 for discrete reasoning, 6 for probabilistic, and 8 for differentiable). The WMC algorithm is implemented using sentential decision diagram (SDD) [19] with naive bottom-up compilation. We allow each provenance to provide its own implementation for operations such as aggregation and sampling. This gives substantial freedom and enables optimizations for complex operations. Our provenance framework is also interfaced with scallopy, allowing to quickly create and test new provenances in Python.

Evaluation

We evaluate the Scallop language and framework on a benchmark suite comprising eight neurosymbolic applications. Our evaluation aims to answer the following research questions:

RQ1 How expressive is Scallop for solving diverse neurosymbolic tasks?

RQ2 How do Scallop’s solutions compare to state-of-the-art baselines in terms of accuracy?

RQ3 Is the differentiable reasoning module of Scallop runtime-efficient?

RQ4 Is Scallop effective at improving generalizability, interpretability, and data-efficiency?

RQ5 What are the failure modes of Scallop solutions and how can we mitigate them?

In the following sections, we first introduce the benchmark tasks and the chosen baselines for each task (§ 6.1). Then, we answer RQ1 to RQ5 in § 6.2 to § 6.6 respectively. All Scallop related and runtime related experiments were conducted on a machine with two 20-core Intel Xeon CPUs, four GeForce RTX 2080 Ti GPUs, and 768 GB RAM.

Benchmarks and Baselines

We present an overview of our benchmarks in Figure 14. They cover a wide spectrum of tasks involving perception and reasoning. The input data modality ranges from images and videos natural language texts and knowledge bases (KB). The size of the training dataset is also presented in the figure. We next elaborate on the benchmark tasks and their corresponding baselines.

Figure 14. Visualization of benchmark tasks. Beside the name of each task we specify the size of the training dataset and the output domain. PacMan-Maze is omitted since it has been shown in § 2.

MNIST-R: A Synthetic MNIST Test Suite. This benchmark is designed to test various features of Scallop such as negation and aggregation. Each task takes as input one or more images of handwritten digits from the MNIST dataset [37] and performs simple arithmetic (sum2, sum3, sum4), comparison (less-than), negation (not-3-or-4), or counting (count-3, count-3-or-4) over the depicted digits. For count-3 and count-3-or-4, we count digits from a set of 8 images. For this test suite, we use a CNN-based model, DeepProbLog (DPL) [43], and our prior work [31] (Prior) as the baselines.

HWF: Hand-Written Formula Parsing and Evaluation. HWF, proposed in [39], concerns parsing and evaluating hand-written formulas. The formula is provided in the form of a sequence of images, where each image represents either a digit (0-9) or an arithmetic symbol (++, −-, ×\times, ÷\div). Formulas are well-formed according to a grammar and do not divide by zero. The size of the formulas ranges from 1 to 7 and is indicated as part of the input. The goal is to evaluate the formula to obtain a rational number as the result. We choose from [39] the baselines NGS-mm-BS, NGS-RL, and NGS-MAPO, which are neurosymbolic methods designed specifically for this task.

Pathfinder: Image Classification with Long-Range Dependency. In this task from [55], the input is an image containing two dots that are possibly connected by curved and dashed lines. The goal is to tell whether the dots are connected. There are two subtasks, Path and Path-X, where Path contains 32×3232 \times32 images and Path-X contains 128×128128 \times128 ones. We pick as baselines standard CNN and Transformer based models, as well as the state-of-the-art neural models S4 [27], S4* [28], and SGConv [40].

PacMan-Maze: Playing PacMan Maze Game. As presented in § 2, this task tests an agent’s ability to recognize entities in an image and plan the path for the PacMan to reach the goal. An RL environment provides the game state image as input and the agent must plan the optimal action {up, down, left, right} to take at each step. There is no “training dataset” as the environment is randomized for every session. We pick as baseline a CNN based Deep-Q-Network (DQN). Unlike other tasks, we use the “success rate” metric for evaluation, i.e., among 1000 game sessions, we measure the number of times the PacMan reaches the goal within a certain time-budget.

CLUTRR: Kinship Reasoning from Natural Language Context. In this task from [53], the input contains a natural language (NL) passage about a set of characters. Each sentence in the passage hints at kinship relations. The goal is to infer the relationship between a given pair of characters. The target relation is not stated explicitly in the passage and it must be deduced through a reasoning chain. Our baseline models include RoBERTa [42], BiLSTM [25], GPT-3-FT (fine-tuned), GPT-3-ZS (zero-shot), and GPT-3-FS (5-shot) [9]. In an alternative setup, CLUTRR-G, instead of the NL passage, the structured kinship graph corresponding to the NL passage is provided, making it a Knowledge Graph Reasoning problem. For CLUTRR-G, we pick GAT [58] and CTP [45] as baselines.

Mugen: Video-Text Alignment and Retrieval. Mugen [30] is based on a game called CoinRun [15]. In the video-text alignment task, the input contains a 3.2 second long video of gameplay footage and a short NL paragraph describing events happening in the video. The goal is to compute a similarity score representing how “aligned” they are. There are two subsequent tasks, Video-to-Text Retrieval (VTR) and Text-to-Video Retrieval (TVR). In TVR, the input is a piece of text and a set of 16 videos, and the goal is to retrieve the video that best aligns with the text. In VTR, the goal is to retrieve text from video. We compare our method with SDSC [30].

CLEVR: Compositional Language and Elementary Visual Reasoning [34]. In this visual question answering (VQA) task, the input contains a rendered image of geometric objects and a NL question that asks about counts, attributes, and relationships of objects. The goal is to answer the question based on the image. We pick as baselines NS-VQA [63] and NSCL [44], which are neurosymbolic methods designed specifically for this task.

VQAR: Visual-Question-Answering with Common-Sense Reasoning. This task, like CLEVR, also concerns VQA but with three salient differences: it contains real-life images from the GQA dataset [32]; the queries are in a programmatic form, asking to retrieve objects in the image; and there is an additional input in the form of a common-sense knowledge base (KB) [22] containing triplets such as (giraffe, is-a, animal) for common-sense reasoning. The baselines for this task are NMNs [4] and LXMERT [54].

RQ1: Our Solutions and Expressivity

To answer RQ1, we demonstrate our Scallop solutions to the benchmark tasks (Table 2). For each task, we specify the interface relations which serve as the bridge between the neural and symbolic components. The neural modules process the perceptual input and their outputs are mapped to (probabilistic) facts in the interface relations. Our Scallop programs subsequently take these facts as input and perform the described reasoning to produce the final output. As shown by the features column, our solutions use all of the core features provided by Scallop.

The complete Scallop program for each task is provided in the Appendix § 14. These programs are succinct, as indicated by the LoCs in the last column of Table 2. We highlight three tasks, HWF, Mugen, and CLEVR, to demonstrate Scallop’s expressivity. For HWF, the Scallop program consists of a formula parser. It is capable of parsing probabilistic input symbols according to a context-free grammar for simple arithmetic expressions. For Mugen, the Scallop program is a *temporal specification checker, where the specification is extracted from NL text to match the sequential events excerpted from the video. For CLEVR, the Scallop program is an interpreter for CLEVR-DSL, a domain-specific functional language introduced in the CLEVR dataset [34].

TaskInputNeural NetInterface Relation(s)Scallop ProgramRNALoC
MNIST-RImagesCNNdigit(idid, digitdigit)Arithmetic, comparison, negation, and counting.✓✓2†
HWFImagesCNNsymbol(idid, symbolsymbol)<br>length(lenlen)Parses and evaluates formula over recognized symbols.✓39
PathfinderImageCNNdot(idid)<br>dash(from_idfrom\_id, to_idto\_id)Checks if the dots are connected by dashes.✓4
PacMan-MazeImageCNNactor(xx, yy)<br>enemy(xx, yy)<br>goal(xx, yy)Plans the optimal action by finding an enemy-free path from actor to goal.✓✓✓31
CLUTRR (-G)NL<br>Query*<br>RuleRoBERTa<br>–<br>–kinship(relarela, subsub, objobj)<br>question(subsub, objobj)<br>composition(r1r_1, r2r_2, r3r_3)Deduces queried relationship by recursively applying learnt composition rules.✓✓✓8
MugenVideo<br>NLS3D<br>DistilBERTaction(frameframe, actionaction, modmod)<br>expr(expr_idexpr\_id, actionaction)<br>mod(expr_idexpr\_id, modmod)Checks if events specified in NL text match the actions recognized from the video.✓✓✓46
CLEVRImage<br>NLFastRCNN<br>BiLSTMobj_attr(obj_idobj\_id, attrattr, valval)<br>obj_rela(relarela, o1o_1, o2o_2)<br>filter_expr(ee, cece, attrattr, valval)<br>count_expr(ee, cece), …Interprets CLEVR-DSL program (extracted from question) on scene graph (extracted from image).✓✓✓51
VQARImage<br>KB*FastRCNN<br>–obj_name(obj_idobj\_id, namename)<br>obj_attr(obj_idobj\_id, valval)<br>obj_rela(relarela, o1o_1, o2o_2)<br>is_a(name1name1, name2name2), …Evaluates query over scene graphs (extracted from image) with the aid of common-sense knowledge base (KB).✓42

Table 2. Characteristics of Scallop solutions for each task. Structured input which is not learnt is denoted by *. Neural models used are RoBERTa [42], DistilBERT [49], and BiLSTM [25] for natural language (NL), CNN and FastRCNN [24] for images, and S3D [60] for video. We show the three key features of Scallop used by each solution: (R)ecursion, (N)egation, and (A)ggregation. †: For MNIST-R, the LoC is 2 for every subtask.

HWF learning curve

Figure 16. HWF learning curve.

We note that our prior work [31], which only supports positive Datalog, cannot express 5 out of the 8 tasks since they need negation and aggregation, as indicated by columns ‘N’ and ‘A’. Moreover, HWF requires floating point support which is also lacking in our prior work.

Besides diverse kinds of perceptual data and reasoning patterns, the Scallop programs are applied in a variety of learning settings. As shown in § 2, the program for PacMan-Maze is used in a online representation learning setting. For CLUTRR, we write integrity constraints (similar to the one shown in § 3.2) to derive semantic loss used for constraining the language model outputs. For CLUTRR-G, learnable weights are attached to composition facts such as composition(FATHER, MOTHER, GRANDMOTHER), which enables to learn such facts from data akin to rule learning in ILP. For Mugen, our program is trained in a contrastive learning setup, since it requires to maximize similarity scores between aligned video-text pairs but minimize that for un-aligned ones.

RQ2: Performance and Accuracy

To answer RQ2, we evaluate the performance and accuracy of our methods in terms of two aspects: 1) the best performance of our solutions compared to existing baselines, and 2) the performance of our solutions with different provenance structures (dmmp, damp, dtkp with different kk).

We start with comparing our solutions against selected baselines on all the benchmark tasks, as shown in Figure 15, Table 3, and Figure 17. First, we highlight two applications, PacMan-Maze and CLUTRR, which benefit the most from our solutions. For PacMan-Maze, compared to DQN, we obtain a 1,000X speed-up in terms of training episodes, and a near perfect success rate of 99.4%. Note that our solution encodes environment dynamics (i.e. game rules) which are unavailable and hard to incorporate in the DQN model. For CLUTRR, we obtain a 25% improvement over baselines, which includes GPT-3-FT, the state-of-the-art large language model fine-tuned on the CLUTRR dataset. Next, for tasks such as HWF and CLEVR, our solutions attain comparable performance, even compared to neurosymbolic baselines NGS-mm-BS, NSCL, and NS-VQA specifically designed for each task. On Path and Path-X, our solution obtains a 4% accuracy gain over our underlying model CNN and even outperforms a carefully designed transformer based model S4.

MNIST-R suite accuracy comparison

Figure 15. MNIST-R suite accuracy comparison.

MethodScallopDQN
dmmpdampdtkp-1
Succ Rate8.80%7.84%99.40%84.90%
#Episodes50505050K

Table 3. PacMan-Maze performance.

Figure 17. Overall benchmark accuracy comparison. The best-performing provenance structure for our solution is indicated for each task. Among the shown tasks, dtkp performs the best on 6 tasks, damp on 2, and dmmp on 1.

The performance of the Scallop solution for each task depends on the chosen provenance structure. As can be seen from Table 3 and Figure 15–Figure 17, although dtkp is generally the best-performing one, each presented provenance is useful, e.g., dtkp for PacMan-Maze and VQAR, damp for less-than (MNIST-R) and Mugen, and dmmp for HWF and CLEVR. Note that under positive Datalog, Scallop’s dtkp is identical to [31], allowing us to achieve similar performance. In conclusion, allowing configurable provenance helps tailor our methods to different applications.

RQ3: Runtime Efficiency

We evaluate the runtime efficiency of Scallop solutions with different provenance structures and compare it against baseline neurosymbolic approaches. As shown in Table 4, Scallop achieves substantial speed-up over DeepProbLog (DPL) on MNIST-R tasks. DPL is a probabilistic programming system based on Prolog using exact probabilistic reasoning. As an example, on sum4, DPL takes 40 days to finish only 4K training samples, showing that it is prohibitively slow to use in practice. On the contrary, Scallop solutions can finish a training epoch (15K samples) in minutes without sacrificing testing accuracy (according to Figure 15). For HWF, Scallop achieves comparable runtime efficiency, even when compared against the hand-crafted and specialized NGS-mm-BS method.

Comparing among provenance structures, we see significant runtime blowup when increasing kk for dtkp. This is expected as increasing kk results in larger boolean formula tags, making the WMC procedure exponentially slower. In practice, we find k=3k = 3 for dtkp to be a good balance point between runtime efficiency and reasoning granularity. In fact, dtkp generalizes DPL, as one can set an extremely large k≥2nk \ge2^n (nn is the total number of input facts) for exact probabilistic reasoning.

RQ4: Generalizability, Interpretability, and Data-Efficiency

We now consider other important desirable aspects of machine learning models besides accuracy and runtime, such as generalizability on unseen inputs, interpretability of the outputs, and data-efficiency of the training process. For brevity, we focus on a single benchmark task in each case.

We evaluate Scallop’s generalization ability for the CLUTRR task. Each data-point in CLUTRR is annotated with a parameter kk denoting the length of the reasoning chain to infer the target kinship relation. To test different solutions’ systematic generalizability, we train them on data-points with k∈{2,3}k \in\{2,3\} and test on data-points with k∈{2,…,10}k \in\{2,\ldots,10\}. As shown in Figure 18, the neural baselines suffer a steep drop in accuracy on the more complex unseen instances, whereas the accuracy of Scallop’s solution degrades more slowly, indicating that it is able to generalize better.

Line chart showing systematic generalizability on the CLUTRR dataset

Figure 18. Systematic generalizability on CLUTRR dataset.

Next, we demonstrate Scallop’s interpretability on the Mugen task. Although the goal of the task is to see whether a video-text pair is aligned, the perceptual model in our method extracts interpretable symbols, i.e., the action of the controlled character at a certain frame. Figure 19 shows that the predicted (action, mod) pairs perfectly match the events in the video. Thus, our solution not only tells whether a video-text pair is aligned, but also why it is aligned.

Figure 19. The predicted most likely (action, mod) pair for example video segments from Mugen dataset.

Lastly, we evaluate Scallop’s data-efficiency on the HWF task, using lesser training data (Table 5). While methods such as NGS-MAPO suffer significantly when trained on less data, Scallop’s testing accuracy decreases slowly, and is comparable to the data-efficiency of the state-of-the-art

%TrainScallop dtkp-5NGS RLNGS MAPONGS mm-BS
100%97.853.471.798.5
50%95.73.69.595.7
25%92.953.55.193.3

Table 5. Testing accuracy of various methods on HWF when trained with only a portion of the data. Numbers are in percentage (%).

Taskdmmpdampdtkp-3dtkp-10Baseline
sum234887218521,430 (DPL)
sum334119711,43030,898 (DPL)
sum434154774,329timeout (DPL)
less-than354234432,540 (DPL)
not-3-or-4373333343,218 (DPL)
HWF891071208,43579 (NGS-mm-BS)
CLEVR1,9641,6182,325timeout–

caption: Runtime efficiency comparison on selected benchmark tasks. Numbers shown are average training time (sec.) per epoch. Our variants attaining the best accuracy are indicated in bold.

:::

neurosymbolic NGS-mm-BS method. PacMan-Maze task also demonstrates Scallop’s data-efficiency, as it takes much less training episodes than DQN does, while achieving much higher success rate.

RQ5: Analysis of Failure Modes

Compared to purely neural models, Scallop solutions provide more transparency, allowing programmers to debug effectively. By manually checking the interface relations, we observed that the main source of error lies in inaccurate predictions from the neural components. For example, the RoBERTa model for CLUTRR correctly extracts only 84.69% of kinship relations. There are two potential causes—either the neural component is not powerful enough, or our solution is not providing adequate supervision to train it. The former can be addressed by employing better neural architectures or more data. The latter can be mitigated in different ways, such as tuning the selected provenance or incorporating integrity constraints (discussed in § 3.2) into training and/or inference. For instance, in PacMan-Maze, a constraint that “there should be no more than one goal in the arena” helps to improve robustness.

Related Work

We survey related work in four different but overlapping domains: provenance reasoning, Datalog and logic programming, probabilistic and differentiable programming, and neurosymbolic methods.

Relational Algebra and Provenance. Relational algebra is extensively studied in databases [2], and extended with recursion [33] in Datalog. The provenance semiring framework [26] was first proposed for positive relational algebra (RA+^{+}) and later extended with difference [3] and fixed-point [18]. It is deployed in variants of Datalog [36] and supports applications such as program synthesis [52]. Scallop employs an extended provenance semiring framework and demonstrates its application to configurable differentiable reasoning.

Datalog is a declarative logic programming language where rules are logical formulas. Despite being less expressive than Prolog, it is widely studied in both the programming language and database communities for language extensions and optimizations [36]. A variety of Datalog-based systems has been built for program analysis [50] and enterprise databases [5]. Scallop is also a Datalog-based system that extends [31] with numerous language constructs such as negation and aggregation.

Probabilistic Programming is a paradigm for programmers to model distributions and perform probabilistic sampling and inference. Such systems include ProbLog [21], Pyro [7], Turing [23], and PPL [van de Meent et al. 2018]. When integrated with modern ML systems, they are well suited for statistical modeling and building generative models. Scallop also supports ProbLog-style exact probabilistic inference as one instantiation of our provenance framework. But advanced statistical sampling and generative modeling is not yet supported and left for future work.

Differentiable Programming (DP) systems seek to enable writing code that is differentiable. Common practices for DP include symbolic differentiation and automatic differentiation (auto-diff) [6], resulting in popular ML frameworks such as PyTorch [47], TensorFlow [1], and JAX [8]. However, most of these systems are designed for real-valued functions. Scallop is also a differentiable programming system, but with a focus on programming with discrete, logical, and relational symbols.

Neurosymbolic Methods have emerged to incorporate symbolic reasoning into existing learning systems. Their success has been demonstrated in a number of applications [13, 39, 44, 45, 59, 62, 63]. Similar to [39, 44, 63], we focus primarily on solutions involving perception followed by symbolic reasoning. Other ways of incorporating symbolic knowledge include semantic loss [61, 62], program synthesis [12, 51], and invoking large language models (LLMs) [14, 64]. Most aforementioned neurosymbolic methods build their own domain-specific language or specialized reasoning components, many of which are programmable in Scallop and are instantiations of our provenance framework [13, 44, 61, 62]. TensorLog [16], DPL [43], and [31] can be viewed as unified neurosymbolic frameworks of varying expressivity. Scallop is inspired by DPL, and additionally offers a more scalable, customizable, and easy-to-use language and framework.

Conclusion

We presented Scallop, a neurosymbolic programming language for integrating deep learning and logical reasoning. We introduced a declarative language and a reasoning framework based on provenance computations. We showed that our framework is practical by applying it to a variety of machine learning tasks. In particular, our experiments show that Scallop solutions are comparable and even supersede many existing baselines.

In the future, we plan to extend Scallop in three aspects: 1) Supporting more machine learning paradigms, such as generative modeling, open domain reasoning, in-context learning, and adversarial learning. 2) Further enhancing the usability, efficiency, and expressiveness of Scallop’s language and framework. We intend to provide bindings to other ML frameworks such as TensorFlow and JAX, leverage hardware such as GPUs to accelerate computation, and support constructs such as algebraic data types. 3) Applying Scallop to real-world and safety-critical domains. For instance, we intend to integrate it with the CARLA driving simulator [20] to specify soft temporal constraints for autonomous driving systems. We also intend to apply Scallop in the medical domain for explainable disease diagnosis from electronic health records (EHR) data.

Acknowledgement

We thank Neelay Velingker, Hanjun Dai, Hanlin Zhang, and Sernam Lin for helpful comments on the presentation and experiments. We thank the anonymous reviewers and artifact reviewers for useful feedback. This research was supported by grants from DARPA (#FA8750-19-2-0201), NSF (#2107429 and #1836936), and ONR (#N00014-18-1-2021).

Artifact Availability

All software necessary to reproduce the experiments in this paper is available at [41]. Additionally, the latest source code of Scallop and its documentation is available at https://github.com/scallop-lang/scallop.

References

A Scallop Language Syntax

In this appendix, we provide the abstract syntax of the full language of Scallop in Figure 20.

item::=@attrName(attrArg∗)defdef::=importDef∣typeDef∣constDef∣relaDef∣queryDefimportDef::=import filetypeDef::=type typeName=aliasName∣type typeName<:superTypeName∣type relationName([name:]type∗)constDef::=const constName[:type]=constantrelaDef::=rel [tag::]relaName(expr∗)∣rel relaName={taggedTuple∗}∣rel [tag::]atom:−formulataggedTuple::=[tag::](constant∗)atom::=relaName(expr∗)formula::=formula and formula∣formula or formula∣formula implies formula∣atom∣¬atom∣constraint∣reducereduce::=var∗=aggregator(var∗:formula [where var∗:formula])∣var∗=sampler(var∗:formula [where var∗:formula])constraint::=exprtype::=u8∣u16∣u32∣u64∣usize∣i8∣i16∣i32∣i64∣isize∣f32∣f64∣bool∣char∣Stringexpr::=expr binOp expr∣unaryOp expr∣expr as type∣if expr then expr else expr∣$func(expr∗)∣variable∣constantbinOp::=+∣−∣∗∣/∣%∣&&∣∥∥∣==∣!=∣<∣<=∣>∣>=unaryOp::=!∣−aggregator::=min∣max∣argmin<var∗>∣argmax<var∗>∣count∣sum∣prod∣exists∣forallsampler::=top<K>∣categorical<K>∣uniform<K>\begin{aligned} \mathit{item} &::= @\mathit{attrName}(\mathit{attrArg}^{*})\mathit{def}\\ \mathit{def} &::= \mathit{importDef}\mid\mathit{typeDef}\mid\mathit{constDef}\mid\mathit{relaDef}\mid\mathit{queryDef}\\ \mathit{importDef} &::= \mathit{import}\ \mathit{file}\\ \mathit{typeDef} &::= \mathit{type}\ \mathit{typeName}=\mathit{aliasName}\mid\mathit{type}\ \mathit{typeName}<:\mathit{superTypeName}\\ &\quad\mid\mathit{type}\ \mathit{relationName}([\mathit{name}:]\mathit{type}^{*})\\ \mathit{constDef} &::= \mathit{const}\ \mathit{constName}[:\mathit{type}]=\mathit{constant}\\ \mathit{relaDef} &::= \mathit{rel}\ [\mathit{tag}::]\mathit{relaName}(\mathit{expr}^{*})\mid\mathit{rel}\ \mathit{relaName}=\{\mathit{taggedTuple}^{*}\}\\ &\quad\mid\mathit{rel}\ [\mathit{tag}::]\mathit{atom}:-\mathit{formula}\\ \mathit{taggedTuple} &::= [\mathit{tag}::](\mathit{constant}^{*})\\ \mathit{atom} &::= \mathit{relaName}(\mathit{expr}^{*})\\ \mathit{formula} &::= \mathit{formula}\ \mathit{and}\ \mathit{formula}\mid\mathit{formula}\ \mathit{or}\ \mathit{formula}\mid\mathit{formula}\ \mathit{implies}\ \mathit{formula}\\ &\quad\mid\mathit{atom}\mid\lnot\mathit{atom}\mid\mathit{constraint}\mid\mathit{reduce}\\ \mathit{reduce} &::= \mathit{var}^{*}=\mathit{aggregator}(\mathit{var}^{*}:\mathit{formula}\ [\mathit{where}\ \mathit{var}^{*}:\mathit{formula}])\\ &\quad\mid\mathit{var}^{*}=\mathit{sampler}(\mathit{var}^{*}:\mathit{formula}\ [\mathit{where}\ \mathit{var}^{*}:\mathit{formula}])\\ \mathit{constraint} &::= \mathit{expr}\\ \mathit{type} &::= \mathit{u8}\mid\mathit{u16}\mid\mathit{u32}\mid\mathit{u64}\mid\mathit{usize}\mid\mathit{i8}\mid\mathit{i16}\mid\mathit{i32}\mid\mathit{i64}\mid\mathit{isize}\mid\mathit{f32}\mid\mathit{f64}\mid\mathit{bool}\mid\mathit{char}\mid\mathit{String}\\ \mathit{expr} &::= \mathit{expr}\ \mathit{binOp}\ \mathit{expr}\mid\mathit{unaryOp}\ \mathit{expr}\mid\mathit{expr}\ \mathit{as}\ \mathit{type}\mid\mathit{if}\ \mathit{expr}\ \mathit{then}\ \mathit{expr}\ \mathit{else}\ \mathit{expr}\\ &\quad\mid\$\mathit{func}(\mathit{expr}^{*})\mid\mathit{variable}\mid\mathit{constant}\\ \mathit{binOp} &::= +\mid-\mid*\mid/\mid\%\mid\&\&\mid\Vert\Vert\mid==\mid!=\mid<\mid<=\mid>\mid>=\\ \mathit{unaryOp} &::= !\mid-\\ \mathit{aggregator} &::= \mathit{min}\mid\mathit{max}\mid\mathit{argmin}<\mathit{var}^{*}>\mid\mathit{argmax}<\mathit{var}^{*}>\mid\mathit{count}\mid\mathit{sum}\mid\mathit{prod}\mid\mathit{exists}\mid\mathit{forall}\\ \mathit{sampler} &::= \mathit{top}<K>\mid\mathit{categorical}<K>\mid\mathit{uniform}<K> \end{aligned}

Figure 20. Language grammar (var\mathit{var} : variable\mathit{variable} and ff : formula\mathit{formula}).

B Reasoning Framework

In this appendix, we provide the extensions to our provenance framework, and illustrate the additional features provided by full ScLRAM.

Provenance Extensions

We present the full provenance interface including two additional features, early removal and weight for sampling, in Figure 21. For early removal, we introduce a function discard where it returns a boolean value based on a tag. When returned true, the fact associated with this tag will be early removed from the computation. For sampling, we allow each provenance to implement a function weight that returns a real number in R\mathbb{R} representing the weight of the tag. These features will be used later when we introduce the full ScLRAM syntax and semantics.

(Tag)t∈T(False)0∈T(True)1∈T(Disjunction)⊕:T×T→T(Conjunction)⊗:T×T→T(Negation)⊖:T→T(Saturation)⊙:T×T→Bool(Early Removal)discard:T→Bool(Weight)weight:T→R\begin{aligned} (\mathrm{Tag})\quad&t\in T\\ (\mathrm{False})\quad&\mathbf{0}\in T\\ (\mathrm{True})\quad&\mathbf{1}\in T\\ (\mathrm{Disjunction})\quad&\oplus:T\times T\to T\\ (\mathrm{Conjunction})\quad&\otimes:T\times T\to T\\ (\mathrm{Negation})\quad&\ominus:T\to T\\ (\mathrm{Saturation})\quad&\odot:T\times T\to\mathrm{Bool}\\ (\mathrm{Early\ Removal})\quad&\mathit{discard}:T\to\mathrm{Bool}\\ (\mathrm{Weight})\quad&\mathit{weight}:T\to\mathbb{R} \end{aligned}

Figure 21. Full interface for a provenance structure.

(Predicate)p(Aggregator)g::=count⁡∣sum⁡∣prod⁡∣exists⁡∣max⁡∣min⁡∣argmax⁡∣argmin⁡(Sampler)μ::=top⁡⟨K⟩∣categorical⁡⟨K⟩∣uniform⁡⟨K⟩(Expression)e::=∅∣p∣1(e)∣∅(e)∣γg(e)∣γ^g(e1,e2)∣ψμ(e)∣ψ^μ(e1,e2)∣πα(e)∣σβ(e)∣e1∪e2∣e1×e2∣e1⋈e2∣e1∩e2∣e1−e2(Rule)r::=p←e(Stratum)s::={r1,…,rn}(Program)s‾::=s1;…;sn\begin{aligned} (\text{Predicate})\quad&p\\ (\text{Aggregator})\quad&g ::= \operatorname{count}\mid\operatorname{sum}\mid\operatorname{prod}\mid\operatorname{exists}\mid\operatorname{max}\mid\operatorname{min}\mid\operatorname{argmax}\mid\operatorname{argmin}\\ (\text{Sampler})\quad&\mu::= \operatorname{top}\langle K\rangle\mid\operatorname{categorical}\langle K\rangle\mid\operatorname{uniform}\langle K\rangle\\ (\text{Expression})\quad&e ::= \emptyset\mid p\mid\mathbf{1}(e)\mid\emptyset(e)\mid\gamma_g(e)\mid\widehat{\gamma}_g(e_1,e_2)\mid\psi_\mu(e)\mid\widehat{\psi}_\mu(e_1,e_2)\mid\pi_\alpha(e)\mid\sigma_\beta(e)\\ &\qquad\mid e_1\cup e_2\mid e_1\times e_2\mid e_1\bowtie e_2\mid e_1\cap e_2\mid e_1-e_2\\ (\text{Rule})\quad&r ::= p\leftarrow e\\ (\text{Stratum})\quad&s ::= \{r_1,\ldots,r_n\}\\ (\text{Program})\quad&\overline{s} ::= s_1;\ldots;s_n \end{aligned}

Fig. 22. Full abstract syntax of SclRam.

Abstract Syntax of SclRam

We revisit the abstract syntax of SclRam, and add extensions including:

  1. Empty-set (∅\emptyset), One-overwrite (1(e)\mathbf{1}(e)) and zero-overwrite (∅(e)\emptyset(e)),

  2. Intersection (∩\cap), Natural-Join (⋈\bowtie), and Anti-join (▹\triangleright),

  3. Group-by aggregate (γ^g(e1,e2)\widehat{\gamma}_g(e_1,e_2)), where e1e_1 is the expression finding groups, and e2e_2 is the main expression to aggregate over, conditioned on the groups found by evaluating e1e_1,

  4. Sampling (ψμ(e)\psi_\mu(e)) where μ\mu denotes a sampler,

  5. Group-by sampling (ψ^μ(e1,e2)\widehat{\psi}_\mu(e_1,e_2)), which is sampling but similar to aggregate, we have e1e_1 being the expression finding groups.

Remark. The One-overwrite 1(e)\mathbf{1}(e) is particularly useful for defining magic-set transformation under tagged semantics. Overwriting 1\mathbf{1} will make the tuples in magic-set predicate serve as pure demand fact for optimization, not conditioned on some given tags.

Operational Semantics of SclRam

We show the full semantics in Figure 23 and Figure 24, with the addition of group-by, sampling, and early-removal. Note that the sampler μ:UR→U\mu: U^{R}\to U takes in facts tagged by weights, and samples according to the weight. The early removal happens in the stage of normalization before each rule update.

Image not extracted

Figure 23. Operational semantics of SclRam.

Operational semantics of SclRam (Cont.)

Figure 24. Operational semantics of SclRam (Cont.)

Provenance Structures

We provide detailed runtime analysis for each presented provenance structure in the following sections. Additionally, we discuss the extended provenance diff-top-k-proofs-me which can handle mutual exclusive facts.

diff-max-min-prob.

Runtime Analysis. We showcase the time complexity for each operator in the max-min-prob provenance structure in Table 6. We next present our optimized counting algorithm in Figure 1 which performs counting over a set of max-min-prob tagged-tuples. Note that we only showed the algorithm for mmp for simplicity. But it easily extends to dmmp. It can be easily shown that its runtime complexity is O(nlog⁡(n))O(n\log(n)).

OperationAlgorithmTime Complexity
t1⊕t2t_1 \oplus t_2max⁡(t1,t2)\max(t_1,t_2)O(1)O(1)
t1⊗t2t_1 \otimes t_2min⁡(t1,t2)\min(t_1,t_2)O(1)O(1)
⊖t\ominus t1^−t\hat{1}-tO(1)O(1)
t1=∘t2t_1 =_{\circ} t_2t1==t2t_1 == t_2O(1)O(1)
ρ(t)\rho(t)ttO(1)O(1)

Table 6. diff-max-min-prob provenance structure run time analysis

diff-add-mult-prob.

Runtime Analysis. We showcase the time complexity for the diff-add-mult-prob provenance structure in Table 7. We denote the number of total variables in the input as nn. Since we are performing calculations over the dual-numbers, the time complexity is decided by the gradient calculation over vectors of dimension nn.

OperationAlgorithmTime Complexity
t1⊕t2t_1 \oplus t_2clamp⁡(t1+t2)\operatorname{clamp}(t_1+t_2)O(n)O(n)
t1⊗t2t_1 \otimes t_2t1⋅t2t_1 \cdot t_2O(n)O(n)
⊖t\ominus t1^−t\hat{1}-tO(n)O(n)
t1=∘t2t_1 =_{\circ} t_2trueO(1)O(1)
ρ(t)\rho(t)ttO(1)O(1)

Table 7. diff-add-mult-prob provenance structure run time analysis

Algorithm 1: Counting over max-min-prob tagged tuples

Data: U_mmp = {t₁ :: u₁, t₂ :: u₂, . . . , tₙ :: uₙ}: U_mmp, set of tagged-tuples
Result: U′_mmp: U_mmp

/* sort all positive tuples according to their tags from small to large. O(nlog(n)) */
1 tᵖᵒˢ = sorted([tᵢ | i = 1 . . . n]);
2 tⁿᵉᵍ = [1 − tᵖᵒˢₙ₋ᵢ₊₁ | i = 1 . . . n];

/* Iterate through all possible partitions between positive and negative tags. O(n) */
3 U′_mmp = {tⁿᵉᵍₙ :: 0, tᵖᵒˢ₁ :: n};
4 for i = 1 . . . (n − 1) do
5     Add min(tᵖᵒˢᵢ₊₁, tⁿᵉᵍᵢ) :: (n − i) to U′_mmp;
6 return U′_mmp

diff-top-k-proofs.

Runtime Analysis. We showcase the time complexity for the diff-top-k-proofs provenance structure in Table 8. Note that we show the runtime analysis for the naive implementation of the cnf2dnf function and weighted model counting process. We leave the optimizations for future work.

OperationAlgorithmTime Complexity
t1⊕t2t_1 \oplus t_2top⁡k(t1∪t2)\operatorname{top}_k(t_1 \cup t_2)O(nk)O(nk)
t1⊗t2t_1 \otimes t_2top⁡k({η∣(η1,η2)∈t1×t2, η=η1∪η2, η no conflict})\operatorname{top}_k(\{\eta\mid(\eta_1,\eta_2)\in t_1 \times t_2,\ \eta=\eta_1\cup\eta_2,\ \eta\ \text{no conflict}\})O(n2k2)O(n^2k^2)
⊖t\ominus ttop⁡k(cnf2dnf⁡({{¬ν∣ν∈η}∣η∈t}))\operatorname{top}_k(\operatorname{cnf2dnf}(\{\{\neg\nu\mid\nu\in\eta\}\mid\eta\in t\}))O(2n)O(2^n)
t1=∘t2t_1 =_{\circ} t_2t1==t2t_1 == t_2O(nk)O(nk)
ρ(t)\rho(t)WMC⁡(t,Γ)\operatorname{WMC}(t,\Gamma)O(2n)O(2^n)

Table 8. diff-top-k-proofs provenance structure run time analysis. We assume the term number for each tag is of O(n)O(n), and the number of clauses is of O(k)O(k). Note that we show the time complexity for the naive implementation of cnf2dnf and WMC algorithms.

diff-top-k-proofs-me.

Support for Mutually Exclusive Facts. We keep the original diff-top-k-proofs and extend it to support mutal exclusive tags (hence the name -me). Most of the operations remains, and we start by giving it a new input tag space:

Idtkp−me=[0,1]×Option⁡⟨N⟩.I_{\mathrm{dtkp-me}} = [0,1] \times\operatorname{Option}\langle\mathbb{N}\rangle.

The probability remains the same, and the second part is an optional identifier of one mutual exclusion. Not providing that means the fact does not belong to a mutual exclusion. If presented, we denote such a tag

ti=(ri,Some⁡(mei))t_i = (r_i, \operatorname{Some}(\mathbf{me}_i))

Example B.1. Consider the sum2 task, we have two distributions specified by

rel digit = {0.90::(A, 0); 0.01::(A, 1); ...; 0.02::(A, 9)}
rel digit = {0.01::(B, 0); 0.91::(B, 1); ...; 0.01::(B, 9)}

Then we would have the input facts being

⟦digit⟧(Foption⟨I⟩)={(0.90,Some⁡(1))::(A,0),(0.01,Some⁡(1))::(A,1),⋮(0.02,Some⁡(1))::(A,9),(0.01,Some⁡(2))::(B,0),(0.91,Some⁡(2))::(B,1),⋮(0.01,Some⁡(2))::(B,9)\llbracket\mathrm{digit}\rrbracket(F_{\mathrm{option}\langle I\rangle}) = \left\{ \begin{aligned} &(0.90,\operatorname{Some}(1)) &&:: (A,0),\\ &(0.01,\operatorname{Some}(1)) &&:: (A,1),\\ & &&\vdots\\ &(0.02,\operatorname{Some}(1)) &&:: (A,9),\\ &(0.01,\operatorname{Some}(2)) &&:: (B,0),\\ &(0.91,\operatorname{Some}(2)) &&:: (B,1),\\ & &&\vdots\\ &(0.01,\operatorname{Some}(2)) &&:: (B,9) \end{aligned} \right.

There are two me-s, namely 1 and 2, suggesting there are two mutual exclusions. The first 10 facts for digit AA belong to mutual exclusion 1, and the next 10 for digit BB belong to mutual exclusion 2.

Putting it in action, two facts fif_i and fjf_j with the same me (mei=mej\mathbf{me}_i = \mathbf{me}_j) cannot appear together in the same proof. This is enforced inside of the conflict check during dtkp’s Λk\Lambda_k and ¬k\neg_k operations. If the proof violates the mutual exclusive assumption, it will be deemed invalid proof and discarded. For example, executing the following rule

rel not_possible() = digit(A, x), digit(A, y), x != y

shall yield no valid output due to this mechanism, i.e., the internal tag associated with not_possible() is going to be ∅\varnothing and be early-removed from the computation.

Evaluation

MNIST-R

Experimental Setup. The total MNIST[37] dataset contains 60K handwritten digits. According to the number of digits used in each task, we further split the MNIST dataset into downstream task data points. For example, we have 30K training pairs for sum-2, 20K training pairs for sum-3, and 15K training pairs for sum-4. As the counting task consumes 8 images per datapoint, we have 7.5K training pairs for the counting tasks. The test and training splits follow the original MNIST task setup. Our neural module consists of a 2-layer CNN connected by a 2-layer MLP, with a hidden layer size of 1024. We trained the Scallop module 10 epochs on the training dataset, the learning rate is set to 0.001, and the batch size is 64, with a BCE-loss closing the training loop.

Scallop code. We present the Scallop code that is used in the MNIST-R benchmark in Figure 25.

Scallop code for MNIST-R
type digit_1(u32), digit_2(u32)
rel sum_2(a + b) = digit_1(a), digit_2(b)

(a) Scallop code for MNIST sum-2.

type digit_1(u32), digit_2(u32), digit_3(u32)
rel sum_3(a + b + c) = digit_1(a), digit_2(b), digit_3(c)

(b) Scallop code for MNIST sum-3.

type digit_1(u32), digit_2(u32), digit_3(u32), digit_4(u32)
rel sum_4(a + b + c + d) = digit_1(a), digit_2(b), digit_3(c), digit_4(d)

(c) Scallop code for MNIST sum-4.

type digit_1(u32), digit_2(u32)
rel less_than(a < b) = digit_1(a), digit_2(b)

(d) Scallop code for MNIST less-than.

type digit(u32)
rel not_3_or_4() = not digit(3) and not digit(4)

(e) Scallop code for MNIST not-3-or-4.

type digit(digit_id: u32, digit_value: u32)
rel count_3(x) :- x = count(o: digit(o, 3))

(f) Scallop code for MNIST count-3.

type digit(digit_id: u32, digit_value: u32)
rel count_3_or_4(x) = x = count(o: digit(o, 3) or digit(o, 4))

(g) Scallop code for MNIST count-3-or-4.

Figure 25. Scallop code for MNIST-R.

Hand Written Formula

Experimental Setup. The HWF [39] dataset takes in a sequence of images, where each image can be either a digit or an arithmetic symbol, and aims to calculate the outcome of the formula. We apply the same CNN-based symbol recognition network as for the MNIST-based tasks, with the only difference being that the model now performs a 14-way classification. We then generate a probabilistic database containing two relations: 1) length(usize), a non-probabilistic relation storing the length of the formula, and 2) symbol(id: usize, σ\sigma: String), a probabilistic relation mapping index IDs to symbols σ∈Σ\sigma\in\Sigma. For the reasoning component, we write a formula parser in Scallop (as shown in 26). Additionally, Scallop is used to perform calculations based on the parsed abstract syntax tree (AST) to obtain the final rational number output. The training loop is closed by a BCE loss at the end, forming an end-to-end training pipeline where gradients can back-propagate all the way from the output to the symbol recognition network. To prune the enormous output domain if we enumerate every possible parse tree, we sample only a subset of symbol predictions to be sent to Scallop. There are 10K images answer pairs for the training dataset. We set the batch size to 16, the learning rate to 0.0001, and the training epochs to 100. To enhance the learning efficiency, we adopt a sampling strategy, which only preserves the 7 most likely classification result for each image classification task, and sends it to Scallop.

1  type symbol(index: usize, symbol: String)
2  type length(n: usize)

4  rel digit = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}

6  type term(value: f32, begin: usize, end: usize)
7  rel term(x as f32, b, b + 1) = symbol(b, x) and digit(x)

9  type mult_div(value: f32, begin: usize, end: usize)
10 rel mult_div(x, b, r) = term(x, b, r)
11 rel mult_div(x * y, b, e) = mult_div(x, b, m) and symbol(m, "*") and
12                                     term(y, m + 1, e)
13 rel mult_div(x / y, b, e) = mult_div(x, b, m) and symbol(m, "/") and
14                                     term(y, m + 1, e)

16 type add_minus(value: f32, begin: usize, end: usize)
17 rel add_minus(x, b, r) = mult_div(x, b, r)
18 rel add_minus(x + y, b, e) = add_minus(x, b, m) and symbol(m, "+") and
19                                mult_div(y, m + 1, e)
20 rel add_minus(x - y, b, e) = add_minus(x, b, m) and symbol(m, "-") and
21                                mult_div(y, m + 1, e)

23 type result(value: f32)
24 rel result(y) = add_minus(y, 0, l) and length(l)

26 query result

Figure 26. Scallop code for HWF.

Examples of positive and negative for each difficulty level

Figure 27. Examples of positive and negative for each difficulty level.

Pathfinder

Problem Definition. Pathfinder is a task that initially set out to test the long-range reasoning ability of neural networks. It is adopted into a benchmark called Long Range Arena (LRA) [55] to evaluate the long-range reasoning ability of neural networks, or more specifically the Transformers [57]. In this task, we are provided with images with dark backgrounds and two white dots possibly connected by dashes. The model is then required to make a binary prediction on whether the two dots are connected or not. There are multiple versions of the dataset: one consisting of only 32×3232 \times32 images (Path) and the other one with 128×128128 \times128 (Path-X). Both versions

// Input from neural networks
type dash(i8, i8)
type dot(i8)

// Connectivity check
rel path(x, y) = dash(x, y) or path(x, z) and dash(z, y)
rel connected() = dot(x), dot(y), path(x, y), x != y

have 3 difficulties, easy, normal, and hard, depending on the length of the dashes connecting the two dots – longer means harder. Table 27 shows the 3 difficulties each with one positive and one negative sample from Path-X.

Architecture. Going to the extreme of symbolism one would use the individual symbol to represent each small dash and dot. However, doing so would mean that the perception network, presumably a CNN, needs to segment the image precisely to extract all dashes and dots as entities. At the same time, the reasoning module bears an extra burden when processing individual connectivities. Instead, we employ a simple grid-based connectivity graph: each node represents a conceptual “dot” and each edge represents a conceptual “dash”. We ask neural networks to take in the image and output a feature vector with the size of the number of dots plus the number of edges. Each logit in this vector is then treated as a probability of that “dot” or “dash”. The Scallop program we use for this task, as shown in Figure 28, is simply a transitive closure that checks whether there are two distinct dots connected by dashes.

Scallop code for Pathfinder

Figure 28. Scallop code for Pathfinder.

Experimental Setup. There are 600K training data points for both PATH and PATH-X, which are images of 32×3232 \times32 and 128×128128 \times128 pixels respectively, and the y-label represents whether there exists a path that connects the two dots on the image. We recognize the “dash” and “dots” relations through a 4-layer CNN, and the local connectivity is recognized through a 2-layer MLP classifier. We set the learning rate to 0.0001, the batch size to 64, and the number of epochs to 100.

PacMan-Maze

PacMan-Maze is a reinforcement learning based planning application, which aims to lead the actor to the flag without running into any enemy. We show the Scallop code for this task in Figure 29. In addition to the code shown in § 2, we added additional “integrity constraint violation” terms that need to be minimized during learning.

Scallop code for PacMan-Maze

Figure 29. Scallop code for PacMan-Maze.

Experimental Setup. We set the size of the maze to be a 5×55 \times5 matrix, and the maximum number of enemies that exists in the arena to be 5. In the training process, we set the batch size to be 24, the memory replay buffer size to be 3000, and the maximum number of actions in an episode to be 30. We update the target net every 10 epochs, we set the exploration rate to be 0.9, its falloff to be 0.98, and the learning rate is set to 0.0001.

CLUTRR

With CLUTRR [53] we step into the domain of NLP on kinship reasoning. Each data point in the CLUTRR dataset consists of a natural language passage, a query, and its answer. The passage tells a story about a family’s daily activities; the query is a tuple of two names, denoting the target pair of persons that we want to predict the relation for; the answer is among the 20 basic relations such as “mother”, “uncle”, and “daughter-in-law”. The dataset is further categorized into

// Input from neural networks
type grid_node(x: usize, y: usize) // 0.99 for each grid cell
type actor(x: usize, y: usize)
type goal(x: usize, y: usize)
type enemy(x: usize, y: usize)

// Basic connectivity
const UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3
rel safe_node(x, y) = grid_node(x, y), not enemy(x, y)
rel edge(x, y, x, yp, UP) = safe_node(x, y), safe_node(x, yp), yp == y + 1
rel edge(x, y, xp, y, RIGHT) = safe_node(x, y), safe_node(xp, y), xp == x + 1
rel edge(x, y, x, yp, DOWN) = safe_node(x, y), safe_node(x, yp), yp == y - 1
rel edge(x, y, xp, y, LEFT) = safe_node(x, y), safe_node(xp, y), xp == x - 1

// Get the next position
rel next_pos(xp, yp, a) = actor(x, y), edge(x, y, xp, yp, a)

// Path for connectivity; will condition on no enemy on the path
rel path(x, y, x, y) = next_pos(x, y, _)
rel path(x1, y1, x3, y3) = path(x1, y1, x2, y2), edge(x2, y2, x3, y3, _)

// Get the next action
rel next_action(a) = next_pos(x, y, a), goal(gx, gy), path(x, y, gx, gy)

// Constraint violation
type too_many_goal(), too_many_actor(), too_many_enemy()
rel too_many_goal() = n := count(x, y: goal(x, y)), n > 1
rel too_many_actor() = n := count(x, y: actor(x, y)), n > 1
rel too_many_enemy() = n := count(x, y: enemy(x, y)), n > 5
rel violation() = too_many_goal() or too_many_enemy() or too_many_actor()
// Define kinships belong to the Relation type
type Relation = usize

// Input from neural networks
type question(sub: String, obj: String)
type kinship(rela: Relation, sub: String, obj: String)
type composition(Relation, Relation, Relation)

// Rules to derive the final answer
rel kinship(r3, x, z) = composition(r1, r2, r3), kinship(r1, x, y),
                         kinship(r2, y, z), x != z
rel answer(r) = question(s, o), kinship(r, s, o)

10 difficulty levels according to the number of facts (kk) required to derive the final result. Note that the knowledge base for kinship compositionality, such as "father’s father is grandfather" is not included in the dataset. We, therefore, designed three experiments to help alleviate the issue of missing knowledge base, a) learning with manually specified rules, b) rule learning, and c) learning without rules. We showcase our Scallop code in Figure 30.

Scallop code for CLUTRR

Figure 30. Scallop code for CLUTRR.

Learn with Manually Specified Rules. A straightforward strategy to overcome the missing required database issue, is to manually add it. We created an external knowledge base with 92 kinship composition triplets and 3 rules. To define how two known relations can be connected to derive the third relation, we design a high-order predicate, composition. As an example, the rule “father’s mother is grandmother” is encoded as composition(FATHER, MOTHER, GRANDMOTHER). The full Scallop program connecting the knowledge base into the reasoning process is shown in Figure 30 Given the knowledge base, context, and question-answer pairs, we are ready to perform learning over the new dataset. As the context has varies lengths, we first separate the context into multiple windows to ensure the perception model processes similar-length-context across the dataset. Then a large language model, such as RoBERTa [42], is adopted to extract relations from these windowed texts. The kinship extracted from the context goes into kinship(rela, sub, obj). For example, kinship(SON, "Alice", "Bob") indicates that Bob is Alice’s son. The query, on the other hand, is stored in the relation question(sub, obj). Next, we will combine the predicted relations from all the context windows into one probabilistic database, together with the knowledge base, and the query to perform logical reasoning. Last, we compare the probabilistic query result with the ground truth with BCE loss.

Rule Learning. Specifying 92 composition rules manually could be time consuming. With Scallop, it is possible to do this in a smarter way. Since there are 20 basic kinship relations, we have a finite space containing 203=8K20^3 = 8\mathrm{K} possible composition facts. We treat all 8K composition facts as probabilistic and to be learnt, and therefore we store them inside a tensor of size 20×20×2020 \times20 \times20. We can initialize this tensor randomly but with a low maximum weight (i.e. 0.1). During training, we will allow gradients to be back-propagated to this composition tensor so that these weights can also be learnt. In this case, the user does not specify any composition fact manually and everything is learnt on the fly. Note that, 8K composition facts can slow down the training time. Therefore, we use multinomial sampling to pick 150 composition facts for training. During testing, we simply select the top 150 for inference.

Learn without Rules. We can also jointly extract entity relations and learn the composition rules without the human specified rules. This is a more challenging task where one needs to figure out the way to combine inferred relations and derive the desired answer without intermediate supervision.

Experimental Setup. We have 10K training data points, which are triplets of passage, query, and answers. We use RoBERTa as the backbone language model. We further train a 2-layer MLP-based relation extractor which takes in the embedding of three components, a global embedding of the passage, and the embedding of the queried subject and the object, and returns the result for a 21-way classification. We set the batch size to 32, the learning rate to 0.00001, and train the models for 100 epochs.

Mugen

Experimental Setup. We sample 1K Mugen[30] video and text pairs as the training dataset, and another 1K for testing. Our neural module consists of the S3D image embedding and

// Input from neural networks
type action(usize, String)
type expr(usize, String)
type expr_start(usize)
type expr_end(usize)
type action_start(usize)
type action_end(usize)

type match_single(usize, usize, usize)
type match_sub(usize, usize, usize, usize)

// Check whether does a subsection of text specification matches the
// video content
rel match_single(tid, vid, vid + 1) = expr(tid, a), action(vid, a)
rel match_sub(tid, tid, vid_start, vid_end) =
    match_single(tid, vid_start, vid_end)
rel match_sub(tid, tid, vid_start, vid_end) =
    match_sub(tid, tid, vid_start, vid_mid),
    match_single(tid, vid_mid, vid_end)
rel match_sub(tid_start, tid_end, vid_start, vid_end) =
    match_sub(tid_start, tid_end - 1, vid_start, vid_mid),
    match_single(tid_end, vid_mid, vid_end)

// Check whether does the whole text specification matches the video content
rel match() = expr_start(tid_start),
    expr_end(tid_end), action_start(vid_start), action_end(vid_end),
    match_sub(tid_start, tid_end, vid_start, vid_end)

// Integrity violation when too many identical text expressions
// occurs consecutively
rel too_many_consecutive_expr() = expr(tid, a),
    expr(tid + 1, a), expr(tid + 2, a), expr(tid + 3, a)

the distillBert text embedding. Then we pass the embeddings through a 2-layer MLP, with a hidden layer size of 256. We trained the Scallop module 1000 epochs on the training dataset, the learning rate is set to 0.0001, and the batch size is 3, with BCE-loss closing the training loop. The Scallop code is shown in Figure 31

Scallop code for Mugen

Figure 31. Scallop code for Mugen.

CLEVR

CLEVR [34] stands for Compositional Language and Elementary Visual Reasoning, is a synthetic dataset testing model’s ability to perform Visual Question Answering (VQA). Each data point of the dataset contains an image and a question-answer pair with regard to the image. The images are randomly generated from a dictionary of 3 shapes, 8 colors, 2 materials, and 2 sizes and the programmatic queries are also randomly generated. Given a rendered image with simple objects such as cubes and spheres, we aim to answer a question about the image.

Architecture. The object feature vectors are obtained by a 4-layer convolutional neural network. The feature vectors are then passed to four 2-layer MLP classifiers and another 3-layer MLP classifier

// yes/no question
rel eval_yn(e, x > y) = greater_than_expr(e, a, b),
                         eval_num(a, x), eval_num(b, y)
rel eval_yn(e, x < y) = less_than_expr(e, a, b),
                         eval_num(a, x), eval_num(b, y)
rel eval_yn(e, x == y) = equal_expr(e, a, b),
                         eval_num(a, x), eval_num(b, y)
rel eval_yn(e, x == y) = equal_color_expr(e, a, b),
                         eval_query(a, x), eval_query(b, y)
rel eval_yn(e, x == y) = equal_material_expr(e, a, b),
                         eval_query(a, x), eval_query(b, y)
rel eval_yn(e, x == y) = equal_shape_expr(e, a, b),
                         eval_query(a, x), eval_query(b, y)
rel eval_yn(e, x == y) = equal_size_expr(e, a, b),
                         eval_query(a, x), eval_query(b, y)
rel eval_yn(e, b) = b := exists(o: eval_objs(f, o)
                     where e: exists_expr(e, f))

// count number of objects
rel eval_num(e, n) = n := count(o: eval_objs(f, o) where e: count_expr(e, f))

// objects filter
rel eval_objs(e, o) = scene_expr(e), obj(o)
rel eval_objs(e, o) = unique_expr(e, f), eval_objs(f, o)
rel eval_objs(e, o) = filter_size_expr(e, f, s), eval_objs(f, o), size(o, s)
rel eval_objs(e, o) = filter_color_expr(e, f, c), eval_objs(f, o), color(o, c)
rel eval_objs(e, o) = filter_material_expr(e, f, m), eval_objs(f, o), material(o, m)
rel eval_objs(e, o) = filter_shape_expr(e, f, s), eval_objs(f, o), shape(o, s)
rel eval_objs(e, o) = and_expr(e, f1, f2), eval_objs(f1, o), eval_objs(f2, o)
rel eval_objs(e, o) = or_expr(e, f1, f2) and (eval_objs(f1, o) or eval_objs(f2, o))

// same attribute
rel eval_objs(e, o) = same_size_expr(e, f),
                      eval_objs(f, p), size(p, c), size(o, c), o != p
rel eval_objs(e, o) = same_color_expr(e, f),
                      eval_objs(f, p), color(p, c), color(o, c), o != p
rel eval_objs(e, o) = same_material_expr(e, f),
                      eval_objs(f, p), material(p, m), material(o, m), o != p
rel eval_objs(e, o) = same_shape_expr(e, f),
                      eval_objs(f, p), shape(p, s), shape(o, s), o != p

// relation
rel relate("right", p, o) = relate("left", o, p)
rel relate("front", p, o) = relate("behind", o, p)
rel eval_objs(e, o) = relate_expr(e, f, r),
                      eval_objs(f, p), relate(r, p, o), o != p

// eval query
rel eval_query(e, s) = query_size_expr(e, f), eval_objs(f, o), size(o, s)
rel eval_query(e, c) = query_color_expr(e, f), eval_objs(f, o), color(o, c)
rel eval_query(e, m) = query_material_expr(e, f), eval_objs(f, o), material(o, m)
rel eval_query(e, s) = query_shape_expr(e, f), eval_objs(f, o), shape(o, s)

to obtain the attributes and the spacial relations respectively. The learning rate is set to 0.0001, the batch size is 32, and the latent dimension is 1024. We show our Scallop code in Figure 32.

Scallop code for CLEVR

Figure 32. Scallop code for CLEVR.

References

  1. [1]Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. 2015. TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems. arXiv:1603.04467arxiv.org/abs/1603.04467
  2. [2]Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of Databases: The Logical Level. Addison-Wesley Longman Publishing Co., Inc.
  3. [3]Yael Amsterdamer, Daniel Deutsch, and Val Tannen. 2011. On the Limitations of Provenance for Queries With Difference. (2011), arXiv:1105.2255arxiv.org/abs/1105.2255
  4. [4]Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016. Neural Module Networks. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR).arxiv.org/abs/1511.02799
  5. [5]Molhar Aref, Balder ten Cate, Todd J. Green, Benny Kimefeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn. 2015. Design and Implementation of the LogicBlox System. In ACM International Conference on Management of Data (SIGMOD).DOI
  6. [6]Atılım Güneş Baydin, Barak A. Pearlmutter, and Alexey Andreyevich Radul. 2015. Automatic Differentiation in Machine Learning: a Survey. (2015). arXiv:1502.05767arxiv.org/abs/1502.05767
  7. [7]Eli Bingham, Jonathan P. Chen, Martin Jankowiak, Fritz Obermeyer, Neeraj Pradhan, Theofanis Karaletsos, Rohit Singh, Paul Szerlip, Paul Horsfall, and Noah D. Goodman. 2018. Pyro: Deep Universal Probabilistic Programming. Journal of Machine Learning Research (2018).arxiv.org/abs/1810.09538
  8. [8]James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018. JAX: Composable Transformations of Python+NumPy Programs. https://github.com/google/jax.
  9. [9]Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language Models are Few-Shot Learners. In Conference on Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2005.14165
  10. [10]Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, et al. 2021. Neurosymbolic Programming. Foundations and Trends in Programming Languages 7, 3 (2021).
  11. [11]Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. 2021b. Evaluating Large Language Models Trained on Code. (2021), arXiv:2107.03374arxiv.org/abs/2107.03374
  12. [12]Qiaochu Chen, Aaron Lamoreaux, Xinyu Wang, Greg Durrett, Osbert Bastani, and Isil Dillig. 2021a. Web Question Answering with Neurosymbolic Program Synthesis. In ACM International Conference on Programming Language Design and Implementation (PLDI).arxiv.org/abs/2104.07162
  13. [13]Xinyun Chen, Chen Liang, Adams Wei Yu, Denny Zhou, Dawn Song, and Quoc V. Le. 2020. Neural Symbolic Reader: Scalable Integration of Distributed and Symbolic Representations for Reading Comprehension. In International Conference on Learning Representations (ICLR).
  14. [14]Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al. 2022. Binding Language Models in Symbolic Languages. (2022). arXiv:2210.02875arxiv.org/abs/2210.02875
  15. [15]Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. 2019. Quantifying generalization in reinforcement learning. In International Conference on Machine Learning (ICML). PMLR, 1282–1289.arxiv.org/abs/1812.02341
  16. [16]William W. Cohen, Fan Yang, and Kathryn Rivard Mazaitis. 2017. TensorLog: Deep Learning Meets Probabilistic DBs. arXiv:1707.05390arxiv.org/abs/1707.05390
  17. [17]Andrew Cropper, Sebastian Dumancic, Richard Evans, and Stephen H. Muggleton. 2022. Inductive Logic Programming at 30. Machine Learning 111, 1 (2022).
  18. [18]Katrin M. Dannert, Erich Grädel, Matthias Naaf, and Val Tannen. 2021. Semiring Provenance for Fixed-Point Logic. In Conference on Computer Science Logic (CSL).
  19. [19]Adnan Darwiche. 2011. SDD: A New Canonical Representation of Propositional Knowledge Bases. In International Joint Conference on Artificial Intelligence (IJCAI).
  20. [20]Alexey Dosovitskiy, German Ros, Felipe Codevilla, Antonio Lopez, and Vladlen Koltun. 2017. CARLA: An Open Urban Driving Simulator. In Conference on Robot Learning (CoRL).
  21. [21]Anton Dries, Angelika Kimmig, Wannes Meert, Joris Renkens, Guy Van den Broeck, Jonas Vlasselaer, and Luc De Raedt. 2015. ProbLog2: Probabilistic Logic Programming. In European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD).DOI
  22. [22]Difei Gao, Ruiping Wang, Shiguang Shan, and Xilin Chen. 2019. From Two Graphs to N Questions: A VQA Dataset for Compositional Reasoning on Vision and Commonsense. (2019). arXiv:1908.02962
  23. [23]Hong Ge, Kai Xu, and Zoubin Ghahramani. 2018. Turing: a Language for Flexible Probabilistic Inference. In International Conference on Artificial Intelligence and Statistics, (AISTATS).DOI
  24. [24]Ross B. Girshick. 2015. Fast R-CNN. (2015). arXiv:1504.08083arxiv.org/abs/1504.08083
  25. [25]Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. 2013. Speech Recognition with Deep Recurrent Neural Networks. In IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP).arxiv.org/abs/1303.5778
  26. [26]Todd J. Green, Grigoris Karvounarakis, and Val Tannen. 2007. Provenance Semirings. In ACM Symposium on Principles of Database Systems (PODS).DOI
  27. [27]Albert Gu, Karan Goel, and Christopher Ré. 2021. Efficiently Modeling Long Sequences with Structured State Spaces. (2021). arXiv:2111.00396arxiv.org/abs/2111.00396
  28. [28]Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Ré. 2022. How to Train Your HiPPO: State Space Models with Generalized Orthogonal Basis Projections. (2022). arXiv:2206.21037arxiv.org/abs/2206.12037
  29. [29]Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. 2017. Program synthesis. Foundations and Trends in Programming Languages 4, 1-2 (2017).
  30. [30]Thomas Hayes, Soyang Zhang, Xi Yin, Guan Pang, Sasha Sheng, Harry Yang, Songwei Ge, Qiyuan Hu, and Devi Parikh. 2022. MUGEN: A Playground for Video-Audio-Text Multimodal Understanding and GENeration. arXiv:2204.08058
  31. [31]Jiani Huang, Ziyang Li, Binghong Chen, Karan Samel, Mayur Naik, Le Song, and Xujie Si. 2021. Scallop: From Probabilistic Deductive Databases to Scalable Differentiable Reasoning. In Conference on Neural Information Processing Systems (NeurIPS).
  32. [32]Drew A Hudson and Christopher D Manning. 2019. Q: A New Dataset for Real-World Visual Reasoning and Compositional Question Answering. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR).arxiv.org/abs/1902.09506
  33. [33]Louis Jachiet, Pierre Genevès, Nils Gebert, and Nabil Layaïda. 2020. On the Optimization of Recursive Relational Queries: Application to Graph Queries. In ACM International Conference on Management of Data (SIGMOD).DOI
  34. [34]Justin Johnson, Bharath Hariharan, Laurens Van Der Maaten, Li Fei-Fei, C Lawrence Zitnick, and Ross Girshick. 2017. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2901–2910.arxiv.org/abs/1612.06890
  35. [35]Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David Shamma, Michael Bernstein, and Li Fei-Fei. 2015. Image Retrieval Using Scene Graphs. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR).DOI
  36. [36]Mahmoud Abo Khamis, Hung Q. Ngo, Reinhard Pichler, Dan Suciu, and Yisu Remy Wang. 2021. Convergence of Datalog over (Pre-) Semirings. arXiv:2105.14435
  37. [37]Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. 1998. Gradient-Based Learning Applied to Document Recognition. Proc. IEEE 86, 11 (1998).
  38. [38]Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, et al. 2022. Solving Quantitative Reasoning Problems with Language Models. (2022).arxiv.org/abs/2206.14858
  39. [39]Qing Li, Siyuan Huang, Yining Hong, Yixin Chen, Ying Nian Wu, and Song-Chun Zhu. 2020. Closed Loop Neural-Symbolic Learning via Integrating Neural Perception, Grammar Parsing, and Symbolic Reasoning. In International Conference on Machine Learning (ICML).arxiv.org/abs/2006.06649
  40. [40]Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. 2022. What Makes Convolutional Models Great on Long Sequence Modeling? (2022). arXiv:2210.09298arxiv.org/abs/2210.09298
  41. [41]Ziyang Li, Jiani Huang, and Mayur Naik. 2023. Scallop: A Language for Neurosymbolic Programming. https://doi.org/10.5281/zenodo.7709690
  42. [42]Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019. RoBERTa: A Robustly Optimized BERT Pretraining Approach. (2019). arXiv:1907.11692arxiv.org/abs/1907.11692
  43. [43]Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. 2021. Neural Probabilistic Logic Programming in DeepProbLog. Artificial Intelligence 298 (2021).arxiv.org/abs/1907.08194
  44. [44]Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B Tenenbaum, and Jiajun Wu. 2019. The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision. (2019). arXiv:1904.12584arxiv.org/abs/1904.12584
  45. [45]Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp, Edward Grefenstette, and Tim Rocktäschel. 2020. Learning Reasoning Strategies in End-to-End Differentiable Proving. In International Conference on Machine Learning (ICML).arxiv.org/abs/2007.06477
  46. [46]Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. 2015. Human-level Control Through Deep Reinforcement Learning. Nature 518, 7540 (2015).DOI
  47. [47]Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Conference on Neural Information Processing Systems (NeurIPS).arxiv.org/abs/1912.01703
  48. [48]Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016. SQuAD: 100,000+ Questions for Machine Comprehension of Text. In Conference on Empirical Methods in Natural Language Processing (EMNLP).arxiv.org/abs/1606.05250
  49. [49]Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. 2019. DistilBERT, a Distilled Version of BERT: Smaller, Faster, Cheaper and Lighter. (2019). arXiv:1910.01108arxiv.org/abs/1910.01108
  50. [50]Bernhard Scholz, Herbert Jordan, Pavle Subotic, and Till Westmann. 2016. On Fast Large-Scale Program Analysis in Datalog. In International Conference on Compiler Construction (CC).DOI
  51. [51]Ameesh Shah, Eric Zhan, Jennifer Sun, Abhinav Verma, Yisong Yue, and Swarat Chaudhuri. 2020. Learning Differentiable Programs with Admissible Neural Heuristics. In Conference on Neural Information Processing Systems (NeurIPS).arxiv.org/abs/2007.12101
  52. [52]Xujie Si, Mukund Raghothaman, Kihong Heo, and Mayur Naik. 2019. Synthesizing Datalog Programs using Numerical Relaxation. In International Joint Conference on Artificial Intelligence (IJCAI).
  53. [53]Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. 2019. CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text. (2019). arXiv:1809.06177
  54. [54]Hao Tan and Mohit Bansal. 2019. LXMERT: Learning Cross-Modality Encoder Representations from Transformers. (2019). arXiv:1908.07490arxiv.org/abs/1908.07490
  55. [55]Yi Tay, Mustafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. 2020. Long Range Arena: A Benchmark for Efficient Transformers. (2020). arXiv:2011.04006
  56. [57]Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention Is All You Need. In Conference on Neural Information Processing Systems (NeurIPS).arxiv.org/abs/1706.03762
  57. [58]Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph Attention Networks. (2017). arXiv:1710.10903arxiv.org/abs/1710.10903
  58. [59]Po-Wei Wang, Priya L. Donti, Bryan Wilder, and Zico Kolter. 2019. SATNet: Bridging Deep Learning and Logical Reasoning Using a Differentiable Satisfiability Solver. In International Conference on Machine Learning (ICML).arxiv.org/abs/1905.12149
  59. [60]Saining Xie, Chen Sun, Jonathan Huang, Zhuowen Tu, and Kevin Murphy. 2018. Rethinking Spatiotemporal Feature Learning: Speed-Accuracy Trade-offs in Video Classification. In European Conference on Computer Vision (ECCV).arxiv.org/abs/1712.04851
  60. [61]Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. 2018. A Semantic Loss Function for Deep Learning with Symbolic Knowledge. In International Conference on Machine Learning (ICML).arxiv.org/abs/1711.11157
  61. [62]Ziwei Xu, Yogesh S Rawat, Yongkang Wong, Mohan Kankanhalli, and Mubarak Shah. 2022. Don’t Pour Cereal into Coffee: Differentiable Temporal Logic for Temporal Action Segmentation. In Conference on Neural Information Processing Systems (NeurIPS).
  62. [63]Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. 2018. Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding. In Conference on Neural Information Processing Systems (NeurIPS).arxiv.org/abs/1810.02338
  63. [64]Eric Zelikman, Qian Huang, Gabriel Poesia, Noah D. Goodman, and Nick Haber. 2023. Parsel: A (De-)compositional Framework for Algorithmic Reasoning with Language Models. arXiv:2212.10561

Paper details

vlnc:W_8m3z4wu4
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents