Méthodes d’apprentissage statistique pour le scoring

Les travaux de thèse présentés dans ce manuscrit portent sur le développement d’une méthode non-paramétrique pour l’apprentissage supervisé de règles d’ordonnancement à partir de données étiquetées de façon binaire.

On suppose que l’on observe une collection d’individus représentatifs d’une population, caractérisés par un ensemble d’entrées (variables ou prédicteurs) et par une étiquette (label ou classe) binaire, de la forme « bons-mauvais » par exemple. Lorsque l’on dispose de telles données, l’objectif le plus courant est d’apprendre un modèle permettant de prédire l’étiquette (inconnue) d’une nouvelle observation de la population. Ce problème d’apprentissage supervisé est bien connu dans la littérature: il s’agit de la classification binaire. Cependant, il existe aussi de nombreuses applications pour lesquelles l’enjeu principal n’est pas de prédire les labels binaires mais plutôt de définir une relation d’ordre sur la population. On parlera dans ce cas d’un problème de scoring ou d’ordonnancement binaire.

Cette problématique apparaît de manière récurrente dans des domaines très variés. On la rencontre par exemple en finance où, pour évaluer le risque de non remboursement de crédits, les sociétés bancaires étudient un panel de clients, pour lesquels elles disposent d’informations concernant leur mode de vie (catégorie socio professionnelle, situation maritale, revenus, etc.) et d’un label binaire indiquant si les crédits qu’ils ont contractés ont été remboursés. De même, la mise au point de règles de décision pour l’aide au diagnostic médical repose sur l’étude de patients pour lesquels on dispose d’une description des symptômes ressentis et d’une étiquette binaire indiquant s’ils sont « sains » ou « atteints ». Un autre exemple d’application réside dans la mise au point de moteurs de recherche capables de hiérarchiser une collection de documents selon leur pertinence par rapport à la requête formulée par un utilisateur.

Ainsi, le champ d’application des méthodes d’ordonnancement est très vaste et c’est encore un tout autre contexte qui a motivé le lancement de ces travaux de recherche par le constructeur automobile Renault, celui de l’objectivation des prestations relatives à l’agrément de conduite et plus particulièrement du brio, qui désigne la sensation d’accélération procurée par un véhicule, dont l’étude a été au centre de ces travaux de thèse. Ainsi, la méthode d’ordonnancement que nous allons présenter dans ce manuscrit a été mise en oeuvre afin d’identifier les caractéristiques physiques des véhicules expliquant le brio ressenti par le client, fourni sous la forme d’une cotation binaire de type « bons-mauvais », et de construire un indice permettant de quantifier le niveau de prestation atteint et de comparer les différents véhicules du marché.

Dans le cadre particulier de l’ordonnancement binaire, où l’étiquette observée est donc de nature binaire, l’objectif est d’arriver à ordonner une population de telle sorte que les « meilleurs » individus se trouvent en tête de classement. Intuitivement, on perçoit qu’une « bonne » solution consisterait à classer les individus selon leur probabilité d’être « bons », ou du moins « pertinents » selon l’étiquette considérée. Le problème de scoring revient alors à estimer l’ordre induit sur l’espace d’entrée X ⊂ R q , q ≥ 1, par la probabilité à posteriori définie par ∀ x ∈ X , η(x) = P{Y = +1 | X = x},

où X ∈ X , représente un ensemble de prédicteurs permettant de modéliser le label binaire Y ∈ {−1, +1}.

Plusieurs méthodes ont été proposées dans la littérature pour produire des règles d’ordonnancement à partir de données étiquetées de façon binaire. D’une manière générale, on peut distinguer deux grandes approches. D’une part, on trouve des méthodes statistiques classiques, qui visent à estimer la probabilité à posteriori η, puis utilisent cet estimateur pour ordonner les observations de l’espace d’entrée X . Parmi ces méthodes on peut citer par exemple l’analyse discriminante linéaire (LDA pour Linear Discriminant Analysis, [Fisher 1936]) ou la régression logistique (voir par exemple [Hastie & Tibshirani 1990], [Friedman et al. 1998] ou [Hastie et al. 2001]), toutes deux basées sur la maximisation du rapport de vraisemblance d’un modèle de type logit. Un autre exemple est la régression logistique à noyau (KLR pour Kernel Logistic Regression, voir par exemple [Zhu & Hastie 2001], [Jaakkola & Haussler 1999] et [Keerthi et al. 2002]), qui procède à l’estimation non paramétrique de la probabilité à posteriori en résolvant un problème d’optimisation convexe de type SVM (pour Support Vector Machines, voir par exemple [Schölkopf & Smola 2002]).

