Les Sparse Embeddings Démystifiés : Du One-Hot Encoding à BM25

Cet article de blog vise à clarifier certaines méthodes de Recherche d’Information (RI) liées aux sparse embeddings (ou vecteurs sparse).

Nous allons étudier les quatre méthodes les plus connues. Examinons-les par ordre croissant de complexité.

Avant de plonger dans les méthodes, nous devons préciser le contexte. Nous supposons avoir un corpus $\mathcal{C}$ de documents, et que chaque document est composé de mots. Ce corpus peut être utilisé pour précalculer certaines valeurs. Ensuite, nous recevons une query, qui est composée de mots, et l’objectif est de trouver le document du corpus le plus pertinent pour celle-ci. En fait, nous attribuons un score à chaque document du corpus et le document le plus pertinent sera celui ayant le score le plus élevé. Comme la query est inconnue à l’avance, son embedding doit être calculé dynamiquement au moment de la query (query-time) et ne peut pas être précalculé.

Pour réaliser cela, nous construisons d’abord un vocabulaire $V$, qui est un ensemble de mots. C’est un problème en soi, car il existe plusieurs façons de le construire. Pour l’instant, nous considérerons que le vocabulaire est constitué de l’ensemble des mots apparaissant dans le corpus.

Pour chaque méthode, nous fournissons une intuition, expliquons comment elle est liée aux sparse embeddings, ce qui peut être précalculé avec un corpus de documents donné, et comment nous trouvons le document le plus pertinent pour une query.

One-Hot Encoding

Un one-hot embedding est la représentation sparse la plus simple, où chaque dimension correspond à un mot unique du vocabulaire. Si un mot est présent, sa position est marquée par un 1 ; sinon, c’est 0. Le dot product entre deux vecteurs one-hot compte le nombre de mots en communs, donnant une mesure basique de chevauchement.

Embedding. Le sparse embedding est le vecteur sparse où chaque dimension correspond à un mot unique du vocabulaire. Le vecteur a un 1 pour la présence d’un mot et des 0 partout ailleurs.

Précalculé. Création du one-hot embedding de chaque document.

Calcul du score au query-time. Nous créons le one-hot embedding de la query. Ensuite, le dot product entre l’embedding de la query et celui d’un document compte le nombre de mots communs.

Plus le dot product avec un document est grand, plus le document est pertinent.

Bag of Words

Un Bag of Words (BoW) embedding est une représentation sparse où chaque dimension correspond à un mot unique du vocabulary. La valeur de chaque dimension représente le nombre d’occurrences de ce mot dans le document. Si un mot apparaît plusieurs fois, sa valeur correspondante reflète la fréquence ; s’il n’apparaît pas, sa valeur est 0. Le dot product entre deux vecteurs Bag of Words donne une mesure de chevauchement basée sur la fréquence des mots communs, fournissant un score de similarité plus nuancé que le One-Hot Encoding.

Embedding. Le sparse embedding est le vecteur sparse qui compte la fréquence de chaque mot dans le document. Contrairement au one-hot, les occurrences multiples d’un mot augmentent sa valeur.

Précalculé. Création du BoW embedding de chaque document.

Calcul du score au query-time. Nous créons le BoW embedding de la query. Ensuite, le dot product donne un score basé sur le nombre de fois où les mots se chevauchent, en tenant compte de leur fréquence (plus de chevauchement signifie un score plus élevé).

Plus le dot product avec un document est grand, plus le document est pertinent.

TF-IDF

Le TF-IDF améliore cela en pondérant les mots selon leur importance. La Term Frequency (TF) compte combien de fois un mot apparaît dans un document, tandis que l’Inverse Document Frequency (IDF) réduit le poids des mots communs dans le corpus. Par exemple, ’le’ pourrait avoir un TF élevé mais un IDF faible, résultant en un poids global faible. Les poids TF-IDF sont obtenus en multipliant TF et IDF. Ensuite, le dot product entre deux vecteurs TF-IDF donne un chevauchement pondéré, mettant l’accent sur les termes rares mais pertinents.

