Comment évaluer automatiquement la qualité des SERPs ?

Comment évaluer automatiquement la qualité des SERPs ?

Quand on est un industriel du search, on a un business assez simple finalement : on gagne de l'argent (via plusieurs canaux) proportionnellement à la masse des utilisateurs du moteur. Hors, la qualité des résultats de classement (les SERPs pour Search Engine Results Pages) est le nerf de la guerre pour se constituer un bonne audience. Chaque moteur a ses propres recettes pour construire les SERPs, mais toutes prennent en compte la qualité perçue par les utilisateurs comme feedback permettant de modifier les filtres et algorithmes mis en place.

C'est d'ailleurs très amusant : alors qu'un moteur est assez grossièrement une machine qui tourne toute seule, ce feedback sur la qualité est entièrement déterminé par le comportement des pauvres humains que nous sommes. Pour l'obtenir, on peut utiliser une vraie méthodologie de détermination humaine de la qualité, c'est-à-dire faire travailler des quality raters. Mais l'approche par le quality rating a plusieurs inconvénients : elle coûte cher, elle ralentit la prise en compte du feedback qualitatif (il n'y a pas autant de quality raters que d'utilisateurs) et enfin il n'y a pas forcément de garantie que les quality raters soient représentatifs des utilisateurs (notamment car ils sont parfois issus de pays culturellement différents).

Pour évaluer rapidement et de manière plus précise la qualité des SERPs, les moteurs vont utiliser des techniques de monitoring online du comportement de leurs utilisateurs. Bien sûr, ces techniques ne peuvent pas être abusivement intrusives : si on vous colle un gros pop-up pour vous demander si vous êtes content à chaque fois que vous cliquez sur le 4ème résultat fourni par le moteur, vous ne risquez pas de revenir souvent ! En pratique, la seule observation utilisable est la suivante : l'utilisateur tape une requête, le classement apparait, et le moteur voit ce qui est cliqué par l'utilisateur et sait si l'utilisateur revient pour taper une autre requête (si elle est la même ou similaire à la précédente, c'est un signe de mécontentement).

Une fois qu'on en est là, il ne subsiste qu'une seule interrogation : qu'est ce qu'on présente comme classement aux utilisateurs pour évaluer la qualité, et comment on détermine ce qui est "gagnant" de ce qui est "perdant" ?

Une méthode typiquement utilisée est de faire de l'A/B testing.  L'image qui suit (provenant du blog de l'équipe de Bing) montre les deux hypothèses qui sont utilisées, et comment elles sont combinées :

 image_thumb_1878E31E

Le problème qui vient immédiatement à l'esprit est celui de la combinaison (le terme technique est entrelacement) des hypothèses. En effet, selon la position dans la page et selon l'entourage, on sait que le taux de conversion est très variable. Il y a donc un biais très fort. Et c'est là qu'enfin je peux vous parler du travail réalisé par deux chercheurs de Bing, sur l'optimisation de l'entrelacement pour obtenir la meilleure qualité d'évaluation possible.

Ce travail a été publié dans les actes de la conférence WSDM 2013. Il s'agit de l'une des meilleures conférences du domaine de l'algorithmique des moteurs de recherche, et le travail dont je vous parle ici à obtenu le prix du meilleur article de la conférence. Cet article, le voici :

F. Radlinski and N. Craswell (2013). Optimized interleaving for online retrieval evaluation. Optimized interleaving for online retrieval evaluation. In Proceedings of WSDM 2013

Les auteurs identifient plusieurs propriétés nécessaires à un bon entrelacement :

  1. L'entrelacement est invisible à l'utilisateur : c'est à dire qu'il ne doit pas se rendre compte qu'il est un cobaye.
  2. L'entrelacement doit être robuste aux biais de l'utilisateur qui ne sont pas dépendants de la qualité du classement : par exemple il ne faut pas que des aspects d'ergonomie pousse à cliquer sur un résultat plutôt qu'un autre.
  3. L'entrelacement proposé ne doit pas modifier totalement l'expérience de recherche. Cette propriété peut être difficile à comprendre, mais elle est en fait assez simple. Si deux classements partagent certains documents, alors ils doivent apparaitre dans l'entrelacement. Si les deux classements commencent par les mêmes résultats, alors l'entrelacement commencera par ses documents. Et enfin, si un document A est avant un document B dans les deux classements, ce sera aussi le cas dans l'entrelacement.
  4. L'évaluation est positive. On évalue les améliorations, pas les dégradations.

Pour créer des entrelacement de ce type, les auteurs ont eu l'idée de travailler avec des préfixes. Ainsi chaque préfixe de l'entrelacement est constitué de l'entrelacement de préfixes des deux classements d'origine. Concrètement, cela veut dire que le résultat 1 de l'entrelacement est le résultat 1 du classement A ou du classement B. Puis que le résultat 2 de l'entrelacement est choisi parmi l'ensemble constitué des deux premiers de A et des deux premiers de B, etc.

Une deuxième idée est alors de créer une fonction de récompense sur le choix du meilleurs résultat : par exemple, si le résultat choisi comme étant le meilleur dans l'entrelacement était le 2 ème du classement A et le 4 ème du classement B, on va attribuer 2 points au classement A et seulement 1 au classement B. Cela permet de "récompenser" le classement d'origine le plus performant.

En utilisant ces deux notions (et d'autres, car les choses sont plus compliquées que les deux idées que je vous livre ici), les auteurs montrent comment créer des familles d'entrelacements qui permettent d'éviter les biais, pour obtenir une évaluation de la qualité des SERPs qui soit sincère et correcte.