Produit

L'algorithme BM25 en pratique - 1re partie : en quoi les partitions influent sur le score de pertinence dans Elasticsearch

By
Shane Connelly

Voici la première publication de cette série de trois articles consacrée à l'algorithme Practical BM25 sur le classement par similarité (pertinence). La publication suivante est disponible en lien en bas de page.

Contexte

Dans Elasticsearch 5.0, nous sommes passés à Okapi BM25 comme algorithme de similarité par défaut, qui est utilisé pour noter les résultats en fonction d'une requête. Je ne vais pas trop m'étendre sur BM25 par rapport aux autres mesures dans ce blog, mais si vous souhaitez une introduction à la justification théorique de BM25, vous pouvez consulter la présentation BM25 Demystified d'Elastic{ON} 2016. Au lieu de cela, je vais couvrir (et j'espère démystifier) l'utilisation pratique de BM25 pour vous, y compris les paramètres disponibles et ce qui affecte la notation.

Gardez à l'esprit que cet article concernera principalement ceux qui effectuent la notation de documents textuels. En d'autres termes, il vise avant tout à aider nos utilisateurs de la fonction de recherche. Si vous indexez des logs ou des métriques et que vous renvoyez des résultats triés par un ordre explicite de métadonnées/numérique, comme l'horodatage, cet article ne satisfera probablement que votre curiosité.

Comprendre l'impact des partitions sur le scoring

Puisque j'espère que vous allez suivre cette procédure chez vous, l'une des premières choses à aborder est de comprendre comment le fait d'avoir plus d'une partition affecte le scoring, car Elasticsearch utilise par défaut 5 shards primaires par index. Commençons par créer un index appelé « people ». Les paramètres que je fournis ici sont les paramètres par défaut (et il est donc inutile de les définir), mais je vais le faire quand même pour être explicite à des fins de démonstration. J'utiliserai des variantes de mon nom (« Shane Connelly ») ici, mais n'hésitez pas à le remplacer par un nom de votre choix si vous suivez cette procédure chez vous. 

PUT people
{
  "settings": {
    "number_of_shards" : 5,
    "index" : {
        "similarity" : {
          "default" : {
            "type" : "BM25"
          }
        }
    }
  }
}

Ajoutons maintenant un document, puis recherchons-le. Tout d'abord, nous allons simplement ajouter mon prénom : 

PUT /people/_doc/1
{
  « title » : « Shane »
}
GET /people/_doc/_search
{
    "query": {
        "match": {
             « title » : « Shane »
         }
      }
}

Vous obtenez 1 résultat à ce stade, avec un score de 0,2876821. Nous verrons comment ce score est calculé dans un instant, mais examinons d’abord ce qui se passe lorsque nous ajoutons quelques documents supplémentaires avec différentes variantes de mon nom complet. 

PUT /people/_doc/2
{
  "title" : "Shane C"
}
PUT /people/_doc/3
{
  "title": "Shane Connelly"
}
PUT /people/_doc/4
{
  "title": "Shane P Connelly"
}

Et maintenant, effectuez à nouveau la même action de rechercher : 

GET /people/_doc/_search
{
    "query": {
        "match": {
             « title » : « Shane »
         }
      }
}

À ce stade, vous devriez effectivement obtenir 4 résultats, mais si vous examinez les scores, vous pourriez être perplexe. Les documents 1 et 3 ont tous deux un score de 0,2876821, mais le document 2 a un score de 0,19856805 et le document 4 a un score de 0,16853254. C'est un point qui déroute souvent les nouveaux utilisateurs. Les documents 2 et 3 sont très similaires — ils contiennent tous deux 2 termes et correspondent tous deux à « shane », mais le document 2 a un score bien inférieur. Vous pourriez commencer à supposer qu'il y a une différence dans le scoring de « C » par rapport à celui de « Connelly », mais en fait, cela est lié à la façon dont les documents ont été répartis dans les partitions.

Pour rappel, Elasticsearch divise les documents en partitions, et chaque partition contient un sous-ensemble des données. Si nous examinons : 

GET /_cat/partitions/people?v

Si vous exécutez ceci, vous verrez que la partition 2 contient 2 documents, tandis que les partitions 3 et 4 n’en contiennent qu’un seul (les partitions 0 et 1 ne contiennent encore aucun document). Cela signifie que le nombre total d’occurrences du terme « shane » diffère selon ces partitions, ce qui explique finalement la différence de scores dans ce cas. Par défaut, Elasticsearch calcule les scores par partition.

Les utilisateurs commencent à charger quelques documents dans leur index et se demandent « pourquoi le document A a-t-il un score plus élevé ou plus bas que le document B ? ». La réponse est parfois que l'utilisateur a un ratio relativement élevé de partitions par rapport aux documents, ce qui fausse les scores entre les différentes partitions. Il existe plusieurs façons d'obtenir des scores plus cohérents entre les partitions :

  1. Plus vous chargez de documents dans votre index, plus les statistiques de termes de vos partitions seront normalisées. Avec un nombre suffisant de documents, vous ne remarquerez peut-être pas les légères différences dans les statistiques de termes et donc dans le scoring de chaque partition.
  2. Vous pourriez utiliser un nombre de partitions inférieur pour réduire les écarts statistiques dans les fréquences des termes. Par exemple, si nous avions défini number_of_shards sur 1 dans les paramètres de l'index, nous obtiendrions des scores très différents. Nous verrions le document 1 avec un score de 0,13245322, les documents 2 et 3 avec des scores de 0,105360515 chacun, et le document 4 avec un score de 0,0874691. Il existe des compromis à avoir différents nombres de shards primaires, ce qui est abordé dans notre webinar sur le dimensionnement quantitatif des clusters.
  3. Vous pouvez ajouter ?search_type=dfs_query_then_fetch à la requête, ce qui permet d'abord de collecter les fréquences de termes distribuées (DFS = Distributed Frequency rechercher), puis de calculer les scores en les utilisant. En fait, cela renvoie le même score que si vous n'aviez qu'une seule partition. Observez la différence entre les résultats avec et sans le paramètre « search_type » : 
    GET /people/_doc/_search?search_type=dfs_query_then_fetch
{
    "query": {
        "match": {
             « title » : « Shane »
         }
      }
}
    Cela revient au même que d'avoir défini number_of_shards=1. Vous pourriez alors demander : « Eh bien, si cela produit des scores plus précis, pourquoi n'est-ce pas activé par défaut ? » La réponse est que cela ajoute un aller-retour supplémentaire pendant le traitement pour aller collecter toutes les statistiques, et pour certains cas d'utilisation (où la précision du score n'est pas aussi importante que la vitesse), cet aller-retour est inutile. De plus, avec suffisamment de données dans les partitions, les statistiques peuvent devenir très proches les unes des autres, rendant également les allers-retours inutiles. Si vous avez suffisamment de données, search_type=dfs_query_then_fetch n'est généralement nécessaire que lorsque les données entre les partitions continuent d'être inégalement réparties, comme c'est le cas avec certains routages personnalisés.

OK, nous avons maintenant une idée de la façon dont le partitionnement (sharding) peut affecter notre scoring (et comment l'ajuster). Ensuite, nous examinerons l'algorithme BM25 et verrons comment différentes variables entrent en jeu.

Poursuivez cette série avec : Partie 2 : L'algorithme BM25 et ses variables