D’autre part, une seconde approche est fondée sur l’optimisation d’un critère évaluant la performance ou a contrario le risque de la règle d’ordonnancement produite, au sens de l’approche ERM (pour Empirical Risk Minimization, [Vapnik & Chervonenkis 1974]). Parmi les nombreuses méthodes proposées, on peut citer les méthodes RankBoost (proposée dans [Freund et al. 2003]) et AdaRank (proposée dans [Xu & Li 2007]), fondées sur une procédure de type boosting ([Freund & Schapire 1999]), les méthodes RankSVM (proposée dans [Rakotomamonjy 2004] et [Joachims 2002b]) et RankRLS (proposée dans [Pahikkala et al. 2007]), basées sur la mise en oeuvre de SVM pour deux fonctions de coût différentes (respectivement la hinge loss et les moindres carrés) ou encore les méthodes RankNet (proposée dans [Burges et al. 2005]) et LambdaRank (proposée dans [Burges et al. 2006]), reposant sur l’utilisation de réseaux de neurones. Toutes ces méthodes présentent un point commun : elles reposent en réalité sur la comparaison des paires d’observations dans l’esprit de l’approche proposée dans [Cohen et al. 1999]. Ainsi, selon la méthode considérée, la performance de la règle d’ordonnancement produite est évaluée par des critères comme l’ASC, l’Aire Sous la Courbe COR (pour Caractéristique de la Courbe de Réception, [Egan 1975]), le τ de Kendall ([Kemeny 1959], [Kendall 1945]) ou encore la statistique de Wilcoxon ([Wilcoxon 1945]), s’exprimant en fonction du nombre de paires discordantes, i.e. du nombre de paires d’observations pour lesquelles l’ordonnancement induit par la règle de prédiction n’est pas cohérent avec les étiquettes binaires observées.

Ces deux approches présentent naturellement des avantages et des inconvénients. S’il semble naturel d’estimer directement la probabilité à posteriori, induisant l’ordonnancement que l’on souhaite retrouver, cette approche présente certaines limites. Tout d’abord, dans les trois méthodes que nous venons de citer, la représentation de la fonction η est imposée par l’utilisation d’un modèle de type logit, qui pourrait ne pas correspondre aux données étudiées. Par ailleurs, les méthodes paramétriques comme la LDA ou la régression logistique sont confrontées à ce que l’on appelle le fléau de la dimension, l’estimation de la probabilité η devenant délicate dans un espace X de grande dimension. Sur ce point précis, les méthodes fondées sur la minimisation d’un risque d’ordonnancement permettront d’obtenir des règles de prédiction plus performantes. Cependant, les procédures de type ERM que nous avons citées ci-dessus présentent elles aussi un inconvénient majeur qui réside dans la nature globale des critères de performance optimisés. En effet, si ceux-ci permettent de trouver un « bon » ordonnancement de manière globale sur l’ensemble des observations, ils ne garantissent nullement d’obtenir le classement le plus pertinent des meilleures observations de l’échantillon. Or, il existe de nombreuses applications, comme la recherche de documents sur Internet par exemple, dans lesquelles on ne s’intéresse qu’au début du classement proposé. Aussi, d’autres critères ont été proposés dans la littérature afin d’évaluer la performance locale d’une règle d’ordonnancement, comme par exemple les critères d’ASC partielles ou tronquées, introduits respectivement dans [Dodd & Pepe 2003] et [Clémençon & Vayatis 2007], ou encore le critère p-norm push proposé dans [Rudin 2006].

Table des matières

