Intégrations dans l'apprentissage automatique : simplifier les données complexes

Travailler avec des données non numériques peut être difficile, même pour les data scientists expérimentés. Un modèle d'apprentissage automatique typique s'attend à ce que ses caractéristiques soient des nombres, et non des mots, des e-mails, des pages de site Web, des listes, des graphiques ou des distributions de probabilités. Pour être utiles, les données doivent d'abord être transformées dans un espace vectoriel. Mais comment?

Une approche courante consisterait à traiter une caractéristique non numérique comme catégorielle . Cela pourrait bien fonctionner si le nombre de catégories est petit (par exemple, si les données indiquent une profession ou un pays). Cependant, si nous essayons d'appliquer cette méthode aux e-mails, nous obtiendrons probablement autant de catégories qu'il y a d'échantillons. Il n'y a pas deux e-mails exactement identiques, donc cette approche ne serait d'aucune utilité.

Une autre approche consisterait à définir une distance entre les échantillons de données , une fonction qui nous indique à quel point deux échantillons sont proches. Ou nous pourrions définir une mesure de similarité , qui nous donnerait la même information sauf que la distance entre deux échantillons proches est petite alors que la similarité est grande. Le calcul de la distance (similarité) entre tous les échantillons de données nous donnerait une matrice de distance (ou de similarité). Ce sont des données numériques que nous pourrions utiliser.

Cependant, ces données auraient autant de dimensions qu'il y a d'échantillons, ce qui n'est généralement pas génial si nous voulons les utiliser comme une caractéristique (voir la malédiction de la dimensionnalité) ou pour les visualiser (alors qu'un tracé peut gérer même 6D, je n'ai pas encore pour voir un tracé 100D). Pourrions-nous réduire le nombre de dimensions à un montant raisonnable ?

La réponse est oui! C'est pour cela que nous avons des incorporations .

Qu'est-ce qu'une incorporation et pourquoi l'utiliser ?

Une incorporation est une représentation de faible dimension de données de grande dimension. En règle générale, une intégration ne capture pas toutes les informations contenues dans les données d'origine. Une bonne intégration, cependant, en capturera suffisamment pour résoudre le problème en question.

Il existe de nombreux plongements adaptés à une structure de données particulière. Par exemple, vous avez peut-être entendu parler de word2vec pour les données textuelles ou de descripteurs de Fourier pour les données d'image de forme. Au lieu de cela, nous discuterons de la façon d'appliquer des incorporations à toutes les données où nous pouvons définir une distance ou une mesure de similarité. Tant que nous pouvons calculer une matrice de distance, la nature des données n'a aucune importance. Cela fonctionnera de la même manière, qu'il s'agisse d'e-mails, de listes, d'arborescences ou de pages Web.

Dans cet article, nous vous présenterons différents types d'intégration et discuterons du fonctionnement de certaines intégrations populaires et de la manière dont nous pourrions utiliser les intégrations pour résoudre des problèmes réels impliquant des données complexes. Nous passerons également en revue les avantages et les inconvénients de cette méthode, ainsi que quelques alternatives. Oui, certains problèmes peuvent être mieux résolus par d'autres moyens, mais malheureusement, il n'y a pas de solution miracle dans l'apprentissage automatique.

Commençons.

Comment fonctionnent les incorporations

Toutes les incorporations tentent de réduire la dimensionnalité des données tout en préservant les informations « essentielles » dans les données, mais chaque intégration le fait à sa manière. Ici, nous allons passer en revue quelques plongements populaires qui peuvent être appliqués à une matrice de distance ou de similarité.

Nous n'essaierons même pas de couvrir toutes les incorporations là-bas. Il existe au moins une douzaine d'intégrations bien connues qui peuvent le faire et de nombreuses autres intégrations moins connues et leurs variantes. Chacun d'eux a sa propre approche, ses avantages et ses inconvénients.

Si vous souhaitez voir quelles autres intégrations existent, vous pouvez commencer ici :

• Guide de l'utilisateur de Scikit-learn
• Les éléments de l'apprentissage statistique (deuxième édition), chapitre 14

Matrice des distances

