Thomas Lukasiewicz

TMLR Journal 2026 Journal Article

A Survey on Deep Learning Approaches for Tabular Data Generation: Utility, Alignment, Fidelity, Privacy, Diversity, and Beyond

• Mihaela C. Stoian
• Eleonora Giunchiglia
• Thomas Lukasiewicz

Generative modelling has become the standard approach for synthesising tabular data. However, different use cases demand synthetic data to comply with different requirements to be useful in practice. In this survey, we review deep generative modelling approaches for tabular data from the perspective of five types of requirements: utility of the synthetic data, alignment of the synthetic data with domain-specific knowledge, statistical fidelity of the synthetic data distribution compared to the real data distribution, privacy-preserving capabilities, and sampling diversity. We group the approaches along two levels of granularity: (i) based on the requirements they address and (ii) according to the underlying model they utilise. Additionally, we summarise the appropriate evaluation methods for each requirement, the relationships among the requirements, and the specific characteristics of each model type. Finally, we discuss future directions for the field, along with opportunities to improve the current evaluation methods. Overall, this survey can be seen as a user guide to tabular data generation: helping readers navigate available models and evaluation methods to find those best suited to their needs.

JBHI Journal 2026 Journal Article

You Need Glimpse Before Segmentation: Stochastic Detector-Actor-Critic for Medical Image Segmentation

• Zhenghua Xu
• Yunxin Liu
• Di Yuan
• Bo Li
• Weipeng Liu
• Thomas Lukasiewicz

Medical images often contain more redundant background areas than natural images, potentially introducing noise and degrading image segmentation performance. Inspired by doctors' diagnostic processes, where they identify the lesion area before conducting a detailed analysis, we introduce a novel S tochastic D etector- A ctor- C ritic (SDAC) framework to tackle this challenge. SDAC initially glimpses the entire image using a detector network and policy gradient algorithms to filter out irrelevant background regions and focus on crucial, smaller areas for segmentation. The Actor-Critic algorithm then dynamically creates segmentation masks pixel by pixel without user intervention or coarse masks, forming a robust segmentation module. Both processes are trained jointly to reduce error propagation and ensure stability and ease of implementation. Our experiments on two commonly used medical image segmentation datasets demonstrate that SDAC achieves competitive results comparable to state-of-the-art methods while using 10x fewer parameters than the best-performing baseline in terms of DICE and IoU metrics. We also conduct detailed ablation studies to enhance understanding and facilitate practical use. Furthermore, SDAC performs well in low-resource settings (i. e. , 50-shot or 100-shot), making it ideal for real-world scenarios. Its lightweight design make SDAC an excellent baseline for medical image segmentation tasks.

ICLR Conference 2025 Conference Paper

Benchmarking Predictive Coding Networks - Made Simple

• Luca Pinchetti
• Chang Qi
• Oleh Lokshyn
• Cornelius Emde
• Amine M'Charrak
• Mufeng Tang
• Simon Frieder
• Bayar Menzat

In this work, we tackle the problems of efficiency and scalability for predictive coding networks (PCNs) in machine learning. To do so, we propose a library that focuses on performance and simplicity, and use it to implement a large set of standard benchmarks for the community to use for their experiments. As most works in the field propose their own tasks and architectures, do not compare one against each other, and focus on small-scale tasks, a simple and fast open-source library, and a comprehensive set of benchmarks, would address all of these concerns. Then, we perform extensive tests on such benchmarks using both existing algorithms for PCNs, as well as adaptations of other methods popular in the bio-plausible deep learning community. All of this has allowed us to (i) test architectures much larger than commonly used in the literature, on more complex datasets; (ii) reach new state-of-the-art results in all of the tasks and dataset provided; (iii) clearly highlight what the current limitations of PCNs are, allowing us to state important future research directions. With the hope of galvanizing community efforts towards one of the main open problems in the field, scalability, we will release the code, tests, and benchmarks.

AIJ Journal 2025 Journal Article

Explanations for query answers under existential rules

• İsmail İlkan Ceylan
• Thomas Lukasiewicz
• Enrico Malizia
• Andrius Vaicenavičius

Ontology-based data access is an extensively studied paradigm aiming at improving query answers with the use of an “ontology”. An ontology is a specification of a domain of interest, which, in this context, is described via a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for ontological query answers. This is a quite important aspect, as the fact that many recent AI systems mostly operating as black boxes has led to some serious concerns. In the literature, various works on explanations in the context of description logics (DLs) have appeared, mostly focusing on explaining concept subsumption and concept unsatisfiability in the ontologies. Some works on explaining query entailment in DLs have appeared as well, however, mainly dealing with inconsistency-tolerant semantics and, actually, non-entailment of the queries. Surprisingly, explaining ontological query entailment has received little attention for ontology languages based on existential rules. In fact, although DLs are popular formalisms to model ontologies, it is generally agreed that rule-based ontologies are well-suited for data-intensive applications, as they allow us to conveniently deal with higher-arity relations, which naturally occur in standard relational databases. The goal of this work is to close this gap, and study the problem of explaining query entailment in the context of existential rules ontologies in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations for various classes of existential rules, and for different complexity measures.

NAI Journal 2025 Journal Article

Machine learning with requirements: A manifesto

• Eleonora Giunchiglia
• Fergus Imrie
• Mihaela van der Schaar
• Thomas Lukasiewicz

In the recent years, machine learning has made great advancements that have been at the root of many breakthroughs in different application domains. However, it is still an open issue how to make them applicable to high-stakes or safety-critical application domains, as they can often be brittle and unreliable. In this paper, we argue that requirements definition and satisfaction can go a long way to make machine learning models even more fitting to the real world, especially in critical domains. To this end, we present two problems in which (i) requirements arise naturally, (ii) machine learning models are or can be fruitfully deployed, and (iii) neglecting the requirements can have dramatic consequences. Our proposed pyramid development process integrates requirements specification into every stage of the machine learning pipeline, ensuring mutual influence between requirements and subsequent phases. Additionally, we explore the pivotal role of Neuro-symbolic AI in facilitating this integration, paving the way for more reliable and robust machine learning applications in critical domains. Through this approach, we aim to bridge the gap between theoretical advancements and practical implementations, ensuring machine learning’s safe and effective deployment in sensitive areas.

ICLR Conference 2025 Conference Paper

Shh, don't say that! Domain Certification in LLMs

• Cornelius Emde
• Alasdair Paren
• Preetham Arvind
• Maxime Guillaume Kayser
• Tom Rainforth
• Thomas Lukasiewicz
• Philip H. S. Torr
• Adel Bibi

Large language models (LLMs) are often deployed to do constrained tasks, with narrow domains. For example, customer support bots can be built on top of LLMs, relying on their broad language understanding and capabilities to enhance performance. However, these LLMs are adversarially susceptible, potentially generating outputs outside the intended domain. To formalize, assess and mitigate this risk, we introduce domain certification; a guarantee that accurately characterizes the out-of-domain behavior of language models. We then propose a simple yet effective approach dubbed VALID that provides adversarial bounds as a certificate. Finally, we evaluate our method across a diverse set of datasets, demonstrating that it yields meaningful certificates.

ICLR Conference 2025 Conference Paper

Towards Certification of Uncertainty Calibration under Adversarial Attacks

• Cornelius Emde
• Francesco Pinto
• Thomas Lukasiewicz
• Philip H. S. Torr
• Adel Bibi

Since neural classifiers are known to be sensitive to adversarial perturbations that alter their accuracy, certification methods have been developed to provide provable guarantees on the insensitivity of their predictions to such perturbations. On the other hand, in safety-critical applications, the frequentist interpretation of the confidence of a classifier (also known as model calibration) can be of utmost importance. This property can be measured via the Brier score or the expected calibration error. We show that attacks can significantly harm calibration, and thus propose certified calibration providing worst-case bounds on calibration under adversarial perturbations. Specifically, we produce analytic bounds for the Brier score and approximate bounds via the solution of a mixed-integer program on the expected calibration error. Finally, we propose novel calibration attacks and demonstrate how they can improve model calibration through adversarial calibration training. The code will be publicly released upon acceptance.

ICLR Conference 2024 Conference Paper

A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks

• Tommaso Salvatori
• Yuhang Song 0001
• Yordan Yordanov
• Beren Millidge
• Lei Sha
• Cornelius Emde
• Zhenghua Xu 0001
• Rafal Bogacz

Predictive coding networks are neuroscience-inspired models with roots in both Bayesian statistics and neuroscience. Training such models, however, is quite inefficient and unstable. In this work, we show how by simply changing the temporal scheduling of the update rule for the synaptic weights leads to an algorithm that is much more efficient and stable than the original one, and has theoretical guarantees in terms of convergence. The proposed algorithm, that we call incremental predictive coding (iPC) is also more biologically plausible than the original one, as it it fully automatic. In an extensive set of experiments, we show that iPC constantly performs better than the original formulation on a large number of benchmarks for image classification, as well as for the training of both conditional and masked language models, in terms of test accuracy, efficiency, and convergence with respect to a large set of hyperparameters.

TMLR Journal 2024 Journal Article

Correcting Flaws in Common Disentanglement Metrics

• Louis Mahon
• Lei Sha
• Thomas Lukasiewicz

Disentangled representations are those in which distinct features, such as size or shape, are represented by distinct neurons. Quantifying the extent to which a given representation is disentangled is not straightforward; multiple metrics have been proposed. In this paper, we identify two failings of existing metrics, which mean they can assign a high score to a model which is still entangled, and we propose two new metrics, which redress these problems. First, we use hypothetical toy examples to demonstrate the failure modes we identify for existing metrics. Then, we show that similar situations occur in practice. Finally, we validate our metrics on the downstream task of compositional generalization. We measure the performance of six existing disentanglement models on this downstream compositional generalization task, and show that performance is (a) generally quite poor, (b) correlated, to varying degrees, with most disentanglement metrics, and (c) most strongly correlated with our newly proposed metrics. Anonymous code to reproduce our results is available at https://github.com/anon296/anon.

AAAI Conference 2024 Conference Paper

Hard Regularization to Prevent Deep Online Clustering Collapse without Data Augmentation

• Louis Mahon
• Thomas Lukasiewicz

Online deep clustering refers to the joint use of a feature extraction network and a clustering model to assign cluster labels to each new data point or batch as it is processed. While faster and more versatile than offline methods, online clustering can easily reach the collapsed solution where the encoder maps all inputs to the same point and all are put into a single cluster. Successful existing models have employed various techniques to avoid this problem, most of which require data augmentation or which aim to make the average soft assignment across the dataset the same for each cluster. We propose a method that does not require data augmentation, and that, differently from existing methods, regularizes the hard assignments. Using a Bayesian framework, we derive an intuitive optimization objective that can be straightforwardly included in the training of the encoder network. Tested on four image datasets, it consistently avoids collapse more robustly than other methods and leads to more accurate clustering. We also conduct further experiments and analyses justifying our choice to regularize the hard cluster assignments. Code is available at https://github.com/Lou1sM/online_hard_clustering.

ICLR Conference 2024 Conference Paper

How Realistic Is Your Synthetic Data? Constraining Deep Generative Models for Tabular Data

• Mihaela C. Stoian
• Salijona Dyrmishi
• Maxime Cordy
• Thomas Lukasiewicz
• Eleonora Giunchiglia

Deep Generative Models (DGMs) have been shown to be powerful tools for generating tabular data, as they have been increasingly able to capture the complex distributions that characterize them. However, to generate realistic synthetic data, it is often not enough to have a good approximation of their distribution, as it also requires compliance with constraints that encode essential background knowledge on the problem at hand. In this paper, we address this limitation and show how DGMs for tabular data can be transformed into Constrained Deep Generative Models (C-DGMs), whose generated samples are guaranteed to be compliant with the given constraints. This is achieved by automatically parsing the constraints and transforming them into a Constraint Layer (CL) seamlessly integrated with the DGM. Our extensive experimental analysis with various DGMs and tasks reveals that standard DGMs often violate constraints, some exceeding 95% non-compliance, while their corresponding C-DGMs are never non-compliant. Then, we quantitatively demonstrate that, at training time, C-DGMs are able to exploit the background knowledge expressed by the constraints to outperform their standard counterparts with up to 4.5% improvement in utility and detection. Further, we show how our CL does not necessarily need to be integrated at training time, as it can be also used as a guardrail at inference time, still producing some improvements in the overall performance of the models. Finally, we show that our CL does not hinder the sample generation time of the models.

IJCAI Conference 2024 Conference Paper

PiShield: A PyTorch Package for Learning with Requirements

• Mihaela C. Stoian
• Alex Tatomir
• Thomas Lukasiewicz
• Eleonora Giunchiglia

Deep learning models have shown their strengths in various application domains, however, they often struggle to meet safety requirements for their outputs. In this paper, we introduce PiShield, the first package ever allowing for the integration of the requirements into the neural networks' topology. PiShield guarantees compliance with these requirements, regardless of input. Additionally, it allows for integrating requirements both at inference and/or training time, depending on the practitioners' needs. Given the widespread application of deep learning, there is a growing need for frameworks allowing for the integration of the requirements across various domains. Here, we explore three application scenarios: functional genomics, autonomous driving, and tabular data generation.

AIJ Journal 2024 Journal Article

Pre-training and diagnosing knowledge base completion models

• Vid Kocijan
• Myeongjun Jang
• Thomas Lukasiewicz

