Modeling with Categorical Features via Exact Fusion and Sparsity Regularisation

Este artículo presenta un nuevo enfoque de estimación para regresión lineal de alta dimensión con predictores categóricos que combina la fusión exacta de niveles mediante programación entera mixta y la regularización de dispersión para lograr compresión del modelo, respaldado por algoritmos eficientes y garantías teóricas que demuestran su superioridad frente a los métodos existentes.

Lo esencial

¡Claro que sí! Imagina que estás intentando predecir el clima o las ventas de una tienda, pero tienes una lista de datos que es un poco caótica. Por ejemplo, tienes datos sobre "ciudades" (con miles de códigos postales diferentes) o "días de la semana" o "horas del día".

El problema es que si tratas cada código postal o cada hora como algo totalmente único, tu modelo se vuelve tan enorme y complejo que es imposible de entender y, a menudo, comete errores.

Esta paper presenta una nueva herramienta matemática llamada ClusterLearn (o "Aprende por Agrupamientos") que actúa como un organizador maestro para estos datos. Aquí te explico cómo funciona con analogías sencillas:

1. El Problema: La "Torre de Babel" de los Datos

Imagina que tienes un mapa de 100 ciudades. Si quieres predecir el tráfico, podrías pensar que cada ciudad es única. Pero, en realidad, muchas ciudades pequeñas se comportan igual: tienen poco tráfico. Si tratas a cada una por separado, tu modelo necesita aprender 100 reglas diferentes. Es como intentar memorizar el nombre de cada persona en un estadio gigante en lugar de agruparlas por equipos.

Además, a veces hay ciudades que simplemente no importan para tu predicción (son "ruido"). Necesitas ignorarlas.

2. La Solución: Dos Superpoderes

La nueva herramienta de los autores tiene dos trucos mágicos para simplificar el modelo:

• Truco A: El "Imán de Agrupamiento" (Fusión Exacta)
  Imagina que tienes un imán muy fuerte. Si dos ciudades tienen un comportamiento de tráfico muy similar, este imán las pega juntas. En lugar de tener 100 reglas diferentes, el modelo dice: "¡Espera! Estas 20 ciudades pequeñas se comportan igual, así que las tratamos como una sola gran ciudad".

  • En lenguaje técnico: Esto se llama "fusión de coeficientes". Reduce el número de categorías únicas agrupando las que son similares.

• Truco B: El "Cuchillo de Podar" (Esparsidad)
  Imagina que tienes un jardín con muchas plantas (categorías). Algunas plantas son malas hierbas que no aportan nada a la belleza del jardín. Este cuchillo identifica esas plantas inútiles y las corta de raíz (las hace cero).

  • En lenguaje técnico: Esto es "regularización de esparsidad". Elimina las variables que no ayudan a la predicción, haciendo el modelo más limpio.

3. ¿Cómo lo hacen? (La Magia detrás del Escenario)

Los autores no solo inventaron una idea bonita, sino que construyeron una máquina muy precisa para hacerlo.

• El Enfoque Exacto (El Arquitecto Preciso):
  Usan una técnica llamada Programación Entera Mixta (MIP). Imagina que eres un arquitecto que quiere construir la casa perfecta. En lugar de adivinar, revisan todas las combinaciones posibles de cómo agrupar las ciudades y cuáles cortar, hasta encontrar la solución matemáticamente óptima.

  • El desafío: Revisar todas las combinaciones es como buscar una aguja en un pajar gigante. Para hacerlo rápido, crearon un algoritmo inteligente que va descartando opciones imposibles rápidamente (como un detective que sabe qué pistas ignorar).

• El Enfoque Rápido (El Chef Express):
  Para cuando tienes millones de datos y no tienes tiempo de esperar a que el arquitecto termine, crearon un algoritmo rápido (basado en "descenso de coordenadas"). Es como un chef que prepara un plato delicioso muy rápido: no es la receta perfecta del mundo, pero es muy buena y lista en segundos.

4. ¿Por qué es mejor que lo anterior?

Antes, los métodos existentes eran como intentar ordenar una habitación tirando cosas al azar o usando reglas muy suaves que a veces no funcionaban bien.

• SCOPE (el anterior líder): Era como un organizador que usaba un pegamento suave. A veces pegaba cosas que no debían ir juntas, o no pegaba las que sí debían.
• ClusterLearn (el nuevo): Es como un organizador con tijeras de precisión y un pegamento instantáneo.
  • Resultado: En pruebas con datos reales (como el alquiler de bicicletas en una ciudad o seguros de vida), su método predijo mejor y creó modelos más simples y fáciles de entender que los anteriores.

