Fiche de révision : Calcul distribué et MapReduce avancé

📋 Plan du Cours

1. Calcul en nuage et MapReduce
2. Agrégation locale et correction
3. Paires, bandes et index inversé
4. Compression des postings
5. Algorithmes sur graphes
6. PageRank distribué
7. Algorithmes EM
8. Modèles de Markov cachés
9. Alignement de mots et langue
10. CRF et optimisation

📖 1. Calcul en nuage et MapReduce

🔑 Notions clés & Définitions

• MapReduce : Modèle de programmation et cadre d’exécution pour effectuer des calculs distribués sur de très grandes quantités de données, sur des grappes de serveurs banalisés.
• Calcul en nuage : Approche de calcul où l’infrastructure de serveurs est fournie comme service, et où des données et traitements sont gérés à distance par des centres de données.
• Utility computing : Principe consistant à facturer les ressources de calcul de façon mesurée, comme un service à la demande, avec élasticité via la mise à disposition de ressources virtuelles.
• Échelle out : Stratégie consistant à augmenter la puissance d’un traitement en ajoutant de nombreux serveurs peu coûteux plutôt qu’en renforçant fortement quelques machines.

📝 Points essentiels

• MapReduce a été initialement développé par Google et s’est largement diffusé via l’implémentation open source Hadoop, dont le développement a été mené par Yahoo puis intégré à l’Apache project.
• Le besoin de calcul massif vient notamment du fait que les données et la capacité de stockage progressent plus vite que la capacité à les traiter et même à les relire, rendant le traitement à grande échelle nécessaire.
• Dans le calcul en nuage, l’élasticité permet d’ajouter ou retirer des ressources de calcul selon la demande, en limitant les investissements initiaux et les coûts en cas de pics imprévus.
• Pour les charges data-intensive, l’approche recommandée est l’« échelle out » sur beaucoup de serveurs bas de gamme, car le coût n’augmente pas de façon favorable comme avec l’« échelle up » sur quelques machines très puissantes.
• MapReduce vise aussi l’accès aux données sans déplacer inutilement les volumes : en pratique, on privilégie une co-localisation code-données et un traitement séquentiel pour éviter les coûts des accès aléatoires disque.
• En architecture distribuée, des pannes sont considérées comme normales : un service bien conçu doit continuer à fonctionner en réaffectant la charge et en redémarrant des tâches sur d’autres nœuds.

💡 Astuce mémo

Out = « plus de machines » plutôt que « plus grosse machine » : données énormes → grappes low-cost → MapReduce.

📖 2. Agrégation locale et correction

🔑 Notions clés & Définitions

• Agrégation locale : L’agrégation locale regroupe des résultats partiels au plus près des données traitées pour réduire la taille et le nombre des paires intermédiaires envoyées sur le réseau.
• Combiner : Un combiner est un “mini-réducteur” exécuté sur la sortie des mappers avant le shuffle, servant à fusionner localement des valeurs partageant la même clé.
• In-mapper combining : L’in-mapper combining exécute l’agrégation dans le mapper lui-même en accumulant un état interne puis en émettant une sortie seulement à la fin du traitement de la tâche.
• Correction sémantique : La correction avec agrégation locale garantit que l’optimisation modifie uniquement l’efficacité, pas le résultat final attendu par la logique du reducer.

📝 Points essentiels

• Les combiners sont des optimisations optionnelles : la correction de l’algorithme ne peut pas dépendre du fait qu’ils s’exécutent (ils peuvent être appelés 0 fois, 1 fois ou plusieurs fois).
• Dans Hadoop, le type des paires clé-valeur du combiner doit correspondre au type produit par le mapper et consommé par le reducer, car le combiner reçoit et émet le même type de clés et de valeurs que le mapper.
• Si l’opération du reducer est commutative et associative, le reducer peut être réutilisé tel quel comme combiner, comme pour l’addition dans un word count.
• Si l’on applique un combiner qui n’est pas sémantiquement équivalent (exemple du calcul de la moyenne arrondie), on agrège des sous-ensembles arbitraires et on change le résultat final.
• L’in-mapper combining dépend de l’ordre d’itération des paires d’entrée puisque l’état interne est mis à jour au fil des appels, ce qui peut introduire des bugs difficiles à reproduire.
• L’in-mapper combining peut être limité par la mémoire car il faut conserver l’état jusqu’à la fin du split ; on peut alors “flusher” par blocs (toutes les n paires) ou par seuil de mémoire, fixé empiriquement.

