Comprendre et implémenter l'algo de score BM25

En tant que SRE, je dois souvent chercher des informations dans des logs, des tas de logs, beaucoup d’informations, dans beaucoup de fichier. Et en règle générale, que ce soit sur internet ou même sur votre ordinateur, vous êtes confronté au même problème. Vous devez chercher de l’information dans des documents qui s’accumulent de plus en plus.

On a là une problématique : quand je cherche le mot Panda sur mon ordinateur, quel fichier est-il censé me remonter en premier ? Le plus récent ? Non, le plus pertinent ! Et savoir si un document est pertinent par rapport à une recherche est le sujet du jour.

Installez-vous, prenez un café, un thé ou un chocolat chaud. C’est parti !

La problématique du jour peut être formalisée comme ceci : pour une recherche, je veux un score de pertinence lié à mes documents, et le premier document qui sortira de ma recherche sera celui avec le plus gros score !

Avant de commencer, un petit mot : cet article contient plusieurs formules mathématiques. Pas de panique, on va traverser ça ensemble étape par étape, et je vais tout expliquer clairement pour que ce soit simple à comprendre.

On va commencer avec une petite liste de documents pour nous accompagner tout au long.
C’est parti pour les présentations :

• Doc 1 : « Un panda est un animal blanc et noir »
• Doc 2 : « Le chien est blanc »
• Doc 3 : « Le chat est noir »
• Doc 4 : « Le panda n'est ni un chat ni un chien »
• Doc 5 : « Le panda roux est roux »
• Doc 6 :« Noir c'est noir, il n'y a vraiment plus d'espoir Je suis dans le noir, j'ai du mal à croire Noir c'est noir, il n'est jamais trop tard Noir c'est noir, il me reste l'espoir Noir c'est noir, il me reste l'espoir Noir c'est noir, il me reste l'espoir »

C’est un jeu de test assez simple, mais qui permet déjà de voir un peu le problème du scoring.

Commençons de façon intuitive : si je cherche le mot « noir », quel document est le plus pertinent ? Entre les documents 1, 3 et 6 ?

Pas facile hein ?

Avant d’entrer un peu plus dans la problématique, posons quelques définitions.

Token
Nos documents, et même notre recherche, ne sont pas composés de "mots", mais de ce qu’on va appeler des tokens.
Pour ce blog post, un mot = un token. Donc pas de gros changement, mais comme on va utiliser le mot token tout au long de l’article, autant le dire dès maintenant.
Par exemple, le doc 1 contient les tokens suivants :
[« Un », « panda », « est », « un », « animal », « blanc », « et », « noir »]

Index inversé
Quand on cherche le mot noir dans nos documents, on ne va pas les ouvrir un par un pour voir si le mot est dedans.
Avant toute recherche, notre application doit indexer les documents : les parcourir pour extraire les tokens présents dans chacun. Pendant cette étape, on construit ce qu’on appelle un index inversé.
Un index inversé, est un dictionnaire où :

• La clé, est un token
• La valeur associée, est la liste des documents qui contiennent ce token

Par exemple, notre index inversé contient les tokens/clés :
« le », « panda », « est », « un », « animal », « noir », « et », « blanc », « chien », « chat », …
La clé « panda », est associée aux documents 1, 4 et 5.
La clé « noir », est associée aux documents 1, 3 et 6.
Et ainsi de suite.

Voyons aussi un léger aperçu des classes que nous allons manipuler.

Nous avons en premier la classe Document:

public class Document
{
    public string Id { get; set; }
    public string Name { get; set; }
    public string Path { get; set; }
    public string Content { get; set; }
    public int Length { get; set; }
    public List<string> ContentTokens { get; set; }
    public List<string> TitleTokens { get; set; }
    public DateTime IndexedAt { get; set; } = DateTime.UtcNow;
}

Et le résultat de notre recherche, via la classe SearchResult:

public class SearchResult
{
    public string Id { get; set; }
    public string Name { get; set; }
    public string Path { get; set; }
    public string ContentSnippet { get; set; }
    public double Score { get; set; }
    public DateTime IndexedAt { get; set; }
}

Notre résultat final est donc une liste d’objets SearchResult.

---

Algorithme de score, simple, basique

Une première façon de faire que l’on pourrait imaginer, c’est de compter le nombre de fois qu’un token apparaît dans le document. Si je cherche le token « noir », il apparaît une fois dans le doc1, une fois dans le doc3 et 11 fois dans le doc6.
Donnons donc un score de 1 à chaque fois que le token est présent. Cela se fait très facilement en C# avec LINQ :

