Jorge Lobo

IJCAI Conference 2023 Conference Paper

Neuro-Symbolic Learning of Answer Set Programs from Raw Data

• Daniel Cunnington
• Mark Law
• Jorge Lobo
• Alessandra Russo

One of the ultimate goals of Artificial Intelligence is to assist humans in complex decision making. A promising direction for achieving this goal is Neuro-Symbolic AI, which aims to combine the interpretability of symbolic techniques with the ability of deep learning to learn from raw data. However, most current approaches require manually engineered symbolic knowledge, and where end-to-end training is considered, such approaches are either restricted to learning definite programs, or are restricted to training binary neural networks. In this paper, we introduce Neuro-Symbolic Inductive Learner (NSIL), an approach that trains a general neural network to extract latent concepts from raw data, whilst learning symbolic knowledge that maps latent concepts to target labels. The novelty of our approach is a method for biasing the learning of symbolic knowledge, based on the in-training performance of both neural and symbolic components. We evaluate NSIL on three problem domains of different complexity, including an NP-complete problem. Our results demonstrate that NSIL learns expressive knowledge, solves computationally complex problems, and achieves state-of-the-art performance in terms of accuracy and data efficiency. Code and technical appendix: https: //github. com/DanCunnington/NSIL

KR Conference 2022 Conference Paper

Embed2Sym - Scalable Neuro-Symbolic Reasoning via Clustered Embeddings

• Yaniv Aspis
• Krysia Broda
• Jorge Lobo
• Alessandra Russo

Neuro-symbolic reasoning approaches proposed in recent years combine a neural perception component with a symbolic reasoning component to solve a downstream task. By doing so, these approaches can provide neural networks with symbolic reasoning capabilities, improve their interpretability and enable generalization beyond the training task. However, this often comes at the cost of poor training time, with potential scalability issues. In this paper, we propose a scalable neuro-symbolic approach, called Embed2Sym. We complement a two-stage (perception and reasoning) neural network architecture designed to solve a downstream task end-to-end with a symbolic optimisation method for extracting learned latent concepts. Specifically, the trained perception network generates clusters in embedding space that are identified and labelled using symbolic knowledge and a symbolic solver. With the latent concepts identified, a neuro-symbolic model is constructed by combining the perception network with the symbolic knowledge of the downstream task, resulting in a model that is interpretable and transferable. Our evaluation shows that Embed2Sym outperforms state-of-the-art neuro-symbolic systems on benchmark tasks in terms of training time by several orders of magnitude while providing similar if not better accuracy.

AAAI Conference 2020 Conference Paper

FastLAS: Scalable Inductive Logic Programming Incorporating Domain-Specific Optimisation Criteria

• Mark Law
• Alessandra Russo
• Elisa Bertino
• Krysia Broda
• Jorge Lobo

Inductive Logic Programming (ILP) systems aim to find a set of logical rules, called a hypothesis, that explain a set of examples. In cases where many such hypotheses exist, ILP systems often bias towards shorter solutions, leading to highly general rules being learned. In some application domains like security and access control policies, this bias may not be desirable, as when data is sparse more specific rules that guarantee tighter security should be preferred. This paper presents a new general notion of a scoring function over hypotheses that allows a user to express domain-specific optimisation criteria. This is incorporated into a new ILP system, called FastLAS, that takes as input a learning task and a customised scoring function, and computes an optimal solution with respect to the given scoring function. We evaluate the accuracy of Fast- LAS over real-world datasets for access control policies and show that varying the scoring function allows a user to target domain-specific performance metrics. We also compare FastLAS to state-of-the-art ILP systems, using the standard ILP bias for shorter solutions, and demonstrate that FastLAS is significantly faster and more scalable.

KR Conference 2020 Conference Paper

Stable and Supported Semantics in Continuous Vector Spaces

• Yaniv Aspis
• Krysia Broda
• Alessandra Russo
• Jorge Lobo

