Logic-based eXplainable Artificial Intelligence (XAI) represents a rigorous alternative to non-symbolic XAI. However, one critical limitation of logic-based explanations is the complexity of reasoning about machine learning (ML) models. Sample-based explanations represent a rigorous, model-agnostic, but also scalable alternative to model-based explanations. Whereas finding one sample-based explanation can be done in polynomial time, the computation of a smallest explanation is computationally hard. This paper develops CovAXp, a novel heuristic method for the computation of small sample-based explanations. The proposal employs a feature-coverage heuristic within a pruned depth-first search that prioritizes features maximizing rule coverage within the sample space. Experimental evaluation shows that CovAXp achieves near-minimal explanation cardinality (mean length 2.48 versus the optimal 2.36), sub-second execution times, and perfect true negative rate, while offering a tunable trade-off between coverage and rule compactness.

In the logic of theory change, the AGM model has acquired the status of a standard model. However, the AGM model does not seem adequate for some contexts and application domains. This inspired many researchers to propose extensions and generalizations to AGM. Among these extensions, one of the most important are belief bases. Belief bases have more expressivity than belief sets, as explicit and implicit beliefs have different statuses. In this paper, we present reformulation, a belief change operation that allows us to reformulate a belief base making some particular sentences explicit without modifying the consequences of the belief base. We provide a constructive method and its axiomatic characterization.

Explainable artificial intelligence (XAI) is at the core of trustworthy AI. The best-known methods of XAI are sub-symbolic. Unfortunately, these methods do not give guarantees of rigor. Logic-based XAI addresses the lack of rigor of sub-symbolic methods, but in turn it exhibits some drawbacks. These include scalability, explanation size, but also the need to access the details of the machine learning model. Furthermore, access to the details of an ML model may reveal sensitive information. This paper builds on recent work on symbolic model-agnostic XAI, which is based on explaining samples of behavior of a blackbox ML model, and proposes efficient algorithms for the computation of explanations. The experiments confirm the scalability of the novel algorithms.

The dialogue game-based approach to argumentation semantics proposes to determine the acceptance status of arguments through two-party zero-sum dialogue games. Furthermore, by selecting different sets of rules to govern the moves of arguments in the game, it allows for the characterization of distinct argumentation semantics. This approach has proven significant for theoretical and practical reasons. Accordingly, the ability to identify the most suitable semantics for a given domain is a key element in promoting the adoption of dialogue game-based semantics in real-world systems. This paper introduces a set of principles for systematically analyzing dialogue game-based semantics. We aim to contribute to existing frameworks by enabling a deeper understanding of the theoretical foundations of such argumentation semantics. In doing so, our framework may also guide the development of new dialogue game-based semantics.

Attribution scores reflect how important the feature values in an input entity are for the output of a machine learning model. One of the most popular attribution scores is the SHAP score, which is an instantiation of the general Shapley value used in coalition game theory. The definition of this score relies on a probability distribution on the entity population. Since the exact distribution is generally unknown, it needs to be assigned subjectively or be estimated from data, which may lead to misleading feature scores. In this paper, we propose a principled framework for reasoning on SHAP scores under unknown entity population distributions. In our framework, we consider an uncertainty region that contains the potential distributions, and the SHAP score of a feature becomes a function defined over this region. We study the basic problems of finding maxima and minima of this function, which allows us to determine tight ranges for the SHAP scores of all features. In particular, we pinpoint the complexity of these problems, and other related ones, showing them to be intractable. Finally, we present experiments on a real-world dataset, showing that our framework may contribute to a more robust feature scoring.

As technology widens our possibilities for communication and knowledge discovery, it can also leave us vulnerable to misinformation and toxic, abusive, manipulative content, which can cause substantial harm both individually and collectively. Combating the malicious use of social media implies solving very complex and subjective tasks that require a synergy between automated tools and humans. Existing ML models, trained on vast datasets, excel in many tasks like summarization, translation, and human-like content generation. However, we argue that in order for those tools to be effective, they need to be able to form the types of representations and semantic inferences that humans use and create, have the ability to combine automatically acquired data and insights with the domain-specific expertise of the users, and involve high-level reasoning, all three features in which knowledge-based and symbolic approaches to artificial intelligence seem to be well-fitted for.

