EXplainable ALgorithmic Tools

Introduction

Deploying algorithmic solutions in real-world applications raises two challenges. First, we need easy-to-use and universal algorithms. Second, we need to guarantee that algorithmic solutions can be understood by people using them. We address the first of these challenges in the TUgbOAT project, which aims to deliver unified algorithmic tools. Here, we propose to develop tools that would address the second of these challenges.

Understanding Algorithmic Solutions

In many use scenarios, algorithms propose a solution to a human operator. The main challenge in such cases is to convince the operator to use the returned solution. Traditionally, we think of algorithms in a black-box manner, i.e., as a tool to find a good solution. We do not expect algorithms to give a human-understandable explanation of why this is the best solution, what alternatives exist, or what the bottlenecks are.

Nevertheless, we humans still tend to ask these questions even if we understand the algorithms that are used. Currently, we lack good tools that could explain the results of optimization algorithms, e.g., for the assignment problem.

Need for Explainable Algorithms

For practitioners, like ourselves, who work together with companies to deploy algorithmic solutions in real-world cases, the need to provide explainable algorithms becomes imminent. Here we will test and implement results developed in TUgbOAT that can be used to complement the algorithms with human explanations.

Planned Developments

In particular, we plan to:

1. Enrich algorithms to give meaningful alternative solutions.
2. Apply Shapley value methods to determine key solution elements.
3. Work with perturbed inputs to create robust and more concise solutions.
4. Generate concise decision trees that would explain the steps taken by algorithms.

Project Goals

This project aims to deliver the base parts of a software library that would provide explainable algorithms. We plan to concentrate on the task assignment problem (i.e., matchings) where we already cooperate with companies.