Author name cluster

João Leite

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

KR Conference 2024 Conference Paper

On Abstracting over the Irrelevant in Answer Set Programming

Zeynep G. Saribatur
Matthias Knorr
Ricardo Gonçalves
João Leite

Generalization is an important ability that allows humans to tackle complex problems by identifying common problem structures and omitting irrelevant details. Whereas such ability comes naturally to humans, it has proved challenging to establish within AI systems. Although different research communities have tackled this challenge, their focus has usually been set on developing efficient algorithms for concrete problems, and a general theoretical understanding of the generalization ability is still lacking. In the context of Answer Set Programming (ASP), a well-established knowledge representation and reasoning paradigm for solving highly combinatorial search problems, research on generalization has primarily focused on forgetting and projection, two related operations that aim at the omission of irrelevant details, while abstraction, an operation that aims at providing a higher-level view on the common solution and problem structures, has largely been overlooked. In this paper, we develop the theoretical foundation for generalized reasoning through abstraction in ASP, focusing on the notion of abstraction through vocabulary clustering. We formally characterize when abstraction is possible, semantically define the desired result, investigate syntactic operators to obtain such abstractions, and study the computational complexity of this problem.

PDF Details DOI

KR Conference 2023 Conference Paper

Revising Boolean Logical Models of Biological Regulatory Networks

Frederico Aleixo
Matthias Knorr
João Leite

Boolean regulatory networks are used to represent complex biological processes, modelling the interactions of biological compounds, such as proteins or genes, with each other and with other substances in a cell. Creating and maintaining computational models of these networks is crucial for comprehending corresponding cellular processes, as they allow reproducing known behaviours and testing new hypotheses and predictions in silico. In this context, model revision focuses on validating and (if necessary) repairing existing models based on new experimental data. However, model revision is commonly performed manually, which is inefficient and prone to error, and the few existing automated solutions either only apply to simpler networks or are limited in their revision process, since they may not be able to produce a solution within a reasonable time frame or miss the optimal solution. In this paper, we develop a solution for revising logical models of Boolean regulatory networks, able to find repairs that are consistent with provided, possibly incomplete experimental data, and minimal w. r. t. the differences to the original network. We show that our solution can be used to revise different real-world Boolean logical models very efficiently, surpassing a previous solution in terms of solved instances and with a considerable margin w. r. t. processing time.

PDF Details DOI

KR Conference 2022 Conference Paper

Looking Inside the Black-Box: Logic-based Explanations for Neural Networks

João Ferreira
Manuel de Sousa Ribeiro
Ricardo Gonçalves
João Leite

Deep neural network-based methods have recently enjoyed great popularity due to their effectiveness in solving difficult tasks. Requiring minimal human effort, they have turned into an almost ubiquitous solution in multiple domains. However, due to the size and complexity of typical neural network models' architectures, as well as the sub-symbolical nature of the representations generated by their neuronal activations, neural networks are essentially opaque, making it nearly impossible to explain to humans the reasoning behind their decisions. We address this issue by developing a procedure to induce human-understandable logic-based theories that attempt to represent the classification process of a given neural network model, based on the idea of establishing mappings from the values of the activations produced by the neurons of that model to human-defined concepts to be used in the induced logic-based theory. Exploring the setting of a synthetic image classification task, we provide empirical results to assess the quality of the developed theories for different neural network models, compare them to existing theories on that task, and give evidence that the theories developed through our method are faithful to the representations learned by the neural networks that they are built to describe.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Aligning Artificial Neural Networks and Ontologies towards Explainable AI

Manuel de Sousa Ribeiro
João Leite

Neural networks have been the key to solve a variety of different problems. However, neural network models are still regarded as black boxes, since they do not provide any humaninterpretable evidence as to why they output a certain result. We address this issue by leveraging on ontologies and building small classifiers that map a neural network model’s internal state to concepts from an ontology, enabling the generation of symbolic justifications for the output of neural network models. Using an image classification problem as testing ground, we discuss how to map the internal state of a neural network to the concepts of an ontology, examine whether the results obtained by the established mappings match our understanding of the mapped concepts, and analyze the justifications obtained through this method.

PDF Details

AIJ Journal 2020 Journal Article

On the limits of forgetting in Answer Set Programming

Ricardo Gonçalves
Matthias Knorr
João Leite
Stefan Woltran

Selectively forgetting information while preserving what matters the most is becoming an increasingly important issue in many areas, including in knowledge representation and reasoning. Depending on the application at hand, forgetting operators are defined to obey different sets of desirable properties. It turns out that, of the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence, which imposes certain conditions on the correspondence between the answer sets of the program pre- and post-forgetting, and a certain independence from non-forgotten atoms, seems to best capture its essence, and be desirable in general. However, it has remained an open problem whether it is always possible to forget a set of atoms from a program while obeying strong persistence. In this paper, we investigate the limits of forgetting in Answer Set Programming. After showing that it is not always possible to forget a set of atoms from a program while obeying this property, we move forward and precisely characterize what can and cannot be forgotten from a program, by presenting a necessary and sufficient criterion. This characterization allows us to draw some important conclusions regarding the existence of forgetting operators for specific classes of logic programs, to characterize the class of forgetting operators that achieve the correct result whenever forgetting is possible, and investigate the related question of determining what we can forget from some specific logic program. Subsequently, we address the issue of what to do when we must forget a set of atoms, but cannot without violating this property. To this end, we investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different natural possible relaxations of the characterization of strong persistence. Additionally, before concluding, we address computational complexity issues – namely of checking whether the novel criterion holds and whether a certain program is a result according to the different classes of forgetting operators we introduce – and discuss the related literature.