In this work, we introduce and analyze an approach to knowledge transfer from one collection of facts to another without the need for entity or relation matching. The method works for both canonicalized knowledge bases and uncanonicalized or open knowledge bases, i. e. , knowledge bases where more than one copy of a real-world entity or relation may exist. The main contribution is a method that can make use of large-scale pre-training on facts, which were collected from unstructured text, to improve predictions on structured data from a specific domain. The introduced method is most impactful on small datasets such as ReVerb20k, where a 6% absolute increase of mean reciprocal rank and 65% relative decrease of mean rank over the previously best method was achieved, despite not relying on large pre-trained models like Bert. To understand the obtained pre-trained models better, we then introduce a novel dataset for the analysis of pre-trained models for Open Knowledge Base Completion, called Doge (Diagnostics of Open knowledge Graph Embeddings). It consists of 6 subsets and is designed to measure multiple properties of a pre-trained model: robustness against synonyms, ability to perform deductive reasoning, presence of gender stereotypes, consistency with reverse relations, and coverage of different areas of general knowledge. Using the introduced dataset, we show that the existing OKBC models lack consistency in presence of synonyms and inverse relations and are unable to perform deductive reasoning. Moreover, their predictions often align with gender stereotypes, which persist even when presented with counterevidence. We additionally investigate the role of pre-trained word embeddings and demonstrate that avoiding biased word embeddings is not a sufficient measure to prevent biased behavior of OKBC models.

ICML Conference 2024 Conference Paper

Predictive Coding beyond Correlations

• Tommaso Salvatori
• Luca Pinchetti
• Amine M'Charrak
• Beren Millidge
• Thomas Lukasiewicz

Biologically plausible learning algorithms offer a promising alternative to traditional deep learning techniques, especially in overcoming the limitations of backpropagation in fast and low-energy neuromorphic implementations. To this end, there has been extensive research in understanding what their capabilities are. In this work, we show how one of such algorithms, called predictive coding, is able to perform causal inference tasks. First, we show how a simple change in the inference process of predictive coding enables to compute interventions without the need to mutilate or redefine a causal graph. Then, we explore applications in cases where the graph is unknown, and has to be inferred from observational data. Empirically, we show how such findings can be used to improve the performance of predictive coding in image classification tasks, and conclude that such models are naturally able to perform causal inference tasks using a biologically plausible kind of message passing.

AAAI Conference 2024 Conference Paper

The Defeat of the Winograd Schema Challenge (Abstract Reprint)

• Vid Kocijan
• Ernest Davis
• Thomas Lukasiewicz
• Gary Marcus
• Leora Morgenstern

The Winograd Schema Challenge—a set of twin sentences involving pronoun reference disambiguation that seem to require the use of commonsense knowledge—was proposed by Hector Levesque in 2011. By 2019, a number of AI systems, based on large pre-trained transformer-based language models and fine-tuned on these kinds of problems, achieved better than 90% accuracy. In this paper, we review the history of the Winograd Schema Challenge and discuss the lasting contributions of the flurry of research that has taken place on the WSC in the last decade. We discuss the significance of various datasets developed for WSC, and the research community's deeper understanding of the role of surrogate tasks in assessing the intelligence of an AI system.

ICLR Conference 2023 Conference Paper

A Theoretical Framework for Inference and Learning in Predictive Coding Networks

• Beren Millidge
• Yuhang Song 0001
• Tommaso Salvatori
• Thomas Lukasiewicz
• Rafal Bogacz

Predictive coding (PC) is an influential theory in computational neuroscience, which argues that the cortex forms unsupervised world models by implementing a hierarchical process of prediction error minimization. PC networks (PCNs) are trained in two phases. First, neural activities are updated to optimize the network's response to external stimuli. Second, synaptic weights are updated to consolidate this change in activity --- an algorithm called \emph{prospective configuration}. While previous work has shown how in various limits, PCNs can be found to approximate backpropagation (BP), recent work has demonstrated that PCNs operating in this standard regime, which does not approximate BP, nevertheless obtain competitive training and generalization performance to BP-trained networks while outperforming them on various tasks. However, little is understood theoretically about the properties and dynamics of PCNs in this regime. In this paper, we provide a comprehensive theoretical analysis of the properties of PCNs trained with prospective configuration. We first derive analytical results concerning the inference equilibrium for PCNs and a previously unknown close connection relationship to target propagation (TP). Secondly, we provide a theoretical analysis of learning in PCNs as a variant of generalized expectation-maximization and use that to prove the convergence of PCNs to critical points of the BP loss function, thus showing that deep PCNs can, in theory, achieve the same generalization performance as BP, while maintaining their unique advantages.

ECAI Conference 2023 Conference Paper

Associative Memories in the Feature Space

• Tommaso Salvatori
• Beren Millidge
• Yuhang Song 0001
• Rafal Bogacz
• Thomas Lukasiewicz

An autoassociative memory model is a function that, given a set of data points, takes as input an arbitrary vector and outputs the most similar data point from the memorized set. However, popular memory models fail to retrieve images even when the corruption is mild and easy to detect for a human evaluator. This is because similarities are evaluated in the raw pixel space, which does not contain any semantic information about the images. This problem can be easily solved by computing similarities in an embedding space instead of the pixel space. We show that an effective way of computing such embeddings is via a network pretrained with a contrastive loss. As the dimension of embedding spaces is often significantly smaller than the pixel space, we also have a faster computation of similarity scores. We test this method on complex datasets such as CIFAR10 and STL10. An additional drawback of current models is the need of storing the whole dataset in the pixel space, which is often extremely large. We relax this condition and propose a class of memory models that only stores low-dimensional semantic embeddings, and uses them to retrieve similar, but not identical, memories. We demonstrate a proof of concept of this method on a simple task on the MNIST dataset.

ICLR Conference 2023 Conference Paper

Backpropagation at the Infinitesimal Inference Limit of Energy-Based Models: Unifying Predictive Coding, Equilibrium Propagation, and Contrastive Hebbian Learning

• Beren Millidge
• Yuhang Song 0001
• Tommaso Salvatori
• Thomas Lukasiewicz
• Rafal Bogacz

