Résumé Technique : Champs de Classification : Clustering Hiérarchique Récursif Arbitrairement Fin à partir de Quelques Exemples

1. Énoncé du Problème

Les méthodes classiques de clustering hiérarchique opèrent généralement sur un échantillon fini fixe, renvoyant soit une partition finie des données, soit un dendrogramme fini. Cette approche est inadéquate lorsque la hiérarchie sous-jacente d'intérêt est un objet géométrique récursif présentant des raffinements à fine échelle qui s'étendent au-delà des niveaux directement observés. Dans de tels régimes, le nombre de centres de clusters latents ($k$) peut croître bien au-delà du nombre de nœuds observés ($N$), et les raffinements peuvent se poursuivre à des profondeurs absentes des données d'entraînement.

La question centrale abordée par ce travail est la suivante : Pouvons-nous apprendre une règle de raffinement local à partir d'un préfixe fini observé d'une hiérarchie et l'étendre récursivement pour générer des niveaux non observés substantiellement plus profonds ?

Les approches actuelles, différentiables ou apprises, pour la hiérarchie ajustent généralement un arbre fini observé, intègrent une structure fixe ou optimisent un objectif de clustering fini. Elles n'apprennent pas directement un mécanisme de raffinement capable d'un déploiement récursif au-delà de la hiérarchie observée.

2. Méthodologie : Champs de Classification

Les auteurs introduisent les Champs de Classification, un modèle métrico-géométrique pour le clustering hiérarchique de profondeur infinie.

2.1 Définitions Fondamentales

• Générateur de Champ de Classification (CFG) : Une règle locale $r: \mathbb{R}^d \to (\mathbb{R}^d)^K$ qui mappe un centre parent vers un $K$-uplet ordonné, borné et séparé de résidus enfants.
  • Contraintes : Pour tout parent $x$, les résidus enfants $\{r_k(x)\}$ doivent se situer dans un anneau euclidien (norme bornée) et être séparés par une distance $s_{sep}$.
  • Construction : Les CFG peuvent être construits via des déformations orthogonale-diagonale-orthogonale d'un empilement de référence fixe, garantissant le respect des contraintes géométriques.
• Champ de Classification : La structure hiérarchique de profondeur infinie obtenue en appliquant récursivement le CFG à partir d'une racine $x_0$ et d'un facteur d'échelle $s$.
  • Structure : Le champ est un graphe acyclique dirigé (DAG) métrique généré récursivement.
  • Composantes : Il génère des centres de clusters, des cellules de Voronoï associées et des adresses généalogiques.
  • Métriques : L'article définit trois métriques de distance sur le champ :
    1. Métrique Arbre : Basée sur des poids d'arêtes combinatoires (dépendants du niveau).
    2. Métrique Basée sur les Points : Basée sur les distances euclidiennes entre les centres.
    3. Métrique Basée sur les Cellules : Basée sur les distances de Hausdorff entre les cellules de Voronoï, mises à l'échelle par la profondeur.

2.2 Apprentissage : Prédicteurs de Champ de Classification (CFP)

Étant donné un préfixe fini d'une hiérarchie (observé jusqu'à la profondeur $L_{train}$), l'objectif est d'apprendre un Prédicteur de Champ de Classification (CFP), noté $\hat{r}$, qui approxime le CFG sous-jacent.

• Objectif d'Entraînement : Minimiser l'erreur quadratique entre les résidus enfants prédits et les résidus observés :
  $$\mathcal{L}(\hat{r} | \mathcal{H}_{train}) = \sum_{l=0}^{L_{train}-1} \sum_{x \in \mathcal{H}_l} \sum_{k=1}^K \| x + s^{l+1}\hat{r}(x)_k - \text{chld}(x)_k \|_2^2$$
• Déploiement Récursif : Au moment du test, $\hat{r}$ est appliqué récursivement à partir de la racine. Chaque enfant généré devient un parent pour le niveau suivant. Aucun nœud de vérité terrain provenant de niveaux invisibles n'est utilisé lors du déploiement.

2.3 Garanties Théoriques

L'article établit que les troncatures finies du champ appris convergent vers le champ de profondeur infinie complété sous des conditions spécifiques :

