Appliquez l’apprentissage statistique aux objets connectés

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.

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  {xi∈Rd}ni=1 en des points  {ti∈Rp}ni=1 de dimension p<d en utilisant la matrice de projection  U=[u1⋯up] . Les colonnes  uk de U sont les vecteurs propres de la matrice de covariance

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

• Ressources mémoire :  O(d2) pour stocker la matrice C ,

• Complexité en temps : le calcul de C requiert O(nd2) opérations et celui de U  nécessite O(pd2) opérations.

K-Means

Cette méthode itérative de catégorisation des données  {xi∈Rd}ni=1 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 : 

   O(n×d) pour les données augmenté de O(K×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 : O(n×d×K) et (ii) mise à jour des centres : O(n×d) 

La complexité calculatoire globale est de l'ordre de O(n×d×K×T) où T est le nombre total d'itérations.

Régression linéaire

Elle consiste à apprendre le modèle linéaire f(x)=x⊤β à partir de données {(xi,yi)∈Rd×R}ni=1 . Les  paramètres  β sont estimés par minimisation du critère des moindres carrés 1n∑ni=1(yi−x⊤iβ)2. Nous avons établi que la solution est

où X∈Rn×d et Y∈Rn sont respectivement la matrice des entrées et le vecteur de sortie. Cela engendre :

• une compléxité mémoire de O(d2) pour stocker la matrice X⊤X et O(d) pour le vecteur X⊤Y ;

•  O(n×d2) opérations pour le calcul de X⊤X et O(n×d) opérations pour calculer X⊤Y. Le calcul de  ˆβ coûte O(d3) 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  {(xi,yi)∈Rd×{0,1}}ni=1 ,  les paramètres du modèle de régression logistique linéaire f(x)=x⊤β se déterminent par résolution du problème

minβJ(β)=∑ni=1[−yix⊤iβ+log(1+expx⊤iβ)]

Nous avons vu qu'on pouvait utiliser la méthode de descente de gradient pour calculer itérativement les paramètres βt=βt−1−αt∇J(βt−1)avec∇J(βt−1)=∑ni=1(yi−expx⊤iβt−11+expx⊤iβt−1)xi(2) Le calcul du gradient nécessite environ O(n×d) opérations ; nous déduisons, si on effectue T itérations, une complexité en temps de l'ordre de O(n×d×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 O(n3) et une complexité en mémoire de O(n2) pour stocker la matrice de noyau K∈Rn×n avec Kij=x⊤ixj .

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(x)=x⊤β . Leur problème d'optimisation peut s'écrire sous la forme générale  minβJ(β)=1n∑ni=1[ℓ(yi,f(xi))+λ‖β‖2](3)

avec λ>0 et la fonction de perte (voir figure 1) :

•  ℓ(yi,f(xi))=(yi−x⊤iβ)2 pour la régression linéaire

•   ℓ(yi,f(xi))=−yix⊤iβ+log(1+expx⊤iβ)  pour la régression logistique,

• ℓ(yi,f(xi))=max(0,1−yix⊤iβ) pour le SVM.

La premier terme de l'équation (3) mesure l'adéquation entre la prédiction f(xi) et la vraie sortie yi (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 βt

• A chaque itération t

  • tirez aléatoirement un point (xi,yi) , i∈{1,⋯,n} des données d'apprentissage ;

  • calculez le gradient partiel ˜gt=∇ℓ(yi,x⊤iβt−1)+λβt−1 ;

  • mettez à jour les paramètres par  βt=βt−1−αt˜gt avec αt le pas ;

  • (Optionnel) moyennez les estimées ˉβ=1t∑tk=1βk .

Chaque itération de la méthode du gradient (voir équation (2)) nécessite le calcul du gradient global g=∑ni=1˜gi , 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 ˜gt=∇ℓ(yi,x⊤iβt−1)+λβt−1 pour mettre à jour les paramètres.

La complexité par itération est donc :

• pour la méthode du gradient, O(n×d) opérations,

• pour la méthode du gradient stochastique, O(d) opérations.

Nous comparons, sur la figure 2, l'évolution des paramètres β 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.

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 ,  βt et les gradients partiels ˜gi,∀i=1,⋯,n 

  À chaque itération t

  • tirez aléatoirement un point (xi,yi) , i∈{1,⋯,n} des données d'apprentissage,

  • calculez at=∇ℓ(yi,x⊤iβt−1)+λβt−1

  • calculez une approximation du gradient

    gt=n∑j=1˜gj=gt−1−˜gi+at

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

  • mettez à jour les paramètres βt=βt−1−αtgt avec α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(βt)−J(β∗) 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.

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.

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 !