Fondations théoriques Protocoles Gossip

Apprentissage statistique et optimisation

Une large majorité de problèmes d’apprentissage statistique se présente sous la forme d’une fonction d’erreur à minimiser ou une fonction de vraisemblance à maximiser, qui qualifient la fidélité d’un modèle vis-à-vis d’un phénomène d’intérêt supposé inconnu. Ce phénomène est représenté par une variable aléatoire X, dont on ne possède qu’un ensemble fini de n réalisations (ou observations) {xi} n i=1. L’objectif consiste généralement à trouver le modèle θ ? qui minimise l’espérance de la fonction de coût sur toutes les réalisations possibles de X, parmi une famille de modèles indexée par un ensemble de paramètres θ : θ ? def = arg min θ EX[J(X, θ)] (1.1) Dans le cas où l’objectif est de maximiser une vraisemblance L, il suffit de considérer J(X, θ) = −L(X|θ) pour obtenir un problème de minimisation et retomber sur (1.1). En guise d’illustration, le problème de régression consiste à estimer une fonction f inconnue liant deux variables X et Y (i.e., Y = f(X)), étant donné un ensemble d’échantillons (xi , yi) n i=1. Dans ce cadre, la régression au sens des moindres carrés (Least Squares, LS) utilise comme fonction de coût l’erreur quadratique entre la valeur prédite par un certain modèle ˆfθ(X) et la valeur réelle f(X) = Y : J(X, θ) def = h ˆfθ(X) − f(X) i2 (1.2) Par exemple, la régression linéaire considère les modèles du type ˆfθ(x) = θ >x où x et θ sont des vecteurs de R D. L’objectif (1.1) peut alors réécrit comme θ ? def = arg min θ∈RD Ex  f(x) − θ >x 2 (1.3) Puisqu’en pratique on ne dispose que d’un ensemble fini d’échantillons (xi , yi) n i=1, on estime θ ? en remplaçant l’espérance inconnue dans (1.3) par la moyenne empirique de la fonction d’erreur sur le jeu d’échantillons, appelée risque empirique [241]) : θ ? def = arg min θ∈RD 1 n Xn i=1  yi − θ >xi 2 (1.4) D’après la loi des grands nombres, si les échantillons sont effectivement issus d’un même processus (i.e., sont identiquement distribués), plus le nombre d’échantillons n est grand plus l’approximation (1.6) se rapproche du véritable optimum (1.3) : lim n→+∞ P  1 n Xn i=1  yi − ˆfθ(xi) 2 = Ex  f(x) − ˆfθ(x)   = 1 (1.5) En l’occurrence, la régression linéaire au sens des moindres carrés trouve une solution analytique (i.e., directement calculable par une formule explicite) [178]. En notant X = [x1, . . . , xn] > et y = (y1, . . . , yn) >, on a en effet θ ? = arg min θ y − Xθ 2 2 = (X>X) −1X>y (1.6)  Dans ce cas spécifique, il suffit donc de calculer l’inverse, lorsqu’elle existe, de X>X (appelée matrice de Gram). Toutefois, un grand nombre de problèmes d’apprentissage statistique n’ont pas de solution analytique en forme close telle que (1.6). C’est de manière générale le cas des problèmes nonlinéaires qui peuvent avoir de multiples optimums locaux sans offrir de formule explicite pour l’optimum global. Pour ces familles de problèmes, on doit recourir à des méthodes d’optimisation itératives. Une approche itérative typique consiste à mettre à jour les paramètres θ pas à pas en approximant J au voisinage de θ (e.g., via son développement de Taylor) de sorte à ce que la résolution du problème approximé à chaque pas soit « facile ». Autrement dit, à partir de paramètres courants θ(t), on cherche de nouveaux paramètres θ(t + 1) calculables par une expression analytique et tels que J(θ(t + 1)) ≤ J(θ). La convergence vers un minimum de J est alors garantie (mais celui-ci peut n’être qu’un minimum local pour un problème non-convexe). 

Optimisation distribuée

