Traduction du brevet décrivant l'algorithme Panda

Les détails de cet algorithme, et comment il procède pour sélectionner les pages et les pénaliser sont entièrement décrits dans le brevet 8,682,892.

Ce document est une double traduction, en français d'une part, en langage clair d'autre part, du document soumis à l'USPTO et qui a obtenu son approbation, écrit lui en anglais et dans un sous-langage juridique où tout pronom est exclu et donc excessivement répétitif.

La méthode décrite dans le brevet s'applique uniquement aux pages sélectionnées pour répondre à une recherche et à pour but de modifier leur classement initial en fonction d'un facteur de modification s'appliquant à un site et déterminé par un ratio.

Le calcul de ce ratio consiste à décompter d'une part les liens indépendants vers les documents d'un site, d'autre part à décompter les requêtes de recherche conduisant aux documents constituant ce groupe, et sur la base de ces deux nombres, définir un facteur de modification à appliquer au score initial de chaque document, lequel dépend des autres critères de positionnement.
La méthode tend à pénaliser les sites dont l'essentiel du trafic vient du moteur de recherche parce que leurs webmasters maîtrisent mieux le référencement. Il favorise aussi les pages plus récentes qui ont plus de chance d'obtenir de nouveaux liens retours.

Le brevet 8,682,892, assigné à Google, dont les auteurs sont Navneet Panda et Vladimir Ofitserov, a été déposé le 28 septembre 2012 et accordé le 25 mars 2014.

Définition des termes employés

Ressource: Une page web, une image, un document textuel, un contenu multimedia, qui est présenté dans les résultats en réponse à une recherche.

Groupe de ressources: Le but étant d'attribuer un même score à un ensemble de ressources liées entre elles, et aussi d'évaluer d'indépendance des liens retours, on réunit les ressources en groupes. Il peut s'agir d'un domaine ou d'un sous-domaine, ou d'un ensemble de domaines appartenant au même propriétaire.

Pluralité de groupes de ressources: Ensemble des groupes concernés par une recherche (plus ou moins des sites) et considérés comme distincts et indépendants les uns des autres.

Liens indépendants: Le but étant d'utiliser les liens d'une page vers une ressource pour juger de l'intérêt de celle-ci, on identifie comme indépendants les liens provenant de groupes de ressources différents du groupe de ressource cible.

Facteur de modification : On attribue à un groupe un facteur qui modifie la position dans les résultats au groupe, par rapport au score de positionnement dépendant de la pertinence et autres signaux, et ce même facteur s'applique à toutes les ressources d'un groupe. Donc on pénalise selon le même facteur toutes les pages d'un site avant de les positionner.

Facteur de modification normalisé. Après avoir calculé un facteur de modification pour un groupe (ce peut être un site), ce facteur est ajusté en fonction de l'ensemble des groupes appartenant à une même partition.

Requête de référence: C'est une requête qui mène à une ressource dans un groupe et par un utilisateur unique. Pour être de référence il faut qu'elle soit faite par un utilisateur qui n'a pas fait de recherche antérieure conduisant à d'autres ressources du même groupe. L'utilisateur est identifié par l'ID ou les cookies.
Ces requêtes participent au calcul du facteur de modification, donc de la pénalité panda.

Requête de navigation: Certaines requêtes de recherche sont jugées de navigation par l'utilisateur quand elles sont faites pour trouver un site en particulier ou une page spécifique. Cela est déterminé par des données stockées par le moteur de recherche qui identifient ce type de requêtes.

Ce qui est revendiqué est:

