Comment prouver que le classement Elo ou le classement de page ont une signification pour mon ensemble?

13

J'ai un ensemble de joueurs. Ils jouent les uns contre les autres (par paires). Les paires de joueurs sont choisies au hasard. Dans n'importe quel jeu, un joueur gagne et un autre perd. Les joueurs jouent entre eux un nombre limité de jeux (certains joueurs jouent plus, certains moins). Donc, j'ai des données (qui gagne contre qui et combien de fois). Maintenant, je suppose que chaque joueur a un classement qui détermine la probabilité de gagner.

Je veux vérifier si cette hypothèse est réellement la vérité. Bien sûr, je peux utiliser le système de notation Elo ou l' algorithme PageRank pour calculer la note de chaque joueur. Mais en calculant les cotes, je ne prouve pas qu'elles (cotes) existent réellement ou qu'elles signifient quelque chose.

En d'autres termes, je veux avoir un moyen de prouver (ou de vérifier) ​​que les joueurs ont des forces différentes. Comment puis-je le faire?

AJOUTÉE

Pour être plus précis, j'ai 8 joueurs et seulement 18 matchs. Donc, il y a beaucoup de paires de joueurs qui n'ont pas joué les uns contre les autres et il y a beaucoup de paires qui n'ont joué qu'une seule fois entre elles. Par conséquent, je ne peux pas estimer la probabilité d'une victoire pour une paire de joueurs donnée. Je vois aussi, par exemple, qu'il y a un joueur qui a gagné 6 fois en 6 matchs. Mais ce n'est peut-être qu'une coïncidence.

romain
la source
Voulez-vous tester l'hypothèse nulle que tous les joueurs ont la même force, ou vérifier l'ajustement d'un modèle de force de joueur?
2011 à
@onestop: Tous les joueurs ayant la même force seraient très improbables, non? Pourquoi suggérez-vous cela comme hypothèse?
endolith

Réponses:

10

Vous avez besoin d'un modèle de probabilité.

L'idée derrière un système de classement est qu'un numéro unique caractérise adéquatement la capacité d'un joueur. Nous pourrions appeler ce nombre leur «force» (parce que «rang» signifie déjà quelque chose de spécifique dans les statistiques). Nous prédisons que le joueur A battra le joueur B lorsque la force (A) dépasse la force (B). Mais cette affirmation est trop faible car (a) elle n'est pas quantitative et (b) elle ne tient pas compte de la possibilité qu'un joueur plus faible batte occasionnellement un joueur plus fort. Nous pouvons surmonter ces deux problèmes en supposant que la probabilité que A bat B ne dépend que de la différence de leurs forces. Si tel est le cas, alors nous pouvons ré-exprimer toutes les forces nécessaires pour que la différence de forces soit égale aux cotes logarithmiques d'une victoire.

Plus précisément, ce modèle est

logit(Pr(A beats B))=λAλB

où, par définition, est la cote du log et j'ai écrit λ Alogit(p)=log(p)log(1p)λUNE pour la force du joueur A, etc.

