Learning to Rank

Comme nous l’avons vu précédemment, les outils de classification supervisée tels que SVM et les réseaux de neurones fournissent des performances intéressantes, mais cette approche a ses limites.
En effet les chevaux sont classés par rapport à leurs features, sans se soucier des autres chevaux présents dans la course. On peut prédire ainsi plusieurs gagnants ou au contraire aucun dans une même course !
Nous avons donc besoin d’un algorithme d’ordonnancement pour aller au-delà de la classification.
Cela permettra également de pouvoir jouer d’autres paris (pas uniquement le simple gagnant).
Nous allons pour cela utiliser l’algorithme de Learning To Rank, qui vient de la discipline de l’Information Retrieval: le cas d’utilisation classique du Learning To Rank est le classement de documents en fonction de leur pertinence par rapport à une requête, typiquement une requête sur un moteur de recherche internet.

Principe
Nous allons utiliser la méthode Pairwise pour l’apprentissage d’ordonnancement.
Cette méthode consiste à transformer notre problème d’ordonnancement n-classes en un problème de classification 2-classes (binaire).
Plus concrètement dans le cas de notre problème, dans une première approche nous cherchons à bien classer les 5 premiers chevaux de la course, c’est à dire que pour chaque course de notre base, on sélectionne les 5 chevaux faisant l’arrivée et on cherche à apprendre à notre modèle à bien les ordonner.
Chaque cheval est représenté par son vecteur Xi décrivant ses features, avec i allant de 1 à 5 donc.
Le principe est pour chaque course de créer toutes les paires (Xi,Xj), puis de chercher à bien effectuer une classification binaire de Xi-Xj (à l’aide d’un algorithme SVM linéaire), permettant ensuite de déduire Xi inférieur ou supérieur à Xj.
Nous présentons à notre modèle des « blocs » de 5 chevaux (correspondant à une course), le label de la classification supervisée étant un vecteur fournissant la place réelle pour ces 5 chevaux.
Contrairement à ce que nous avons fait avec les modèles de machine learning précédents, le split en train et en test doit donc être fait sur l’identifiant de la course et non sur le cheval, puisqu’on doit traiter par bloc les 5 chevaux d’une même course.
La métrique prise en compte dans l’apprentissage est le taux de succès d’ordonnancement de toutes les paires; nous entraînons donc en fait directement le modèle à bien effectuer cette classification pour l’ensemble des paires, au lieu de simplement comparer un score de Xi avec un score de Xj comme nous le ferions si nous utilisions un modèle plus classique comme une régression (qui peut d’ailleurs être considérée comme méthode basique d’ordonnancement de learning to rank, dite méthode pointwise, basée uniquement sur le tri par score).
Notons que comme nous devons classer Xi-Xj, nous ne pouvons utiliser que des features numériques.
Le schéma ci-dessous décrit le fonctionnement de l’algorithme:

Résultat
Le score obtenu est de 65% environ:

Cela signifie que nous arrivons par cet algorithme à exactement ordonner toutes les paires dans 65% des courses fournies dans le jeu de test.
Ce score est relativement bon compte-tenu du fait qu’on mesure la capacité à trouver l’ordre exact parmi les 5 chevaux.

Utilisation
Nous fournissons à notre modèle les 5 vecteurs représentant les 5 chevaux de l’arrivée d’une course encore non vue par le modèle (ni en apprentissage ni en test).
Nous pouvons comparer ensuite sur cet exemple l’ordre prédit par le modèle, et l’ordre réel à l’arrivée (les chevaux étant identifiés par des indices de 0 à 4):

Evaluation des résultats
Pour évaluer la performance de notre modèle, le score de 65% indiqué plus haut n’est pas la mesure la plus pertinente. En effet il correspond à l’ordonnancement exact de toutes les paires.
Or il reste intéressant d’obtenir un résultat où l’on a commis une seule erreur entre 2 chevaux par exemple, et donc de pouvoir valoriser ce cas par rapport à un autre cas où on se serait complètement trompé dans l’ordre.
De plus, arriver à bien ordonner les premiers chevaux devrait avoir plus d’importance que d’arriver à bien ordonner les derniers. En effet si on a bien ordonné les 2 premiers, cela doit être valorisé par rapport au fait d’avoir bien ordonné les 2 derniers des 5 chevaux par exemple, puisque nous aurons trouvé les 2 premiers et pourrons jouer les paris correspondants (jeu simple et couplé).
Ainsi une métrique d’évaluation plus pertinente qu’on peut prendre en compte pour l’évaluation du modèle est le NDCG, utilisé en Information Retrieval.
Pour calculer le NDCG nous devons d’abord calculer le DCG, défini ainsi, pour p éléments à ordonner:

où rel(i) est la pertinence (relevance en anglais) du rang i, c’est à dire le poids qu’on accorde pour avoir bien classé l’élément au rang i.
Le NDCG est alors défini ainsi, avec IDCG correspondant au DCG de la liste Idéale (parfaitement ordonnée):

Le NDCG est donc une note sur 1, qui va « récompenser » la capacité à prédire les rangs les plus pertinents.
Pour illustrer cela calculons le IDCG, DCG et finalement NDCG de notre exemple précédent, en accordant un poids de 5 pour bien classer le 1er cheval, 4 pour le 2ème etc.. jusqu’à 1 pour le 5ème:

On obtient un NDCG de 0,9, ce qui reste ici relativement abstrait sur un seul exemple, il faudra l’apprécier de façon relative par rapport à d’autres ordonnancements, sur d’autres courses.
On pourra alors ajuster notre méthode de définition de la pertinence (ou poids), par exemple on pourrait aussi définir celle-ci comme étant égale pour chaque rang à 1/i (i étant toujours le rang du cheval).
Notons que la formule de base du NDCG présentée ci-dessus fait que 2 listes dont on a inversé l’ordre des 2 chevaux aux 2 premiers rangs ont le même NDCG. Pour contrer cet effet on peut utiliser des variantes à log2(i+1) au lieu de log2(i) dans la formule du DCG.