Une méthode mise en oeuvre par un ou plusieurs ordinateurs, qui comprend le fait de déterminer,
- pour chacun dans une pluralité de groupes de ressources, un décompte respectif des liens entrants vers les ressources dans le groupe,
- pour chacun dans une pluralité de groupes de ressource un décompte respectif des requêtes de référence;
Déterminer
- pour chacun dans une pluralité de groupes de ressources un facteur de modification respectif aux groupes de ressources,
- alors que le score en question est basé sur le décompte des liens indépendants et le décompte des requêtes de référence pour le groupe;
et associer
- avec chacun dans une pluralité de groupes de ressources, le facteur de modification pour le groupe
- alors que la modification respective propre au groupe modifie le score initial généré pour les ressources dans le groupe, en réponse aux requêtes de recherche reçues.
Selon cette méthode, on reçoit une requête provenant d'un utilisateur; on dispose de données sur une pluralité de ressources avec leur score de positionnement initial pour chaque ressource; on identifie un groupe de ressource pour chacune; on ajuste le score initial de chaque ressource en fonction d'un facteur de modification qui s'applique au groupe dont elle fait partie. Cela génère un nouveau score.
On utilise le nouveau score pour générer un score de positionnement pour chaque ressource. On présente les résultats à l'utilisateur en fonction du nouveau score.
On fait d'autres ajustements au classement avant de présenter le résultat.
On distingue un groupe de ressources sur la base de de chaque URL de ressources disponible dans l'index.
Pour ajuster le score initial avec le facteur de modification, il faut définir un facteur de modification spécifique à chaque ressource basé sur celui du groupe.
Pour ajuster le score initial de chaque ressource, on le multiplie par le facteur de modification qui la concerne.
Quand on génère un facteur de modification spécifique pour une première ressource de résultat de recherche, on détermine si c'est une requête de navigation. Dans ce cas le score initial n'est pas modifié.
Quand on détermine le facteur de modification pour une ressource qui est le premier résultat de recherche, déterminer que ce n'est pas une requête de navigation.
Déterminer que la valeur du score initial d'une première ressource de résultat de recherche ne dépasse pas un premier seuil. Et s'il le dépasse, générer un facteur de modification pour cette ressource qui ne change pas le score initial.
Quand on génère un facteur de modification pour une seconde ressource de résultat de recherche, on détermine que le score initial excède la valeur d'un premier pallier mais n'excède pas celle d'un second et plus haut palier. Si T.sub.1 est le premier pallier, IS est le score initial, M est le facteur de modification du groupe, la formule pour déterminer le facteur de modification f.sub.1 pour la ressource est:
```
f.sub.1 = T.sub.1 + ( IS - T.sub.1) M / IS 
```
Quand on génère un facteur de modification spécifique à la troisième ressource des résultats de recherche: on détermine que le score initial dépasse la valeur du second palier; et on génère un facteur de modification f.sub.2 tel que:
```
f.sub.2 = f.sub.3 / log.sub.T.sub.2 (IS) g(f.sub.3)
```
ou T.sub.2 est la valeur du second pallier,
f.sub.3 est le facteur de modification initial spécifique à la ressource,
et g(f.sub.3) est une fonction d'adoucissement qui réduit l'effet du facteur de modification pour des intervalles de valeur particuliers du facteur de modification initial.
On évalue f.sub.3 selon la formule suivante:
```
f.sub.3 = T.sub.1 + (IS-T.sub.1) M / IS
```
ou T.sub.1 est la valeur du premier palier, IS est le score initial, M est le facteur de modification pour le groupe.
La fonction d'adoucissement est définie comme:
```
g(f.sub.3)=1,
if f.sub.3.ltoreq.Q and g(f.sub.3) = (1-f.sub.3)/1-P,
if f.sub.3 > Q
```
où Q est la valeur de palier prédéterminée.
Le procédé en 1 spécifie quand un lien indépendant pour un groupe de ressource est un lien provenant d'une ressource source vers une ressource cible, où la cible est incluse dans un groupe particulier, et ou la source et la cible ont été déterminés comme étant indépendants.
Pour déterminer en 15 que la source et la cible sont indépendants, on détermine qu'ils sont inclus dans des groupes de ressources différents.
Le procédé en 15, comprend de déterminer que le groupe source et le groupe cible n'ont aucune chance d'être en relation.
Le procédé en 15, comprend de déterminer que la ressource source n'a aucune chance d'être un duplicata de la ressource cible.
Selon le procédé en 1 une recherche de référence pour un groupe de ressources particulier est une requête de recherche soumise auparavant qui a été classée comme concernant une ressource dans ce groupe.
Le procédé en 19 comprend de déterminer que la requête précédemment soumise inclut un ou plusieurs termes dont il a été déterminé qu'ils concernent la ressource dans le groupe.
Le procédé en 1 où on détermine le facteur de modification pour le groupe comprend: déterminer un facteur de modification initial pour le groupe, qui est un ratio du nombre de liens indépendants comptés pour le groupe sur le nombre de requêtes de références comptées pour le groupe.
Le procédé en 21, concernant un groupe de ressources particulier, comprend: partitionner la pluralité de groupes de ressource en pluralité de partitions basée sur les comptes respectifs de requêtes de référence;
et déterminer un facteur de modification normalisé pour le groupe particulier en normalisant son facteur initial en se basant sur le facteur de normalisation initial des groupes dans la même partition.
Le système comprend: déterminer pour chacun dans une pluralité de groupes de ressources, un décompte respectif des liens entrants indépendants vers les ressources du groupe. Déterminer pour chacun un décompte respectif des requêtes de référence. Déterminer pour chacun un facteur de modification propre au groupe, tel qu'il soit basé sur le décompte des liens indépendants et et décompte des requêtes de référence, et associer avec chacun dans une pluralité de groupes de ressources, le facteur de modification propre au groupe, de sorte que ce facteur modifie les scores initiaux des ressources du groupe.
Le système selon 23 donc recoit une première requête de recherche de la part d'un utilisateur, reçoit des données identifiant une pluralité de ressources de résultats de recherche avec leur score initial pour chacune, identifie les groupes de ressource auxquels chacune appartient, et ajuste le score initial selon le facteur de modification du groupe, afin de générer un nouveau score.
Le système selon 24 utilise le nouveau score obtenu pour classer les ressources répondant à la requête, et afficher les résultats en fonction de ces scores de positionnement.
Le système selon 25 effectue d'autres ajustements aux scores de positionnements obtenus avant d'afficher les résultats.
Le système selon 23 dans lequel on identifie les liens entre une source et une cible et détermine que la source et la cible sont indépendants.
Le système selon 27, dans lequel on détermine que la source et la cible sont indépendants détermine que la ressource source et cible appartiennent à des groupes de ressources différents.
Le système selon 27 détermine que le groupe source et cible ne sont pas en relation.
Le système selon 27 dans lequel on détermine l'indépendance des groupes détermine que la ressource source a peu de chance d'être un duplicata de la cible.
Le système selon 23 dans lequel une requête de référence pour un groupe de ressources est une requête soumise auparavant pour une ressource considérée comme appartenant à ce groupe.
Le système selon la revendication 31, dans lequel on identifie une requête de référence en ce qu'elle contient un terme ou plus concernant la ressource.
Le système selon 23 où on détermine le facteur de modification du groupe détermine un facteur de modification initial qui est le ratio du nombre de liens indépendants compté pour ce groupe, sur le nombre de requête de références compté pour ce groupe.
Le système selon 33 partitionne la pluralité de groupes de ressources en une pluralité de partitions en se basant sur leur décompte de requête de référence respectifs; et détermine un facteur de modification normalisé pour le groupe en normalisant le facteur initial d'après le facteur des groupes de ressources dans la partition à laquelle il appartient.
(De 35 à 46, on précise le fait que toutes les étapes précédemment décrites sont exécutées par un ordinateur. Comme le langage juridique ignore les pronoms on reprend chaque revendication en précisant qu'elle est mise en oeuvre par une machine...)

Description

FOND

Cette spécification concerne le classement de résultats pour des requêtes de recherche soumise à un moteur de recherche sur Internet.

Les moteurs de recherche ont pour but d'identifier des ressources, autrement dit des pages web, images, documents textuels, contenu multimedia qui sont pertinents pour les besoins de l'utilisateur et de présenter l'information concernant les ressources de la manière la plus utile à l'utilisateur. Les moteurs de recherche Internet généralement retournent un ensemble de résultats de recherche, dont chacun identifie une ressource, en réponse à une requête soumise par un utilisateur.

SOMMAIRE

(Le sommaire reprend les points précédemment exposés dans la revendication.)

La matière du sujet décrit dans la spécification est implémentée pour réaliser au moins un des avantages suivants:

Les résultats de recherche identifiant des ressources de basse qualité peuvent être déclassés dans l'ordre de présentation des résultats répondant à une recherche.
Donc l'expérience de l'utilisateur peut être améliorée parce que les résultats mieux classés répondent mieux à son besoin d'information.

BREVE DECRIPTION DES DESSINS

FIG. 1 montre un exemple de système de recherche.

FIG. 2 est un ordinogramme d'un exemple de processus pour ajuster un score initial d'une ressource identifée par le système de recherche pour une requête de recherche reçue.

FIG. 3 est un ordinogramme d'un exemple de processus pour déterminer un facteur de modification pour un groupe de ressources.

FIG. 4 est un ordinogramme d'un exemple de processus pour déterminer les facteurs de modification normalisés pour les groupes de ressources.

FIG. 5 est un ordinogramme d'un exemple de processus pour générer un facteur de modification spécifique à une ressource.

Tels numéros de référence et désignation dans les différents dessins indiquent tels éléments.

DESCRIPTION DETAILLEE

(Le détail reprend des points sur la mise en oeuvre de la méthode exposée qui n'intéresseront que les avocats dans le cadre d'un procès. On ne reprend pas ces points dans cette traduction qui s'adresse aux webmasters. Mais il donne aussi des précisions supplémentaires que nous traduisons ci-dessous.)

La figure 1 montre un exemple de système de recherche, numéro 114. C'est un exemple de système pour retrouver une information implémenté en programme informatique sur un ou plusieurs ordinateurs en un ou plusieurs endroits.

Dans certains cas, le système de recherche 114 peut être implémenté sur l'appareil de l'utilisateur 104, par exemple, si l'utilisateur installe une application qui effectue des recherches pour l'appareil de l'utilisateur.

Un groupe de ressources est une portion des ressources d'Internet. Un groupe peut être de façons variées. Un groupe de ressources basée sur l'adresse est défini par l'URL des ressources du groupe.
Les ressources sont groupées de sorte qu'aucune n'appartionne à plus d'un groupe. Par exemple, un groupe peut inclure toutes les ressources qui peuvent être accédées en utilisant un nom de domaine. Ainsi, le groupe peut inclure http://www.domaine.com/ressource1, http://www.domaine.com/ressource2, etc... sans considération du moment où les ressources deviennent accessible au moteur de recherche pour leur indexation.
Alternativement un groupe de ressources peut inclure chaque ressource qui puisse être accédée par un nom d'hôte particulier sous la forme http://hôte.example.com/ressourceX. (NDT: sous-domaine).
D'autres regroupement basés sur l'adresse sont possibles. On peut utiliser seulement une partie des ressources d'un domaine ou d'un sous-domaine.
Alternativement, un groupe de ressource peut inclure plusieurs domaines ou sous-domaines.

La figure 2 est un ordinogramme d'un exemple de processus (no 200) pour ajuster un score initial d'une ressource.

Le système reçoit des données identifiant une ressource et son score initial. Le score initial d'une ressource (avant Panda, NDT), peut être la mesure de pertinence de la ressource par rapport à la requête, une mesure de qualité de la ressource, ou les deux.

Le système identifie le groupe de ressource basé sur l'adresse auquel la ressource appartient (204) en se basant sur l'URL. Le group peut partager le même domaine our le même hébergement.
Il accède aux données de facteurs de modification (206). Une base de données stocke les facteurs de modification pour tous les groupes.

Le sytème génére un facteur de modification spécifique à le ressource (208). Généralement le système peut ajuster le facteur de modification du groupe sur la base d'un ou plusieurs paramètres spécifiques à la requête pour le générer.

Le système applique le facteur de modification spécifique au score initial (210). Le facteur de modification spécifique à une ressource peut être un facteur de multiplication appliqué au score initial pour générer un score modifié. (NdT: aucune autre méthode n'étant précisée, le "peut" semble être un "est").

La figure 3 est un ordinogramme d'un exemple de processus (300) pour déterminer un facteur de modification pour un groupe de ressources. Il est accompli pour chacun des groupes dans un ensemble.

Le système décompte les liens indépendant pour le groupe (302). Un lien pour un groupe de ressources est un lien entrant vers une ressource du groupe, donc qui est la cible. Les liens peuvent inclure des hyperliens ou des liens implicites. Un lien implicite est une référence à une ressource cible sans hyperlien, et que l'utilisateur ne peut suivre.

Un lien est considéré indépendant si la source et la cible appartiennent à des groupes différents.

Le système peut avoir accès à des données qui indiquent que des groupes de ressource ont des chances d'être en relation. Parce qu'ils sont possédés par la même entité, hébergés par la même entité, ou créés par la même entité. Dans ce cas le système estime que les ressources des deux groupes ne sont pas indépendantes.

Autre exemple, le système peut avoir accès à des données qui indiquent comment deux ressources sont similaires sur un ou plusieurs aspects, donc ont un contenu, des images, un format, une feuille de style etc... identiques ou similaires. Si les données indiquent que les deux ressources sont suffisamment semblables, il conclut qu'elles ne sont pas indépendantes.

Eventuellement, le système calcule un score d'indépendance à partir des valeurs des attributs considérés pour une paire de ressources, et les classe comme indépendantes si le score satisfait un critère.

Eventuellement le système compte un lien au plus à partir de chaque ressource dans chaque groupe pointant vers un groupe cible. Dans d'autres cas si plus d'un lien est identifié dans les ressources d'une groupe source vers les ressources du groupe cible, le nombre de liens indépendants compté pour le groupe cible peut être une fonction du nombre total de liens indépendants. Le nombre total de liens indépendants peut être le nombre total trouvé dans les ressources. Il peut être un logarithme de ce nombre. Ou une autre fonction de ce nombre.

Une requête est considérée comme référant à une ressource selon un terme reconnu qu'elle contient. Ce terme peut être l'URL ou une partie de l'URL. Par exemple "example.com". Autre exemple, si les données indiquent que "example sf" et "esf" sont couramment utilisés par les internautes pour référer à la ressource dont l'URL est "http://www.example.com", les requêtes contenant ces termes comme "example sf news" et "esf restaurant reviews" sont comptés comme des requêtes de référence pour le groupe qui inclut la ressource dont l'URL est "http://www.example.com".

Une requête de navigation peut aussi considérée comme référant à une ressource. Il s'agit d'une requête soumise pour obtenir un site ou une page en particulier (plutôt qu'une liste de résultats, NdT). Le système l'évalue à partir d'une base de données qui enregistre ce genre de requêtes.

Dans certaines implémentations, le système compte comme requêtes de référence pour un groupe seulement les requêtes soumises par des utilisateurs uniques. Donc s'ils n'ont pas déjà soumis des requêtes pour des ressources du même groupe. Le système identifie les utilisateurs par les moyens conventionnels tels que cookies, login d'identification. Cela peut s'appliquer sur une période limitée ou non.

Le facteur de modification peut être le ratio du nombre de liens indépendants vers le groupe sur le nombre de requêtes de références pour le groupe. Donc selon la formule:

M = IL / RQ

où M est le facteur de modification, IL le nombre de liens indépendants, RQ le nombre de requêtes de références.

Dans certaines implémentations, au lieu de stocker le facteur de modification pour un groupe, on normalise ce facteur et l'on stocke le facteur normalisé.

La figure 4 est un ordinogramme d'un exemple de processus (no 400) pour déterminer les facteurs de modification normalisés pour les groupes de ressources.

Le système peut partitionner les groupes de ressources (402) sur la base du décompte des requêtes de références de sorte que chaque partition inclut les groupes de ressources dont le décompte se situe dans un intervalle.
Pour ce faire, le système peut ne comparer les facteurs de modification qu'entre les groupes ayants des décomptes de requêtes de références similaires.

Pour chaque groupe dans une partition, le système normalise le facteur de modification (404) sur la base de ceux des autres groupes de la partition. Par exemple, il peut calculer une mesure statistique des facteurs. Par exemple, cette mesure peut être la tendance centrale, comme la moyenne arithmétique, géométrique ou harmonique, la médiane, la valeur dominante, etc...
Ou encore la mesure statistique peut être le facteur de modification minimal ou maximal.
Le facteur de modification normalisé NM pour un groupe donné dans une partition peut être exprimé comme:

NM = M - m / m

où M est le facteur de modification pour le groupe et m la mesure statistique.

La figure 5 est un ordinogramme d'un exemple de processus (no 500) pour générer un facteur de modification spécifique à une ressource. Le processus 500 peut être accompli pour chacune des ressources en réponse à une requête reçue d'un utilisateur.

Quand il reçoit une requête de navigation vers une ressource, le système assigne au facteur de modification une valeur qui n'affecte pas le score initial de la ressource concernée.

Sinon le système détermine si le score initial est sous la valeur d'un premier palier. Si c'est le cas, le facteur de modification est altéré de façon à ne pas changer le score initial.

Si le score initial n'est pas sous le premier palier, le système détermine s'il se situe sous un second palier plus élevé. Si c'est le cas le système détermine un premier facteur de modification à appliquer au score initial.
Par exemple, si le facteur de modification est multiplicatif, le premier facteur f.sub.1 peut être exprimé comme:

f.sub.1 = T.sub.1 + (IS - T.sub.1)M / IS

où T.sub.1 est la valeur du premier palier, IS est le score initial, et M le facteur de modification pour le groupe de ressources. Donc un facteur de modification qui baisse d'autant plus que le score initial augmente.

Si le score initial n'est pas sous le second palier, le système génère un second facteur de modification à lui appliquer. Il peut être basé sur le premier.
Par exemple, si le FM est multiplicatif, le second facteur f.sub.2 peut être exprimé comme:

f.sub.2 = f.sub.1 / log.sub.T.sub.2(IS)g(f.sub.1)

où T.sub.2 est la valeur du second palier, et g(f.sub.1) est une fonction d'adoucissement qui réduit l'effet du second FM sur IS pour des intervalles particuliers du premier FM.
Par example, la fonction d'adoucissement peut être définie de sorte que, si le premier FM dépasse un palier, le second FM quand il est appliqué au score initial à un effet amoindri pour ne pas avoir d'effet sur la valeur du score initial.
Dans certaines implémentation, la fonction d'adoucissement est définie comme une fonction morcelée telle que:

g(f.sub.1)=1, 
if f.sub.1.ltoreq.Q and g(f.sub.1)=(1-f.sub.1)/1-P, 
if f.sub.1>Q

où Q est une valeur de palier prédéterminée. Dans ces implémentation, si la valeur de log.sub.T.sub.2(IS)g(f.sub.1) est inférieure à 1 donc si f.sub.1 est égale à un et donc le produit égal à zéro, le système peut faire quef.sub.2 soit égale à f.sub.1 pour éviter que la valeur de f.sub.2 ne soit plus grande que f.sub.1 ou que f.sub.2 ne soit indéfini.

(Les paragraphes qui suivent sont destinés à inclure les termes juridiques nécessaires à l'application du brevet, en précisant le matériel sur lequel la méthode est implémentée. Ils sont donc ignorés.)

Commentaires

Tout cela peut se définir comme un perfectionnement du PageRank et on est assez loin des critères de qualité donnés par Google. Il ne s'agit que des backlinks de sources différentes et des recherches par des utilisateurs différents, formant un ratio pour déterminer la qualité du site! Tout cela mis dans une formule mathématique qui laisse place à beaucoup d'approximation et qui déclasse notamment les pages contenant des réponses très précises mais sur des sites peu connus. La popularité d'un site est supposée être un facteur de qualité et elle est supposée s'étendre à toutes les pages et toutes les "ressources" du site...

Traduit et déposé par Denis Sureau le 31 mars 2014. Toute reproduction est interdite sur un autre site Web, mais autorisée sous forme imprimée.