public int GetScore(string token, Document doc)
{
    int score = 0;
    var tokens = Tokenize(content);
    score = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
    return score;
}

Ici, nous comptons le nombre de fois où un token de notre requête est présent dans le document.

On aura donc un score de 1 pour les documents 1 et 3, et un score de 11 pour le document 6.

Bon… mis à part que le nombre de tokens n’est pas forcément un bon indicateur, on va vite se rendre compte d'un autre problème. Si ma requête est « chat », « noir », le document 6 aura toujours un score de 11, alors que le document 3, qui contient les deux tokens, n’aura qu’un score de 2.

Alors qu’il contient les deux tokens de ma requête ! Il est donc logiquement, pour nous, plus pertinent !

Pour régler ce premier problème, on peut ajouter un boost au score final quand un document contient tous les tokens.
Mais surtout, on peut tenter de réduire l’impact d’un token qui apparaît plusieurs fois dans un document.

Est-ce qu’un document qui contient 50 fois le token « noir » doit avoir un score deux fois supérieur à un document qui contient 25 fois le même token ?
Probablement pas. Être devant, oui, mais pas autant !

Et puis, les documents 1 et 3 ont le même score (1) pour le token « noir ».
Nous n'avons aucun moyen de les départager avec cette simple méthode.

---

Une version améliorée de la fonction de score

On peut modifier notre fonction de score pour :

• Calculer le score pour tous les tokens de la requête
• Limiter l’impact qu’un seul token peut avoir sur le score final
• Booster les résultats qui matchent plusieurs tokens

public int GetScore(List<string> queryTokens, Document doc)
{
    int totalScore = 0;
    int matchToken = 0;

    foreach (var token in queryTokens)
    {
        int score = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (score > 5)
            score = 5;

        if (score > 0)
            matchToken++;

        totalScore += score;
    }

    totalScore += matchToken * 10;
    return totalScore;
}

Désormais, un token ne peut plus influencer le score au-delà de 5.
Et le score du document gagne 10 points par token trouvé dans la requête.

Faisons un nouvel essai avec la requête « chat », « noir » :
Les documents correspondants sont : 1, 3, 4 et 6.

• Les documents 1 et 4, qui ne contiennent qu’un seul token chacun, auront un score de 11 : 1 point pour la fréquence du token, et 10 points car ils matchent un token présent dans la requête.
• Le document 3 aura un score de 22 : 2 points pour la présence de « chat » et « noir », et 20 points pour avoir matché 2 tokens de la requête.
• Le document 6 aura 15 points : 5 points pour la fréquence du token « noir » (limitée à 5), et 10 points pour avoir matché 1 token.

Résultat final :

• Doc 3 → 22 points
• Doc 6 → 15 points
• Doc 1 et Doc 4 → 11 points

On a réglé nos deux premiers problèmes… mais on peut faire mieux !

Ici, le vrai problème, c’est la limite à 5.
Ce n’est pas tant la valeur "5" qui pose problème, mais le fait qu’on a une augmentation linéaire du score qui s’arrête brutalement à une limite arbitraire.

---

Les rendements décroissants

Pour régler ce problème, on ne va pas instaurer une limite fixe au-delà de laquelle la fréquence d’un terme ne rapporte plus de points, mais plutôt un rendement décroissant. Par exemple, la première occurrence vaut 1, la deuxième 0.95, la troisième 0.92, etc.
Voici la formule que l’on va utiliser :

Par exemple, utilisons une valeur de decay à 0.97, pour la requête « noir ».

Pour un document qui aurai une fréquence du token « noir » de 6, obtient le résultat suivant :

La différence n’est ici pas flagrante (on aurai eu 6 avant, on a 5.4 maintenant). Mais calculons le score de fréquence avec un token qui apparaîtrait encore plus :

• Pour 20 :

• Pour 50 :

• Pour 100 :

On a donc bien un moyen de différencier deux documents qui n’auraient pas le même nombre d’occurrences d’un token, sans pour autant favoriser exagérément un document qui contient ce token un très grand nombre de fois.

L’impact du terme sur le score diminue progressivement.
On obtient donc une évolution non linéaire, et on évite d’arrêter arbitrairement le moment où la fréquence d’un token cesse d’avoir un effet.

