Comment prédire un classement global à partir d’estimations locales ?
Daoud, Data Scientist & NLP specialist, partage son retour d’expérience sur l’élaboration d’un modèle de prédiction dans le domaine des résultats sportifs.
Il revient sur le cheminement mené, et nous montre comment des prédictions en apparence limitées et morcelées, lui ont permis d’approcher un résultat final. Soit dans ce cas, comment il est passé de la prédiction de résultats de duels au classement global d’une course de compétition.
Notre équipe d’experts Data, a eu l’occasion de s’engager sur un projet excitant. Ce projet à fort enjeu, avait pour particularité de comporter un grand volume de données et de porter sur un sujet rarement abordé en data science : les courses sportives !
L’objectif de ce projet était de développer un outil d’aide à la prise de paris sportifs, qui permette d’identifier les favoris et les outsiders d’une course donnée.
Comment ? En prédisant pour chaque coureur sa probabilité d’arriver à un rang donné.
Pour atteindre cet objectif, nous avions à notre disposition de nombreuses données concernant les coureurs (âge, palmarès, statistiques variées, …), mais aussi sur la course en elle-même (date et heure, température, nature de la piste, …).
Dans cet article, je vous dévoile la méthode mise au point par l’équipe Datawok pour obtenir des scores égalant ceux d’experts en prise de paris.
Notre objectif en termes de prédiction
L’objectif initial peut s’exprimer ainsi :
Étant donné les informations accumulées sur les coureurs participant à une course et les données sur la course elle-même (aussi appelée ‘événement’ dans cet article), sommes-nous capables de prédire pour chaque coureur, sa probabilité d’arriver à chaque rang du classement final ?
Plus formellement, soit :
- N le nombre initial de coureurs dans une course — cette valeur est variable,
- K le nombre de features (les variables utilisées pour faire une prédiction) qui décrivent un coureur — cette valeur est constante,
- G le nombre de features qui décrivent un événement— cette valeur est constante.
Le tableau suivant décrit par exemple les résultats de deux événements distincts.
Pour chaque coureur nous avons K=2 features (âge et palmarès — ‘Age’ & ‘Prizes won’ dans le tableau) and G=1 feature (longueur de la piste — ‘Track length’ dans le tableau).
En partant de ces résultats, deux solutions peuvent être envisagées :
- Étant donné toutes les features de tous les coureurs d’une même course et les features de l’événement, prédire une matrice de taille N,N où i,j est la probabilité que le coureur i termine au rang j.
- ou prédire une unique probabilité pour un couple coureur/rang.
Dans les deux cas, la question à se poser est :
Que considérons-nous comme une observation : une course ou l’arrivée d’un coureur à un rang donné ?
Premiers modèles prédictifs et premières limites
Les deux solutions présentent des limites :
- Dans le premier cas, les entrées et les sorties du modèle ont des formes et des tailles différentes en fonction de N (le nombre de coureurs) qui varie grandement d’une course à l’autre. Cela implique qu’un padding (le padding est l’ajout de données “neutres”, de remplissage, qui permettent à une donnée d’atteindre une certaine taille) devrait être appliqué sur les données d’entrée et de sortie pour conserver des tailles constantes. Cette solution implique aussi de devoir choisir un ordre — ici forcément arbitraire — pour représenter les données de tous les coureurs.
- À première vue le second cas semble plus simple : la taille des données d’entrée et de sortie est constante et ne dépend pas du nombre de coureurs de l’événement. Toutefois, la probabilité coureur/rang obtenue se fait sans information sur les autres coureurs. Une solution serait alors de calculer cette probabilité en intégrant des informations de tailles constantes sur tous les autres concurrents. Mais ces informations prendraient forcément la forme de données agrégées (moyennes, minimums et maximums des features des autres coureurs). Et hélas, représenter un ensemble de concurrents d’un coureur sur une course avec des agrégats n’est pas très précis.
Cela étant dit, nous savons maintenant que notre solution doit satisfaire les conditions suivantes :
- Les données d’entrée et de sortie doivent avoir des tailles et des formes constantes.
- La prédiction de la probabilité pour un couple coureur/rang doit être obtenue en prenant en compte les données des concurrents et de préférence sans recourir à de l’agrégation.
Prédiction de duels
Les solutions conventionnelles proposées précédemment sont en mesure de produire des résultats convenables, et ce malgré leurs limites. Mais nous avons voulu faire de cette mission une opportunité pour expérimenter un nouveau paradigme. Nous avons donc retenu la solution suivante :
Chaque événement peut-être considéré comme N*(N-1) duels entre tous les couples de concurrents (en distinguant un duel entre un concurrent A et un concurrent B d’un duel entre B et A). Un duel, donc la différence de rang entre un concurrent A et B à la fin d’une course, est donc maintenant notre observation (c’est donc l’objet de notre prédiction).
Chaque observation a donc maintenant une taille constante : K features pour décrire un premier coureur, K autres pour décrire un second, et finalement G features pour décrire l’événement en question. Enfin, la valeur à prédire est à présent la probabilité que le premier coureur perde face au second.
La possibilité de prédire l’ordre relatif de deux coureurs à la fin de la course, et ce pour tous les coureurs, nous permet d’estimer une matrice de taille N,N où i,j est la probabilité que le coureur i termine la course après le coureur j.
À l’inverse de la matrice précédemment mentionnée, nous n’estimons pas ici la probabilité sur des couples coureur/rang, mais plutôt la probabilité que le coureur i termine après le coureur j.
Ce nouveau paradigme a les propriétés suivantes :
- nous manipulons des données d’entrée de taille constante (et indépendantes de la valeur de N) et nous produisons des sorties de taille constante,
- nous produisons nos probabilités pour un couple de coureur, nous utilisons donc les features des deux compétiteurs (et non pas des agrégats, forcément imprécis)
Il faut garder en tête, qu’à ce stade une observation est n-uplet A,B,G,Y où :
- A représente les features d’un coureur,
- B représente les features d’un de ses concurrents,
- G représente les features de l’événement,
- Y est la valeur à prédire, soit 0 ou 1 selon que respectivement A perde face à B (cela équivaut à prédire si le rang final de A est supérieur au rang final de B).
La première course du tableau illustratif (où Event Id vaut 0) peut donc être représentée comme 12 duels (4 joueurs avec chacun 3 concurrents) et ainsi chaque duel devient une observation. Remarquez que cette méthode augmente artificiellement notre nombre d’observations : avec R courses et avec une moyenne de 10 coureurs par course, nous obtenons de l’ordre de R*100 observations.
La matrice des “duels” obtenue a typiquement cet aspect :
Encore une fois, chaque cellule de cette matrice (vert pour les valeurs élevées et jaune clair sinon), est la probabilité estimée par notre modèle ; la probabilité que le coureur i en ligne perde contre le coureur j en colonne. Le modèle n’est donc pas spécifiquement entraîné à prédire que f(A,B) = 1 -f(B,A), A et B représentant les coureurs et f(A,B) étant la probabilité que A perde face à B. Nous avons choisi d’utiliser la valeur (f(A,B) + 1-f(B,A))/2 (soit la moyenne des deux prédictions, A contre B et B contre A) comme notre estimation du résultat du duel entre A et B.
Pour résumer :
- Chaque course est constituée dans nos données initiales de N enregistrements (N lignes).
- Chaque enregistrement contient des données sur la course et un coureur. Chaque enregistrement contient aussi le rang d’arrivée final d’un coureur à cette course.
- Les enregistrements sont regroupés par course et chaque course de N coureur est transformée en N*(N-1) duels.
Pour illustrer notre démarche, cet exemple montre comment la première course donnée est représentée par un ensemble de duels :
C’est de cette façon que notre jeu de données a été construit. Partant de 11000 courses qui ont eu lieu entre 2017 et juillet 2018 nous avons produit 1 million d’observations — de duels donc — à partir desquelles nous avons pu entraîner nos modèles. Puis un autre demi-million d’observations a été produit, à partir de 5000 autres courses qui ont eu lieu entre juin 2018 et juin 2019, pour constituer le jeu de test de nos modèles.
Prédiction d‘ensemble
Nous avons dû faire beaucoup de feature engineering et de nettoyage de données au préalable.
Beaucoup des features de nos coureurs ont été calculées sur leurs performances avant une course donnée : nombre de fois où le coureur a été classé au rang 5 ou mieux sur les 12 derniers mois, nombre de disqualifications sur les 6 derniers mois, etc.
Cependant, cet article ayant pour principal sujet la représentation des données, nous ne présenterons pas toutes les étapes de notre travail de machine learning. Mais nous sommes bien passés par toutes les étapes typiques d’un projet de Data Science : compréhension métier du problème, modélisation, et enfin évaluation de nos modèles jusqu’à atteindre des résultats satisfaisants.
Nous avons finalement retenu un modèle de type XGBoost pour notre prédiction et la métrique utilisée est la précision (ou accuracy). Remarquez qu’un modèle prédisant de façon aléatoire pour un duel 0 ou 1 aurait une précision de 0.5, puisque pour chaque échantillon de A contre B ayant une valeur à prédire de 1, il existe un échantillon de B contre A avec une valeur à prédire de 0 (et inversement pour un duel A contre B avec une valeur de 0 à prédire). Cette remarque s’applique aussi à un modèle qui produirait une valeur constante comme prédiction.
En parlant de métrique… Atteindre un certain score en prédisant l’ordre d’arrivée correct d’une paire de coureurs ne répond pas encore tout à fait à notre objectif initial. Nous devons toujours trouver un moyen de produire la matrice coureur/rang souhaitée, en partant de ces prédictions de duels. Nous pouvons d’ores et déjà prédire l’issue de tous les duels d’une course. Et cela nous donne les probabilités pour un coureur donné d’être battu par tous les autres concurrents.
Nous pouvons par exemple obtenir le tableau suivant de probabilités, pour un coureur A d’être battu par ses concurrents à une course — la ième valeur étant la probabilité que A perde face au coureur i pour une course donnée. Partant de l’exemple précédent, voyons quelles sont les estimations produites par notre modèle pour le coureur John, arrivé premier à la course :
Nous pouvons à partir de là estimer la probabilité qu’a John d’arriver à chaque rang en simulant M fois chaque duel face à ces compétiteurs. En partant du tableau précédent, une simulation consisterait en trois nombres aléatoires choisis uniformément entre 0 et 1 (un par concurrent). Si la ième valeur aléatoire tirée est supérieure à la ième probabilité estimée, nous considérons que John gagne ce duel face à son concurrent. Être premier signifie par exemple ne perdre aucun duel (cela correspond au cas où aucune des valeurs tirées aléatoirement n’est inférieure aux probabilités prédites par le modèle). De la même façon, finir la course au rang n signifie perde exactement n-1 duels.
Toujours avec ce même exemple, nous pouvons faire une simulation en générant trois jeux de nombres aléatoires (3 valeurs, une par concurrent de John) et en comptant le nombre total de duels perdus pour cette course :
Dans cet exemple à 3 simulations, dans 67% des cas John atteint le premier rang (donc ne perd aucun de ses duels). Nous estimons aussi que dans 33% des cas, John finit deuxième. Ici M — le nombre de simulations par coureur — vaut 3. Dans nos expériences, nous avons retenu la valeur de M = 4000.
L’application de cette méthode de simulation à chaque coureur nous donne les lignes de la matrice souhaitée : chaque ligne représente un coureur et chaque colonne une probabilité d’arriver à un certain rang. Notez que la somme des probabilités en ligne de cette matrice est égale à 1 mais que cela n’est pas le cas en colonne.
Côté métier, cette matrice est utilisée pour produire des classements en ne retenant qu’un coureur par colonne (donc par rang) étant donné les probabilités estimées. Ainsi, plus la probabilité qu’a un coureur d’atteindre un rang donné est élevée, plus il est susceptible d’être retenu comme arrivant à ce rang dans notre estimation du classement final d’une course. Cela implique que nous devons normaliser la matrice obtenue en colonne — les probabilités de tous les coureurs d’arriver à un rang donné somment donc à 1.
La matrice suivante résulte de l’application de la méthode de simulation présentée plus haut à la première matrice présentée (la matrice de “duels”). Ainsi, dans la matrice suivante, la cellule i,j est la probabilité que le coureur i atteigne le rang j à la fin de la course :
Les résultats de notre modèle de prédiction
Le KPI utilisé mesure la capacité de notre algorithme à prédire correctement la présence de k coureurs parmi les n premiers rangs et ce pour différentes valeurs de k et de n. Nous savons qu’un score de 0.5 de précision peut être obtenu en proposant une probabilité aléatoire pour l’issue de chaque duel et que cela produirait un classement aléatoire pour une course après simulation. Nous savons aussi qu’un score de 1 de précision lors de la prédiction des issues des duels d’une course résulterait en un classement parfait d’une course après simulation. Entre ces deux valeurs extrêmes, nous ne disposons pas de façon d’estimer la qualité de nos classements à partir du seul score du modèle.
Comme nous l’avons dit en introduction, notre modèle est capable de produire des résultats égalant ceux d’experts en prise de paris (en termes de KPIs). Cela est d’autant plus fascinant que ces performances ont été obtenues avec un modèle qui avait un score de précision de… 0.65 pour la prédiction de duels ! N’est-ce pas surprenant ? Avec 35% de paires de coureurs mal classées nous obtenons malgré tout des résultats très satisfaisants ! Cela peut laisser penser qu’en effectuant plusieurs plus petites prédictions sur N*(N-1) duels pour une course plutôt que pour tout l’événement, nous répartissons l’erreur au lieu de la cumuler.
L’auteur
Data Scientist & NLP specialist
Nous publions régulièrement des articles sur des sujets de développement produit web et mobile, data et analytics, sécurité, cloud, hyperautomatisation et digital workplace.
Suivez-nous pour être notifié des prochains articles et réaliser votre veille professionnelle.
Retrouvez aussi nos publications et notre actualité via notre newsletter, ainsi que nos différents réseaux sociaux : LinkedIn, Twitter, Youtube, Twitch et Instagram
Vous souhaitez en savoir plus ? Consultez notre site web et nos offres d’emploi.
