Enhancing Classification and Regression Tree-Based Models by means of Mathematical Optimization

Description

Esta tesis combina las disciplinas de Investigación Operativa y Aprendizaje Automático a través del desarrollo de formulaciones de Optimización Matemática y algoritmos de resolución numérica para construir modelos basados en árboles de clasificación y regresión. A diferencia de los árboles de clasificación y regresión clásicos, generados de manera heurística y voraz, construir un árbol a través de un problema de optimización nos permite incluir fácilmente propiedades estructurales globales deseables. En esta tesis, ilustramos esta flexibilidad para modelar los siguientes aspectos: sparsity, como sinónimo de interpretabilidad, controlando el número de coeficientes no nulos, el número de variables predictoras y, si son funcionales, la proporción de dominio usado en la predicción; un criterio social importante, la equidad del modelo, evitando predicciones que discriminen a algunos individuos por su etnia u otras características sensibles; y la sensibilidad al coste de grupos de riesgo, asegurando un rendimiento aceptable para ellos. Además, con este enfoque se obtiene de manera natural el impacto que las variables predictoras continuas tienen en la predicción de cada individuo, mejorando así la explicabilidad local de los modelos de clasificación y regresión basados en árboles. Todos los enfoques propuestos en esta tesis se formulan a través de problemas de Optimización Continua que son escalables con respecto al tamaño de la muestra de entrenamiento, se estudian desde el punto de vista teórico, se evalúan en conjuntos de datos reales y son competitivos frente a los procedimientos habituales. Esto, junto a las buenas propiedades resumidas en el párrafo anterior, se ilustra a lo largo de los diferentes capítulos de esta tesis. La tesis se estructura de la siguiente manera. El estado del arte sobre árboles de decisión (óptimos) se discute ampliamente en el Capítulo 1, mientras que los cuatro capítulos siguientes exponen nuestra metodología. El Capítulo 2 introduce de forma detallada el marco general que hila los capítulos de esta tesis: un árbol aleatorizado con cortes oblicuos. En particular, presentamos nuestra propuesta para tratar problemas de clasificación, la cual construye la probabilidad de pertenencia a cada clase ajustada a cada individuo, a diferencia de las técnicas más populares existentes, en las que a todos los individuos en el mismo nodo hoja se les asigna la misma probabilidad. Se tratan con éxito preferencias en las tasas de clasificación en clases críticas mediante restricciones de sensibilidad al coste. El Capítulo 3 extiende la metodología de clasificación del Capítulo 2 para tratar adicionalmente sparsity. Esto se modela mediante regularizaciones con normas poliédricas que se añaden a la función objetivo. Se estudian propiedades teóricas del árbol más sparse, y se demuestra nuestra habilidad para sacrificar un poco de precisión en la clasificación por una ganancia en sparsity. En el Capítulo 4, los resultados obtenidos en los Capítulos 2 y 3 se adaptan para construir árboles sparse para regresión. Se exploran propiedades teóricas de las soluciones. Los experimentos numéricos demuestran la escalabilidad de nuestro enfoque con respecto al tamaño de la muestra de entrenamiento, y se ilustra cómo se generan las explicaciones locales en las variables predictoras continuas. Además, mostramos cómo esta metodología puede reducir la discriminación de grupos sensibles a través de las denominadas restricciones de justicia. El Capítulo 5 extiende la metodología de regresión del Capítulo 4 para considerar variables predictoras funcionales. De manera simultánea, la detección de un número reducido de intervalos que son críticos para la predicción es abordada. La sparsity en la proporción de dominio de las variables predictoras funcionales a usar se modela también a través de un término de regularización añadido a la función objetivo. De esta forma, se ilustra el equilibrio obtenido entre la precisión de predicción y la sparsity en este marco. Por último, el Capítulo 6 cierra la tesis con conclusiones generales y líneas futuras de investigación.

Abstract

This PhD dissertation bridges the disciplines of Operations Research and Machine Learning by developing novel Mathematical Optimization formulations and numerical solution approaches to build classification and regression tree-based models. Contrary to classic classification and regression trees, built in a greedy heuristic manner, formulating the design of the tree model as an optimization problem allows us to easily include, either as hard or soft constraints, desirable global structural properties. In this PhD dissertation, we illustrate this flexibility to model: sparsity, as a proxy for interpretability, by controlling the number of non-zero coefficients, the number of predictor variables and, in the case of functional ones, the proportion of the domain used for prediction; an important social criterion, the fairness of the model, which aims to avoid predictions that discriminate against race, or other sensitive features; and the cost-sensitivity for groups at risk, by ensuring an acceptable accuracy performance for them. Moreover, we provide in a natural way the impact that continuous predictor variables have on each individual prediction, thus enhancing the local explainability of tree models. All the approaches proposed in this thesis are formulated through Continuous Optimization problems that are scalable with respect to the size of the training sample, are studied theoretically, are tested in real data sets and are competitive in terms of prediction accuracy against benchmarks. This, together with the good properties summarized above, is illustrated through the different chapters of this thesis. This PhD dissertation is organized as follows. The state of the art in the field of (optimal) decision trees is fully discussed in Chapter 1, while the next four chapters state our methodology. Chapter 2 introduces in detail the general framework that threads the chapters in this thesis: a randomized tree with oblique cuts. Particularly, we present our proposal to deal with classification problems, which naturally provides probabilistic output on class membership tailored to each individual, in contrast to the most popular existing approaches, where all individuals in the same leaf node are assigned the same probability. Preferences on classification rates in critical classes are successfully handled through cost-sensitive constraints. Chapter 3 extends the methodology for classification in Chapter 2 to additionally handle sparsity. This is modeled by means of regularizations with polyhedral norms added to the objective function. The sparsest tree case is theoretically studied. Our ability to easily trade in some of our classification accuracy for a gain in sparsity is shown. In Chapter 4, the findings obtained in Chapters 2 and 3 are adapted to construct sparse trees for regression. Theoretical properties of the solutions are explored. The scalability of our approach with respect to the size of the training sample, as well as local explanations on the continuous predictor variables, are illustrated. Moreover, we show how this methodology can avoid the discrimination of sensitive groups through fairness constraints. Chapter 5 extends the methodology for regression in Chapter 4 to consider functional predictor variables instead. Simultaneously, the detection of a reduced number of intervals that are critical for prediction is performed. The sparsity in the proportion of the domain of the functional predictor variables to be used is also modeled through a regularization term added to the objective function. The obtained trade off between accuracy and sparsity is illustrated. Finally, Chapter 6 closes the thesis with general conclusions and future lines of research.

Additional details