Abordons brièvement les matrices de distance. Trouver une distance appropriée pour les données nécessite une bonne compréhension du problème, des connaissances en mathématiques et parfois de la chance . Dans l'approche décrite dans cet article, cela pourrait être le facteur le plus important contribuant au succès ou à l'échec global de votre projet.

Vous devez également garder à l'esprit quelques détails techniques. De nombreux algorithmes d'intégration supposent qu'une matrice de distance (ou de dissemblance ) $\textbf{D}$ a des zéros sur sa diagonale et est symétrique. Si ce n'est pas symétrique, nous pouvons utiliser $(\textbf{D} + \textbf{D}^T) / 2$ à la place. Les algorithmes utilisant l'astuce du noyau supposeront également qu'une distance est une métrique, ce qui signifie que l'inégalité triangulaire est valable :

\[\pourtous a, b, c \;\; d(a,c) \leq d(a,b) + d(b,c)\]

De plus, si un algorithme nécessite une matrice de similarité à la place, nous pourrions appliquer n'importe quelle fonction monotone décroissante pour transformer une matrice de distance en une matrice de similarité : par exemple, $\exp -x$.

Analyse en composantes principales (ACP)

L'analyse en composantes principales, ou PCA, est probablement l'intégration la plus largement utilisée à ce jour. L'idée est simple : trouver une transformation linéaire des caractéristiques qui maximise la variance capturée ou (de manière équivalente) minimise l'erreur de reconstruction quadratique .

Plus précisément, supposons que les entités soient un exemple de matrice $\textbf{X} \in \mathbb{R}^{n \times p}$ ont $n$ entités et $p$ dimensions. Pour plus de simplicité, supposons que la moyenne de l'échantillon de données est égale à zéro. On peut réduire le nombre de dimensions de $p$ à $q$ en multipliant $\textbf{X}$ par une matrice orthonormée $\textbf{V}_q \in \mathbb{R}^{p \times q}$ :

\[\hat{\textbf{X}} = \textbf{X} \textbf{V}_q\]

