编者注，WOF世界等级分排名引用的其实是法国棋联的Emmanuel.Lazard先生计算后公布的排名，其他信息见楼下中文简析。
La cuisine du classement
Le classement utilisé par la FFO (classement européen) a été imaginé par le mathématicien Thomas Jech (American Mathematical Monthly, avril 1983). Il a été redécouvert par Thierry Bousch en 1988, par une approche tout à fait différente, ce qui semblerait prouver que sur le plan théorique, c'est ce système de classement qui est le plus naturel et qui possède le plus de bonnes propriétés. Thierry Bousch a décrit le classement dans un article de Fforum 12 (printemps 1989), que nous reprenons presque intégralement dans la présentation ci-dessous (les modifications, mineures, portent essentiellement sur le passage de la première personne à la troisième personne du singulier). Qu'est-ce qu'un système de classement ?Cela consiste à attribuer une "note" à chaque joueur, censée représenter sa "force". On convient également, parce que les écarts entre les joueurs peuvent être très grands, que l'échelle doit être logarithmique, si bien que la probabilité pour un joueur de gagner contre un autre ne dépend que de la différence entre leurs notes. Plus précisément, si i et j sont deux joueurs, alors la probabilité que i gagne contre j doit être Pij=f(Ei-Ej) où Ei et Ej sont les notes des joueurs, et f est une fonction de R dans ]0,1[ telle que f(x)+f(-x)=1 (puisque Pij+Pji=1), f(x)>=1/2 si x>=0, et f(x) tend vers 1 quand x tend vers +infini. Ceci montre que les notes ne sont définies qu'à une constante additive près, et qu'il faut calibrer l'ensemble des notes pour que, par exemple, la moyenne soit 1600 points. Difficultés d'un système de classementMais ceci montre également les difficultés de tout système de classement. Premièrement, les probabilités Pij sont inconnues ! En effet si l'on compte le nombre de paires de joueurs (i,j) qui ont joué au moins une partie ensemble, ce nombre est à peine inférieur au nombre total de parties. C'est-à-dire qu'en général deux joueurs ne jouent qu'une partie l'un contre l'autre, ou aucune. Si on dispose d'une seule partie pour estimer Pij, c'est bien maigre. Mais même si on disposait d'un très grand nombre de parties pour pouvoir estimer correctement les classements relatifs entre tous les joueurs, on aurait une autre difficulté : si n est le nombre de joueurs, on devrait résoudre n(n-1)/2 équations, alors que le nombre d'inconnues n'est que n-1. Dès que n est supérieur ou égal à 3, il y a plus d'équations que d'inconnues, et, la perfection n'étant pas de ce monde, ces équations ont toutes les chances d'être incompatibles. Un système de classement se doit donc de "concilier" ces équations qui ne pourront jamais être toutes vérifiées simultanément, de s'arranger pour que la plupart d'entre elles soient approximativement vérifiées. Choix de la transformationTout d'abord, nous devons choisir la fonction f. Pour des questions de comptabilité avec le système Elo, il faut qu'une différence de 200 points corresponde à trois chances contre une (i.e. f(200)=0.75)). Mais ceci n'est pas nécessaire pour la théorie, donc oublions-le. L'idée de T. Jech et de T. Bousch est que si la note est E, alors la "force" est exp(E). Donc si on a deux joueurs i et j, le rapport de forces est exp(Ei) chances pour i contre exp(Ej) chances pour j, donc Pij=exp(Ei)/(exp(Ei)+exp(Ej))=1/(1+exp(Ej-Ei)), ce qui conduit à choisir f(x)=1/(1+exp(-x)). Maintenant comment trouver les classements Ei ? C'est là que les chemins de T. Jech et de T. Bousch divergent. Regardons d'abord la première approche, celle de Jech. On a n joueurs, numérotés de 1 à n, ayant disputé un certain nombre de parties. Si i et j sont deux joueurs, soit Mij le nombre de parties jouées entre i et j. Soit Si le score du joueur i (c'est-à-dire le nombre de parties gagnées par i). Les inconnues seront les Ei : comme elles ne sont définies qu'à une constante additive près, il y a n-1 inconnues et pas n. A partir d'elles, définissons Pij=f(Ei-Ej). On devrait s'attendre à ce que le joueur i gagne MijPij parties contre j. Au total le score du joueur i devrait être Somme(j<>i,MijPij). Imposons alors que ce score estimé soit égal au score effectivement réalisé. On obtient donc n équations : Somme(j<>i,MijPij) = Si, pour tous les i variant de 1 à n. Mais en fait ces n équations sont liées par une relation, si bien qu'en fait il n'y a que n-1 équations indépendantes (en effet, si on fait la somme des n équations on obtient une relation qui est toujours vraie). Donc autant d'équations que d'inconnues. Jech a prouvé que si tous les joueurs sont comparables, alors ce système a une solution et une seule. Qu'est-ce que la comparabilité ?On dira que i est logiquement plus fort que j si i a gagné au moins une partie contre un joueur qui a gagné au moins une partie contre ... etc ... contre j. C'est la fermeture réflexive et transitive de la relation "a gagné contre". Et on dira que i et j sont comparables si i est logiquement plus fort que j et j est logiquement plus fort que i. La comparabilité est manifestement une relation d'équivalence, et si on considère le graphe (orienté) de la relation "a gagné contre" sur l'ensemble des joueurs, alors les composantes connexes de ce graphe sont exactement les classes d'équivalence de la relation de comparabilité. Maximum de vraisemblanceRevenons au calcul effectif des notes des joueurs. Nous avons vu l'approche de T. Jech. Celle de T. Bousch est une méthode bien connue des statisticiens sous le nom de méthode du maximum de vraisemblance. Elle consiste à chercher les valeurs des Ei pour lesquelles la probabilité que les parties jouées se terminent comme elles se sont terminées dans la réalité est maximale (pour illustrer cette méthode, donnons un autre exemple d'application : j'ai une pièce truquée; je l'ai lancée mille fois; elle est tombée 400 fois sur pile et 600 fois sur face, et je voudrais estimer la probabilité p qu'elle tombe du côté pile; l'estimateur le plus simple est celui de la moyenne, qui donne 0.4, mais la méthode du maximum de vraisemblance donne exactement le même résultat: la probabilité que la pièce tombe 400 fois sur pile et 600 fois sur face est maximale quand p=0.4). Soit donc V=(E1,...,En) avec E1=0 (par exemple) pour supprimer la dégénérescence par translation. Si les notes des joueurs (les Ek) sont connues, alors on peut calculer la probabilité que toutes les parties prises en compte se terminent comme elles se sont effectivement terminées. Par exemple, si i gagne contre j, la probabilité de cet événement est f(Ei-Ej). On admet que toutes les parties sont indépendantes, alors la probabilité totale est : P(V)=Produit(f(Ew(p) - El(p)), le produit étant effectué sur toutes les parties p, w(p) et l(p) désignant respectivement le gagnant et le perdant de la partie p. Le théorème de Bays nous dit que la densité de probabilité de V est proportionnelle à P(V). Il s'agit donc de savoir si la fonction P:R^(n-1)->R admet un ou plusieurs maxima, et où ? Or cela dépend essentiellement des propriétés du graphe des joueurs, muni des flèches "a gagné contre". Tout d'abord soit S = -log(P). Il est clair que S est partout définie, analytique au sens réel et strictement positive. Il est facile de voir - mais c'est essentiel - que S est convexe. Il est à peine plus difficile de voir que S est strictement convexe si et seulement si le graphe des joueurs est connexe; et dans ce cas, la dérivée seconde de S est partout définie positive. Il est moins facile de voir que S est propre (c'est-à-dire que S(V) tend vers l'infini quand norme(V) tend vers l'infini) si et seulement si le graphe des joueurs est connexe par arcs (i.e. tous les joueurs sont comparables). Par conséquent, S admet un minimum unique si et seulement si le graphe des joueurs est connexe par arcs (donc connexe), et quand cette hypothèse est vérifiée, le minimum de S (donc le maximum de P) est donné par grad(S)=0. Si on explicite les formules, cette condition donne - ô miracle ! - les équations de Jech. Intervalles de confianceMais il y a mieux. La fonction P représente une densité de probabilité, et il est donc intéressant de se demander dans quelle région se trouve concentrée, mettons, 90% de la probabilité, en d'autres termes trouver des intervalles de confiance pour les notes de joueurs. Au voisinage du maximum de probabilité, S'' est une forme quadratique définie positive, donc P est localement (et approximativement) une gaussienne. Quand on fait les calculs des approximations des écarts-types des Ek, on trouve que l'intervalle de confiance de la note d'un joueur dépend non seulement du nombre de parties jouées par ce joueur, mais aussi du nombre de parties équilibrées : plus je joue contre des adversaires "assez proches" de moi, plus mon classement est estimé correctement. DiscussionEncore quelques remarques théoriques sur le classement de Jech. Tout d'abord, il est clair que les composantes connexes du graphe des joueurs ne dépendent que des appariements. Ce qui est plus surprenant, c'est que les composantes connexes par arcs, c'est-à-dire les classes de joueurs comparables, ne dépendent que des appariements et des scores des joueurs. Supposons donc que les appariements et les scores soient tels que tous les joueurs sont comparables : alors les notes des joueurs sont entièrement déterminées par les appariements et les scores, à l'exclusion de tout autre critère. Comme pour le classement Elo. En d'autres termes, peu importe contre qui vous marquez des points : si vous gagnez contre un joueur fort et perdez contre un joueur faible ou le contraire, eh bien c'est pareil (pour vous du moins). De même, l'ordre des parties n'intervient pas. D'autre part, dans le cas d'un tournoi toutes rondes ou plusieurs fois toutes rondes, le classement de Jech et le classement du tournoi par score coïncident. Tous ces arguments concourants semblent prouver que le classement de Jech est la méthode la plus naturelle de notation des joueurs. Le problème, c'est la comparabilité : si on réfléchit un peu, on se rend compte que c'est une notion tout à fait naturelle (on ne pourra jamais comparer les martiens et les terriens à Othello, même si on a beaucoup de résultats de parties de martiens entre eux), mais que c'est également une obstruction qui empêche de classer tous les joueurs. Nous avons donc décidé de procéder ainsi : a) Chercher le joueur qui a joué le plus de parties. b) Prendre sa composante connexe par arcs et enlever tous les autres joueurs. C'est comme cela que l'on a le plus de chances de sélectionner la plus grande composante connexe par arcs. Dans la pratique, le joueur qui a joué le plus de parties, bien qu'il s'agisse souvent d'un bon joueur, est comparable avec pratiquement tous les autres joueurs - sauf bien sûr avec les joueurs qui ont gagné ou perdu toutes leurs parties, ou les joueurs d'une autre composante connexe. Prise en compte des tournoisLa totalité des tournois homologués par la FFO et où des joueurs membres de la FFO participent est prise en compte pour le calcul du classement, qui intègre également des tournois européens et américains (depuis peu). Seules les parties effectivement jouées en tournoi (ayant au moins 2 coups joués) comptent pour le classement. Les parties gagnées par forfait ne sont pas comptabilisées. Le calcul du classement est fait par un programme informatique suivant l'algorithme décrit ci-dessus. Toutes les parties jouées depuis 1992 sont prises en compte avec un poids dégressif, fonction de leur ancienneté :
Période 1 : 0 - 7 mois, poids 150
Période 2 : 7 - 14 mois, poids 100
Période 3 : 14 - 26 mois, poids 60
Période 4 : 26 - 38 mois, poids 30
Période 5 : toutes les parties plus anciennes, poids 1
Seuls les joueurs ayant disputé au moins une partie (prise en compte dans le classement) dans les 38 derniers mois apparaissent dans le classement publié.
PS de Thierry Bousch, 18 juin 2002 Bonjour Stéphane, En fait, comme je l'ai appris récemment, le classement "de Jech" est bien antérieur à l'article de Jech de 1983, et a été redécouvert par nombre de personnes, dont Jech, ainsi que ton serviteur. Il semble avoir été décrit pour la première fois dans un article d'Ernst Zermelo de 1929: E. Zermelo, Die Berechnung der Turnier-Ergebnisse als ein Maximumproblem der Wahrscheinlichkeitsrechnung, Math. Z. 29 (1929). Un article de revue de Michael Stob discute ce classement ainsi que les différentes approches qui y mènent; voici la fiche de MathSciNet a propos de cet article: Stob, Michael; A supplement to: "A mathematician's guide to popular sports" [Amer. Math. Monthly 90 (1983), no. 4, 246--266; MR 85i:05122a] by T. Jech. Amer. Math. Monthly 91 (1984), no. 5, 277--282. Jech's article is a nice piece of exposition of (unknown to him) an old problem which concludes with two real-life illustrations. He claims to have found the "one and only one correct way" of comparing teams according to their records even when their playing schedules are not identical. To this reviewer, the lack of any recognition and references of contributions to the ranking problem (there is not a single reference) is a serious scholarly flaw. For this ranking method is not new, as it has been discovered independently by, among others, E. Zermelo [Math. Z. 29 (1928), no. 2-3, 436--460], R. A. Bradley and M. E. Terry [Biometrika 39 (1952), 324--345; MR 17, 56], and L. R. Ford, Jr. [Amer. Math. Monthly 64 (1957), no. 8, part II, 28--33; MR 20 #4340]. Much is known about it and other ranking methods, so that Jech's claim has been challenged by some Amer. Math. Monthly readers, including Stob in the second paper under review. Stob's paper summarizes Jech's model and several other ranking models in a class of linear models including the classical Zermelo model, a model due to Mosteller, and the uniform model, and mentions ranking models based on axioms of choice behavior, on number and degree of upsets, and on transitivity. While Jech's model is different from Zermelo's model, both arrive at the same ranking procedure. Zermelo used a maximum likelihood argument while Jech made interesting use of Brouwer's fixed point theorem. Stob's valuable contribution is a summary of some of the debate over Jech's claims. Apparently not all reasonable people who consider the matter carefully are forced to accept Jech's multiplicative odds assumption. Stob points out that ranking schemes based on the linear model (such as Jech's, i.e. Zermelo's) are hypotheses about the probability distribution functions governing the playing out of the schedule. Morover, there are other reasonable candidates besides the method of Jech and that of maximum likelihood for methods of estimating parameters in a probabilistic model. As a concrete example, tennis is used by Stob to illustrate the difficulty of applying Zermelo's conception of relative strength or Jech's multiplicative odds to both the probabilities of winning sets and matches. (Reviewed by K. B. Reid) Mon commentaire à propos de ce commentaire: Stob et Reid sous-estiment l'originalité de l'article de Jech. Jech est le premier (à ma connaissance) à donner des équations qui ne soient pas basées sur la méthode du maximum de vraisemblance. Ceci est remarquable par deux aspects: premièrement, on retombe sur le classement de Zermelo; deuxièmement, la description donnée par Jech montre que le classement ne dépend que des appariements et des scores. Cela n'intéresse pas Stob, pour qui le point important est que le classement de Zermelo-Jech n'est qu'un classement particulier parmi tous ceux basés sur le principe du maximum de vraisemblance. Bizarrement, ces temps-ci je suis en train de travailler sur des choses qui ne sont pas sans rapport avec le classement de Zermelo-Jech. Thierry Bousch
|
窥视卡
雷达卡
发表于 2014-7-26 23:39:02
微信
收藏
淘帖
支持
反对
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
显身卡
楼主