Personalize Expedia Hotel Searches - ICDM 2013
Expedia est une agence de voyages en ligne. Lorsque vous effectuez une recherche le site vous affiche une liste d’hôtels susceptible de vous intéresser, le résultat qui en résulte est calculé en amont par Expédia. Ce calcul provient d'un algorithme de classement (ranking) qui vise à augmenter la probabilité que le client procède à une réservation. Cet algorithme est fonction de la caractéristique des hôtels, du pays de destination, de l'historique d'achat ainsi que des prix proposés par la concurrence. L'objectif est de réussir à créer un modèle qui a de meilleurs résultats que celui déjà existant.
Critère de classement
5 - Si l'utilisateur a pris une chambre à cet hôtel
1 - L'utilisateur a cliqué pour avoir plus d'information sur l’hôtel
0 - L'utilisateur n'a ni cliqué ni pris une chambre à cet hôtel
Il faut donc pour chaque recherche proposer le meilleur classement soit pour les trois premiers résultats : 5,1,0
Résultat :
Le critère d'évaluation est le NDCG. Il fallait battre le NDCG d'Expedia qui est de 0.49748.
En conclusion, le meilleur modèle a un de NDCG de 0.54075, mon modèle obtient un NDCG de 0.47527.
En classement final, j'obtiens la 132e place sur un total de 337 équipes participantes. La taille de la mémoire nécessaire à l'apprentissage et à la prédiction, la lenteur de divers traitement sous R ont rendu plus ardue la recherche du meilleur modèle.
Pour les modèles de learning ranking (apprendre à classer), il y a trois types approches :
Pointwise
Le problème de ranking est transformé en un problème de régression, classification. La structure de la requête est ignorée.
Pairwise
Ici le problème de ranking est transformé en un problème classification, mais ici les différents résultats de la requête sont classés deux par deux. La structure de la requête dans son ensemble est ainsi ignorée. Cette méthodologie est lourde en calcul du fait du grand nombre de combinaison.(RankSVM)
Listwise
En comparaison avec l'approche pairwise qui minimise les erreurs de classification des documents des requêtes par deux, l'approche pairwise vise à minimiser l'erreur de ranking de la requête. On tient compte ici de la structure de la requête. (ListNet, Lambdarank)
Un excellent document pour commencer :
http://www.hangli-hl.com/uploads/3/4/4/6/34465961/learning_to_rank.pdf
NDCG
Normalized Discounted Cumulative Gain est la mesure de performance d'un système de recommandation. Elle varie de 0.0 à 1.0, où 1.0 représente le classement idéal. Cette mesure est communément utilisée pour évaluer la performance d'un moteur de recherche.
Exemple issu de wikipedia
 |  |  | |
|---|---|---|---|
| 1 | 3 | 0 | N/A |
| 2 | 2 | 1 | 2 |
| 3 | 3 | 1.585 | 1.892 |
| 4 | 0 | 2.0 | 0 |
| 5 | 1 | 2.322 | 0.431 |
| 6 | 2 | 2.584 | 0.774 |
Données
Expédia a fourni une base Train qui inclus à la fois des clients dont les données ont été ordonnées (en première position : réservation de chambre ou clique) par l'algorithme d'Expédia et des clients dont les données ont été mises dans le désordre.
La base Train a 9,9 millions de lignes et la base Test a 6,6 millions de lignes.
Pour faire apprendre mon modèle, j'utilise la base Train non randomisée soit 3 millions de lignes.
Mon modèle final est de type pointwise après avoir tenté un modèle de type pairwise.
1.Modèle pointwise
Le but du jeu est de déterminer pour chaque requête, les hôtels pour lesquels les clients vont réserver au moins une nuit soit 5, cliquer soit 1 ou ne rien faire soit 0.
En utilisant l'approche pointwise, je transforme un problème de classement en une "simple" prédiction. Lors de chaque recherche, une liste d'hôtels est présentée au client or cette liste peut-être longue (jusqu'à plus de 30 hôtels). Si l'on utilise l'ensemble de la base Train c'est-à-dire l'ensemble des hôtels proposés pour réaliser le modèle la proportion des 5 et des 1 est très faible par rapport à la fréquence des 0, les 5 et 1 sont alors des événements rares. C'est pour cela que je limite le nombre d'hôtels aux 5 premiers proposé ce qui fait mécaniquement augmenter la proportion de 5 et de 1, les 5 et les 1 étant en début de classement. La proportion de 1 étant toujours trop faible, je transforme les 1 en 0 et simplifie le problème. Le modèle devient binomial et s'attache à rechercher les hôtels les plus susceptibles d'être réservés versus ceux qui le sont le moins.
Pour le classement final, j'ordonne les hôtels en fonction de leur probabilité d'être réservé.
J'utilise un gradient boosting qui est constitué d'un ensemble de 2000 arbres avec comme paramètre une distribution de type Bernouilli. La base de train a près de 20% d'hôtels qui ont le score de 5 suite au choix de 5 premiers hôtels. Le gradient boosting a l'avantage de s’accommoder avec les données manquantes et les outliers c'est pourquoi je n'ai pas procédé aux remplacements des valeurs manquantes.
2.Modèle pairwise
Selon la littérature, les modèles pairwise et listwise sont les plus performants pour résoudre les problèmes de ranking, j'ai commencé à réaliser des tests avec l'algorithme du RankSVM concluant rapide, performant, économe en mémoire vive.
http://www.cs.cornell.edu/people/tj/svm_light/svm_rank.html
Cet algorithme utilise un format de fichier peu commun, il a fallu réaliser sous R un petit programme pour convertir mes données dans ce format cependant lorsque j'ai appliqué ce programme à l'ensemble des données de train et de test (10 millions de lignes) j'ai rencontré un problème de performance. Je pense refaire ce programme sous Python.
Conclusion
Mon modèle nécessite quelques heures d’exécution, le modèle gagnant près de 30 heures. Ces concours sont très utiles pour se former et échanger, mais dans un cadre industriel où la référence de temps est la centaine de millisecondes le meilleur modèle est déjà trop lent. À la suite d'une conférence chez Critéo, j'ai découvert que les modèles de ce dernier ainsi que ceux de Google étaient plus "simples" que je ne l'avais pensé, ils sont surtout rapides et optimisés.
Autres :