Cristina Molero-Río
Laboratoire d’Informatique École Polytechnique
0000-0002-9600-4799
molero@lix.polytechnique.fr
Directores:
Rafael Blanquero (Universidad de Sevilla)
Emilio Carrizosa (Universidad de Sevilla)
Dolores Romero Morales (Copenhagen Business School)
Palabras Clave: Árboles óptimos de clasificación y de regresión, Datos funcionales multivariantes, Equidad, Explicabilidad local, Programación no lineal, Sparsity, Sensibilidad al coste.
MSC Clasificación por Temas: 62H99, 68T01, 90C30.
Esta tesis doctoral (Molero-Rı́o 2022) combina las disciplinas de aprendizaje automático e investigación operativa. En particular, contribuye a la mejora de los modelos de clasificación y de regresión basados en árboles mediante el desarrollo de nuevas formulaciones de optimización matemática.
Los árboles de clasificación y de regresión se diseñaron inicialmente para datos tabulares. Ver la parte izquierda de la Figura 1.
| Muestra | Clasificación | Regresión | ||
|---|---|---|---|---|
| Cliente | Edad | Nivel de | Préstamo | Gastos de |
| ingresos | devuelto | alquiler | ||
| 1 | 22 | Bajo | No | 500 |
| 2 | 26 | Alto | No | 600 |
| 3 | 30 | Bajo | Sí | 700 |
| 4 | 32 | Bajo | No | 750 |
| 5 | 20 | Alto | No | 550 |
| 6 | 45 | Alto | Sí | 1100 |
| 7 | 60 | Alto | No | 900 |
| 8 | 54 | Alto | Sí | 1000 |
| 9 | 50 | Bajo | No | 650 |
| 10 | 48 | Alto | Sí | 1050 |
Imaginemos que tenemos como problema de clasificación la concesión de un préstamo. Para ello, partimos de una muestra, conjunto de observaciones, constituida por antiguos solicitantes del préstamo que vienen caracterizados por su edad y su nivel de ingresos. Con esta información, el modelo tratará de predecir si el préstamo fue finalmente devuelto o no. En la parte derecha de la Figura 1, puede observarse en azul el árbol de clasificación correspondiente. Si predijéramos un valor numérico, como los gastos de alquiler del solicitante, tendríamos un árbol de regresión como el que se intuye en magenta.
Un árbol de clasificación o de regresión consiste en la partición recursiva de la muestra en subconjuntos de observaciones cada vez más pequeños, a los que se denomina nodos. Los nodos rama son aquéllos sobre los que se aplican los cortes que dividen la muestra según condiciones impuestas sobre las variables predictoras, mientras que sobre los nodos hoja se asocian las predicciones. Éstos aparecen representados mediante círculos y cuadrados, respectivamente, en la Figura 1. Dado que la construcción óptima de árboles es un problema NP-completo, la literatura se ha centrado tradicionalmente en el diseño de heurísticas basadas en procedimientos de partición secuencial y voraz sencillos que generan cortes univariantes. Esto requiere un esfuerzo computacional bajo que puede dar lugar a cortes potencialmente subóptimos.
Gracias a los avances en las últimas décadas tanto en el hardware como en los solvers de optimización, existe un creciente interés en desarrollar enfoques para construir árboles óptimos de clasificación y de regresión, donde el procedimiento de división voraz se reemplaza por una estrategia global donde todos los cortes en el árbol se deciden a la vez. La mayoría de estos paradigmas están basados en optimización lineal entera mixta, así como en programación con restricciones, programación dinámica y satisfactibilidad booleana, entre otros. Nuestra propuesta, un enfoque de optimización continua. Una revisión de la literatura sobre árboles (óptimos) de clasificación y de regresión se hace en el Capítulo 1 (Carrizosa, Molero-Rı́o, and Romero Morales 2021).
En comparación a los métodos ya propuestos que implementan cortes determinísticos, modelamos cortes probabilísticos que se definen a través de la inclusión, en cada nodo rama, de una función de densidad univariante suave. Por tanto, en cada nodo rama, cada observación tiene una probabilidad de tomar la rama izquierda y la derecha. Así, cada nodo hoja no contendrá un subconjunto de observaciones sino todas ellas con una cierta probabilidad. Finalmente, se asignará a cada nodo hoja aquella predicción que minimice el error de predicción sobre toda la muestra. Además, proponemos una generalización de los cortes, permitiendo que sean multivariantes, y de las predicciones en el caso de regresión, permitiendo asimismo una predicción lineal en cada nodo hoja. En los Capítulos 2 (Blanquero et al. 2021) y 3 (Blanquero et al. 2020) detallamos nuestra propuesta para la construcción de árboles óptimos de clasificación y de regresión para datos tabulares.
A diferencia de los enfoques clásicos, generados de manera heurística y voraz, construir un árbol a través de un problema de optimización nos permite incluir explícitamente propiedades deseables en el área del aprendizaje automático. Esta tesis ilustra dicha flexibilidad para modelar los siguientes aspectos.
La sparsity, como sinónimo de interpretabilidad; controlando el número de variables predictoras usadas en los cortes así como en todo el árbol. Este aspecto se modela mediante regularizaciones con normas poliédricas que se añaden a la función objetivo. Para más detalle, ver el Capítulo 3 (Blanquero et al. 2020), donde se precisa el caso de clasificación y se obtiene empíricamente una mejora de la sparsity del modelo sin perjudicar la precisión en la predicción.
La equidad; evitando predicciones que discriminen grupos con características sensibles, como el género o la etnia. Este aspecto se modela mediante restricciones. Por ejemplo, en el caso de regresión, puede imponerse que la predicción media del modelo en tal grupo no difiera en exceso de la de toda la muestra. Para más detalle, ver el Capítulo 4 (Blanquero et al. 2022), donde se demuestra que somos capaces de obtener un modelo justo, a costa de perjudicar ligeramente la precisión en la predicción.
La sensibilidad al coste; asegurando cierto rendimiento para grupos de riesgo, como los pacientes de cierta enfermedad. Este aspecto se modela mediante restricciones. Por ejemplo, en el caso de clasificación, puede ocurrir que clasificar erróneamente tenga diferentes consecuencias para las distintas clases. Por tanto, puede imponerse que el rendimiento sobre la clase crítica satisfaga cierto umbral. Para más detalle, ver el Capítulo 2 (Blanquero et al. 2021), donde se demuestra que somos capaces de mejorar nuestro poder de clasificación sobre la clase crítica.
Además, gracias a que la función predictora resultante de nuestro enfoque es suave por construcción, se deriva de manera natural el impacto que tienen las variables predictoras continuas sobre la predicción de cada observación, mejorando así la explicabilidad local de los modelos basados en árboles. Para más detalle, ver el Capítulo 4 (Blanquero et al. 2022), donde tras linealizar dicha función predictora y obtener el vector de derivadas parciales con respecto a las variables predictoras continuas, se identifican cuáles de ellas son las que más afectan a la predicción.
Por último, nuestro enfoque puede tratar observaciones de naturaleza funcional multivariante. Para más detalle, ver el Capítulo 5 (Blanquero et al. 2023), donde adaptamos nuestra metodología a este tipo de datos complejos en el caso de regresión. De manera simultánea, se lleva a cabo la detección de un número reducido de intervalos críticos para la predicción, produciendo así un resultado más interpretable. En este marco entra en juego un tipo adicional de sparsity, la cual controla la proporción de dominio de las variables predictoras funcionales usada, y se modela mediante un término de regularización.
Junto a estas buenas propiedades, nuestro enfoque es estudiado teóricamente, es competitivo frente a los métodos de predicción de referencia en conjuntos de datos reales, y es escalable con respecto al tamaño de la muestra pues no existen variables de decisión asociadas a cada observación. El Capítulo 6 cierra la tesis con conclusiones generales y posibles líneas futuras de investigación.
Como curiosidad, los árboles óptimos de regresión desarrollados en esta tesis se usaron en combinación con otros regresores para predecir la evolución de la COVID-19 en España. Ver (Benı́tez-Peña et al. 2021).
Agradecimientos
Esta investigación ha sido financiada parcialmente por los siguientes proyectos de investigación: FQM-329, P18-FR-2369 y US-1381178 (Junta de Andalucía); FUNDBBVA/016/005 (Fundación BBVA); MTM2015- 65915-R y PID2019-110886RB-I00 (Ministerio de Ciencia, Innovación y Universidades, España); EC H2020 MSCA RISE NeEDS (Grant agreement ID: 822214, Comisión Europea). Este apoyo es altamente agradecido.