Luc De Raedt

AAAI Conference 2026 Conference Paper

DeepProofLog: Efficient Proving in Deep Stochastic Logic Programs

• Ying Jiao
• Rodrigo Castellano Ontiveros
• Luc De Raedt
• Marco Gori
• Francesco Giannini
• Michelangelo Diligenti
• Giuseppe Marra

Neurosymbolic (NeSy) AI combines neural architectures and symbolic reasoning to improve accuracy, interpretability, and generalization. While logic inference on top of subsymbolic modules has been shown to effectively guarantee these properties, this often comes at the cost of reduced scalability, which can severely limit the usability of NeSy models. This paper introduces DeepProofLog (DPrL), a novel NeSy system based on stochastic logic programs, which addresses the scalability limitations of previous methods. DPrL parameterizes all derivation steps with neural networks, allowing efficient neural guidance over the proving system. Additionally, we establish a formal mapping between the resolution process of our deep stochastic logic programs and Markov Decision Processes, enabling the application of dynamic programming and reinforcement learning techniques for efficient inference and learning. This theoretical connection improves scalability for complex proof spaces and large knowledge bases. Our experiments on standard NeSy benchmarks and knowledge graph reasoning tasks demonstrate that DPrL outperforms existing state-of-the-art NeSy systems, advancing scalability to larger and more complex settings than previously possible.

ECAI Conference 2025 Conference Paper

DEEPGRAPHLOG for Layered Neurosymbolic AI

• Adem Kikaj
• Giuseppe Marra
• Floris Geerts
• Robin Manhaeve
• Luc De Raedt

Neurosymbolic AI (NeSy) aims to integrate the statistical strengths of neural networks with the interpretability and structure of symbolic reasoning. However, current NeSy frameworks like DEEPGRAPHLOG enforce a fixed flow where symbolic reasoning always follows neural processing. This restricts their ability to model complex dependencies, especially in irregular data structures such as graphs. In this work, we introduce DEEPGRAPHLOG, a novel NeSy framework that extends PROBLOG with Graph Neural Predicates. DEEPGRAPHLOG enables multi-layer neural-symbolic reasoning, allowing neural and symbolic components to be layered in arbitrary order. In contrast to DEEPGRAPHLOG, which cannot handle symbolic reasoning via neural methods, DEEPGRAPHLOG treats symbolic representations as graphs, enabling them to be processed by Graph Neural Networks (GNNs). We showcase the capabilities of DEEPGRAPHLOG on tasks in planning, knowledge graph completion with distant supervision, and GNN expressivity. Our results demonstrate that DEEPGRAPHLOG effectively captures complex relational dependencies, overcoming key limitations of existing NeSy systems. By broadening the applicability of neurosymbolic AI to graph-structured domains, DEEPGRAPHLOG offers a more expressive and flexible framework for neural-symbolic integration. Code is available at https: //github. com/ML-KULeuven/DeepGraphLog.

NeurIPS Conference 2025 Conference Paper

LexiCon: a Benchmark for Planning under Temporal Constraints in Natural Language

• Periklis Mantenoglou
• Rishi Hazra
• Pedro Zuidberg Dos Martires
• Luc De Raedt

Owing to their reasoning capabilities, large language models (LLMs) have been evaluated on planning tasks described in natural language. However, LLMs have largely been tested on planning domains without constraints. In order to deploy them in real-world settings where adherence to constraints, in particular safety constraints, is critical, we need to evaluate their performance on constrained planning tasks. We introduce LexiCon—a natural language-based (Lexi) constrained (Con) planning benchmark, consisting of a suite of environments, that can be used to evaluate the planning capabilities of LLMs in a principled fashion. The core idea behind LexiCon is to take existing planning environments and impose temporal constraints on the states. These constrained problems are then translated into natural language and given to an LLM to solve. A key feature of LexiCon is its extensibility. That is, the set of supported environments can be extended with new (unconstrained) environment generators, for which temporal constraints are constructed automatically. This renders LexiCon future-proof: the hardness of the generated planning problems can be increased as the planning capabilities of LLMs improve. Our experiments reveal that the performance of state-of-the-art LLMs, including reasoning models like GPT-5, o3, and R1, deteriorates as the degree of constrainedness of the planning tasks increases.

IJCAI Conference 2025 Conference Paper

NeSyA: Neurosymbolic Automata

• Nikolaos Manginas
• George Paliouras
• Luc De Raedt

Neurosymbolic (NeSy) AI has emerged as a promising direction to integrate neural and symbolic reasoning. Unfortunately, little effort has been given to developing NeSy systems tailored to sequential/temporal problems. We identify symbolic automata (which combine the power of automata for temporal reasoning with that of propositional logic for static reasoning) as a suitable formalism for expressing knowledge in temporal domains. Focusing on the task of sequence classification and tagging we show that symbolic automata can be integrated with neural-based perception, under probabilistic semantics towards an end-to-end differentiable model. Our proposed hybrid model, termed NeSyA (Neuro Symbolic Automata) is shown to either scale or perform more accurately than previous NeSy systems in a synthetic benchmark and to provide benefits in terms of generalization compared to purely neural systems in a real-world event recognition task. Code is available at: https: //github. com/nmanginas/nesya

ECAI Conference 2025 Conference Paper

Neurosymbolic OCR for Handwritten Tax Forms

• Quinten Dewulf
• Robin Manhaeve
• Wannes Meert
• Luc De Raedt

Neurosymbolic AI integrates low-level perception with high-level reasoning, making it well suited for tasks that involve both visual recognition and domain-specific constraints. One such task is the digitization of structured documents like handwritten tax forms, which must satisfy numerous known rules. While neural OCR models are becoming increasingly capable at reading handwritten text, they fail to enforce such constraints on their output, leading to invalid predictions. By combining neural OCR outputs with grammar-based stochastic reasoning over these constraints, neurosymbolic OCR can correct both neural perception errors and user mistakes. This paper demonstrates the application of DeepStochLog, a neurosymbolic AI system, to digitize handwritten IRS 1040 tax forms. Its ability to incorporate background knowledge and ease of use make DeepStochLog an attractive framework for constrained OCR applications.

PRL Workshop 2025 Workshop Paper

Neurosymbolic Reinforcement Learning With Sequential Guarantees

• Lennert De Smet
• Gabriele Venturato
• Luc De Raedt
• Giuseppe Marra

AAAI Conference 2025 System Paper

Neurosymbolic Reinforcement Learning: Playing MiniHack with Probabilistic Logic Shields

• David Debot
• Gabriele Venturato
• Giuseppe Marra
• Luc De Raedt

Probabilistic logic shields integrate deep reinforcement learning (RL) with probabilistic logic reasoning to train agents that operate in uncertain environments while giving strong guarantees with respect to logical constraints, such as safety properties. In this demo paper, we introduce a codebase that streamlines the design of custom MiniHack environments where neurosymbolic RL agents leverage probabilistic logic shields to learn safe and interpretable policies with strong guarantees. Our framework allows expert users to easily define and train agents that integrate deep neural policies with probabilistic logic in arbitrarily complex games: from simple exploration to planning and interacting with enemies. Additionally, we provide a web-based platform that showcases our application, offering an interactive interface for the broader community to experiment with and explore the capabilities of neurosymbolic reinforcement learning. This lowers the barrier for researchers and developers, making it accessible for a wider audience to engage with safety-critical RL scenarios.

AAAI Conference 2025 Conference Paper

Relational Neurosymbolic Markov Models

• Lennert De Smet
• Gabriele Venturato
• Luc De Raedt
• Giuseppe Marra

Sequential problems are ubiquitous in AI, such as in reinforcement learning or natural language processing. State-of-the-art deep sequential models, like transformers, excel in these settings but fail to guarantee the satisfaction of constraints necessary for trustworthy deployment. In contrast, neurosymbolic AI (NeSy) provides a sound formalism to enforce constraints in deep probabilistic models but scales exponentially on sequential problems. To overcome these limitations, we introduce relational neurosymbolic Markov models (NeSy-MMs), a new class of end-to-end differentiable sequential models that integrate and provably satisfy relational logical constraints. We propose a strategy for inference and learning that scales on sequential settings, and that combines approximate Bayesian inference, automated reasoning, and gradient estimation. Our experiments show that NeSy-MMs can solve problems beyond the current state-of-the-art in neurosymbolic AI and still provide strong guarantees with respect to desired properties. Moreover, we show that our models are more interpretable and that constraints can be adapted at test time to out-of-distribution scenarios.

ECAI Conference 2025 Conference Paper

TABIA: A Language to Transform, Combine, and Reason over Semi-Structured Tabular Data

• Dirko Coetsee
• Steve Kroon
• McElory Hoffmann
• Luc De Raedt

Semi-structured tables are transformed, combined, and wrangled using a multitude of tools and languages. Table processing tools such as SQL and pandas assume fixed, declared schemata and treat layout metadata as secondary. Semi-structured tables such as spreadsheets, in contrast, embed headers and data in the same grid. There is therefore a need for a table manipulation and merging base-language that takes the structure and layout into account. We propose a language for interactively transforming semi-structured tables, synthesising table structure transformations from examples, and mining relationships between tables from a large corpus. Our language comprise a few simple base operations, based on the relational algebra, which combine to form higher-level operations. Our approach facilitates reasoning to prune the search space for a new tabular relationship mining task, thereby allowing researchers to better understand the lineage of semi-structured data. Our findings offer insights into the design of data transformation languages for semi-structured tabular data and provides a base language for data mining on tabular data.

AAAI Conference 2025 Conference Paper

The Gradient of Algebraic Model Counting

• Jaron Maene
• Luc De Raedt

Algebraic model counting unifies many inference tasks on logic formulas by exploiting semirings. Rather than focusing on inference, we consider learning, especially in statistical-relational and neurosymbolic AI, which combine logical, probabilistic and neural representations. Concretely, we show that the very same semiring perspective of algebraic model counting also applies to learning. This allows us to unify various learning algorithms by generalizing gradients and backpropagation to different semirings. Furthermore, we show how cancellation and ordering properties of a semiring can be exploited for more memory-efficient backpropagation. This allows us to obtain some interesting variations of state-of-the-art gradient-based optimisation methods for probabilistic logical models. We also discuss why algebraic model counting on tractable circuits does not lead to more efficient second-order optimization. Empirically, our algebraic backpropagation exhibits considerable speed-ups as compared to existing approaches.