How the brain performs credit assignment is a fundamental unsolved problem in neuroscience. Many `biologically plausible' algorithms have been proposed, which compute gradients that approximate those computed by backpropagation (BP), and which operate in ways that more closely satisfy the constraints imposed by neural circuitry. Many such algorithms utilize the framework of energy-based models (EBMs), in which all free variables in the model are optimized to minimize a global energy function. However, in the literature, these algorithms exist in isolation and no unified theory exists linking them together. Here, we provide a comprehensive theory of the conditions under which EBMs can approximate BP, which lets us unify many of the BP approximation results in the literature (namely, predictive coding, equilibrium propagation, and contrastive Hebbian learning) and demonstrate that their approximation to BP arises from a simple and general mathematical property of EBMs at free-phase equilibrium. This property can then be exploited in different ways with different energy functions, and these specific choices yield a family of BP-approximating algorithms, which both includes the known results in the literature and can be used to derive new ones.

KR Conference 2023 Conference Paper

Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Preferred Repairs

• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro

Inconsistency-tolerant semantics have been proposed to provide meaningful ontological query answers even in the presence of inconsistencies. Several such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the database, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/- has considered only the subset and cardinality maximality criteria. We take here a step further and study inconsistency-tolerant semantics under maximality criteria based on weights and priority levels. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

NeSy Conference 2023 Conference Paper

Exploiting T-norms for Deep Learning in Autonomous Driving

• Mihaela C. Stoian
• Eleonora Giunchiglia
• Thomas Lukasiewicz

Deep learning has been at the core of the autonomous driving field development, due to the neural networks’ success in finding patterns in raw data and turning them into accurate predictions. Moreover, recent neuro-symbolic works have shown that incorporating the available background knowledge about the problem at hand in the loss function via t-norms can further improve the deep learning models’ performance. However, t-norm-based losses may have very high memory requirements and, thus, they may be impossible to apply in complex application domains like autonomous driving. In this paper, we show how it is possible to define memory-efficient t-norm-based losses, allowing for exploiting t-norms for the task of event detection in autonomous driving. We conduct an extensive experimental analysis on the ROAD-R dataset and show (i) that our proposal can be implemented and run on GPUs with less than 25 GiB of available memory, while standard t-norm-based losses are estimated to require more than 100 GiB, far exceeding the amount of memory normally available, (ii) that t-norm-based losses improve performance, especially when limited labelled data are available, and (iii) that t-norm-based losses can further improve performance when exploited on both labelled and unlabelled data.

JBHI Journal 2023 Journal Article

Hi-BEHRT: Hierarchical Transformer-Based Model for Accurate Prediction of Clinical Events Using Multimodal Longitudinal Electronic Health Records

• Yikuan Li
• Mohammad Mamouei
• Gholamreza Salimi-Khorshidi
• Shishir Rao
• Abdelaali Hassaine
• Dexter Canoy
• Thomas Lukasiewicz
• Kazem Rahimi

Electronic health records (EHR) represent a holistic overview of patients’ trajectories. Their increasing availability has fueled new hopes to leverage them and develop accurate risk prediction models for a wide range of diseases. Given the complex interrelationships of medical records and patient outcomes, deep learning models have shown clear merits in achieving this goal. However, a key limitation of current study remains their capacity in processing long sequences, and long sequence modelling and its application in the context of healthcare and EHR remains unexplored. Capturing the whole history of medical encounters is expected to lead to more accurate predictions, but the inclusion of records collected for decades and from multiple resources can inevitably exceed the receptive field of the most existing deep learning architectures. This can result in missing crucial, long-term dependencies. To address this gap, we present Hi-BEHRT, a hierarchical Transformer-based model that can significantly expand the receptive field of Transformers and extract associations from much longer sequences. Using a multimodal large-scale linked longitudinal EHR, the Hi-BEHRT exceeds the state-of-the-art deep learning models 1% to 5% for area under the receiver operating characteristic (AUROC) curve and 1% to 8% for area under the precision recall (AUPRC) curve on average, and 2% to 8% (AUROC) and 2% to 11% (AUPRC) for patients with long medical history for 5-year heart failure, diabetes, chronic kidney disease, and stroke risk prediction. Additionally, because pretraining for hierarchical Transformer is not well-established, we provide an effective end-to-end contrastive pre-training strategy for Hi-BEHRT using EHR, improving its transferability on predicting clinical events with relatively small training dataset.

NeurIPS Conference 2023 Conference Paper

Mathematical Capabilities of ChatGPT

• Simon Frieder
• Luca Pinchetti
• Chevalier Chevalier
• Ryan-Rhys Griffiths
• Tommaso Salvatori
• Thomas Lukasiewicz
• Philipp Petersen
• Julius Berner

We investigate the mathematical capabilities of two iterations of ChatGPT (released 9-January-2023 and 30-January-2023) and of GPT-4 by testing them on publicly available datasets, as well as hand-crafted ones, using a novel methodology. In contrast to formal mathematics, where large databases of formal proofs are available (e. g. , mathlib, the Lean Mathematical Library), current datasets of natural-language mathematics used to benchmark language models either cover only elementary mathematics or are very small. We address this by publicly releasing two new datasets: GHOSTS and miniGHOSTS. These are the first natural-language datasets curated by working researchers in mathematics that (1) aim to cover graduate-level mathematics, (2) provide a holistic overview of the mathematical capabilities of language models, and (3) distinguish multiple dimensions of mathematical reasoning. These datasets test on 1636 human expert evaluations whether ChatGPT and GPT-4 can be helpful assistants to professional mathematicians by emulating use cases that arise in the daily professional activities of mathematicians. We benchmark the models on a range of fine-grained performance metrics. For advanced mathematics, this is the most detailed evaluation effort to date. We find that ChatGPT and GPT-4 can be used most successfully as mathematical assistants for querying facts, acting as mathematical search engines and knowledge base interfaces. GPT-4 can additionally be used for undergraduate-level mathematics but fails on graduate-level difficulty. Contrary to many positive reports in the media about GPT-4 and ChatGPT's exam-solving abilities (a potential case of selection bias), their overall mathematical performance is well below the level of a graduate student. Hence, if you aim to use ChatGPT to pass a graduate-level math exam, you would be better off copying from your average peer!

ICML Conference 2023 Conference Paper

NP-SemiSeg: When Neural Processes meet Semi-Supervised Semantic Segmentation

• Jianfeng Wang
• Daniela Massiceti
• Xiaolin Hu 0001
• Vladimir Pavlovic 0001
• Thomas Lukasiewicz

Semi-supervised semantic segmentation involves assigning pixel-wise labels to unlabeled images at training time. This is useful in a wide range of real-world applications where collecting pixel-wise labels is not feasible in time or cost. Current approaches to semi-supervised semantic segmentation work by predicting pseudo-labels for each pixel from a class-wise probability distribution output by a model. If this predicted probability distribution is incorrect, however, it leads to poor segmentation results which can have knock-on consequences in safety critical systems, like medical images or self-driving cars. It is, therefore, important to understand what a model does not know, which is mainly achieved by uncertainty quantification. Recently, neural processes (NPs) have been explored in semi-supervised image classification, and they have been a computationally efficient and effective method for uncertainty quantification. In this work, we move one step forward by adapting NPs to semi-supervised semantic segmentation, resulting in a new model called NP-SemiSeg. We experimentally evaluated NP-SemiSeg on the public benchmarks PASCAL VOC 2012 and Cityscapes, with different training settings, and the results verify its effectiveness.

AIJ Journal 2023 Journal Article

Rationalizing predictions by adversarial information calibration

• Lei Sha
• Oana-Maria Camburu
• Thomas Lukasiewicz

Explaining the predictions of AI models is paramount in safety-critical applications, such as in legal or medical domains. One form of explanation for a prediction is an extractive rationale, i. e. , a subset of features of an instance that lead the model to give its prediction on that instance. For example, the subphrase “he stole the mobile phone” can be an extractive rationale for the prediction of “Theft”. Previous works on generating extractive rationales usually employ a two-phase model: a selector that selects the most important features (i. e. , the rationale) followed by a predictor that makes the prediction based exclusively on the selected features. One disadvantage of these works is that the main signal for learning to select features comes from the comparison of the answers given by the predictor to the ground-truth answers. In this work, we propose to squeeze more information from the predictor via an information calibration method. More precisely, we train two models jointly: one is a typical neural model that solves the task at hand in an accurate but black-box manner, and the other is a selector-predictor model that additionally produces a rationale for its prediction. The first model is used as a guide for the second model. We use an adversarial technique to calibrate the information extracted by the two models such that the difference between them is an indicator of the missed or over-selected features. In addition, for natural language tasks, we propose a language-model-based regularizer to encourage the extraction of fluent rationales. Experimental results on a sentiment analysis task, a hate speech recognition task, as well as on three tasks from the legal domain show the effectiveness of our approach to rationale extraction.

AIJ Journal 2023 Journal Article

The defeat of the Winograd Schema Challenge

• Vid Kocijan
• Ernest Davis
• Thomas Lukasiewicz
• Gary Marcus
• Leora Morgenstern

The Winograd Schema Challenge—a set of twin sentences involving pronoun reference disambiguation that seem to require the use of commonsense knowledge—was proposed by Hector Levesque in 2011. By 2019, a number of AI systems, based on large pre-trained transformer-based language models and fine-tuned on these kinds of problems, achieved better than 90% accuracy. In this paper, we review the history of the Winograd Schema Challenge and discuss the lasting contributions of the flurry of research that has taken place on the WSC in the last decade. We discuss the significance of various datasets developed for WSC, and the research community's deeper understanding of the role of surrogate tasks in assessing the intelligence of an AI system.

ICML Conference 2022 Conference Paper

(Non-)Convergence Results for Predictive Coding Networks

• Simon Frieder
• Thomas Lukasiewicz

Predictive coding networks (PCNs) are (un)supervised learning models, coming from neuroscience, that approximate how the brain works. One major open problem around PCNs is their convergence behavior. In this paper, we use dynamical systems theory to formally investigate the convergence of PCNs as they are used in machine learning. Doing so, we put their theory on a firm, rigorous basis, by developing a precise mathematical framework for PCN and show that for sufficiently small weights and initializations, PCNs converge for any input. Thereby, we provide the theoretical assurance that previous implementations, whose convergence was assessed solely by numerical experiments, can indeed capture the correct behavior of PCNs. Outside of the identified regime of small weights and small initializations, we show via a counterexample that PCNs can diverge, countering common beliefs held in the community. This is achieved by identifying a Neimark-Sacker bifurcation in a PCN of small size, which gives rise to an unstable fixed point and an invariant curve around it.

JBHI Journal 2022 Journal Article

An Explainable Transformer-Based Deep Learning Model for the Prediction of Incident Heart Failure

• Shishir Rao
• Yikuan Li
• Rema Ramakrishnan
• Abdelaali Hassaine
• Dexter Canoy
• John Cleland
• Thomas Lukasiewicz
• Gholamreza Salimi-Khorshidi

Predicting the incidence of complex chronic conditions such as heart failure is challenging. Deep learning models applied to rich electronic health records may improve prediction but remain unexplainable hampering their wider use in medical practice. We aimed to develop a deep-learning framework for accurate and yet explainable prediction of 6-month incident heart failure (HF). Using 100, 071 patients from longitudinal linked electronic health records across the U. K. , we applied a novel Transformer-based risk model using all community and hospital diagnoses and medications contextualized within the age and calendar year for each patient's clinical encounter. Feature importance was investigated with an ablation analysis to compare model performance when alternatively removing features and by comparing the variability of temporal representations. A post-hoc perturbation technique was conducted to propagate the changes in the input to the outcome for feature contribution analyses. Our model achieved 0. 93 area under the receiver operator curve and 0. 69 area under the precision-recall curve on internal 5-fold cross validation and outperformed existing deep learning models. Ablation analysis indicated medication is important for predicting HF risk, calendar year is more important than chronological age, which was further reinforced by temporal variability analysis. Contribution analyses identified risk factors that are closely related to HF. Many of them were consistent with existing knowledge from clinical and epidemiological research but several new associations were revealed which had not been considered in expert-driven risk prediction models. In conclusion, the results highlight that our deep learning model, in addition high predictive performance, can inform data-driven risk factor identification.

AIJ Journal 2022 Journal Article

Complexity results for preference aggregation over (m)CP-nets: Max and rank voting

• Thomas Lukasiewicz
• Enrico Malizia

Aggregating preferences over combinatorial domains has a plethora of applications in AI. Due to the exponential nature of combinatorial preferences, compact representations are needed, and conditional ceteris paribus preference networks (CP-nets) are among the most studied compact representation formalisms. Unlike the problem of outcome dominance over individual CP-nets, which received an extensive complexity analysis in the literature, mCP-nets (and global voting/preference aggregation over CP-nets) lacked such a thorough complexity characterization, despite this being reported multiple times in the literature as an open problem. An initial complexity analysis for mCP-nets was carried out only recently, where Pareto and majority dominance semantics were studied. In this paper, we further explore the complexity of mCP-nets, giving a precise complexity analysis of the dominance semantics in mCP-nets when the max and rank voting schemes are considered. In particular, we show that deciding dominance under max voting is Θ 2 P -complete, while deciding optimal outcomes and their existence under max voting is complete for Π 2 P and Σ 3 P, respectively. We also show that, under max voting, deciding optimum outcomes is Π 2 P -complete, and deciding their existence is Π 2 P -hard and in Σ 3 P. As for rank voting, apart from deciding whether mCP-nets have rank optimal outcomes, which is a trivial problem, as all mCP-nets have rank optimal outcomes, all the other rank voting tasks considered are tractable and in P. Interestingly, we show here that these problems are not only in P, but also P-hard (and hence P-complete). Furthermore, we show that deciding whether mCP-nets have Pareto optimum outcomes, which was known to be feasible in polynomial time, is actually P-complete, as well as that various tasks for CP-nets are P-complete. These results provide interesting insights, as P-complete problems are (currently believed to be) inherently sequential, and hence they cannot benefit from highly parallel computations.

IJCAI Conference 2022 Conference Paper

Deep Learning with Logical Constraints

• Eleonora Giunchiglia
• Mihaela Catalina Stoian
• Thomas Lukasiewicz

In recent years, there has been an increasing interest in exploiting logically specified background knowledge in order to obtain neural models (i) with a better performance, (ii) able to learn from less data, and/or (iii) guaranteed to be compliant with the background knowledge itself, e. g. , for safety-critical applications. In this survey, we retrace such works and categorize them based on (i) the logical language that they use to express the background knowledge and (ii) the goals that they achieve.

IJCAI Conference 2022 Conference Paper

Explanations for Negative Query Answers under Inconsistency-Tolerant Semantics

• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro

Inconsistency-tolerant semantics have been proposed to provide meaningful query answers even in the presence of inconsistent knowledge. Recently, explainability has also become a prominent problem in different areas of AI. While the complexity of inconsistency-tolerant semantics is rather well-understood, not much attention has been paid yet to the problem of explaining query answers when inconsistencies may exist. Recent work on existential rules in the inconsistent setting has focused only on understanding why a query is entailed. In this paper, we address another important problem, which is explaining why a query is not entailed under an inconsistency-tolerant semantics. In particular, we consider three popular semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.

AIJ Journal 2022 Journal Article

Inconsistency-tolerant query answering for existential rules

• Thomas Lukasiewicz
• Enrico Malizia
• Maria Vanina Martinez
• Cristian Molinaro
• Andreas Pieris
• Gerardo I. Simari

Querying inconsistent knowledge bases is an intriguing problem that gave rise to a flourishing research activity in the knowledge representation and reasoning community during the last years. It has been extensively studied in the context of description logics (DLs), and its computational complexity is rather well-understood. Although DLs are popular formalisms for modeling ontologies, it is generally agreed that rule-based ontologies are well-suited for data-intensive applications, since they allow us to conveniently deal with higher-arity relations, which naturally occur in standard relational databases. The goal of this work is to perform an in-depth complexity analysis of querying inconsistent knowledge bases in the case of the main decidable classes of existential rules, based on the notions of guardedness, linearity, acyclicity, and stickiness, enriched with negative (a. k. a. denial) constraints. Our investigation concentrates on three central inconsistency-tolerant semantics: the ABox repair (AR) semantics, considered as the standard one, and its main sound approximations, the intersection of repairs (IAR) semantics and the intersection of closed repairs (ICR) semantics.

ICML Conference 2022 Conference Paper

Knowledge-Grounded Self-Rationalization via Extractive and Natural Language Explanations

• Bodhisattwa Prasad Majumder
• Oana Camburu
• Thomas Lukasiewicz
• Julian J. McAuley

Models that generate extractive rationales (i. e. , subsets of features) or natural language explanations (NLEs) for their predictions are important for explainable AI. While an extractive rationale provides a quick view of the features most responsible for a prediction, an NLE allows for a comprehensive description of the decision-making process behind a prediction. However, current models that generate the best extractive rationales or NLEs often fall behind the state-of-the-art (SOTA) in terms of task performance. In this work, we bridge this gap by introducing RExC, a self-rationalizing framework that grounds its predictions and two complementary types of explanations (NLEs and extractive rationales) in background knowledge. Our framework improves over previous methods by: (i) reaching SOTA task performance while also providing explanations, (ii) providing two types of explanations, while existing models usually provide only one type, and (iii) beating by a large margin the previous SOTA in terms of quality of both types of explanations. Furthermore, a perturbation analysis in RExC shows a high degree of association between explanations and predictions, a necessary property of faithful explanations.

NeurIPS Conference 2022 Conference Paper

Learning on Arbitrary Graph Topologies via Predictive Coding

• Tommaso Salvatori
• Luca Pinchetti
• Beren Millidge
• Yuhang Song
• Tianyi Bao
• Rafal Bogacz
• Thomas Lukasiewicz

Training with backpropagation (BP) in standard deep learning consists of two main steps: a forward pass that maps a data point to its prediction, and a backward pass that propagates the error of this prediction back through the network. This process is highly effective when the goal is to minimize a specific objective function. However, it does not allow training on networks with cyclic or backward connections. This is an obstacle to reaching brain-like capabilities, as the highly complex heterarchical structure of the neural connections in the neocortex are potentially fundamental for its effectiveness. In this paper, we show how predictive coding (PC), a theory of information processing in the cortex, can be used to perform inference and learning on arbitrary graph topologies. We experimentally show how this formulation, called PC graphs, can be used to flexibly perform different tasks with the same network by simply stimulating specific neurons. This enables the model to be queried on stimuli with different structures, such as partial images, images with labels, or images without labels. We conclude by investigating how the topology of the graph influences the final performance, and comparing against simple baselines trained with BP.

ICML Conference 2022 Conference Paper

NP-Match: When Neural Processes meet Semi-Supervised Learning

• Jianfeng Wang
• Thomas Lukasiewicz
• Daniela Massiceti
• Xiaolin Hu 0001
• Vladimir Pavlovic 0001
• Alexandros Neophytou

Semi-supervised learning (SSL) has been widely explored in recent years, and it is an effective way of leveraging unlabeled data to reduce the reliance on labeled data. In this work, we adjust neural processes (NPs) to the semi-supervised image classification task, resulting in a new method named NP-Match. NP-Match is suited to this task for two reasons. Firstly, NP-Match implicitly compares data points when making predictions, and as a result, the prediction of each unlabeled data point is affected by the labeled data points that are similar to it, which improves the quality of pseudolabels. Secondly, NP-Match is able to estimate uncertainty that can be used as a tool for selecting unlabeled samples with reliable pseudo-labels. Compared with uncertainty-based SSL methods implemented with Monte Carlo (MC) dropout, NP-Match estimates uncertainty with much less computational overhead, which can save time at both the training and the testing phases. We conducted extensive experiments on four public datasets, and NP-Match outperforms state-of-theart (SOTA) results or achieves competitive results on them, which shows the effectiveness of NPMatch and its potential for SSL.

NeurIPS Conference 2022 Conference Paper

Predictive Coding beyond Gaussian Distributions

• Luca Pinchetti
• Tommaso Salvatori
• Yordan Yordanov
• Beren Millidge
• Yuhang Song
• Thomas Lukasiewicz

A large amount of recent research has the far-reaching goal of finding training methods for deep neural networks that can serve as alternatives to backpropagation~(BP). A prominent example is predictive coding (PC), which is a neuroscience-inspired method that performs inference on hierarchical Gaussian generative models. These methods, however, fail to keep up with modern neural networks, as they are unable to replicate the dynamics of complex layers and activation functions. In this work, we solve this problem by generalizing PC to arbitrary probability distributions, enabling the training of architectures, such as transformers, that are hard to approximate with only Gaussian assumptions. We perform three experimental analyses. First, we study the gap between our method and the standard formulation of PC on multiple toy examples. Second, we test the reconstruction quality on variational autoencoders, where our method reaches the same reconstruction quality as BP. Third, we show that our method allows us to train transformer networks and achieve performance comparable with BP on conditional language models. More broadly, this method allows neuroscience-inspired learning to be applied to multiple domains, since the internal distributions can be flexibly adapted to the data, tasks, and architectures used.

IJCAI Conference 2022 Conference Paper

Predictive Coding: Towards a Future of Deep Learning beyond Backpropagation?

• Beren Millidge
• Tommaso Salvatori
• Yuhang Song
• Rafal Bogacz
• Thomas Lukasiewicz

The backpropagation of error algorithm (BP) used to train deep neural networks has been fundamental to the successes of deep learning. However, it requires sequential backwards updates and non-local computations which make it challenging to parallelize at scale and is unlike how learning works in the brain. Neuroscience-inspired learning algorithms, however, such as \emph{predictive coding} which utilize local learning have the potential to overcome these limitations and advance beyond deep learning technologies in the future. While predictive coding originated in theoretical neuroscience as a model of information processing in the cortex, recent work has developed the idea into a general-purpose algorithm able to train neural networks using only local computations. In this survey, we review works that have contributed to this perspective and demonstrate the close connection between predictive coding and backpropagation in terms of generalization quality, as well as works that highlight the multiple advantages of using predictive coding models over backprop-trained neural networks. Specifically, we show the substantially greater flexibility of predictive coding networks against equivalent deep neural networks, which can function as classifiers, generators, and associative memories simultaneously, and can be defined on arbitrary graph topologies. Finally, we review direct benchmarks of predictive coding networks on machine learning classification tasks, as well as its close connections to control theory and applications in robotics.

AAAI Conference 2022 Conference Paper

Reverse Differentiation via Predictive Coding

• Tommaso Salvatori
• Yuhang Song
• Zhenghua Xu
• Thomas Lukasiewicz
• Rafal Bogacz

Deep learning has redefined AI thanks to the rise of artificial neural networks, which are inspired by neuronal networks in the brain. Through the years, these interactions between AI and neuroscience have brought immense benefits to both fields, allowing neural networks to be used in a plethora of applications. Neural networks use an efficient implementation of reverse differentiation, called backpropagation (BP). This algorithm, however, is often criticized for its biological implausibility (e. g. , lack of local update rules for the parameters). Therefore, biologically plausible learning methods that rely on predictive coding (PC), a framework for describing information processing in the brain, are increasingly studied. Recent works prove that these methods can approximate BP up to a certain margin on multilayer perceptrons (MLPs), and asymptotically on any other complex model, and that zerodivergence inference learning (Z-IL), a variant of PC, is able to exactly implement BP on MLPs. However, the recent literature shows also that there is no biologically plausible method yet that can exactly replicate the weight update of BP on complex models. To fill this gap, in this paper, we generalize (PC and) Z-IL by directly defining it on computational graphs, and show that it can perform exact reverse differentiation. What results is the first PC (and so biologically plausible) algorithm that is equivalent to BP in the way of updating parameters on any neural network, providing a bridge between the interdisciplinary research of neuroscience and deep learning. Furthermore, the above results in particular also immediately provide a novel local and parallel implementation of BP.

ICML Conference 2022 Conference Paper

Universal Hopfield Networks: A General Framework for Single-Shot Associative Memory Models

• Beren Millidge
• Tommaso Salvatori
• Yuhang Song 0001
• Thomas Lukasiewicz
• Rafal Bogacz

A large number of neural network models of associative memory have been proposed in the literature. These include the classical Hopfield networks (HNs), sparse distributed memories (SDMs), and more recently the modern continuous Hopfield networks (MCHNs), which possess close links with self-attention in machine learning. In this paper, we propose a general framework for understanding the operation of such memory networks as a sequence of three operations: similarity, separation, and projection. We derive all these memory models as instances of our general framework with differing similarity and separation functions. We extend the mathematical framework of Krotov et al (2020) to express general associative memory models using neural network dynamics with local computation, and derive a general energy function that is a Lyapunov function of the dynamics. Finally, using our framework, we empirically investigate the capacity of using different similarity functions for these associative memory models, beyond the dot product similarity measure, and demonstrate empirically that Euclidean or Manhattan distance similarity metrics perform substantially better in practice on many tasks, enabling a more robust retrieval and higher memory capacity than existing models.

NeurIPS Conference 2021 Conference Paper

Associative Memories via Predictive Coding

• Tommaso Salvatori
• Yuhang Song
• Yujian Hong
• Lei Sha
• Simon Frieder
• Zhenghua Xu
• Rafal Bogacz
• Thomas Lukasiewicz

Associative memories in the brain receive and store patterns of activity registered by the sensory neurons, and are able to retrieve them when necessary. Due to their importance in human intelligence, computational models of associative memories have been developed for several decades now. In this paper, we present a novel neural model for realizing associative memories, which is based on a hierarchical generative network that receives external stimuli via sensory neurons. It is trained using predictive coding, an error-based learning algorithm inspired by information processing in the cortex. To test the model's capabilities, we perform multiple retrieval experiments from both corrupted and incomplete data points. In an extensive comparison, we show that this new model outperforms in retrieval accuracy and robustness popular associative memory models, such as autoencoders trained via backpropagation, and modern Hopfield networks. In particular, in completing partial data points, our model achieves remarkable results on natural image datasets, such as ImageNet, with a surprisingly high accuracy, even when only a tiny fraction of pixels of the original images is presented. Our model provides a plausible framework to study learning and retrieval of memories in the brain, as it closely mimics the behavior of the hippocampus as a memory index and generative model.

AAAI Conference 2021 Conference Paper

Learning from the Best: Rationalizing Predictions by Adversarial Information Calibration

• Lei Sha
• Oana-Maria Camburu
• Thomas Lukasiewicz

Explaining the predictions of AI models is paramount in safety-critical applications, such as in legal or medical domains. One form of explanation for a prediction is an extractive rationale, i. e. , a subset of features of an instance that lead the model to give its prediction on the instance. Previous works on generating extractive rationales usually employ a two-phase model: a selector that selects the most important features (i. e. , the rationale) followed by a predictor that makes the prediction based exclusively on the selected features. One disadvantage of these works is that the main signal for learning to select features comes from the comparison of the answers given by the predictor and the ground-truth answers. In this work, we propose to squeeze more information from the predictor via an information calibration method. More precisely, we train two models jointly: one is a typical neural model that solves the task at hand in an accurate but black-box manner, and the other is a selector-predictor model that additionally produces a rationale for its prediction. The first model is used as a guide to the second model. We use an adversarial-based technique to calibrate the information extracted by the two models such that the difference between them is an indicator of the missed or over-selected features. In addition, for natural language tasks, we propose to use a language-model-based regularizer to encourage the extraction of fluent rationales. Experimental results on a sentiment analysis task as well as on three tasks from the legal domain show the effectiveness of our approach to rationale extraction.

JAIR Journal 2021 Journal Article

Multi-Label Classification Neural Networks with Hard Logical Constraints

• Eleonora Giunchiglia
• Thomas Lukasiewicz

Multi-label classification (MC) is a standard machine learning problem in which a data point can be associated with a set of classes. A more challenging scenario is given by hierarchical multi-label classification (HMC) problems, in which every prediction must satisfy a given set of hard constraints expressing subclass relationships between classes. In this article, we propose C-HMCNN(h), a novel approach for solving HMC problems, which, given a network h for the underlying MC problem, exploits the hierarchy information in order to produce predictions coherent with the constraints and to improve performance. Furthermore, we extend the logic used to express HMC constraints in order to be able to specify more complex relations among the classes and propose a new model CCN(h), which extends C-HMCNN(h) and is again able to satisfy and exploit the constraints to improve performance. We conduct an extensive experimental analysis showing the superior performance of both C-HMCNN(h) and CCN(h) when compared to state-of-the-art models in both the HMC and the general MC setting with hard logical constraints.

AAAI Conference 2021 Conference Paper

Multi-type Disentanglement without Adversarial Training

• Lei Sha
• Thomas Lukasiewicz

Controlling the style of natural language by disentangling the latent space is an important step towards interpretable machine learning. After the latent space is disentangled, the style of a sentence can be transformed by tuning the style representation without affecting other features of the sentence. Previous works usually use adversarial training to guarantee that disentangled vectors do not affect each other. However, adversarial methods are difficult to train. Especially when there are multiple features (e. g. , sentiment, or tense, which we call style types in this paper), each feature requires a separate discriminator for extracting a disentangled style vector corresponding to that feature. In this paper, we propose a unified distribution-controlling method, which provides each specific style value (the value of style types, e. g. , positive sentiment, or past tense) with a unique representation. This method contributes a solid theoretical basis to avoid adversarial training in multi-type disentanglement. We also propose multiple loss functions to achieve a style-content disentanglement as well as a disentanglement among multiple style types. In addition, we observe that if two different style types always have some specific style values that occur together in the dataset, they will affect each other when transferring the style values. We call this phenomenon training bias, and we propose a loss function to alleviate such training bias while disentangling multiple types. We conduct experiments on two datasets (Yelp service reviews and Amazon product reviews) to evaluate the style-disentangling effect and the unsupervised styletransfer performance on two style types: sentiment and tense. The experimental results show the effectiveness of our model.

AAAI Conference 2021 Conference Paper

Preferred Explanations for Ontology-Mediated Queries under Existential Rules

• İsmail İlkan Ceylan
• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro
• Andrius Vaicenavičius

Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.

AAAI Conference 2021 Conference Paper

The Gap on Gap: Tackling the Problem of Differing Data Distributions in Bias-Measuring Datasets

• Vid Kocijan
• Oana-Maria Camburu
• Thomas Lukasiewicz

Diagnostic datasets that can detect biased models are an important prerequisite for bias reduction within natural language processing. However, undesired patterns in the collected data can make such tests incorrect. For example, if the feminine subset of a gender-bias-measuring coreference resolution dataset contains sentences with a longer average distance between the pronoun and the correct candidate, an RNNbased model may perform worse on this subset due to longterm dependencies. In this work, we introduce a theoretically grounded method for weighting test samples to cope with such patterns in the test data. We demonstrate the method on the GAP dataset for coreference resolution. We annotate GAP with spans of all personal names and show that examples in the female subset contain more personal names and a longer distance between pronouns and their referents, potentially affecting the bias score in an undesired way. Using our weighting method, we find the set of weights on the test instances that should be used for coping with these correlations, and we re-evaluate 16 recently released coreference models. 1

IJCAI Conference 2021 Conference Paper

The Surprising Power of Graph Neural Networks with Random Node Initialization

• Ralph Abboud
• İsmail İlkan Ceylan
• Martin Grohe
• Thomas Lukasiewicz

Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.

AAAI Conference 2020 Conference Paper

Arena: A General Evaluation Platform and Building Toolkit for Multi-Agent Intelligence

• Yuhang Song
• Andrzej Wojcicki
• Thomas Lukasiewicz
• Jianyi Wang
• Abi Aryan
• Zhenghua Xu
• Mai Xu
• Zihan Ding

Learning agents that are not only capable of taking tests, but also innovating is becoming a hot topic in AI. One of the most promising paths towards this vision is multi-agent learning, where agents act as the environment for each other, and improving each agent means proposing new problems for others. However, existing evaluation platforms are either not compatible with multi-agent settings, or limited to a specific game. That is, there is not yet a general evaluation platform for research on multi-agent intelligence. To this end, we introduce Arena, a general evaluation platform for multi-agent intelligence with 35 games of diverse logics and representations. Furthermore, multi-agent intelligence is still at the stage where many problems remain unexplored. Therefore, we provide a building toolkit for researchers to easily invent and build novel multi-agent problems from the provided game set based on a GUI-configurable social tree and five basic multi-agent reward schemes. Finally, we provide Python implementations of five state-of-the-art deep multi-agent reinforcement learning baselines. Along with the baseline implementations, we release a set of 100 best agents/teams that we can train with different training schemes for each game, as the base for evaluating agents with population performance. As such, the research community can perform comparisons under a stable and uniform standard. All the implementations and accompanied tutorials have been open-sourced for the community at https: //sites. google. com/view/arena-unity/.

NeurIPS Conference 2020 Conference Paper

BoxE: A Box Embedding Model for Knowledge Base Completion

• Ralph Abboud
• Ismail Ceylan
• Thomas Lukasiewicz
• Tommaso Salvatori

Knowledge base completion (KBC) aims to automatically infer missing facts by exploiting information already present in a knowledge base (KB). A promising approach for KBC is to embed knowledge into latent spaces and make predictions from learned embeddings. However, existing embedding models are subject to at least one of the following limitations: (1) theoretical inexpressivity, (2) lack of support for prominent inference patterns (e. g. , hierarchies), (3) lack of support for KBC over higher-arity relations, and (4) lack of support for incorporating logical rules. Here, we propose a spatio-translational embedding model, called BoxE, that simultaneously addresses all these limitations. BoxE embeds entities as points, and relations as a set of hyper-rectangles (or boxes), which spatially characterize basic logical properties. This seemingly simple abstraction yields a fully expressive model offering a natural encoding for many desired logical properties. BoxE can both capture and inject rules from rich classes of rule languages, going well beyond individual inference patterns. By design, BoxE naturally applies to higher-arity KBs. We conduct a detailed experimental analysis, and show that BoxE achieves state-of-the-art performance, both on benchmark knowledge graphs and on more general KBs, and we empirically show the power of integrating logical rules.

NeurIPS Conference 2020 Conference Paper

Can the Brain Do Backpropagation? --- Exact Implementation of Backpropagation in Predictive Coding Networks

• Yuhang Song
• Thomas Lukasiewicz
• Zhenghua Xu
• Rafal Bogacz

Backpropagation (BP) has been the most successful algorithm used to train artificial neural networks. However, there are several gaps between BP and learning in biologically plausible neuronal networks of the brain (learning in the brain, or simply BL, for short), in particular, (1) it has been unclear to date, if BP can be implemented exactly via BL, (2) there is a lack of local plasticity in BP, i. e. , weight updates require information that is not locally available, while BL utilizes only locally available information, and (3)~there is a lack of autonomy in BP, i. e. , some external control over the neural network is required (e. g. , switching between prediction and learning stages requires changes to dynamics and synaptic plasticity rules), while BL works fully autonomously. Bridging such gaps, i. e. , understanding how BP can be approximated by BL, has been of major interest in both neuroscience and machine learning. Despite tremendous efforts, however, no previous model has bridged the gaps at a degree of demonstrating an equivalence to BP, instead, only approximations to BP have been shown. Here, we present for the first time a framework within BL that bridges the above crucial gaps. We propose a BL model that (1) produces \emph{exactly the same} updates of the neural weights as~BP, while (2)~employing local plasticity, i. e. , all neurons perform only local computations, done simultaneously. We then modify it to an alternative BL model that (3) also works fully autonomously. Overall, our work provides important evidence for the debate on the long-disputed question whether the brain can perform~BP.

NeurIPS Conference 2020 Conference Paper

Coherent Hierarchical Multi-Label Classification Networks

• Eleonora Giunchiglia
• Thomas Lukasiewicz

Hierarchical multi-label classification (HMC) is a challenging classification task extending standard multi-label classification problems by imposing a hierarchy constraint on the classes. In this paper, we propose C-HMCNN(h), a novel approach for HMC problems, which, given a network h for the underlying multi-label classification problem, exploits the hierarchy information in order to produce predictions coherent with the constraint and improve performance. We conduct an extensive experimental analysis showing the superior performance of C-HMCNN(h) when compared to state-of-the-art models.

AAAI Conference 2020 Conference Paper

Explanations for Inconsistency-Tolerant Query Answering under Existential Rules

• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro

Querying inconsistent knowledge bases is a problem that has attracted a great deal of interest over the last decades. While several semantics of query answering have been proposed, and their complexity is rather well-understood, little attention has been paid to the problem of explaining query answers. Explainability has recently become a prominent problem in different areas of AI. In particular, explaining query answers allows users to understand not only what is entailed by an inconsistent knowledge base, but also why. In this paper, we address the problem of explaining query answers for existential rules under three popular inconsistency-tolerant semantics, namely, the ABox repair, the intersection of repairs, and the intersection of closed repairs semantics. We provide a thorough complexity analysis for a wide range of existential rule languages and for different complexity measures.

KR Conference 2020 Conference Paper

Explanations for Negative Query Answers under Existential Rules

• İsmail İlkan Ceylan
• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro
• Andrius Vaicenavičius

Ontology-mediated query answering is an extensively studied paradigm, where the conceptual knowledge provided by an ontology is leveraged towards more enhanced querying of data sources. A major advantage of ontological reasoning is its interpretability, which allows one to derive explanations for query answers. Indeed, explanations have a long history in knowledge representation, and have also been investigated for ontology languages based on description logics and existential rules. Existing works on existential rules, however, merely focus on understanding why a query is entailed, i. e. , explaining positive query answers. In this paper, we continue this line of research and address another important problem, namely, explaining why a query is not entailed under existential rules, i. e. , explaining negative query answers. We consider various problems related to explaining non-entailments from the abduction literature, and also introduce new problems. For all considered problems, we give a detailed complexity analysis for a wide range of existential rule languages and complexity measures.

ECAI Conference 2020 Conference Paper

Explanations for Ontology-Mediated Query Answering in Description Logics

• Ismail Ilkan Ceylan
• Thomas Lukasiewicz
• Enrico Malizia
• Andrius Vaicenavicius

Ontology-mediated query answering is a paradigm that seeks to exploit the semantic knowledge expressed in terms of ontologies to improve query answers over incomplete data sources. In this paper, we focus on description logic ontologies, and study the problem of explaining why an ontology-mediated query is entailed from a given data source. Specifically, we view explanations as minimal sets of assertions from an ABox, which satisfy the ontology-mediated query. Based on such explanations, we study a variety of problems taken from the recent literature on explanations (studied for existential rules), such as recognizing all minimal explanations. Our results establish tight connections between intractable explanation problems and variants of propositional satisfiability problems. We provide insights on the inherent computational difficulty of deriving explanations for ontology-mediated queries.

AAAI Conference 2020 Conference Paper

Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting

• Ralph Abboud
• Ismail Ceylan
• Thomas Lukasiewicz

Weighted model counting (WMC) has emerged as a prevalent approach for probabilistic inference. In its most general form, WMC is #P-hard. Weighted DNF counting (weighted #DNF) is a special case, where approximations with probabilistic guarantees are obtained in O(nm), where n denotes the number of variables, and m the number of clauses of the input DNF, but this is not scalable in practice. In this paper, we propose a neural model counting approach for weighted #DNF that combines approximate model counting with deep learning, and accurately approximates model counts in linear time when width is bounded. We conduct experiments to validate our method, and show that our model learns and generalizes very well to large-scale #DNF instances.

NeurIPS Conference 2020 Conference Paper

Lightweight Generative Adversarial Networks for Text-Guided Image Manipulation

• Bowen Li
• Xiaojuan Qi
• Philip Torr
• Thomas Lukasiewicz

We propose a novel lightweight generative adversarial network for efficient image manipulation using natural language descriptions. To achieve this, a new word-level discriminator is proposed, which provides the generator with fine-grained training feedback at word-level, to facilitate training a lightweight generator that has a small number of parameters, but can still correctly focus on specific visual attributes of an image, and then edit them without affecting other contents that are not described in the text. Furthermore, thanks to the explicit training signal related to each word, the discriminator can also be simplified to have a lightweight structure. Compared with the state of the art, our method has a much smaller number of parameters, but still achieves a competitive manipulation performance. Extensive experimental results demonstrate that our method can better disentangle different visual attributes, then correctly map them to corresponding semantic words, and thus achieve a more accurate image modification using natural language descriptions.

AAAI Conference 2020 Conference Paper

Mega-Reward: Achieving Human-Level Play without Extrinsic Rewards

• Yuhang Song
• Jianyi Wang
• Thomas Lukasiewicz
• Zhenghua Xu
• Shangtong Zhang
• Andrzej Wojcicki
• Mai Xu

Intrinsic rewards were introduced to simulate how human intelligence works; they are usually evaluated by intrinsicallymotivated play, i. e. , playing games without extrinsic rewards but evaluated with extrinsic rewards. However, none of the existing intrinsic reward approaches can achieve humanlevel performance under this very challenging setting of intrinsically-motivated play. In this work, we propose a novel megalomania-driven intrinsic reward (called mega-reward), which, to our knowledge, is the first approach that achieves human-level performance in intrinsically-motivated play. Intuitively, mega-reward comes from the observation that infants’ intelligence develops when they try to gain more control on entities in an environment; therefore, mega-reward aims to maximize the control capabilities of agents on given entities in a given environment. To formalize mega-reward, a relational transition model is proposed to bridge the gaps between direct and latent control. Experimental studies show that mega-reward (i) can greatly outperform all state-ofthe-art intrinsic reward approaches, (ii) generally achieves the same level of performance as Ex-PPO and professional human-level scores, and (iii) has also a superior performance when it is incorporated with extrinsic rewards.

JAIR Journal 2020 Journal Article

Ontology Reasoning with Deep Neural Networks

• Patrick Hohenecker
• Thomas Lukasiewicz

The ability to conduct logical reasoning is a fundamental aspect of intelligent human behavior, and thus an important problem along the way to human-level artificial intelligence. Traditionally, logic-based symbolic methods from the field of knowledge representation and reasoning have been used to equip agents with capabilities that resemble human logical reasoning qualities. More recently, however, there has been an increasing interest in using machine learning rather than logic-based symbolic formalisms to tackle these tasks. In this paper, we employ state-of-the-art methods for training deep neural networks to devise a novel model that is able to learn how to effectively perform logical reasoning in the form of basic ontology reasoning. This is an important and at the same time very natural logical reasoning task, which is why the presented approach is applicable to a plethora of important real-world problems. We present the outcomes of several experiments, which show that our model is able to learn to perform highly accurate ontology reasoning on very large, diverse, and challenging benchmarks. Furthermore, it turned out that the suggested approach suffers much less from different obstacles that prohibit logic-based symbolic reasoning, and, at the same time, is surprisingly plausible from a biological point of view.

IJCAI Conference 2020 Conference Paper

Ontology Reasoning with Deep Neural Networks (Extended Abstract)

• Patrick Hohenecker
• Thomas Lukasiewicz

The ability to conduct logical reasoning is a fundamental aspect of intelligent human behavior, and thus an important problem along the way to human-level artificial intelligence. Traditionally, logic-based symbolic methods from the field of knowledge representation and reasoning have been used to equip agents with capabilities that resemble human logical reasoning qualities. More recently, however, there has been an increasing interest in using machine learning rather than logic-based symbolic formalisms to tackle these tasks. In this paper, we employ state-of-the-art methods for training deep neural networks to devise a novel model that is able to learn how to effectively perform logical reasoning in the form of basic ontology reasoning.

AAAI Conference 2019 Conference Paper

Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Cardinality-Based Repairs

• Thomas Lukasiewicz
• Enrico Malizia
• Andrius Vaicenavičius

Querying inconsistent ontological knowledge bases is an important problem in practice, for which several inconsistencytolerant query answering semantics have been proposed, including query answering relative to all repairs, relative to the intersection of repairs, and relative to the intersection of closed repairs. In these semantics, one assumes that the input database is erroneous, and the notion of repair describes a maximally consistent subset of the input database, where different notions of maximality (such as subset and cardinality maximality) are considered. In this paper, we give a precise picture of the computational complexity of inconsistencytolerant (Boolean conjunctive) query answering in a wide range of Datalog± languages under the cardinality-based versions of the above three repair semantics.

AIJ Journal 2019 Journal Article

Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting

• Thomas Lukasiewicz
• Enrico Malizia

Aggregating preferences over combinatorial domains has many applications in artificial intelligence (AI). Given the inherent exponential nature of preferences over combinatorial domains, compact representation languages are needed to represent them, and (m)CP-nets are among the most studied ones. Sequential and global voting are two different ways of aggregating preferences represented via CP-nets. In sequential voting, agents' preferences are aggregated feature-by-feature. For this reason, sequential voting may exhibit voting paradoxes, i. e. , the possibility to select sub-optimal outcomes when preferences have specific feature dependencies. To avoid paradoxes in sequential voting, one has often assumed the (quite) restrictive constraint of O -legality, which imposes a shared common topological order among all the agents' CP-nets. On the contrary, in global voting, CP-nets are considered as a whole during the preference aggregation process. For this reason, global voting is immune from the voting paradoxes of sequential voting, and hence there is no need to impose restrictions over the CP-nets' structure when preferences are aggregated via global voting. Sequential voting over O -legal CP-nets received much attention, and O -legality of CP-nets has often been required in other studies. On the other hand, global voting over non- O -legal CP-nets has not carefully been analyzed, despite it was explicitly stated in the literature that a theoretical comparison between global and sequential voting was highly promising and a precise complexity analysis for global voting has been asked for multiple times. In quite a few works, only very partial results on the complexity of global voting over CP-nets have been given. In this paper, we start to fill this gap by carrying out a thorough computational complexity analysis of global voting tasks, for Pareto and majority voting, over not necessarily O -legal acyclic binary polynomially connected (m)CP-nets. We show that all these problems belong to various levels of the polynomial hierarchy, and some of them are even in P or LOGSPACE. Our results are a notable achievement, given that the previously known upper bound for most of these problems was the complexity class EXPTIME. We provide various exact complexity results showing tight lower bounds and matching upper bounds for problems that (up to now) did not have any explicit non-obvious lower bound.

NeurIPS Conference 2019 Conference Paper

Controllable Text-to-Image Generation

• Bowen Li
• Xiaojuan Qi
• Thomas Lukasiewicz
• Philip Torr

In this paper, we propose a novel controllable text-to-image generative adversarial network (ControlGAN), which can effectively synthesise high-quality images and also control parts of the image generation according to natural language descriptions. To achieve this, we introduce a word-level spatial and channel-wise attention-driven generator that can disentangle different visual attributes, and allow the model to focus on generating and manipulating subregions corresponding to the most relevant words. Also, a word-level discriminator is proposed to provide fine-grained supervisory feedback by correlating words with image regions, facilitating training an effective generator which is able to manipulate specific visual attributes without affecting the generation of other content. Furthermore, perceptual loss is adopted to reduce the randomness involved in the image generation, and to encourage the generator to manipulate specific attributes required in the modified text. Extensive experiments on benchmark datasets demonstrate that our method outperforms existing state of the art, and is able to effectively manipulate synthetic images using natural language descriptions.

AAAI Conference 2019 Conference Paper

Diversity-Driven Extensible Hierarchical Reinforcement Learning

• Yuhang Song
• Jianyi Wang
• Thomas Lukasiewicz
• Zhenghua Xu
• Mai Xu

Hierarchical reinforcement learning (HRL) has recently shown promising advances on speeding up learning, improving the exploration, and discovering intertask transferable skills. Most recent works focus on HRL with two levels, i. e. , a master policy manipulates subpolicies, which in turn manipulate primitive actions. However, HRL with multiple levels is usually needed in many real-world scenarios, whose ultimate goals are highly abstract, while their actions are very primitive. Therefore, in this paper, we propose a diversitydriven extensible HRL (DEHRL), where an extensible and scalable framework is built and learned levelwise to realize HRL with multiple levels. DEHRL follows a popular assumption: diverse subpolicies are useful, i. e. , subpolicies are believed to be more useful if they are more diverse. However, existing implementations of this diversity assumption usually have their own drawbacks, which makes them inapplicable to HRL with multiple levels. Consequently, we further propose a novel diversity-driven solution to achieve this assumption in DEHRL. Experimental studies evaluate DEHRL with nine baselines from four perspectives in two domains; the results show that DEHRL outperforms the state-of-the-art baselines in all four aspects.

IJCAI Conference 2019 Conference Paper

Explanations for Query Answers under Existential Rules

• İsmail İlkan Ceylan
• Thomas Lukasiewicz
• Enrico Malizia
• Andrius Vaicenavičius

Ontology-mediated query answering is an extensively studied paradigm, which aims at improving query answers with the use of a logical theory. As a form of logical entailment, ontology-mediated query answering is fully interpretable, which makes it possible to derive explanations for query answers. Surprisingly, however, explaining answers for ontology-mediated queries has received little attention for ontology languages based on existential rules. In this paper, we close this gap, and study the problem of explaining query answers in terms of minimal subsets of database facts. We provide a thorough complexity analysis for several decision problems associated with minimal explanations under existential rules.

AAAI Conference 2019 Conference Paper

Ontology-Mediated Query Answering over Log-Linear Probabilistic Data

• Stefan Borgwardt
• İsmail İlkan Ceylan
• Thomas Lukasiewicz

Large-scale knowledge bases are at the heart of modern information systems. Their knowledge is inherently uncertain, and hence they are often materialized as probabilistic databases. However, probabilistic database management systems typically lack the capability to incorporate implicit background knowledge and, consequently, fail to capture some intuitive query answers. Ontology-mediated query answering is a popular paradigm for encoding commonsense knowledge, which can provide more complete answers to user queries. We propose a new data model that integrates the paradigm of ontology-mediated query answering with probabilistic databases, employing a log-linear probability model. We compare our approach to existing proposals, and provide supporting computational results.

IJCAI Conference 2018 Conference Paper

Complexity of Approximate Query Answering under Inconsistency in Datalog+/-

• Thomas Lukasiewicz
• Enrico Malizia
• Cristian Molinaro

Several semantics have been proposed to query inconsistent ontological knowledge bases, including the intersection of repairs and the intersection of closed repairs as two approximate inconsistency-tolerant semantics. In this paper, we analyze the complexity of conjunctive query answering under these two semantics for a wide range of Datalog+/- languages. We consider both the standard setting, where errors may only be in the database, and the generalized setting, where also the rules of a Datalog+/- knowledge base may be erroneous.

NeurIPS Conference 2018 Conference Paper

e-SNLI: Natural Language Inference with Natural Language Explanations

• Oana-Maria Camburu
• Tim Rocktäschel
• Thomas Lukasiewicz
• Phil Blunsom

In order for machine learning to garner widespread public adoption, models must be able to provide interpretable and robust explanations for their decisions, as well as learn from human-provided explanations at train time. In this work, we extend the Stanford Natural Language Inference dataset with an additional layer of human-annotated natural language explanations of the entailment relations. We further implement models that incorporate these explanations into their training process and output them at test time. We show how our corpus of explanations, which we call e-SNLI, can be used for various goals, such as obtaining full sentence justifications of a model’s decisions, improving universal sentence representations and transferring to out-of-domain NLI datasets. Our dataset thus opens up a range of research directions for using natural language explanations, both for improving models and for asserting their trust

IJCAI Conference 2018 Conference Paper

Recent Advances in Querying Probabilistic Knowledge Bases

• Stefan Borgwardt
• İsmail İlkan Ceylan
• Thomas Lukasiewicz

We give a survey on recent advances at the forefront of research on probabilistic knowledge bases for representing and querying large-scale automatically extracted data. We concentrate especially on increasing the semantic expressivity of formalisms for representing and querying probabilistic knowledge (i) by giving up the closed-world assumption, (ii) by allowing for commonsense knowledge (and in parallel giving up the tuple-independence assumption), and (iii) by giving up the closed-domain assumption, while preserving some computational properties of query answering in such formalisms.

TCS Journal 2017 Journal Article

A novel characterization of the complexity class Θ k P based on counting and comparison

• Thomas Lukasiewicz
• Enrico Malizia

The complexity class Θ 2 P, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e. g. , whether its size is an odd number). In this paper, we introduce a new characterization of this class and its generalization Θ k P to the k-th level of the polynomial hierarchy. We show that problems in Θ k P are also those whose solution involves deciding, for two given sets A and B of instances of two Σ k − 1 P -complete (or Π k − 1 P -complete) problems, whether the number of “yes”-instances in A is greater than those in B. Moreover, based on this new characterization, we provide a novel sufficient condition for Θ k P -hardness. We also define the general problem Comp-Valid k, which is proven here Θ k + 1 P -complete. Comp-Valid k is the problem of deciding, given two sets A and B of quantified Boolean formulas with at most k alternating quantifiers, whether the number of valid formulas in A is greater than those in B. Notably, the problem Comp-Sat of deciding whether a set contains more satisfiable Boolean formulas than another set, which is a particular case of Comp-Valid 1, demonstrates itself as a very intuitive Θ 2 P -complete problem. Nonetheless, to our knowledge, it eluded its formal definition to date. In fact, given its strict adherence to the count-and-compare semantics here introduced, Comp-Valid k is among the most suitable tools to prove Θ k P -hardness of problems involving the counting and comparison of the number of “yes”-instances in two sets. We support this by showing that the Θ 2 P -hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ k P introduced in this paper.

IJCAI Conference 2017 Conference Paper

Most Probable Explanations for Probabilistic Database Queries

• İsmail İlkan Ceylan
• Stefan Borgwardt
• Thomas Lukasiewicz

Forming the foundations of large-scale knowledge bases, probabilistic databases have been widely studied in the literature. In particular, probabilistic query evaluation has been investigated intensively as a central inference mechanism. However, despite its power, query evaluation alone cannot extract all the relevant information encompassed in large-scale knowledge bases. To exploit this potential, we study two inference tasks; namely finding the most probable database and the most probable hypothesis for a given query. As natural counterparts of most probable explanations (MPE) and maximum a posteriori hypotheses (MAP) in probabilistic graphical models, they can be used in a variety of applications that involve prediction or diagnosis tasks. We investigate these problems relative to a variety of query languages, ranging from conjunctive queries to ontology-mediated queries, and provide a detailed complexity analysis.

AAAI Conference 2017 Conference Paper

Ontology-Mediated Queries for Probabilistic Databases

• Stefan Borgwardt
• Ismail Ceylan
• Thomas Lukasiewicz

Probabilistic databases (PDBs) are usually incomplete, e. g. , containing only the facts that have been extracted from the Web with high confidence. However, missing facts are often treated as being false, which leads to unintuitive results when querying PDBs. Recently, open-world probabilistic databases (OpenPDBs) were proposed to address this issue by allowing probabilities of unknown facts to take any value from a fixed probability interval. In this paper, we extend Open- PDBs by Datalog± ontologies, under which both upper and lower probabilities of queries become even more informative, enabling us to distinguish queries that were indistinguishable before. We show that the dichotomy between P and PP in (Open)PDBs can be lifted to the case of first-order rewritable positive programs (without negative constraints); and that the problem can become NPPP -complete, once negative constraints are allowed. We also propose an approximating semantics that circumvents the increase in complexity caused by negative constraints.

FLAP Journal 2017 Journal Article

Preface to the Speical Issue on Reasoning about Preferences, Uncertainty, and Vagueness.

• Thomas Lukasiewicz
• Rafael Peñaloza
• Anni-Yasmin Turhan

IJCAI Conference 2017 Conference Paper

Query Answering in Ontologies under Preference Rankings

• İsmail İlkan Ceylan
• Thomas Lukasiewicz
• Rafael Peñaloza
• Oana Tifrea-Marciuska

We present an ontological framework, based on preference rankings, that allows users to express their preferences between the knowledge explicitly available in the ontology. Using this formalism, the answers for a given query to an ontology can be ranked by preference, allowing users to retrieve the most preferred answers only. We provide a host of complexity results for the main computational tasks in this framework, for the general case, and for EL and DL-Lite_core as underlying ontology languages.

IJCAI Conference 2017 Conference Paper

Tag-Aware Personalized Recommendation Using a Hybrid Deep Model

• Zhenghua Xu
• Thomas Lukasiewicz
• Cheng Chen
• Yishu Miao
• Xiangwu Meng

Recently, many efforts have been put into tag-aware personalized recommendation. However, due to uncontrolled vocabularies, social tags are usually redundant, sparse, and ambiguous. In this paper, we propose a deep neural network approach to solve this problem by mapping the tag-based user and item profiles to an abstract deep feature space, where the deep-semantic similarities between users and their target items (resp. , irrelevant items) are maximized (resp. , minimized). To ensure the scalability in practice, we further propose to improve this model's training efficiency by using hybrid deep learning and negative sampling. Experimental results show that our approach can significantly outperform the state-of-the-art baselines in tag-aware personalized recommendation (3. 8 times better than the best baseline), and that using hybrid deep learning and negative sampling can dramatically enhance the model's training efficiency (hundreds of times quicker), while maintaining similar (and sometimes even better) training quality and recommendation performance.

AAAI Conference 2016 Conference Paper

Basic Probabilistic Ontological Data Exchange with Existential Rules

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Livia Predoiu
• Gerardo I. Simari

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.

ECAI Conference 2016 Conference Paper

Complexity of Threshold Query Answering in Probabilistic Ontological Data Exchange

• Thomas Lukasiewicz
• Livia Predoiu

We study the complexity of threshold query answering in the logical framework for probabilistic ontological data exchange, which is an extension of the classical probabilistic data exchange framework with (1) probabilistic databases compactly encoded with several different annotations according to three different probability models used and (2) existential rules of different expressiveness. The ontological data exchange framework provides a logical formalization of exchanging probabilistic data and knowledge from one ontology to another via either deterministic or probabilistic mappings. We define the threshold query answering task in this framework and provide a thorough analysis of its computational complexity for different classes of existential rules and types of complexity. We also delineate several classes of existential rules and a probability model along with a compact encoding in which the threshold query answering problem can be solved in polynomial time in the data complexity.

ECAI Conference 2016 Conference Paper

Complexity Results for Probabilistic Datalog ±

• Ismail Ilkan Ceylan
• Thomas Lukasiewicz
• Rafael Peñaloza

We study the query evaluation problem in probabilistic databases in the presence of probabilistic existential rules. Our focus is on the Datalog± family of languages for which we define the probabilistic counterpart using a flexible and compact encoding of probabilities. This formalism can be viewed as a generalization of probabilistic databases, as it allows to generate new facts from the given ones, using so-called tuple-generating dependencies, or existential rules. We study the computational cost of this additional expressiveness under two different semantics. First, we use a conventional approach and assume that the probabilistic knowledge base is consistent and employ the standard possible world semantics. Thereafter, we introduce a probabilistic inconsistency-tolerant semantics, which we call inconsistency-tolerant possible world semantics. For both of these cases, we provide a thorough complexity analysis relative to different languages, drawing a complete picture of the complexity of probabilistic query answering in this family.

KR Conference 2016 Conference Paper

Generalized Consistent Query Answering under Existential Rules

• Thomas Eiter
• Thomas Lukasiewicz
• Livia Predoiu

Previous work has proposed consistent query answering as a way to resolve inconsistencies in ontologies. In these approaches to consistent query answering, however, only inconsistencies due to errors in the underlying database are considered. In this paper, we additionally assume that ontological axioms may be erroneous, and that some database atoms and ontological axioms may not be removed to resolve inconsistencies. This problem is especially well-suited in debugging mappings between distributed ontologies. We define two different semantics, one where ontological axioms as a whole are ignored to resolve an inconsistency, and one where only some of their instances are ignored. We then give a precise picture of the complexity of consistent query answering under these two semantics when ontological axioms are encoded as different classes of existential rules. In the course of this, we also close two open complexity problems in standard consistent query answering under existential rules.

AAAI Conference 2016 Conference Paper

On the Complexity of mCP-nets

• Thomas Lukasiewicz
• Enrico Malizia

mCP-nets are an expressive and intuitive formalism based on CP-nets to reason about preferences of groups of agents. The dominance semantics of mCP-nets is based on the concept of voting, and different voting schemes give rise to different dominance semantics for the group. Unlike CP-nets, which received an extensive complexity analysis, mCP-nets, as reported multiple times in the literature, lack a precise study of the voting tasks’ complexity. Prior to this work, only a complexity analysis of brute-force algorithms for these tasks was available, and this analysis only gave EXPTIME upper bounds for most of those problems. In this paper, we start to fill this gap by carrying out a precise computational complexity analysis of voting tasks on acyclic binary polynomially connected mCP-nets whose constituents are standard CP-nets. Interestingly, all these problems actually belong to various levels of the polynomial hierarchy, and some of them even belong to PTIME or LOGSPACE. Furthermore, for most of these problems, we provide completeness results, which show tight lower bounds for problems that (up to date) did not have any explicit non-obvious lower bound.

IJCAI Conference 2016 Conference Paper

Preferential Query Answering over the Semantic Web with Possibilistic Networks

• Stefan Borgwardt
• Bettina Fazzinga
• Thomas Lukasiewicz
• Akanksha Shrivastava
• Oana Tifrea-Marciuska

In this paper, we explore how ontological knowledge expressed via existential rules can be combined with possibilistic networks (i) to represent qualitative preferences along with domain knowledge, and (ii) to realize preference-based answering of conjunctive queries (CQs). We call these combinations ontological possibilistic networks (OP-nets). We define skyline and k-rank answers to CQs under preferences and provide complexity (including data tractability) results for deciding consistency and CQ skyline membership for OP-nets. We show that our formalism has a lower complexity than a similar existing formalism.

KR Conference 2016 Conference Paper

Probabilistic Models over Weighted Orderings: Fixed-Parameter Tractable Variable Elimination

• Thomas Lukasiewicz
• Maria Vanina Martinez
• David Poole
• Gerardo Simari

Probabilistic models with weighted formulas, known as Markov models or log-linear models, are used in many domains. Recent models of weighted orderings between elements that have been proposed as flexible tools to express preferences under uncertainty, are also potentially useful in applications like planning, temporal reasoning, and user modeling. Their computational properties are very different from those of conventional Markov models; because of the transitivity of the “less than” relation, standard methods that exploit structure of the models, such as variable elimination, are not directly applicable, as there are no conditional independencies between the orderings within connected components. The best known algorithms for general inference in these models are exponential in the number of statements. Here, we present the first algorithms that exploit the available structure. We begin with the special case of models in the form of chains; we present an exact O(n3) algorithm, where n is the total number of elements. Next, we generalize this technique to models in which the set of statements are comprised of arbitrary sets of atomic weighted preference formulas (while the query and evidence are conjunctions of atomic preference formulas), and the resulting exact algorithm runs in time O(m ∗ n2 ∗ nc), where m is the number of preference formulas, n is the number of elements, and c is the maximum number of elements in a linear cut (which depends both on the structure of the model and the order in which the elements are processed)—therefore, this algorithm is tractable for cases in which c can be bounded to a low value. Finally, we report on the results of an empirical evaluation of both algorithms, showing how they scale with reasonably-sized models.

IJCAI Conference 2015 Conference Paper

Combining Existential Rules with the Power of CP-Theories

• Tommaso Di Noia
• Thomas Lukasiewicz
• Maria Vanina Martinez
• Gerardo I. Simari
• Oana Tifrea-Marciuska

The tastes of a user can be represented in a natural way by using qualitative preferences. In this paper, we explore how ontological knowledge expressed via existential rules can be combined with CP-theories to (i) represent qualitative preferences along with domain knowledge, and (ii) perform preference-based answering of conjunctive queries (CQs). We call these combinations ontological CP-theories (OCP-theories). We define skyline and k-rank answers to CQs based on the user’s preferences encoded in an OCP-theory, and provide an algorithm for computing them. We also provide precise complexity (including data tractability) results for deciding consistency, dominance, and CQ skyline membership for OCP-theories.

AAAI Conference 2015 Conference Paper

From Classical to Consistent Query Answering under Existential Rules

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Andreas Pieris
• Gerardo Simari

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.

ECAI Conference 2014 Conference Paper

Probabilistic Preference Logic Networks

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Gerardo I. Simari

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.

KR Conference 2014 Conference Paper

Stable Model Semantics for Guarded Existential Rules and Description Logics

• Georg Gottlob
• Andre Hernich
• Clemens Kupke
• Thomas Lukasiewicz

Baget et al. 2009; 2011; Thomazo 2011; Calı̀, Gottlob, and Pieris 2012; Gottlob, Manna, and Pieris 2013). Related syntactic conditions led to the Datalog± family (Calı̀, Gottlob, and Lukasiewicz 2012). A class of major relevance are guarded TGDs (GTGDs). A TGD is guarded if its body contains an atom, called guard, that covers all body variables. NCs may be safely used together with guarded TGDs; their bodies are not required to contain a guard atom. A nice and important aspect of guarded rules is that they generalize well-known description logics (DLs). All the DLs of the DL-Lite family in (Calvanese et al. 2007; Poggi et al. 2008) and the DL ELHI (Baader, Brandt, and Lutz 2005) can be embedded into guarded Datalog± (Calı̀, Gottlob, and Lukasiewicz 2012). In particular, this holds for DL-LiteR, the theoretical basis of the QL profile of the Web ontology language OWL 2. To appreciate how easily DL axioms can be transformed into Datalog±, note that rule (1) can be written as ∃EmpProj u BaseLevel v ∃IsManagedBy. We tackle a long-standing open research problem and prove the decidability of query answering under the stable model semantics for guarded existential rules, where rule bodies may contain negated atoms, and provide complexity results. The results extend to guarded Datalog± with negation, and thus provide a natural and decidable stable model semantics to description logics such as ELHI and DL-LiteR. 1 1. 1

IJCAI Conference 2013 Conference Paper

Preference-Based Query Answering in Datalog+/– Ontologies

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Gerardo I. Simari

The study of preferences has a long tradition in many disciplines, but it has only relatively recently entered the realm of data management through their application in answering queries to relational databases. The current revolution in data availability through the Web and, perhaps most importantly in the last few years, social media sites and applications, puts ontology languages at the forefront of data and information management technologies. In this paper, we propose the first (to our knowledge) integration of ontology languages with preferences as in relational databases by developing PrefDatalog+/–, an extension of the Datalog+/– family of languages with preference management formalisms closely related to those previously studied for relational databases. We focus on two kinds of answers to queries that are relevant to this setting, skyline and k-rank (a generalization of top-k queries), and develop algorithms for computing these answers to both DAQs (disjunctions of atomic queries) and CQs (conjunctive queries). We show that DAQ answering in PrefDatalog+/– can be done in polynomial time in the data complexity, as in relational databases, as long as query answering can also be done in polynomial time (in the data complexity) in the underlying classical ontology.

AAAI Conference 2012 Conference Paper

Equality-Friendly Well-Founded Semantics and Applications to Description Logics

• Georg Gottlob
• André Hernich
• Clemens Kupke
• Thomas Lukasiewicz

We tackle the problem of defining a well-founded semantics for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (WFS) for the recent Datalog± family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog± by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed-point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog± with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.

UAI Conference 2012 Conference Paper

Heuristic Ranking in Tightly Coupled Probabilistic Description Logics

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Giorgio Orsi 0001
• Gerardo I. Simari

The Semantic Web effort has steadily been gaining traction in the recent years. In particular, Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on the Web. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.

ECAI Conference 2012 Conference Paper

Inconsistency Handling in Datalog+/- Ontologies

• Thomas Lukasiewicz
• Maria Vanina Martinez
• Gerardo I. Simari

The advent of the Semantic Web has made the problem of inconsistency management especially relevant. Datalog+/− is a family of ontology languages that is in particular useful for representing and reasoning over lightweight ontologies in the Semantic Web. In this paper, we study different semantics for query answering in inconsistent Datalog+/− ontologies. We develop a general framework for inconsistency management in Datalog+/− ontologies based on incision functions from belief revision, in which we can characterize several query answering semantics as special cases: (i) consistent answers, originally developed for relational databases and recently adopted for some classes of description logics (DLs), (ii) intersection semantics, a sound approximation of consistent answers, and (iii) lazy consistent answers, a novel alternative semantics that offers a good compromise between quality of answers and computation time. We also provide complexity results for query answering under the different semantics, including data tractability results.

AAAI Conference 2010 Conference Paper

Ontological Reasoning with F-logic Lite and its Extensions

• Andrea Cali
• Georg Gottlob
• Michael Kifer
• Thomas Lukasiewicz
• Andreas Pieris

AIJ Journal 2008 Journal Article

Combining answer set programming with description logics for the Semantic Web

• Thomas Eiter
• Giovambattista Ianni
• Thomas Lukasiewicz
• Roman Schindlauer
• Hans Tompits

We propose a combination of logic programming under the answer set semantics with the description logics SHIF ( D ) and SHOIN ( D ), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set P of description logic rules (or dl-rules). Such rules are similar to usual rules in nonmonotonic logic programs, but they may also contain queries to L, possibly under default negation, in their bodies. They allow for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We define a suite of semantics for various classes of dl-programs, which conservatively extend the standard semantics of the respective classes and coincide with it in absence of a description logic knowledge base. More concretely, we generalize positive, stratified, and arbitrary normal logic programs to dl-programs, and define a Herbrand model semantics for them. We show that they have similar properties as ordinary logic programs, and also provide fixpoint characterizations in terms of (iterated) consequence operators. For arbitrary dl-programs, we define answer sets by generalizing Gelfond and Lifschitz's notion of a transform, leading to a strong and a weak answer set semantics, which are based on reductions to the semantics of positive dl-programs and ordinary positive logic programs, respectively. We also show how the weak answer sets can be computed utilizing answer sets of ordinary normal logic programs. Furthermore, we show how some advanced reasoning tasks for the Semantic Web, including different forms of closed-world reasoning and default reasoning, as well as DL-safe rules, can be realized on top of dl-programs. Finally, we give a precise picture of the computational complexity of dl-programs, and we describe efficient algorithms and a prototype implementation of dl-programs which is available on the Web.

AIJ Journal 2008 Journal Article

Expressive probabilistic description logics

• Thomas Lukasiewicz

The work in this paper is directed towards sophisticated formalisms for reasoning under probabilistic uncertainty in ontologies in the Semantic Web. Ontologies play a central role in the development of the Semantic Web, since they provide a precise definition of shared terms in web resources. They are expressed in the standardized web ontology language OWL, which consists of the three increasingly expressive sublanguages OWL Lite, OWL DL, and OWL Full. The sublanguages OWL Lite and OWL DL have a formal semantics and a reasoning support through a mapping to the expressive description logics SHIF ( D ) and SHOIN ( D ), respectively. In this paper, we present the expressive probabilistic description logics P- SHIF ( D ) and P- SHOIN ( D ), which are probabilistic extensions of these description logics. They allow for expressing rich terminological probabilistic knowledge about concepts and roles as well as assertional probabilistic knowledge about instances of concepts and roles. They are semantically based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning, which naturally interprets this terminological and assertional probabilistic knowledge as knowledge about random and concrete instances, respectively. As an important additional feature, they also allow for expressing terminological default knowledge, which is semantically interpreted as in Lehmann's lexicographic entailment in default reasoning from conditional knowledge bases. Another important feature of this extension of SHIF ( D ) and SHOIN ( D ) by probabilistic uncertainty is that it can be applied to other classical description logics as well. We then present sound and complete algorithms for the main reasoning problems in the new probabilistic description logics, which are based on reductions to reasoning in their classical counterparts, and to solving linear optimization problems. In particular, this shows the important result that reasoning in the new probabilistic description logics is decidable/computable. Furthermore, we also analyze the computational complexity of the main reasoning problems in the new probabilistic description logics in the general as well as restricted cases.

IJCAI Conference 2007 Conference Paper

• Alessandro Farinelli
• Alberto Finzi
• Thomas Lukasiewicz

In this paper, we present the agent programming language TeamGolog, which is a novel approach to programming a team of cooperative agents under partial observability. Every agent is associated with a partial control program in Golog, which is completed by the TeamGolog interpreter in an optimal way by assuming a decision-theoretic semantics. The approach is based on the key concepts of a synchronization state and a communication state, which allow the agents to passively resp. actively coordinate their behavior, while keeping their belief states, observations, and activities invisible to the other agents. We show the usefulness of the approach in a rescue simulated domain.

ECAI Conference 2006 Conference Paper

Adaptive Multi-Agent Programming in GTGolog

• Alberto Finzi
• Thomas Lukasiewicz

We present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with game-theoretic multi-agent planning in stochastic games. In GTGolog, the transition probabilities and reward values of the domain must be provided with the model. The adaptive generalization of GTGolog proposed here is directed towards letting the agents themselves explore and adapt these data. We use high-level programs for the generation of both abstract states and optimal policies.

AIJ Journal 2006 Journal Article

Causes and explanations in the structural-model approach: Tractable cases

• Thomas Eiter
• Thomas Lukasiewicz

This paper continues the research on the computational aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph. Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph, respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structure-based causes and explanations in first-order reasoning about actions, which produces large causal models that are naturally layered through the time line, and thus have the structure of layered causal graphs. Furthermore, an important feature of the tractable cases for causal trees and layered causal graphs is that they can be recognized efficiently, namely in linear time. Finally, by extending the new characterization of weak cause, we obtain similar techniques for computing the degrees of responsibility and blame, and hence also novel tractability results for structure-based responsibility and blame.

KR Conference 2006 Conference Paper

Variable-Strength Conditional Preferences for Matchmaking in Description Logics

• Thomas Lukasiewicz
• Joerg Schellhase

We present an approach to variable-strength conditional preferences for matchmaking and ranking objects in description logics. In detail, we introduce conditional preference bases, which consist of a description logic knowledge base and a finite set of variable-strength conditional preferences, and which are associated with a formal semantics based on ranking functions. We then define the notions of consistency and preferential entailment for conditional preference bases, which strictly generalize e-consistency and entailment in System Z+ in default reasoning from conditional knowledge bases, respectively. We also describe some semantic properties of preferential entailment. We then show how preferential entailment can be used to define a distance measure between two conditional preference bases. We also define functions for ranking objects relative to a conditional preference base, and we describe an application in the area of literature search. Finally, we provide algorithms for solving the main computational tasks related to conditional preference bases.

AAMAS Conference 2005 Conference Paper

Game Theoretic Golog under Partial Observability

• Alberto Finzi
• Thomas Lukasiewicz

AIJ Journal 2005 Journal Article

Weak nonmonotonic probabilistic logics

• Thomas Lukasiewicz

We present an approach where probabilistic logic is combined with default reasoning from conditional knowledge bases in Kraus et al. 's System P, Pearl's System Z, and Lehmann's lexicographic entailment. The resulting probabilistic generalizations of default reasoning from conditional knowledge bases allow for handling in a uniform framework strict logical knowledge, default logical knowledge, as well as purely probabilistic knowledge. Interestingly, probabilistic entailment in System P coincides with probabilistic entailment under g-coherence from imprecise probability assessments. We then analyze the semantic and nonmonotonic properties of the new formalisms. It turns out that they all are proper generalizations of their classical counterparts and have similar properties as them. In particular, they all satisfy the rationality postulates of System P and some Conditioning property. Moreover, probabilistic entailment in System Z and probabilistic lexicographic entailment both satisfy the property of Rational Monotonicity and some Irrelevance property, while probabilistic entailment in System P does not. We also analyze the relationships between the new formalisms. Here, probabilistic entailment in System P is weaker than probabilistic entailment in System Z, which in turn is weaker than probabilistic lexicographic entailment. Moreover, they all are weaker than entailment in probabilistic logic where default sentences are interpreted as strict sentences. Under natural conditions, probabilistic entailment in System Z and lexicographic entailment even coincide with such entailment in probabilistic logic, while probabilistic entailment in System P does not. Finally, we also present algorithms for reasoning under probabilistic entailment in System Z and probabilistic lexicographic entailment, and we give a precise picture of its complexity.

KR Conference 2004 Conference Paper

Combining Answer Set Programming with Description Logics for the Semantic Web

• Thomas Eiter
• Thomas Lukasiewicz
• Roman Schindlauer
• Hans Tompits

Towards the integration of rules and ontologies in the Semantic Web, we propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. This combination allows for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We introduce description logic programs (dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules (dl-rules) P. Such rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L, possibly default negated, in their bodies. We define Herbrand models for dl-programs, and show that satisfiable positive dl-programs have a unique least Herbrand model. More generally, consistent stratified dl-programs can be associated with a unique minimal Herbrand model that is characterized through iterative least Herbrand models. We then generalize the (unique) minimal Herbrand model semantics for positive and stratified dl-programs to a strong answer set semantics for all dl-programs, which is based on a reduction to the least model semantics of positive dl-programs. We also define a weak answer set semantics based on a reduction to the answer sets of ordinary logic programs. Strong answer sets are weak answer sets, and both properly generalize answer sets of ordinary normal logic programs. We then give fixpoint characterizations for the (unique) minimal Herbrand model semantics of positive and stratified dl-programs, and show how to compute these models by finite fixpoint iterations. Furthermore, we give a precise picture of the complexity of deciding strong and weak answer set existence for a dl-program.

AIJ Journal 2004 Journal Article

Combining probabilistic logic programming with the power of maximum entropy

• Gabriele Kern-Isberner
• Thomas Lukasiewicz

This paper is on the combination of two powerful approaches to uncertain reasoning: logic programming in a probabilistic setting, on the one hand, and the information-theoretical principle of maximum entropy, on the other hand. More precisely, we present two approaches to probabilistic logic programming under maximum entropy. The first one is based on the usual notion of entailment under maximum entropy, and is defined for the very general case of probabilistic logic programs over Boolean events. The second one is based on a new notion of entailment under maximum entropy, where the principle of maximum entropy is coupled with the closed world assumption (CWA) from classical logic programming. It is only defined for the more restricted case of probabilistic logic programs over conjunctive events. We then analyze the nonmonotonic behavior of both approaches along benchmark examples and along general properties for default reasoning from conditional knowledge bases. It turns out that both approaches have very nice nonmonotonic features. In particular, they realize some inheritance of probabilistic knowledge along subclass relationships, without suffering from the problem of inheritance blocking and from the drowning problem. They both also satisfy the property of rational monotonicity and several irrelevance properties. We finally present algorithms for both approaches, which are based on generalizations of recent techniques for probabilistic logic programming under logical entailment. The algorithm for the first approach still produces quite large weighted entropy maximization problems, while the one for the second approach generates optimization problems of the same size as the ones produced in probabilistic logic programming under logical entailment.

AIJ Journal 2004 Journal Article

Complexity results for explanations in the structural-model approach

• Thomas Eiter
• Thomas Lukasiewicz

We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual cause. In particular, we give a precise picture of the complexity of deciding explanations, α-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an α-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, the complexity of deciding explanations in the general case of situations, and the complexity of deciding subsumption and equivalence between causal models. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.

ECAI Conference 2004 Conference Paper

Game-Theoretic Agent Programming in Golog

• Alberto Finzi
• Thomas Lukasiewicz

NMR Workshop 2004 Conference Paper

Qualitative and probabilistic uncertainty in reasoning about actions with sensing

• Luca Iocchi
• Thomas Lukasiewicz
• Daniele Nardi
• Riccardo Rosati 0001

α We present the description logic PN-ALCKNF for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of the description logic α ALCKNF by actions with nondeterministic and probabilisα tic effects. We define a formal semantics of PN-ALCKNF in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states, which are sets of possible states of the world. We introduce the notions of a conditional plan and its goodness under qualitative and probabilistic uncertainty. We then formulate the problem of conditional planning in this framework, and we present an algorithm for solving it. This algorithm is based on a reduction to reasoning in description logics, and is shown to be sound and complete in the sense that it generates all optimal plans. We also describe an application in a robotic-soccer scenario.

ECAI Conference 2004 Conference Paper

Reasoning about Actions with Sensing under Qualitative and Probabilistic Uncertainty

• Luca Iocchi
• Thomas Lukasiewicz
• Daniele Nardi
• Riccardo Rosati 0001

JELIA Conference 2004 Conference Paper

Relational Markov Games

• Alberto Finzi
• Thomas Lukasiewicz

Abstract Towards a compact and elaboration-tolerant first-order representation of Markov games, we introduce relational Markov games, which combine standard Markov games with first-order action descriptions in a stochastic variant of the situation calculus. We focus on the zero-sum two-agent case, where we have two agents with diametrically opposed goals. We also present a symbolic value iteration algorithm for computing Nash policy pairs in this framework.

UAI Conference 2003 Conference Paper

Probabilistic Reasoning about Actions in Nonmonotonic Causal Theories

• Thomas Eiter
• Thomas Lukasiewicz

We present the language {m P}{cal C}+ for probabilistic reasoning about actions, which is a generalization of the action language {cal C}+ that allows to deal with probabilistic as well as nondeterministic effects of actions. We define a formal semantics of {m P}{cal C}+ in terms of probabilistic transitions between sets of states. Using a concept of a history and its belief state, we then show how several important problems in reasoning about actions can be concisely formulated in our formalism.

UAI Conference 2003 Conference Paper

Structure-Based Causes and Explanations in the Independent Choice Logic

• Alberto Finzi
• Thomas Lukasiewicz

This paper is directed towards combining Pearl's structural-model approach to causal reasoning with high-level formalisms for reasoning about actions. More precisely, we present a combination of Pearl's structural-model approach with Poole's independent choice logic. We show how probabilistic theories in the independent choice logic can be mapped to probabilistic causal models. This mapping provides the independent choice logic with appealing concepts of causality and explanation from the structural-model approach. We illustrate this along Halpern and Pearl's sophisticated notions of actual cause, explanation, and partial explanation. This mapping also adds first-order modeling capabilities and explicit actions to the structural-model approach.

UAI Conference 2002 Conference Paper

Causes and Explanations in the Structural-Model Approach: Tractable Cases

• Thomas Eiter
• Thomas Lukasiewicz

In this paper, we continue our research on the algorithmic aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we present new characterizations of weak causes for certain classes of causal models, which show that under suitable restrictions deciding causes and explanations is tractable. To our knowledge, these are the first explicit tractability results for the structural-model approach.

KR Conference 2002 Conference Paper

Complexity Results for Explanations in the Structural-Model Approach

• Thomas Eiter
• Thomas Lukasiewicz

AIJ Journal 2002 Journal Article

Complexity results for structure-based causality

• Thomas Eiter
• Thomas Lukasiewicz

We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.

NMR Workshop 2002 Conference Paper

Nonmonotonic probabilistic logics between model-theoretic probabilistic logic and probabilistic logic under coherence

• Thomas Lukasiewicz

Recently, it has been shown that probabilistic entailment under coherence is weaker than model-theoretic probabilistic entailment. Moreover, probabilistic entailment under coherence is a generalization of default entailment in System P. In this paper, we continue this line of research by presenting probabilistic generalizations of more sophisticated notions of classical default entailment that lie between modeltheoretic probabilistic entailment and probabilistic entailment under coherence. That is, the new formalisms properly generalize their counterparts in classical default reasoning, they are weaker than model-theoretic probabilistic entailment, and they are stronger than probabilistic entailment under coherence. The new formalisms are useful especially for handling probabilistic inconsistencies related to conditioning on zero events. They can also be applied for probabilistic belief revision. More generally, in the same spirit as a similar previous paper, this paper sheds light on exciting new formalisms for probabilistic reasoning beyond the well-known standard ones.

JELIA Conference 2002 Conference Paper

P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the Semantic Web

• Rosalba Giugno
• Thomas Lukasiewicz

Abstract Ontologies play a central role in the development of the semantic web, as they provide precise definitions of shared terms in web resources. One important web ontology language is DAML+OIL; it has a formal semantics and a reasoning support through a mapping to the expressive description logic \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ) with the addition of inverse roles. In this paper, we present a probabilistic extension of \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ), called P- \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ), to allow for dealing with probabilistic ontologies in the semantic web. The description logic P- \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ) is based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning. It allows to express rich probabilistic knowledge about concepts and instances, as well as default knowledge about concepts. We also present sound and complete reasoning techniques for P- \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ), which are based on reductions to classical reasoning in \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ) and to linear programming, and which show in particular that reasoning in P- \( \mathcal{S}\mathcal{H}\mathcal{O}\mathcal{Q} \) ( D ) is decidable.

UAI Conference 2001 Conference Paper

Probabilistic Logic Programming under Inheritance with Overriding

• Thomas Lukasiewicz

We present probabilistic logic programming under inheritance with overriding. This approach is based on new notions of entailment for reasoning with conditional constraints, which are obtained from the classical notion of logical entailment by adding the principle of inheritance with overriding. This is done by using recent approaches to probabilistic default reasoning with conditional constraints. We analyze the semantic properties of the new entailment relations. We also present algorithms for probabilistic logic programming under inheritance with overriding, and program transformations for an increased efficiency.

UAI Conference 2000 Conference Paper

Credal Networks under Maximum Entropy

• Thomas Lukasiewicz

We apply the principle of maximum entropy to select a unique joint probability distribution from the set of all joint probability distributions specified by a credal network. In detail, we start by showing that the unique joint distribution of a Bayesian tree coincides with the maximum entropy model of its conditional distributions. This result, however, does not hold anymore for general Bayesian networks. We thus present a new kind of maximum entropy models, which are computed sequentially. We then show that for all general Bayesian networks, the sequential maximum entropy model coincides with the unique joint distribution. Moreover, we apply the new principle of sequential maximum entropy to interval Bayesian networks and more generally to credal networks. We especially show that this application is equivalent to a number of small local entropy maximizations.

AIJ Journal 2000 Journal Article

Default reasoning from conditional knowledge bases: Complexity and tractable cases

• Thomas Eiter
• Thomas Lukasiewicz

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form “φ→ψ”, which informally read as “generally, if φ then ψ”. Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default φ→ψ, does KB entail φ→ψ? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al. 's maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.

JELIA Conference 2000 Conference Paper

New Tractable Cases in Default Reasoning from Conditional Knowledge Bases

• Thomas Eiter
• Thomas Lukasiewicz

Abstract We present new tractable cases for default reasoning from conditional knowledge bases. In detail, we introduce q-Horn conditional knowledge bases, which allow for a limited use of disjunction. We show that previous tractability results for ε-entailment, proper ε-entailment, and z - and z + -entailment in the Horn case can be extended to the q-Horn case. Moreover, we present feedback-free- Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. We show that the maximum entropy approach and lexicographic entailment are tractable in the feedback-free-Horn case. Our results complement and extend previous results, and contribute in refining the tractability/ intractability frontier of default reasoning from conditional knowledge bases.

CSL Conference 1999 Conference Paper

Many-Valued First-Order Logics with Probabilistic Semantics

• Thomas Lukasiewicz

Abstract We present n -valued first-order logics with a purely probabilistic semantics. We then introduce a new probabilistic semantics of n -valued first-order logics that lies between the purely probabilistic semantics and the truth-functional semantics of the n -valued Łukasiewicz logics Ł n. Within this semantics, closed formulas of classical first-order logics that are logically equivalent in the classical sense also have the same truth value under all n -valued interpretations. Moreover, this semantics is shown to have interesting computational properties. More precisely, n -valued logical consequence in disjunctive logic programs with n -valued disjunctive facts can be reduced to classical logical consequence in n -1 layers of classical disjunctive logic programs. Moreover, we show that n -valued logic programs have a model and a fixpoint semantics that are very similar to those of classical logic programs. Finally, we show that some important deduction problems in n -valued logic programs have the same computational complexity like their classical counterparts.

UAI Conference 1998 Conference Paper

Magic Inference Rules for Probabilistic Deduction under Taxonomic Knowledge

• Thomas Lukasiewicz

We present locally complete inference rules for probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events. Crucially, in contrast to similar inference rules in the literature, our inference rules are locally complete for conjunctive events and under additional taxonomic knowledge. We discover that our inference rules are extremely complex and that it is at first glance not clear at all where the deduced tightest bounds come from. Moreover, analyzing the global completeness of our inference rules, we find examples of globally very incomplete probabilistic deductions. More generally, we even show that all systems of inference rules for taxonomic and probabilistic knowledge-bases over conjunctive events are globally incomplete. We conclude that probabilistic deduction by the iterative application of inference rules on interval restrictions for conditional probabilities, even though considered very promising in the literature so far, seems very limited in its field of application.

ECAI Conference 1998 Conference Paper

Probabilistic Logic Programming

• Thomas Lukasiewicz