Architecture du Transformateur

Transformateur

• Un modèle d'apprentissage en profondeur introduit en 2017 par Vaswani et al. dans "Attention is All You Need".
• Principalement utilisé en traitement du langage naturel (TLN) pour la traduction automatique, mais applicable à la vision artificielle, etc.

Architecture

• Repose sur le mécanisme de self-attention, avec une architecture encodeur-décodeur.

Encodeur

• Constitué de plusieurs couches d'encodeur identiques.
• Chaque couche d'encodeur comprend deux sous-couches :
• Un mécanisme de self-attention multi-tête.
• Un réseau de feed forward entièrement connecté par position.
• Chaque sous-couche utilise une connexion résiduelle suivie d'une normalisation de couche.
• La sortie de chaque sous-couche est $LayerNorm(x + Sublayer(x))$.
• $Sublayer(x)$ est la fonction implémentée par la sous-couche.

Décodeur

• Comprend également plusieurs couches de décodeur identiques.
• Chaque couche de décodeur a trois sous-couches :
• Un mécanisme de self-attention multi-tête.
• Un mécanisme d'attention multi-tête fonctionnant sur la sortie de la pile d'encodeurs.
• Un réseau de feed forward entièrement connecté par position.
• Comme l'encodeur, chaque sous-couche utilise une connexion résiduelle, suivie d'une normalisation de couche.
• La sortie de chaque sous-couche est $LayerNorm(x + Sublayer(x))$.
• Elle comprend une couche linéaire finale et une fonction softmax pour prédire la probabilité du mot suivant.

Attention

• Un composant essentiel de l'architecture Transformer qui permet de se concentrer sur les parties les plus pertinentes de la séquence d'entrée.

Self-attention Dot-Product à l'échelle

• Le mécanisme d'attention utilisé prend trois entrées : les requêtes (Q), les clés (K) et les valeurs (V).
• La sortie est calculée en prenant le produit scalaire des requêtes avec les clés, divisé par la racine carrée de la dimension des clés ($d_k$), puis en appliquant une fonction softmax. * Cette dernière obtient les poids sur les valeurs.
• La formule est : $Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V$

Self-attention multi-tête

• Utilisation de la self-attention multi-tête pour que le modèle puisse apprendre différentes relations entre les mots dans une séquence.
• Multi-head attention exécute h fonctions d'attention indépendantes en parallèle au lieu d'une seule fonction d'attention.
• La sortie de chaque tête est concaténée puis projetée linéairement.

Avantages

• Parallélisation : peut gérer toute la séquence d'entrée en parallèle, contrairement aux RNN séquentiels.
• Plus rapide que les RNN, en particulier pour les séquences longues.
• Dépendances à longue distance : l'attention permet d'apprendre les dépendances entre les mots distants dans une phrase, ce qui est crucial pour la traduction automatique.
• Scalabilité : peut être mis à l'échelle vers des modèles massifs avec des milliards de paramètres pour une grande précision dans de nombreuses tâches de Traitement du Langage Naturel.

Applications

• Traduction automatique
• Résumé de texte
• Réponse aux questions
• Génération de texte
• Vision artificielle

Théorie Algorithmique des Jeux - Introduction

• Traite des contextes multi-agents où chaque agent a des préférences/objectifs différents.
• L'objectif est de concevoir des stratégies pour chaque agent afin d'obtenir le meilleur résultat possible pour lui-même.

Exemple

• Routage du trafic
• Chaque conducteur veut minimiser son temps de trajet.
• L'itinéraire emprunté par un conducteur affecte le temps de trajet des autres conducteurs.

Théorie Algorithmique des Jeux (TAG)

• Combine la théorie des jeux (incitations et rationalité) avec la conception d'algorithmes (calcul et efficacité).

Questions en TAG

• Calcul : Peut-on calculer efficacement les stratégies optimales ?
• Conception de mécanismes : Peut-on concevoir les règles du jeu pour que le résultat soit socialement souhaitable ?
• Prix de l'anarchie : Dans quelle mesure le résultat est-il inefficace lorsque les agents agissent de manière égoïste ?

Exemple 1 : Routage égoïste

Modèle

• Un graphe dirigé $G = (V, E)$.
• $r$ paires source-destination $(s_i, t_i)$.
• $f_i$ : quantité de trafic de $s_i$ à $t_i$.
• $\mathcal{R}_i$ : ensemble de chemins de $s_i$ à $t_i$.
• $c_e(x)$ : coût de l'arête $e$ lorsqu'elle transporte une quantité $x$ de trafic.

Agents

• Chaque agent contrôle une quantité infinitésimale de trafic et agit égoïstement pour minimiser son temps de trajet.

Équilibre de Wardrop