Introduction
I Apprentissage d’Arbres Binaires d’Ordonnancement
1 Méthode TreeRank : Optimisation récursive de la courbe COR
1.1 Un problème de scoring
1.1.1 Problématique d’ordonnancement binaire
1.1.2 Fonction de score
1.1.3 Fonction de score optimale
1.2 Mesures de performance d’une règle de score
1.2.1 Courbe COR
1.2.1.1 Mesures de performance d’un classifieur binaire
1.2.1.2 Courbe COR d’une collection de classifieurs binaires
1.2.1.3 Courbe COR associée à une fonction de score
1.2.1.4 Courbe optimale COR∗
1.2.1.5 Courbes COR et RP
1.2.2 Aire sous la courbe COR
1.2.2.1 Aire sous la courbe COR empirique
1.2.2.2 Aire sous la courbe optimale COR∗
1.2.2.3 Limites du critère ASC
1.3 M-estimation d’une fonction de score
1.4 Approximation de la courbe COR∗ par une fonction affine par morceaux
1.4.1 Fonction de score constante par morceaux
1.4.1.1 (P, σ)-représentation
1.4.1.2 D- et I-représentations
1.4.1.3 Fonction de score constante par morceaux quasi-optimale
1.4.2 Approximation récursive et adaptative de la courbe COR∗
1.4.2.1 Première itération
1.4.2.2 Nème itération
1.4.2.3 Partitionnement récursif de l’espace X
1.4.2.4 Résultat théorique de convergence
1.4.3 Un schéma d’approximation arborescent
1.4.3.1 Première itération
1.4.3.2 d ème itération
1.4.3.3 Approximation de type éléments finis
1.5 L’algorithme TreeRank
1.5.1 Arbres binaires d’ordonnancement
1.5.2 Un algorithme de partitionnement récursif
1.5.3 Résultats théoriques
1.5.4 Résultats expérimentaux
1.5.4.1 Exemple Unif2d
1.5.4.2 Exemple GaussCroix2d
1.6 Conclusion et perspectives
II Partitionnement, Elagage et Agrégation
2 LeafRank : Procédure d’Optimisation Locale de l’ASC
2.1 Procédure LeafRank : scinder pour mieux estimer
2.1.1 Etape d’optimisation de la procédure TreeRank
2.1.2 La procédure LeafRank
2.2 Stratégies de partitionnement
2.2.1 Partition fixée à priori : un premier pas vers la flexibilité
2.2.2 Un problème de classification binaire pondérée
2.3 Deux exemples d’implémentation
2.3.1 Une version pondérée de l’algorithme de classification CART
2.3.1.1 L’algorithme CART
2.3.1.2 Une règle de score interprétable
2.3.1.3 Mesure de l’importance relative des variables
2.3.2 Implémentation récursive de Machines à Vecteurs Supports
2.3.2.1 Cas séparable
2.3.2.2 Cas non-séparable
2.3.2.3 Condition de marge souple
2.3.2.4 Adaptation au problème de classification binaire pondérée
2.3.2.5 Flexibilité et interprétabilité de la règle de score
2.3.3 Résultats expérimentaux
2.3.3.1 Exemple GaussLin2d
2.3.3.2 Exemples GaussCroix2d et GaussQuad2d
2.4 Conclusion et perspectives
3 Elagage d’un arbre d’ordonnancement
3.1 Sélection de modèle
3.1.1 Méthodes de validation
3.1.1.1 Validation « hold-out »
3.1.1.2 Validation croisée
3.1.2 Méthodes de pénalisation
3.1.2.1 Une pénalité idéale
3.1.2.2 Pénalités ré-échantillonnées
3.1.2.3 Bornes supérieures pour la déviation du critère ASC
3.2 Elaguer un arbre binaire d’ordonnancement
3.3 Elagage par optimisation de l’ASC « régularisée »
3.3.1 Une pénalisation linéaire
3.3.2 Construction d’une suite de sous-arbres optimaux
3.3.3 Sélection du sous-arbre optimal par validation
3.4 Elagage par optimisation de l’ASC structurelle
3.4.1 Une pénalisation non-linéaire
3.4.2 Deux exemples de pénalités
3.4.3 Règles de score consistantes
3.5 Conclusion et perspectives
Conclusion

Cours gratuitTélécharger le document complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *