![\"\"](\"https:\/\/dataninja.nrw\/wp-content\/uploads\/2021\/04\/illustration-1.png\")
<\/figure>\n\n\n\nProject Overview<\/h3>\n\n\n\n
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.<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
\u200b1\u20134\u200b<\/sup><\/span><\/p>\n\n\n\n Identifying Top-k Players in Cooperative Games via Shapley Bandits 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 \ud835\udc58 best players, but not the values themselves. We consider the problem of identifying the \ud835\udc58 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.<\/p>\n\n\n\n Non-Stationary Dueling Bandits<\/strong> Data Science and Data Engineering<\/p><\/b><\/a>\n Prof. Dr. Emmanuel M\u00fcller<\/p><\/a>\n PhD student: Chiara Balestra<\/a><\/p>\n <\/div>\n<\/div>\n Communications Engineering Group<\/p><\/b><\/a>\n Prof. Dr. Rainhold H\u00e4b-Umbach<\/p><\/a>\n PhD student: Patrick Kolpaczki<\/a><\/p>\n <\/div>\n<\/div>\n Associated with Prof. Dr. Eyke H\u00fcllermeier, <\/a> LMU M\u00fcnchen<\/p>\n <\/div>\n<\/div>\n\n\n\n![\"\"](\"https:\/\/dataninja.nrw\/wp-content\/uploads\/2022\/06\/08_X-FI_A3-1024x724.jpg\")
\n\n\n\nCurrent Work<\/h3>\n\n\n\n
<\/strong>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\u200b2,5\u200b<\/sup><\/span>. 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\u200b6\u200b<\/sup><\/span>.<\/p>\n\n\n\n
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 \u200b7,8\u200b<\/sup><\/span>). 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.<\/p>\n\n\n\n![\"\"](\"https:\/\/dataninja.nrw\/wp-content\/uploads\/2022\/06\/BtWR-1024x597.png\")
\n\n\n\nProject Publications<\/h3>\n\n\n\n
\n
\n\n\n\nCooperation<\/h3>\n\n\n\n
![\"\"](\"https:\/\/dataninja.nrw\/wp-content\/uploads\/2021\/04\/500px-Technische_Universitat_Dortmund_Logo.png\"){kind=logo}
<\/a>\n <\/div>\n ![\"\"](\"https:\/\/dataninja.nrw\/wp-content\/uploads\/2021\/04\/500px-Logo_Uni_Paderborn.png\"){kind=logo}
<\/a>\n <\/div>\n
\n\n\n\nReferences<\/h3>\n\n\n\n
<\/ol><\/section>\n\n\n\n