Machine learning is more and more used by non-expert users, in a large variety of different contexts. For this reason it becomes  important that (i) machine learning methods are designed for an interactive usage where are humans and machines can jointly improve each other's decisions; (ii) where machine learning results are interpretable, (iii) and where even the input to machine learning algorithms can easily be understood by human users.

Joint Human-Machine Decision Making. In fields like medicine and finance it is becomming increasingly clear that future decisions will be made by humans who are informed by machine learning algorithms. This novel human+algorithm decision making problem poses new challenges for machine learners. It is no longer sufficient to optimize performance on a given task but one also needs to decide how the task of the machine should be given in the first place. As a consequence, and despite an increasing amount of practical work on the topic, human-machine decision making still lacks a systematic understanding. We tried to bridge this gap by providing theoretical perspectives on what can (and cannot!) be expected in human-machine decision making. Our approach is to formally model the most salient aspects of the problem. In our view, these are the presence of unobserved information and limited understanding between the two decision makers (i.e. the human and the algorithm). Our analysis reveals that both of these aspects have important consequences for learning. In particular, we demonstrate the suprising hardness of optimally advising a decision maker who has access to external information. We can prove that in the worst-case, it is impossible to advance beyond a simple learning strategy of trial-and-error. To our current knowledge, more efficient learning is only possible under strong structural assumptions on the problem. A survey of the extant literature on human-machine decision making revealed that most of it (implicitly) makes such assumptions. This work is submitted and can be found on arxiv, but is not published yet.

Analysis of Post-Hoc Explanations. When machine learning algoithms are being used in sensitive applications interpretability becomes a pressing need. Popular post-hoc explainability algorithms such as LIME, SHAP and Integrated Gradients are based on heuristic ideas of how to obtain meaningful explanations. In many sensitive applications a heuristic understanding might not be enough. We would need formal guarantees on how explanations relate to the function that we explain. In [], we provide the first theoretical analysis of the popular LIME (Local Interpretable Model-Agnostic Explanation) algorithm for tabular data. We are able to derive closed-form expressions for the coefficients of the interpretable model when the function to explain is linear. In this scenario, LIME indeed discovers meaningful features and the explanations are proportional to the gradient of the function to explain. However, our analysis also reveals that poor choices of parameters can lead LIME to miss important features. 

In other machine learning applications, individual features don't have any particular meaning. The most prominent example of this is image classification. These problems and the typically learned deep neural networks are often highly non-linear. Thus, conceptualizing meaningful explanations can become quite challenging. Even in relatively simple examples, it can been shown that 'explaining' non-linear functions with linear approximations can lead to misleading conclusions. In our most recent project, we attempt to identify neccesary conditions for meaningful explanations in high-dimensional settings. In image classification, a potential candidate to judge the meaningfulness of explanations is the tangent space of the manifold on which high-dimensional image data is often believed to lie. For synthetically constructed problems, we can analytically derive the tangent space of the data manifold and measure empirically how well it aligns with different kinds of explanations. This work can be found on arxiv and is submitted, but not yet published.

Comparison-Based Learning. Machine learning based on easy to generate, human interpretable data. In the typical machine learning setting we are given a data set $\mathcal{D}$ of objects and a distance function $\delta$ that quantifies how ``close'' the objects are to each other. In recent years,  a whole new branch of the machine learning literature has emerged that relaxes this scenario. Instead of being able to evaluate the distance function $\delta$ itself, we only get to see the results of comparisons such as $\delta(A,B) < \delta(C,D)$, where $A,B,C,D\in\mathcal{D}$. We refer to any collection of answers to such comparisons as ordinal distance information. Our group investigates how machine learning algorithms can work with such data. We can learn a Euclidean representation that respects the comparisons but evaluating the quality of such an embedding is difficult []. As an alternative we proposed several algorithmic solutions that learn directly from the comparisons.

In a series of papers we investigated this learning framework: We developed kernels, allowing us to use kernel methods with ordinal distance comparisons [], and derived a series of algorithms for medoid estimation, outlier identification, classification, and clustering based on the lens depth function []. We proposed a method for large scale classification with generalization guarantees in a boosting framework [] (IJCAI best paper award). The search for nearest neighbors is another example of a classical machine learning task for which we proposed a comparison-based approach. The comparison tree [] is a random tree constructed by recursively splitting the space by choosing random pivots and assigning  data points to the nearest pivot. This structure allows for efficient search of the nearest neighbors of a query point, and we proved theoretical guarantees on the performance of this method. In a next step we then aggregate many of these trees to construct a random forest. Albeit having access to very little information, these ``comparison-based random forests'' perform about as well as methods that have access to the true distances and can be proved to be statistically consistent []. Finally we give theoretical guarantees on hierarchical clustering algorithms based on comparisons [].