A key challenge for the wide-spread use of machine learning (ML) methods is the (lack of) explainability of its predictions [6] , [8] , [15] , [20] . The predictions delivered by ML methods are often used to motivate decisions affecting humans.
As a point in case, consider the school closures during the Covid-19 pandemic throughout Europe [19] . The decision makers (politicians) often based their decisions on the predictions obtained by fitting models to data, which is exactly what ML methods do. For the policy-makers in European countries, it was customary that decisions on restrictions or school closures have been explained to the public [4] . 1 Explanations of predictions, motivating decisions that affect humans, are increasingly becoming a legal obligation [20] . It also seems that humans have a basic need for understanding decision making processes [13] , [14] .
Most machine learning (ML) methods are based on a simple principle: fit a predictor map to given training data points [2] , [7] , [10] . This empirical risk minimization paradigm is also driving deep learning methods []. The various ML methods differ merely in their choice for the hypothesis spaces which collects all feasible predictor maps to choose from and the loss function to measure the quality of a fit.
We consider explainable ML methods that not only take into account how good a predictor map fits the training data (empirical risk minimization) but also how comprehensible the predictions are to a specific user.
AJ is with the Department of Computer Science, Aalto University, Finland. 1 You can find the communication of decisions by the Finnish prime minister at https://vnk.fi/en/communications-on-decisions.
Existing approaches to explainable (or interpretable) ML broadly form two categories [16] . The first category are methods that are considered as intrinsically interpretable [1] , [6] , [17] . A prominent example for this class of explainable methods is linear regression which many consider as interpretable due to the additive combination of weighted features. The weights for each feature are interpreted as a measure for the importance or relevance of that feature.
There is no widely accepted formal definition for when to consider a ML method as intrinsically interpretable. A ML method tends to be considered Interpretable if it uses a "simple" hypothesis space. Examples for a simple hypothesis space are linear maps or shallow decision trees. What sets our approach apart from previous work on intrinsically explainable ML methods is that we use an information-theoretic measure for the intrinsic explainability of a predictor map.
A second class of explainable ML methods is based on providing post-hoc (after model training) explanations [18] . These methods are model-agnostic in the sense of only requiring some training examples of the model predictions. We have recently put forward an information-theoretic approach to computing optimal post-hoc explanations for a specific user [12] .
We build on our previous work [12] and use an informationtheoretic measure for the explainability of a particular predictor. In contrast to [12] , we use this measure to directly steer the learning process for finding a good predictor map. This leads naturally to a form of regularized empirical risk minimization [7] , [11] .
Our main contribution is the concept of explainable empirical risk minimization (EERM). The idea of EERM is to use the mutual information between prediction and user summary to regularize empirical risk minimization.
Outline. We introduce the main building blocks of our approach, empirical risk minimization, regularization and information-theoretic measure of explainability in Section II. Our main contribution is the formulation of EERM in Section III.
We consider ML problems revolving around the prediction of some label value y which represents a higher-level fact about a data point. The prediction is based solely on certain low-level properties or features of the data point. We use a predictor (map)
to compute the predicted labelŷ = g(x) using the features
Any ML method that can only use finite computational resources can only use a subset of (computationally) feasible arXiv:2009.01492v1 [cs.
LG] 3 Sep 2020 maps. We refer to this subset as the hypothesis space H of a ML method. Examples for such a hypothesis space are linear maps or spaces spanned by polynomials.
For a given data point with features x and label y, we measure the quality of a predictor h using some loss function L(g, (x, y)). Formally, a loss function maps a pair (g, (x, y)) consisting of hypothesis g and data point (x, y) to some number L(g, (x, y)).
The number L(g, (x, y)) is used as a measure for the error or loss incurred by predicting the label y of a data point using the predictionŷ = g(x). Popular examples for loss functions are the squared error loss L = (ŷ − y) 2 (for numeric labels y ∈ R) or the logistic loss L = log(1 + exp(−h(x)y)) (for binary labels y ∈ {−1, 1}).
A widely used principle for learning a predictor map is empirical risk minimization (ERM). The idea of ERM is to learn a predictor map with small training error [2] , [7] , [10] 
The training error is computed on a set of labelled data points
for which we know the true label values y (i) . The set D denotes all available labeled data points. The training error E(g) is the average loss incurred on some labelled (training) data T ⊆ D . The most direct implementation of the ERM principle is to learn a predictor map via solvingĝ ∈ arg min g∈H E(g).
In general we use a strict subset T ⊂ D of all labeled data points to compute the training error (2) . The remaining data points D \ T , which are not used for the training, are then used to validate the predictor learnt via (4) [7] , [11] .
The direct form (4) of ERM is rarely used in practice since it is prone to overfitting. Overfitting happens when the size of the hypothesis space is much larger than the number of training data points. As a rule of thumb, for ERM (4) to work we should have several times more training data points than tunable (learnable) parameters of the hypothesis space. Current deep neural networks involves billions of tunable parameters. However, it is often not feasible to aquire billions of labelled training examples.
To avoid overfitting we can use regularization strategies. Loosely speaking, regularization aims at estimating or anticipating how much the average loss would increase on new data which is different from the training data. We then add this estimated increase as an additive ("regularization") term to the ERM (4),ĝ ∈ arg min g∈H E(g) + λR(g).
The regularization parameter λ ≥ 0 in the regularized ERM (5) allows to trade smaller training error (small λ) against weaker regularization. A different implementation of regularization is via adding a constraint to the ERM,
For the hypothesis space constituted by linear maps g(x) = w T x, we obtain ridge regression as the special case of (5) with the regularizer R(g) = w 2 = n i=1 w 2 i . Another special case using linear predictor maps is the least absolute shrinkage and selection operator (Lasso). We obtain the Lasso from (5) for the choice R(h) = w 1 = n i=1 |w i |. Somewhat different to ridge regression and Lasso, our choice for the regularizer R(g) is not directly motivated by robustness or sparsity. Instead, we propose a regularizer that measures, in a sense made precise below, the explainability of the predictionŝ y = g(x) to a specific user.
Assume we have learnt a predictorĝ via regularized ERM (5). We can then apply this predictor to new data points (outside the training data T ) to obtain the predictionŷ =ĝ(x). The predictionŷ is often delivered to human users with varying background knowledge on ML principles. Indeed, some users might have a university degree in ML while other users might have no formal training in statistics.
Depending on her background, the user often has some intuition for the relation between features x and label y of a data point. We can think of this intuition as some crude model that has been built up during past experiences. To characterize the user intuition we allow her to provide some "user summary" u ∈ R for a given data point.
For ease of exposition, we assume that the user summary is obtained by a deterministic map u(·) : R n → R : x →û := u(x).
However, we expect our approach to be readily extended to user summaries obtained via stochastic maps (a conditional probability distribution) p(û|x). We interpretû as a "summary" formed by the user about a data point based on its features x and the user knowledge. In what follows, we formally identify a user with the function u(·) that maps the features of a given data point to the user summaryû = u(x) Let us illustrate the concept of a user summary by two examples. Consider a user that is able to implement linear regression using a single hand-picked feature of a data point (spreadsheet row in Figure 1 ). Here, a user summary could be the prediction obtained from a linear regression using few features (see Figure 1 ). For facial pictures, a user summary u could be a course characterization of the eye-spacing [9] (see Figure 2 ).
To study the explainability of a predictionŷ delivered to a user u(·), we use a simple probabilistic model (see Figure  3 ). We interpret the features x and label y of data points as realizations of random variables with joint distribution p(x, y). Our approach does not require knowledge of the Note that the predictionŷ = h(x) and user summaryû = u(x) are random variables as they are obtained by applying maps to the random features x. We tacitly assume the existence of a joint probability density function for the random variableŝ y and u(x).
We propose to measure the (lack of) explainability ofŷ = g(x) via the conditional (differential) entropy [5, Ch. 2 and 8] h(ŷ|û) := −E log p(ŷ|û) .
The conditional entropy (8) measures uncertainty about the predictionŷ given the user summaryû = u(x). Smaller values h(ŷ; u) correspond to smaller levels of uncertainty in the predictionsŷ that the user u experiences. We aim at learning a predictor h ∈ H such that the user has minimal uncertainty h(ŷ|û) about the predictionsŷ = h(x) obtained for a random data point. The preference for predictors incurring a small h(ŷ|û) serves the basic human need to understand observed phenomena, such as the predictions from a ML method [13] .
We now combine the parts developed in Section II to learn a predictor that is intrinsically explainable to a given user u. The idea is to use the explainability measure (8) to regularize empirical risk minimization. In particular, we define explainable empirical risk minimization (EERM) aŝ
Note that the random variableŷ in the constraint of (9) is obtained by applying the predictor map h ∈ H to the features,
The constraint h(ŷ|û) ≤ η of EERM (9) enforces the resulting predictorĝ to be sufficiently explainable in the sense that the conditional entropy h(ĝ|û) ≤ η does not exceed a prescribed level η.
To gain more insight into the properties of EERM, we consider the hypothesis space of linear maps g (w) (x) := w T x with some weight vector w ∈ R n . (10)
Moreover, we assume that the features x of a data point and its user summary u are jointly Gaussian with mean zero and covariance matrix C,
Under the assumptions (10) and (11) 
Here, we used the conditional variance σ 2 y|û ofŷ given the random user summary u = u(x). Inserting (12) into the generic form of EERM (9),
By the monotonicity of the logarithm, (13) is equivalent tô
To further develop (15), we use the identity
The identity (15) relates the conditional variance σ 2 y|û to the minimum mean squared error that can be achieved by estimatingŷ using a linear estimator αû with some α ∈ R.
Using (15) and assumption (10), we can formulate (14) aŝ g ∈ arg min w∈R n ,α∈R
Note that the inequality constraint in (16) 
By convex duality, for a given threshold e η in (16), we can find a value for λ in (17) such that (16) and (17) have the same solutions [3, Ch. 5] .
In order to actually use (17) to learn an explainable predictor g we need to replace the expectation E w T x − αû 2 by a sample average on i.i.d. training data x (i) ,ŷ (i) ,û (i) for i = 1, . . . , m. We have proposed EERM to learn predictors that are explainable in a certain sense. In particular, we regularize empirical risk minimization using an information-theoretic measure for the explainability of the predictions to a given user. Thus, we learn predictors that are intrinsically explainable to individual users. We have spelled out our approach for the special case of linear least squares regression and using a simple probabilistic model for the data and user.