Ensuite, $\hat{\textbf{X}} \in \mathbb{R}^{n \times q}$ sera le nouvel ensemble de fonctionnalités. Pour mapper les nouvelles entités dans l'espace d'origine (cette opération s'appelle reconstruction ), nous devons simplement la multiplier à nouveau par $\textbf{V}_q^T$.

Il s'agit maintenant de trouver la matrice $\textbf{V}_q$ qui minimise l'erreur de reconstruction :

\[\min_{\textbf{V}_q} ||\textbf{X}\textbf{V}_q\textbf{V}_q^T - \textbf{X}||^2\]

Les colonnes de la matrice $\textbf{V}_q$ sont appelées directions des composantes principales, et les colonnes de $\hat{\textbf{X}}$ sont appelées composantes principales. Numériquement, nous pouvons trouver $\textbf{V}_q$ en appliquant la décomposition SVD à $\textbf{X}$, bien qu'il existe d'autres façons tout aussi valables de le faire.

L'ACP peut être appliquée directement aux caractéristiques numériques. Ou, si nos caractéristiques ne sont pas numériques, nous pouvons l'appliquer à une matrice de distance ou de similarité.

Si vous utilisez Python, PCA est implémenté dans scikit-learn.

L'avantage de cette méthode est qu'elle est rapide à calculer et assez robuste au bruit dans les données.

L'inconvénient serait qu'il ne peut capturer que des structures linéaires, de sorte que les informations non linéaires contenues dans les données d'origine risquent d'être perdues.

PCA du noyau

Kernel PCA est une version non linéaire de PCA. L'idée est d'utiliser l' astuce du noyau , dont vous avez probablement entendu parler si vous êtes familier avec Support Vector Machines SVM.

Plus précisément, il existe plusieurs façons différentes de calculer l'ACP. L'une d'elles consiste à calculer la décomposition propre de la version double centrée de la matrice de gramme $\textbf{X} \textbf{X}^T \in \mathbb{R}^{n \times n}$. Maintenant, si nous calculons une matrice noyau $\textbf{K} \in \mathbb{R}^{n \times n}$ pour nos données, Kernel PCA la traitera comme une matrice gramme afin de trouver les composantes principales.

Soit $x_i$, $i \in {1,..,n}$ les échantillons de caractéristiques. La matrice noyau est définie par une fonction noyau $K(x_i,x_j)=\langle \phi(x_i),\phi(x_j) \rangle$.

Un choix populaire est un noyau radial :

\[K(x_i,x_j)=\exp -\gamma \cdot d(x_i,x_j)\]

où $d$ est une fonction de distance.

Kernel PCA nous a demandé de spécifier une distance. Par exemple, pour les entités numériques, nous pourrions utiliser la distance euclidienne : $d(x_i,x_j)=\vert\vert x_i-x_j \vert \vert ^2$.

Pour les fonctionnalités non numériques, nous devrons peut-être faire preuve de créativité. Une chose à retenir est que cet algorithme suppose que notre distance est une métrique.

Si vous utilisez Python, Kernel PCA est implémenté dans scikit-learn.

L'avantage de la méthode Kernel PCA est qu'elle peut capturer des structures de données non linéaires.

L'inconvénient est qu'il est sensible au bruit dans les données et que le choix des fonctions de distance et de noyau affectera grandement les résultats.

Mise à l'échelle multidimensionnelle (MDS)

La mise à l'échelle multidimensionnelle (MDS) tente de préserver les distances entre les échantillons à l'échelle mondiale. L'idée est assez intuitive et fonctionne bien avec les matrices de distance.

Plus précisément, étant donné les échantillons d'entités $x_i$, $i \in {1,..,n}$ et une fonction de distance $d$, nous calculons de nouveaux échantillons d'entités $z_i \in \mathbb{R}^{q}$, $i \in {1,..,n}$ en minimisant une fonction de contrainte :

\[\min_{z_1,..,z_n} \sum_{1 \leq i < j \leq n} (d(x_i, x_j) - ||z_i - z_j||)^2\]

Si vous utilisez Python, MDS est implémenté dans scikit-learn. Cependant, scikit-learn ne prend pas en charge la transformation des points hors échantillon, ce qui pourrait être gênant si nous voulons utiliser une incorporation en conjonction avec un modèle de régression ou de classification. En principe, cependant, c'est possible.

L'avantage de MDS est que son idée s'accorde parfaitement avec notre cadre et qu'il n'est pas très affecté par le bruit dans les données.

L'inconvénient est que son implémentation dans scikit-learn est assez lente et ne prend pas en charge la transformation hors échantillon.

Cas d'utilisation : suivi des envois

Quelques colonies sur une petite île tropicale ont développé des services d'expédition de colis pour répondre aux besoins de l'industrie touristique locale. Un commerçant de l'une de ces colonies a décidé de prendre des mesures pour prendre l'avantage sur la concurrence. Il a donc mis en place un système de surveillance par satellite pour suivre toutes les expéditions de colis sur l'île. Une fois les données collectées, le commerçant a fait appel à un data scientist (c'est nous !) pour l'aider à répondre à la question suivante : Peut-on prédire la destination d'un colis actuellement en route ?

L'ensemble de données contient des informations sur 200 envois suivis. Pour chaque envoi suivi, il existe une liste des coordonnées (x,y) de tous les emplacements où le colis a été repéré, ce qui correspond généralement à 20 et 50 observations. Le graphique ci-dessous montre à quoi ressemblent ces données.

Ces données ressemblent à des problèmes - deux saveurs différentes de problèmes, en fait.

Le premier problème est que les données que nous traitons sont de grande dimension. Par exemple, si chaque colis était repéré à 50 endroits, nos données auraient 100 dimensions, ce qui semble beaucoup, comparé aux 200 échantillons à votre disposition.

Le deuxième problème : différentes routes d'expédition ont en fait un nombre différent d'observations, nous ne pouvons donc pas simplement empiler les listes avec des coordonnées pour représenter les données sous forme de tableau (et même si c'était le cas, cela n'aurait toujours pas vraiment de sens).

Le marchand tambourine avec impatience sur la table avec ses doigts, et le data scientist s'efforce de ne montrer aucun signe de panique.