• Convergence Exponentielle : Sous des hypothèses de bornitude, de séparation et de régularité, la distance de Hausdorff entre la troncature de profondeur-$L$ et le champ complété décroît exponentiellement avec $L$.
• Réalisation Neurale : Les fenêtres de raffinement finies requises pour approximer le CFG peuvent être réalisées par des Perceptrons Multicouches (MLP) à fonction d'activation ReLU.
  • Complexité : La largeur requise est $O(\varepsilon^{-\gamma})$ et la profondeur est $\tilde{O}(\varepsilon^{-3\gamma/2})$, où $\gamma = \log K / (-\log s)$.
  • Cela prouve qu'un réseau de neurones fini peut agir comme un mécanisme d'approximation fini pour une structure hiérarchique de profondeur infinie.

3. Validation Expérimentale

Les auteurs évaluent le CFP dans trois configurations présentant un écart croissant par rapport à la théorie idéalisée :

1. Hiérarchies Générées par CFG Apparié :

   • Configuration : Données générées par un CFG connu issu de la même famille utilisée dans la théorie.
   • Résultat : Le CFP maintient l'erreur par niveau la plus faible sur des horizons de déploiement invisibles par rapport aux bases de référence (prédicteurs constants apprenables, résidu moyen et affine). Cela confirme que la règle locale apprise reste cohérente sous composition récursive.

2. Hiérarchies Fractales IFS Hors Famille :

   • Configuration : Hiérarchies générées par des Systèmes de Fonctions Itérées (IFS) avec des perturbations non linéaires lisses (par exemple, triangle de Sierpiński, poussière de Cantor, courbe de Koch). Ceux-ci possèdent une structure récursive exacte mais ne sont pas tirés de la famille paramétrée des CFG.
   • Résultat : Le CFP atteint un MSE inférieur, une Distance de Chamfer Invariante par Permutation (PI-CD) inférieure et une distorsion de profondeur moindre que les bases de référence. Cela démontre que la formulation du champ de classification se généralise au-delà de la classe de générateurs appariée.

3. Hiérarchies de Clustering Récursif Induites par Image :

   • Configuration : Hiérarchies construites à partir des embeddings CLIP d'images CIFAR-10 et CIFAR-100 en utilisant une méthode de clustering profond récursive. La règle de raffinement est approximative et les emplacements enfants nécessitent une canonicalisation (ordonnancement) via l'ACP.
   • Résultat : Le CFP surpasse significativement les bases de référence dans la préservation de la géométrie non ordonnée (PI-CD) et des métriques de chemin au niveau hiérarchique (dpt-distortion). Cela suggère que même dans des contextes de données réelles bruyantes, les préfixes de hiérarchie finis contiennent des mécanismes de raffinement apprenables.

4. Contributions Clés

1. Cadre Conceptuel : Introduction des Champs de Classification comme modèle métrico-géométrique pour le clustering hiérarchique de profondeur infinie, déplaçant l'accent de l'apprentissage d'une hiérarchie sur des échantillons finis vers l'apprentissage d'une règle de raffinement parent-enfant locale réutilisable.
2. Théorie Métrique : Développement d'une théorie métrique rigoureuse pour ces objets, incluant des définitions pour les distances basées sur l'arbre, les points et les cellules, ainsi que des bornes quantitatives pour la convergence des troncatures finies vers le champ complété.
3. Réalisation Neurale : Preuve que les fenêtres de raffinement finies peuvent être représentées par des prédicteurs ReLU, établissant un mécanisme de déploiement neuronal fini pour la complétion hiérarchique de profondeur infinie avec des bornes de complexité explicites.

5. Signification et Revendications

L'article revendique que les observations hiérarchiques finies peuvent révéler des règles de raffinement locales capables de générer des champs de classification substantiellement plus profonds. Les résultats soutiennent l'idée que le clustering hiérarchique peut être formulé comme l'apprentissage d'une loi de raffinement récursif local plutôt que comme la construction d'un résumé combinatoire fini.

Les auteurs positionnent ce travail comme une vision complémentaire aux méthodes existantes de clustering hiérarchique. Ils notent explicitement les limites : le cadre suppose un facteur de branchement fixe, une séparation suffisante et un processus de raffinement réutilisable. Ils reconnaissent que l'extension du cadre à des hiérarchies bruyantes, à branchement variable, faiblement alignées ou non auto-similaires reste une direction importante pour les travaux futurs. Les expériences sont présentées comme des sondes de validation plutôt que comme des affirmations selon lesquelles chaque problème de clustering hiérarchique admet un champ de classification parfait.