public double GetScore(List<string> queryTokens, string content, double decay = 0.97)
{
    double totalScore = 0;
    int matchToken = 0;

    foreach (var token in queryTokens)
    {
        int frequency = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());

        if (frequency > 0)
            matchToken++;

        double freqScore = (1 - Math.Pow(decay, frequency)) / (1 - decay);

        totalScore += freqScore;
    }

    if (matchToken == queryTokens.Count)
        matchToken *= 2;

    totalScore += matchToken * 10;

    return totalScore;
}

Mais est-ce qu’on peut faire mieux ? Ou plutôt : quels autres problèmes pouvons-nous encore avoir ?

Faisons la requête suivante : « le », « animal »
Si on se base uniquement sur le score de fréquence (et on peut le faire, car aucun document ne matche les deux tokens, donc le boost donné par le nombre de tokens matchés n’aura ici aucun effet), les documents contenant le token « le » auront tous le même score :

• doc2 – 1
• doc3 – 1
• doc5 – 1
• doc6 - 1

Pour le token « animal », qui n’est présent qu’une seule fois dans le document 1, il obtiendra également un score de 1.

On se retrouve donc encore une fois avec un manque de discrimination entre les documents. On pourrait penser que, comme chaque terme n’apparaît qu’une fois dans chaque document, on ne peut pas mieux faire... Mais c’est faux !
Il existe une différence : leur fréquence dans l’ensemble des documents, pas juste dans un document.

Le mot « le » apparaît dans presque tous les documents, alors que « animal» n’apparaît que dans un seul.

Il y a donc une différence de rareté — et cette rareté, on peut l’exploiter.

---

TF-IDF

Jusqu’à présent, nous avons uniquement calculé ce qu’on appelle le TF (Term Frequency), c’est-à-dire la fréquence d’un token dans un document. Il est maintenant temps d’inclure dans notre score le Inverse Document Frequency (IDF), pour mesurer la rareté d’un mot dans l’ensemble des documents.

L’idée est de se dire que plus un mot est rare, plus il est informatif. Ce qui est exactement le cas ici : le token « le», présent partout, n’aide pas à affiner le résultat.

Pour calculer notre IDF, nous allons utiliser la formule suivante :

Où t est le token, N le nombre total de documents dans notre corpus, et nt le nombre de documents qui contiennent ce token.

Calculons l’IDF de « le » :

Puis de « animal » :

Et utilisons cette IDF dans notre calcul de score, qui s’appelle désormais TF-IDF (la multiplication de TF par IDF) :
Vu que notre TF est toujours égal à 1 ici, le calcul est simplifié : on garde uniquement la valeur de l’IDF.
Les scores des documents pour notre requête sont donc maintenant :
doc1 – 0.778
doc2 – 0.079
doc3 – 0.079
doc4 – 0.079
doc5 – 0.079
doc6 – 0.079

Et si on avait un autre document ne contenant que les 2 tokens il se placerait en 1er position avec le score de 0.857

Remarquez qu’on n’a même plus besoin de booster artificiellement le score en fonction du nombre de tokens matchés dans la requête — un boost qui était arbitraire. Et c’est beaucoup mieux !

On a la formule, passons maintenant au code :

public double GetScore(List<string> queryTokens, Document doc, double decay = 0.97)
{
    double totalScore = 0;

    foreach (var token in queryTokens)
    {
        int frequency = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());
        if (frequency == 0)
            continue;

        int df = ReversedIndex[token].Count;
        double idf = Math.Log((double)Documents.Count / (1 + df));

        double tf = (1 - Math.Pow(decay, frequency)) / (1 - decay);
        double tfidf = tf * idf;

        totalScore += tfidf;
    }

    return totalScore;
}

Le calcul de fréquence ne change pas : on récupère simplement la fréquence des documents contenant le token (df), grâce à notre index inversé, qui contient déjà cette information.

Le nombre total de documents est lui aussi déjà connu au moment de l’indexation.

On a donc notre IDF, notre TF, et donc le score final du document !

Mais… est-ce qu’on peut faire encore mieux ?
Voyons les limites actuelles (même si on est déjà pas mal).
Un des problèmes vient du TF : comme on l’a vu, il peut augmenter très vite et biaiser le score.

Dans un premier temps, on avait mis en place une limite de saturation pour éviter ça. Limite qui, normalement, n’est pas prévue dans le TF-IDF classique.

Mais malgré ça, cet algorithme favorise en réalité les documents longs (via le TF), alors qu’un document long n’est pas forcément plus pertinent.
De plus, on a peu de paramètres sur lesquels jouer pour fine-tuner un peu nos résultats (à part le decay, qui n’est pas non plus présent dans la version de base).