As AI models become ever more complex and intertwined in humans’ daily lives, greater levels of interactivity of explainable AI (XAI) methods are needed. In this paper, we propose the use of belief change theory as a formal foundation for operators that model the incorporation of new information, i.e. user feedback in interactive XAI, to logical representations of data-driven classifiers. We argue that this type of formalisation provides a framework and a methodology to develop interactive explanations in a principled manner, providing warranted behaviour and favouring transparency and accountability of such interactions. Concretely, we first define a novel, logic-based formalism to represent explanatory information shared between humans and machines. We then consider real world scenarios for interactive XAI, with different prioritisations of new and existing knowledge, where our formalism may be instantiated. Finally, we analyse a core set of belief change postulates, discussing their suitability for our real world settings and pointing to particular challenges that may require the relaxation or reinterpretation of some of the theoretical assumptions underlying existing operators.

In this article, we provide a new kind of belief revision operator that we call Moderated Revision. At first glance, it is a non-prioritized operator that combines a basic classical AGM operator with a credibility-limited one. The underlying idea is this: when new observation μ is received, it is accepted but with doubts, i.e., uncertainty. We use a revision operator to model the accepted part and a credibility-limited one to represent uncertainty, whenever necessary. In the presence of uncertainty, a selection of the old knowledge balances the result of the revision through a disjunction, allowing the agent to accept part of the new observation and remain unsettled about the rest.

In the deeply interconnected world we live in, pieces of information link domains all around us. As graph databases embrace effectively relationships among data and allow processing and querying these connections efficiently, they are rapidly becoming a popular platform for storage that supports a wide range of domains and applications. As in the relational case, it is expected that data preserves a set of integrity constraints that define the semantic structure of the world it represents. When a database does not satisfy its integrity constraints, a possible approach is to search for a ‘similar’ database that does satisfy the constraints, also known as a repair. In this work, we study the problem of computing subset and superset repairs for graph databases with data values using a notion of consistency based on having a set of Reg-GXPath expressions as integrity constraints. We show that for positive fragments of Reg-GXPath these problems admit a polynomial-time algorithm, while the full expressive power of the language renders them intractable.

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

Generating counterfactuals to discover hypothetical predictive scenarios is the de facto standard for explaining machine learning models and their predictions. However, building a counterfactual explainer that is time-efficient, scalable, and model-agnostic, in addition to being compatible with continuous and categorical attributes, remains an open challenge. To complicate matters even more, ensuring that the contrastive instances are optimised for feature sparsity, remain close to the explained instance, and are not drawn from outside of the data manifold, is far from trivial. To address this gap we propose BayCon: a novel counterfactual generator based on probabilistic feature sampling and Bayesian optimisation. Such an approach can combine multiple objectives by employing a surrogate model to guide the counterfactual search. We demonstrate the advantages of our method through a collection of experiments based on six real-life datasets representing three regression tasks and three classification tasks.

People are becoming increasingly more connected to each other as social networks continue to grow both in number and variety, and this is true for autonomous software agents as well. Taking them as a collection, such social platforms can be seen as one complex network with many different types of relations, different degrees of strength for each relation, and a wide range of information on each node. In this context, social media posts made by users are reflections of the content of their own individual (or local) knowledge bases; modeling how knowledge flows over the network—or how this can possibly occur—is therefore of great interest from a knowledge representation and reasoning perspective. In this article, we provide a formal introduction to the network knowledge base model, and then focus on the problem of how a single agent’s knowledge base changes when exposed to a stream of news items coming from other members of the network. We do so by taking the classical belief revision approach of first proposing desirable properties for how such a local operation should be carried out (theoretical characterization), arriving at three different families of local operators, exploring concrete algorithms (algorithmic characterization) for two of the families, and proving properties about the relationship between the two characterizations (representation theorem). One of the most important differences between our approach and the classical models of belief revision is that in our case the input is more complex, containing additional information about each piece of information.

In this note, we introduce the local version of the operator for belief promotion proposed by Schwind et al. We propose a set of postulates and provide a representation theorem that characterizes the proposal. This family of operators is related to belief promotion in the same way that updating is related to revision, and we provide several results that allow us to show this relationship formally. Furthermore, we also show the relationship of the proposed operator with features of credibility-limited revision theory.

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

Knowledge can be seen as the collection of skills and information an individual (or group) has acquired through experience, while intelligence as the ability to apply such knowledge. In many areas of Artificial Intelligence, we have been focusing for the last 40 years on the formalization and development of automated ways of finding and collecting data, as well as on the construction of models to represent that data adequately in a way that an automated system can make sense of it. However, in order to achieve real artificial intelligence we need to go beyond data and knowledge representation, and deeper into how such a system could, and would, use available knowledge in order to empower and enhance the capabilities of humans in making decisions in real-world applications. From my point of view, an AI should be able to combine automatically acquired data and knowledge together with specific domain expertise from the users that the tool is expected to help.

