• 12 heures
  • Moyenne
Licence

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 29/01/2024

Initiez-vous à l'apprentissage large échelle (Large Scale Learning)

L'objectif du cours est de :

  • comprendre les problématiques liées au traitement de données à large échelle,

  • se familiariser en particulier avec la complexité en temps et la complexité mémoire des algorithmes que nous avons vu dans ce cours,

  • apprendre à mettre en œuvre les méthodes de type gradient stochastique et leurs variantes pour casser la complexité algorithmique.

Analysez la complexité algorithmique

Nous avons vu dans les chapitres précédents des méthodes d'apprentissage statistique pour :

  • la réduction de dimension (ACP),

  • le clustering (K-Means),

  • la régression linéaire (avec ou sans régularisation),

  • la classification (régression logistique et SVM).

Ces méthodes requièrent de résoudre des problèmes d'optimisation qui dépendent du nombre $\(n\)$ et la dimension $\(d\)$ des données. La problématique de l'apprentissage à large échelle apparaît lorsque ce nombre d'observations est très grand et/ou la dimension augmente. Le tableau 1 illustre la volumétrie de quelques bases de données publiques liées à l'IOT.

Données

Nombre de points $\(n\)$

Dimension $\(d\)$

IoT botnet attacks

7.062.606

115

Home activity monitoring

919.438

11

Heterogeneity Activity Recognition

43.930.257

16

Tableau 1 : Exemples de données IOT

Pour appréhender la problématique, nous allons rappeler le principe des algorithmes étudiés dans les précédents chapitres et analysez leur complexité.

Analyse en composantes principales

Elle vise à projeter linéairement des données centrées  $\(\{\mathbf{x}_i \in \mathbb{R}^d \}_{i=1}^n\)$ en des points  $\(\{\mathbf{t}_i \in \mathbb{R}^p \}_{i=1}^n\)$ de dimension $\(p < d\)$ en utilisant la matrice de projection  $\(\mathbf{U} = \begin{bmatrix} \mathbf{u}_1 & \cdots & \mathbf{u}_p \end{bmatrix}\)$ . Les colonnes  $\(\mathbf{u}_k\)$ de $\(\mathbf{U}\)$ sont les vecteurs propres de la matrice de covariance

$\[\mathbf{C} = \frac{1}{n} \sum_{i=1}^n {\mathbf{x}}_i \, {\mathbf{x}}_i^\top \in \mathbb{R}^{d\times d}\]$

La complexité de l'ACP se décompose comme suit :

  • Ressources mémoire :  $\(\mathcal{O}\left(d^2\right)\)$ pour stocker la matrice $\(\mathbf{C}\)$ ,

  • Complexité en temps : le calcul de $\(\mathbf{C}\)$ requiert $\(\mathcal{O}\left( n \, d^2 \right)\)$ opérations et celui de $\(\mathbf{U}\)$  nécessite $\(\mathcal{O}\left( p \, d^2 \right)\)$ opérations.

K-Means

Cette méthode itérative de catégorisation des données  $\(\{\mathbf{x}_i \in \mathbb{R}^d \}_{i=1}^n\)$ en $\(K\)$ clusters, comprend à chaque itération deux étapes : (i) une étape d'affectation des points à un cluster, et (ii) une mise à jour des centres.  Sa complexité est de deux ordres :

  • Complexité mémoire : 

     $\(\mathcal{O}(n\times d)\)$ pour les données augmenté de $\(\mathcal{O}(K\times d)\)$ pour le stockage des centres, soit principalement le coût de stockage des données ;

  • Complexité en temps : (i) affectation des points aux clusters : $\(\mathcal{O}(n\times d \times K)\)$ et (ii) mise à jour des centres : $\(\mathcal{O}(n\times d)\)$ 

La complexité calculatoire globale est de l'ordre de $\(\mathcal{O}(n\times d \times K \times T)\)$ où $\(T\)$ est le nombre total d'itérations.

Régression linéaire

Elle consiste à apprendre le modèle linéaire $\(f(\mathbf{x}) = \mathbf{x}^\top\boldsymbol{\beta}\)$ à partir de données $\(\{(\mathbf{x}_i, y_i) \in \mathbb{R}^d \times \mathbb{R} \}_{i=1}^n\)$ . Les  paramètres  $\(\boldsymbol{\beta}\)$ sont estimés par minimisation du critère des moindres carrés $\(\,\, \frac{1}{n} \sum_{i=1}^n \, (y_i - \mathbf{x}_i^\top \boldsymbol{\beta})^2.\)$ Nous avons établi que la solution est

$\[\hat{\boldsymbol{\beta}} = \left( \mathbf{X}^\top \mathbf{X} \right)^{-1}(\mathbf{X}^\top \mathbf{Y}) \hspace{100pt} (1)\]$

