Comprendre le fonctionnement des transformeurs : les mathématiques cachées derrière

 (osanseviero.github.io)
5 points par GN⁺ 2024-01-04 | 1 commentaires | Partager sur WhatsApp
  • Le processus d’inférence d’un transformeur est réduit à un exemple de traduction Hello World → Hola Mundo, afin de pouvoir suivre à la main chaque étape, de la tokenisation au calcul des probabilités du token suivant via l’encodeur et le décodeur
  • Au lieu de la grande configuration de l’article original, l’exemple utilise des embeddings en 4 dimensions, 2 têtes d’attention et une couche feed-forward en 8 dimensions, pour rendre plus compact le flux des multiplications de matrices et du softmax
  • L’encodeur ajoute un encodage positionnel aux embeddings des tokens, puis construit une représentation contextuelle de la séquence d’entrée via une self-attention multi-têtes et une couche feed-forward
  • Le décodeur démarre avec SOS, utilise conjointement les tokens déjà générés et la sortie de l’encodeur, et dans l’attention encodeur-décodeur, les query viennent du décodeur tandis que les key/value sont calculés à partir de la sortie de l’encodeur
  • Le dernier embedding du décodeur devient une probabilité sur le token suivant après une couche linéaire et un softmax, mais l’exemple utilise des poids aléatoires, donc il ne faut pas s’attendre à une vraie qualité de traduction

Objectif et hypothèses

  • Vérifier, via un exemple de bout en bout, comment s’enchaînent les mathématiques de l’inférence à l’intérieur d’un modèle transformeur
  • La taille du modèle est fortement réduite pour que les calculs puissent être suivis à la main
    • Au lieu des 512 dimensions d’embedding de l’article original, l’exemple utilise 4 dimensions
    • Au lieu des 8 têtes d’attention de l’article original, l’exemple en utilise 2
    • Au lieu des 2048 dimensions du feed-forward de l’article original, l’exemple utilise 8 dimensions
  • Le prérequis principal est une base d’algèbre linéaire, et la plupart des calculs se font via des multiplications de matrices
  • L’accent est mis non pas sur ce qu’est un transformeur, mais sur la manière dont les calculs se déroulent réellement
  • Pour une explication intuitive, la lecture se marie bien avec The Illustrated Transformer, et l’article original est Attention is all you need

Construire l’entrée de l’encodeur

  • Tokenisation

    • Les modèles de machine learning traitent des nombres, pas directement du texte ; le texte d’entrée est donc converti en identifiants de tokens
    • Pour simplifier, l’exemple découpe "Hello World" en deux tokens mots : "Hello" et "World"
    • En pratique, la tokenisation peut être fondée sur les mots, les caractères ou les subwords
    • Une tokenisation au niveau des mots nécessite un grand vocabulary et traite "dog" et "dogs" comme deux tokens distincts
    • Une tokenisation au niveau des caractères demande un vocabulary plus petit, mais peut contenir moins d’information sémantique
    • La tokenisation subword se situe entre les deux ; le tokenizer est appris via un processus statistique

  • Embeddings de tokens

    • Un identifiant de token n’a pas de sens en soi, donc chaque token est converti en un embedding, c’est-à-dire un vecteur de taille fixe
    • L’exemple utilise des valeurs d’embedding arbitraires
      • Hello -> [1, 2, 3, 4]
      • World -> [2, 3, 4, 5]
    • Dans un vrai transformeur, la correspondance vers les embeddings est elle aussi apprise, afin que le modèle acquière des représentations adaptées à la tâche
    • Les deux embeddings sont regroupés dans une seule matrice pour les multiplications matricielles ultérieures

  • Encodage positionnel

    • Les embeddings seuls ne permettent pas de connaître la position des mots dans la phrase ; on leur ajoute donc un encodage positionnel
    • L’article original utilise un encodage positionnel fixe en sinus/cosinus, et l’exemple suit la même approche
    • Dans l’exemple, l’encodage positionnel est calculé comme suit
      • Hello -> [0, 1, 0, 1]
      • World -> [0.84, 0.99, 0, 1]
    • On additionne l’embedding du token et l’encodage positionnel pour construire la matrice d’entrée de l’encodeur
      • Hello -> [1, 3, 3, 5]
      • World -> [2.84, 3.99, 4, 6]

