Topologie et apprentissage machine
Notes from the Margin, la publication biannuelle du comité étudiant de la SMC contenant des articles de la communauté étudiante pour un public amateur de mathématiques, offre depuis plusieurs années une plateforme pour des sujets passant de l’analyse de Fourier d’ordre supérieur à comment se préparer aux entrevues pour des postes dans le milieu académique. C’est avec beaucoup d’excitation que nous vous présentons le deuxième article du blogue de Notes from the Margin qui complémentera, sans toutefois remplacer, la revue biannuelle imprimée. Nous vous invitons à soumettre vos idées d’article à student-editor@cms.math.ca, et ce, tout au long de l’année.
Topologie et apprentissage machine
Olivier Binette
1. Le problème
Rappelons le Théorème de Jordan: une courbe , simple et régulière, sépare le plan en deux régions connexes, l’une d’entre elles étant bornée. Supposons maintenant que
nous est cachée, mais que nous pigions au hasard des points
du plan
étiquetés respectivement par
. On nous assure que si
est dans la région bornée par la courbe
, alors
avec probabilité plus grande que
; et si
est dans la région non bornée, alors
avec probabilité plus grande que
. Est-il possible d’apprendre des exemples observés pour reconstruire la courbe et prédire l’étiquette d’un point
?

Figure 1. Une courbe (en noir) sépare le carré en deux régions. Des points sont colorés bleu ou vert avec une plus grande probabilité d’être bleu s’ils sont dans la région inférieure, et une plus grande probabilité d’être vert autrement. La courbe est reconstruite (en pointillé) en utilisant ces données et la méthode de la section 2.
C’est le problème de la classification binaire, typique de l’apprentissage machine: on veut apprendre à distinguer les éléments de deux catégories et identifier la frontière de séparation à partir d’exemples (probablement) bien classés.
Nous verrons comment un théorème classique de la géométrie algébrique réelle nous donne une solution qui, dans la limite du grand nombre d’exemples, permet de reconstruire d’une façon topologiquement et métriquement exacte.
1.1 Modèle et hypothèses. Contraignons le problème à une région bornée du plan, disons le carré . Notons
la fonction qui associe à un point
sa probabilité d’être étiquetté
. On suppose que
est la courbe de niveau
de
, que
est lisse (infiniment différentiable) et que
pour tout
. Notre mesure de distance entre la courbe
et une autre courbe
est donnée par la métrique de Hausdorff: c’est la plus grande distance possible entre un point sur une courbe et son point le plus proche sur l’autre courbe.
2. Reconstruction de la frontière de séparation
L’idée est de reconstruire en approximant tout d’abord
par un polynôme en deux variables. Par le Théorème de Nash-Tognoli de la géométrie algébrique réelle, l’approche est valable: il existe un polynôme
tel que
est une courbe difféomorphe1 à
et tel que
est arbitrairement proche de
dans la métrique de Hausdorff. La preuve de ce théorème, dans notre cas, s’appuie sur le résultat suivant.
Lemme 1 (voir [2]). Soit ,
, une suite de fonctions lisses convergeant uniformément vers
et telle que
converge aussi uniformément vers
. Alors,
converge vers
dans la métrique de Hausdorff. De plus, pour tout
suffisamment grand,
est difféomorphe à
.
En fait, par une extension du théorème d’approximation de Weierstrass [4], on peut utiliser pour le polynôme
(1)
où les sont les polynômes de Bernstein
et les
sont les petits carrés
. Mais puisque
nous est inconnue, il faut remplacer
dans (1) par une estimation. Pour faire simple, on utilise la moyenne empirique
où est le nombre de points parmi
étiquettés
et tombant dans la région
. Alors, si
est une fonction du nombre
d’observations croissant suffisamment lentement, les estimées
seront uniformément précises: on peut obtenir, avec probabilité 1 (ce que nous omettrons de mentionner à nouveau),
. Dans ce cas, on vérifie que
est telle que et
convergent uniformément vers
et
, respectivement. Il suit enfin du Lemme 1 que
est une courbe éventuellement difféomorphe à
et convergeant vers
dans la métrique de Hausdorff lorsque le nombre d’observations augmente.

Figure 2. Détection des contours d’une image utilisant notre méthode de classification. Quelques points de la photo ont étés manuellement classifiés contour (en bleu) ou intérieur (en vert). On choisit ensuite une fonction pour la plonger sur le carré et on classifie automatiquement les autres points.
2.1 Extensions. Plus généralement, on considère des classes contenues dans un espace euclidien et une hypersurface de séparation compacte. Le fait que
soit éventuellement difféomorphe à
nous assure que chaque propriété topologique de la surface, comme son nombre de composantes connexes et son genre, sera éventuellement découverte.
Je suis toujours fasciné de voir les mathématiques s’appliquer à la résolution de problèmes concrets, même si je ne m’en étonne plus!
Références
[1] Hastie, T., Tibshirani, R. and Friedman, J. The elements of statistical learning. Second edition. Springer Series in Statistics. Springer, New York, 2009.
[2] Kollar, J. Nash’s Work in Algebraic Geometry. Bull. Amer. Math. Soc. (N.S.) 54 no. 2 (2017) 307-324.
[3] Lima, E. L. The Jordan-Brouwer separation theorem for smooth hypersurfaces. Amer. Math. Monthly 95 no. 1 (1988) 39-42.
[4] Telyakovskii, S. A. On the approximation of dierentiable functions by Bernstein polynomials and Kantorovich polynomials. Proc. Steklov Inst. Math. 260 no. 1 (2008) 279-286.
[5] Vapnik, V. N. Statistical learning theory. John Wiley & Sons, Inc., New York, 1998.
Note de bas de page
1. Un difféomorphisme est une fonction différentiable inversible dont l’inverse est aussi différentiable.
Olivier Binette étudie en probabilité et statistique à l’Université du Québec à Montréal. On peut le trouver sur le campus à boire du thé et à jouer au hacky sack. Dans ses temps libres, il aime travailler sur divers petits projets allant de la restauration de vieux meubles à la conception électronique.