💡 Astuce mémo

Combiner = avant le réseau ; In-mapper = avant le shuffle : si l’agrégation n’est pas associative/commutative, la correction casse.

📖 3. Paires, bandes et index inversé

🔑 Notions clés & Définitions

• Approche pairs : Approche MapReduce où l’on émet pour chaque événement cooccurrent une clé correspondant au couple (w,wʹ) et une valeur de comptage, puis le réducteur somme par clé.
• Approche stripes : Approche MapReduce où l’on émet pour chaque mot w une clé w et une valeur associative qui regroupe, pour ses voisins, les comptes de coocurrence.
• Inversion d’ordre : Technique qui force l’ordre de traitement des clés au réducteur pour obtenir d’abord un marginal, puis diviser les comptes joints par ce marginal.
• Index inversé : Structure de recherche qui associe chaque terme à une liste (postings) des documents où il apparaît, souvent compressée à l’aide de paramètres ajustés par l’inversion d’ordre.

📝 Points essentiels

• Avec pairs, le nombre de clés intermédiaires explose car chaque mot de gauche est répété pour chaque cooccurrent, tandis que stripes garde une seule clé par mot de gauche et encapsule les voisins dans une associative array.
• Dans l’étude APW (5,7 Go, fenêtre de cooccurrence 2), stripes est bien plus rapide que pairs : 666 s (~11 min) contre 3758 s (~62 min), soit un facteur ~5,7.
• Toujours sur APW, pairs génère 2,6 milliards de couples intermédiaires (31,2 Go) avant combiners, puis 1,1 milliard ; stripes génère 653 millions intermédiaires (48,1 Go) avant combiners, puis 28,8 millions.
• Le bon usage de stripes suppose que chaque associative array puisse tenir en mémoire, ce qui devient problématique à mesure que la taille du vocabulaire croît (loi de Heap).
• Pour calculer des fréquences relatives f(wʲ|wᵢ), l’approche pairs peut s’appuyer sur une inversion d’ordre : émission d’une clé spéciale (wᵢ, ∗) pour le marginal, puis traitement trié pour diviser les joints par ce marginal.
• L’inversion d’ordre sert aussi à la construction d’un index inversé, afin de régler correctement des paramètres de compression des postings.

💡 Astuce mémo

Pairs = clé par couple (w,wʹ) ; Stripes = clé par mot (w) + un tableau de voisins ; Index inversé = postings par terme, et l’inversion d’ordre aide à fixer la compression grâce au marginal d’abord.

📖 4. Compression des postings

🔑 Notions clés & Définitions

• d-gaps : Les d-gaps sont des différences entre identifiants de documents consécutifs dans une liste de postings, encodées à la place des identifiants eux-mêmes.
• varInt : Le codage varInt compresse des entiers en utilisant un bit de continuation et un nombre variable d’octets, jusqu’à la fin du mot codé.
• group varInt : Le group varInt code des paquets de 4 entiers avec un octet préfixe indiquant, via des longueurs, le nombre d’octets utilisés pour chacun.
• Simple-9 : Simple-9 est un codage par mots où un sélecteur de 4 bits indique comment répartir 28 bits restants pour stocker plusieurs entiers.
• codes à préfixe : Les codes à préfixe (prefix-free) sont des codages bit-alignés où aucun mot valide n’est le préfixe d’un autre, rendant le découpage sans ambiguïté.

📝 Points essentiels

