Direction de recherche : Patrick GALLINARI

Co-encadrement : USUNIER Nicolas

De la Consistance des Formulations de Substitution Convexes pour l’Ordonnancement

Cette thèse traite de l'étude de l'apprentissage pour l'ordonnancement, dont les moteurs de recherches du web sont l'une des applications les plus notables. En raison de la taille conséquentes des données à traiter, la question du passage à l'échelle des méthodes d'apprentissage est critique. Il est donc innenvisageable d'utiliser des méthodes d'optimisation directe du risque associé à la mesure d'évaluation de la tâche qui est généralement un problème NP-difficile. Pour cette raison, lors de la phase d'optimisation, il est d'usage de remplacer la mesure d'évaluation par une fonction de coût auxiliaire plus simple à optimiser (ex : continue, dérivable, convexe). Toutefois, il faut s'assurer que le coût auxiliaire se comporte correctement par rapport à l'objectif initial qui reste d'optimiser le risque d'évaluation. Il est donc souhaitable que l'optimisation du risque auxiliaire mène à des solutions optimales pour le risque d'évaluation. Un tel comportement est équivalent à la calibration du coût auxiliaire par rapport à la mesure d'évaluation. Dans cette thèse, nous nous intéressons aux différentes mesures d'évaluation d'ordonnancement et à la possibilité de construire des coûts auxiliaires convexes, et donc simple à optimiser, qui soient calibrés avec ces mesures. Le résultat clé de cette thèse est un théorème qui caractérise les mesures d'évaluation pour lesquelles il existe des coûts auxiliaires convexes et calibrés. D'une part, cela nous permet de prouver qu'un certain nombre de mesures d'évaluation courantes, telles que l'Expected Reciprocal Rank, l'Average Precision et le Pairwise Disagreement, ne possèdent pas de coût auxiliaire calibré. Cela signifie que l'optimisation d'un risque auxiliaire convexe mène à des solutions non-optimales pour ces mesures et qu'il faut donc trouver une alternative à l'utilisation d'une fonction de coût auxiliaire convexe quand on veut utiliser ces mesures. D'autre part, nous déduisons du théorème de caractérisation, une méthode pour construire explicitement un coût auxiliaire convexe et calibré pour les mesures d'évaluation pour lesquelles il en existe. Ensuite, pour les mesure d'évaluation dont la structure générale est similaire à un Discounted Cumulative Gain, nous montrons que la calibration d'un cout auxiliaire implique une garantie plus forte que la calibration : l'existence d'une borne sur le regret associé au coût auxiliaire. Pour un certain nombre de coûts auxiliaires convexes, nous calculons explicitement ces bornes de regret. Enfin nous proposons une implémentation en C++ de notre méthode de construction de coûts auxiliaires convexes et calibrés à travers le framework SLF. A l'aide de cette implémentation, nous proposons finalement une validation expérimentale de notre méthode.

Publications 2011-2013

• 2013
  • C. Calauzenes : “On the Consistency of Convex Surrogate Formulations for Ranking”, soutenance de thèse, soutenance 19/07/2013, direction de recherche Gallinari, Patrick, co-encadrement : Usunier, Nicolas (2013)
  • C. Calauzènes, N. Usunier, P. Gallinari : “Calibration and regret bounds for order-preserving surrogate losses in learning to rank”, Machine Learning, vol. 93 (2-3), pp. 227-260, (Springer Verlag) (2013)
• 2012
  • C. Calauzènes, N. Usunier, P. Gallinari : “On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking”, Advances in Neural Information Processing Systems 25, Lake Tahoe, NV, United States, pp. 197-205, (Curran Associates, Inc.) (2012)
• 2011
  • D. Buffoni, C. Calauzènes, P. Gallinari, N. Usunier : “Learning Scoring Functions with Order-Preserving Losses and Standardized Supervision”, The 28^th International Conference on Machine Learning (ICML 2011), Bellevue, WA, United States, pp. 825-832 (2011)