Explainable Machine Learning: Mathematical Optimization in Counterfactual Analysis

BACHELOR’S DEGREE FINAL PROJECT Explainable Machine Learning: Mathematical Optimization in Counterfactual Analysis Presented by: Agust´ın Mart´ın Ag¨uera Supervised by: Dr. Emilio Carrizosa Priego FACULTY OF MATHEMATICS Statistics and Operational Research Department Sevilla, June 2022 Abstract Counterfactual Analysis is a recent field of Explainable Machine Learning focused on the development of methods to provide human-understandable explanations for the results of predictive models. Further research and advancement in the area is deemed fundamental on account of the rapidly spreading usage of Machine Learning algorithms in human-impacting automated decision-making processes. In this work we present an approach to Counterfactual Analysis through the formulation of optimization programs, posing single-objective and multi-objective problems that lead to counterfactual generation. We then particularize them for specific choices of classifier model and parameters, though further options are outlined. Computational experiments are conducted and reported for the multiobjective approach. 3 4 Resumen El An´alisis Contraf´actico es un ´area de creaci´on reciente dentro del Aprendizaje Autom´atico Explicable, que se centra en el desarrollo de t´ecnicas que permitan obtener explicaciones aptas para interpretaci´on humana para los resultados de modelos predictivos. Dada la r´apida expansi´on de los algoritmos de Aprendizaje Autom´atico en sistemas de decisi´on autom´atica que tienen consecuencias directas sobre vidas humanas, la investigaci´on en este campo se vuelve fundamental. En este trabajo tratamos el An´alisis Contraf´actico desde la formulaci´on de programas de optimizaci´on matem´atica, proponiendo problemas de un solo objetivo y multiobjetivo. Posteriormente los particularizamos para elecciones espec´ıficas de modelo de clasificaci´on y par´ametros; aunque dejamos indicadas otras opciones. Por ´ultimo, presentamos resultados num´ericos de la aplicaci´on a un caso pr´actico de problemas de la variedad multiobjetivo. 5 6 Contents Abstract 3 Resumen 5 1 Introduction 9 1.1 Machine Learning in automated decision-making . . . . . . . . . . 9 1.2 Counterfactual Analysis . . . . . . . . . . . . . . . . . . . . . . . 10 2 Previous results 13 2.1 Supervised Classification . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Optimization problems . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Multi-objective optimization . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 The Weighting Method . . . . . . . . . . . . . . . . . . . . 17 3 Counterfactual Optimization Problems 19 3.1 Afirstapproach............................ 19 3.2 A multi-objective approach . . . . . . . . . . . . . . . . . . . . . . 20 3.3 On the flexibility of the problems . . . . . . . . . . . . . . . . . . 21 4 Classification models 25 4.1 Variableencoding........................... 25 4.2 LinearClassifiers ........................... 26 4.3 LogisticRegression .......................... 26 4.3.1 Thebinarycase........................ 27 4.3.2 Computation ......................... 27 4.3.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . 28 4.4.1 Computation ......................... 29 4.4.2 Non-linear SVM and kernel methods . . . . . . . . . . . . 30 4.4.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . 31 7 8CONTENTS 5 Particularization of Counterfactual Problems 33 5.1 The Simple Counterfactual Optimization Problem . . . . . . . . . 35 5.2 The Multi-objective Counterfactual Optimization Problem . . . . 38 6 Numerical Illustration 41 6.1 The German Credit Data dataset . . . . . . . . . . . . . . . . . . 41 6.2 Training the classifiers . . . . . . . . . . . . . . . . . . . . . . . . 42 6.3 Constraints and other settings . . . . . . . . . . . . . . . . . . . . 43 6.4 Results................................. 44 6.5 Some comments on the results . . . . . . . . . . . . . . . . . . . . 49 References 51 Chapter 1 Introduction 1.1 Machine Learning in automated decisionmaking Machine Learning (ML) is the field that seeks to understand and build models with the ability to learn, that is, models that are trained on data to improve performance on some set of tasks [14]. As an extensively researched, computerized and effective tool, it is nowadays used in large-scale automation in many domains, which include but are not restricted to the objectives of Artificial Intelligence. Its applications range from the extraordinary to the mundane, where ML algorithms are often used to support decisions that directly impact human lives. Such is the case of their usage in credit lending [17], medical treatment [6] or talent sourcing [16]. However, Machine Learning algorithms can be wrong. In spite of the cleanness of their theoretical formulation, training a ML model is a complex process which requires a deep dive in the data at hand, good unbiased error estimators, and many subtle adjustments of the parameters of the model. Even when correctly trained, sometimes models will learn biases that, while present in the data, are not acceptable as criteria for decision-making in certain domains, such as sex or race. When there are hard consequences on the line for humans, these biases need to be identified and accounted for. More often than not this proves a challenging task due to the intricate complexity of some models, especially those trained over large volumes of data. This has led specialists in the field to coin the expression black box model, to refer to a predictive algorithm whose internal functioning is completely obscured. But even if no substantial bias is present, people deserve explanations about the machine- 9 16 CHAPTER 2. PREVIOUS RESULTS We will consider a multi-objective optimization problem of the form minimize {f1(x), f2(x), ...fK(x)} subject to x∈S(2.5) in which we have K≥2objective functions to minimize over a feasible set S. For this problem to be of interest, the objective functions must be conflicting in some way, which does not allow for the simultaneous minimization of them all. We usually denote the image of the feasible region, the outcome set, by Z=f(S), and its elements by z= (z1, z2, ..zK)T. These are the outcome vectors. We say a objective vector z∗dominates another objective vector zif z∗ i≤zi ∀i= 1...K and there is at least one jsuch that z∗ j< zj. This is to say, z∗offers a better value for objective function fj, without prejudice to any other objective function. An ideal outcome would be feasible (z∗∈Z) while dominating all other feasible solutions. Such vector is, more often than not, non-existent. This is the case in figure 2.1: z∗dominates all feasible outcomes, but is not feasible itself. Nonetheless, the notion of dominance gives rise the Pareto optimal set (POS). An objective vector zis said to be Pareto optimal if it feasible and it is not dominated by any other feasible objective vector. In figure 2.1, the Pareto optimal set is represented in red, while vector ˆ zis Pareto optimal. Z POS f2(x) f1(x) ˆ z z∗ Figure 2.1: Representation of an outcome set. Even when no ideal all-minimizing objective vector is available, it is sensible to search for a solution to the multiobjective problem within the POS, since all other 2.3. MULTI-OBJECTIVE OPTIMIZATION 17 feasible outcomes are dominated, and so they would give rise to less-than-optimal solutions. 2.3.1 The Weighting Method A wide range of strategies used to obtain satisfactory solutions to problem (2.5) involve the generation of (part of) the POS to choose a point from. These are named a posteriori methods [12], since the choice of optimal solution is made after the computations. We will be applying one of these: the Weighting Method, where each objective function is assigned a weight coefficient; and the weighted sum of the objectives is minimized. In this way the problem is reduced to a scalar one, to be solved through usual means. Problem (2.5) is thus modified into the following weighting problem, where coefficients ωiare real, non-negative numbers that add up to one. minimize PK i=1 wifi(x) subject to x∈S(2.6) There are results assuring Pareto-optimality of the solution of problem (2.6) if all weights are positive, or if the solution is unique. Furthermore, if the multiobjective optimization problem is convex, then every Pareto optimal point is solution to a weighting problem with an appropriate weighting vector [12]. Then, under convexity assumptions, one can generate any PO vector by solving the related weighting problem. In the bi-objective case there is only one degree of freedom in the values of the weights. This allows for an easy numeric exploration and representation of the POS, in such a way that a decision maker could easily contrast PO solutions to their preference. 18 CHAPTER 2. PREVIOUS RESULTS Chapter 3 Counterfactual Optimization Problems In this chapter we develop an approach to Counterfactual Analysis through mathematical optimization, proposing two alternative problems to pose and solve in order to get counterfactual explanations [2]. 3.1 A first approach A first idea is to find, for a misclassified instance, the closest (for some notion of closeness) feasible point in the desired region. Membership of such counterfactual to the desired class may be somewhat weak, as it is very near or even sitting on the border between classification regions. Thus, it might not be something to recommend to a user searching to change their classification, but it would offer insight on the classifier’s internal working. Definition 3.1.1 Let Xbe a space of predictor vectors, and C={1, . . . , K}a set of Klabels. Let g:X−→ C be a classification rule for the corresponding supervised classification problem. Furthermore, let us have: (1) A set of inequality constraints {hj(x)≤0}1≤j≤pto be imposed on the counterfactual. (2) A distance D:X×X−→ R Finally, let us have a point x0∈Xand a desired label k∈ C. Then the Simple Counterfactual Optimization Problem (SCOP) for x0into class kis arg minx∈XD(x,x0) subject to g(x) = k hj(x)≤0,1≤j≤p (3.1) 19 20 CHAPTER 3. COUNTERFACTUAL OPTIMIZATION PROBLEMS Observation 3.1.1 When the classifier in question makes use of scoring functions, the class condition in problem (3.1) may be written in terms of those scoring functions: g(x) = k⇐⇒ k= arg max 1≤k≤Kfk(x)⇐⇒ fk(x)≥fi(x),1≤i≤K, i =k (3.2) Furthermore, if it is a binary classification problem, then the class condition is written as a single inequality: g(x) = 1 ⇐⇒ f(x)≥0 (3.3) 3.2 A multi-objective approach We will propose another way of handling the validity condition; since as already stated, solutions to problem (3.1) are not likely to be robust. In the score-based case, one or many of the K−1 inequalities are likely to end up saturated while solving the optimization problem. Counterfactual xis then on the border of the desired region, and any slight change in the classifier’s internal settings may be capable of letting xback into misclassification. This is a concern, for instance, if the classifier in question is trained by a Online Machine Learning algorithm. Online Learning methods –as opposed to the usual Batch Learning methods– involve the sequential training of the model as new data becomes available. It is a common technique in situations where the classifier has a need to dynamically adapt to changes in the patterns of data [7]. Fortunately, we can find a solution for score-based classifiers, where scoring functions offer a measure of the certainty of classification in each class. Thus, we propose other formulation for the counterfactual optimization problem in these situations: to (i) minimize the distance to the original point while (ii) maximizing the difference between scores of the desired class and the rest. Definition 3.2.1 Let Xbe a space of predictor vectors, and C={1, . . . , K}a set of Klabels. Let {fk:X−→ R}1≤k≤Kbe the respective scoring functions for a supervised classification problem. Furthermore, let us have: (1) A set of inequality constraints {hj(x)≤0}1≤j≤pto be imposed on the counterfactual. (2) A distance D:X×X−→ R . Finally, let us have a point x0∈X; and for the sake of simplicity we will take Kas our desired label, without loss of generality. Then the Multi-objective 3.3. ON THE FLEXIBILITY OF THE PROBLEMS 21 Counterfactual Optimization Problem (MCOP) for x0into class Kis arg minx∈X{D(x,x0), f1(x)−fK(x), . . . , fK−1(x)−fK(x)} subject to hj(x)≤0,1≤j≤p(3.4) This is a multi-objective optimization problem with Kobjectives. Observation 3.2.1 The binary case is written rather simply in terms of the only scoring function as a two-objective optimization problem: arg minx∈X{D(x,x0),−f(x)} subject to hj(x)≤0,1≤j≤p(3.5) We propose the use of the Weighting Method as a tool to scalarize and solve to MCOP. Iterative solving through a sweep in the space of possible weights gives a variety of solutions from which to choose, attending to the trade-off between distance and scores. Figure 3.1 shows a simplified representation of this method for instance x. desirable region x x1 x2 x3 x4 x5 Figure 3.1: Different solutions to the MCOP for a given instance. 3.3 On the flexibility of the problems The definitions given above are general enough to accommodate for a variety of situations and approaches to the problem, as the choices of distance and constraints for a given problem are not unique; and different methods may report results of varying interest. Moreover, they will likely change the character of problems (3.1), (3.4) and (3.5) as optimization programs, and thus the algorithms that may be used to solve them. We first need to define space X, distance D, and constraints hj. 22 CHAPTER 3. COUNTERFACTUAL OPTIMIZATION PROBLEMS The predictor space X.In order to better handle and solve the classification problem, categorical and ordinal variables are usually encoded as binary and integer variables, respectively. Space Xis thus a product of the form Rm1×Zm2× {0,1}m3. This is, the (almost certain) presence of categorical or non-continuous variables always implies a mixed-integer character of the proposed problems. Distance D.The choice of distance between points is not free of consequence. If we focus on Minkowski metrics, we find an interesting array of features: •The L2 distance seems a natural choice of distance based on the geometric intuition of proximity. If we use (L2)2then the distance term is quadratic in the predictor variables, which is a desirable feature for the optimization problem. L2(x,x0) = X i (xi−x0i)2(3.6) •The L1 distance is similar to L2, but it assigns a greater distance to situations where the difference between points is spread between variables. This makes it an asset for promoting sparsity of the counterfactual. L1(x,x0) = X i |xi−x0i|(3.7) The L1 distance can be linearized by means of a norm cone, in order to keep the problem linear and convex. However, this introduces further real variables tiand new constraints. minimize L1(x,x0) subject to x∈X≡ minimize PM i=1 ti subject to x∈X ti∈R1≤i≤M xi−xi0≤ti1≤i≤M −(xi−xi0)≤ti1≤i≤M (3.8) •The L0 distance, as defined by expression (3.9), only reflects whether variables have the same value or differ. This makes it our best tool to promote sparsity. L0(x,x0) = X i I(xi, x0i),where I(x, x′) = 0 if x=x′ 1 if x=x′(3.9) 3.3. ON THE FLEXIBILITY OF THE PROBLEMS 23 To linearize the L0 distance, we may use the big-M method. This way, binary decision variables siand new constraints are introduced. The idea is that for every variable i,si= 1 if xi=x′ i,si= 0 otherwise. minimize L0(x,x0) subject to x∈X≡ minimize PM i=1 si subject to x∈X si∈ {0,1}1≤i≤M xi−xi0≤M′si1≤i≤M −(xi−xi0)≤M′si1≤i≤M (3.10) where M′needs to be large enough to account for every possible variation in a variable. A possible choice for it would be: M′= 2 max |(xi)j|(3.11) A convex combination of the three of them will be used in the formulation of the concrete problems that we will propose, so as to benefit from the features of all three. Furthermore, there is the question of standardization. Usually variables come in very different units and numeric ranges, which are not indicative of the relative difficulty of changing the value of the variable. If we think of the credit-lending example, the difficulty in changing one’s disposable income by 10 (euros) is not equivalent to that of changing one’s age by 10 (years). In the computation of distances, variables must be weighted to account for the units scales that they are expressed in –standardization– and their ”resistance to movement”. Thus, we will consider the weighted versions of L2 and L1 distances. But far from being an obstacle, this opens the door to new ways to further tailor the problems. One could, for example, ask users about their perceived relative difficulty in changing each variable; and use the input as a guide when computing weights for the variables. This human-supervised method would account for users’ preferences, which is a desirable feature for counterfactual generation. On the other hand, there is an argument for replacing the weighted L2 distance with the Mahalanobis distance, as the latter rewards closeness to the data manifold; and thus is likely to present counterfactuals that are more realistic than the former. Constraints hjreflect conditions that must hold true for a counterfactual to be feasible. For example, it would be nonsensical to suggest to an user that they decrease their age; or get a higher-income job while maintaining the duration of their current post. 24 CHAPTER 3. COUNTERFACTUAL OPTIMIZATION PROBLEMS Constraints can also be used to impose limits on the change of variable values, to prevent an excess of variation in any given one. They may also help enforce sparsity, by setting a hard maximum on the number of features that can change. For instance, a recent paper [11] sets the limit at 2 variables for a ”good” counterfactual. Finally, some variables may not be considered actionable, and so their values must stay fixed in the counterfactual generation. Chapter 4 Classification models In this chapter we give a brief presentation of the supervised classification models on which we will apply counterfactual analysis. We begin by assessing the case of logistic regression, as one of the simplest and most easily interpretable models. We then keep on with the Support Vector Machine model (SVM), a powerful and flexible method stemming from statistical learning. In SVMs, kernels methods are used to increase the model’s flexibility, altering the shape of the boundary that separates the two classes, and thus modifying the form of the validity condition in our counterfactual optimization problems. 4.1 Variable encoding Most classification models are designed to only accept numerical values as inputs, the implication being that categorical and ordinal variables must be encoded prior to their processing. Ordinal values are usually subject to integer encoding, which maps the ordered categories to integers so as to preserve the order relations. In contrast, categorical variables pass through one hot encoding. One-hot encoding maps a categorical variable cwith categories 1 . . . n to a vector (c1, . . . , cn)∈ {0,1}n, in such a way that cj= 1 if c=j,cj= 0 otherwise. This ensures a numerical codification in which no order relation is unwillingly introduced. It is also a common approach to get rid of one of the new variables, and let the null vector (0,...,0) represent the corresponding category. Subsequently, the predictor space Xis mapped to a subset of RM′. We will take this to be the case from now on. 25 32 CHAPTER 4. CLASSIFICATION MODELS Chapter 5 Particularization of Counterfactual Problems In this chapter we specify the forms of Simple Counterfactual Optimization Problem (3.1) and the Multi-objective Counterfactual Optimization Problem (3.4) for the aforementioned classification methods. Furthermore, we aim to write formulations that explicitly showcase every aspect of the problems, so as to ease numerical implementation. The feasible set Let us firstly consider the predictor variables. As stated in section 4.1, features are codified so that only numerical variables remain. The methods used to achieve this impose inherent constraints to the values that the newly created variables can take. This is, just by considering the result of encoding, we have for our problems: •Rcontinuous decision variables {r1, . . . , rR}. •Zinteger decision variables {z1, . . . , zZ}. •Oordinal-turned-integer decision variables {o1, . . . , oO}. •For each original ordinal feature, an lower and a upper bound to the values that the corresponding integer variable may take, typically 0 and number of levels - 1. This makes 2Obounds. •For each original categorical feature cjwith Njclasses, Njbinary decision variables cj,1, . . . , cj,Nj; making a total of B:=PjNjbinary variables. •For each original categorical feature cj, a linear equality restriction stating 33 34 CHAPTER 5. PARTICULARIZATION OF PROBLEMS that exactly one of the categories must be applicable in each case: Nj X l=1 cj,l = 1 1 ≤j≤C(5.1) This gives us a feasible set that is a subset of RR×ZZ+O× {0,1}B, with 2O bounds1and Clinear equality restrictions, that may be transformed into 2C linear inequality restrictions if so desired. With these, we ensure that solutions to the counterfactual problem are interpretable in terms of the original features. Actionability and feasibility constraints These enforce the viability of the counterfactual instances. We may face three different kinds in our formulation: bounds, inequalities and immutability conditions. The former two can be directly introduced in our model, while the last are a consequence of some features not being actionable, and their presence makes it worth reconsidering the need for some decision variables. For instance, an immutable categorical feature cjneeds not give rise to any binary decision variable or extra constraint. It can just be used to calculate the values of the scoring functions, and so the problems lose decision variables and constraints, and become simpler. We will choose to only formulate linear inequalities as part of the constraints, in order to keep the boundaries piece-wise linear. Note that for now our feasible space is a polyhedron intersected with a grid; as all constraints imposed are affine. The distance function As stated in section 3.3, we will propose a convex combination of weighted distances L0, L1 and L2, appropriately converted to provide a quadratic expression. The distance between an instance x0and the tobe-calculated counterfactual constitutes an objective function to be minimized. A slight tweak is needed for the application of the L0 distance on the categorical variables. In our current formulation, a change in value of a categorical feature is represented as a change in two binary variables, practically giving double weight to categorical features in the L0 distance. Thus, we will have to compensate for this effect by introducing a 0.5 factor in the corresponding terms. These comments are valid for all problems that we intent to formulate; but when tackling validity of the counterfactual, we must specify to keep on developing. 1We distinguish bounds from linear inequalities because of the difference that most solver softwares make between them. 5.1. THE SCOP 35 5.1 The Simple Counterfactual Optimization Problem The validity restriction In the Simple Counterfactual Optimization Problem, classification in the desired class is ensured by a hard restriction, which in the score-based case took the form of K−1 inequality constraints, as expressed in (3.2). We will take the K-th class as the desired one in the multi-class case, for the sake of simplicity of notation. The Simple Counterfactual Optimization Problem is then stated as: minimize a0PM i=1 cisi+a1PM i=1 biti+a2PM i=1 b2 i(xi−x0,i)2 subject to                rj∈R zj∈Z oj∈Z cj,l ∈ {0,1} 1≤j≤R 1≤j≤Z 1≤j≤O 1≤j≤C, 1≤l≤Nj          0≤oj≤uj PNj l=1 cj,l = 1 Ax≤b 1≤j≤O 1≤j≤C nfk(x)≤fK(x)1≤k≤K−1          si∈ {0,1} xi−xi0≤M′si xi−xi0≥ −M′si 1≤i≤M 1≤i≤M 1≤i≤M          ti∈R xi−xi0≤ti xi−xi0≥ −ti 1≤i≤M 1≤i≤M 1≤i≤M (5.2) 36 CHAPTER 5. PARTICULARIZATION OF PROBLEMS where we have noted x= (r1, . . . , rR, z1, . . . , zZ, o1, . . . , oO, c1,1, . . . , cC,NC)Tto simplify the expressions. Mis the dimension of x, and M′is the big-M constant that we proposed in (3.11). Bounds ujreflect the number of categories of each ordinal feature, as already stated. Weights biare given and reflect the ranges and resistance to change of the variables, as stated in section 3.3, while citake values on account of the interaction between the L0 distance and one-hot encoding. ci=0.5 if xiis a binary variable arising from a categorical feature 1 if it is not (5.3) Coefficients a0, a1, a2for the distances are also presumed to be known. For clarity, we have broken up the constraints into brackets, in such a way that: •The first one states the nature of the decision variables. •The second states the affine inequalities and bounds required for the welldefinition of the ordinal and categorical variables, as well as for feasibility and actionability. •The third presents the validity constraints, ensuring the desired classification. •The fourth and fifth are required for the linearization of norms L0 and L1, respectively. It is at the validity constraints that the problems for different classifiers behave separately. In the case of linear classifiers such constraints are affine, and so the resulting feasible space keeps its polyhedral character. In a multi-class Logistic Regression classifier setting, the validity condition takes the shape fk(x) = βT kx+βk0≤0,1≤k≤K−1 (5.4) In the binary Logistic Regression and the binary linear SVM settings, taking +1 as the desirable class, we get f(x) = βTx+β0≥0 (5.5) In both cases, problem (5.2) is a Mixed-Integer Convex Quadratic Program. 5.1. THE SIMPLE COUNTERFACTUAL OPTIMIZATION PROBLEM 37 In non-linear classifiers however these constraints may not even be convex, resulting in the loss of both the linear and convex characters of the set. In the binary non-linear SVM setting, the form of the validity constraint is f(x) = N X j=1 αjyjK(xj,x) + β0≥0 (5.6) and it is the kernel K(·,·) that determines the shape of the feasible region. In general, problem (5.2) will not exhibit convexity or any other characteristic that facilitates its solving. Resolution may be accomplished by heuristic or local search methods, but these do not ensure optimality of the reached counterfactual. 38 CHAPTER 5. PARTICULARIZATION OF PROBLEMS 5.2 The Multi-objective Counterfactual Optimization Problem The validity objective In the MCOP, classification in the desired class is not enforced but encouraged through maximization of the difference between scoring functions, which appear as separate objectives. The Multi-objective Counterfactual Optimization Problem is then stated as: minimize na0PM i=1 cisi+a1PM i=1 biti+a2PM i=1 b2 i(xi−x0,i)2, f1(x)−fK(x), . . . , fK−1(x)−fK(x)o subject to                rj∈R zj∈Z oj∈Z cj,l ∈ {0,1} 1≤j≤R 1≤j≤Z 1≤j≤O 1≤j≤C, 1≤l≤Nj          0≤oj≤uj PNj l=1 cj,l = 1 Ax≤b 1≤j≤O 1≤j≤C          si∈ {0,1} xi−xi0≤M′si xi−xi0≥ −M′si 1≤i≤M 1≤i≤M 1≤i≤M          ti∈R xi−xi0≤ti xi−xi0≥ −ti 1≤i≤M 1≤i≤M 1≤i≤M (5.7) The comments we made about the brackets in problem (5.2) are also in order here, with the exception of those about validity constraints. 5.2. THE MULTI-OBJECTIVE COUNTERFACTUAL OPTIMIZATION PROBLEM39 When reducing problem (5.7) to a single-objective one through the weighting method, the objective function takes the form C(x):=w0ha0PM i=1 cisi+a1PM i=1 biti+a2PM i=1 b2 i(xi−x0,i)2i+ +w1hf1(x)−fK(x)i+. . . +wK−1hfK−1(x)−fK(x)i(5.8) with weights w0, . . . , wK−1. In the case of linear classifiers all scoring functions are affine, and so the objective is a quadratic function of x. The resulting problem is then a Mixed- Integer Convex Quadratic Program. Furthermore, if the classification problem is binary, expression (5.8) is simplified to C(x):=w0"a0 M X i=1 cisi+a1 M X i=1 biti+a2 M X i=1 b2 i(xi−x0,i)2#−w1hβTx+β0i(5.9) The optimal values for w0and w1can be determined a posteriori, as a user decides how to balance both objectives. In this sense, it is useful to account for the interpretation of the scoring function in each setting: •The scoring function of a Logistic Regression classifier is a monotonous transformation of the probability of belonging to the desired class. P[1|X=x] = exp(βTx+β0) 1 + exp(βTx+β0)(5.10) Expressing the counterfactual instances in terms of ”changes to be made” and ”probability of belonging to the desired class” may then be the most intuitive way to approach the choice. •The scoring function of a SVM takes value 0 at the border between classes, and ±1 at the edge of the margins; so a score in (0,1) is classified in the desirable class, but remains somewhat atypical; while a score greater than 1 rests safely inside the desirable region. For non-linear classifiers the scoring objectives may not be convex, which again prevents an easy approach to the problem. In the binary SVM case, we have C(x):=w0ha0PM i=1 cisi+a1PM i=1 biti+a2PM i=1 b2 i(xi−x0,i)2i+ −w1hPN j=1 αjyjK(xj,x) + β0i(5.11) 40 CHAPTER 5. PARTICULARIZATION OF PROBLEMS Optimal weights w0and w1can be determined through the same strategy as the linear case; as the interpretation of the SVM scoring function does not vary when non-linear kernels are introduced. Chapter 6 Numerical Illustration In this chapter we apply the aforeposed problems to the generation of counterfactuals for a concrete dataset and classifiers. In order to do this, we previously encode categorical features and train a linear classifier of each type considered: Logistic Regression and linear SVM. Multi-objective Counterfactual Problems are then formulated and solved for various training instances and different values of the weights, offering a range of possible counterfactuals with associated measures of the certainty of classification. Our purpose here is to showcase a direct implementation of these problems and the obstacles and peculiarities that may arise as a result. 6.1 The German Credit Data dataset We have worked with the Statlog (German Credit Data) Data Set, as found at the Machine Learning Repository of the University of California, Irvine [4]. This dataset was collected by professor Dr. Hans Hofmann at Universit¨at Hamburg in 2000. It classifies people described by a set of attributes as good or bad credit takers, intending to help banks and other credit-lending institutions predict whether an application for a credit is worth the risk. The dataset contains 1000 instances of data, 700 of them labeled as good credit takers with the remaining 300 being bad. Variables included in it are categorical, ordinal, integer or continuous in nature; as described in table (6.1). Categorical features labeled with (*) lack instances in one of the categories. This absence of data may cause some coefficients to be undetermined during training, and so we have removed the empty categories for the sake of simplicity. 41 48 CHAPTER 6. NUMERICAL ILLUSTRATION Instance D Single man, 36 years old, asking for a 1374 DM credit in order to buy furniture or equipment. Installment rate is 1% of disposable income. Actual label is good application. w1Changes to be made Probability 0.00 None 0.38 0.87 Level increase in checking account status 0.53 0.90 Get a guarantor 0.86 Resolve other installment plans (banks) 0.92 Level increase in checking account status 0.92 0.95 Level increase in savings account status 0.96 0.96 Reduction in credit amount: 1236.6 DM 0.96 Reduction in installment rate: 0.9% Level increase in savings account status 0.97 Level increase in current employment duration 0.97 0.98 Resolve 1 of 1 existing credits 0.98 Level increase in savings account status Level increase in current employment duration Table 6.9: Counterfactuals for instance D, Logistic Regression classifier w1Changes to be made Score f 0.00 None -1.35 0.87 Resolve other installment plans (banks) -0.30 0.885 Level increase in checking account status 0.22 0.910 Get a guarantor 0.93 0.935 Level increase in checking account status 1.45 0.955 Level increase in checking account status 1.97 0.960 Level increase in savings account status 2.14 0.975 Reduction in credit amount: 1236.6 DM 2.29 Reduction in installment rate: 0.90% Level increase in current employment duration 0.980 Level increase in savings account status 2.45 0.985 Resolve 1 of 1 existing credits 2.73 Level increase in current employment duration 0.990 Level increase in savings account status 3.01 Table 6.10: Counterfactuals for instance D, Lineal SVM classifier 6.5. SOME COMMENTS ON THE RESULTS 49 6.5 Some comments on the results The Logistic and the linear SVM classifiers are sufficiently alike to offer very similar counterfactual instances. The most popular recommendations for the first steps seem to be: •Increasing the level of one’s checking account. •Getting someone to act as a guarantor for the credit. •Reducing the credit’s amount. Not that there are not minor-scale trends: all applicants stating new car as the purpose of the credit are recommended to change it to used car as their first suggestion, as is the case of instance B. Similarly, applicants with other installment plans are generally told soon to resolve them, as we see in instance D. Note that while these may seem obvious suggestions, they happen to achieve the greatest improvement in the score function with the smallest change in input. For instance, increasing the level of one’s savings account or resolving other existing credits are also reasonable courses of action, but appear consistently later as suggestions since they do not imply a sufficiently large increment in the score. An important aspect of the generation of these counterfactuals is the step size in the w1sweep. It would be ideal if each new counterfactual introduced changes in just one variable, so that we could isolate and weight the effects of each further change. Nevertheless this is often not the case. As an example we have table (6.5), wherein the same counterfactual is obtained for values w1= 0.87,0.88,0.89 but there is a sudden change in three variables for w1= 0.90. A smaller step size may have been able to generate an intermediate counterfactual, but would also have increased significantly the number of computations. We have chosen different values for our classifiers –0.1 for the Logistic, 0.05 for the SVM– to further showcase this effect, which is visibly more prevalent in the Logistic tables than in the SVM ones. Moreover, higher values of w1seem to need a smaller step size. The numerical results here given are supposed to serve as an illustration of both the capabilities of the method and the process of implementation. There is surely room for improvement in a finer tuning of the distance weights a0, a1, a2, a greater insight in the causal relations between variables, or in a deeper assessment of the resistance to movement of variables. 50 CHAPTER 6. NUMERICAL ILLUSTRATION We aim to show that, in general, the direct application of Counterfactual Problems to concrete classifiers is not uniquely defined, as there is room for subjectivity. Familiarization, direct handling of the database and a complete assessment of the situation at hand have proved to be essential to arrive at this formulation, able to give rise to sensible results. References [1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. isbn: 9780521833783. [2] Emilio Carrizosa, Jasone Ram´ırez-Ayerbe, and Dolores Romero Morales. “Generating Collective Counterfactual Explanations in Score-Based Classification via Mathematical Optimization”. In: (July 2021). doi:10.13140/ RG.2.2.22996.12168/1. [3] Emilio Carrizosa and Dolores Romero Morales. “Supervised Classification and Mathematical Optimization”. In: Computers & Operations Research 40.1 (2013). doi:10.1016/j.cor.2012.05.015.url:https://www. sciencedirect.com/science/article/pii/S0305054812001190. [4] Dheeru Dua and Casey Graff. UCI Machine Learning Repository. 2017. url:http://archive.ics.uci.edu/ml. [5] Official Journal of the European Union. Recital 71 EU GDPR. Last accessed 10 June 2022. url:https://www.privacy-regulation.eu/en/r71.html. [6] Daniel Faggella. “Machine Learning for Medical Diagnostics - 4 Current Applications”. In: (2020). url:https://emerj.com/ai-sector-overviews/ machine-learning-medical-diagnostics-4-current-applications/. [7] Oscar Fontenla-Romero et al. “Online Machine Learning”. In: Efficiency and Scalability Methods for Computational Intellect. Ed. by Boris Igelnik and Jacek M. Zurada. IGI Global, 2013. [8] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual. 2022. url: https://www.gurobi.com. [9] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning. Springer, 2001. isbn: 0387952845. [10] Alan Julian Izenman. Modern Multivariate Statistical Techniques: Regression, Classification, and Manifold Learning. Springer texts in statistics. Dordrecht: Springer, 2006. doi:10 . 1007 / 978 - 0 - 387 - 78189 - 1.url: https://cds.cern.ch/record/1338317. [11] Mark T. Keane and Barry Smyth. “Good Counterfactuals and Where to Find Them: A Case-Based Technique for Generating Counterfactuals for Explainable AI (XAI)”. In: CoRR abs/2005.13997 (2020). doi:10.48550/ ARXIV.2005.13997.url:https://arxiv.org/abs/2005.13997. 51 52 REFERENCES [12] Kaisa Miettinen. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, 1999. isbn: 0792382781. [13] Tim Miller. “Explanation in artificial intelligence: Insights from the social sciences”. In: Artificial Intelligence 267 (2019). doi:10 . 1016 / j . artint.2018.07.007.url:https://www.sciencedirect.com/science/ article/pii/S0004370218305988. [14] Tom Mitchell. Machine Learning. McGraw Hill, 1997. isbn: 0-07-042807-7. [15] F. Pedregosa et al. “Scikit-learn: Machine Learning in Python”. In: Journal of Machine Learning Research 12 (2011), pp. 2825–2830. [16] Kumba Sennaar. “Machine Learning for Recruiting and Hiring - 6 Current Applications”. In: (2019). url:https://www.aitimejournal.com/ @saurav.singla/machinelearning- topredict- creditrisk- inlending-industry. [17] Saurav Singla. “Machine Learning to Predict Credit Risk in Lending Industry”. In: (2020). url:https://www.aitimejournal.com/@saurav. singla/machinelearning- topredict- creditrisk- inlending- industry. [18] Sahil Verma, John Dickerson, and Keegan Hines. “Counterfactual Explanation for Machine Learning: A Review”. In: CoRR abs/2010.10596 (Oct. 2020). url:https://arxiv.org/abs/2010.10596. [19] Sandra Wachter, Brent Mittelstadt, and Chris Russel. “Counterfactual Explanations Without Opening the Black Box: Automated Decisions and the CDPR”. In: Harvard Journal of Law & Technology 31.2 (Nov. 2018). doi: 10.2139/ssrn.3063289.url:https://ssrn.com/abstract=3063289.