En Resumen

Imagina que tienes una caja de LEGO con 10,000 piezas de colores diferentes.

• Los métodos viejos te decían: "Usa todas las piezas, pero intenta que no se vean mal".
• ClusterLearn te dice: "¡Espera! Estas 500 piezas rojas son idénticas, únelas en un solo bloque. Y estas 200 piezas verdes no sirven para nada, tíralas. Ahora tienes un modelo con solo 50 bloques, es más fácil de construir y funciona mejor".

Es una herramienta poderosa para tomar datos desordenados y convertirlos en historias claras y precisas, ya sea para predecir el clima, los precios de las casas o los riesgos de seguros.

Resumen técnico

Aquí presento un resumen técnico detallado del artículo "Modeling with Categorical Features via Exact Fusion and Sparsity Regularisation", estructurado según los puntos solicitados.

1. Planteamiento del Problema

El artículo aborda el problema de la regresión lineal de alta dimensión que incluye predictores categóricos nominales con un gran número de niveles (por ejemplo, códigos postales, marcas de vehículos o códigos de diagnóstico médico).

El desafío principal radica en la interpretabilidad y la eficiencia del modelo cuando se tienen muchas variables categóricas con muchos niveles. Los enfoques estándar (como Lasso o Elastic Net) tratan cada nivel como una variable independiente, lo que puede resultar en modelos con demasiados parámetros y poco interpretables.

El objetivo es desarrollar un estimador que logre dos cosas simultáneamente:

1. Fusión (Agrupamiento): Colapsar niveles de una misma variable categórica que tienen efectos similares sobre la respuesta, reduciendo así el número de coeficientes distintos.
2. Escasez (Sparsity): Seleccionar un subconjunto de predictores y niveles relevantes, eliminando aquellos con coeficientes cero.

El modelo propuesto busca estimar los coeficientes $\theta_{j,k}$ minimizando una función de pérdida que incluye penalizaciones tanto por el número de coeficientes no nulos como por el número de valores distintos (clusters) dentro de cada variable categórica.

2. Metodología Propuesta: ClusterLearn-L0

Los autores proponen un nuevo estimador llamado ClusterLearn-L0, basado en optimización discreta.

Formulación del Estimador

El estimador se define como la solución al siguiente problema de optimización:
$$(\hat{\alpha}, \hat{\beta}) \in \arg\min_{\alpha, \beta} \frac{1}{n}\|y - \alpha\mathbf{1} - X\beta\|_2^2 + \lambda_0 \|\beta\|_0 + \lambda \sum_{j=1}^q |\{\beta_k : k \in I_j\}|$$
Donde:

• $\|\beta\|_0$: Penaliza el número total de coeficientes no nulos (promueve la escasez global).
• $\sum |\{\beta_k : k \in I_j\}|$: Penaliza el número de valores distintos (clusters) para cada variable categórica $j$. Esto fomenta que los coeficientes de los niveles de una misma categoría se agrupen.
• $\lambda_0$ y $\lambda$: Parámetros de ajuste que controlan la fuerza de la penalización de escasez y fusión, respectivamente.

Enfoques Algorítmicos

El artículo presenta dos vías principales para resolver este problema no convexo y de optimización entera:

A. Enfoque Exacto (Programación Entera Mixta - MIP):

• Formulación MIP: Se reformula el problema utilizando variables binarias para codificar tanto la escasez ($z_i = \mathbb{I}(\beta_i \neq 0)$) como el patrón de agrupamiento ($z_{i,k} = \mathbb{I}(\beta_i \neq \beta_k)$).
• Generación de Filas (Row Generation): Dado que la formulación directa puede tener $O(p^2)$ restricciones, lo cual es computacionalmente costoso, los autores desarrollan un algoritmo de generación de filas personalizado. Este método resuelve iterativamente un subproblema simplificado y añade restricciones solo cuando es necesario, acelerando significativamente la convergencia de solucionadores comerciales como Gurobi.
• Garantía: Este enfoque permite encontrar soluciones óptimas globales con certificados de optimalidad para problemas de tamaño moderado (cientos a miles de variables).

B. Enfoque Aproximado (Descenso de Coordenadas por Bloques - BCD):