Lorsque le nombre d’échantillons n et leur dimension D restent raisonnables (quelques milliers), la plupart des problèmes d’optimisation peuvent être résolus efficacement par des algorithmes séquentiels qui ne manipulent qu’un échantillon à la fois et supposent que tous les échantillons sont accessibles depuis une mémoire centrale unique. Or, pour les raisons à la fois subies et désirées évoquées en introduction de cette thèse, les méthodes d’apprentissage statistique sont amenées à considérer des ensembles d’entraînement de très grande taille et de très grande dimension, entraînant trois conséquences : • L’ensemble d’entraînement ne peut plus être stocké dans une unique mémoire centrale, mais doit être réparti sur plusieurs sites de stockage. • Le nombre d’opérations à réaliser pour obtenir le résultat augmentant avec n et D, le temps de calcul explose. • La taille des données intermédiaires nécessaires aux calculs, éventuellement liées à n et/ou D, dépassent la capacité mémoire d’une machine seule. Ces limitations ont conduit à la formulation d’algorithmes distribués pour la résolution de problèmes d’optimisation large échelle. Ces algorithmes font généralement l’hypothèse que les données sont dispersées sur un ensemble de nœuds de stockage, et que l’on dispose de multiples nœuds de calcul, chaque noeud de calcul étant couplé à une ou plusieurs unités de stockage et pouvant au besoin échanger des données avec certains nœuds voisins par le biais d’un protocole de communication. Cette configuration, spécifiée indépendamment de l’algorithme lui-même, correspond donc à la définition d’un réseau de N noeuds connectées selon un certain graphe orienté G. Chaque noeud est doté de capacités de calcul et d’une mémoire locales et héberge un sous-ensemble Xi , 1 ≤ i ≤ N des données d’entraînement X. On suppose de plus que S i Xi = X et que ∀i, j, Xi ∩ Xj = ∅, c’est à dire que {Xi} N i=1 est une partition de X. Un algorithme distribué doit alors garantir l’obtention du résultat quels que soient le graphe G et l’allocation des données {Xi}. On cherche en effet à ce que l’influence du réseau soit la plus transparente possible. 

Modèle de temps

Formellement, un processus de calcul distribué est un système dynamique et doit être analysé en tant que tel. La définition du modèle de temps dans lequel ce système dynamique évolue est une hypothèse importante mais souvent implicite. Modèle de temps globalement synchrone De nombreuses méthodes de calcul distribué supposent qu’à chaque pas de temps t ∈ N, chaque noeud effectue une certaine opération. Cette hypothèse induit de fait une synchronisation globale, dont la mise en œuvre pratique requiert (i) une horloge commune à tous les nœuds qui, à chaque pas de temps, déclenche une opération et une seule en chaque noeud, (ii) que l’instant t + 1 ne survient que lorsque toutes les opérations au temps t sont terminées. Une conséquence directe est que les opérations en tout noeud s’effectuent aussi lentement que le noeud le plus lent. Plus grave, si une communication entre nœuds est nécessaire à un instant donné, les nœuds non impliqués dans cette opérations doivent attendre que les données soient transmises avant de procéder à leur propres calculs et/ou échanges. Une méthode distribuée s’appuyant sur un modèle de temps globalement synchrone est donc fondamentalement sous-efficiente. La principale justification de ce type d’approches synchrones réside dans la facilitation des preuves théoriques de convergence et l’analyse asymptotique, qui peut alors s’appuyer sur un formalisme purement itératif où l’évolution du système est globalement maîtrisée à chaque étape. Modèle de temps partiellement asynchrone Au contraire, un système distribué privé d’horloge globale est intrinsèquement asynchrone. Chaque noeud est guidé par sa propre horloge qui peut fonctionner à une fréquence très différente selon le nœud considéré. Dans un modèle de temps asynchrone, on considère un temps réel t ∈ R fondamentalement continu, au sein duquel surviennent des événements de « tics » d’horloges épars. Une approche classique est de modéliser ces horloges entières comme des processus stochastique de comptage ponctuels [39]. Formellement, les horloges sont définies comme des processus de Poisson superposés et indépendants. Dans le cas où les fréquences d’horloge des nœuds sont identiques, disons égales à λ, le processus global d’activation des horloges à travers le réseau est lui-même un processus de Poisson de taux Nλ. Il est alors commode de supposer que l’état d’un noeud évolue instantanément au moment où son horloge s’active. On peut ainsi assimiler indifféremment t au temps réel (t ∈ R) ou au processus de comptage global (t ∈ N) sans perte de généralité. En réalité, une opération ne s’effectue jamais instantanément. De plus, un noeud ne peut exécuter plusieurs opérations simultanément, en tant qu’unité de calcul séquentielle. L’éventualité qu’un noeud soit « occupé » ne doit donc pas être ignoré dans l’analyse. Ainsi, les horloges locales ne peuvent pas être rigoureusement modélisées par des processus de Poisson indépendants (qui associent une probabilité non-nulle à tout intervalle non-nul). Lorsqu’un noeud envoie un message à un noeud occupé, il nous faut donc expliciter le comportement du couple émetteurrécepteur.