KR Conference 2024 Conference Paper

Automated Reasoning in Systems Biology: A Necessity for Precision Medicine

• Pedro Zuidberg Dos Martires
• Vincent Derkinderen
• Luc De Raedt
• Marcus Krantz

Recent developments in AI have reinvigorated pursuits to advance the (life) sciences using AI techniques, thereby creating a renewed opportunity to bridge different fields and find synergies. Headlines for AI and the life sciences have been dominated by data-driven techniques, for instance, to solve protein folding with next to no expert knowledge. In contrast to this, we argue for the necessity of a formal representation of expert knowledge -- either to develop explicit scientific theories or to compensate for the lack of data. Specifically, we argue that the fields of knowledge representation (KR) and systems biology (SysBio) exhibit important overlaps that have been largely ignored so far. This, in turn, means that relevant scientific questions are ready to be answered using the right domain knowledge (SysBio), encoded in the right way (SysBio/KR), and by combining it with modern automated reasoning tools (KR). Hence, the formal representation of domain knowledge is a natural meeting place for SysBio and KR. On the one hand, we argue that such an interdisciplinary approach will advance the field SysBio by exposing it to industrial-grade reasoning tools and thereby allowing novel scientific questions to be tackled. On the other hand, we see ample opportunities to move the state-of-the-art in KR by tailoring KR methods to the field of SysBio, which comes with challenging problem characteristics, e. g. , scale, partial knowledge, noise, or sub-symbolic data. We stipulate that this proposed interdisciplinary research is necessary to attain a prominent long-term goal in the health sciences: precision medicine.

AIJ Journal 2024 Journal Article

Declarative probabilistic logic programming in discrete-continuous domains

• Pedro Zuidberg Dos Martires
• Luc De Raedt
• Angelika Kimmig

Over the past three decades, the logic programming paradigm has been successfully expanded to support probabilistic modeling, inference and learning. The resulting paradigm of probabilistic logic programming (PLP) and its programming languages owes much of its success to a declarative semantics, the so-called distribution semantics. However, the distribution semantics is limited to discrete random variables only. While PLP has been extended in various ways for supporting hybrid, that is, mixed discrete and continuous random variables, we are still lacking a declarative semantics for hybrid PLP that not only generalizes the distribution semantics and the modeling language but also the standard inference algorithm that is based on knowledge compilation. We contribute the measure semantics together with the hybrid PLP language DC-ProbLog (where DC stands for distributional clauses) and its inference engine infinitesimal algebraic likelihood weighting (IALW). These have the original distribution semantics, standard PLP languages such as ProbLog, and standard inference engines for PLP based on knowledge compilation as special cases. Thus, we generalize the state of the art of PLP towards hybrid PLP in three different aspects: semantics, language and inference. Furthermore, IALW is the first inference algorithm for hybrid probabilistic programming based on knowledge compilation.

ECAI Conference 2024 Conference Paper

EXPLAIN, AGREE, LEARN: Scaling Learning for Neural Probabilistic Logic

• Victor Verreet
• Lennert De Smet
• Luc De Raedt
• Emanuele Sansone

Neural probabilistic logic systems follow the neuro-symbolic (NeSy) paradigm by combining the perceptive and learning capabilities of neural networks with the robustness of probabilistic logic. Learning corresponds to likelihood optimization of the neural networks. However, to obtain the likelihood exactly, expensive probabilistic logic inference is required. To scale learning to more complex systems, we therefore propose to instead optimize a sampling based objective. We prove that the objective has a bounded error with respect to the likelihood, which vanishes when increasing the sample count. Furthermore, the error vanishes faster by exploiting a new concept of sample diversity. We then develop the EXPLAIN, AGREE, LEARN (EXAL) method that uses this objective. EXPLAIN samples explanations for the data. AGREE reweighs each explanation in concordance with the neural component. LEARN uses the reweighed explanations as a signal for learning. In contrast to previous NeSy methods, EXAL can scale to larger problem sizes while retaining theoretical guarantees on the error. Experimentally, our theoretical claims are verified and EXAL outperforms recent NeSy methods when scaling up the MNIST addition and Warcraft pathfinding problems.

AIJ Journal 2024 Journal Article

From statistical relational to neurosymbolic artificial intelligence: A survey

• Giuseppe Marra
• Sebastijan Dumančić
• Robin Manhaeve
• Luc De Raedt

This survey explores the integration of learning and reasoning in two different fields of artificial intelligence: neurosymbolic and statistical relational artificial intelligence. Neurosymbolic artificial intelligence (NeSy) studies the integration of symbolic reasoning and neural networks, while statistical relational artificial intelligence (StarAI) focuses on integrating logic with probabilistic graphical models. This survey identifies seven shared dimensions between these two subfields of AI. These dimensions can be used to characterize different NeSy and StarAI systems. They are concerned with (1) the approach to logical inference, whether model or proof-based; (2) the syntax of the used logical theories; (3) the logical semantics of the systems and their extensions to facilitate learning; (4) the scope of learning, encompassing either parameter or structure learning; (5) the presence of symbolic and subsymbolic representations; (6) the degree to which systems capture the original logic, probabilistic, and neural paradigms; and (7) the classes of learning tasks the systems are applied to. By positioning various NeSy and StarAI systems along these dimensions and pointing out similarities and differences between them, this survey contributes fundamental concepts for understanding the integration of learning and reasoning.

AAAI Conference 2024 Conference Paper

Inference and Learning in Dynamic Decision Networks Using Knowledge Compilation

• Gabriele Venturato
• Vincent Derkinderen
• Pedro Zuidberg Dos Martires
• Luc De Raedt

Decision making under uncertainty in dynamic environments is a fundamental AI problem in which agents need to determine which decisions (or actions) to make at each time step to maximise their expected utility. Dynamic decision networks (DDNs) are an extension of dynamic Bayesian networks with decisions and utilities. DDNs can be used to compactly represent Markov decision processes (MDPs). We propose a novel algorithm called mapl-cirup that leverages knowledge compilation techniques developed for (dynamic) Bayesian networks to perform inference and gradient-based learning in DDNs. Specifically, we knowledge-compile the Bellman update present in DDNs into dynamic decision circuits and evaluate them within an (algebraic) model counting framework. In contrast to other exact symbolic MDP approaches, we obtain differentiable circuits that enable gradient-based parameter learning.

ICML Conference 2024 Conference Paper

On the Hardness of Probabilistic Neurosymbolic Learning

• Jaron Maene
• Vincent Derkinderen
• Luc De Raedt

The limitations of purely neural learning have sparked an interest in probabilistic neurosymbolic models, which combine neural networks with probabilistic logical reasoning. As these neurosymbolic models are trained with gradient descent, we study the complexity of differentiating probabilistic reasoning. We prove that although approximating these gradients is intractable in general, it becomes tractable during training. Furthermore, we introduce WeightME, an unbiased gradient estimator based on model sampling. Under mild assumptions, WeightME approximates the gradient with probabilistic guarantees using a logarithmic number of calls to a SAT solver. Lastly, we evaluate the necessity of these guarantees on the gradient. Our experiments indicate that the existing biased approximations indeed struggle to optimize even when exact solving is still feasible.

AAAI Conference 2024 Conference Paper

SayCanPay: Heuristic Planning with Large Language Models Using Learnable Domain Knowledge

• Rishi Hazra
• Pedro Zuidberg Dos Martires
• Luc De Raedt

Large Language Models (LLMs) have demonstrated impressive planning abilities due to their vast "world knowledge". Yet, obtaining plans that are both feasible (grounded in affordances) and cost-effective (in plan length), remains a challenge, despite recent progress. This contrasts with heuristic planning methods that employ domain knowledge (formalized in action models such as PDDL) and heuristic search to generate feasible, optimal plans. Inspired by this, we propose to combine the power of LLMs and heuristic planning by leveraging the world knowledge of LLMs and the principles of heuristic search. Our approach, SayCanPay, employs LLMs to generate actions (Say) guided by learnable domain knowledge, that evaluates actions' feasibility (Can) and long-term reward/payoff (Pay), and heuristic search to select the best sequence of actions. Our contributions are (1) a novel framing of the LLM planning problem in the context of heuristic planning, (2) integrating grounding and cost-effective elements into the generated plans, and (3) using heuristic search over actions. Our extensive evaluations show that our model surpasses other LLM planning approaches.

NeSy Conference 2024 Conference Paper

Valid Text-to-SQL Generation with Unification-Based DeepStochLog

• Ying Jiao
• Luc De Raedt
• Giuseppe Marra

Abstract Large language models have been used to translate natural language questions to SQL queries. Without hard constraints on syntax and database schema, they occasionally produce invalid queries that are not executable. These failures limit the usage of these systems in real-life scenarios. We propose a neurosymbolic framework that imposes SQL syntax and schema constraints with unification-based definite clause grammars and thus guarantees the generation of valid queries. Our framework also builds a bi-directional interface to language models to leverage their natural language understanding abilities. The evaluation results on a subset of SQL grammars show that all our output queries are valid. This work is the first step towards extending language models with unification-based grammars. We demonstrate this extension enhances the validity, execution accuracy, and ground truth alignment of the underlying language model by a large margin. Our code is available at https: //github. com/ML-KULeuven/deepstochlog-lm.

JAIR Journal 2023 Journal Article

A Markov Framework for Learning and Reasoning About Strategies in Professional Soccer

• Maaike Van Roy
• Pieter Robberechts
• Wen-Chi Yang
• Luc De Raedt
• Jesse Davis