Details DOI

AAAI Conference 2019 Conference Paper

Forgetting in Modular Answer Set Programming

Ricardo Gonçalves
Tomi Janhunen
Matthias Knorr
João Leite
Stefan Woltran

Modular programming facilitates the creation and reuse of large software, and has recently gathered considerable interest in the context of Answer Set Programming (ASP). In this setting, forgetting, or the elimination of middle variables no longer deemed relevant, is of importance as it allows one to, e. g. , simplify a program, make it more declarative, or even hide some of its parts without affecting the consequences for those parts that are relevant. While forgetting in the context of ASP has been extensively studied, its known limitations make it unsuitable to be used in Modular ASP. In this paper, we present a novel class of forgetting operators and show that such operators can always be successfully applied in Modular ASP to forget all kinds of atoms – input, output and hidden – overcoming the impossibility results that exist for general ASP. Additionally, we investigate conditions under which this class of operators preserves the module theorem in Modular ASP, thus ensuring that answer sets of modules can still be composed, and how the module theorem can always be preserved if we further allow the reconfiguration of modules.

PDF Details

AIJ Journal 2018 Journal Article

Reactive multi-context systems: Heterogeneous reasoning in dynamic environments

Gerhard Brewka
Stefan Ellmauthaler
Ricardo Gonçalves
Matthias Knorr
João Leite
Jörg Pührer

Managed multi-context systems (mMCSs) allow for the integration of heterogeneous knowledge sources in a modular and very general way. They were, however, mainly designed for static scenarios and are therefore not well-suited for dynamic environments in which continuous reasoning over such heterogeneous knowledge with constantly arriving streams of data is necessary. In this paper, we introduce reactive multi-context systems (rMCSs), a framework for reactive reasoning in the presence of heterogeneous knowledge sources and data streams. We show that rMCSs are indeed well-suited for this purpose by illustrating how several typical problems arising in the context of stream reasoning can be handled using them, by showing how inconsistencies possibly occurring in the integration of multiple knowledge sources can be handled, and by arguing that the potential non-determinism of rMCSs can be avoided if needed using an alternative, more skeptical well-founded semantics instead with beneficial computational properties. We also investigate the computational complexity of various reasoning problems related to rMCSs. Finally, we discuss related work, and show that rMCSs do not only generalize mMCSs to dynamic settings, but also capture/extend relevant approaches w. r. t. dynamics in knowledge representation and stream reasoning.

Details DOI

AIJ Journal 2015 Journal Article

On updates of hybrid knowledge bases composed of ontologies and rules

Martin Slota
João Leite
Theresa Swift

Throughout the last decade, two distinct knowledge representation paradigms have been standardised to capture rich metadata on the Web: ontology languages based on Classical Logic and reasoning rules based on Logic Programming. Both offer important features for knowledge representation and the interest in their integration has recently resulted in frameworks for hybrid knowledge bases that consist of an ontology and a rule component. Instead of the usual static view of hybrid knowledge, in this paper we address its dynamics and in particular focus on updates. We develop two hybrid update semantics that fit the needs of particular use cases of hybrid knowledge and provide the expected results when used in specific application domains. The first semantics uses a given ontology update operator to update the ontology component of a hybrid knowledge base in the presence of static rules. Inspired by a realistic application, and based on a generalised notion of splitting, known from Logic Programming, the second semantics offers a way to modularly combine an ontology update operator with a rule update semantics. It can be used for performing updates of hybrid knowledge bases consisting of ontology and rule layers that share information through a rule-based interface. Both of these developments constitute solutions to the problem of hybrid updates for restricted classes of hybrid knowledge bases. We examine their fundamental formal properties and show that despite the different ideas behind each of them, they are fully compatible with one another, i. e. when both are applicable, they lead to the same result.

Details DOI

IJCAI Conference 2013 Conference Paper

On Condensing a Sequence of Updates in Answer-Set Programming

Martin Slota
João Leite

Update semantics for Answer-Set Programming assign models to sequences of answer-set programs which result from the iterative process of updating programs by programs. Each program in the sequence represents an update of the preceding ones. One of the enduring problems in this context is state condensing, or the problem of determining a single logic program that faithfully represents the sequence of programs. Such logic program should 1) be written in the same alphabet, 2) have the same stable models, and 3) be equivalent to the sequence of programs when subject to further updates. It has been known for more than a decade that update semantics easily lead to non-minimal stable models, so an update sequence cannot be represented by a single non-disjunctive program. On the other hand, more expressive classes of programs were never considered, mainly because it was not clear how they could be updated further. In this paper we solve the state condensing problem for two foundational rule update semantics, using nested logic programs. Furthermore, we also show that disjunctive programs with default negation in the head can be used for the same purpose.

PDF Details DOI

AAMAS Conference 2009 Conference Paper

Resource Allocation with Answer-Set Programming

João Leite
José Alferes
Belopeta Mito

Multi-agent resource allocation is a growing area of research at the frontier between Economics and Computer Science. Despite the extensive theoretical work and raising number of practical applications, many fundamental problems in multi-agent resource allocation still require adequate attention to its computational aspects. This paper addresses computational aspects of multi-agent resource allocation through the use of a fully declarative and highly expressive logic programming paradigm – Answer Set Programming – to provide uniform, general and ﬂexible solutions to many multi-agent resource allocation problems in a compact and declarative manner.

PDF