Calcul de la self-attention

  • Construction de Q, K, V

    • La self-attention calcule query (Q), key (K) et value (V) à partir des embeddings d’entrée
    • L’exemple utilise 2 têtes d’attention, chacune avec ses propres matrices WQ, WK, WV
    • Chaque matrice de poids transforme un embedding en 4 dimensions en query/key/value en 3 dimensions
    • Pour la première tête, on multiplie la matrice d’entrée par WK1, WV1 et WQ1 afin d’obtenir K1, V1 et Q1

  • Formule de l’attention

    • Les scores d’attention sont calculés en quatre étapes
      • calculer le produit scalaire entre la query et chaque key
      • diviser par la racine carrée de la dimension des key
      • transformer le résultat avec softmax en poids positifs dont la somme vaut 1
      • produire une somme pondérée des vecteurs value à l’aide de ces poids
    • Ce processus est condensé dans la formule de l’article original
    • [
    • Attention(Q,K,V) = \text{softmax}\left(\frac{QK^\top}{\sqrt{d}}\right)V
    • ]
    • Dans l’exemple, à cause de la petite dimension et des valeurs initiales arbitraires, le résultat du softmax est presque entièrement polarisé vers 0 et 1
    • De grands produits scalaires peuvent être fortement amplifiés par le softmax, d’où la nécessité du facteur d’échelle via la racine carrée de la dimension des key
    • Pour l’explication, une variante divisant temporairement par 30 au lieu de sqrt(3) est aussi utilisée, mais ce n’est pas une solution durable

  • Sortie de l’attention multi-têtes

    • Les résultats d’attention de chaque tête sont concaténés, puis multipliés par une matrice de poids apprise pour revenir à la dimension d’embedding
    • Dans l’exemple, les deux sorties de tête sont combinées en une matrice de dimension 6, puis transformées en une sortie de dimension 4
    • Cette sortie est transmise à l’étape suivante du bloc encodeur : la couche feed-forward

Couche feed-forward et bloc encodeur

  • Couche feed-forward

    • Après la self-attention vient un réseau feed-forward (FFN)
    • Le FFN se compose de deux transformations linéaires avec une activation ReLU entre les deux
    • La première couche linéaire augmente la dimension, et la seconde la ramène à sa taille d’origine
    • ReLU met les valeurs négatives à 0 et laisse les positives inchangées, ajoutant ainsi de la non-linéarité
    • Dans l’exemple, l’entrée en 4 dimensions est étendue à 8 dimensions puis ramenée à 4 dimensions
    • [
    • \text{FFN}(x) = \text{ReLU}(xW_1 + b_1)W_2 + b_2
    • ]

  • Bloc encodeur

    • Un bloc encodeur se compose d’une attention multi-têtes et d’un FFN
    • L’article original empile 6 encodeurs, et le code d’exemple répète lui aussi l’encodeur avec n=6
    • Si l’on traverse simplement plusieurs blocs encodeur, les valeurs peuvent devenir trop grandes, provoquer un overflow dans le calcul du softmax, puis produire des nan

Connexions résiduelles et normalisation de couche

  • Problème d’explosion des valeurs

    • Dans l’exemple, après passage dans 6 encodeurs, des avertissements overflow encountered in exp et invalid value encountered in divide apparaissent, et la sortie devient nan
    • Le fait que les valeurs deviennent trop grandes puis continuent à croître dans les couches suivantes est un problème courant dans les réseaux de neurones profonds
    • Quand les gradients deviennent trop grands pendant la backpropagation, on parle de gradient explosion

  • Connexion résiduelle

    • Une connexion résiduelle consiste à ajouter l’entrée d’une couche à sa sortie
    • [
    • \text{Residual}(x) = x + \text{Layer}(x)
    • ]
    • Dans l’exemple, une connexion résiduelle est appliquée à la sortie de l’attention puis à celle du FFN
    • Les connexions résiduelles servent à atténuer le problème de vanishing gradient

  • Layer normalization

    • La layer normalization normalise chaque dimension d’embedding pour obtenir une moyenne de 0 et un écart type de 1
    • La formule est la suivante
    • [
    • \text{LayerNorm}(x) = \frac{x - \mu}{\sqrt{\sigma^2 + \epsilon}} \times \gamma + \beta
    • ]
    • (\epsilon) est une petite valeur utilisée pour éviter une division par 0 lorsque l’écart type vaut 0
    • (\gamma) et (\beta) sont des paramètres appris qui contrôlent la mise à l’échelle et le décalage
    • Après ajout des connexions résiduelles et de la layer normalization, les 6 encodeurs produisent des valeurs normales sans nan