où $\(\mathbf{X} \in \mathbb{R}^{n \times d}\)$ et $\(\mathbf{Y} \in \mathbb{R}^n\)$ sont respectivement la matrice des entrées et le vecteur de sortie. Cela engendre :

  • une compléxité mémoire de $\(\mathcal{O}\left(d^2\right)\)$ pour stocker la matrice $\(\mathbf{X}^\top \mathbf{X}\)$ et $\(\mathcal{O}(d)\)$ pour le vecteur $\(\mathbf{X}^\top \mathbf{Y}\)$ ;

  •  $\(\mathcal{O}(n \times d^2)\)$ opérations pour le calcul de $\(\mathbf{X}^\top \mathbf{X}\)$ et $\(\mathcal{O}(n \times d)\)$ opérations pour calculer $\(\mathbf{X}^\top \mathbf{Y}\)$. Le calcul de  $\(\hat{\boldsymbol{\beta}}\)$ coûte $\(\mathcal{O}(d^3)\)$ opérations.

Cette complexité est similaire si l'on considère la régression ridge.

Régression logistique linéaire

Dans le cadre d'un problème de classification binaire de données  $\(\{(\mathbf{x}_i, y_i) \in \mathbb{R}^d \times \{0, 1\} \}_{i=1}^n\)$ ,  les paramètres du modèle de régression logistique linéaire $\(f(\mathbf{x}) = \mathbf{x}^\top\boldsymbol{\beta}\)$ se déterminent par résolution du problème

$\(\min_{\boldsymbol{\beta}}J(\boldsymbol{\beta}) = \sum_{i=1}^n \,\, \big[- y_i \, \boldsymbol{x}_i^\top \, \boldsymbol{\beta} + \log \left(1 + \exp^{\boldsymbol{x}_i^\top \,\, \boldsymbol{\beta}} \,\, \right) \big]\)$

Nous avons vu qu'on pouvait utiliser la méthode de descente de gradient pour calculer itérativement les paramètres $\(\boldsymbol{\beta}^t = \boldsymbol{\beta}^{t-1} - \alpha_t \nabla J\left(\beta^{t-1}\,\, \right) \quad \text{avec} \quad \nabla J\left(\beta^{t-1}\,\, \right) = \, \sum_{i=1}^n \,\, \left(y_i - \frac{\exp^{\boldsymbol{x}_i^\top} \boldsymbol{\beta}^{t-1} \,\, }{1 + \exp^{\boldsymbol{x}_i^\top} \boldsymbol{\beta}^{t-1} \,\, } \, \right) \, \boldsymbol{x}_i \, \hspace{25pt} (2)\)$ Le calcul du gradient nécessite environ $\(\mathcal{O}(n \times d)\)$ opérations ; nous déduisons, si on effectue $\(T\)$ itérations, une complexité en temps de l'ordre de $\(\mathcal{O}(n \times d \times T)\)$ .

SVM

Nous avons montré dans le chapitre précédent que l'apprentissage d'un modèle SVM linéaire nécessite de résoudre le dual, qui est un problème de programmation quadratique. Une implémentation directe (et un peu naïve) du problème dual nécessite une complexité en temps de $\( \mathcal{O}(n^3)\)$ et une complexité en mémoire de $\( \mathcal{O}(n^2)\)$ pour stocker la matrice de noyau $\(\mathbf{K} \in \mathbb{R}^{n \times n}\)$ avec $\(K_{ij} = \mathbf{x}_i^\top \mathbf{x}_j\)$ .

Adaptez ces algorithmes à la large échelle

Comment faire tourner ces méthodes sur son ordinateur personnel si $\(n\)$ et $\(d\)$ sont grands

Nous pouvons exploiter la structure des problèmes d'optimisation liés à ces algorithmes. Considérons les modèles de régression linéaire, régression logistique ridge et SVM de la forme $\(f(\mathbf{x}) = \boldsymbol{x}^\top \,\, \boldsymbol{\beta}\)$ . Leur problème d'optimisation peut s'écrire sous la forme générale  $\(\min_{\boldsymbol{\beta}}J(\boldsymbol{\beta}) = \frac{1}{n} \sum_{i=1}^n \,\, \left[\, \ell(y_i, \, f(\mathbf{x}_i)) + \lambda \, \| \boldsymbol{\beta} \|^2 \, \right] \hspace{100pt} (3)\)$