Embedding. Le sparse embedding est le vecteur pondéré où chaque mot se voit attribuer une valeur basée sur son importance. TF mesure la fréquence des mots dans le document, et IDF réduit le poids des mots communs dans le corpus.

Précalculé.

• Pour chaque term $t \in V$ et chaque document $D \in \mathcal{C}$, nous pouvons précalculer

  $$ \text{TF}(t,D) = \frac{f_{t,D}}{\sum_{t’ \in D} f_{t’,D}} $$

  où $f_{t,D}$ est le nombre d’occurrences du term $t$ dans le document $D$.

  Cela conduit à un tableau de $|V| \times |\mathcal{C}|$ valeurs.

• Pour chaque term $t \in V$ nous pouvons précalculer

  $$ \text{IDF}(t) = \log\left(\frac{|\mathcal{C}|}{1 + n_t}\right) $$

  où $|\mathcal{C}|$ est le nombre total de documents, et $n_t$ est le nombre de documents contenant le term $t$.

Ainsi, pour chaque document $D \in \mathcal{C}$ nous avons accès à $\text{TF-IDF}(t,D)=\text{TF(t,D)} \times \text{IDF}(t)$ pour chaque term $t \in V$. Cela signifie que nous avons un embedding de taille $|V|$ pour chaque document du corpus.

Calcul du score au query-time. Étant donné la query $Q$ nous calculons $\text{TF-IDF}(t,Q)$ pour chaque term $t \in V$. Nous avons alors un embedding de taille $|V|$ pour la query $Q$. Nous calculons enfin le dot product (ou cosine similarity) des vecteurs TF-IDF de la query et du document qui donne un chevauchement pondéré, mettant l’accent sur les termes rares mais pertinents.

Plus le dot product (ou cosine similarity) avec un document est grand, plus le document est pertinent.

BM25

BM25 affine davantage cela en introduisant une fonction de saturation qui limite l’impact de la term frequency, la rendant plus efficace pour les longs documents. Il prend également en compte la normalisation de la longueur des documents et ajoute un boost de pertinence ajustable pour les mots apparaissant à la fois dans la query et le document. BM25 utilise l’importance des termes, leur fréquence et la longueur du document pour calculer un score de pertinence, améliorant le TF-IDF.

Embedding. Pas de vecteur explicite. BM25 calcule un score de pertinence en utilisant la fréquence des termes, la longueur du document et l’importance des termes (IDF).

Précalculé.

• IDF pour chaque terme $t \in V$ :

  $$ \text{IDF}(t) = \log \left( \frac{|\mathcal{C}| - n_t + 0.5}{n_t + 0.5} + 1 \right) $$

  où $|\mathcal{C}|$ est le nombre total de documents dans le corpus, et $n_t$ est le nombre de documents contenant le term $t$.

• $f_{t,D}$ le nombre d’occurrences du terme $t$ dans le document $D$, pour chaque terme $t \in V$.

• Average document length $\text{avgdl}$.

Calcul du score au query-time. Le score BM25 est calculé comme :

$$ \text{Score}(Q, D) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{f_{t,D} \cdot (k_1 + 1)}{f_{t,D} + k_1 \cdot \left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)} $$

où $f_{t,D}$ est le nombre d’occurrences du terme $t$ dans le document $D$, $k_1$ et $b$ sont des paramètres ajustables, $|D|$ est la longueur du document, et $\text{avgdl}$ est la longueur moyenne des documents dans le corpus $\mathcal{C}$.

Plus le score est grand, plus le document est pertinent.

Conclusion

En résumé, le One-Hot Encoding est le plus simple, représentant la présence des mots. Le Bag of Words ajoute des informations de fréquence. Le TF-IDF pondère les mots selon leur importance, et le BM25 introduit une fonction de saturation, le rendant très efficace pour le ranking de documents, même longs.