Structure du décodeur

  • Entrée du décodeur et mode de génération

    • Le décodeur prend en entrée la sortie de l’encodeur et la séquence de sortie générée jusqu’à présent
    • Pendant l’inférence, il commence par le token SOS (start-of-sequence)
    • Le décodeur génère les tokens de manière autorégressive, un par un
      • 1er tour : il reçoit SOS en entrée et génère "hola"
      • 2e tour : il reçoit SOS + hola en entrée et génère "mundo"
      • 3e tour : il reçoit SOS + hola + mundo en entrée et génère EOS
    • Le décodage s’arrête lorsqu’un token EOS (end-of-sequence) est généré
    • L’encodeur peut produire sa représentation en une seule forward pass, mais le décodeur doit en effectuer plusieurs, ce qui le rend plus lent

  • Composition du bloc décodeur

    • Le bloc décodeur est plus complexe que le bloc encodeur et suit l’ordre suivant
      • masked self-attention
      • connexion résiduelle et layer normalization
      • attention encodeur-décodeur
      • connexion résiduelle et layer normalization
      • couche feed-forward
      • connexion résiduelle et layer normalization
    • Dans l’exemple d’inférence, on ajoute l’encodage positionnel à l’embedding de SOS pour obtenir [1, 1, 0, 1]
    • Pendant l’entraînement, on utilise une masked self-attention qui masque les scores d’attention avec -inf pour empêcher de voir les tokens futurs

Attention encodeur-décodeur

  • L’attention encodeur-décodeur est l’étape qui permet au décodeur de se concentrer sur les parties pertinentes de la phrase d’entrée
  • Le calcul est identique à celui de la self-attention, mais les entrées servant à construire Q/K/V sont différentes
    • les query sont calculées à partir de la sortie de la couche précédente du décodeur
    • les key et value sont calculées à partir de la sortie de l’encodeur
  • Grâce à cette structure, chaque position du décodeur peut prendre en compte toutes les positions de la séquence d’entrée
  • C’est particulièrement utile pour des tâches comme la traduction, où les tokens de sortie doivent dépendre de positions pertinentes dans la phrase source

Génération du token de sortie

  • Couche linéaire et softmax

    • La sortie du décodeur n’est pas directement un mot ; le dernier embedding est donc passé dans une couche linéaire pour être transformé en vecteur de logits de taille égale au vocabulary
    • Dans l’exemple, la taille du vocabulary est 10, et les candidats pour le token suivant sont les suivants
      • hello, mundo, world, how, ?, EOS, SOS, a, hola, c
    • Les logits passent ensuite par un softmax pour produire une distribution de probabilité sur chaque token
    • Dans l’exemple, "hola" a la probabilité la plus élevée et est donc choisi comme token suivant
    • Choisir systématiquement le token à la probabilité la plus élevée correspond au greedy decoding, qui n’est pas toujours la meilleure stratégie
    • Les méthodes de génération sont détaillées plus en profondeur dans cet article de Hugging Face

  • Boucle complète de génération

    • La procédure complète suit le flux suivant
      • convertir la séquence d’entrée en embeddings
      • l’encodeur produit une représentation contextuelle de l’ensemble de l’entrée
      • le décodeur démarre avec SOS et utilise à la fois les tokens déjà générés et la sortie de l’encodeur
      • appliquer une couche linéaire puis un softmax au dernier embedding du décodeur
      • sélectionner le token suivant le plus probable et l’ajouter à la séquence
      • répéter jusqu’à obtenir EOS ou atteindre la longueur maximale
    • Dans l’exemple, l’exécution produit SOS hola mundo world pour l’entrée hello world
    • Comme tous les poids et embeddings sont aléatoires, le résultat n’est pas une bonne traduction, ce qui est ici le comportement attendu

