How Hard Is Continuous Clustering? Lower Bounds from the Existential Theory of the Reals

1. Énoncé du problème

L'article examine la complexité computationnelle des problèmes de clustering continu formulés directement sur une fonction de densité de probabilité polynomiale $f: \mathbb{R}^d \to \mathbb{R}$, plutôt que sur des ensembles de points finis. L'objectif est de déterminer la difficulté inhérente à décider si une structure de cluster spécifique existe au sein du « paysage » défini par le polynôme, étant donné un seuil de densité $\theta$.

L'auteur formalise quatre problèmes de décision naturels qui s'étendent des critères géométriques locaux aux propriétés topologiques globales :

1. CMRC (Continuous Multi-Region Clustering) : Existe-t-il $k$ points deux à deux séparés par une distance $\delta$ où la densité $f(x) \geq \theta$ ?
2. VSC (Valley-Separated Clusters) : Existe-t-il deux points $p, q$ tels que $f(p), f(q) \geq \theta$ et que leur milieu se situe strictement en dessous du seuil ($f(\frac{p+q}{2}) < \theta$) ? Cela certifie géométriquement une « vallée » séparant deux régions de haute densité.
3. CLSC-k (Continuous Level-Set Component Counting) : L'ensemble de niveau supérieur $L_\theta = \{x \mid f(x) \geq \theta\}$ possède-t-il au moins $k$ composantes connexes ?
4. HD (Hole Detection) : L'ensemble de niveau supérieur $L_\theta$ possède-t-il un groupe d'homologie singulière première non trivial (c'est-à-dire contient-il un « trou ») ?

2. Méthodologie

L'article utilise des outils issus de la géométrie algébrique réelle computationnelle et de la théorie de la complexité, en se concentrant spécifiquement sur la Théorie Existentielle des Réels ($\exists\mathbb{R}$).

• Classe de complexité $\exists\mathbb{R}$ : Cette classe comprend les problèmes de décision réductibles à la détermination de la vérité de phrases de la forme $\exists x_1 \dots \exists x_n \Phi(x_1, \dots, x_n)$, où $\Phi$ est une combinaison booléenne sans quantificateur d'équations et d'inéquations polynomiales. Le problème complet canonique est Feas (déterminer si un polynôme possède une racine réelle).
• Réductions : L'auteur construit des réductions en temps polynomial depuis le problème complet canonique $\exists\mathbb{R}$, Feas, vers les problèmes de clustering.
  • La construction « Two-Sheet » (Deux feuillets) : Un gadget algébrique central est utilisé pour encoder l'existence d'une racine d'un polynôme d'entrée $r(y)$ dans la géométrie du problème de clustering. La construction crée un polynôme $F$ dont l'ensemble de niveau supérieur se compose de deux « feuillets » parallèles (par exemple à $s=1$ et $s=-1$) si une racine existe, et est vide sinon.
  • Embeddings topologiques : Pour la détection de trous, la construction incorpore l'ensemble des zéros de $r(y)$ comme facteur dans un produit avec le cercle unité ($S^1$), en utilisant la formule de Künneth pour garantir que l'espace résultant possède une homologie non triviale si et seulement si une racine existe.

3. Contributions et résultats clés

A. Complétude pour le clustering local et basé sur les vallées

L'article démontre que les deux premiers problèmes sont $\exists\mathbb{R}$-complets.

• CMRC : Le problème est montré appartenir à $\exists\mathbb{R}$ car il peut être exprimé comme une phrase existentielle sur les réels (quantifiant sur $k$ points et vérifiant des inéquations polynomiales). Il est prouvé $\exists\mathbb{R}$-difficile via une réduction depuis Feas utilisant une coordonnée factice pour assurer la séparation.
• VSC : Bien que ce soit un concept « global » (nécessitant une vallée), VSC reste dans $\exists\mathbb{R}$ car l'existence d'une vallée peut être témoinée par un seul quantificateur existentiel (le point milieu). La preuve de difficulté utilise la construction à deux feuillets où les deux feuillets sont séparés par une vallée à $s=0$.
• Implication : Puisque $\text{NP} \subseteq \exists\mathbb{R}$ et que l'inclusion est supposée stricte, CMRC et VSC ne sont pas dans NP (sauf si $\text{NP} = \exists\mathbb{R}$). Cela établit que même un clustering continu simple est plus difficile que les problèmes NP-complets standards comme les $k$-moyennes.

B. Difficulté et décidabilité pour le clustering topologique

L'article aborde la complexité des problèmes purement topologiques (CLSC-k et HD).

• Bornes inférieures : CLSC-k et HD sont tous deux prouvés $\exists\mathbb{R}$-difficiles. La même construction à deux feuillets est utilisée pour CLSC-k (comptage de composantes), et une construction de produit avec un cercle est utilisée pour HD.
• Bornes supérieures et l'écart : Contrairement à CMRC et VSC, l'appartenance de CLSC-k et HD à $\exists\mathbb{R}$ est inconnue.
  • Ces problèmes sont décidables via la décomposition algébrique cylindrique (CAD), les plaçant dans la théorie du premier ordre des réels (qui est dans PSPACE).
  • Cependant, les placer dans $\exists\mathbb{R}$ nécessiterait un certificat existentiel de taille polynomiale pour la déconnexion ou l'homologie non triviale d'un ensemble semi-algébrique. C'est un problème ouvert notoire en géométrie algébrique réelle (lié aux bornes de degré du Positivstellensatz).
• Conclusion : Ces problèmes se situent probablement strictement au-dessus de $\exists\mathbb{R}$ dans la hiérarchie polynomiale réelle (potentiellement dans $\exists\forall\mathbb{R}$), représentant un saut de complexité des critères « locaux/vallées » vers la « topologie globale ».

4. Signification et implications

1. Classification de complexité rigoureuse : C'est le premier travail à fournir une classification de complexité rigoureuse pour le clustering continu exact, allant au-delà du cadre discret et d'échantillons finis (qui est typiquement NP-dur).
2. Identification d'une frontière nette : L'article délimite une frontière précise dans la complexité du clustering :
   • $\exists\mathbb{R}$-Complet : Séparation locale et séparation basée sur les vallées (des témoins géométriques existent).
   • Au-dessus de $\exists\mathbb{R}$ : Caractéristiques topologiques globales (composantes connexes, trous) où aucun témoin existentiel simple n'existe.
3. Justification théorique pour l'approximation : Les résultats expliquent pourquoi les algorithmes de clustering exact sur des densités continues sont intraitables. Puisque ces problèmes sont probablement plus difficiles que NP, l'utilisation répandue de méthodes approximatives, itératives ou basées sur l'échantillonnage dans la pratique est théoriquement justifiée.
4. Lien avec la géométrie algébrique réelle : L'article met en évidence un lien profond entre l'apprentissage non supervisé et les problèmes ouverts en géométrie algébrique réelle. Prouver que le clustering topologique est dans $\exists\mathbb{R}$ nécessiterait de résoudre le problème de la recherche de certificats de taille polynomiale pour la séparation semi-algébrique, une avancée majeure en soi.

Résumé

L'article démontre que le clustering continu exact est fondamentalement plus difficile que NP (en supposant $\text{NP} \neq \exists\mathbb{R}$). Alors que les critères locaux et basés sur les vallées sont complets pour la théorie existentielle des réels, l'introduction de contraintes topologiques globales (comme le comptage de composantes ou la détection de trous) pousse la complexité vers un niveau supérieur de la hiérarchie polynomiale réelle, dépendant de questions non résolues en géométrie semi-algébrique.