C'est là que les matrices de distance et les plongements seront utiles. Nous devons juste trouver un moyen de comparer deux itinéraires d'expédition. La distance de Fréchet semble être un choix raisonnable. Avec une distance, nous pouvons calculer une matrice de distance.

Remarque : Cette étape peut prendre un certain temps. Nous devons calculer $O(n^2)$ distances avec chaque distance ayant $O(k^2)$ itérations, où $n$ est le nombre d'échantillons et $k$ est le nombre d'observations dans un échantillon. L'écriture efficace d'une fonction de distance est essentielle. Par exemple, en Python, vous pouvez utiliser numba pour accélérer ce calcul plusieurs fois.

Visualisation des représentations incorporées

Maintenant, nous pouvons utiliser une intégration pour réduire le nombre de dimensions de 200 à quelques-unes. Nous pouvons clairement voir qu'il n'y a que quelques routes commerciales, nous pouvons donc espérer trouver une bonne représentation des données même en deux ou trois dimensions. Nous utiliserons les intégrations dont nous avons parlé précédemment : PCA, Kernel PCA et MDS.

Sur les tracés ci-dessous, vous pouvez voir les données d'itinéraire étiquetées (données à titre de démonstration) et leur représentation par un plongement en 2D et 3D (de gauche à droite). Les données étiquetées marquent quatre postes commerciaux reliés par six routes commerciales. Deux des six routes commerciales sont bidirectionnelles, ce qui fait huit groupes d'expédition au total (6+2). Comme vous pouvez le voir, nous avons obtenu une séparation assez claire des huit groupes d'expédition avec des intégrations 3D.

C'est un bon début.

Incorporations dans un pipeline modèle

Maintenant, nous sommes prêts à former une incorporation. Bien que MDS ait montré les meilleurs résultats, il est plutôt lent ; De plus, l'implémentation de scikit-learn ne prend pas en charge la transformation hors échantillon. Ce n'est pas un problème pour la recherche mais cela peut l'être pour la production, nous utiliserons donc le noyau PCA à la place. Pour Kernel PCA, il ne faut pas oublier d'appliquer au préalable un noyau radial à la matrice de distance.

Comment sélectionnez-vous le nombre de dimensions de sortie ? L'analyse a montré que même la 3D fonctionne bien. Juste pour être sûr et ne pas laisser de côté des informations importantes, réglons la sortie d'intégration sur 10D. Pour de meilleures performances, le nombre de dimensions de sortie peut être défini comme un hyper-paramètre de modèle, puis ajusté par validation croisée.

Nous aurons donc 10 caractéristiques numériques que nous pourrons utiliser comme entrée pour à peu près n'importe quel modèle de classification. Que diriez-vous d'un modèle linéaire et d'un modèle non linéaire : par exemple, la régression logistique et l'amplification des gradients ? À titre de comparaison, utilisons également ces deux modèles avec une matrice de distance complète comme entrée. En plus de cela, testons également SVM (SVM est conçu pour fonctionner directement avec une matrice de distance, donc aucune intégration ne serait nécessaire).

La précision du modèle sur l'ensemble de test est indiquée ci-dessous (10 ensembles de données d'entraînement et de test ont été générés afin que nous puissions estimer la variance du modèle) :

• Le Gradient Boosting associé à un embedding (KernelPCA+GB) obtient la première place. Il a surpassé Gradient Boosting sans intégration (Go). Ici, Kernel PCA s'est avéré utile.
• La régression logistique a bien fonctionné. Ce qui est intéressant, c'est que la régression logistique sans intégration (LR) a mieux fonctionné qu'avec une intégration (KernelPCA + LR). Ce n'est pas tout à fait inattendu. Les modèles linéaires ne sont pas très flexibles mais relativement difficiles à surajuster. Ici, la perte d'informations causée par une incorporation semble l'emporter sur l'avantage d'une dimensionnalité d'entrée plus petite.
• Enfin, SVM a également bien performé, bien que la variance de ce modèle soit assez importante.

Précision du modèle

Le code Python pour ce cas d'utilisation est disponible sur GitHub.

Conclusion

