Faster Algorithms

Introduction

Non-monotonic reasoning is appropriate for applications in a world that is under constant change. This applies to many applications in artificial intelligence, but for instance also to areas such as medical diagnosis, network security, or explainability in machine learning.

Unfortunately, current methods to perform non-monotonic reasoning come with extremely high computational cost. The goal of this project is to reduce this computational cost, so it can possibly run on an ordinary PC.

The project’s primary focus lies on abduction, a backwards oriented reasoning formalism. One starts with observations and looks for explanations to account for the observations. For instance, a reasonable explanation for the observation “people are wearing umbrellas” could be “it is raining”. Contrary to deduction, abduction is non-monotonic: an explanation may need to be revised at a later point in time if new information arrives; if we learn that “it does not rain”, we need to find an alternative explanation to “people are wearing umbrellas”.

Purpose

The purpose is twofold: on the one hand, explore how to construct faster, more efficient algorithms (upper bounds) and determine how close to optimal the algorithms are (lower bounds). On the other hand, advance mathematical tools to precisely analyze the computational complexity of non-monotonic reasoning problems of rich modelling power.

Motivation

Deduction is a well-studied problem with a wealth of theoretical complexity results as well as concrete software that can solve instances with millions of input variables. But despite also abduction is extensively studied from many different angles, and abduction and non-monotonic reasoning formalisms are of significant practical interest within AI, no methods or algorithms are currently known that could tackle instances of similar size.

Approach and expected results

Could it be that abductive reasoning is fundamentally more difficult to computerize than deductive reasoning? Or are there presently unknown classes of methods to computerize abductive reasoning? The goal of the project is to investigate fundamental complexity aspects of abduction and similar non-monotonic reasoning formalisms. New methods shall be developed to solve difficult abduction problems that can be used, for instance, to accelerate AI software that uses non-monotonic reasoning components. An important ingredient is the so-called algebraic method which allows to relate computational aspects with algebraic properties. Through developing such methods, we expect to obtain generalized tools to study fine-grained complexity that can advance the research front for a wealth of different non-monotonic reasoning formalisms and pave the way to speed up practical solvers.

Financiers

For more information