We study the complexity of exchanging probabilistic data between ontology-based probabilistic databases. We consider the Datalog+/- family of languages as ontology and ontology mapping languages, and we assume different compact encodings of the probabilities of the probabilistic source databases via Boolean events. We provide an extensive complexity analysis of the problem of deciding the existence of a probabilistic (universal) solution for a given probabilistic source database relative to a (probabilistic) data exchange problem for the different languages considered.

Knowledge bases in the form of ontologies are receiving increasing attention as they allow to clearly represent both the available knowledge, which includes the knowledge in itself and the constraints imposed to it by the domain or the users. In particular, Datalog± ontologies are attractive because of their property of decidability and the possibility of dealing with the massive amounts of data in real world environments; however, as it is the case with many other ontological languages, their application in collaborative environments often lead to inconsistency related issues. In this paper we introduce the notion of incoherence regarding Datalog± ontologies, in terms of satisfiability of sets of constraints, and show how under specific conditions incoherence leads to inconsistent Datalog± ontologies. The main contribution of this work is a novel approach to restore both consistency and coherence in Datalog± ontologies. The proposed approach is based on kernel contraction and restoration is performed by the application of incision functions that select formulas to delete. Nevertheless, instead of working over minimal incoherent/inconsistent sets encountered in the ontologies, our operators produce incisions over non-minimal structures called clusters. We present a construction for consolidation operators, along with the properties expected to be satisfied by them. Finally, we establish the relation between the construction and the properties by means of a representation theorem. Although this proposal is presented for Datalog± ontologies consolidation, these operators can be applied to other types of ontological languages, such as Description Logics, making them apt to be used in collaborative environments like the Semantic Web.

Querying inconsistent ontologies is an intriguing new problem that gave rise to a flourishing research activity in the description logic (DL) community. The computational complexity of consistent query answering under the main DLs is rather well understood; however, little is known about existential rules. The goal of the current work is to perform an in-depth analysis of the complexity of consistent query answering under the main decidable classes of existential rules enriched with negative constraints. Our investigation focuses on one of the most prominent inconsistency-tolerant semantics, namely, the AR semantics. We establish a generic complexity result, which demonstrates the tight connection between classical and consistent query answering. This result allows us to obtain in a uniform way a relatively complete picture of the complexity of our problem.

Over the years, inconsistency management has caught the attention of researchers of different areas. Inconsistency is a problem that arises in many different scenarios, for instance, ontology development or knowledge integration. In such settings, it is important to have adequate automatic tools for handling conflicts that may appear in a knowledge base. We introduce an approach to consolidation of belief bases based on a refinement of kernel contraction that accounts for the relation among kernels using clusters instead. We define cluster contraction-based consolidation operators contraction by falsum on a belief base using cluster incision functions, a refinement of kernel incision functions.

Reasoning about an entity's preferences (be it a user of an application, an individual targeted for marketing, or a group of people whose choices are of interest) has a long history in different areas of study. In this paper, we adopt the point of view that grows out of the intersection of databases and knowledge representation, where preferences are usually represented as strict partial orders over the set of tuples in a database or the consequences of a knowledge base. We introduce probabilistic preference logic networks (PPLNs), which flexibly combine such preferences with probabilistic uncertainty. Their applications are clear in domains such as the Social Semantic Web, where users often express preferences in an incomplete manner and through different means, many times in contradiction with each other. We show that the basic problems associated with reasoning with PPLNs (computing the probability of a world or a given query) are #P-hard, and then explore ways to make these computations tractable by: (i) leveraging results from order theory to obtain a polynomial-time randomized approximation scheme (FPRAS) under fixed-parameter assumptions; and (ii) studying a fragment of the language of PPLNs for which exact computations can be performed in fixed-parameter polynomial time.

