Much of "AI" today is driven by black-box machine learning models whose inner mechanics cannot really be understood. There are various ideas to explain their decisions, one of them are "counterfactual explanations". The standard motivation for counterfactuals is a loan application scenario. Suppose that a loan application is rejected by a black-box model, and the user wants to understand why. A counterfactual explanation explains the decision by generating an input that is as close to the original input as possible but changes the outcome of the black-box model (an optimization problem). For example, the counterfactual explanation may state that the application had not been rejected if the income had been higher and the debt lower. Counterfactual explanations are quite intuitive in my opinion, but they also suffer from a robustness problem: users may receive very different explanations for similar inputs, which can be confusing, frustrating and can even be exploited for adversarial attacks. The robustness problem can be solved to some extent by reporting multiple diverse rather than a single counterfactual. However, the computational problem is quite challenging. We recently proposed a heuristic to solve the problem that works quite well compared to the state-of-the-art, but there is still a lot that one can improve. A dissertation in this direction could explore alternative filter functions or different search strategies and again contain analytical elements (runtime guarantees like in Proposition 3 or more general formal guarantees) and/or an implementation part.

https://ojs.aaai.org/index.php/AAAI/article/view/30127