• Para problemas de gran escala, se propone un algoritmo rápido basado en BCD.
• Bloque Univariable: La clave del algoritmo es la resolución eficiente del subproblema univariable (optimizar los coeficientes de una sola variable categórica manteniendo fijas las demás).
• Algoritmo DP Exacto: Para resolver el subproblema univariable, los autores desarrollan un algoritmo exacto basado en Programación Dinámica (DP), una extensión del trabajo de Johnson (2013) sobre segmentación de señales. Este algoritmo maneja la estructura no convexa introducida por la penalización $\ell_0$, logrando ser hasta 500 veces más rápido que los métodos aproximados existentes (como SCOPE) en ciertos escenarios.
• Extensión: El método se extiende también a clasificación binaria utilizando pérdida logística.

3. Contribuciones Clave

1. Nuevo Estimador Discreto: Introducción de ClusterLearn-L0, que controla directamente el número de clusters y la escasez mediante penalizaciones $\ell_0$ y de fusión, a diferencia de métodos anteriores que usan penalizaciones convexas o no convexas aproximadas (como MCP).
2. Formulación MIP y Algoritmo de Aceleración: Desarrollo de una formulación MIP novedosa y un algoritmo de generación de filas que permite resolver problemas de regresión con variables categóricas a optimalidad global en tiempos razonables.
3. Algoritmo de Programación Dinámica: Creación de un solucionador exacto para el caso univariable con penalización de fusión y escasez, que sirve como bloque de construcción fundamental para el algoritmo BCD rápido.
4. Teoría Estadística:
   • Se establecen límites de error de predicción que demuestran que el estimador alcanza tasas óptimas (hasta factores logarítmicos) incluso cuando los coeficientes verdaderos no están agrupados.
   • Se prueban garantías de recuperación de clusters: bajo condiciones de separación mínima entre los coeficientes verdaderos, el estimador recupera el patrón de agrupamiento correcto con alta probabilidad.
5. Resultados Numéricos: Demostración empírica de que el método supera a los estados del arte (como SCOPE, Elastic Net y Lasso) en precisión de predicción, recuperación de clusters y eficiencia computacional.

4. Resultados Experimentales

Los autores evaluaron su método en datos sintéticos y reales:

• Datos Sintéticos:

  • En escenarios con ruido y alta dimensionalidad, ClusterLearn-L0 logró un mejor rendimiento en la métrica $R^2$ (coeficiente de determinación) y una mayor pureza de agrupamiento (recuperación correcta de niveles) en comparación con SCOPE, Elastic Net e IHT.
  • El método demostró ser robusto ante diferentes niveles de relación señal-ruido (SNR).
  • Eficiencia: El algoritmo aproximado (BCD) fue hasta 500 veces más rápido que el algoritmo aproximado de SCOPE para problemas con miles de niveles categóricos. El algoritmo exacto (MIP con generación de filas) pudo resolver problemas con $p \approx 4500$ en menos de 15 minutos, obteniendo certificados de optimalidad, algo que los solucionadores MIP estándar no lograban en tiempos competitivos.

• Datos Reales:

  • Conjunto de Datos de Alquiler de Bicicletas: ClusterLearn-L0 obtuvo la mejor $R^2$ de prueba y un número reducido de niveles de coeficientes, superando a SCOPE y Elastic Net.
  • Conjunto de Datos de Seguros (Prudential): En una tarea de clasificación binaria, el método logró la mayor precisión, con un número de niveles de coeficientes significativamente menor que Lasso y Elastic Net, y menor tiempo de ejecución que SCOPE.
  • Datos de Acceso de Empleados y Flares Solares: Resultados consistentes mostrando superioridad en precisión y eficiencia.

5. Significancia e Impacto

Este trabajo es significativo por varias razones:

• Interpretabilidad: Permite a los analistas descubrir estructuras latentes en variables categóricas (ej. agrupar códigos postales por comportamiento de riesgo similar) sin perder información crítica, algo crucial en dominios como la salud y los seguros.
• Rigor Computacional: A diferencia de la mayoría de los métodos de fusión de coeficientes que son heurísticos o aproximados, este enfoque ofrece una vía para obtener soluciones óptimas globales mediante MIP, lo cual es un avance teórico y práctico importante.
• Escalabilidad: La combinación de un algoritmo exacto para subproblemas univariables y un esquema BCD permite aplicar estos métodos rigurosos a conjuntos de datos de gran escala, llenando un vacío entre la teoría de optimización discreta y la práctica del aprendizaje automático.
• Generalidad: La metodología no se limita a la regresión lineal, sino que se extiende a problemas de clasificación, ampliando su utilidad en aplicaciones reales.

En resumen, el artículo presenta un marco unificado que combina la potencia de la optimización discreta exacta con algoritmos aproximados rápidos, logrando un equilibrio superior entre la calidad de la predicción, la interpretabilidad del modelo y la eficiencia computacional en el manejo de variables categóricas de alta dimensión.