Optimal probabilistic feature shifts for reclassification in tree ensembles

Víctor Blanco † , Alberto Japón ‡,⋆ , Justo Puerto ‡ , and Peter Zhang ⋆ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla ⋆ Heinz College of Information Systems and Public Policy, Carnegie Mellon University · 2024

Read Optimal probabilistic feature shifts for reclassification in tree ensembles by Víctor Blanco † , Alberto Japón ‡,⋆ , Justo Puerto ‡ , and Peter Zhang ⋆ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla ⋆ Heinz College of Information Systems and Public Policy, Carnegie Mellon University (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03722.txt.

Introduction

Víctor Blanco and co-authors published a research paper in 2024 on the cheapest realistic way to nudge a classified case into a desired class. The classifier is a forest of decision trees. The nearest point of the target class is not always the smartest target: people can only change a few features, and each change carries its own chance of success.

Their optimization finds the feature shifts that maximize the probability of reclassification, rather than the smallest distance. The same machinery ranks which features matter most inside the ensemble. Tested on a real data set, the method produced sensible, achievable change plans. The work serves recourse problems, like telling a loan applicant what would actually flip a decision.

Catalog record

CREATORVíctor Blanco † , Alberto Japón ‡,⋆ , Justo Puerto ‡ , and Peter Zhang ⋆ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla ⋆ Heinz College of Information Systems and Public Policy, Carnegie Mellon University
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE63 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03722

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal probabilistic feature shifts for reclassification in tree ensembles Víctor Blanco † , Alberto Japón ‡,⋆ , Justo Puerto ‡ , and Peter Zhang ⋆ † Institute of Mathematics (IMAG), Universidad de Granada ‡ Institute of Mathematics (IMUS), Universidad de Sevilla ⋆ Heinz College of Information Systems and Public Policy, Carnegie Mellon University Abstract . In this paper we provide a novel mathematical optimization based methodology to perturb the features of a given observation to be re-classified, by a tree ensemble classification rule, to a certain desired class. The method is based on these facts: the most viable changes for an observation to reach the desired class do not always coincide with the closest distance point (in the feature space) of the target class; individuals put effort on a few number of features to reach the desired class; and each individual is endowed with a probability to change each of its features to a given value, which determines the overall probability of changing to the target class. Putting all together, we provide different methods to find the features where the individuals must exert effort to maximize the probability to reach the target class. Our method also allows us to rank the most important features in the tree-ensemble. The proposed methodology is tested on a real dataset, validating the proposal. [email protected] , [email protected] , [email protected] , [email protected] 1. Introduction Nowadays, machine learning models are used in a wide range of knowledge areas such as health care, transportation, finance, etc. Models are commonly required to fulfill certain characteristics that depend on the area of study, but generally there are two main features that stand out: precision and interpretability. For example, the classification models used to predict whether a credit card transaction is fraudulent or not, are as most accurate as possible, while it is less important to understand the rules that the model uses [ 22 ] . On the other hand, there are other cases where besides accuracy, it is of vital importance to understand the classifier itself. For example when predicting a certain disease outcome, being able to interpret the disease progression implied by a model could be important to understand the nature of the disease, or how to mitigate it. Consequently, given the numerous advantages of using interpretable machine learning models for acquiring knowledge, they have been widely studied and have attracted much interest in recent years (see [ 26 ] ). When thinking about interpretable machine learning, the first fundamental aspect to consider is the global interpretability of the model and how the variables of the problem interact. Linear and logistic regression are some of the preferred models because of their easy and manageable interpretation. In addition, different techniques, such as lasso or robust regression (see [ 29 , 30 ] ) can be used to reduce the number of features to be interpreted within the models, which can significantly reduce the complexity of the task. On the other hand, decision tree-based models with univariate splits, or decision forests when they are of moderate size, are also very popular since the solutions can be reduced to a set of concatenated univariate decisions that can be easily followed and have a simple visual representation. In the latter, advances have been made in the field of mathematical optimization to derive optimal models that, smaller than their heuristic counterparts and reducing the number of univariate decisions to be interpreted, do not sacrifice accuracy when working with small to medium-sized data sets. In particular, in [ 1 ] and [ 3 ] the authors introduce Optimal Classification Trees (OCT) and Weighted Optimal Classification Forests, respectively, which have been proven to be useful in the design of interpretable classification tools. The multiple advantages of being able to interpret models globally are so widely spread that it can even be seen in [ 7 ] and [ 19 ] different ways of extracting decision trees from complex models such as neural networks, to try to understand how these models work internally. On the other hand, there are cases in which, in addition to understanding the global functioning of the model, which may or may not be possible, it is of great interest to understand the prediction pathways for specific data points. For example, in binary classification, we will be interesting in understanding why a negative label prediction is assigned to a particular observation. Specifically, we derive feasible changes in the feature values of this observation to be predicted in the desired label. We will call the new perturbed observation the feature shifts (FS) vector. The analysis of the best feature shifts for a given observation allows us to develop causal studies and open up predictive models to interventions results [ 14 , 15 ] . The classical example in this type of studies is the case of an individual who applies for a mortgage loan in a bank and this is rejected (by certain classification rule). In this case, it would be beneficial for both the bank and the applicant to understand what the individual could change (assuming the classification tool stays the same) in the near future (e.g., if applicable, try to increase its salary), so that the loan would be granted, allowing the individual to buy the property and the bank to benefit from the loan. Nevertheless, to provide explanations on the reasons why an observation failed to be positively classified, it is clear, that the classification method must be explainable and interpretable. Furthermore, understanding how to repair undesirable classification labels may have direct implications in the design of strategies, as for instance, in the development of public policies to palliate a disease, traffic accidents, suicides, etc. The study of FSs has been carried out in numerous models and applications, from the most interpretable to the most opaque or black-box models [ 16 , 28 , see e.g.] . In our work, we focus on the study of FSs solutions for tree ensembles under mathematical optimization lens. Although this is not new, as it has already been studied in [ 6 ] or [ 24 ] , we take a different approach based on the feasibility of change for each individual, which can provide several advantages. Most of the proposals to derive FSs are distance-based models. They construct the most appropriate changes to perform on the features of one or more individuals to be classified as positive, using the closest-distance rule and the solution is the closest point (with respect to a given distance) in the feature space to the observation/s. A drawback of this type of feature shifts is that the solutions may sometimes not be entirely satisfactory, since they do not necessarily reflect how feasible it is in practice for the observations to achieve the proposed solutions. For instance, if the feature shifts proposed in the solution for an observation is very different from the rest of the data, it may be perceived as impractical or impossible to achieve. On top of that, when using a distance-based approach, the solutions can sometimes fall very close to the decision boundary of the classifier, which makes them unstable to small perturbations of the classifier itself. Faced with these scenarios, in [ 10

Read the complete text