Classement Elo, algorithme EM
Classement Elo
Une projection des joueurs d’échecs sur $\mathbf{R}_+$ (leur score). Ça a été proposé par Arpad Elo il y a assez longtemps.
Aujourd’hui, c’est utilisé par des plateformes comme Codeforces ou HackerRank.
- La probabilité que A batte B ne dépend que de la différence de leurs scores.
- La logistique, c’est le fait d’avoir une sorte de multiplicité sur les produits de probabilité.
TrueSkill
Microsoft a fait une version maison pour la Xbox. Elle est copyrightée, mais :
- The Maths Behind TrueSkill
- trueskill.org est une suggestion d’implémentation Python
Maximum de vraisemblance et algorithme EM
À partir des résultats des matchs, on cherche à déterminer les scores Elo les plus vraisemblables, c’est-à-dire maximiser $Pr(ces scores Elo sachant ces données)$. C’est l’estimateur du maximum de vraisemblance.
En général, lorsqu’il est compliqué de déterminer les variables cachées sachant les variables observées, on utilise l’algorithme EM qui fait plusieurs itérations. Voici un tutorial clair, avec des illustrations.
Mais dans le cas d’Elo, c’est facile. La logistique étant facile à dériver, on peut obtenir une formule close. Ensuite, on en détermine simplement un zéro par la méthode de Newton qui converge quadratiquement. C’est expliqué sur ce blog, mais c’est un peu moche donc n’hésitez pas à le réécrire.
D’autres ressources
Scikit-learn
- http://scikit-learn.org/stable/modules/covariance.html
- http://scikit-learn.org/stable/auto_examples/covariance/plot_covariance_estimation.html
- http://scikit-learn.org/stable/modules/naive_bayes.html
- http://scikit-learn.org/stable/modules/generated/sklearn.decomposition.PCA.html
- http://scikit-learn.org/stable/modules/mixture.html#expectation-maximization
### Kaggle
- Finding Elo, une compétition qui consiste à prédire le score Elo de quelqu’un à partir du déroulé complet des matchs
- Ce qui est bien sur Kaggle, c’est que les gagnants s’expriment sur le forum