• Le flux $f$ est en équilibre de Wardrop si pour chaque $s_i, t_i$ et chaque $R_i, R'_i \in \mathcal{R}_i$ avec $f_R > 0$:

$\qquad c(R_i) \le c(R'_i)$

Coût social

• Temps de trajet total de tous les agents :

$\qquad SC(f) = \sum_{e \in E} f_e \cdot c_e(f_e)$

• Une question importante est de savoir dans quelle mesure le coût social à l'équilibre de Wardrop est élevé, comparé au coût social optimal ?

Exemple 2 : Enchères

Cadre

• Un seul objet à vendre.
• $n$ enchérisseurs avec des valeurs privées $v_i$.

Mécanisme

• Un mécanisme spécifie :
• Règle d'attribution : quel enchérisseur obtient l'objet ?
• Règle de paiement : combien chaque enchérisseur paie-t-il ?

But

• Concevoir un mécanisme qui soit :
• À l'épreuve des stratégies : L'offre véridique est une stratégie dominante.
• Efficace : L'objet est attribué à l'enchérisseur avec la valeur la plus élevée.
• Maximisation des revenus : Maximiser les revenus du vendeur.
• Enchère de Vickrey
• L'enchérisseur le plus offrant remporte, mais paie le deuxième prix le plus élevé.
• Elle est à l'épreuve des stratégies et efficace.

Plan du cours

1. Bases de la théorie des jeux :

• Jeux sous forme normale, équilibre de Nash, stratégies mixtes

2. Conception de mécanismes :

• Mécanisme de Vickrey-Clarke-Groves (VCG), maximisation des revenus

3. Prix de l'anarchie :

• Routage égoïste, jeux de formation de réseau

4. Partage équitable :

• Découpe de gâteau, allocation de ressources

5. Choix social :

• Règles de vote, manipulation

Prérequis

• Algorithmes et structures de données
• Théorie de base des probabilités
• Maturité mathématique

Complexité Algorithmique

• Mesure de la quantité de temps (complexité temporelle) et d'espace de stockage (complexité spatiale) qu'un algorithme requiert pour résoudre un problème d'une taille donnée.

Importance

• Aide à choisir le meilleur algorithme pour une tâche spécifique.
• Permet de prédire la performance d'un algorithme.
• Essentiel pour une conception logicielle efficace.

Expression

• Notation « Grand O », qui décrit la limite supérieure du taux de croissance d'un algorithme.

Complexités courantes

• $O(1)$ - Constante : Le temps d'exécution est le même quelle que soit la taille de l'entrée.
• $O(log n)$ - Logarithmique : Le temps d'exécution augmente logarithmiquement avec la taille de l'entrée.
• $O(n)$ - Linéaire : Le temps d'exécution augmente linéairement avec la taille de l'entrée.
• $O(n log n)$ - Linéarithmique : Le temps d'exécution augmente presque linéairement avec la taille de l'entrée.
• $O(n^2)$ - Quadratique : Le temps d'exécution augmente quadratiquement avec la taille de l'entrée.
• $O(2^n)$ - Exponentielle : Le temps d'exécution double à chaque ajout de taille à l'entrée.
• $O(n!)$ - Factorielle : Le temps d'exécution augmente considérablement avec la taille de l'entrée.

Exemple

• Recherche d'un élément dans un tableau trié :
• Recherche linéaire : $O(n)$
• Recherche binaire : $O(log n)$
• La recherche binaire est plus efficace pour les grands tableaux en raison de sa complexité temporelle logarithmique.
• La compréhension de la complexité algorithmique aide à écrire un code efficace et évolutif.

Fonction Logistique

• Aussi appelée courbe sigmoïde. Forme mathématique :

$\qquad S(x) = \frac{L}{1 + e^{-k(x-x_0)}}$

• $x_0$ est la valeur du point milieu de la sigmoïde
• $L$ est la valeur maximale
• $k$ est la pente de la courbe
• Fonction logistique standard : $L=1$, $x_0=0$ et $k=1$

$\qquad S(x) = \frac{1}{1 + e^{-x}}$

• Utilisée en statistiques, en apprentissage automatique comme fonction d'activation des réseaux de neurones, en biologie pour la modélisation de la croissance des populations, et en économie pour modéliser la diffusion d'une innovation.

Propriétés

• Définie pour toutes les valeurs réelles de $x$.
• Continue et différentiable.
• Bornée entre 0 et $L$.
• Croissante.
• Symétrique par rapport au point $(x_0, L/2)$.

Dérivée

• La dérivée de la fonction logistique est :

$\qquad S'(x) = kS(x)(1 - S(x)/L)$

• Pour la fonction logistique standard :

$\qquad S'(x) = S(x)(1 - S(x))$

• La dérivée est maximale au point milieu de la sigmoïde, à $x = x_0$