Recherche lexicale avec BM25

La recherche sémantique comprend le sens, mais elle peut manquer une correspondance exacte : un identifiant, un code d’erreur, un nom de produit. La recherche lexicale, elle, cherche les mots eux-mêmes. Cette leçon présente BM25, l’algorithme lexical le plus utilisé en RAG, et l’implémente.

Quand le sens ne suffit pas

Cherchez l’incident INC-2023-Q4-011 dans le rapport d’exemple. Dans la démonstration du cours officiel, la recherche sémantique ramène bien la section cybersécurité, qui contient l’identifiant, mais place en deuxième une section d’analyse financière qui ne le mentionne pas. Elle mesure une proximité de sens, pas la présence d’une chaîne précise.

L’article d’Anthropic sur la récupération contextuelle donne un exemple du même ordre : pour la requête « Error code TS-999 » dans une base de support technique, un modèle d’embedding trouve des pages sur les codes d’erreur en général, et peut manquer celle qui contient exactement « TS-999 ».

Comment BM25 classe les documents

1. Découper la requête en termes. « a INC-2023-Q4-011 » devient ["a", "inc-2023-q4-011"].
2. Mesurer la rareté de chaque terme. Un terme présent dans presque tous les documents, comme « a », ne distingue rien ; un terme rare, comme l’identifiant, compte beaucoup. C’est la fréquence inverse en documents, ou IDF.
3. Compter les occurrences dans chaque document, avec une saturation : la dixième occurrence d’un terme rapporte bien moins que la première.
4. Tenir compte de la longueur : à nombre d’occurrences égal, un document court est plus centré sur le terme qu’un long.

BM25 (Best Matching 25) prolonge ainsi TF-IDF, comme le rappelle l’article d’Anthropic, en ajoutant la saturation et la prise en compte de la longueur des documents.

Un index BM25

Le cours officiel fournit sa classe BM25Index dans un fichier à part. En voici une version complète, avec des valeurs courantes pour ses deux paramètres, k1 = 1,5 et b = 0,75 :

import math
import re
from collections import Counter

def tokenize(text):
    return re.findall(r"\w+(?:-\w+)*", text.lower())

class BM25Index:
    def __init__(self, k1=1.5, b=0.75):
        self.k1, self.b = k1, b
        self.documents = []
        self.term_counts = []
        self.doc_freq = Counter()

    def add_document(self, document):
        counts = Counter(tokenize(document["content"]))
        self.documents.append(document)
        self.term_counts.append(counts)
        self.doc_freq.update(counts.keys())

    def search(self, query, k=1):
        n = len(self.documents)
        avg_len = sum(sum(c.values()) for c in self.term_counts) / n
        results = []
        for doc, counts in zip(self.documents, self.term_counts):
            length = sum(counts.values())
            score = 0.0
            for term in set(tokenize(query)):
                tf = counts.get(term, 0)
                if tf == 0:
                    continue
                df = self.doc_freq[term]
                idf = math.log(1 + (n - df + 0.5) / (df + 0.5))
                score += idf * tf * (self.k1 + 1) / (tf + self.k1 * (1 - self.b + self.b * length / avg_len))
            if score > 0:
                results.append((doc, score))
        results.sort(key=lambda pair: pair[1], reverse=True)   # score décroissant : le meilleur d'abord
        return results[:k]

Trois détails comptent :

• tokenize garde les termes à tirets d’un seul tenant : INC-2023-Q4-011 reste un terme, au lieu de se perdre en « inc », « 2023 », « q4 » et « 011 ».
• La formule de l’IDF utilisée ici reste positive même pour un terme présent dans tous les documents.
• BM25 renvoie un score, à trier par ordre décroissant, alors que l’index vectoriel renvoie une distance, à trier par ordre croissant. La leçon suivante en tient compte.

L’essai

store = BM25Index()
for chunk in chunk_by_section(text):
    store.add_document({"content": chunk})

results = store.search("Que s'est-il passé avec INC-2023-Q4-011 ?", 3)
for doc, score in results:
    print(round(score, 2), doc["content"][:200], "\n----\n")

Dans la démonstration du cours officiel, BM25 place en tête les sections ingénierie logicielle et cybersécurité, les deux qui contiennent réellement l’identifiant.

Deux recherches complémentaires

Aucune des deux ne suffit seule. La solution courante, décrite par le cours officiel comme par l’article d’Anthropic, consiste à lancer les deux recherches et à fusionner leurs résultats : c’est l’objet de la leçon suivante.

À vous de jouer

Trouver les limites de chacune. Sur votre propre document, écrivez deux questions : l’une qui contient un identifiant ou un terme rare, l’autre qui reformule une idée sans reprendre ses mots. Lancez chacune dans le VectorIndex de la leçon 50 et dans BM25Index, et notez laquelle des deux recherches trouve le bon passage.

Sources officielles : BM25 lexical search (Claude Academy) · Contextual Retrieval (Anthropic : BM25, TF-IDF et correspondances exactes)

Points clés à retenir

• La recherche sémantique peut manquer une correspondance exacte ; BM25 cherche les mots eux-mêmes.
• BM25 donne du poids aux termes rares, sature les répétitions et tient compte de la longueur.
• Gardez les identifiants à tirets d’un seul tenant quand vous découpez en termes.
• BM25 renvoie un score à trier par ordre décroissant, l’index vectoriel une distance à trier par ordre croissant.
• Les deux recherches sont complémentaires : on les combine.