Ce modèle a autant de paramètres que de joueurs (mais il y a un degré de liberté en moins, car il ne peut identifier que les forces relatives , donc nous fixerions l'un des paramètres à une valeur arbitraire). C'est une sorte de modèle linéaire généralisé (dans la famille Binomiale, avec lien logit).

Les paramètres peuvent être estimés par Maximum de vraisemblance . La même théorie fournit un moyen d'ériger des intervalles de confiance autour des estimations des paramètres et de tester des hypothèses (par exemple, si le joueur le plus fort, selon les estimations, est significativement plus fort que le joueur le plus faible estimé).

Plus précisément, la probabilité d'un ensemble de jeux est le produit

tous les jeuxexp(λgagnant-λperdant)1+exp(λgagnant-λperdant).

Après avoir fixé la valeur de l'un des , les estimations des autres sont les valeurs qui maximisent cette probabilité. Ainsi, la variation de l'une quelconque des estimations réduit la probabilité de son maximum. S'il est trop réduit, il n'est pas cohérent avec les données. De cette façon, nous pouvons trouver des intervalles de confiance pour tous les paramètres: ce sont les limites dans lesquelles la variation des estimations ne diminue pas trop la probabilité logarithmique. Les hypothèses générales peuvent également être testées: une hypothèse contraint les forces (par exemple en supposant qu'elles sont toutes égales), cette contrainte limite l'ampleur de la probabilité, et si ce maximum restreint tombe trop loin du maximum réel, l'hypothèse est rejeté.λ


Dans ce problème particulier, il y a 18 jeux et 7 paramètres gratuits. En général, c'est trop de paramètres: il y a tellement de flexibilité que les paramètres peuvent varier assez librement sans beaucoup changer la probabilité maximale. Ainsi, l'application de la machine ML est susceptible de prouver l'évidence, c'est-à-dire qu'il n'y a probablement pas suffisamment de données pour avoir confiance dans les estimations de résistance.

whuber
la source
2
sA=exp(λA)ABsA/(sA+sB). (3) Si un tournoi à tour complet est joué (ce qui n'est pas le cas ici), le classement des forces coïncidera exactement avec le pourcentage de victoires de chaque joueur. (4) La qualité de l'ajustement est liée aux flux sur le graphique avec les joueurs comme nœuds et les jeux comme arêtes.
Cardinal
(suite) Lester R. Ford, Jr. a même publié un article sur un algorithme d'ajustement basé sur cette idée dans un Amer. Morceau mensuel de mathématiques de 1957 écrit en l'honneur de son père.
Cardinal
4

Si vous voulez tester l'hypothèse nulle selon laquelle chaque joueur est également susceptible de gagner ou de perdre chaque partie, je pense que vous voulez un test de symétrie du tableau de contingence formé en tabulant les gagnants contre les perdants.

Configurez les données de sorte que vous ayez deux variables, «gagnant» et «perdant» contenant l'ID du gagnant et du perdant pour chaque jeu, c'est-à-dire que chaque «observation» est un jeu. Vous pouvez ensuite construire une table de contingence du gagnant contre le perdant. Votre hypothèse nulle est que vous vous attendez à ce que ce tableau soit symétrique (en moyenne sur les tournois répétés). Dans votre cas, vous obtiendrez un tableau 8 × 8 où la plupart des entrées sont nulles (correspondant aux joueurs qui ne se sont jamais rencontrés), c'est-à-dire. le tableau sera très clairsemé, donc un test «exact» sera presque certainement nécessaire plutôt qu'un test reposant sur des asymptotiques.

Un tel test exact est disponible dans Stata avec la commande symétrie . Dans ce cas, la syntaxe serait:

symmetry winner loser, exact

Il est sans aucun doute également implémenté dans d'autres packages de statistiques que je connais moins bien.

un arrêt
la source
(+1) C'est drôle, je viens de réaliser que cette commande Stata pourrait être utilisée pour le test de transmission / déséquilibre en génétique :) J'ai discuté des packages R dans une réponse précédente, stats.stackexchange.com/questions/5171/… .
chl
En effet, le TDT est une application discutée dans l'aide Stata que j'ai liée ci-dessus. C'est aussi le contexte dans lequel j'ai rencontré ce test pour la première fois. Merci pour le lien vers ce Q précédent - on dirait que j'étais occupé avec d'autres Q quand il a été publié.
onestop
Bien que la question se réfère aux tests d'hypothèse, son choix est axé sur la question de la qualité de l'ajustement: une force numérique (scalaire) unique modélise-t-elle efficacement les résultats des matchs entre joueurs?
whuber
1

Avez-vous vérifié certaines des publications de Mark Glickman? Celles-ci semblent pertinentes. http://www.glicko.net/

La valeur attendue d'un jeu est implicite dans l'écart-type des notes. (Cet écart-type est fixé à un nombre spécifique dans Elo de base et variable dans le système Glicko). Je dis la valeur attendue plutôt que la probabilité d'une victoire à cause des tirages. Les éléments clés à comprendre concernant les notations Elo que vous avez sont l'hypothèse de distribution sous-jacente (normale ou logistique, par exemple) et l'écart-type supposé.

La version logistique des formules Elo suggère que la valeur attendue d'une différence de note de 110 points est de 0,653, par exemple le joueur A avec 1330 et le joueur B avec 1220.

http://en.wikipedia.org/wiki/Elo_rating_system (OK, c'est une référence Wikipedia mais j'ai déjà passé trop de temps sur cette réponse.)

Alors maintenant, nous avons une valeur attendue pour chaque jeu en fonction de la note de chaque joueur, et un résultat basé sur le jeu.

À ce stade, la prochaine chose que je ferais serait de vérifier cela graphiquement en organisant les écarts de bas en haut et en totalisant les résultats attendus et réels. Ainsi, pour les 5 premiers matchs, nous pourrions avoir un total de points de 2 et des points attendus de 1,5. Pour les 10 premiers matchs, nous pourrions avoir un total de points de 8 et des points attendus de 8,8, etc.

En faisant un graphique cumulatif de ces deux lignes (comme vous le feriez pour un test de Kolmogorov-Smirnov), vous pouvez voir si les valeurs cumulées attendues et réelles se suivent bien ou mal. Il est probable que quelqu'un d'autre puisse fournir un test plus formel.

zbicycliste
la source
1

L'exemple le plus célèbre pour tester la précision de la méthode d'estimation dans le système de notation est la notation des échecs - Elo contre la compétition Reste du monde sur Kaggle , dont la structure est la suivante:

Les concurrents entraînent leurs systèmes de notation à l'aide d'un ensemble de données d'entraînement de plus de 65 000 résultats récents pour 8 631 meilleurs joueurs. Les participants utilisent ensuite leur méthode pour prédire l'issue de 7 809 matchs supplémentaires.

Le gagnant était Elo ++ .

Cela semble être un bon schéma de test pour vos besoins, théoriquement, même si 18 correspondances ne sont pas une bonne base de test. Vous pouvez même vérifier les différences entre les résultats pour différents algorithmes (voici une comparaison entre Rankade , notre système de classement et les plus connus, notamment Elo , Glicko et Trueskill ).

Tomaso Neri
la source
0

Vous souhaitez tester l'hypothèse selon laquelle la probabilité d'un résultat dépend de la correspondance. H0, alors, c'est que chaque jeu est essentiellement un lancer de pièce.

Un test simple pour cela serait de calculer la proportion de fois que le joueur avec plus de jeux précédents gagnera, et de comparer cela à la fonction de distribution cumulative binomiale. Cela devrait montrer l'existence d'une sorte d'effet.

Si vous êtes intéressé par la qualité du système de notation Elo pour votre jeu, une méthode simple serait d'exécuter une validation croisée de 10 fois sur les performances prédictives du modèle Elo (qui suppose en fait que les résultats ne sont pas iid, mais je '' ll ignorer cela) et comparer cela à un lancer de pièce.

sesqu
la source
Pour être plus précis. J'ai 8 joueurs et seulement 18 matchs. Donc, il y a beaucoup de paires de joueurs qui ne jouent pas ensemble et il y a beaucoup de paires qui ne jouent qu’une seule. Par conséquent, je ne peux pas estimer la probabilité de gagner pour une paire de joueurs donnée. Je vois aussi, par exemple, qu'il y a un joueur qui a gagné 6 fois en 6 matchs. Mais peut-être que ce n'est qu'une coïncidence.
Roman