Modeling with Categorical Features via Exact Fusion and Sparsity Regularisation

Cet article propose une nouvelle méthode d'estimation pour la régression linéaire à haute dimension avec des prédicteurs catégoriels, qui combine la fusion exacte des niveaux et la régularisation par parcimonie via des formulations en programmation en nombres entiers et des algorithmes rapides, démontrant ainsi des performances supérieures aux approches existantes.

L'essentiel

Imaginez que vous essayez de prédire le nombre de vélos loués dans une ville, en fonction de l'heure de la journée et du jour de la semaine. Vous avez beaucoup de données, mais elles sont un peu "en désordre". Par exemple, le lundi, le mardi et le jeudi se comportent de manière très similaire, tandis que le samedi et le dimanche sont totalement différents. De même, la nuit (minuit à 5h) est calme, mais le matin et le soir sont très actifs.

Le problème, c'est que les méthodes statistiques classiques traitent chaque jour et chaque heure comme une entité unique et totalement distincte. C'est comme si vous deviez apprendre 168 noms différents pour chaque jour et chaque heure, ce qui rend le modèle lourd, compliqué et difficile à comprendre.

C'est ici qu'intervient cette nouvelle recherche, que nous pouvons appeler "Le Grand Tri Intelligent".

Voici une explication simple de ce que les auteurs ont créé, en utilisant des analogies du quotidien :

1. Le Problème : Trop de détails, pas assez de sens