Strategy-optimization is a fundamental element of dynamic and complex team sports such as soccer, American football, and basketball. As the amount of data that is collected from matches in these sports has increased, so has the demand for data-driven decisionmaking support. If alternative strategies need to be balanced, a data-driven approach can uncover insights that are not available from qualitative analysis. This could tremendously aid teams in their match preparations. In this work, we propose a novel Markov modelbased framework for soccer that allows reasoning about the specific strategies teams use in order to gain insights into the efficiency of each strategy. The framework consists of two components: (1) a learning component, which entails modeling a team’s offensive behavior by learning a Markov decision process (MDP) from event data that is collected from the team’s matches, and (2) a reasoning component, which involves a novel application of probabilistic model checking to reason about the efficacy of the learned strategies of each team. In this paper, we provide an overview of this framework and illustrate it on several use cases using real-world event data from three leagues. Our results show that the framework can be used to reason about the shot decision-making of teams and to optimise the defensive strategies used when playing against a particular team. The general ideas presented in this framework can easily be extended to other sports.

JAIR Journal 2023 Journal Article

First-Order Context-Specific Likelihood Weighting in Hybrid Probabilistic Logic Programs

• Nitesh Kumar
• Ondřej Kuželka
• Luc De Raedt

Statistical relational AI and probabilistic logic programming have so far mostly focused on discrete probabilistic models. The reasons for this is that one needs to provide constructs to succinctly model the independencies in such models, and also provide efficient inference. Three types of independencies are important to represent and exploit for scalable inference in hybrid models: conditional independencies elegantly modeled in Bayesian networks, context-specific independencies naturally represented by logical rules, and independencies amongst attributes of related objects in relational models succinctly expressed by combining rules. This paper introduces a hybrid probabilistic logic programming language, DC#, which integrates distributional clauses' syntax and semantics principles of Bayesian logic programs. It represents the three types of independencies qualitatively. More importantly, we also introduce the scalable inference algorithm FO-CS-LW for DC#. FO-CS-LW is a first-order extension of the context-specific likelihood weighting algorithm (CS-LW), a novel sampling method that exploits conditional independencies and context-specific independencies in ground models. The FO-CS-LW algorithm upgrades CS-LW with unification and combining rules to the first-order case.

AIJ Journal 2023 Journal Article

Learning MAX-SAT from contextual examples for combinatorial optimisation

• Mohit Kumar
• Samuel Kolb
• Stefano Teso
• Luc De Raedt

Combinatorial optimisation problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with an objective function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism as it is a simple yet powerful setting having these features. We study the learnability of MAX-SAT models. Our theoretical results show that high-quality MAX-SAT models can be learned from contextual examples in the realisable and agnostic settings, as long as the data satisfies an intuitive “representativeness” condition. We also contribute two implementations based on our theoretical results: one leverages ideas from syntax-guided synthesis while the other makes use of stochastic local search techniques. The two implementations are evaluated by recovering synthetic and benchmark models from contextual examples. The experimental results support our theoretical analysis, showing that MAX-SAT models can be learned from contextual examples. Among the two implementations, the stochastic local search learner scales much better than the syntax-guided implementation while providing comparable or better models.

JAIR Journal 2023 Journal Article

Lifted Reasoning for Combinatorial Counting

• Pietro Totis
• Jesse Davis
• Luc De Raedt
• Angelika Kimmig

Combinatorics math problems are often used as a benchmark to test human cognitive and logical problem-solving skills. These problems are concerned with counting the number of solutions that exist in a specific scenario that is sketched in natural language. Humans are adept at solving such problems as they can identify commonly occurring structures in the questions for which a closed-form formula exists for computing the answer. These formulas exploit the exchangeability of objects and symmetries to avoid a brute-force enumeration of all possible solutions. Unfortunately, current AI approaches are still unable to solve combinatorial problems in this way. This paper aims to fill this gap by developing novel AI techniques for representing and solving such problems. It makes the following five contributions. First, we identify a class of combinatorics math problems which traditional lifted counting techniques fail to model or solve efficiently. Second, we propose a novel declarative language for this class of problems. Third, we propose novel lifted solving algorithms bridging probabilistic inference techniques and constraint programming. Fourth, we implement them in a lifted solver that solves efficiently the class of problems under investigation. Finally, we evaluate our contributions on a real-world combinatorics math problems dataset and synthetic benchmarks.

UAI Conference 2023 Conference Paper

Neural probabilistic logic programming in discrete-continuous domains

• Lennert De Smet
• Pedro Zuidberg Dos Martires
• Robin Manhaeve
• Giuseppe Marra
• Angelika Kimmig
• Luc De Raedt

Neural-symbolic AI (NeSy) allows neural networks to exploit symbolic background knowledge in the form of logic. It has been shown to aid learning in the limited data regime and to facilitate inference on out-of-distribution data. Probabilistic NeSy focuses on integrating neural networks with both logic and probability theory, which additionally allows learning under uncertainty. A major limitation of current probabilistic NeSy systems, such as DeepProbLog, is their restriction to finite probability distributions, i. e. , discrete random variables. In contrast, deep probabilistic programming (DPP) excels in modelling and optimising continuous probability distributions. Hence, we introduce DeepSeaProbLog, a neural probabilistic logic programming language that incorporates DPP techniques into NeSy. Doing so results in the support of inference and learning of both discrete and continuous probability distributions under logical constraints. Our main contributions are 1) the semantics of DeepSeaProbLog and its corresponding inference algorithm, 2) a proven asymptotically unbiased learning algorithm, and 3) a series of experiments that illustrate the versatility of our approach.

NeSy Conference 2023 Conference Paper

Safe Reinforcement Learning via Probabilistic Logic Shields

• Wen-Chi Yang
• Giuseppe Marra
• Gavin Rens
• Luc De Raedt

Safe Reinforcement learning (Safe RL) aims at learning optimal policies while staying safe. A popular solution to Safe RL is shielding, which uses a logical safety specification to prevent an RL agent from taking unsafe actions. However, traditional shielding techniques are difficult to integrate with continuous, end-to-end deep RL methods. To this end, we introduce Probabilistic Logic Policy Gradient (PLPG). PLPG is a model-based Safe RL technique that uses probabilistic logic programming to model logical safety constraints as differentiable functions. Therefore, PLPG can be seamlessly applied to any policy gradient algorithm while still providing the same convergence guarantees. In our experiments, we show that PLPG learns safer and more rewarding policies compared to other state-of-the-art shielding techniques.

IJCAI Conference 2023 Conference Paper

Safe Reinforcement Learning via Probabilistic Logic Shields

• Wen-Chi Yang
• Giuseppe Marra
• Gavin Rens
• Luc De Raedt

Safe Reinforcement learning (Safe RL) aims at learning optimal policies while staying safe. A popular solution to Safe RL is shielding, which uses a logical safety specification to prevent an RL agent from taking unsafe actions. However, traditional shielding techniques are difficult to integrate with continuous, end-to-end deep RL methods. To this end, we introduce Probabilistic Logic Policy Gradient (PLPG). PLPG is a model-based Safe RL technique that uses probabilistic logic programming to model logical safety constraints as differentiable functions. Therefore, PLPG can be seamlessly applied to any policy gradient algorithm while still providing the same convergence guarantees. In our experiments, we show that PLPG learns safer and more rewarding policies compared to other state-of-the-art shielding techniques.

NeurIPS Conference 2023 Conference Paper

Soft-Unification in Deep Probabilistic Logic

• Jaron Maene
• Luc De Raedt

A fundamental challenge in neuro-symbolic AI is to devise primitives that fuse the logical and neural concepts. The Neural Theorem Prover has proposed the notion of soft-unification to turn the symbolic comparison between terms (i. e. unification) into a comparison in embedding space. It has been shown that soft-unification is a powerful mechanism that can be used to learn logic rules in an end-to-end differentiable manner. We study soft-unification from a conceptual point and outline several desirable properties of this operation. These include non-redundancy in the proof, well-defined proof scores, and non-sparse gradients. Unfortunately, these properties are not satisfied by previous systems such as the Neural Theorem Prover. Therefore, we introduce a more principled framework called DeepSoftLog based on probabilistic rather than fuzzy semantics. Our experiments demonstrate that DeepSoftLog can outperform the state-of-the-art on neuro-symbolic benchmarks, highlighting the benefits of these properties.

AAAI Conference 2022 Conference Paper

DeepStochLog: Neural Stochastic Logic Programming

• Thomas Winters
• Giuseppe Marra
• Robin Manhaeve
• Luc De Raedt

Recent advances in neural-symbolic learning, such as Deep- ProbLog, extend probabilistic logic programs with neural predicates. Like graphical models, these probabilistic logic programs define a probability distribution over possible worlds, for which inference is computationally hard. We propose Deep- StochLog, an alternative neural-symbolic framework based on stochastic definite clause grammars, a kind of stochastic logic program. More specifically, we introduce neural grammar rules into stochastic definite clause grammars to create a framework that can be trained end-to-end. We show that inference and learning in neural stochastic logic programming scale much better than for neural probabilistic logic programs. Furthermore, the experimental evaluation shows that DeepStochLog achieves state-of-the-art results on challenging neural-symbolic learning tasks.

AAAI Conference 2022 Conference Paper

Inference and Learning with Model Uncertainty in Probabilistic Logic Programs

• Victor Verreet
• Vincent Derkinderen
• Pedro Zuidberg Dos Martires
• Luc De Raedt

An issue that has so far received only limited attention in probabilistic logic programming (PLP) is the modeling of so-called epistemic uncertainty, the uncertainty about the model itself. Accurately quantifying this model uncertainty is paramount to robust inference, learning and ultimately decision making. We introduce BetaProbLog, a PLP language that can model epistemic uncertainty. BetaProbLog has sound semantics, an effective inference algorithm that combines Monte Carlo techniques with knowledge compilation, and a parameter learning algorithm. We empirically outperform state-of-the-art methods on probabilistic inference tasks in second-order Bayesian networks, digit classification and discriminative learning in the presence of epistemic uncertainty.

KR Conference 2021 Conference Paper

Approximate Inference for Neural Probabilistic Logic Programming

• Robin Manhaeve
• Giuseppe Marra
• Luc De Raedt

