Savez vous classer les choux ? Pardon, les Blogs ! (Part III/III)

Par Vicnent, dimanche 5 octobre 2008 à 13:55:39 :: Mathématiques :: permalien #1122

Troisième et dernière partie, l'algorithme de Fight-Blog !

En relisant les parties I/III et II/III (si si, faites le !), vous avez bien compris que l'un des paradigmes qui me gène le plus, c'est de dire que tel blog est meilleur que tel autre d'une part, et que parce que tel blog a trois navets et deux choux, alors il est devant tel autre.... Bref, ce n'est pas tant la relation d'ordre qui me gène que le classement fait "ainsi", même si Jean commence à tout lâcher sur les entrailles du classement Wikio (Partie I, Partie II). D'ailleurs, relisez les pages du top blog, on a classement, certes, mais un classement selon quels critères ou quelle méthode ? Quand vous observez le classement du foot ou du tennis, à une victoire est associée un certain nombre de points, sans tenir compte, en aucune façon de la notion de performance inhérente au résultat.

En effet, dire que le blog X est devant le blog Y, ou encore que le blog X est nième et le blog Y est n+1ième n'apporte aucune aucune information sur la qualité :

du blog X
du blog Y
du blog X par rapport au le blog Y
de l'évolution du blog X dans le temps

Pour faire simple, la carotte est un aliment moins gras que la noix, mais on ne sait pas si ces aliments sont peu gras tous les deux, très gras tous les deux, si l'un est très gras et l'autre encore plus ou encore si l'un l'est très peu et l'autre énormément.

Prenons des chiffres et 3 élèves A, B et C et prenons leurs classements en mathématiques sur trois années :

En 2006, A est premier, B est deuxième et C est troisième.
En 2007, A est toujours premier, B est toujours deuxième, et C est donc toujours troisième
En 2008, B passe en tête, A est deuxième, C est toujours dernier.

Que nous dit ce classement ? Ce classement nous dit que ... ben, il ne nous dit pas grand chose. Nous voulions un classement, nous l'avons mais il ne nous donne aucune autre information. Notamment, trois informations pourraient être intéressantes :

le premier a-t-il un bon niveau ? (on peut être premier de sa classe avec 04/20 de moyenne)
la différence de niveau entre deux classés (en 2006, A et B peuvent avoir tous les deux 04/20 et en 2007 11/20 ! ou tout à fait autre chose !)
l'évolution du niveau de A entre 2006 et 2007 (s'est il amélioré ? a-t-il chuté et tous les autres aussi ?)

Pour votre information, voila les notes !

2006 : A a 06/20, B a 05/20 et C a 04/20
2007 : A a 11/20, B a 10/20 et C a toujours 04/20
2008 : A a 12/20, B a 16/20 et C a 06/20