Imaginez que vous êtes un chef cuisinier. Vous avez 100 ingrédients différents. La méthode classique vous dit : "Utilisez chaque ingrédient séparément, et si vous ne l'utilisez pas, mettez-le de côté."
Mais souvent, certains ingrédients sont presque identiques (par exemple, le sel de mer et le sel de l'Himalaya). Les utiliser séparément gâche la recette et la rend trop complexe. Vous voulez regrouper les ingrédients similaires et n'utiliser que ceux qui sont vraiment nécessaires.

Dans le monde des données, cela s'appelle des variables catégorielles (comme les jours, les codes postaux, les marques de voitures). Souvent, ces catégories ont des niveaux qui se ressemblent beaucoup.

2. La Solution : Deux super-pouvoirs

Les auteurs ont créé un nouvel outil mathématique (qu'ils appellent ClusterLearn-L0) qui fait deux choses magiques en même temps :

• Le Super-Pouvoir de la Fusion (Le "Regroupement") :
  Imaginez que vous avez une boîte de Legos de toutes les couleurs. Au lieu de garder chaque brique séparée, votre outil dit : "Attends, ces briques rouges et ces briques roses sont si similaires qu'on peut les coller ensemble et les appeler simplement 'Roses'."
  Mathématiquement, cela signifie qu'il regroupe les jours ou les heures qui ont le même effet sur le résultat. Il réduit le nombre de catégories distinctes, rendant le modèle plus simple et plus facile à lire.

• Le Super-Pouvoir de l'Élagage (La "Sparsité") :
  Maintenant, imaginez que parmi tous vos ingrédients, certains ne servent à rien du tout (comme ajouter du sable à une tarte). L'outil dit : "On jette tout ça !" Il élimine complètement les catégories qui n'ont aucun impact sur la prédiction.
  Cela permet de créer un modèle très épuré, qui ne garde que l'essentiel.

3. Comment ça marche ? (La Cuisine et le Puzzle)

Pour trouver la meilleure combinaison, les chercheurs ont développé deux approches :

• L'Approche de Précision (Le Puzzle Parfait) :
  Ils ont créé un algorithme qui résout le problème comme un puzzle mathématique parfait. Il teste des milliards de combinaisons possibles pour trouver exactement la meilleure façon de regrouper et d'éliminer. C'est comme si un super-ordinateur essayait chaque pièce de puzzle jusqu'à trouver l'image parfaite. C'est lent mais garanti d'être parfait pour les problèmes de taille moyenne.
  Analogie : C'est comme un détective qui vérifie chaque piste une par une pour être sûr de ne rien manquer.

• L'Approche Rapide (Le Chef Expérimenté) :
  Pour les très gros problèmes (des milliers de données), ils ont aussi créé une version rapide. C'est comme un chef expérimenté qui, par intuition et expérience, sait rapidement quelles épices mélanger et lesquelles jeter, sans avoir besoin de tester chaque combinaison possible. C'est très rapide et donne un résultat excellent, même si ce n'est pas mathématiquement "parfait" à 100%.

4. Pourquoi c'est génial ? (Les Résultats)

Les chercheurs ont testé leur outil sur des données réelles (comme les locations de vélos à Boston ou les assurances vie).

• Plus précis : Leur modèle prédit mieux que les méthodes actuelles les plus avancées.
• Plus simple : Au lieu d'avoir un modèle avec des centaines de règles incompréhensibles, ils obtiennent un modèle avec quelques règles claires (ex: "Les jours de semaine sont pareils", "La nuit est calme").
• Plus rapide : Leur méthode rapide bat les concurrents en vitesse, et leur méthode précise trouve des solutions optimales que les autres ne peuvent même pas atteindre.

En résumé

Ce papier propose un nouvel outil pour faire le ménage dans les données. Au lieu de traiter chaque détail comme unique, il regroupe ce qui est semblable et supprime ce qui est inutile.

C'est comme passer d'une liste de courses interminable et confuse à une recette de cuisine claire, simple et efficace, qui vous dit exactement quels ingrédients utiliser pour obtenir le meilleur résultat possible. C'est une avancée majeure pour rendre l'intelligence artificielle plus intelligente, plus rapide et plus facile à comprendre pour les humains.

Résumé technique

1. Problématique

L'article aborde le problème de la régression linéaire en haute dimension lorsque les prédicteurs incluent des variables catégorielles nominales possédant un grand nombre de niveaux (par exemple, codes postaux, marques de véhicules, codes de diagnostic).

Les défis principaux sont :

• Dimensionnalité : Le nombre de variables dummy (indicateurs) peut être très élevé, dépassant souvent le nombre d'observations ($p \gg n$).
• Interprétabilité et Compacité : Il est souhaitable de réduire la complexité du modèle en regroupant (fusionnant) les niveaux d'une même variable catégorielle qui ont un effet similaire sur la réponse.
• Parcimonie : Il est également crucial de sélectionner un sous-ensemble de variables pertinentes (parcimonie globale) pour éviter le surapprentissage.

L'objectif est de développer un estimateur capable de réaliser simultanément :

1. La fusion des coefficients de régression associés à un même prédicteur catégoriel (réduisant ainsi le nombre de valeurs distinctes).
2. La parcimonie (réduisant le nombre total de coefficients non nuls).

2. Méthodologie Proposée : ClusterLearn-L0

Les auteurs proposent un nouvel estimateur nommé ClusterLearn-L0, basé sur l'optimisation discrète.

Formulation de l'Estimateur

L'estimateur est défini comme la solution globale d'un problème d'optimisation combinant une perte des moindres carrés avec deux termes de pénalité :

$$(\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\}|$$

Où :

• $\|\beta\|_0$ est la pénalité de parcimonie (comptant le nombre de coefficients non nuls).
• $\sum_{j=1}^q |\{\beta_k : k \in I_j\}|$ est la pénalité de fusion, comptant le nombre de valeurs distinctes des coefficients pour chaque prédicteur catégoriel $j$.
• $\lambda$ et $\lambda_0$ sont des paramètres de régularisation.

Cette formulation permet un contrôle direct sur le nombre de clusters (groupes de niveaux fusionnés) et le nombre de variables sélectionnées.

Algorithmes et Résolution

Le problème est reformulé comme un Programme Linéaire en Nombres Entiers Mixtes (MIP).

1. Formulation MIP Exacte :

   • Les auteurs utilisent des variables binaires pour encoder à la fois le schéma de parcimonie (coefficients nuls ou non) et le schéma de clustering (coefficients égaux ou non).
   • Contrairement aux approches approximatives, cette formulation permet de trouver la solution optimale globale à l'aide de solveurs commerciaux (comme Gurobi).
   • Génération de Lignes (Row Generation) : Pour surmonter la complexité computationnelle (le nombre de contraintes peut être en $O(p^2)$), les auteurs développent un algorithme de génération de lignes personnalisé. Il ajoute dynamiquement les contraintes nécessaires uniquement lorsque cela est requis par la solution courante, accélérant considérablement la résolution exacte.

2. Algorithme Approximatif (BCD) :

   • Pour les très grands problèmes, une méthode de Descente de Coordonnées par Blocs (Block Coordinate Descent - BCD) est proposée.
   • Le cœur de cet algorithme est la résolution exacte d'un sous-problème univarié (un seul prédicteur catégoriel) via un algorithme de Programmation Dynamique (DP).
   • Cet algorithme DP, nommé DpSegPen-L0, étend les travaux antérieurs sur la segmentation de signaux pour gérer simultanément la fusion et la parcimonie ($\ell_0$). Il est jusqu'à 500 fois plus rapide que l'algorithme de l'état de l'art (SCOPE) pour les problèmes univariés.

3. Extension : La méthode est également étendue à la classification binaire (régression logistique) via une borne quadratique supérieure de la fonction de perte logistique.

3. Contributions Clés

• Approche Exacte vs Approximative : Contrairement à la méthode de référence actuelle (SCOPE, basée sur la pénalité Minimax Concave et des algorithmes approximatifs), cette méthode offre une garantie d'optimalité globale via le MIP.
• Contrôle Direct des Clusters : La pénalité sur le nombre de valeurs distinctes permet un contrôle explicite du nombre de clusters, contrairement aux pénalités de type "fusion" continues qui nécessitent un réglage indirect.
• Nouvel Algorithme DP : Développement d'un algorithme de programmation dynamique exact pour le cas univarié avec pénalité $\ell_0$ et fusion, qui est plus rapide et plus général que les méthodes existantes.
• Théorie :
  • Bornes d'Erreur de Prédiction : Démonstration que l'estimateur atteint un taux d'erreur de prédiction optimal (à un facteur logarithmique près), comparable à la régression linéaire parcimonieuse standard, même sans hypothèse de clustering préalable.
  • Récupération de Clusters : Preuve théorique que l'estimateur peut récupérer avec une haute probabilité le schéma de clustering vrai, sous une condition de séparation minimale des coefficients. Cette condition est minimax optimale dans le cas univarié.
• Efficacité Computationnelle : L'algorithme approché est significativement plus rapide que SCOPE pour les grands jeux de données, et l'algorithme exact (avec génération de lignes) résout des problèmes de taille modérée (plusieurs milliers de variables) en quelques minutes avec des certificats d'optimalité.

4. Résultats Numériques

Les expériences ont été menées sur des données synthétiques et réelles (partage de vélos, assurance vie, accès employé, éruptions solaires).

• Performance de Prédiction : ClusterLearn-L0 surpasse systématiquement ou égale les méthodes de l'état de l'art (SCOPE, Elastic Net, IHT) en termes de $R^2$ (coefficient de détermination) ou d'exactitude de classification, en particulier dans les régimes à faible rapport signal/bruit (SNR).
• Récupération de Clusters : La méthode obtient une "pureté" de clustering supérieure, retrouvant plus fidèlement les groupes de niveaux catégoriels qui ont le même effet.
• Compacité du Modèle : ClusterLearn-L0 produit des modèles avec moins de niveaux de coefficients (clusters) que SCOPE et Elastic Net, améliorant ainsi l'interprétabilité.
• Temps de Calcul :
  • L'algorithme approché (BCD) est jusqu'à 500 fois plus rapide que SCOPE pour les grands problèmes.
  • L'algorithme exact (MIP avec génération de lignes) résout des problèmes avec $p \approx 4500$ en moins de 15 minutes sur un ordinateur portable, offrant des certificats d'optimalité que SCOPE ne peut pas fournir.

5. Signification et Impact

Ce travail est significatif car il comble le fossé entre la théorie de l'optimisation discrète et la pratique de la modélisation statistique pour les données catégorielles.

1. Fiabilité : En fournissant des solutions globalement optimales (et non pas juste des points stationnaires locaux comme SCOPE), la méthode élimine l'incertitude liée à la convergence des algorithmes heuristiques.
2. Interprétabilité : La capacité à fusionner exactement les niveaux de variables catégorielles tout en sélectionnant les variables pertinentes permet de créer des modèles plus simples et plus explicables, ce qui est crucial dans des domaines comme la santé ou l'assurance.
3. Faisabilité : L'article démontre que les problèmes d'optimisation combinatoire complexes en haute dimension, autrefois considérés comme insolubles, peuvent être résolus efficacement grâce aux avancées récentes en MIP et à des algorithmes spécialisés (génération de lignes, DP).

En résumé, ClusterLearn-L0 représente une avancée majeure pour l'analyse de données contenant des variables catégorielles à haute cardinalité, offrant un équilibre supérieur entre précision prédictive, parcimonie, interprétabilité et garanties théoriques.