DeepProbLog is a neural-symbolic framework that integrates probabilistic logic programming and neural networks. It is realized by providing an interface between the probabilistic logic and the neural networks. Inference in probabilistic neural symbolic methods is hard, since it combines logical theorem proving with probabilistic inference and neural network evaluation. In this work, we make the inference more efficient by extending an approximate inference algorithm from the field of statistical-relational AI. Instead of considering all possible proofs for a certain query, the system searches for the best proof. However, training a DeepProbLog model using approximate inference introduces additional challenges, as the best proof is unknown at the start of training which can lead to convergence towards a local optimum. To be able to apply DeepProbLog on larger tasks, we propose: 1) a method for approximate inference using an A*-like search, called DPLA* 2) an exploration strategy for proving in a neural-symbolic setting, and 3) a parametric heuristic to guide the proof search. We empirically evaluate the performance and scalability of the new approach, and also compare the resulting approach to other neural-symbolic systems. The experiments show that DPLA* achieves a speed up of up to 2-3 orders of magnitude in some cases.

AAAI Conference 2021 System Paper

Democratizing Constraint Satisfaction Problems through Machine Learning

• Mohit Kumar
• Samuel Kolb
• Clement Gautrais
• Luc De Raedt

Constraint satisfaction problems (CSPs) are used widely, especially in the field of operations research, to model various real world problems like scheduling or planning. However, modelling a problem as a CSP is not trivial, it is labour intensive and requires both modelling and domain expertise. The emerging field of constraint learning deals with this problem by automatically learning constraints from a given dataset. While there are several interesting approaches for constraint learning, these works are hard to access for a non-expert user. Furthermore, different approaches have different underlying formalism and require different setups before they can be used. This demo paper combines these researches and brings it to non-expert users in the form of an interactive Excel plugin. To do this, we translate different formalism for specifying CSPs into a common language, which allows multiple constraint learners to coexist, making this plugin more powerful than individual constraint learners. Moreover, we integrate learning of CSPs from data with solving them, making it a self sufficient plugin. For the developers of different constraint learners, we provide an API that can be used to integrate their work with this plugin by implementing a handful of functions.

IJCAI Conference 2021 Conference Paper

Learning CNF Theories Using MDL and Predicate Invention

• Arcchit Jain
• Clément Gautrais
• Angelika Kimmig
• Luc De Raedt

We revisit the problem of learning logical theories from examples, one of the most quintessential problems in machine learning. More specifically, we develop an approach to learn CNF-formulae from satisfiability. This is a setting in which the examples correspond to partial interpretations and an example is classified as positive when it is logically consistent with the theory. We present a novel algorithm, called Mistle -- Minimal SAT Theory Learner, for learning such theories. The distinguishing features are that 1) Mistle performs predicate invention and inverse resolution, 2) is based on the MDL principle to compress the data, and 3) combines this with frequent pattern mining to find the most interesting theories. The experiments demonstrate that Mistle can learn CNF theories accurately and works well in tasks involving compression and classification.

AIJ Journal 2021 Journal Article

Neural probabilistic logic programming in DeepProbLog

• Robin Manhaeve
• Sebastijan Dumančić
• Angelika Kimmig
• Thomas Demeester
• Luc De Raedt

We introduce DeepProbLog, a neural probabilistic logic programming language that incorporates deep learning by means of neural predicates. We show how existing inference and learning techniques of the underlying probabilistic logic programming language ProbLog can be adapted for the new language. We theoretically and experimentally demonstrate that DeepProbLog supports (i) both symbolic and subsymbolic representations and inference, (ii) program induction, (iii) probabilistic (logic) programming, and (iv) (deep) learning from examples. To the best of our knowledge, this work is the first to propose a framework where general-purpose neural networks and expressive probabilistic-logical modeling and reasoning are integrated in a way that exploits the full expressiveness and strengths of both worlds and can be trained end-to-end based on examples.

ECAI Conference 2020 Conference Paper

Algebraic Circuits for Decision Theoretic Inference and Learning

• Vincent Derkinderen
• Luc De Raedt

While it is well known that arithmetic circuits can be used for efficient probabilistic inference, arithmetic circuits can also be used for other tasks. In this paper, we show how arithmetic circuits in a semiring setting (i. e. , algebraic circuits) can solve decision theoretic inference tasks and a utility learning task under partial observability. The former involves finding the set of decisions that maximises the expected utility. We introduce two approaches for this, both applying algebraic circuits. The learning task involves learning unknown utility values from partially observed interpretations of which the total utility is given. We provide the necessary theory and also perform an experimental evaluation of the approaches.

IJCAI Conference 2020 Conference Paper

From Statistical Relational to Neuro-Symbolic Artificial Intelligence

• Luc De Raedt
• Sebastijan Dumančić
• Robin Manhaeve
• Giuseppe Marra

Neuro-symbolic and statistical relational artificial intelligence both integrate frameworks for learning with logical reasoning. This survey identifies several parallels across seven different dimensions between these two fields. These cannot only be used to characterize and position neuro-symbolic artificial intelligence approaches but also to identify a number of directions for further research.

AAAI Conference 2020 Conference Paper

Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation

• Mohit Kumar
• Samuel Kolb
• Stefano Teso
• Luc De Raedt

Combinatorial optimization problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with a preference function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show – in a particular context – whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism. We provide learnability results within the realizable and agnostic settings, as well as HASSLE, an implementation based on syntax-guided synthesis and showcase its promise on recovering synthetic and benchmark instances from examples.

UAI Conference 2020 Conference Paper

Ordering Variables for Weighted Model Integration

• Vincent Derkinderen
• Evert Heylen
• Pedro Zuidberg Dos Martires
• Samuel Kolb
• Luc De Raedt

State-of-the-art probabilistic inference algorithms, such as variable elimination and search-based approaches, rely heavily on the order in which variables are marginalized. Finding the optimal ordering is an NP-complete problem. This computational hardness has led to heuristics to find adequate variable orderings. However, these heuristics have mostly been targeting discrete random variables. We show how variable ordering heuristics from the discrete domain can be ported to the discrete-continuous domain. We equip the state-of-the-art F-XSDD(BR) solver for discrete-continuous problems with such heuristics. Additionally, we propose a novel heuristic called bottom-up min-fill (BU-MiF), yielding a solver capable of determining good variable orderings without having to rely on the user to provide such an ordering. We empirically demonstrate its performance on a set of benchmark problems.

IJCAI Conference 2020 Conference Paper

ProbAnch: a Modular Probabilistic Anchoring Framework

• Andreas Persson
• Pedro Zuidberg Dos Martires
• Luc De Raedt
• Amy Loufti

Modeling object representations derived from perceptual observations, in a way that is also semantically meaningful for humans as well as autonomous agents, is a prerequisite for joint human-agent understanding of the world. A practical approach that aims to model such representations is perceptual anchoring, which handles the problem of mapping sub-symbolic sensor data to symbols and maintains these mappings over time. In this paper, we present ProbAnch, a modular data-driven anchoring framework, whose implementation requires a variety of well-orchestrated components, including a probabilistic reasoning system.

IJCAI Conference 2019 Conference Paper

Acquiring Integer Programs from Data

• Mohit Kumar
• Stefano Teso
• Luc De Raedt

Integer programming (IP) is widely used within operations research to model and solve complex combinatorial problems such as personnel rostering and assignment problems. Modelling such problems is difficult for non-experts and expensive when hiring domain experts to perform the modelling. For many tasks, however, examples of working solutions are readily available. We propose ARNOLD, an approach that partially automates the modelling step by learning an integer program from example solutions. Contrary to existing alternatives, ARNOLD natively handles multi-dimensional quantities and non-linear operations, which are at the core of IP problems, and it only requires examples of feasible solution. The main challenge is to efficiently explore the space of possible programs. Our approach pairs a general-to-specific traversal strategy with a nested lexicographic ordering in order to prune large portions of the space of candidate constraints while avoiding visiting the same candidate multiple times. Our empirical evaluation shows that ARNOLD can acquire models for a number of realistic benchmark problems

AAAI Conference 2019 Conference Paper

Exact and Approximate Weighted Model Integration with Probability Density Functions Using Knowledge Compilation

• Pedro Zuidberg Dos Martires
• Anton Dries
• Luc De Raedt

Weighted model counting has recently been extended to weighted model integration, which can be used to solve hybrid probabilistic reasoning problems. Such problems involve both discrete and continuous probability distributions. We show how standard knowledge compilation techniques (to SDDs and d-DNNFs) apply to weighted model integration, and use it in two novel solvers, one exact and one approximate solver. Furthermore, we extend the class of employable weight functions to actual probability density functions instead of mere polynomial weight functions.

UAI Conference 2019 Conference Paper

How to Exploit Structure while Solving Weighted Model Integration Problems

• Samuel Kolb
• Pedro Zuidberg Dos Martires
• Luc De Raedt

Weighted model counting (WMC) is a state-of-the-art technique for probabilistic inference in discrete domains. WMC has recently been extended towards weighted model integration (WMI) in order to handle discrete and continuous distributions alike. While a number of WMI solvers have been introduced, their relationships, strengths and weaknesses are not yet well understood. WMI solving consists of two sub-problems: 1) finding convex polytopes; and 2) integrating over them efficiently. We formalize the first step as $\lambda$-SMT and discuss what strategies solvers apply to solve both the $\lambda$-SMT and the integration problem. This formalization allows us to compare state-of-the-art solvers and their behaviour across different types of WMI problems. Moreover, we identify factorizability of WMI problems as a key property that emerges in the context of probabilistic programming. Problems that can be factorized can be solved more efficiently. However, current solvers exploiting this property restrict themselves to WMI problems with univariate conditions and fully factorizable weight functions. We introduce a new algorithm, F-XSDD, that lifts these restrictions and can exploit factorizability in WMI problems with multivariate conditions and partially factorizable weight functions. Through an empirical evaluation, we show the effectiveness of our approach.

NeSy Conference 2019 Conference Paper

Neuro-Symbolic = Neural + Logical + Probabilistic

• Luc De Raedt
• Robin Manhaeve
• Sebastijan Dumancic
• Thomas Demeester
• Angelika Kimmig

The overall goal of neuro-symbolic computation is to integrate high-level reasoning with low-level perception. We argue 1) that neuro-symbolic computation should integrate neural networks with the two most prominent methods for reasoning, that is, logic and probability, and 2) that neuro-symbolic integrated methods should have the pure neural, logical and probabilistic methods as special cases. We examine the state-of-the-art with regard to these claims and briefly position our own contribution DeepProbLog in this perspective.