Conclusion et portée

  • L’exemple relie dans un même flux les composants clés d’un transformeur : embeddings, encodage positionnel, self-attention, attention multi-têtes, FFN, connexions résiduelles, layer normalization, attention encodeur-décodeur et sortie softmax
  • Les architectures de transformeurs modernes ajoutent de nombreuses techniques, mais les mathématiques fondamentales reposent toujours sur la structure présentée ici
  • La pile utilisée peut varier selon le type de tâche
    • pour une tâche centrée sur la compréhension, comme la classification, on peut placer une couche linéaire au-dessus de la pile d’encodeurs
    • pour une tâche centrée sur la génération, comme la traduction, on peut utiliser à la fois une pile d’encodeurs et une pile de décodeurs
    • pour une génération libre, comme avec ChatGPT ou Mistral, on peut n’utiliser qu’une pile de décodeurs
  • L’apprentissage n’est pas traité ici ; l’objectif est de comprendre les mathématiques de l’inférence lorsqu’on utilise un modèle existant
  • Pour une ressource mathématique plus formelle, voir ce PDF

À lire aussi

1 commentaires

 
GN⁺ 2024-01-04
Commentaires Hacker News

  • Le « mystère » du Transformer tient au fait qu’au lieu de multiplier, à chaque couche, des poids et des valeurs statiques dans un ordre linéaire, on crée trois matrices obtenues en multipliant la même entrée par des poids appris, puis on multiplie ces matrices entre elles.
    Cela fonctionne bien grâce à un parallélisme accru, mais la formule d’attention elle-même est fixe, ce qui la rend très limitée.
    Pour aller plus loin, il semble nécessaire de trouver un moyen de généraliser le graphe de calcul lui-même en paramètres apprenables. Je ne sais pas si c’est possible avec les méthodes classiques à base de gradient, à cause des effets chaotiques où de petits changements entraînent de grands écarts de performance ; il faudra peut-être, en interne, quelque chose comme des algorithmes génétiques ou l’optimisation par essaim particulaire.

    • Cette explication n’est pas du tout correcte. Ce qui rend les Transformers particuliers, c’est qu’ils permettent à chaque élément d’une séquence de choisir, parmi tous les autres éléments, les parties importantes pour lui, puis de les extraire pour les calculer.
      Par rapport aux RNN, le grand avantage théorique est qu’ils prennent cela en charge sans perte. Chaque élément peut en effet accéder à toute l’information de tous les autres éléments de la séquence, ou, dans un ordre temporel, à toute l’information des éléments précédents.
      À l’inverse, les RNN et les « Transformers linéaires » compressent les valeurs passées ; il est donc généralement difficile pour le dernier élément d’une longue séquence d’accéder à toute l’information du premier, et c’est impossible sauf si l’état interne est très grand et ne jette aucune information.
    • Dire qu’« il faut généraliser le graphe de calcul en paramètres apprenables pour aller plus loin » est assez audacieux. Il y a déjà eu d’immenses progrès sans apprentissage du graphe de calcul.
    • Cette approche peut, en gros, apprendre à ignorer certains chemins et à amplifier les plus importants, puis élaguer les chemins dont la suppression n’entraîne pas une grosse perte de qualité.
      Le problème, c’est qu’on n’y gagne pas grand-chose. Les opérations autres que les multiplications matricielles seront probablement plus lentes, ou à une vitesse comparable.
    • Je suis d’accord sur l’idée de généraliser le graphe de calcul en paramètres apprenables. Cela ressemble à la façon dont les processus mentaux humains résolvent les problèmes que l’on aimerait voir les LLM résoudre : des problèmes plus proches du raisonnement réel, au-delà du « traitement du langage » où les Transformers excellent.
      Mais si l’on ajoute du contrôle de flux, on risque en fait d’obtenir une machine de Turing, et l’apprentissage devient alors effectivement le problème dont il est question. Cela dit, ce n’est peut-être pas un problème totalement insoluble.
    • Le réglage des hyperparamètres va déjà, dans une certaine mesure, dans la direction de l’apprentissage du graphe de calcul. Mais c’est très limité et cela demande beaucoup plus d’entraînement.

  • Pour une explication plus sèche, formelle et concise, il y a “The Transformer Model in Equations” de John Thickstun [0].
    Avec une notation mathématique standard, tout tient sur une page.
    [0] https://johnthickstun.com/docs/transformers.pdf

    • Je suis content qu’une explication comme celle-ci existe enfin. À mon avis, 7 lignes de notation mathématique valent bien mieux que plusieurs pages de bavardage qualitatif.
      On a souvent l’impression que les chercheurs en machine learning n’ont jamais étudié les maths.
    • En lisant des articles, j’ai dû recoller ce genre de choses plusieurs fois dans mes notes personnelles, et je n’étais jamais sûr de ne rien avoir oublié.

  • L’explication selon laquelle « on obtient NaN, les valeurs sont trop grandes et explosent en passant à l’encodeur suivant, c’est l’explosion du gradient » est, d’après ce que j’ai compris, fausse.
    Ici, on ne calcule de gradient à aucun moment, donc ce n’est pas une explosion du gradient.
    Le problème semble plutôt venir de l’implémentation de softmax, et une méthode numériquement stable pour implémenter softmax est expliquée ici [0].
    [0]: https://jaykmody.com/blog/stable-softmax/

    • Exact. J’essayais de relier les problèmes courants d’entraînement que sont l’explosion et la disparition du gradient à la sensibilité de softmax aux grandes valeurs, mais je reconnais que c’est trompeur ou imprécis, donc je vais réécrire cette partie.
      Cela dit, comme tout le réseau neuronal est sensible aux grandes valeurs, un softmax numériquement stable ne suffit pas à résoudre le problème. Pour que le réseau fonctionne, la normalisation est essentielle.

  • Les tutoriels sur les Transformers pourraient devenir les nouveaux tutoriels sur les monades. C’est un concept difficile à comprendre, du genre qu’on ne saisit qu’en se débattant avec des exemples et en les pratiquant.
    Comme beaucoup de choses en informatique.

    • Au moment où l’on comprend les Transformers, on n’est plus capable de les expliquer.
    • Les monades, un concept difficile ? Une monade n’est qu’un monoïde dans la catégorie des endofoncteurs, où est le problème ?
    • J’attends l’article de blog intitulé “You could have invented transformers”.

  • Je n’ai lu que six paragraphes et j’ai déjà une question.
    Dans Hello -> [1,2,3,4] World -> [2,3,4,5], les vecteurs sont censés être aléatoires, mais on dirait qu’il y a un motif. Je me demande si le 2 présent dans les deux vecteurs signifie quelque chose, ou si c’est l’ensemble complet qui crée l’unicité.

    • La réutilisation des chiffres tient surtout à une petite paresse de l’auteur. On peut regarder si deux vecteurs pointent dans des directions similaires, ou calculer l’angle entre eux pour estimer leur similarité.
      Ici, ils sont séparés d’environ 60 degrés et vont en partie dans la même direction, mais comme l’exemple évite les nombres négatifs, les vecteurs paraissent plus proches qu’ils ne le seraient en réalité.
      Le fait que les chiffres soient réutilisés n’a pas de signification en soi. Le 1 en première position n’a presque aucun rapport avec un 1 en deuxième position. On ne fait pas de convolution sur ces vecteurs.
    • Ce n’est pas un bon exemple. Pour chaque token, le vecteur est initialisé aléatoirement, chaque élément étant tiré d’une distribution normale.
      Après entraînement, des mots similaires auront dans une certaine mesure une similarité cosinus, mais il est très rare qu’elle soit aussi élevée que celle de [1,2,3,4] et [2,3,4,5].

  • Ce n’est pas une question tout à fait liée, mais je cherche un article ou un papier qui explique pourquoi un Transformer, alors qu’il fonctionne simplement comme un « prédicteur du prochain token », peut traiter des questions comme celles-ci :

    1. Les cas où il traite des mots, sous-mots ou tokens inconnus qu’il n’a pas vus dans le jeu de données d’entraînement. Exemple : créer dans pandas un tableau avec "sdsfs_ff" et "fsdf_value" comme colonnes
    2. Les cas où l’on crée un exemple absent des données d’entraînement et où l’on demande au LLM de produire une sortie similaire
      Ça doit être une question courante, mais je ne trouve pas les mots-clés à chercher. J’aimerais aussi des liens qui approfondissent les embeddings positionnels, et je n’ai pas encore obtenu de réponse satisfaisante sur la raison d’utiliser sinus/cosinus, ni sur la multiplication par rapport à l’addition.
    • J’imagine que même un caractère seul peut être encodé comme token, mais que le traiter à l’intérieur du modèle utilise davantage de bande passante, et qu’il contient par défaut moins de sens qu’un token correspondant à un mot précis.
      Si le modèle estime que c’est nécessaire, il peut reproduire une séquence inconnue en copiant des tokens de caractères individuels, ou en inventer une nouvelle si cela a du sens dans le contexte.
    • P(X_1=x_1, X_2=x_2, X_3=x_3) = P(X_3=x_3 | X_1=X_1, X_2=x_2) • P(X_1=x_1, X_2=x_2)
      = P(X_3=x_3 | X_1=X_1, X_2=x_2) • P(X_2=x_2 | X_1=x_1) • P(X_1=x_1)
      Autrement dit, si l’on dispose de la bonne distribution de probabilité conditionnelle pour le prochain token étant donné les tokens précédents, on obtient aussi la bonne distribution de probabilité pour toute la séquence de tokens.
      La « bonne distribution de probabilité sur les séquences de tokens », ou la bonne distribution de probabilité conditionnelle d’une séquence de tokens étant données certaines conditions, permet en pratique de décrire presque n’importe quel comportement d’entrée/sortie en ces termes.
      Donc le fait que cela « fonctionne en prédisant le prochain token » n’est pas, en principe, une contrainte forte sur les comportements d’entrée/sortie possibles.
      Aussi impressionnante que soit une action, le fait que sa sortie provienne de P(X_{n+1}=x_{n+1} | X_1=x_1, ..., X_n=x_n), c’est-à-dire de la « prédiction du prochain token », n’est pas contradictoire.
    • Il ne s’agit pas de reproduire les chaînes exactes des données d’entraînement, mais de reproduire des motifs et des motifs de motifs.
      La prédiction du prochain token est une tâche plus intelligente qu’elle n’en a l’air.

  • Je suis d’accord avec l’idée que « la complexité vient du nombre d’étapes et du nombre de paramètres ».
    Les modèles Transformer assez simples pour que nous les comprenions ne font rien d’intéressant, et les Transformers assez complexes pour faire des choses intéressantes semblent trop complexes pour que nous les comprenions.
    J’aimerais étudier des modèles de taille intermédiaire, suffisamment simples pour être compris mais assez complexes pour faire des choses intéressantes.

    • Si vous ne connaissez pas déjà ce domaine, les travaux sur l’interprétabilité mécaniste pourraient vous intéresser. Neel Nanda a publié beaucoup de ressources accessibles sur le sujet : https://www.neelnanda.io/mechanistic-interpretability
    • J’ai l’impression que les deux frontières ressemblent en réalité à ceci : la zone intermédiaire est probablement déjà trop complexe pour être réellement comprise par les humains, tout en étant encore trop petite pour faire des choses intéressantes.

  • C’est difficile à comprendre quand des concepts sont utilisés sans être définis ni introduits. La section Encoder démarre directement, sans expliquer ce que c’est ni où elle se situe dans l’ensemble du processus.
    Je vois ce que l’auteur essaie de faire, mais il manque la structure de base consistant à introduire les idées, les expliquer, puis les utiliser.
    Pour quelqu’un qui n’est pas déjà en train d’étudier le sujet et qui ne l’a pas à moitié compris, l’ensemble de l’article paraît confus.

  • J’ai déjà écrit un ANN à partir de zéro et je n’ai pas utilisé TensorFlow, mais cette explication reste confuse.
    J’ai demandé à ChatGPT de m’expliquer, sans utiliser les mots Matrix ni Vector, comment modifier un ANN de base pour implémenter la self-attention, et il m’a donné une explication assez simple. Je ne l’ai pas encore implémentée.
    Je préfère penser à tout en termes de nœuds, de poids et de couches. Les matrices et les vecteurs rendent plus difficile le lien avec ce qui se passe réellement à l’intérieur d’un ANN.
    Dans la manière familière d’écrire un ANN, chaque nœud d’entrée est un scalaire, mais l’algorithme de propagation avant multiplie tous les nœuds d’entrée par des poids et les additionne, ce qui ressemble à une multiplication vecteur-matrice. J’ai l’impression d’aborder ce type d’explications avec le mauvais état d’esprit, et il est possible qu’il me manque les connaissances de base nécessaires.