We introduce a novel approach for the computation of stable and supported models of normal logic programs in continuous vector spaces by a gradient-based search method. Specifically, the application of the immediate consequence operator of a program reduct can be computed in a vector space. To do this, Herbrand interpretations of a propositional program are embedded as 0-1 vectors in $\mathbb{R}^N$ and program reducts are represented as matrices in $\mathbb{R}^{N \times N}$. Using these representations we prove that the underlying semantics of a normal logic program is captured through matrix multiplication and a differentiable operation. As supported and stable models of a normal logic program can now be seen as fixed points in a continuous space, non-monotonic deduction can be performed using an optimisation process such as Newton's method. We report the results of several experiments using synthetically generated programs that demonstrate the feasibility of the approach and highlight how different parameter values can affect the behaviour of the system.

AAAI Conference 2019 Conference Paper

Representing and Learning Grammars in Answer Set Programming

• Mark Law
• Alessandra Russo
• Elisa Bertino
• Krysia Broda
• Jorge Lobo

In this paper we introduce an extension of context-free grammars called answer set grammars (ASGs). These grammars allow annotations on production rules, written in the language of Answer Set Programming (ASP), which can express context-sensitive constraints. We investigate the complexity of various classes of ASG with respect to two decision problems: deciding whether a given string belongs to the language of an ASG and deciding whether the language of an ASG is non-empty. Specifically, we show that the complexity of these decision problems can be lowered by restricting the subset of the ASP language used in the annotations. To aid the applicability of these grammars to computational problems that require context-sensitive parsers for partially known languages, we propose a learning task for inducing the annotations of an ASG. We characterise the complexity of this task and present an algorithm for solving it. An evaluation of a (prototype) implementation is also discussed.

AAAI Conference 1999 Conference Paper

A Policy Description Language

• Jorge Lobo
• Randeep Bhatia
• Shamim Naqvi
• Bell Labs

Apolicy describesprinciples or strategies for a plan of action designedto achieve a particular set of goals. We define a policy as a functionthat maps a series of events into a set of actions. In this paperweintroduceP~D£, a simplebut expressivelanguageto specify policies. The design of the languagehas beenstrongly influenced by the action languages of Geffner and Bonet (Geffner Boner1998)and Gelfondand Lifschitz (Gelfond&Lifschitz 1993) and the compositetemporal event language of Motakis and Zaniolo (Motakis &Zaniolo 1997). The semantics is founded on recent results on formal descriptions of action theories based on automata and their application to active databases. Wesummarize somecomplexity results on the hardness of evaluating polices and briefly describe the implementationof a policy server being used to provide centralized administration of a soft switch in a communication network.

AIJ Journal 1997 Journal Article

Abductive consequence relations

• Jorge Lobo
• Carlos Uzcátegui

In this paper we present a systematic study of abductive consequence relations. We show that a monotone abductive consequence relation satisfies the properties of a cumulative monotonic system as defined by Kraus, Lehmann and Magidor when the disjunction of all abductive explanations is the explanation used to justify the observations. We also show that, in general, for this class of abductive consequence relations the Or rule does not hold. We present an example that shows that when there are preferences between different abductive explanations monotonicity does not hold. We show that nonmonotonic abductive systems preserve a partial version of rational monotonicity and in fact are very similar to rational relations. We also present semantic characterizations of both monotonic and nonmonotonic abductive systems in terms of cumulative models as defined by Kraus, Lehmann and Magidor.

AAAI Conference 1997 Conference Paper

Adding Knowledge to the Action Description Language A

• Jorge Lobo

We introduce dk an extension of the action description language A (Gelfond & Lifschitz 1993) to handle actions which affect knowledge. We use sensing actions to increase an agent’s knowledge of the world and non-determinis tic actions to remove knowledge. We include complex plans involving conditionals and loops in our query language for hypothetical reasoning. Finally, we present a translation of descriptions in dk to epistemic logic programs.

TCS Journal 1991 Journal Article

Semantics of Horn and disjunctive logic programs

• Jorge Lobo
• Arcot Rajasekar
• Jack Minker