LLM from scratch en Python (partie 1)

L'objectif de ce "cours" (à l'origine, c'est plutôt un bloc note que j'ai orienté avec un ton éducatif) est de comprendre comment fonctionne une LLM. Pour ce faire, rien de mieux que de construire notre propre moteur.

Note

💡 Définition : Un LLM (en anglais Large Language Model, en français grand modèle de langage/linguistique est un modèle d’intelligence artificielle entraîné à comprendre et à générer du texte.

Notre moteur permettra de :

Lire un texte,
apprendre quelle lettre a tendance à suivre (statistiquement) quelle lettre,
générer du texte,
et mesurer la propre qualité du résultat.

Pour commencer, nous allons construire un n-gramme, et plus précisément un bigramme.

Note

💡 Définition : Un \(n\)-gramme est une sous-séquence de \(n\) éléments construite à partir d'une séquence donnée dont il est possible d'obtenir la fonction de vraisemblance de l'apparition du \(n\) suivant. Par extension, un bigramme est un cas particulier d'une séquence de deux éléments adjacents. Dans notre cas, 2 lettres consécutives.

Un bigramme est un modèle minuscule, mais il contient les ingrédients d'un LLM : un vocabulaire, des probabilités, une génération par "tirage au sort" et une fonction de perte.

Le problème

Un modèle de langage répond à une seule question : Etant donné le caractère qui précède, quelle est la probabilité de chaque caractère possible ensuite ? Pour y répondre concrètement, nous allons utiliser un texte minuscule qui servira de fil rouge. Le mot : banane (parce que pourquoi pas).

Le texte comme suite de symboles

Un texte de longueur \(T\) est une suite de caractères \(x_1\), \(x_2\), ... , \(x_T\). Pour notre mot banane, cela donne :

t	1	2	3	4	5	6
\(x_t\)	b	a	n	a	n	e

Ainsi, \(T = 6\). L'ensemble des caractères distincts s'appelle le vocabulaire : \(\{ a, b, e, n\}\) et sa taille est noté \(V = 4\).

texte = 'banane'

alphabet = sorted(set(texte))
V = len(alphabet)

print(alphabet, V)

['a', 'b', 'e', 'n'] 4

Note

La fonction set() permet de construire un ensemble dont les éléments sont uniques et non ordonnés.
et la fonction sorted() permet de les ordonner selon l’ordre lexicographique (basé sur les valeurs Unicode)

Dans un vrai LLM, un caractère devient un token (nous opérons une tokénisation), nous verrons cela plus tard.

Calculer les paires

Une paire est un caractère accompagné de son suivant, notée \((x_t, x_{t+1})\). Un texte de \(T\) caractères est composé de \(T-1\) paires. Pour banane, on a les paires suivantes :

(b,a)  (a,n)  (n,a)  (a,n)  (n,e)

On note :

\(N(a,b)\), le nombre de fois où la paire \((a,b)\) apparaît. Pour notre mot banane, nous avons \(N(a,n)=2\).
\(N(a)\), le nombre de fois où \(a\) est suivi de quelque chose. Dans notre cas, \(N(n) = 2\)

On a toujours \(N(a) = \sum_b N(a,b)\). Par exemple, dans banane, le caractère \(n\) est suivi de \(a\) une fois et de \(e\) une fois. \(N(n,a)=1\), \(N(n,e)=1\) et donc \(N(n)=1+1=2\).

On parcourt donc notre texte une seule fois. Pour chaque position dans le texte, on lit la paire et on incrémente de 1 deux compteurs :

Celui de la paire,
et celui du premier caractère.

texte = 'banane'

comptes = {}   # Compteur de la paire, N(a,b)
totaux = {}    # Compteur du premier caractère, N(a)

for i in range(len(texte) - 1):
    a = texte[i]
    b = texte[i + 1]
    comptes[(a, b)] = comptes.get((a, b), 0) + 1
    totaux[a] = totaux.get(a, 0) + 1

print(comptes)
print(totaux)

{('b', 'a'): 1, ('a', 'n'): 2, ('n', 'a'): 1, ('n', 'e'): 1}
{'b': 1, 'a': 2, 'n': 2}

Note

La fonction range() permet de boucler sur la taille du texte
et la méthode .get(clé, 0) lit le compteur s'il existe, sinon renvoie 0

Le modèle sous forme de tableau

Pour construire notre modèle, nous allons constituer un tableau de taille \(V \times V\). La ligne représente le caractère précédent et la colonne le caractère suivant. Chaque case est un paramètre : un nombre que le modèle retient. C'est le principe même d'un modèle : c'est un ensemble de paramètres. Apprendre consiste à lui trouver de bonnes valeurs, ici en les comptant, plus tard par descente de gradient.

précédent ↓ / suivant →	a	e	n	total N(a)
a	0	0	2	2
b	1	0	0	1
e	0	0	0	0
n	1	1	0	2

Notre modèle a donc 16 paramètres.

Du comptage aux probabilités

Une ligne du tableau répond à une question simple : le caractère précédent étant \(a\), que vient-il après ? La réponse est un entier. Mais il est nécessaire de normaliser la réponse, car un comptage simple ne permet ni de comparer, ni de tirer au sort, ni de noter le modèle :

Les comptes dépendent de la taille du texte et dire "\(a\) apparaît 2 fois après \(n\)" ne veut rien dire tant qu’on ne sait pas combien de fois \(n\) a été vu. Diviser par le total donne une valeur toujours comparable, entre \(0\) et \(1\).
Pour générer du texte, il faut des "chances" ; un tirage au sort a besoin de savoir le pourcentage de chance d'apparition de la lettre \(a\) et de la lettre \(e\) connaissant la lettre précédente.

Pour transformer notre question "le caractère précédent étant \(a\), que vient-il après ?" en probabilité, on divise chaque case par le total de la ligne :

\[P(b \mid a) = \frac{N(a,b)}{N(a)}\]

Il faut lire, \(P(b \mid a)\) probabilité de b sachant a. Ainsi, pour "banane" : \(P(a \mid n) = \frac{1}{2}\), \(P(e \mid n) = \frac{1}{2}\), \(P(n \mid a) = \frac{2}{2} = 1\) ... etc.

Une vraie distribution de probabilités respecte deux règles :

Chaque valeur est comprise entre \(0\) et \(1\),
et la somme sur une ligne vaut 1

Ainsi nous avons :

\[\sum_b P(b \mid a) = 1\]

Dès lors, on observe un défaut : La ligne \(e\) est entièrement vide dans notre exemple : \(N(e)=0\), donc on diviserait par zéro. Toutes les cases à 0 donnent également \(P=0\), donc le modèle déclare comme impossible un évènement qu'il n'a simplement jamais rencontré. Et c'est un grand problème pour le calcul de la perte.

Lisser pour éviter l'impossible

Dans notre modèle actuel, un évènement jamais rencontré est considéré comme impossible. Pour corriger ce défaut, il faut faire comme si on avait vu chaque paire possible \(\alpha\) fois de plus (disons \(\alpha = 1\)). C'est ce qu'on appel le lissage de Laplace.

\[P(b \mid a) = \frac{N(a,b) + \alpha}{N(a) + \alpha V}\]

Dans le dénominateur, le terme \(\alpha V\) est indispensable car on a ajouté \(\alpha\) dans chacune des \(V\) cases de la ligne. Donc le total de la ligne augmente de \(\alpha V\). Vérifions que la somme d'une ligne vaut toujours 1.

La probabilité de chaque \(b\) est :

\[P(b \mid a) = \frac{N(a,b) + \alpha}{N(a) + \alpha V}\]

Pour vérifier que la ligne vaut bien 1, on additionne ces probabilités sur tous les \(b\) :

\[\sum_b P(b \mid a) = \frac{\displaystyle\sum_b \bigl(N(a,b) + \alpha\bigr)} {N(a) + \alpha V} \]

Le numérateur vaut donc \(N(a) + \alpha V\)

\[\sum_b P(b \mid a) = \frac{N(a) + \alpha V}{N(a) + \alpha V} = 1\]

Vérifions avec notre banane, pour la ligne \(n\), avec \(\alpha = 1\) et \(V = 4\) :

b	N(n,b)	N(n,b) + 1	Probabilité
a	1	2	2/6
b	0	1	1/6
e	1	2	2/6
n	0	1	1/6
Somme	2	6	6/6 = 1

La somme des numérateurs vaut \(6\), et le dénominateur \(N(n) + \alpha V = 2 + 1×4\) vaut aussi \(6\).

Ainsi nous avons pour banane : \(P(a \mid n) = \frac{1+1}{2+4} = \frac{2}{6} \approx 0{,}33\) et même \(P(b \mid n) = \frac{0+1}{2+4} = \frac{1}{6} \approx 0{,}17\) au lieu de \(0\). La ligne \(e\), vide, donne \(1/4\) à chaque lettre : le modèle ne dit donc plus "impossible", mais "je ne sais pas, toutes les valeurs sont également possibles".

A noter que quand \(N(a)\) est très grand, \(\alpha\) et \(\alpha V\) deviennent négligeables et l'on retombe sur \(\frac{N(a,b)}{N(a)}\), et quand \(N(a)\) est petit, le lissage domine. C'est un réglage : trop petit, le modèle est trop sûr de lui ; trop grand, il n'apprend plus rien.

import math
import random

texte = "banane"

comptes: dict[tuple[str, str], int] = {}  # N(a,b)
totaux: dict[str, int] = {}  # N(a)
for i in range(len(texte) - 1):
    a = texte[i]
    b = texte[i + 1]
    comptes[(a, b)] = comptes.get((a, b), 0) + 1
    totaux[a] = totaux.get(a, 0) + 1
print(comptes)
print(totaux)

alphabet = sorted(set(texte))
V = len(alphabet)

lissage = 1


def proba(a: str, b: str) -> float:
    compte = comptes.get((a, b), 0)
    total = totaux.get(a, 0)
    return (compte + lissage) / (total + lissage * V)


# Vérifier qu'une ligne du tableau doit sommer à 1
print(sum(proba("n", x) for x in alphabet))


def suivante(a: str) -> str:
    poids = [proba(a, b) for b in alphabet]
    return random.choices(alphabet, weights=poids)[0]


lettre = "b"
sortie = "b"
for _ in range(30):
    lettre = suivante(lettre)
    sortie = sortie + lettre
print(sortie)

Note

random.choices(liste, weights=poids) tire un élément avec des chances proportionnelles aux poids etrenvoie une liste. Le résultat change à chaque lancement, c'est le principe d'un modèle probabiliste.

{('b', 'a'): 1, ('a', 'n'): 2, ('n', 'a'): 1, ('n', 'e'): 1}
{'b': 1, 'a': 2, 'n': 2}
1.0
bnnenbaaeaaabenenabnbanaenaneea

Notre modèle a généré le texte bnnenbaaeaaabenenabnbanaenaneea qui est, selon lui et pour le moment, probable. Vous pouvez générer plusieurs fois un texte, le résultat sera différent à chaque fois, mais probable.

Mesurer la qualité : la perte

Le texte bnnenbaaeaaabenenabnbanaenaneea est donc probable. Mais ce n'est pas une mesure, c'est un résultat probabilistique. Pour mesurer le résultat, il faut pouvoir le comparer avec un nombre et le minimiser automatiquement.

Pour une paire de lettre \((x_t, x_{t+1})\) du texte, notre modèle a prévu la probabilité \(p = P(x_{t+1} \mid x_t)\). Ainsi, si \(p\) est grande, le modèle avait "raison", inversement si \(p\) est petite, il est "surpris". La probabilité que le modèle donne au texte entier est le produit de toutes ces probabilités. Le souci est qu'un produit de nombres inférieurs à 1 devient vite microscopique. Sur un grande nombre de caractère (disons 1 millions), notre machine ne sait plus le représenter car le produit tend vers 0 :

print(0.0000002345 * 0.000006343)

1.4874334999999999e-12

Pour régler ce problème, il nous faut une opération qui remplace les produits par des sommes qui sont bien plus simples à manipuler, c'est le logarithme (naturel ou népérien). Celui-ci mesure "l'ordre de grandeur" d'un nombre. Multiplier un nombre par 10 ajoute toujours \(ln(10) \approx 2,3026\) car \(\ln(10x) = \ln(x) + \ln(10)\).

nombre	1000	100	10	1	0,1	0,01
log	6,91	4,61	2,30	0	−2,30	−4,61

Ainsi, un nombre minuscule comme \(10^{-400}\) devient un nombre ordinaire \(\log(10^{-400}) \approx -921\) et transforme bien un produit en sommes : \(\log(p \cdot q) = \log(p) + \log(q)\). Vérifions cela :

\[\log(0{,}5 \times 0{,}5) = \log(0{,}25) = -1{,}386 \quad\text{et}\quad \log(0{,}5) + \log(0{,}5) = -0{,}693 - 0{,}693 = -1{,}386\]

De plus, le logarithme est croissant : Si \(p\) est plus petit que \(q\), alors \(\log(p)\) est plus petit que \(\log(q)\). Le classement du modèle est inchangé.

On cherche à minimiser la perte, on ajoute donc un signe moins qu'un résultat "plus petit" signifie "meilleur" et on divise par le nombre de paires pour obtenir une moyenne :

\[\text{Perte} = -\frac{1}{T-1}\sum_t \log P(x_{t+1} \mid x_t)\]

Qu'on lit "la moyenne de \(-\log(p)\) sur toutes les paires du texte". On le nomme log-vraisemblance négative ou entropie croisée.

probabilité p	−log(p)	lecture
1	0	aucune surprise
0,5	0,69
0,1	2,30
0,01	4,61	grande surprise
0	+∞	impossible à calculer

Calculons maintenant la perte sans lissages, on applique d'abord la probabilité de chaque paire :

Paire	N(a,b)	N(a)	\(p = N(a,b) / N(a)\)
b → a	1	1	1
a → n	2	2	1
n → a	1	2	½
a → n	2	2	1
n → e	1	2	½

Puis on addition les valeurs de \(-\log(p)\) pour chaque \(p\) du tableau, que l'on divise par le nombre de paires (5 dans notre exemple) :

\[\begin{aligned} \text{Perte} &= -\frac{1}{5} \left( \log 1 + \log 1 + \log \frac{1}{2} + \log 1 + \log \frac{1}{2} \right) \\ &= -\frac{1}{5} \left( 0 + 0 - 0{,}69 + 0 - 0{,}69 \right) \\ &= \frac{1}{5} \cdot 1{,}39 \\ &\approx 0{,}28 \end{aligned}\]

Maintenant, avec lissage :

paire	calcul	p	−log(p)
b → a	(1+1)/(1+4)	0,40	0,92
a → n	(2+1)/(2+4)	0,50	0,69
n → a	(1+1)/(2+4)	0,33	1,10
a → n	(2+1)/(2+4)	0,50	0,69
n → e	(1+1)/(2+4)	0,33	1,10

Donc une perte d'environ 0,90 au lieu des 0,28 calculés sans lissage. La perte augmente parce que le lissage retire de la probabilité aux paires vues pour en donner aux paires jamais vues : après \(b\), le modèle ne dit plus "à 100%", mais "à 40%".

import math
import random

texte = "banane"
comptes = {}  #  N(a,b)
totaux = {}  #  N(a)
for i in range(len(texte) - 1):
    a = texte[i]
    b = texte[i + 1]
    comptes[(a, b)] = comptes.get((a, b), 0) + 1
    totaux[a] = totaux.get(a, 0) + 1
print(comptes)
print(totaux)

alphabet = sorted(set(texte))
V = len(alphabet)

lissage = 1


def proba(a: str, b: str) -> float:
    compte = comptes.get((a, b), 0)
    total = totaux.get(a, 0)
    return (compte + lissage) / (total + lissage * V)


# Vérifier qu'une ligne du tableau doit sommer à 1
print(sum(proba("n", x) for x in alphabet))


def suivante(a: str) -> str:
    poids = [proba(a, b) for b in alphabet]
    return random.choices(alphabet, weights=poids)[0]


lettre = "b"
sortie = "b"
for _ in range(30):
    lettre = suivante(lettre)
    sortie = sortie + lettre
print(sortie)


def perte(t):
    somme = 0
    for i in range(len(t) - 1):
        somme = somme - math.log(proba(t[i], t[i + 1]))
    return somme / (len(t) - 1)


print(perte("banane"))

0.899961934066053

Mais 0,90 ne veut pas dire grand chose. Un seul nombre ne permet pas d'interpréter la qualité du résultat, il faut le comparer avec ce qu'un modèle pourrait deviner au hasard. Le hasard pur, donnerait \(p = \frac{1}{V}\), donc une perte calculée de \(-\log\left(\frac{1}{V}\right)\) équivalent à \(\log V\) soit \(\log 4 \approx 1{,}39\). Le modèle fait donc un peu mieux que le hasard, mais sur un texte aussi court (5 paires dans notre exemple), le lissage pèse lourd.

Validation et sur-apprentissage

Tant que l'on mesure la perte sur le texte qui a servi à remplir le tableau, la note sera forcement bonne. C'est comme réviser un examen en connaissant d'avance les questions. Le modèle connait-il la langue ou seulement un texte précis ? On appele la mémorisation le sur-apprentissage.

La solution est de découper le texte en 2 :

Une grande partie (disons 90%) pour entrainer le modèle et compléter notre tableau de paramètre,
et le reste pour valider et mesurer la perte sur des données jamais vues.

Mais la mémorisation dépend du nombre d'observations par paramètre. Notre exemple "banane" avec nos 26 lettres (soit 676 cases) pour 5 paires observés, le tableau devient une copie du texte, le sur-apprentissage est garanti.

Pour un texte plus long (prenons par exemple le jeu de données "Tiny Shakespeare"[^1] qui est un extrait condensé des oeuvres de Shakespeare de quelques Ko), avec \(V=39\) (tout en minuscule), nous avons 1521 cases pour environ un million de paires, soit environ 700 observations par case. Chaque case est une moyenne de centaines de cas, donc elle capture une tendance, pas un détail.

Une fréquence mesurée sur \(n\) observations a une erreur typique de l'ordre de \(\frac{1}{\sqrt{n}}\). Avec \(n = 5\), l'erreur est d'environ 45 % (la fréquence colle à ce texte) alors qu'avec \(n = 700\), l'erreur passe à 4 % (la fréquence est stable et se généralise).

La limite d'un bigramme

Ce modèle ne regarde que le caractère qui précède. C'est pourquoi avec Tiny Shakespeare par exemple, le texte généré ressemble à sh t gntoow ms wham to. Si chaque paire est linguistiquement possible, l'ensemble n'a pas encore de sens.

La solution pourrait être d'augmenter le contexte à \(n\) caractères, mais le tableau aurait alors une ligne par contexte possible :

\[\text{Nombre de paramètres} = V^n \times V = V^{n+1}\]

Pour \(V=39\) et \(n=8\) par exemple, on aurait environ \(10^{14}\) cases pour un texte de seulement 1 million de caractères. Presque toutes les cases resteraient vide. Au final, compter ne peut plus suivre. Au lieu de stocker un décompte par cas possible, on pourrait plutôt utilise un petit nombre de paramètres qui s'ajusteraient pour donner de bonnes probabilités, et ce, même sur des contextes jamais vus. Et pour les ajuster, il faudrait savoir dans quel sens les modifier pour faire baisser la perte : ce sera le rôle de la dérivée en partie 2.

[^1] https://github.com/karpathy/char-rnn/blob/master/data/tinyshakespeare/input.txt