EXplainable ALgorithmic Tools

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 thesechallenges in TUgbOAT project, which aims to deliver unified algorithmic tools.

Here, we propose to develop tools that would addressthe second of these challenges.In many use scenarios, algorithms propose a solution to a human operator. The main challenge in such cases is to convince him to usethe returned solution. Traditionally we think of algorithms in a black-box manner, i.e., as a tool to find a good solution.

We do notexpect algorithms to give a human-understandable explanation of why this is the best solution, or what alternatives exist or what arethe bottlenecks.

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.For practitioners, like ourselves, that work together with companies to deploy algorithmic solutions in real-world cases, the need toprovide explainable algorithms becomes immanent.

Here we will test and implement results developed in TUgbOAT that can be usedto complement the algorithms with human explanations.

In particular, we plan to:- enrich algorithms to give meaningful alternative solutions,- apply Shapley value methods to determine key solution elements,- work with perturbed inputs to create robust and more concise solutions,- generate concise decision trees that would explain steps taken by algorithms.This project aims to deliver the base parts of a software library that would give explainable algorithms.

We plan to concentrate on thetask assignment problem (i.e., matchings) where we already cooperate with companies.