• Un encodage naïf docid sur 32 bits et tf sur 16 bits coûte 6 octets par posting, soit une taille proche de la collection.
• Comme les postings sont triés, on encode des d-gaps positifs (sauf le premier, encodé tel quel) pour rendre les valeurs plus petites et donc plus faciles à coder.
• Avec varInt, 0 ≤ n < 2^7 tient sur 1 octet, 2^7 ≤ n < 2^14 sur 2 octets, 2^14 ≤ n < 2^21 sur 3 octets et 2^21 ≤ n < 2^28 sur 4 octets.
• Les codes byte-alignés sont décodés vite mais gaspillent des bits car ils consomment des multiples de 8, tandis que les codes bit-alignés évitent ce gaspillage au prix d’un découpage plus complexe.
• En group varInt, chaque groupe de 4 entiers consomme entre 5 et 17 octets car l’octet préfixe encode, en 2 bits par entier, la taille (en octets) attendue.
• Simple-9 utilise 4 bits de sélecteur et 28 bits de données dans un mot de 32 bits, et le sélecteur indique comment compacter plusieurs entiers (jusqu’à 9 répartitions possibles).

📖 5. Algorithmes sur graphes

🔑 Notions clés & Définitions

• Matrice d’adjacence : Représentation d’un graphe en une matrice $n\times n$ où une case indique l’existence (ou le poids) de l’arête entre deux sommets.
• Listes d’adjacence : Représentation d’un graphe en associant à chaque sommet la liste de ses voisins accessibles via ses arêtes sortantes.
• Recherche en largeur parallèle : Algorithme de plus courts chemins en distances par passes itératives MapReduce, où chaque itération étend la frontière de recherche d’un cran.
• Frontière de recherche : En largeur parallèle, ensemble des sommets nouvellement atteints dont les distances servent à découvrir les voisins lors de l’itération suivante.

📝 Points essentiels

• Les graphes traités sont surtout supposés épars, donc les listes d’adjacence évitent le coût mémoire $O(n^2)$ d’une matrice d’adjacence.
• Dans la largeur parallèle unitaire, chaque itération correspond à un saut : les voisins à distance $d$ reçoivent une distance $d+1$.
• À chaque itération, le graphe doit être “passé” au reducer en réémettant la structure du sommet avec sa clé, puis en mettant à jour la distance minimale avant de réémettre la version mise à jour.
• Avec des arêtes de poids unité, le nombre d’itérations nécessaires est lié au diamètre du graphe (la plus grande distance entre deux sommets).
• Avec des distances arbitraires, l’arrêt se fait quand les distances de tous les sommets ne changent plus ; le cas le plus défavorable peut nécessiter jusqu’à $|V|-1$ itérations.
• Pour initialiser l’algorithme, on fixe la distance du sommet source à $0$ et toutes les autres à $\infty$, puis un “driver” MapReduce utilise des counters pour décider de poursuivre ou non.

💡 Astuce mémo

Frontière = vague : 1 itération = 1 saut (d→d+1), jusqu’au diamètre, puis arrêt quand plus aucune distance ne bouge.

📖 6. PageRank distribué

🔑 Notions clés & Définitions

• PageRank : Le PageRank est une distribution de probabilité sur les nœuds d’un graphe qui mesure la fréquence d’une marche aléatoire sur le graphe, à partir des liens entrants et sortants.
• Facteur de saut α : Le facteur α pondère la probabilité de “téléportation” lors de la marche aléatoire, ajoutant une contribution uniforme indépendamment des liens.
• Nœud pendant : Un nœud pendant est un nœud dont la liste de sorties est vide, ce qui fait perdre de la masse de probabilité si on exécute l’itération sans correction.
• Masse manquante : La masse manquante est la somme de PageRank perdue aux nœuds pendants, puis redistribuée uniformément à tous les nœuds à chaque itération.

📝 Points essentiels

• La contribution d’un nœud $m$ à un nœud $n$ vaut $P(m)/C(m)$, où $C(m)$ est le degré sortant, et le PageRank combine aussi une téléportation uniforme $/|G|$ pondérée par $α$.
• Dans la version simplifiée sans pendants ni téléportation, une itération MapReduce mappe chaque nœud en répartissant uniformément sa masse sur ses voisins puis réduit en sommant les contributions entrantes.
• Pour traiter les nœuds pendants, on calcule la masse perdue $m$ (par compteur ou via une clé spéciale) puis on met à jour chaque nœud avec $p' = α(1/|G|) + (1-α)((m/|G|)+p)$.
• Une itération complète de PageRank requiert deux jobs MapReduce : un pour propager la masse via les arêtes, puis un pour corriger pendants et téléportation (ce deuxième job n’a pas besoin de reducers).
• Le driver exécute des itérations jusqu’à convergence, par exemple quand les valeurs n’évoluent plus (ou dans une tolérance liée aux flottants), ou jusqu’à stabilité des rangs.
• Dans l’étude originale, une convergence a été observée en 52 itérations sur un graphe avec 322 millions d’arêtes, avant prise en compte de modifications dues au spam et au link gaming.