IJCAI Conference 2019 Conference Paper

The pywmi Framework and Toolbox for Probabilistic Inference using Weighted Model Integration

• Samuel Kolb
• Paolo Morettin
• Pedro Zuidberg Dos Martires
• Francesco Sommavilla
• Andrea Passerini
• Roberto Sebastiani
• Luc De Raedt

Weighted Model Integration (WMI) is a popular technique for probabilistic inference that extends Weighted Model Counting (WMC) -- the standard inference technique for inference in discrete domains -- to domains with both discrete and continuous variables. However, existing WMI solvers each have different interfaces and use different formats for representing WMI problems. Therefore, we introduce pywmi (http: //pywmi. org), an open source framework and toolbox for probabilistic inference using WMI, to address these shortcomings. Crucially, pywmi fixes a common internal format for WMI problems and introduces a common interface for WMI solvers. To assist users in modeling WMI problems, pywmi introduces modeling languages based on SMT-LIB. v2 or MiniZinc and parsers for both. To assist users in comparing WMI solvers, pywmi includes implementations of several state-of-the-art solvers, a fast approximate WMI solver, and a command-line interface to solve WMI problems. Finally, to assist developers in implementing new solvers, pywmi provides Python implementations of commonly used subroutines.

NeurIPS Conference 2018 Conference Paper

DeepProbLog: Neural Probabilistic Logic Programming

• Robin Manhaeve
• Sebastijan Dumancic
• Angelika Kimmig
• Thomas Demeester
• Luc De Raedt

We introduce DeepProbLog, a probabilistic logic programming language that incorporates deep learning by means of neural predicates. We show how existing inference and learning techniques can be adapted for the new language. Our experiments demonstrate that DeepProbLog supports (i) both symbolic and subsymbolic representations and inference, (ii) program induction, (iii) probabilistic (logic) programming, and (iv) (deep) learning from examples. To the best of our knowledge, this work is the first to propose a framework where general-purpose neural networks and expressive probabilistic-logical modeling and reasoning are integrated in a way that exploits the full expressiveness and strengths of both worlds and can be trained end-to-end based on examples.

AAAI Conference 2018 Conference Paper

Learning Constraints From Examples

• Luc De Raedt
• Andrea Passerini
• Stefano Teso

While constraints are ubiquitous in artificial intelligence and constraints are also commonly used in machine learning and data mining, the problem of learning constraints from examples has received less attention. In this paper, we discuss the problem of constraint learning in detail, indicate some subtle differences with standard machine learning problems, sketch some applications and summarize the state-of-the-art.

IJCAI Conference 2018 Conference Paper

Learning SMT(LRA) Constraints using SMT Solvers

• Samuel Kolb
• Stefano Teso
• Andrea Passerini
• Luc De Raedt

We introduce the problem of learning SMT(LRA) constraints from data. SMT(LRA) extends propositional logic with (in)equalities between numerical variables. Many relevant formal verification problems can be cast as SMT(LRA) instances and SMT(LRA) has supported recent developments in optimization and counting for hybrid Boolean and numerical domains. We introduce SMT(LRA) learning, the task of learning SMT(LRA) formulas from examples of feasible and infeasible instances, and we contribute INCAL, an exact non-greedy algorithm for this setting. Our approach encodes the learning task itself as an SMT(LRA) satisfiability problem that can be solved directly by SMT solvers. INCAL is an incremental algorithm that achieves exact learning by looking only at a small subset of the data, leading to significant speed-ups. We empirically evaluate our approach on both synthetic instances and benchmark problems taken from the SMT-LIB benchmarks repository.

AIJ Journal 2017 Journal Article

MiningZinc: A declarative framework for constraint-based mining

• Tias Guns
• Anton Dries
• Siegfried Nijssen
• Guido Tack
• Luc De Raedt

We introduce MiningZinc, a declarative framework for constraint-based data mining. MiningZinc consists of two key components: a language component and an execution mechanism. First, the MiningZinc language allows for high-level and natural modeling of mining problems, so that MiningZinc models are similar to the mathematical definitions used in the literature. It is inspired by the Zinc family of languages and systems and supports user-defined constraints and functions. Secondly, the MiningZinc execution mechanism specifies how to compute solutions for the models. It is solver independent and supports both standard constraint solvers and specialized data mining systems. The high-level problem specification is first translated into a normalized constraint language (FlatZinc). Rewrite rules are then used to add redundant constraints or solve subproblems using specialized data mining algorithms or generic constraint programming solvers. Given a model, different execution strategies are automatically extracted that correspond to different sequences of algorithms to run. Optimized data mining algorithms, specialized processing routines and generic solvers can all be automatically combined. Thus, the MiningZinc language allows one to model constraint-based itemset mining problems in a solver independent way, and its execution mechanism can automatically chain different algorithms and solvers. This leads to a unique combination of declarative modeling with high-performance solving.

IJCAI Conference 2017 Conference Paper

Solving Probability Problems in Natural Language

• Anton Dries
• Angelika Kimmig
• Jesse Davis
• Vaishak Belle
• Luc De Raedt

The ability to solve probability word problems such as those found in introductory discrete mathematics textbooks, is an important cognitive and intellectual skill. In this paper, we develop a two-step end-to-end fully automated approach for solving such questions that is able to automatically provide answers to exercises about probability formulated in natural language. In the first step, a question formulated in natural language is analysed and transformed into a high-level model specified in a declarative language. In the second step, a solution to the high-level model is computed using a probabilistic programming system. On a dataset of 2160 probability problems, our solver is able to correctly answer 97. 5% of the questions given a correct model. On the end-to-end evaluation, we are able to answer 12. 5% of the questions (or 31. 1% if we exclude examples not supported by design).

IJCAI Conference 2017 Conference Paper

Stochastic Constraint Programming with And-Or Branch-and-Bound

• Behrouz Babaki
• Tias Guns
• Luc De Raedt

Complex multi-stage decision making problems often involve uncertainty, for example, regarding demand or processing times. Stochastic constraint programming was proposed as a way to formulate and solve such decision problems, involving arbitrary constraints over both decision and random variables. What stochastic constraint programming still lacks is support for the use of factorized probabilistic models that are popular in the graphical model community. We show how a state-of-the-art probabilistic inference engine can be integrated into standard constraint solvers. The resulting approach searches over the And-Or search tree directly, and we investigate tight bounds on the expected utility objective. This significantly improves search efficiency and outperforms scenario-based methods that ground out the possible worlds.

IS Journal 2017 Journal Article

The Inductive Constraint Programming Loop

• Christian Bessiere
• Luc De Raedt
• Tias Guns
• Lars Kotthoff
• Mirco Nanni
• Siegfried Nijssen
• Barry O'Sullivan
• Anastasia Paparrizou

Constraint programming is used for a variety of real-world optimization problems, such as planning, scheduling, and resource allocation problems, all while we continuously gather vast amounts of data about these problems. Current constraint programming software doesn't exploit such data to update schedules, resources, and plans. The authors propose a new framework that they call the inductive constraint programming loop. In this approach, data is gathered and analyzed systematically to dynamically revise and adapt constraints and optimization criteria. Inductive constraint programming aims to bridge the gap between the areas of data mining and machine learning on one hand and constraint programming on the other.

AIJ Journal 2016 Journal Article

Exploiting local and repeated structure in Dynamic Bayesian Networks

• Jonas Vlasselaer
• Wannes Meert
• Guy Van den Broeck
• Luc De Raedt

We introduce the structural interface algorithm for exact probabilistic inference in Dynamic Bayesian Networks. It unifies state-of-the-art techniques for inference in static and dynamic networks, by combining principles of knowledge compilation with the interface algorithm. The resulting algorithm not only exploits the repeated structure in the network, but also the local structure, including determinism, parameter equality and context-specific independence. Empirically, we show that the structural interface algorithm speeds up inference in the presence of local structure, and scales to larger and more complex networks.

ECAI Conference 2016 Conference Paper

Learning the Structure of Dynamic Hybrid Relational Models

• Davide Nitti 0001
• Irma Ravkic
• Jesse Davis
• Luc De Raedt

Typical approaches to relational MDPs consider only discrete variables or else discretize the continuous variables prior to inference or learning. In contrast, we consider hybrid relational MDPs, which are represented as probabilistic programs and specify the probability density function of the continuous variables. Our key contribution is that we introduce a technique for learning their structure (and parameters) from data. The learned models contain rich relational descriptions as well as mathematical equations. We demonstrate the utility of our approach by learning a model that accurately predicts the effects of robot-arm actions. The learned model is then used for planning tasks.

IJCAI Conference 2015 Conference Paper

Anytime Inference in Probabilistic Logic Programs with Tp-Compilation

• Jonas Vlasselaer
• Guy Van den Broeck
• Angelika Kimmig
• Wannes Meert
• Luc De Raedt

Existing techniques for inference in probabilistic logic programs are sequential: they first compute the relevant propositional formula for the query of interest, then compile it into a tractable target representation and finally, perform weighted model counting on the resulting representation. We propose TP -compilation, a new inference technique based on forward reasoning. TP -compilation proceeds incrementally in that it interleaves the knowledge compilation step for weighted model counting with forward reasoning on the logic program. This leads to a novel anytime algorithm that provides hard bounds on the inferred probabilities. Furthermore, an empirical evaluation shows that TP compilation effectively handles larger instances of complex real-world problems than current sequential approaches, both for exact and for anytime approximate inference.

IJCAI Conference 2015 Conference Paper

Graph Invariant Kernels

• Francesco Orsini
• Paolo Frasconi
• Luc De Raedt

We introduce a novel kernel that upgrades the Weisfeiler-Lehman and other graph kernels to effectively exploit highdimensional and continuous vertex attributes. Graphs are first decomposed into subgraphs. Vertices of the subgraphs are then compared by a kernel that combines the similarity of their labels and the similarity of their structural role, using a suitable vertex invariant. By changing this invariant we obtain a family of graph kernels which includes generalizations of Weisfeiler-Lehman, NSPDK, and propagation kernels. We demonstrate empirically that these kernels obtain state-ofthe-art results on relational data sets.

IJCAI Conference 2015 Conference Paper

Inducing Probabilistic Relational Rules from Probabilistic Examples

• Luc De Raedt
• Anton Dries
• Ingo Thon
• Guy Van den Broeck
• Mathias Verbeke

We study the problem of inducing logic programs in a probabilistic setting, in which both the example descriptions and their classification can be probabilistic. The setting is incorporated in the probabilistic rule learner ProbFOIL+, which combines principles of the rule learner FOIL with ProbLog, a probabilistic Prolog. We illustrate the approach by applying it to the knowledge base of NELL, the Never-Ending Language Learner.

IJCAI Conference 2015 Conference Paper

kLog: A Language for Logical and Relational Learning with Kernels (Extended Abstract)

• Paolo Frasconi
• Fabrizio Costa
• Luc De Raedt
• Kurt De Grave

We introduce kLog, a novel language for kernelbased learning on expressive logical and relational representations. kLog allows users to specify logical and relational learning problems declaratively. It builds on simple but powerful concepts: learning from interpretations, entity/relationship data modeling, and logic programming. Access by the kernel to the rich representation is mediated by a technique we call graphicalization: the relational representation is first transformed into a graph — in particular, a grounded entity/relationship diagram. Subsequently, a choice of graph kernel defines the feature space. The kLog framework can be applied to tackle the same range of tasks that has made statistical relational learning so popular, including classification, regression, multitask learning, and collective classification. An empirical evaluation shows that kLog can be either more accurate, or much faster at the same level of accuracy, than Tilde and Alchemy. kLog is GPLv3 licensed and is available at http: //klog. dinfo. unifi. it along with tutorials.

AAAI Conference 2015 Conference Paper

Languages for Learning and Mining

• Luc De Raedt

Applying machine learning and data mining to novel applications is cumbersome. This observation is the prime motivation for the interest in languages for learning and mining. This note provides a gentle introduction to three types of languages that support machine learning and data mining: inductive query languages, which extend database query languages with primitives for mining and learning, modelling languages, which allow to declaratively specify and solve mining and learning problems, and programming languages, that support the learning of functions and subroutines. It uses an example of each type of language to introduce the underlying ideas and puts them into a common perspective. This then forms the basis for a short analysis of the state-ofthe-art.

EWRL Workshop 2015 Workshop Paper

Sample-based abstraction for hybrid relational MDPs

• Davide Nitti
• Vaishak Belle
• Tinne De Laet
• Luc De Raedt

We study planning in relational Markov Decision Processes involving discrete and continuous states and actions. This combination of hybrid relational domains has so far not received a lot of attention. While several symbolic approaches have been proposed for hybrid and relational domains separately, they generally do not provide an integrated approach and they often make restrictive assumptions to make exact inference possible. Removing those restrictions requires approximations such as Monte-Carlo methods. We propose HyBrel: a sample-based planner for hybrid relational domains that combines model-based approaches with state abstraction. HyBrel samples episodes and uses the previous episodes as well as the model to approximate the Q-function. Abstraction is performed for each sampled episode, this removes typical restrictions of symbolic approaches. In our empirical evaluations, HyBrel is shown to have a wide applicability, confirming the advantage of sampled-based abstraction.

ECAI Conference 2014 Conference Paper

Condition Monitoring with Incomplete Observations

• Jonas Vlasselaer
• Wannes Meert
• Rocco Langone
• Luc De Raedt

We introduce an approach for predicting the behaviour of a machine during a production cycle. Typical data analysis methods assume that continuous behaviour is (fully) observed. This assumption is unrealistic as monitored machines are often interrupted and restarted at irregular points in time. We study the resulting problem, propose a solution and report on a use-case in wire drawing.

AAAI Conference 2014 Conference Paper

Explanation-Based Approximate Weighted Model Counting for Probabilistic Logics

• Joris Renkens
• Angelika Kimmig
• Guy Van den Broeck
• Luc De Raedt

Probabilistic inference can be realized using weighted model counting. Despite a lot of progress, computing weighted model counts exactly is still infeasible for many problems of interest, and one typically has to resort to approximation methods. We contribute a new bounded approximation method for weighted model counting based on probabilistic logic programming principles. Our bounded approximation algorithm is an anytime algorithm that provides lower and upper bounds on the weighted model count. An empirical evaluation on probabilistic logic programs shows that our approach is effective in many cases that are currently beyond the reach of exact methods.

AIJ Journal 2014 Journal Article

kLog: A language for logical and relational learning with kernels

• Paolo Frasconi
• Fabrizio Costa
• Luc De Raedt
• Kurt De Grave

We introduce kLog, a novel approach to statistical relational learning. Unlike standard approaches, kLog does not represent a probability distribution directly. It is rather a language to perform kernel-based learning on expressive logical and relational representations. kLog allows users to specify learning problems declaratively. It builds on simple but powerful concepts: learning from interpretations, entity/relationship data modeling, logic programming, and deductive databases. Access by the kernel to the rich representation is mediated by a technique we call graphicalization: the relational representation is first transformed into a graph — in particular, a grounded entity/relationship diagram. Subsequently, a choice of graph kernel defines the feature space. kLog supports mixed numerical and symbolic data, as well as background knowledge in the form of Prolog or Datalog programs as in inductive logic programming systems. The kLog framework can be applied to tackle the same range of tasks that has made statistical relational learning so popular, including classification, regression, multitask learning, and collective classification. We also report about empirical comparisons, showing that kLog can be either more accurate, or much faster at the same level of accuracy, than Tilde and Alchemy. kLog is GPLv3 licensed and is available at http: //klog. dinfo. unifi. it along with tutorials.

IROS Conference 2014 Conference Paper

Learning relational affordance models for two-arm robots

• Bogdan Moldovan
• Luc De Raedt

Affordances are used in robotics to model action opportunities of a robotic manipulator on an object in the environment. Previous work has shown how statistical relational learning can be used in a discrete setting to extend affordances to model relations and interactions between multiple objects being manipulated by a robotic arm and deal with environment uncertainty. In this paper, we first extend this concept of relational affordances to a continuous setting and then to a two-arm robot. A relational affordance model can first be learnt for one arm through a behavioural babbling stage, and then with the use of statistical relational learning, after constructing a symmetrical model for the other arm, two-arm manipulation actions can be modelled, where the arms can act sequentially or simultaneously. The model is evaluated in a two-arm action recognition task in a shelf object manipulation setting.

ICRA Conference 2014 Conference Paper

Occluded object search by relational affordances

• Bogdan Moldovan
• Luc De Raedt

Searching for objects in occluded spaces is one of the problems robots need to solve when tackling mobile manipulation tasks. Most approaches focus only on searching for a specific object. In this paper, we use the concept of relational affordances to improve occluded object search performance. Affordances define action possibilities on an object in the environment and play a role in basic cognitive capabilities. Relational affordances extend this concept by modelling relations between multiple objects. By learning and using a relational affordance model we can search for any of the multiple objects that afford a given action, each object type having a probability distribution over possible sizes and shapes, and where spatial relations between objects such as co-occurrence and stacking are modelled. The experimental results show the viability of the relational affordance models for occluded object search.

ICRA Conference 2014 Conference Paper

Relational object tracking and learning

• Davide Nitti 0001
• Tinne De Laet
• Luc De Raedt

We propose a relational model for online object tracking during human activities using the Distributional Clauses Particle Filter framework, which allows to encode commonsense world knowledge such as qualitative physical laws, object properties as well as relations between them. We tested the framework during a packaging activity where many objects are invisible for longer periods of time. In addition, we extended the framework to learn the parameters online and tested it in a tracking scenario involving objects connected by strings.

IROS Conference 2013 Conference Paper

A particle filter for hybrid relational domains

• Davide Nitti 0001
• Tinne De Laet
• Luc De Raedt

We introduce a probabilistic language and a fast inference algorithm for state estimation in hybrid dynamic relational domains with an unknown number of objects. More specifically, we apply Particle Filters to distributional clauses. The particles represent (partial) interpretations of possible worlds (with discrete and/or continuous variables) and the filter recursively updates its beliefs about the current state. We use backward reasoning to determine which facts should be included in the partial interpretations. Experiments show that our framework can outperform the classical particle filter and is promising for robotics applications.

IJCAI Conference 2013 Conference Paper

MiningZinc: A Modeling Language for Constraint-based Mining

• Tias Guns
• Anton Dries
• Guido Tack
• Siegfried Nijssen
• Luc De Raedt

We introduce MiningZinc, a general framework for constraint-based pattern mining, one of the most popular tasks in data mining. MiningZinc consists of two key components: a language component and a toolchain component. The language allows for high-level and natural modeling of mining problems, such that MiningZinc models closely resemble definitions found in the data mining literature. It is inspired by the Zinc family of languages and systems and supports user-defined constraints and optimization criteria. The toolchain allows for finding solutions to the models. It ensures the solver independence of the language and supports both standard constraint solvers and specialized data mining systems. Automatic model transformations enable the efficient use of different solvers and systems. The combination of both components allows one to rapidly model constraint-based mining problems and execute these with a wide variety of methods. We demonstrate this experimentally for a number of well-known solvers and data mining tasks.

ICRA Conference 2012 Conference Paper

Learning relational affordance models for robots in multi-object manipulation tasks

• Bogdan Moldovan
• Plinio Moreno
• Martijn van Otterlo
• José Santos-Victor
• Luc De Raedt

Affordances define the action possibilities on an object in the environment and in robotics they play a role in basic cognitive capabilities. Previous works have focused on affordance models for just one object even though in many scenarios they are defined by configurations of multiple objects that interact with each other. We employ recent advances in statistical relational learning to learn affordance models in such cases. Our models generalize over objects and can deal effectively with uncertainty. Two-object interaction models are learned from robotic interaction with the objects in the world and employed in situations with arbitrary numbers of objects. We illustrate these ideas with experimental results of an action recognition task where a robot manipulates objects on a shelf.

AAAI Conference 2011 Conference Paper

An Algebraic Prolog for Reasoning about Possible Worlds

• Angelika Kimmig
• Guy Van den Broeck
• Luc De Raedt

We introduce aProbLog, a generalization of the probabilistic logic programming language ProbLog. An aProbLog program consists of a set of definite clauses and a set of algebraic facts; each such fact is labeled with an element of a semiring. A wide variety of labels is possible, ranging from probability values to reals (representing costs or utilities), polynomials, Boolean functions or data structures. The semiring is then used to calculate labels of possible worlds and of queries. We formally define the semantics of aProbLog and study the aProbLog inference problem, which is concerned with computing the label of a query. Two conditions are introduced that allow one to simplify the inference problem, resulting in four different algorithms and settings. Representative basic problems for each of these four settings are: is there a possible world where a query is true (SAT), how many such possible worlds are there (#SAT), what is the probability of a query being true (PROB), and what is the most likely world where the query is true (MPE). We further illustrate these settings with a number of tasks requiring more complex semirings.

UAI Conference 2011 Conference Paper

Inference in Probabilistic Logic Programs using Weighted CNF's

• Daan Fierens
• Guy Van den Broeck
• Ingo Thon
• Bernd Gutmann
• Luc De Raedt

Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. Several classical probabilistic inference tasks (such as MAP and computing marginals) have not yet received a lot of attention for this formalism. The contribution of this paper is that we develop efficient inference algorithms for these tasks. This is based on a conversion of the probabilistic logic program and the query and evidence to a weighted CNF formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting. To solve such tasks, we employ state-of-the-art methods. We consider multiple methods for the conversion of the programs as well as for inference on the weighted CNF. The resulting approach is evaluated experimentally and shown to improve upon the state-of-the-art in probabilistic logic programming.

AIJ Journal 2011 Journal Article

Itemset mining: A constraint programming perspective

• Tias Guns
• Siegfried Nijssen
• Luc De Raedt

The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and constraint programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative constraint programming approach to data mining.

IJCAI Conference 2011 Conference Paper

Lifted Probabilistic Inference by First-Order Knowledge Compilation

• Guy Van den Broeck
• Nima Taghipour
• Wannes Meert
• Jesse Davis
• Luc De Raedt

Probabilistic logical languages provide powerful formalisms forknowledge representation and learning. Yet performing inference inthese languages is extremely costly, especially if it is done at thepropositional level. Lifted inference algorithms, which avoid repeatedcomputation by treating indistinguishable groups of objects as one, helpmitigate this cost. Seeking inspiration from logical inference, wherelifted inference (e. g. , resolution) is commonly performed, we developa model theoretic approach to probabilistic lifted inference. Our algorithmcompiles a first-order probabilistic theory into a first-orderdeterministic decomposable negation normal form (d-DNNF) circuit. Compilation offers the advantage that inference is polynomial in thesize of the circuit. Furthermore, by borrowing techniques from theknowledge compilation literature our algorithm effectively exploitsthe logical structure (e. g. , context-specific independencies) withinthe first-order model, which allows more computation to be done at the lifted level. An empirical comparison demonstrates the utility of the proposed approach.

AAAI Conference 2010 Conference Paper

Constraint Programming for Data Mining and Machine Learning

• Luc De Raedt
• Tias Guns
• Siegfried Nijssen

Machine learning and data mining have become aware that using constraints when learning patterns and rules can be very useful. To this end, a large number of special purpose systems and techniques have been developed for solving such constraint-based mining and learning problems. These techniques have, so far, been developed independently of the general purpose tools and principles of constraint programming known within the field of artificial intelligence. This paper shows that off-the-shelf constraint programming techniques can be applied to various pattern mining and rule learning problems (cf. also (De Raedt, Guns, and Nijssen 2008; Nijssen, Guns, and De Raedt 2009)). This does not only lead to methodologies that are more general and flexible, but also provides new insights into the underlying mining problems that allow us to improve the state-ofthe-art in data mining. Such a combination of constraint programming and data mining raises a number of interesting new questions and challenges.

AAAI Conference 2010 Conference Paper

DTProbLog: A Decision-Theoretic Probabilistic Prolog

• Guy Van den Broeck
• Ingo Thon
• Martijn van Otterlo
• Luc De Raedt

We introduce DTPROBLOG, a decision-theoretic extension of Prolog and its probabilistic variant ProbLog. DT- PROBLOG is a simple but expressive probabilistic programming language that allows the modeling of a wide variety of domains, such as viral marketing. In DTPROBLOG, the utility of a strategy (a particular choice of actions) is defined as the expected reward for its execution in the presence of probabilistic effects. The key contribution of this paper is the introduction of exact, as well as approximate, solvers to compute the optimal strategy for a DTPROBLOG program and the decision problem it represents, by making use of binary and algebraic decision diagrams. We also report on experimental results that show the effectiveness and the practical usefulness of the approach.

ECAI Conference 2010 Conference Paper

ProbLog Technology for Inference in a Probabilistic First Order Logic

• Maurice Bruynooghe
• Theofrastos Mantadelis
• Angelika Kimmig
• Bernd Gutmann
• Joost Vennekens
• Gerda Janssens
• Luc De Raedt

We introduce First Order ProbLog, an extension of first order logic with soft constraints where formulas are guarded by probabilistic facts. The paper defines a semantics for FOProbLog, develops a translation into ProbLog, a system that allows a user to compute the probability of a query in a similar setting restricted to Horn clauses, and reports on initial experience with inference.

IJCAI Conference 2009 Conference Paper

• Angelika Kimmig
• Luc De Raedt

Local pattern mining is concerned with finding the set of patterns that satisfy a constraint in a database. We study local pattern mining in the context of ProbLog, a probabilistic Prolog system, and introduce an approach for finding correlated patterns in the form of queries in such a Prolog system. The approach combines principles of inductive logic programming, data mining and statistical relational learning. Experiments on a challenging biological network mining task provide evidence for the interestingness of the approach.

AIJ Journal 2008 Journal Article

An experimental evaluation of simplicity in rule learning

• Ulrich Rückert
• Luc De Raedt

While recent research on rule learning has focused largely on finding highly accurate hypotheses, we evaluate the degree to which these hypotheses are also simple, that is small. To realize this, we compare well-known rule learners, such as CN2, RIPPER, PART, FOIL and C5. 0 rules, with the benchmark system SL2 that explicitly aims at computing small rule sets with few literals. The results show that it is possible to obtain a similar level of accuracy as state-of-the-art rule learners using much smaller rule sets.

IJCAI Conference 2007 Conference Paper

• Luc De Raedt
• Angelika Kimmig
• Hannu Toivonen

We introduce ProbLog, a probabilistic extension of Prolog. A ProbLog program defines a distribution over logic programs by specifying for each clause the probability that it belongs to a randomly sampled program, and these probabilities are mutually independent. The semantics of ProbLog is then defined by the success probability of a query, which corresponds to the probability that the query succeeds in a randomly sampled program. The key contribution of this paper is the introduction of an effective solver for computing success probabilities. It essentially combines SLD-resolution with methods for computing the probability of Boolean formulae. Our implementation further employs an approximation algorithm that combines iterative deepening with binary decision diagrams. We report on experiments in the context of discovering links in real biological networks, a demonstration of the practical usefulness of the approach.

IJCAI Conference 2007 Conference Paper

• Niels Landwehr
• Luc De Raedt

We introduce relational grams (r-grams). They upgrade n-grams for modeling relational sequences of atoms. As n-grams, r-grams are based on smoothed n-th order Markov chains. Smoothed distributions can be obtained by decreasing the order of the Markov chain as well as by relational generalization of the r-gram. To avoid sampling object identifiers in sequences, r-grams are generative models at the level of variablized sequences with local object identity constraints. These sequences define equivalence classes of ground sequences, in which elements are identical up to local identifier renaming. The proposed technique is evaluated in several domains, including mobile phone communication logs, Unix shell user modeling, and protein fold prediction based on secondary protein structure.

IJCAI Conference 2007 Conference Paper

• Gemma C. Garriga
• Roni Khardon
• Luc De Raedt

We investigate the problem of mining closed sets in multi-relational databases. Previous work introduced different semantics and associated algorithms for mining closed sets in multi-relational databases. However, insight into the implications of semantic choices and the relationships among them was still lacking. Our investigation shows that the semantic choices are important because they imply different properties, which in turn affect the range of algorithms that can mine for such sets. Of particular interest is the question whether the seminal LCM algorithm by Uno et al. can be upgraded towards multi-relational problems. LCM is attractive since its run time is linear in the number of closed sets and it does not need to store outputs in order to avoid duplicates. We provide a positive answer to this question for some of the semantic choices, and report on experiments that evaluate the scalability and applicability of the upgraded algorithm on benchmark problems.

JMLR Journal 2007 Journal Article

Integrating Naïve Bayes and FOIL

• Niels Landwehr
• Kristian Kersting
• Luc De Raedt

A novel relational learning approach that tightly integrates the naïve Bayes learning scheme with the inductive logic programming rule-learner FOIL is presented. In contrast to previous combinations that have employed naïve Bayes only for post-processing the rule sets, the presented approach employs the naïve Bayes criterion to guide its search directly. The proposed technique is implemented in the N FOIL and T FOIL systems, which employ standard naïve Bayes and tree augmented naïve Bayes models respectively. We show that these integrated approaches to probabilistic model and rule learning outp erform post-processing approaches. They also yield significantly more accurate models than si mple rule learning and are competitive with more sophisticated ILP systems. [abs] [ pdf ][ bib ] &copy JMLR 2007. ( edit, beta )

NeSy Conference 2007 Conference Paper

Statistical Relational Learning - A Logical Approach (Abstract of Invited Talk)

• Luc De Raedt

In this talk I will briefly outline and survey some developments in the field of statistical relation learning, especially focussing on logical approaches. Statistical relational learning is a novel research stream within artificial intelligence that combines principles of relational logic, learning and probabilistic models. This endeavor is similar in spirit to the developments in Neural Symbolic Reasoning in that it attempts to integrate symbolic representation and reasoning methods with the advantages of subsymbolic representations. In the talk, I shall attempt to make this link more explicit and to present an overview of the state of the art in Statistical Relational Learning. This overview shall start by providing some background in logical approaches to learning (relational learning and inductive logic programming) and then extend it with probabilistic elements.

JMLR Journal 2006 Journal Article

Kernels on Prolog Proof Trees: Statistical Learning in the ILP Setting

• Andrea Passerini
• Paolo Frasconi
• Luc De Raedt

We develop kernels for measuring the similarity between relational instances using background knowledge expressed in first-order logic. The method allows us to bridge the gap between traditional inductive logic programming (ILP) representations and statistical approaches to supervised learning. Logic programs are first used to generate proofs of given visitor programs that use predicates declared in the available background knowledge. A kernel is then defined over pairs of proof trees. The method can be used for supervised learning tasks and is suitable for classification as well as regression. We report positive empirical results on Bongard-like and M -of- N problems that are difficult or impossible to solve with traditional ILP techniques, as well as on real bioinformatics and chemoinformatics data sets. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

AAAI Conference 2006 Conference Paper

kFOIL: Learning Simple Relational Kernels

• Niels Landwehr
• Luc De Raedt

A novel and simple combination of inductive logic programming with kernel methods is presented. The kFOIL algorithm integrates the well-known inductive logic programming system FOIL with kernel methods. The feature space is constructed by leveraging FOIL search for a set of relevant clauses. The search is driven by the performance obtained by a support vector machine based on the resulting kernel. In this way, kFOIL implements a dynamic propositionalization approach. Both classification and regression tasks can be naturally handled. Experiments in applying kFOIL to wellknown benchmarks in chemoinformatics show the promise of the approach.

IROS Conference 2006 Conference Paper

Learning Relational Navigation Policies

• Alexandru Cocora
• Kristian Kersting
• Christian Plagemann
• Wolfram Burgard
• Luc De Raedt

Navigation is one of the fundamental tasks for a mobile robot. The majority of path planning approaches has been designed to entirely solve the given problem from scratch given the current and goal configurations of the robot. Although these approaches yield highly efficient plans, the computed policies typically do not transfer to other, similar tasks. We propose to learn relational decision trees as abstract navigation strategies from example paths. Relational abstraction has several interesting and important properties. First, it allows a mobile robot to generalize navigation plans from specific examples provided by users or exploration. Second, the navigation policy learned in one environment can be transferred to unknown environments. In several experiments with real robots in a real environment and in simulated runs, we demonstrate the usefulness of our approach

AAAI Conference 2005 Conference Paper

Towards Learning Stochastic Logic Programs from Proof-Banks

• Luc De Raedt

Stochastic logic programs combine ideas from probabilistic grammars with the expressive power of definite clause logic; as such they can be considered as an extension of probabilistic context-free grammars. Motivated by an analogy with learning tree-bank grammars, we study how to learn stochastic logic programs from proof-trees. Using proof-trees as examples imposes strong logical constraints on the structure of the target stochastic logic program. These constraints can be integrated in the least general generalization (lgg) operator, which is employed to traverse the search space. Our implementation employs a greedy search guided by the maximum likelihood principle and failure-adjusted maximization. We also report on a number of simple experiments that show the promise of the approach.

ICML Conference 2004 Conference Paper

Bellman goes relational

• Kristian Kersting
• Martijn van Otterlo
• Luc De Raedt

KR Conference 2004 Conference Paper

Condensed Representations for Inductive Logic Programming

• Luc De Raedt
• Jan Ramon

When mining frequent Datalog queries, many queries will cover the same examples; i. e., they will be equivalent and hence, redundant. The equivalences can be due to the data set or to the regularities specified in the background theory. To avoid the generation of redundant clauses, we introduce various types of condensed representations. More specifically, we introduce delta-free and closed clauses, that are defined w. r. t. the data set, and semantically free and closed clauses, that take into account a logical background theory. A novel algorithm that employs these representations is also presented and experimentally evaluated on a number of benchmark problems in inductive logic programming.

ICML Conference 2001 Conference Paper

Feature Construction with Version Spaces for Biochemical Applications

• Stefan Kramer 0001
• Luc De Raedt

ICML Conference 1998 Conference Paper

Relational Reinforcement Learning

• Saso Dzeroski
• Luc De Raedt
• Hendrik Blockeel

ICML Conference 1998 Conference Paper

Top-Down Induction of Clustering Trees

• Hendrik Blockeel
• Luc De Raedt
• Jan Ramon

AIJ Journal 1998 Journal Article

Top-down induction of first-order logical decision trees

• Hendrik Blockeel
• Luc De Raedt

A first-order framework for top-down induction of logical decision trees is introduced. The expressivity of these trees is shown to be larger than that of the flat logic programs which are typically induced by classical ILP systems, and equal to that of first-order decision lists. These results are related to predicate invention and mixed variable quantification. Finally, an implementation of this framework, the TILDE system, is presented and empirically evaluated.

AIJ Journal 1997 Journal Article

Logical settings for concept-learning

• Luc De Raedt

Three different formalizations of concept-learning in logic (as well as some variants) are analyzed and related. It is shown that learning from interpretations reduces to learning from entailment, which in turn reduces to learning from satisfiability. The implications of this result for inductive logic programming and computational learning theory are then discussed, and guidelines for choosing a problem-setting are formulated.

IJCAI Conference 1995 Conference Paper

Forgetting and Compacting data in Concept Learning

• Gunther Sablon
• Luc De Raedt

Incremental concept learning algorithms using backtracking have to store previous data. These data can be ordered by the "is more specific than" relation. Using this order only the most informative data have to be stored, and the less informative data can be discarded. Moreover, under certain conditions some data can be replaced by automatically generated, more informative data. We investigate some conditions for data to be discarded, independently of the chosen concept learning algorithm or concept representation language. Then an algorithm for discarding data is presented in the framework of Iterative Versionspaces, which is a depth-first algorithm computing versionspaces as introduced by Mitchell. We update the datastructures used in the Iterative Versionspaces algorithm, while preserving its most important properties.

AIJ Journal 1994 Journal Article

First-order jk-clausal theories are PAC-learnable

• Luc De Raedt
• Sašo Džeroski

We present positive PAC-learning results for the nonmonotonic inductive logic programming setting. In particular, we show that first-order range-restricted clausal theories that consist of clauses with up to k literals of size at most j each are polynomial-sample polynomial-time PAC-learnable with one-sided error from positive examples only. In our framework, concepts are clausal theories and examples are finite interpretations. We discuss the problems encountered when learning theories which only have infinite nontrivial models and propose a way to avoid these problems using a representation change called flattening. Finally, we compare our results to PAC-learnability results for the normal inductive logic programming setting.

AIJ Journal 1994 Journal Article

Iterative versionspaces

• Gunther Sablon
• Luc De Raedt
• Maurice Bruynooghe

An incremental depth-first algorithm for computing the S- and ς-set of Mitchell's Candidate Elimination and Mellish's Description Identification algorithm is presented. As in Mellish's approach, lowerbounds (examples) as well as upperbounds can be handled. Instead of storing the complete S- and ς-sets, only one element s ϵ S and g ϵ ς is stored, together with backtrack information. The worst-case space complexity of our algorithm is linear in the number of lower- and upperbounds. For the Candidate Elimination algorithm this can be exponential. We introduce a test for membership of S and ς with a number of coverage tests linear in the number of examples. Consequently the worst-case time complexity to compute S and ς for each example is only a linear factor worse than the Candidate Elimination algorithm's.

KER Journal 1992 Journal Article

A unifying framework for concept-learning algorithms

• Luc De Raedt
• Maurice Bruynooghe

Abstract A unifying framework for concept-learning, derived from Mitchell's Generalization as Search-paradigm, is presented. Central to the framework is the generic algorithm Gencol. Gencol forms a synthesis of existing concept-learning algorithms as it identifies the key issues in concept-learning: the representation of concepts and examples, the search strategy and heuristics, and the operators that transform one concept-description into another one when searching the concept description space. Gencol is relevant for practical purposes as it offers a solid basis for the design and implementation of concept-learning algorithms. The presented framework is quite general as seemingly disparate algorithms such as TDIDT, AQ, MIS and version spaces fit into Gencol.

AIJ Journal 1992 Journal Article

Belief updating from integrity constraints and queries

• Luc De Raedt
• Maurice Bruynooghe

It is argued that the problems of intensional knowledge base updating and incremental concept-learning—when formulated in a logical framework—can be understood as instances of the more general problem of belief updating. This insight allows interesting cross-fertilization between both areas. To support this claim, we sketch a simple extension of Shapiro's Model Inference System that solves the belief updating problem within a restricted subset of first order logic. This extension uses integrity constraints and allows for the assertion of non-unit clauses. The former generalizes the use of examples in concept-learning whereas the latter generalizes the set of revisions considered in knowledge base updating.

ECAI Conference 1992 Conference Paper

Inverse Resolution in an Integrated Inductive-Deductive Learning System

• Hilde Adé
• Luc De Raedt
• Maurice Bruynooghe

ECAI Conference 1990 Conference Paper

On Negation and Three-Valued Logic in Interactive Concept-Learning

• Luc De Raedt
• Maurice Bruynooghe

IJCAI Conference 1989 Conference Paper

Explanation Based Program Transformation

• Maurice Bruynooghe
• Luc De Raedt
• Danny De Schreye

Fold-unfold is a well known program transformation technique. Its major drawback is that folding requires an Eureka step to invent new procedures. In the context of logic programming, we present a technique where the folding is driven by an example. The transformation is aimed at programs suffering from inefficiencies due to the repetition of identical subcomputations. The execution of an example is analysed to locate repeated subcomputations. Then the structure of the example is used to control a fold-unfoldtransformation of the program. The transformation can be automated. The method can be regarded as an extension of explanation based learning.

IJCAI Conference 1989 Conference Paper

Towards Friendly Concept-Learners

• Luc De Raedt
• Maurice Bruynooghe

We give a general overview of CUNT, a userfriendly interactive concept-learner, which can be used as a module for Learning Apprentice Systems. CLINT combines several interesting features: it uses domain-knowledge, generates examples, copes with indirect relevance, shifts its bias, recovers from errors and identifies concepts in the limit.