The deployment of pre-trained perception models in novel environments often leads to performance degradation due to distributional shifts. Although recent artificial intelligence approaches for metacognition use logical rules to characterize and filter model errors, improving precision often comes at the cost of reduced recall. This paper addresses the hypothesis that leveraging multiple pre-trained models can mitigate this recall reduction. We formulate the challenge of identifying and managing conflicting predictions from various models as a consistency-based abduction problem, building on the idea of abductive learning (ABL) but applying it to test-time instead of training. The input predictions and the learned error detection rules derived from each model are encoded in a logic program. We then seek an abductive explanation—a subset of model predictions—that maximizes prediction coverage while ensuring the rate of logical inconsistencies (derived from domain constraints) remains below a specified threshold. We propose two algorithms for this knowledge representation task: an exact method based on Integer Programming (IP) and an efficient Heuristic Search (HS). Through extensive experiments on a simulated aerial imagery dataset featuring controlled, complex distributional shifts, we demonstrate that our abduction-based framework outperforms individual models and standard ensemble baselines, achieving, for instance, average relative improvements of approximately 13.6% in F1-score and 16.6% in accuracy across 15 diverse test datasets when compared to the best individual model. Our results validate the use of consistency-based abduction as an effective mechanism to robustly integrate knowledge from multiple imperfect models in challenging, novel scenarios.

Computational models of argumentation is an active research field within Artificial Intelligence, with growing recent interest in real-world applications due to its intuitive reasoning mechanism and similarities to human reasoning. In this work, we focus on structured argumentation, which differs from abstract argumentation frameworks in that they work with the internal structure of the arguments. Much of the research in this area is still theoretical in nature, mostly because of the lack of benchmarks (which have mostly been investigated for abstract argumentation)—this has proven to be an important hurdle to overcome in the path to experimental research. Towards addressing this issue, we develop a knowledge base generator, called DPG, for the Defeasible Logic Programming (DeLP) framework that is designed to build synthetic programs for the practical evaluation of several computational tasks based on a set of nine parameters. We also develop a set of seven metrics in order to adequately assess the structural complexity of the generated programs and the computational cost of querying them; we study the computational complexity of computing such metrics, showing that most of them are intractable. Finally, we carry out an experimental evaluation of DPG in two parts. First, we carry out a rigorous study of the relationship between DPG parameter settings and metrics, which leads to the identification of interesting correlations that yield insights into how parameters must be adjusted in order to generate programs of a desired nature. Second, by setting thresholds for the value of specific metrics, we can divide programs into “easy” or “hard”, and we show that it is feasible to train binary classifiers that, given a specific set of values for the parameters of the generator, are able to predict whether or not the generated instances will be difficult or easy to solve in terms of the running time metric. We also investigate the use of autoencoders to support the fully automated generation of easy or hard programs, achieving promising results in this task as well. These results demonstrate that one can avoid the theoretically costly “generate and check” process.

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.

We consider behavior of agents in a long-term multiagent coopetitive setting in which agents vary their cooperative and competitive stances over time. Using the game ofDiplomacyas a testbed, we study how successful agents vary their coopetitive behavior, developing a new “style of play” (SoP) characterization of player behavior. We assess five novel SoP hypotheses about successful behavior. We propose two algorithms to automatically compute an agent’s SoP vector and describe the important factors in this computation. As an agent’s SoP depends on the game state and its perception of threat, we develop a novel “means, motive, and opportunity” (MMO) model of threat and show that we can predict threats effectively using this model. We provide novel insights into how agents should behave to more successfully achieve their goals in long-term coopetitive settings.

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.

An essential part of argumentation-based reasoning is to identify arguments in favor and against a statement or query, select the acceptable ones, and then determine whether or not the original statement should be accepted. We present here an abstract framework that considers two independent forms of argument interaction—support and conflict—and is able to represent distinctive information associated with these arguments. This information can enable additional actions such as: (i) a more in-depth analysis of the relations between the arguments; (ii) a representation of the user’s posture to help in focusing the argumentative process, optimizing the values of attributes associated with certain arguments; and (iii) an enhancement of the semantics taking advantage of the availability of richer information about argument acceptability. Thus, the classical semantic definitions are enhanced by analyzing a set of postulates they satisfy. Finally, a polynomial-time algorithm to perform the labeling process is introduced, in which the argument interactions are considered.

Data present in a wide array of platforms that are part of today's information systems lies at the foundation of many decision making processes, as we have now come to depend on social media, videos, news, forums, chats, ads, maps, and many other data sources for our daily lives. In this article, we first discuss how such data sources are involved in threats to systems' integrity, and then how they can be leveraged along with knowledge-based tools to tackle a set of challenges in the cybersecurity domain. Finally, we present a brief discussion of our roadmap for research and development in the near future to address the set of ever-evolving cyber threats that our systems face every day.

The problem of understanding the reasons behind why different machine learning classifiers make specific predictions is a difficult one, mainly because the inner workings of the algorithms underlying such tools are not amenable to the direct extraction of succinct explanations. In this paper, we address the problem of automatically extracting balanced explanations from predictions generated by any classifier, which include not only why the prediction might be correct but also why it could be wrong. Our framework, calledBalanced English Explanations of Forecasts, can generate such explanations in natural language. After showing that the problem of generating explanations is NP-complete, we focus on the development of a heuristic algorithm, empirically showing that it produces high-quality results both in terms of objective measures—with statistically significant effects shown for several parameter variations—and subjective evaluations based on a survey completed by 100 anonymous participants recruited via Amazon Mechanical Turk.