💡 Astuce mémo

Idée clé : PageRank = “masse” qui se répartit sur les liens sortants, et les pendants “injectent” toute leur masse uniformément via $m/|G|$.

📖 7. Algorithmes EM

🔑 Notions clés & Définitions

• Estimation du maximum de vraisemblance : Critère d’estimation qui choisit les paramètres qui rendent la donnée d’entraînement la plus probable sous le modèle.
• Variable latente : Variable dont les valeurs ne sont pas observées directement, mais qui influence la génération des observations observées.
• Vraisemblance marginale : Quantité obtenue en sommant, dans le modèle, la probabilité conjointe sur toutes les valeurs possibles de la variable latente.
• Expectation Maximization : Algorithme itératif qui améliore la vraisemblance marginale quand des variables latentes sont manquantes.
• E-step et M-step : Étapes successives d’EM : calculer une distribution a posteriori en E puis maximiser un critère d’espérance en M.

📝 Points essentiels

• MLE choisit $\theta^* = \arg\max_\theta \Pr(X=x;\theta)$ en maximisant la probabilité d’observer la donnée d’entraînement sous le modèle.
• Avec variable latente $Y$, la vraisemblance marginale devient $\Pr(X=x)=\sum_{y\in Y}\Pr(X=x,Y=y;\theta)$, donc on maximise ce terme sur $\theta$.
• EM garantit, à chaque itération, que la vraisemblance marginale $|x|\prod_j\sum_{y\in Y}\Pr(X=x_j,Y=y;\theta^{(i+1)})$ est au moins aussi grande que pour $\theta^{(i)}$.
• E-step calcule la distribution a posteriori $q(X=x,Y=y;\theta^{(i)})$ à partir de $\Pr(Y=y\mid X=x;\theta^{(i)})$ et de la fréquence d’occurrence de $x$.
• M-step met à jour $\theta^{(i+1)}$ en maximisant l’espérance de $\log \Pr(X=x,Y=y;\theta')$ pondérée par $q$ calculée à l’étape E.
• EM s’arrête quand la vraisemblance ne change plus, mais la solution obtenue est en général un maximum local uniquement.

💡 Astuce mémo

EM = E-step calcule le posterior (qui est probable pour $Y$), puis M-step maximise l’espérance du log (qui fixe $\theta$).

📖 8. Modèles de Markov cachés

🔑 Notions clés & Définitions

• Algorithme EM : Un algorithme EM est une méthode itérative qui améliore la vraisemblance marginale quand certaines variables du modèle ne sont pas observées.
• Modèle de Markov caché : Un modèle de Markov caché est un modèle séquentiel où des états cachés suivent une dynamique de Markov et émettent des observations selon des lois conditionnelles.
• Probabilité forward : La probabilité forward $t(q)$ est la masse de probabilité dune observation partielle jusqu au temps t en étant dans létat q.
• Algorithme de Viterbi : Lalgorithme de Viterbi calcule la séquence détats la plus probable à partir dune suite dobservations, via une dynamique avec pointeurs de retour.

📝 Points essentiels

• Un HMM définit $M=\langle S,O,\theta\rangle$ avec $\theta=\langle A,B,\pi\rangle$, où $A$ donne les transitions, $B$ les émissions et $\pi$ l état initial.
• La vraisemblance d une séquence d observations se calcule en sommant sur toutes les séquences d états, ce qui est évité en utilisant l algorithme forward.
• La récurrence forward est $\alpha_t(r)=B_r(x_t)\cdot \sum_{q\in S}\alpha_{t-1}(q)\cdot A_q(r)$, et $\Pr(x;\theta)=\sum_{q\in S}\alpha_{|x|}(q)$.
• La Viterbi remplace les sommes par des maxima et stocke un pointeur arrière $bp_t(r)$ pour reconstruire la meilleure suite d états.
• Dans l EM, la E-step calcule la distribution postérieure $q(X=x,Y=y;\theta^{(i)})$ sur les variables latentes et la M-step choisit $\theta^{(i+1)}$ via l espérance du log de la vraisemblance conjointe.
• Pour entraîner un HMM, les mises à jour utilisent des comptes attendus via des probabilités postérieures de transitions $\Pr(y_i=q,y_{i+1}=r\mid x;\theta)$ et d émissions $\Pr(y_i=q\mid x;\theta)$ calculées avec forward-backward.

💡 Astuce mémo

EM = E-step calcule les attentes (postérieurs), M-step maximise en utilisant ces attentes; pour HMM, forward donne la probabilité partielle et Viterbi donne le chemin le plus probable.

📖 9. Alignement de mots et langue

🔑 Notions clés & Définitions

• Variable d’alignement : La variable d’alignement désigne, pour chaque mot cible, l’indice du mot source qui l’a généré.
• Alignement HMM : L’alignement HMM modélise la traduction mot à mot avec une dépendance d’ordre via une transition entre positions consécutives de l’alignement.
• Modèle IBM 1 : Le modèle IBM 1 simplifie l’alignement en supposant que tous les alignements sont uniformément probables et ne dépend pas de la séquence des positions.

📝 Points essentiels

• Le modèle d’alignement HMM impose que Pr(e,a|f)=∏{i=1}^{|e|}Pr(a_i|a{i-1})·∏{i=1}^{|e|}Pr(e_i|f{a_i}], où le premier facteur est la transition sur les positions et le second la génération lexicale.
• Sous les hypothèses d’indépendance, l’alignement et la traduction sont appris avec EM en traitant a comme une variable latente, puis l’alignement le plus probable se déduit par Viterbi.
• Pour initialiser l’HMM d’alignement, le modèle IBM 1 fixe une probabilité uniforme sur les alignements, ce qui rend EM convexe partout et évite la dépendance aux paramètres initiaux.
• Dans IBM 1, on obtient des estimations attendues des comptes d’émission en temps $O(|e|\cdot|f|)$ plutôt que via forward-backward qui exigerait $O(|e|\cdot|f|^2)$, grâce à l’uniformité des alignements.

💡 Astuce mémo

HMM = transitions de positions (a_i|a_{i-1}) ; IBM1 = uniformité de a, donc EM devient insensible à l’initialisation.

📖 10. CRF et optimisation

🔑 Notions clés & Définitions

• Champ aléatoire conditionnel : Un modèle probabiliste conditionnel qui associe une distribution de sortie aux entrées, en modélisant la structure de séquence via une énergie exponentielle.
• Modèle log-linéaire : Un modèle où la probabilité prend une forme exponentielle avec des paramètres $theta_i$ pondérant des fonctions de traits $H_i(x,y)$.
• Vraisemblance conditionnelle : Un objectif d’apprentissage qui maximise la probabilité de l’étiquette $y$ étant donné l’entrée $x$.
• Optimisation par gradient : Une famille de méthodes itératives qui ajuste les paramètres en suivant des gradients d’une fonction objectif différentiable.

📝 Points essentiels

• Le CRF s’entraîne en maximisant une vraisemblance conditionnelle, ce qui revient à minimiser une perte négative de log de $Pr(y|x;\theta)$.
• Le gradient de la perte pour un modèle log-linéaire s’écrit comme une différence entre une valeur de trait $H_i(x,y)$ et son espérance sous $Pr(y'|x;\theta)$.
• Dans des modèles de séquences avec la même hypothèse de Markov que les HMM, on peut réutiliser l’algorithme forward-backward pour calculer les espérances nécessaires au gradient du CRF.
• La forme exponentielle des CRF rend leur optimisation compatible avec des techniques d’optimisation par gradient, dont les itérations peuvent être parallélisées en MapReduce quand l’objectif se décompose sur les instances d’entraînement.
• En MapReduce pour l’optimisation par gradient, les mappers émettent des composantes $\langle F(\theta),\nabla F(\theta)\rangle$ et les reducers additionnent puis exécutent l’étape d’actualisation des paramètres.
• Si le calcul des espérances implique l’énumération de toutes les sorties possibles, il devient coûteux et l’hypothèse structurelle (Markov) est précisément utilisée pour rendre le calcul tractable.

💡 Astuce mémo

CRF = log-linéaire + espérances: gradient = (trait observé) − (trait espéré), et forward-backward sert à calculer l’espérance en séquence.

📅 Repères chronologiques

1. April 11, 2010Manuscript prepared date
2. 2004Google processes 100 TB of data a day with MapReduce
3. 2008Google processes 20 PB of data a day with MapReduce
4. April 2009Blog post about eBay’s two petabyte data warehouses

📊 Tableaux de synthèse

Pairs vs stripes (word co-occurrence)

⚠️ Pièges & confusions fréquents

1. Penser que le combiner change le résultat : en Hadoop il est optionnel (0,1,ou plusieurs exécutions), donc la correction ne doit pas en dépendre.
2. Réutiliser un reducer comme combiner même si l’opération n’est pas commutative/associative (exemple typique : moyenne arrondie).
3. Utiliser l’in-mapper combining sans comprendre qu’il dépend de l’ordre d’itération (bug d’ordre d’entrée) et peut casser la correction si l’agrégat n’est pas compatible.
4. Confondre pairs et stripes pour les fréquences relatives : sans inversion d’ordre (clé spéciale (w,∗)+tri), on ne connaît pas le marginal au bon moment.
5. Oublier que Hadoop ne fournit pas l’ordre sur les valeurs : pour trier par (clé puis valeur), il faut “value-to-key conversion” et un partitioner sur la partie clé voulue.
6. Compresser des postings en encodant docid brut en 32 bits : tu perds le gain principal (d-gaps + encodage plus efficace sur les petits écarts).
7. Croire que PageRank s’arrête dès que les contributions entrantes “semblent” stables : en pratique l’arrêt doit suivre une condition de convergence/variation de PageRank (ou un nombre fixe d’itérations) contrôlée par le driver.

✅ Checklist Examen

1. Définir MapReduce et le rôle de mappers/reducers, puis expliquer le shuffle-and-sort et pourquoi le reducer reçoit toutes les valeurs d’une même clé.
2. Expliquer la différence sémantique : combiner optionnel (types clé/valeur identiques mapper→combiner→reducer) vs in-mapper combining (état interne, dépendance à l’ordre d’entrée, contraintes mémoire).
3. Justifier quand reducer peut servir de combiner (opération commutative et associative) et donner un exemple où cela casse (moyenne).
4. Décrire les patterns “pairs” et “stripes” pour cooccurrence, et relier leur impact à la taille des clés intermédiaires et aux opportunités de combiners.
5. Construire les fréquences relatives f(wʲ|wᵢ) via inversion d’ordre : clé spéciale (wᵢ,∗), tri garantissant le traitement du marginal avant les joints, et partitioner sur le mot de gauche.
6. Expliquer la différence entre tri par clé (naturel) et tri secondaire : résoudre le problème via value-to-key conversion (clé composite (idGroupe, valeur) + partitioner).
7. Coder efficacement des postings : expliquer d-gaps, varInt/group varInt/Simple-9 et l’idée des codes à préfixe (bit-aligned) pour lever l’ambiguïté de décodage.
8. Pour l’index inversé MapReduce : donner le baseline (buffer postings + sort en mémoire) et la version révisée (value-to-key avec partitioner sur le terme).
9. Décrire parallel BFS : itératif (frontière), passage de la structure du graphe entre jobs, arrêt via compteur/découverte de distances (diamètre en cas d’arêtes unitaires).
10. Décrire PageRank distribué : propagation de masse via liens sortants, traitement des nœuds pendants (masse manquante redistribuée), et mise à jour avec α (téléportation), en 2 jobs par itération.
11. Décrire EM : E-step (postérieur sur variable latente) puis M-step (max de l’espérance du log), garantie de non-diminution de la vraisemblance marginale et maximum local.
12. Décrire HMM : rôle des paramètres (A,B,π), forward et Viterbi, puis l’apprentissage via forward-backward (comptes attendus) ; enfin alignement IBM 1 (uniformité) et généralisation HMM alignement.