Topologie et apprentissage machine

novembre 13, 2017

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 à callen15@uoguelph.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 $\gamma$ , 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 $\gamma$ nous est cachée, mais que nous pigions au hasard des points $x_1, x_2, \dots, x_n$ du plan $\mathbb{R}^2$ étiquetés respectivement par $\ell_1, \ell_2, \dots, \ell_n \in \{0, 1\}$ . On nous assure que si $x_i$ est dans la région bornée par la courbe $\gamma$ , alors $\ell_i = 0$ avec probabilité plus grande que $1/2$ ; et si $x_i$ est dans la région non bornée, alors $\ell_i = 1$ avec probabilité plus grande que $1/2$ . Est-il possible d’apprendre des exemples observés pour reconstruire la courbe et prédire l’étiquette d’un point $x_{n+1}$ ?

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 $\gamma$ 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é $(0,1)^2$ . Notons $p$ la fonction qui associe à un point $x\in (0,1)^2$ sa probabilité d’être étiquetté $0$ . On suppose que $\gamma$ est la courbe de niveau $1/2$ de $p$ , que $p$ est lisse (infiniment différentiable) et que $\nabla p(x) \not = 0$ pour tout $x \in \gamma$ . Notre mesure de distance entre la courbe $\gamma$ et une autre courbe $\widehat{\gamma}$ 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 $\gamma = p^{-1}(1/2)$ en approximant tout d’abord $p$ 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 $f$ tel que $f^{-1}(1/2)$ est une courbe difféomorphe¹ à $\gamma$ et tel que $f^{-1}(1/2)$ est arbitrairement proche de $\gamma$ 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 $f_k: (0,1)^2 \rightarrow \mathbb{R}$ , $k \in \mathbb{N}$ , une suite de fonctions lisses convergeant uniformément vers $p$ et telle que $\nabla f_k$ converge aussi uniformément vers $\nabla p$ . Alors, $f^{-1}_k(1/2)$ converge vers $\gamma$ dans la métrique de Hausdorff. De plus, pour tout $k$ suffisamment grand, $f_k^{-1}(1/2)$ est difféomorphe à $\gamma$ .

En fait, par une extension du théorème d’approximation de Weierstrass [4], on peut utiliser pour $f_k$ le polynôme

(1) $\begin{equation*} f_k(u,v) = (k+1)^2 \sum_{i,j = 0}^k \left(\int_{R_{i,j}^k} p({\bf x}) \,\mathrm{d}{\bf x} \right) B_{i}^k(u) B_j^k(v),\end{equation*}$

où les $B_i^k$ sont les polynômes de Bernstein $B_j^k(u) = {k \choose j} u^j (1-u)^{k-j}$ et les $R_{i,j}^k$ sont les petits carrés $R_{i,j}^k = [\tfrac{i}{k+1}, \tfrac{i+1}{k+1}]\times [\tfrac{j}{k+1}, \tfrac{j+1}{k+1}]$ . Mais puisque $p$ nous est inconnue, il faut remplacer $(k+1)^2\int_{R_{i,j}^k} p({\bf x}) \,\mathrm{d}{\bf x}$ dans (1) par une estimation. Pour faire simple, on utilise la moyenne empirique

$E_{i,j}^n = \frac{N_0(i,j) + 1}{N_0(i,j) + N_1(i,j) + 2},$

où $N_\ell (i,j)$ est le nombre de points parmi $\{x_1, x_2, \dots, x_n\}$ étiquettés $\ell$ et tombant dans la région $R_{i,j}^k$ . Alors, si $k = k(n)$ est une fonction du nombre $n$ d’observations croissant suffisamment lentement, les estimées $E_{i,j}^n$ seront uniformément précises: on peut obtenir, avec probabilité 1 (ce que nous omettrons de mentionner à nouveau), $\sup_{i,j} |E_{i,j}^n - (k+1)^2 \int _{R_{i,j}^n} p({\bf x}) \,\mathrm{d}{\bf x}| = o(1/n)$ . Dans ce cas, on vérifie que

$\hat f_k(u,v) = \sum_{i,j=0}^k E_{i,j}^n B_i^k(u) B_j^k(v)$

est telle que $\hat f_k$ et $\nabla \hat f_k$ convergent uniformément vers $f_k$ et $\nabla f_k$ , respectivement. Il suit enfin du Lemme 1 que $\hat f_k^{-1}(1/2)$ est une courbe éventuellement difféomorphe à $\gamma = p^{-1}(1/2)$ et convergeant vers $\gamma$ 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é $(0,1)^2$ 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 $\gamma$ une hypersurface de séparation compacte. Le fait que $f_k^{-1}(1/2)$ soit éventuellement difféomorphe à $\gamma$ 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.

« Why Compactness? »

septembre 29, 2017

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 premier 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 à callen15@uoguelph.ca, et ce, tout au long de l’année.

L’article de septembre est en anglais; il est disponible ici.