avec $\(\lambda > 0\)$ et la fonction de perte (voir figure 1) :

  •  $\(\ell(y_i, f(\mathbf{x}_i)) = (y_i - \boldsymbol{x}_i^\top \,\, \boldsymbol{\beta})^2\)$ pour la régression linéaire

  •   $\(\ell(y_i, f(\mathbf{x}_i)) = \,- y_i \, \boldsymbol{x}_i^\top \, \boldsymbol{\beta} + \log \left(1 + \exp^{\boldsymbol{x}_i^\top \,\, \boldsymbol{\beta}} \,\, \right)\)$  pour la régression logistique,

  • $\(\ell(y_i, f(\mathbf{x}_i)) = \max(0, 1 - y_i \, \boldsymbol{x}_i^\top\boldsymbol{\beta})\)$ pour le SVM.

Figure 1 : fonctions de perte usuelles pour la régression et la classification.
Figure 1 : fonctions de perte usuelles pour la régression et la classification

La premier terme de l'équation (3) mesure l'adéquation entre la prédiction $\(f(\mathbf{x}_i)\)$ et la vraie sortie $\( y_i\)$ (terme d'erreur) ; le second terme est la régularisation ridge. La remarque importante à faire, c'est que le critère J(\boldsymbol{\beta}) s'écrit comme la somme de $\(n\)$ éléments : c'est cette information que nous allons exploiter.

Au lieu d'utiliser simultanément toutes les données pour calculer les paramètres de ces modèles comme dans les équations (1) et (2), on cherche à casser la complexité en temps en sous-échantillonnant et en traitant les données par petits lots (le cas extrême est de les traiter une à une).  Qu'est-ce que cela change ? Cela aboutit à considérer des algorithmes stochastiques de résolution dont certains sont présentés ci-dessous.

Approches de gradient stochastique

Nous allons nous concentrer dans cette partie sur les problèmes de régression linéaire ou de régression logistique pour la classification binaire pour illustrer le principe des approches stochastiques.

Gradient stochastique (Stochastic Gradient Descend, SGD)

Le principe de cette approche pour résoudre le problème (3) est résumé par les lignes suivantes :

  • Initialisez $\(t=0\)$ et $\( \boldsymbol{\beta}^t\)$

  • A chaque itération $\(t \)$

    • tirez aléatoirement un point $\((\mathbf{x}_{i}, y_{i})\)$ , $\(i \in \{1, \cdots, n\}\)$ des données d'apprentissage ;

    • calculez le gradient partiel $\(\tilde{\mathbf{g}}_t = \nabla \ell \left (y_{i}, \boldsymbol{x}_i^\top \boldsymbol{\beta}^{t-1} \, \right) + \lambda \, \boldsymbol{\beta}^{t-1}\)$ ;

    • mettez à jour les paramètres par  $\(\boldsymbol{\beta}^t = \boldsymbol{\beta}^{t-1} - \alpha_t \,\, \tilde{\mathbf{g}}_t\)$ avec $\( \alpha_t\)$ le pas ;

    • (Optionnel) moyennez les estimées $\(\bar{\boldsymbol{\beta}} = \frac{1}{t} \sum_{k=1}^t \,\, \boldsymbol{\beta}^k\)$ .

Quels sont les avantages et les inconvénients du SGD ?

Chaque itération de la méthode du gradient (voir équation (2)) nécessite le calcul du gradient global $\(\mathbf{g} = \sum_{i=1}^n \, \tilde{\mathbf{g}}_i\)$ , qui est la somme de $\( n\)$ gradients partiels. Il faut donc "visiter" tous les points d'apprentissage avant de faire la mise à jour des paramètres. A contrario, le gradient stochastique se contente d'un gradient partiel courant $\(\tilde{\mathbf{g}}_t = \nabla \ell \left (y_{i}, \boldsymbol{x}_i^\top \boldsymbol{\beta}^{t-1} \, \right) + \lambda \, \boldsymbol{\beta}^{t-1}\)$ pour mettre à jour les paramètres.

La complexité par itération est donc :

  • pour la méthode du gradient, $\(\mathcal{O}(n \times d)\)$ opérations,

  • pour la méthode du gradient stochastique, $\(\mathcal{O}(d)\)$ opérations.

Nous comparons, sur la figure 2, l'évolution des paramètres $\(\boldsymbol{\beta} \)$ au fil des itérations pour la méthode du gradient et du gradient stochastique. Sur chaque graphe, les points bleu et rouge représentent respectivement l'initialisation et la solution et les points noirs les solutions intermédiaires. Les lignes de niveau sont celles du critère d'entropie binaire.

Nous constatons que les estimations du SGD évoluent de façon un peu erratique sur les lignes de niveau. Chaque estimation ne conduit pas nécessairement à une diminution du critère $\(J\)$ à cause du gradient partiel, mais au final le SGD converge vers une solution proche de celle du GD.

Figure 1 : comparaison méthodes du gradient et gradient stochastique sur le problème de classification d'athlètes à partir de données biologiques (voir chapitre sur la régression logistique). Sur chaque figure, le point bleu représente l'initialisa
Figure 2 : comparaison méthodes du gradient et gradient stochastique sur le problème de classification d'athlètes à partir de données biologiques (voir chapitre sur la régression logistique)
SAG (Stochastic Average Gradient)

Cette technique vise à obtenir les avantages des deux méthodes : la complexité par itération du SGD et le nombre d'itérations (la vitesse de convergence) de la méthode du gradient. Son principe est de calculer une approximation du gradient meilleure que le gradient partiel du SGD. Il est illustré ci-dessous :

  • Initialisez $\(t=0\)$ ,  $\(\boldsymbol{\beta}^t \)$ et les gradients partiels $\(\tilde{\mathbf{g}}_i, \forall \, i=1, \cdots, n\)$ 

    À chaque itération $\(t \)$

    • tirez aléatoirement un point $\((\mathbf{x}_{i}, y_{i})\)$ , $\(i \in \{1, \cdots, n\}\)$ des données d'apprentissage,

    • calculez $\(a_t = \nabla \ell \left (y_{i}, \boldsymbol{x}_i^\top \boldsymbol{\beta}^{t-1} \, \right) + \lambda \, \boldsymbol{\beta}^{t-1}\)$

    • calculez une approximation du gradient

      $\[{\mathbf{g}}_t = \sum_{j=1}^n \, \tilde{\mathbf{g}}_j = \mathbf{g}_{t-1} - \tilde{\mathbf{g}}_i + a_t\]$

    • mettez à jour le gradient partiel  \tilde{\mathbf{g}}_i = a_t

    • mettez à jour les paramètres $\(\boldsymbol{\beta}^t = \boldsymbol{\beta}^{t-1} - \alpha_t \,\, {\mathbf{g}}_t\)$ avec $\(\alpha_t > 0\)$ le pas.

Nous constatons donc que cette approche permet d'obtenir le meilleur des deux mondes : le coût par itérations du SGD et la vitesse de convergence du GD, moyennant des ressources mémoire supplémentaires pour stocker les gradients partiels. La figure 3 compare la vitesse de convergence de GD, SGD et SAG. On constate au début la décroissance plus rapide de   $\(J(\boldsymbol{\beta}^t) - J(\boldsymbol{\beta}^*)\)$ pour le SGD, comparativement à GD suivi d'une stagnation. SAG fait décroître plus rapidement l'écart à l'optimum avec un taux de décroissance linéaire.

Figure 1 : Comparaison GD, SGD et SAG
Figure 3 : Comparaison GD, SGD et SAG sur un problème de régression logistique avec \(n = 10^4 \) et \(d=100\). L'axe des ordonnées est en échelle logarithmique.

Notons qu'il existe d'autres approches stochastiques pour résoudre le problème (3) comme SAGA ou SVRG. Sous scikit learn, pour apprendre un modèle de régression logistique plusieurs solveurs, sont proposés comme  solveurs : Newton-CG, L-BFGS (des méthodes d'optimisation de type 2e ordre), SAG ou SAGA. La régression linéaire ridge avec scikit learn peut également se résoudre avec des solveurs SAG ou SAGA. Il faut donc choisir le solveur le plus adapté à la volumétrie et à la dimensionalité des données d'apprentissage.

En résumé

Trouver un modèle de machine learning revient généralement à résoudre un problème d'optimisation défini à partir de $\(n\)$ données. Ce problème se formule souvent comme la somme de fonctions de perte sur les $\(n\)$ points d'apprentissage et d'un terme de régularisation du modèle. Ce chapitre a permis de comprendre :

  • les problématiques de complexité algorithmique liées à la résolution du problème d'optimisation pour des données à large échelle,

  • le principe des approches stochastiques utilisées pour casser la complexité algorithmique et obtenir des solutions raisonnables en temps raisonnable.

Ce sont ces stratégies qui sont utilisées dans l'apprentissage des réseaux de neurones (deep learning).

Nous n'avons pas abordé dans ce chapitre les approches distribuées pour gérer la large échelle. Ces approches consistent à paralléliser massivement les calculs sur plusieurs machines. Vous pouvez consulter le cours  "Réalisez des calculs distribués sur des données massives" pour en savoir plus.

Vous êtes arrivés à la fin de ce cours, félicitations ! À présent, vous avez toutes les clés en main pour :

  • décrire la démarche et la méthodologie de l'apprentissage statistique ;

  • mettre en place un modèle d'apprentissage statistique adapté à son besoin ;

  • mettre en œuvre des modèles d'apprentissage statistiques.

N'oubliez pas de réaliser les exercices à la fin de chaque partie pour valider ces compétences. Ensuite, vous pouvez poursuivre votre apprentissage avec le cours "Initiez-vous au Deep Learning". Nous vous souhaitons une bonne continuation dans tous vos projets !

Exemple de certificat de réussite
Exemple de certificat de réussite