A la lumière de ces notes et du classement précédent, on peut constater pas mal de chose : C, tout d'abord, est mauvais, n'a que très peu progressé et, cependant, aurait été premier ex-aequo en 2006 ! B démarre à un niveau faible mais à force de travail, prend finalement la tête, le tout avec un bon niveau. Quant à A, il a été mauvais, il ne sera finalement au mieux que juste moyen. Des trois, il a quand même été deux fois premier, une fois deuxième. (Les mauvaises langues diront qu'il a bien commencé pour finir avant dernier

C'est donc assez clair : un classement, sans entraille ni modèle, ne vaut rien. Il ne représente rien et est complétement biaisé. (Pardon Pierre, mais rassure toi, j'ai déjà une immense estime pour (tout) ce que tu as déjà accompli et pour les récentes décisions que tu as prises... (d'où ma motivation à rentrer dans le wikio labs))

Ce qui suit se veut constructif : c'est toujours simple de dénoncer une situation, ce n'est pas toujours facile de dire pourquoi. Ca l'est clairement encore moins d'y remédier. Sauf à utiliser des yaka-focon

Ici, j'essaie simplement de proposer un modèle mathématique. Ce qu'on appelle aussi communément modéliser un problème. L'avantage d'utiliser un modèle est principalement que l'on va dégager des propriétés, ou inversement, les traduire dans le modèle. Ainsi, si un algorithme de classement doit apparaitre, les formules et les paramètres ne seront pas sortis de je-ne-sais-où. Le modèle que je propose pour les blogs est le suivant :

considérons que ces blogs sont en lutte pour la première place, la première place d'un classement de popularité thématique.
considérons qu'un blog n'a aucun moyen d'influencer son propre classement à travers les paramètres mesurés.

La première condition indique qu'on veut un classement, et qu'il est thématique. La deuxième condition indique que les paramètres pris en compte pour le classement d'un blog ne sont pas manipulables par le blog lui même. D'autre part, nous savons (et vous savez, puisque vous avez relu les parties I/III et II/III ) que les paramètres à mesurer doivent être mesurables, quantifiables et tout le toutim... Par exemple, les ... backlinks !

Une fois les bases posées, il reste à trouver l'algorithme. C'est parti.

Définition préliminaire : on nomme Probabilité de Fight Blog du blog X par rapport au blog Y la probabilité que le blog X soit meilleur que le Blog Y. On le note $P_f(B_x/B_y)$

Imaginons maintenant que nous ayons 3 blogs $B_x \text{, }B_y\text{ et }B_z$ : si $P_f(B_x/B_y)$ et si $P_f(B_y/B_z)$ alors $P_f(B_x/B_z) = P_f(B_x/B_y)\cdot P_f(B_y/B_z)$ En effet, cette égalité exprime le fait que les probabilités que le blog $B_x$ soit mieux classé que le blog $B_y$ et que le blog $B_y$ soit mieux classé que le blog $B_z$ sont indépendantes et qu'il existe néanmoins une relation entre $P_f(B_x/B_y)$ $P_f(B_y/B_z)$ et $P_f(B_x/B_z)$ . Cela permet également d'introduire une forme de relation de Chasles dans les propriétés du modèle qui va nous servir.

De même, $P_f(B_z/B_x) = P_f(B_z/B_y)\cdot P_f(B_y/B_x)$

Or, $P_f(B_x/B_z) = 1- P_f(B_z/B_x)$

Donc, $1- P_f(B_x/B_z) = (1-P_f(B_x/B_y))\cdot(1- P_f(B_y/B_z))$

Donc, $\frac{P_f(B_x/B_z)}{1- P_f(B_x/B_z)} = \frac{P_f(B_x/B_y) }{1-P_f(B_x/B_y)}\cdot\frac{P_f(B_y/B_z)}{1-P_f(B_y/B_z)}$

Prenons le logarithme népérien de l'expression en nous souvenant que $ln(a\cdot b) = ln(a) + ln(b)$ et que $ln(\frac{a}{b}) = ln(a) - ln(b)$

Nous obtenons $ln(\frac{P_f(B_x/B_z)}{1- P_f(B_x/B_z)}) = ln(\frac{P_f(B_x/B_y) }{1-P_f(B_x/B_y)})+ln(\frac{P_f(B_y/B_z)}{1-P_f(B_y/B_z)})$

Posons $D_{xy} = C \cdot ln(\frac{P_f(B_x/B_y)}{1- P_f(B_x/B_y)})$ : nous avons donc $D_{xz} = D_{xy} + D_{yz}$

Or, on peut également écrire $\frac{P_f(B_x/B_y)}{1-P_f(B_x/B_y)} = e^{(\frac{D_{xy}}{C})}$ en prenant la fonction inverse que nous pouvons désormais résoudre.

$\frac{P_f(B_x/B_y)}{1-P_f(B_x/B_y)} = H$ soit $P_f(B_x/B_y)= H \cdot (1-P_f(B_x/B_y))$ c'est à dire : $P_f(B_x/B_y)= \frac{1}{1+\frac{1}{H}}$

Donc $P_f(B_x/B_y)= \frac{1}{1+e^{(\frac{-D_{xy}}{C})}}$ qui est une fonction logistique

En différenciant la probabilité par rapport à la différence de points de classement, nous obtenons : $\frac{\partial P_f(B_x/B_y)}{\partial D_{xy}}= \frac{e^{-(\frac{D_{xy}}{C})}}{1+e^{-(\frac{D_{xy}}{C})}}$ au coefficient C près.

Concrétement, l'algorithme de Fight Blog va se présenter ainsi : Soient deux Blogs $B_x$ et $B_y$ dont on connait le classement en point de fight-blog (pfb). On connait donc, via leur différence de pfb la probabilité que l'un batte l'autre. A la bataille suivante, on calcule le résultat entre $B_x$ et $B_y$ et nous obtenons un nouveau résultat : si l'un ou l'autre fait mieux que le résultat attendu, son classement en point progresse. Cette progression est bien évidemment calculable. (et idem pour la baisse : quand l'un monte, l'autre baisse...). Enfin, en choisissant bien une valeur pour C, on peut réduire le calcul pour un blog en ne le faisant pas se battre contre toute la blogosphère mais contre un échantillon réduit, finement calculé. (L'idée est par exemple de ne pas considérer le résultat entre Federer et un joueur de cinquième série, tant le niveau est différent)

Exemple : comme indiqué ci dessus, si $B_x$ a actuellement 2235 pfb et $B_y$ a 2140 pfb, on s'attend, si ces deux blogs bataillent, à ce que que $B_x$ prenne 65% des liens de toute la blogosphère qui concernent uniquement $B_x$ et $B_y$ . Au mois suivant (ou à la période suivante), on s'aperçoit que $B_x$ ne prend plus que 61% des liens. Le niveau de $B_x$ a donc baissé. Cette baisse est exactement calculable.

Ce qui est vraiment intéressant avec ce modèle et cet algorithme, c'est que nous pourrons désormais :

voir évoluer le niveau d'un blog dans le temps. Je vous l'ai expliqué quelques paragraphes plus haut, on peut être en 2006 le premier de sa classe avec 07/20 puis être le dernier en 2008 avec 16/20 tout en ayant vu son niveau progresser.
comparer les classements des premiers dans le temps : le blog presse citron est premier du classement Top blog depuis 'n' mois, avant lui, c'était un autre : comment le niveau du premier du top blog a-t-il évolué dans le temps sur cette période ?
Aussi, il deviendra possible également de comparer le niveau entre le premier blog de cuisine et le premier blog de sport.
Enfin, les buzz seront également bien gérés : le fait qu'un billet "explose" pendant un mois fera bien évidemment progresser son classement, mais dans des proportions calculées par le modèle donc raisonnable du fait de l'échantillon : c'est la notion de performance ; si un blog vient à battre beaucoup de blogs du fait d'un billet par rapport à la performance attendue, ce n'est pas pour autant que le blog est devenu bien meilleur ou beaucoup plus populaire. Pour vous en convaincre, prenons l'exemple du classement au football : ce n'est pas parce que le dernier bat le premier sur un match que le dernier va se retrouver sur le podium du classement d'un coup. Et de mauvaise équipe, elle ne deviendra pas une bonne équipe pour autant. Cependant, cette performance est notable et est incontestablement meilleure que le troisième faisant un match nul avec le second. Cette notion de incontestablement meilleure sera également calculable. Pour prendre une autre image, nous saurons désormais calculer la vitesse moyenne d'un blog, et son accélération...

Alors, qu'en pensez vous ? Et Monsieur le conseiller scientifique ? Et Monsieur le directeur ?

Trackbacks

Aucun trackback.

Pour faire un tracback sur ce billet : http://www.vicnent.info/blog/tb.php?id=1122

Commentaires

1. Le lundi 6 octobre 2008 à 11:20:12, par Jean-Marie Le Ray

Clap, clap, clap ! Je n'ai rien compris (à l'algo), mais bravo.
Démonstration brillante, assez aisément compréhensible dans son raisonnement (contrairement au noyau dur de l'algo), quant à l'utilité de sa mise en oeuvre, le conseiller scientifique et le directeur sauront y répondre mieux que moi.
En tout cas je suis admiratif
Jean-Marie

2. Le lundi 6 octobre 2008 à 15:39:42, par pangloss

Pareil, je n'ai rien compris mais la au moins il y a de l'argument... Bravo!

3. Le lundi 6 octobre 2008 à 18:11:25, par Eric C.

Quand tu écris Pf(Bx/Bz) = Pf(Bx/By).Pf(By/Bz), je ne suis pas sûr d'être d'accord.

Je m'attendais un peu à celle là... Éric, peux tu développer ce qui te fait douter ? Pour ma part, prend une fonction de probabilité P dont on ne connait pas à priori les fonctions de densité et de répartition, puis posons que si Pf(Bx/By) est la probabilité que Bx soit plus "proriété" que By, alors Pf(Bx/By) existe, Pf(By/Bz) existe, et est indépendante de Pf(Bx/By). (jusque là OK ?)
Ensuite, Pf(Bx/bz) = C'est la probabilité que Bx soit plus "proriété" que Bz. En prenant comme hypothèse (vérifiée) que la propriété exprime une qualité de la relation d'ordre, la formule plus générale ne me choque pas. Par exemple, la probabilité que je sois devant toi est la probabilité que je sois devant X dont je connais la proabilité que X soit lui même devant toi. non ? (Ok, ça mériterait peut être plus de formalisme, mais bon, c'est un billet de blog, j'écris pas une publi non plus.)

Vicnent

4. Le lundi 6 octobre 2008 à 22:54:30, par Eric C.

Si je reprends ta métaphore sportive, Federer mène 9-8 dans ses face-à-face avec Nalbandian, et Nalbandian mène 2-0 dans ses f-a-f avec Nadal. On devrait donc s'attendre à ce que Rodgeur mène face à Rafa. Or il n'en est rien (12-6 pour l'espagnol).
Et la réponse "oui mais ce sont des rencontres sportives, c'est pas pareil" ne tient pas
Enfin tout dépend de la finesse de ton découpage thématique ...

"On devrait donc s'attendre à ce que Rodgeur mène face à Rafa." avec une certaine probabilité, dont la probabilité contraire n'est pas nulle... (et là, par exemple, le découpage thématique, ça pourrait être la surface....)
Vicnent

5. Le mardi 7 octobre 2008 à 08:08:18, par iBeer

merci pour cette belle démonstration, je vais l'appliquer!

6. Le mardi 7 octobre 2008 à 09:48:55, par Eric C.

Encore un petit lien sur le sujet (le net n'en manque pas de toute façon), qui pointe amha une des insuffisances de la méthode proposée par Jean : le "score" des billets effectuant un rétrolien sur le billet à évaluer n'est pas pris en compte
arxiv.org/abs/0810.0852

J'ai raté un billet chez Jean ou bien ? Il ne me semble pas que ce dernier propose une méthode. Mais de façon assez étonnante, la méthode actuellement employée par wikio n'est pas "si mauvaise". Dommage que les paramètres soient au doigt mouillés et non continus, mais la formule, il y a "de ça"
Vicnent

7. Le mardi 7 octobre 2008 à 11:03:56, par Eric C.

Non, j'ai essayé deux fois de repasser un commentaire mais ça n'a pas dû plaire à machinplemousse, me suis fait virer. Je disais que je n'avais pas encore lu son deuxième billet sur le classement wikio, où il expliquait que la "qualité" des liens était bien prise en compte. Mon commentaire est donc à oublier.

8. Le mardi 7 octobre 2008 à 11:06:14, par Eric C.

Pour faire suite à ça (www.vicnent.info/blog/ind... la probabilité contraire n'est certes pas nulle, mais elle ne représenterait pas correctement la hiérarchie observée.

Je ne comprends pas bien ce que tu veux dire : si je lance une pièce 6 fois, et que j'ai 6 piles, est ce que ça remet en question le fait que la probabilité à chaque lancer d'avoir pile ou face est 1/2 ?.
Effectivement, si A bat facilement B, qui bat facilement C qui lui même bat facilement A, alors, le modèle va certainement indiquer "au final" que les joueurs ont en gros le même niveau. C'est finalement assez logique du fait que si on fait un tournoi entre A, B et C et qu'ils jouent chacun 5 aller/retour entre eux, ils auront, à la fin, le même nombre de points. Il ne faut pas oublier que mon modèle prend en compte tous les résultats simultanément... Pense à la notion de "point fixe"...
Vicnent

9. Le mardi 7 octobre 2008 à 23:03:18, par Philippe

Hi Vicnent!

Tu as écrit : "Par exemple, la probabilité que je sois devant toi est la probabilité que je sois devant X dont je connais la proabilité que X soit lui même devant toi. non ?"

Mes notions de probas sont très réduites, je prends donc un exemple : soit une variable x qui vaut 10 à proba 1/2 et 5 à proba 1/2, une variable y qui vaut 7 à proba 1, enfin une variable z qui vaut 8 à proba 1/2 et 4 à proba 1/2. On tire indépendamment un x, un y et un z. Il y a quatre différents tirages possibles pour (x,y,z) : {(10,7,8),(10,7,4),(5,7,8),(5,7,4)}. On calcule les probas : P(x>z)=P(x=10 et y=8)+P(x=10 et y=4)+P(x=5 et z=4)=3/4. P(x>y)=P(x=10 et y=7)=1/2. P(y>z)=P(y=7 et z=4)=1/2. Et là c'est le drame, puisque 3/4=P(x>z) != P(x>y)P(y>z)=1/4. Est-ce que j'ai mal compris les conditions d'application de ta formule ?

En outre j'avoue avoir un peu de mal à repérer le problème que résout ton algorithme, et quelles données il utilise en entrée : ce score en pfb, dont tu donnes un exemple de 2235 et 2140 pfb, il est calculé comment ? Et quand tu dis que "cette baisse est exactement calculable", eh ben justement, j'aimerais bien avoir les détails du calcul, et son résultat notamment, pour comprendre comment l'algo fonctionne...

En tout cas, très sympa de voir "véroniser" une de mes lectures blogosphériques. A bientôt pour de prochaines expérimentations !

10. Le mercredi 8 octobre 2008 à 08:45:36, par Paul

Vicnent: moi c'est le coeur de l'approche probabiliste qui me gêne dans ce cas. L'hypothèse sous jacente est que le classement affiché est un tirage parmi tous les classements possibles, avec une certaine loi de probabilité.
En sous-jacent encore, l'hypothèse qu'il existe une qualité objective du blog (loi de proba inconnue) dont la perception sur un mois est à un nouveau une réalisation (ou un tirage).

Il me semble ahurissant de faire des probas avec aucun de ces objets, et encore plus de supposer qu'ils sont les mêmes !

11. Le mercredi 8 octobre 2008 à 10:00:32, par Vicnent

En gros, @Philippe, @Paul, vous êtes en train de me dire qu'il va falloir que j'écrive la partie IV/III ? (je vais vous répondre...)

12. Le mercredi 8 octobre 2008 à 11:15:44, par Christophe D.

Salut Vicnet,

Contrainte supplémentaire imposée par la section Oulipo du haut Conseil des commentateurs de blogs pour le billet IV : réussir à expliquer sans utiliser aucune formule mathématique (pour qu'on puisse tous comprendre

Par exemple, je suis assez d'accord sur la notion de vitesse et d'accélération mais je ne comprends pas en quoi ton modèle est plus pertinent que le nombre de liens (ou n'importe quel autre critère) mesuré sur une période définie (vitesse) et le nombre de place gagnées ou perdues dans le classement périodique qui en découle (accélération) ? Je me doute bien qu'il y a une finesse derrière ce modèle mais je ne comprends pas. Je n'arrive même pas à voir ou intervient la notion de temps dans ta démonstration ? Pourtant, tu écris à la fin de ton billet :

« prenons l'exemple du classement au football : ce n'est pas parce que le dernier bat le premier sur un match que le dernier va se retrouver sur le podium du classement d'un coup »

Il me semble que cela dépend avant tout de la période de mesure. Si le championnat se déroule sur 3 macths, une seule victoire peut propulser à la première place (Toulouse qui est le meilleur en ayant remporté ses 3 derniers matchs — oui, j'ai regardé les résultats du championnat pour écrire ce commentaire ) ; s'il se déroule sur les 32 derniers matchs, cela fera un peu de mouvement (Lyon qui est le meilleur) ; et si le classement est calculé sur les 1 000 derniers matchs, ça ne bougera presque pas (Marseille qui est le meilleur). La notion de « meilleur » dépend elle du niveau d'une équipe à un instant T (dans ce cas, il faut un classement élaboré sur une courte période, avec beaucoup de mouvement à prévoir chaque mois, un peu à l'inverse de ce que tu as écrit dans la citation ci-dessus) ou dépend elle du niveau de cette équipe sur les 9 derniers mois ? (dans ce cas, ne vaut il pas mieux publier un classement définitif… que tous les 9 mois, comme cela se fait dans le football d'ailleurs ? — entre temps, il ne s'agit que d'un classement provisoire.)

Bon, tu l'auras compris, ce sont avant tout les interrogations d'un lecteur qui ne comprend pas

13. Le mercredi 8 octobre 2008 à 14:07:00, par Paul

Vicnent: pour ajouter du grain à moudre au débat sur la question des probas...

Si p(A>B) = 50%
et p(B>C) = 50%

Donne la probabilité de chacun des situations suivantes...
A > B > C
A > C > B
B > A > C
B > C > A
C > B > A
C > A > B

Oui c'est dur....

14. Le mercredi 8 octobre 2008 à 14:08:18, par Paul

Vicnent : l'exemple ci dessus montre l'importance des densités de probabilité et donc l'explicitation de définir l'espace des possibles dans lequel tu te places, et quelles propriétés tu étudies.

:: Fil rss des commentaires de ce billet ::

Ajouter un commentaire

de 1 jusque 20, c'est Moi !

CKwaDonk ??

Last.Photo.En.Ligne

wtf ?

Avertissements d'usage, parce que vous le valez bien. Je, Vicnent, suis propriétaire et Auteur de ce Blog. En tant que propriétaire des lieux, je m'autorise à y mettre ce que je veux, mensonges éhontés ou par omission si je veux. En tant qu'Auteur, sachez que les droits d'auteur s'appliquent à toute oeuvre de l'esprit, quels qu'en soient le genre, la forme d'expression, le mérite ou la destination. Tout lecteur de ce blog doit en respecter les droits de propriété intellectuelle. Il doit notamment veiller à ne pas reproduire et diffuser les articles et contributions publiées sur ce blog sur d'autres blogs, forums ou d'autres supports sans mon accord. Tout lecteur peut néanmoins reproduire le contenu de ce blog à des fins de consultations privées ou reproduire et diffuser de courts extraits d'un article ou d'un message, à des fins d'information ou de recherches, en citant Blog de Vicnent (.|) comme Auteur de l'article ou du message. Une fonction spéciale permet même de faire des trackback vers chaque article. Vous allez rire, mais la fonction Trackback porte le nom Trackback. Déni de responsabilité : Les articles de ce blog résultent en général ou en particulier de la compilation d'informations en provenance de plusieurs sources et/ou d'expériences personnelles. Dans la mesure du possible, ils tentent de compiler une documentation exhaustive ou non dont les sources sont citées dans la mesure du possible ou non. Toute personne mettant en application ces renseignements le fait à ses propres risques. Je, Vicnent, n'assume aucune responsabilité des dommages susceptibles de résulter de l'usage de ces renseignements. En particulier toute décision concernant un traitement médical devrait toujours se prendre en consultation avec un professionnel de la santé qualifié, diplomé et compétent. Vous devriez également arrêter de fumer, passer votre permis moto, faire de parachutisme et ne jamais arrêtez de vous cultiver sinon, vous deviendrez xénophobe. Que vous ayez 18 ans ou plus m'est totalement égal, vous pouvez de toute façon sortir et/ou arrêter la lecture de ce blog quand bon vous semble. Votre avis reste de toute façon votre avis et quand parfois, je vois ce que je vois et j'entends ce que j'entends, je me dis que j'ai raison de penser ce que je pense. En dernier recours, vous pouvez aussi aller vous faire foutre. Bonnes lectures.

Vicnent (.|)