Nous avons expliqué ce que sont les plongements et démontré comment ils peuvent être utilisés conjointement avec des matrices de distance pour résoudre des problèmes du monde réel. L'heure du verdict :

Les intégrations sont-elles quelque chose qu'un data scientist devrait utiliser ? Jetons un coup d'œil aux deux côtés de l'histoire.

Avantages et inconvénients de l'utilisation des incorporations

Avantages:

• Cette approche nous permet de travailler avec des structures de données inhabituelles ou complexes tant que vous pouvez définir une distance, ce qui, avec un certain degré de connaissance, d'imagination et de chance, vous le pouvez généralement.
  
• La sortie est constituée de données numériques de faible dimension, que vous pouvez facilement analyser, regrouper ou utiliser comme caractéristiques de modèle pour pratiquement tous les modèles d'apprentissage automatique.

Les inconvénients:

• En utilisant cette approche, on va forcément perdre certaines informations :

  • Au cours de la première étape, lorsque nous remplaçons les données d'origine par la matrice de similarité
  • Au cours de la deuxième étape, lorsque nous réduisons la dimensionnalité à l'aide d'un plongement
• Selon les données et la fonction de distance, le calcul d'une matrice de distance peut prendre du temps. Ceci peut être atténué par une fonction de distance écrite efficacement.
• Certaines représentations vectorielles continues sont très sensibles au bruit dans les données. Cela peut être atténué par un nettoyage supplémentaire des données.
• Certains plongements sont sensibles au choix de ses hyper-paramètres. Cela peut être atténué par une analyse minutieuse ou un réglage des hyperparamètres.

Alternatives : pourquoi ne pas utiliser… ?

• Pourquoi ne pas simplement utiliser un plongement directement sur les données, plutôt qu'une matrice de distance ?
  Si vous connaissez une intégration capable d'encoder efficacement vos données directement, par tous les moyens, utilisez-la. Le problème est qu'il n'existe pas toujours.
  
• Pourquoi ne pas simplement utiliser la clusterisation sur une matrice de distance ?
  Si votre seul objectif est de segmenter votre ensemble de données, ce serait tout à fait acceptable de le faire. Certaines méthodes de clusterisation tirent également parti des intégrations (par exemple, le clustering spectral). Si vous souhaitez en savoir plus, voici un tutoriel sur la clusterisation.
  
• Pourquoi ne pas simplement utiliser une matrice de distance comme caractéristiques ?
  La taille d'une matrice de distance est $(n_{échantillons}, n_{échantillons})$. Tous les modèles ne peuvent pas y faire face efficacement - certains peuvent sur-adapter, certains peuvent être lents à s'adapter, certains peuvent ne pas s'adapter complètement. Les modèles à faible variance seraient un bon choix ici, tels que les modèles linéaires et/ou régularisés.
  
• Pourquoi ne pas simplement utiliser SVM avec une matrice de distance ?
  SVM est un excellent modèle, qui a bien fonctionné dans notre cas d'utilisation. Cependant, il y a quelques mises en garde. Tout d'abord, si nous voulons ajouter d'autres fonctionnalités (il peut s'agir de simples nombres numériques), nous ne pourrons pas le faire directement. Nous devrions les incorporer dans notre matrice de similarité et perdre potentiellement des informations précieuses. Deuxièmement, aussi bon que soit SVM, un autre modèle peut mieux fonctionner pour votre problème particulier.
  
• Pourquoi ne pas simplement utiliser le deep learning ?
  C'est vrai, pour n'importe quel problème, vous pouvez trouver un réseau de neurones adapté si vous cherchez assez longtemps. Gardez à l'esprit, cependant, que le processus de recherche, de formation, de validation et de déploiement de ce réseau de neurones ne sera pas nécessairement simple. Alors, comme toujours, utilisez votre meilleur jugement.

En une phrase

Les plongements en conjonction avec les matrices de distance sont un outil extrêmement utile si vous travaillez avec des données non numériques complexes, en particulier lorsque vous ne pouvez pas transformer directement vos données en un espace vectoriel et que vous préférez avoir une entrée de faible dimension pour votre modèle.