Il est donc temps de passer à un nouvel algorithme : BM25.

Best Match 25

Best Match 25 est la 25ᵉ version de l'algorithme censé combler un peu les problèmes du TF-IDF.

Voici d’abord sa formule :

Inutile de partir en courant, si vous êtes arrivé jusqu’ici, vous avez toutes les cartes en main pour la comprendre, et on va voir ça ensemble.

L’IDF, on le connaît déjà, aucun problème donc. On va plutôt regarder ce qui vient remplacer le TF.

Commençons par le numérateur :

• f(t,d) est la fréquence du terme t dans le document d.
• k1 +1 est un moyen de contrôler la saturation, exactement comme notre decay plus haut.

Plus k1 est petit, plus la saturation est rapide, ce qui réduira de façon non linéaire l’impact de chaque nouveau token présent dans le document.

Pour le dénominateur, on retrouve encore notre fréquence et notre variable k1 pour la saturation, ainsi qu’un facteur de normalisation lié à la longueur du document.

• |d| est la longueur actuelle du document (le nombre de tokens qu’il contient).
• avgdl est la longueur moyenne de nos documents indexés
• b est un paramètre qui sert à ajuster l’importance de la normalisation.

Quand nous avons un document qui est donc plus long que la moyenne, le score aura donc tendance à diminuer. Au contraire, un document court verra son score progresser plus rapidement.

Voyons ça avec un exemple. Reprenons notre liste de documents, et excluons le document 6 qui était très long. Et cherchons le token « noir ».

Commençons par définir nos paramètres k1 et b.

• k1 sera 1.5
• b sera 0.75

(ce sont des valeurs assez communes pour ces paramètres).

Calculons aussi la longueur moyenne de nos documents qui est : 8 + 4 + 4 + 9 + 5, soit 30. Divisé par le nombre de documents (5), ça nous donne une longueur moyenne de 6.

avgdl est donc égal à 6.

Le token « noir » est présent dans doc1 et doc3, avec un IDF de 0.916.
Commençons par calculer le score du document 1. Sa longueur |d| est de 8.

Commençons par remplacer les valeurs du numérateur : la fréquence du terme dans le document est de 1, la valeur de k1 est de 1.5. On connaît aussi déjà l’IDF. On a donc :

Ou :

Au dénominateur, on peut aussi facilement remplacer les valeurs déjà connues (tf et k1) :

On connaît la longueur moyenne des documents et la longueur du document actuel, on peut donc remplacer |d| et avgdl :

Ou :

b est connu, il est de 0.75 :

On a donc :

Un score final donc de 0.796 pour le document 1. Qu’en est-il du document 3 ?

Le document 3 est très similaire : la fréquence du terme est toujours de 1 et l’IDF est le même. La seule partie qui change est bien sûr la longueur du document, qui au lieu d’être de 8 sur 6, est de 4 sur 6.

Un score final de 1.077 pour notre document 3. Un meilleur score que notre document 1 !

Beaucoup de calculs ont été nécessaires pour démontrer comment marche BM25, mais les opérations étant assez simples, elles sont en fait très faciles à traduire en code :

public double GetScore(List<string> queryTokens,  Document doc)
{
    double tfWeight = 1.5;
    double docLengthPenalty = 0.75;
    double score = 0;
    double avgDocLength = Documents.Average(doc => doc.Key.Length);

    foreach (var token in queryTokens)
    {
        int tf = doc.ContentTokens.Count(t => t == token.ToLowerInvariant());

        if (tf == 0 || !ReversedIndex.ContainsKey(token))
            continue;

        int df = ReversedIndex[token].Count;
        double idf = Math.Log((double)Documents.Count / (1 + df));

        double norm;

        norm = (tf * (tfWeight + 1)) /
                (tf + tfWeight * (1 - docLengthPenalty + docLengthPenalty * (doc.Content.Length / avgDocLength)));

        score += idf * norm;
    }

    return score;
}

---

Bravo, vous savez maintenant comment calculer un score de pertinence sur un contenu et renvoyer en premier le meilleur document à votre utilisateur.
Bien sûr, d’autres paramètres peuvent être pris en compte, comme les tokens trouvés dans le titre, la date de modification du document ou même sa localisation.

Ici, nous nous sommes concentrés sur le contenu d'un document, mais cet algorithme peut être adapté et complété avec la d’autres champs comme le titre, la date, etc.