The Web has recently been evolving into a system that is in many ways centered on social interactions and is now more and more becoming what is called the Social Semantic Web. One of the many implications of such an evolution is that the ranking of search results no longer depends solely on the structure of the interconnections among Web pages—instead, the social components must also come into play. In this article, we argue that such rankings can be based on ontological background knowledge and on user preferences. Another aspect that has become increasingly important in recent times is that of uncertainty management, since uncertainty can arise due to many uncontrollable factors. To combine these two aspects, we propose extensions of the Datalog+/-- family of ontology languages that both allow for the management of partially ordered preferences of groups of users as well as uncertainty, which is represented via a probabilistic model. We focus on answering k -rank queries in this context, presenting different strategies to compute group preferences as an aggregation of the preferences of a collection of single users. We also study merging operators that are useful for combining the preferences of the users with those induced by the values obtained from the probabilistic model. We then provide algorithms to answer k -rank queries for DAQs (disjunctions of atomic queries) under these group preferences and uncertainty that generalizes top- k queries based on the iterative computation of classical skyline answers. We show that such DAQ answering in Datalog+/-- can be done in polynomial time in the data complexity, under certain reasonable conditions, as long as query answering can also be done in polynomial time (in the data complexity) in the underlying classical ontology. Finally, we present a prototype implementation of the query answering system, as well as experimental results (on the running time of our algorithms and the quality of their results) obtained from real-world ontological data and preference models, derived from information gathered from real users, showing in particular that our approach is feasible in practice.

In the recent years, the Web has been changing more and more towards the so-called Social Semantic Web. Rather than being based on the link structure between Web pages, the ranking of search results in the Social Semantic Web needs to be based on something new - we believe that it can be based on user preferences and underlying ontological knowledge. Modeling uncertainty is also playing an increasingly important role in these domains, since uncertainty can arise due to many uncontrollable factors. In this paper, we propose an extension of the Data log+/- ontology language with a model for representing preferences of groups of users and a model for representing the (probabilistic) uncertainty in the domain. Assuming that more probable answers are more preferable, this raises the question of how to rank query results, since the preferences of single users may be in conflict both with the probability-based preferences as well as with each other. To this end, we propose preference merging and aggregation operators, respectively, and study their semantic and computational properties. Based on these operators, we provide algorithms for answering k-rank queries for DAQs (disjunctions of atomic queries), which generalize top-k queries based on the iterative computation of classical skyline answers, and show that, under certain reasonable conditions, they run in polynomial time in the data complexity.

Most real-world databases have at least some missing data. Today, users of such databases are “on their own” in terms of how they manage this incompleteness. In this paper, we propose the general concept of partial information policy (PIP) operator to handle incompleteness in relational databases. PIP operators build upon preference frameworks for incomplete information, but accommodate different types of incomplete data (e.g., a value exists but is not known; a value does not exist; a value may or may not exist). Different users in the real world have different ways in which they want to handle incompleteness-PIP operators allow them to specify a policy that matches their attitude to risk and their knowledge of the application and how the data was collected. We propose index structures for efficiently evaluating PIP operators and experimentally assess their effectiveness on a real-world airline data set. We also study how relational algebra operators and PIP operators interact with one another.

In this work we introduce an extension of an structured argumentation system in which presumptions are fully integrated in the reasoning mechanism. A presumption is defined as a piece of information that is tentatively taken to be true, usually in the absence of acceptable reasons to the contrary. In Presumptive Defeasible Logic Programming (PreDeLP), arguments can be built from both facts and presumptions. We analyze several criteria to compare arguments in PreDeLP, and highlight one possibility that captures the semantic difference between presumptions and facts or defeasible rules. On top of PreDeLP we develop a defeasible approach to argumentation-based diagnostic reasoning. The use of presumptions permits to extend the reasoning beyond factual information, creating in this way a universe of possible scenarios that support or interfere with a claim. We characterize the set of possible scenarios for and against a claim and identify those that best explain the warrant status of the query.

Inconsistency and partial information is the norm in knowledge bases used in many real world applications that support, among other things, human decision making processes. In this work we argue that the management of this kind of data needs to be context-sensitive, creating a synergy with the user to build useful, flexible data management systems.

Recent interest in managing uncertainty in data integration has led to the introduction of probabilistic schema mappings and the use of probabilistic methods to answer queries across multiple databases using two semantics: by-table and by-tuple. In this paper, we develop three possible semantics for aggregate queries: the range, distribution, and expected value semantics, and show that these three semantics combine with the by-table and by-tuple semantics in six ways. We present algorithms to process COUNT, AVG, SUM, MIN, and MAX queries under all six semantics and develop results on the complexity of processing such queries under all six semantics. We show that computing COUNT is in PTIME for all six semantics and computing SUM is in PTIME for all but the by-tuple/distribution semantics. Finally, we show that AVG, MIN, and MAX are PTIME computable for all by-table semantics and for the by-tuple/range semantics.We developed a prototype implementation and experimented with both real-world traces and simulated data. We show that, as expected, naive processing of aggregates does not scale beyond small databases with a small number of mappings. The results also show that the polynomial time algorithms are scalable up to several million tuples as well as with a large number of mappings.