dataninja

Interpretable machine learning through game-theoretical analysis of influencing variables and interaction effects

Goal

Most machine learning (ML) methods assume a representation of data entities in terms of a fixed set of variables (features). Analyzing the importance of individual variables for a model induced from the data, or for the prediction made with that model in a specific situation, facilitates the interpretation of ML models and supports subtasks such as feature selection. The goal of this project is to develop novel methods for feature analysis. In particular, we are interested in numerical measures quantifying the importance of individual variables in a machine learning task, i.e., the contribution of individual variables to the task at hand and predictions made by a model, as well as the interaction and dependencies between different variables.

Project Overview

This project aims at transparent modeling of dependencies and interactions between variables as well as theoretically justified reductions of nonlinear dependencies to understandable and interpretable measures for the influence of individual variables, both for supervised and unsupervised learning. A theoretical framework of that kind shall be complemented by suitable visualization techniques to further facilitate interpretation, the interaction with users and domain experts, and the exploration of dependencies in high-dimensional data spaces. All methods shall be evaluated in various case studies in the medical domain.

The main innovation of the project is to establish a connection between feature analysis and (cooperative) game theory. To this end, a feature subset is considered as a coalition in game theory, and the performance of a model trained with these features as the value of the coalition. The importance of individual variables can then be quantified in terms of well-established game-theoretical measures, such as the Shapley value, just like the interaction between pairs or groups of variables. Due to the exponential size of the lattice of feature subsets, the exact computation of such quantities is in general infeasible. Therefore, a key challenge of the project is the development of efficient approximate algorithms.

^​1–4​

Current Work

Identifying Top-k Players in Cooperative Games via Shapley Bandits
The formal notion of a cooperative game, in which players can form coalitions to accomplish a
certain task, is a versatile concept with countless practical applications. In the context of (supervised) machine learning, individual features can be seen as players and feature subsets as coalitions – the task here is to train a model with high predictive performance^​2,5​. An interesting question in the context of cooperative games concerns the importance or contribution of an individual player: How to distribute the collective benefit of a coalition among the individual players? Independent of the considered application, cooperative game theory has proposed different solution concepts, with the Shapley value as the arguably most popular one^​6​.

Due to the computational effort growing exponentially with the number of participants in a game, several methods have been proposed to approximate Shapley values. Yet, in many applications, only the order of players according to their Shapley values is important, or maybe the set of the 𝑘 best players, but not the values themselves. We consider the problem of identifying the 𝑘 players in a cooperative game with the highest Shapley values and denote it as the Top-k Shapley problem. By viewing the marginal contributions of a player as a random variable, we establish a connection between cooperative games and multi-armed bandits, which in turn allows us to reduce Top-k Shapley to the multiple arms identification problem. We call the resulting bandits problem Shapley bandits. Besides adopting existing algorithms for multiple arms identifications, we propose the Border Uncertainty Sampling algorithm (BUS) and provide empirical evidence for its superiority over state-of-the-art algorithms.

Non-Stationary Dueling Bandits
The dueling bandits problem is an online decision making problem in which a learner has to repeatedly select a pair of items, upon he observes a noisy binary preference feedback of stochastic nature. The learner’s goal is to play as often as possible over a given time horizon pairs that contain the best item, where we define the best item to be the Condorcet Winner, i.e., the item that beats all others with probability greater than half. The innovation of our setting is the introduction of non-stationarity. In particular, the underlying hidden preferences are not fixed in time, but are likely to change. We motivate this by the observation that user preferences tend to shift over time in various contexts. We propose with Beat the Winner Reset (BtWR) an algorithm for which we not only prove satisfying results for the novel non-stationary setting, but also discover its asymptotic superiority over current state-of-the-art algorithms (for example, see ^​7,8​). We are optimistic that the combination of our previously established connection between Shapley values and multi-armed bandits and the work on non-stationary dueling bandits opens up new room for research questions and methodology to be discovered.

Project Publications

• P. Kolpaczki, V. Bengs, E. Hüllermeier (2021), Identifying Top-k Players in Cooperative Games via Shapley Bandits. In Proceedings of the LWDA 2021 Workshops, volume 2993, pages 133-144, 2021.
• P. Kolpaczki, V. Bengs, and E. Hüllermeier (2022). Non-Stationary Dueling Bandits. CoRR, abs/2202.00935, 2022.

Cooperation

Data Science and Data Engineering

Prof. Dr. Emmanuel Müller

PhD student: Chiara Balestra

Communications Engineering Group

Prof. Dr. Rainhold Häb-Umbach

PhD student: Patrick Kolpaczki

References