Recent incidents of data breaches call for organizations to proactively identify cyber attacks on their systems. Darkweb/Deepweb (D2web) forums and marketplaces provide environments where hackers anonymously discuss existing vulnerabilities and commercialize malicious software to exploit those vulnerabilities. These platforms offer security practitioners a threat intelligence environment that allows to mine for patterns related to organization-targeted cyber attacks. In this paper, we describe a system (called DARKMENTION) that learns association rules correlating indicators of attacks from D2web to real-world cyber incidents. Using the learned rules, DARKMENTION generates and submits warnings to a Security Operations Center (SOC) prior to attacks. Our goal was to design a system that automatically generates enterprise-targeted warnings that are timely, actionable, accurate, and transparent. We show that DARKMENTION meets our goal. In particular, we show that it outperforms baseline systems that attempt to generate warnings of cyber attacks related to two enterprises with an average increase in F1 score of about 45% and 57%. Additionally, DARKMENTION was deployed as part of a larger system that is built under a contract with the IARPA Cyber-attack Automated Unconventional Sensor Environment (CAUSE) program. It is actively producing warnings that precede attacks by an average of 3 days.

Malicious attackers often scan nodes in a network in order to identify vulnerabilities that they may exploit as they traverse the network. In this paper, we propose that the system generates a mix of true and false answers in response to scan requests. If the attacker believes that all scan results are true, then he will be on a wrong path. If he believes some scan results are faked, he would have to expend time and effort in order to separate fact from fiction. We propose a probabilistic logic of deception and show that various computations are NP-hard. We model the attacker's state and show the effects of faked scan results. We then show how the defender can generate fake scan results in different states that minimize the damage the attacker can produce. We develop a Naive-PLD algorithm and a Fast-PLD heuristic algorithm for the defender to use and show experimentally that the latter performs well in a fraction of the run time of the former. We ran detailed experiments to assess the performance of these algorithms and further show that by running Fast-PLD off-line and storing the results, we can very efficiently answer run-time scan requests.

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.

A major challenge in cyber-threat analysis is combining information from different sources to find the person or the group responsible for the cyber-attack. It is one of the most important technical and policy challenges in cybersecurity. The lack of ground truth for an individual responsible for an attack has limited previous studies. In this paper, we take a first step towards overcoming this limitation by building a dataset from the capture-the-flag event held at DEFCON, and propose an argumentation model based on a formal reasoning framework called DeLP (Defeasible Logic Programming) designed to aid an analyst in attributing a cyber-attack. We build models from latent variables to reduce the search space of culprits (attackers), and show that this reduction significantly improves the performance of classification-based approaches from 37% to 62% in identifying the attacker.

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.

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.

Action-probabilistic logic programs ( ap -programs) are a class of probabilistic logic programs that have been extensively used during the last few years for modeling behaviors of entities. Rules in ap -programs have the form “If the environment in which entity E operates satisfies certain conditions, then the probability that E will take some action A is between L and U ”. Given an ap -program, we are interested in trying to change the environment, subject to some constraints, so that the probability that entity E takes some action (or combination of actions) is maximized. This is called the Basic Abductive Query Answering Problem (BAQA). We first formally define and study the complexity of BAQA, and then go on to provide an exact (exponential time) algorithm to solve it, followed by more efficient algorithms for specific subclasses of the problem. We also develop appropriate heuristics to solve BAQA efficiently. The second problem, called the Cost-based Query Answering (CBQA) problem checks to see if there is some way of achieving a desired action (or set of actions) with a probability exceeding a threshold, given certain costs. We first formally define and study an exact (intractable) approach to CBQA, and then go on to propose a more efficient algorithm for a specific subclass of ap -programs that builds on the results for the basic version of this problem. We also develop the first algorithms for parallel evaluation of CBQA. We conclude with an extensive report on experimental evaluations performed over prototype implementations of the algorithms developed for both BAQA and CBQA, showing that our parallel algorithms work well in practice.

Annotated Probabilistic Temporal (APT) logic programs support building applications where we wish to reason about statements of the form “Formula G becomes true with a probability in the range [ L , U ] within (or in exactly) Δt time units after formula F became true.” In this paper, we present a sound, but incomplete fixpoint operator that can be used to check consistency and entailment in APT logic programs. We present the first implementation of APT-logic programs and evaluate both its compute time and convergence on a suite of 23 ground APT-logic programs that were automatically learned from two real-world data sets. In both cases, the APT-logic programs contained up to 1,000 ground rules. In one data set, entailment problems were solved on average in under 0.1 seconds per ground rule, while in the other, it took up to 1.3 seconds per ground rule. Consistency was also checked in a reasonable amount of time. When discussing entailment of APT-logic formulas, convergence of the fixpoint operator refers to ( U − L ) being below a certain threshold. We show that on virtually all of the 23 automatically generated APT-logic programs, convergence was quick---often in just 2-3 iterations of the fixpoint operator. Thus, our implementation is a practical first step towards checking consistency and entailment in temporal probabilistic logics without independence or Markovian assumptions.

The semantics of most logics of time and probability is given via a probability distribution over threads , where a thread is a structure specifying what will be true at different points in time (in the future). When assessing the probabilities of statements such as “Event a will occur within 5 units of time of event b ,” there are many different semantics possible, even when assessing the truth of this statement within a single thread. We introduce the syntax of annotated probabilistic temporal (APT) logic programs and axiomatically introduce the key notion of a frequency function (for the first time) to capture different types of intrathread reasoning, and then provide a semantics for intrathread and interthread reasoning in APT logic programs parameterized by such frequency functions. We develop a comprehensive set of complexity results for consistency checking and entailment in APT logic programs, together with sound and complete algorithms to check consistency and entailment. The basic algorithms use linear programming, but we then show how to substantially and correctly reduce the sizes of these linear programs to yield better computational properties. We describe a real world application we are developing using APT logic programs.

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.