Brevet FR2865562A1 — publié le 20050729

L'invention concerne le domaine de l'apprentissage automatique et notamment un procédé permettant de mesurer l'importance de variables ayant servi à l'élaboration d'un modèle prédictif de classification ou de régression. L'invention concerne donc, outre l'apprentissage automatique au sens strict, également la sélection de variables, l'exploitation de données et l'aide à la décision. Le domaine de l'apprentissage automatique regorge aujourd'hui de techniques capables de résoudre efficacement des problèmes de régression et/ou de classification. Généralement ces techniques emploient la totalité des variables disponibles pour construire le modèle et sont incapables d'indiquer à posteriori quelles sont les variables qui ont effectivement contribué à la performance du modèle, ce qui résulte en des modèles à la fois surdimensionnés donc lents et ne permettant aucune interprétation des résultats. Le problème de la sélection de variables est devenu le centre de beaucoup de recherches dans les secteurs applicatifs pour lesquels les bases de données disponibles comportent des dizaines voir des centaines de milliers de variables. Ces secteurs incluent le traitement des données textuelles, des documents d'Internet, l'expression des gènes, la clasificatin de la fraude, 25 etc. L'objectif du choix des variables est triple: améliorer la performance des prédicteurs, fournir des prédicteurs plus rapides et plus rentables et permettre une meilleure compréhension du processus sous-jacent qui a produit les données. Parmi les techniques dédiées au choix des Variables, nous trouvons les méthodes qui sélectionnent les variables en les classant selon des coefficients de corrélation ( filtrer ) et les méthodes consistant à choisir un sous-ensemble optimal de variables ( wrapper ). Celles-ci incluent les méthodes qui évaluent les sous-ensembles de variables selon leur utilité à un modèle donné. Les méthodes wrapper utilisent le modèle élaboré comme une boîte noire pour ordonner les sous-ensembles de variables selon leur utilité 5 à la tache de modélisation. En pratique, on a besoin de définir: (i) comment rechercher dans l'espace possible des sous-ensembles de variables, (ii) comment évaluer la performance en termes de prédiction d'une machine à apprendre pour guider la recherche et interrompre la recherche, et (iii) quel prédicteur utiliser. On considérera notamment les enseignements suivants: [1] Article: A methodology to explain neural network classification - Neural Networks 15 (2002) 237-246 [2] Article: "Explaining Results of Neural Networks by Conceptual 15 Importance and Utility" Proceedings of the AISV'96 conference, 1-2 April 1996. Brighton UK, 1996. Les principaux écueils des méthodes antérieures sont l'absence de prise en compte de la distribution de probabilité des variables dont on cherche l'importance et la non-applicabilité à la régression. Le procédé proposé en [2] est insatisfaisant car il fait la supposition d'une variation strictement monotone croissante à la sortie d'un modèle lorsqu'on fait varier une variable de façon strictement monotone croissante. Le procédé proposé dans le document [1], quant à lui, ne permet pas de résoudre les problèmes inhérents aux méthodes existantes alors, en prenant compte la distribution de probabilité des variables dont on cherche l'importance. De plus, il n'est pas applicable aux problèmes de régression. Les auteurs de [1] proposent de mesurer l'importance des variables utilisées au cours de la phase de modélisation selon les termes suivants, nous les citons: Pour tenir compte des valeurs possibles de la variable d'entrée, nous utiisons:: S(xi f)--- f f, P(x;)P(a x;)(f (x; + a) f où P(a x;) est une antériorité sur les valeurs possibles de x; : x; qui peut être discrète, positive, liée, etc. La connaissance nécessaire pour definir l'antériorité dépend seulement du type de la variable d'entrée. Par exemple, pour une variable binaire, l'antériorité peut être: P(x;+a=l) = % et P(x;+a=0 = %) et 0 ailleurs". Or l'utilisation d'un prior ne permet pas de prendre en compte le vrai intervalle de variation d'une variable. On vise, par la présente invention, une mesure plus efficace de l'importance des variables ayant servi à l'élaboration d'une modélisation (classification ou régression). L'invention vise ainsi à permettre d'exploiter des classifieurs/régresseurs, en menant une analyse à posteriori de l'importance des variables, et en mettant ensuite en oeuvre des classifieurs/régresseurs utilisant peu de variables mais ayant des performances similaires (voire meilleures) à ceux utilisant toutes les variables. En d'autres termes, en mesurant l'importance des variables, il est possible d'éliminer les variables ne participant pas (ou très peu) à l'élaboration du résultat (régression ou classification). Les modèles que l'invention permet d'obtenir sont plus économes en 20 mémoire et en temps de calcul, ainsi que plus rapide. Le fait de connaître les variables importantes permet aussi de réduire la taille des bases de données. Cette efficacité est atteinte selon l'invention grâce à un procédé de mesure de l'importance d'une variable d'entrée sur le fonctionnement d'un modèle à apprentissage automatique; apte à élaborer des données de sortie à partir de données d'entrée par un traitement que ledit modèle est prévu pour apprendre lui-même, ledit procédé étant caractérisé en ce qu'il fait appel à l'élaboration d'une moyenne d'une valeur aléatoire, cette valeur aléatoire étant une différence entre d'une part une sortie obtenue pour un vecteur de variables d'entrée considéré et d'autre part une sortie obtenue pour un vecteur d'entrée perturbé, ce vecteur d'entrée perturbé étant défini comme étant ledit vecteur d'entrée considéré dans lequel la valeur de ladite variable d'entrée dont on souhaite mesurer l'importance est une valeur perturbée, la moyenne étant en outre calculée en appliquant à chaque dite valeur aléatoire considérée, à la fois la probabilité d'apparition du vecteur d'entrée considéré ainsi que la probabilité d'apparition de la valeur perturbée de la variable, la moyenne de la valeur aléatoire étant effectuée sur l'ensemble d'une distribution de probabilités des vecteurs d'entrée et sur l'ensemble d'une distribution de probabilités des valeurs de la variable d'entrée. D'autres caractéristiques, buts et avantages de l'invention 10 apparaîtront à la lecture de la description détaillée qui va suivre, faite en référence aux figures annexées sur lesquelles: - la figure 1 est un schéma fonctionnel illustratif du procédé selon l'invention; - la figure 2 est un organigramme illustratif d'un procédé de sélection 15 de variables mettant en oeuvre l'invention; - la figure 3 est un tracé représentant une erreur mesurée en relation avec le nombre de variables mises en oeuvre après sélection par le procédé de la figure 2. Le procédé ci-après décrit permet de résoudre les problèmes inhérents aux méthodes existantes en prenant en compte la distribution de probabilité des variables dont on cherche l'importance et en étant applicable, de plus, aux problèmes de régression. Il permet d'ordonner les sous-ensembles de variables selon leur utilité à la tâche de modélisation en mesurant l'importance des variables ayant servi à l'élaboration d'un modèle prédictif de classification ou de régression. Pour cela, on met ici en oeuvre le fait que l'importance d'une variable s'avère être à la fois fonction de la distribution de probabilité des exemples (vecteur de variables d'entrées effectivement apparus, I; sur la figure 1) et à la fois fonction de la distribution de probabilité de la variable en question (Vi sur la figure 1). On définit l'importance d'une variable comme étant la moyenne des variations mesurées en sortie du modèle lorsqu'on perturbe les exemples effectivement apparus en fonction de la distribution de probabilité de cette variable Vi. La sortie perturbée du modèle symbolisé par une fonction f, est définie pour un exemple I; comme étant la sortie du modèle pour cet exemple I; mais en ayant échangé la composante j de cet exemple par l'une des valeurs, Vk, de la variable Vj. Cette étape d'élaboration d'une entrée perturbée est illustrée à la figure 1 sous la référence 10. La variation mesurée, pour l'exemple fi est donc la différence entre la vraie sortie du modèle f(I;, Iii) pour l'exemple I; et la sortie perturbée du modèle, notée alors f(l;, Ikj) où Ikj est l'exemple (vecteur d'entrée perturbée). Cette différence est effectuée à l'étape 20 sur la figure 1, symbolisée par un soustracteur. L'importance de la variable Vj est ensuite considérée comme étant la moyenne des différences données par f(Ij,Iij) f(Ii,Iki)I, où la moyenne est calculée sur la distribution de probabilité des exemples et sur la distribution de probabilité de la variable V. Cette moyenne est calculée à l'étape 30 sur la figure 1, ici symbolisé par un additionneur. On décrira maintenant une telle approche en termes mathématiques. Les équations ci-après spécifiées font pour cela appel aux 20 paramètres suivants: - j est la variable dont on cherche l'importance; - Mi est une réalisation de la variable j; - I est un vecteur de dimension n, c'est à dire un exemple ayant servi à la construction du modèle; lmestunvecteurm; - im est la composante I du vecteur m - f est le modèle réalisé. - Pv (u) est la distribution de probabilité de la variable Vj - P1(v) est la distribution de probabilité des vecteurs L 30 On pose en outre fj(a;b) = f;(a1, ..., an; b) = b, aj+i, ... an) ; ap étant la P1ème composante du vecteur a. On définit ici l'importance de la variable Vi pour le modèle f comme étant: S(VJ If) = J f Pv_ (u)duP1 (I; ; Ikj) fi (I; ; )I Dans un mode de réalisation préférentiel car de mise en oeuvre particulièrement aisée, la façon de mesurer cette espérance S(Vj I f) est la suivante: on réalise simultanément des tirages de I et de Vi qui permettent d'observer des réalisations de am= I f(l, IO I. Dans ce cas, on applique des lois de distribution de probabilité sur le vecteur et la variable en réalisant simplement des tirages mettant en oeuvre directement cette probabilité. La mesure de l'espérance de am est alors réalisé par filtrage. On utilise pour cela, par exemple, un filtre de Kalman jusqu'à convergence. Un autre exemple de mise en oeuvre de la mesure de cette espérance est la suivante. Si on approxime la distribution des exemples à l'aide de la base de données disponible (comportant M exemples) et qui a servi à construire le modèle. On peut réécrire S(VV 1 f) sous la forme: S(VVIf) =JPI(v)dv JPvj(u)duG fi(I;;Iki) (I;;)I j S(VV f) =M E(E{ If,(I;;Ik,) fi(I;}) Si on approxime la distribution de probabilités P,. (u) de la variable j à l'aide d'une statistique d'ordres (par exemple les centiles, P=100) on a alors: S(VVIf) 1 1 @f.(I;;Ik.) f.(I;;I; MP M P L'illustration de la figure 1, qui symbolise l'opération de calcul de la moyenne, sous la forme d'un additionneur 30, prend alors sa signification littérale. On reportera maintenant l'évaluation d'une telle mesure de l'importance des variables dans le cas où le modèle est élaboré, et mis en oeuvre, par un réseau de neurones de type perceptron à une couche cachée. Ce procédé y a été appliqué à la sélection de variables par une élimination de moindre importance , la mesure d'importance étant refaite 10 après chaque élimination de variable et réapprentissage. L'algorithme de backward-elimination est illustré par l'organigramme de la figure 2. Le procédé de mesure de l'importance de variable y intervient dans la phase grisée. Sur cet organigramme, on réalise de manière itérative les étapes suivantes: a) mesure de l'importance de chaque variable d'entrée mise en oeuvre à l'itération précédente (étape 100 sur la figure 2) ; b) élimination d'une ou plusieurs valeurs d'entrée de moindre 20 importance (étape 200 sur la figure 2) ; c) mis en oeuvre d'un réapprentissage du modèle en fonction des variables restantes (étape 300 sur la figure 2). En outre, ces étapes sont répétées jusqu'à ce que l'ensemble des variables soit éliminé, et, pour chaque itération, on réalise une mesure de l'erreur des résultats obtenus par le module à nombre de variable réduit par rapport à des résultats considérés comme idéaux. L'arrêt de ces itérations est défini, au final, par le fait qu'il n'existe plus aucune variable en entrée. On obtient enfin un tracé de l'erreur constatée en fonction du nombre de variables mis en oeuvre, ce nombre de variables s'étalant du nombre maximal de variables disponibles (ici 280) jusqu'à un nombre de variables réduit à 0. Ce tracé présentant l'influence du nombre de variables conservées est présenté à la figure 3. On voit alors apparaître, sur ce cas réel qu'il ne sert à rien d'utiliser toutes les variables disponibles. En effet, il est possible d'obtenir le même niveau d'erreur en utilisant seulement 55 variables (aux points A et A' du tracé) plutôt qu'en utilisant les variables de départ (aux points B et B' du tracé). On obtient même une erreur inférieure à celle de départ pour un nombre de variables égal à 120 (points C et C' du tracé). REVENDICATIONS 1. Procédé de mesure de l'importance d'une variable d'entrée sur le fonctionnement d'un modèle à apprentissage automatique, apte à élaborer des données de sortie à partir de données d'entrée par un traitement que ledit modèle est prévu pour apprendre lui-même, ledit procédé étant caractérisé en ce qu'il fait appel à l'élaboration d'une moyenne d'une valeur aléatoire (30), cette valeur aléatoire étant une différence (20) entre d'une part une sortie obtenue pour un vecteur de variables d'entrée considéré et d'autre part une sortie obtenue pour un vecteur d'entrée perturbé (10), ce vecteur d'entrée perturbé étant défini comme étant ledit vecteur d'entrée considéré dans lequel la valeur de ladite variable d'entrée dont on souhaite mesurer l'importance est une valeur perturbée, la moyenne étant en outre calculée en appliquant à chaque dite valeur aléatoire considérée, à la fois la probabilité d'apparition du vecteur d'entrée considéré ainsi que la probabilité d'apparition de la valeur perturbée de la variable, la moyenne de la valeur aléatoire étant effectuée sur l'ensemble d'une distribution de probabilités des vecteurs d'entrée et sur l'ensemble d'une distribution de probabilités des valeurs de la variable d'entrée. 2. Procédé de mesure selon la revendication 1, caractérisé en ce que l'importance de la variable d'entrée est donnée par l'expression: S(VV If) = $ Pv, (u)duPI (v)dl fi (I; ; IkJ) fi (Ti; I;) IJ où f est une fonction représentant le modèle, Vj est la variable dont on souhaite mesurer l'importance, Pv (u) est la distribution de probabilité de la variable Vb Ii est un vecteur d'entrée du modèle, PI(v)est la distribution de probabilité des vecteurs I, Ik1 est le vecteur perturbé. 3. Procédé de mesure selon la revendication 1 ou la revendication 2, caractérisé en ce que lesdites probabilités sont appliquées en calculant la moyenne sur des tirages, pour chaque différence, des vecteurs d'entrée et/ou de la variable d'entrée utilisée pour perturber le vecteur d'entrée. 4. Procédé selon l'une quelconque des revendications précédentes, caractérisé en ce que le modèle est mis en oeuvre par un réseau de neurones. 5. Procédé selon la revendication 4, caractérisé en ce que le réseau de neurones est un réseau de type perceptron à une couche cachée. 6. Procédé de sélection de variables mises en oeuvre dans un modèle à apprentissage automatique, apte à élaborer des données de sortie à partir de données d'entrée par un traitement que ledit modèle est prévu pour apprendre lui-même, ledit procédé de sélection incluant le procédé de mesure selon la revendication 1, le procédé de sélection étant caractérisé en ce qu'il consiste à mettre en oeuvre, de manière répétitive la série d'étapes suivantes: a) mesure de l'importance des variables d'entrée mises en oeuvre à l'itération précédente, par la mise en oeuvre dudit procédé de mesure (100); b) élimination d'une ou plusieurs variables d'entrée de moindre importance (200) ; c) mise en oeuvre d'un réapprentissage du modèle en fonction des variables restantes (300). 7. Procédé de sélection de variables selon la revendication 6, caractérisé en ce qu'il comprend en outre l'étape consistant à effectuer une évaluation de niveau d'erreur du modèle obtenu à chaque itération, et à comparer les niveaux d'erreurs (A, A', B, B', C, C'), pour ces différents modèles obtenus à chaque itération. 8. Dispositif de mesure de l'importance d'une variable d'entrée sur le fonctionnement d'un modèle à apprentissage automatique apte à élaborer des données de sortie à partir de données d'entrée par un traitement que ledit modèle est prévu pour apprendre lui-même, ledit dispositif étant essentiellement constitué d'une mémoire et d'un processeur ainsi que d'un ensemble de moyens de commande de ce processeur et de cette mémoire, ledit dispositif de mesure étant caractérisé en ce qu'il comprend des moyens d'élaboration d'une moyenne d'une valeur aléatoire (30), cette valeur aléatoire étant une différence (20) entre d'une part une sortie obtenue pour un vecteur de variables d'entrée considéré et d'autre part une sortie obtenue pour un vecteur d'entrée perturbé (10), ce vecteur d'entrée perturbé étant défini comme étant ledit vecteur d'entrée considéré dans lequel la valeur de ladite variable d'entrée dont on souhaite mesurer l'importance est une valeur perturbée, ledit dispositif de mesure comprenant des moyens prévus pour calculer la moyenne en appliquant à chaque dite valeur aléatoire considérée, à la fois la probabilité d'apparition du vecteur d'entrée considéré ainsi que la probabilité d'apparition de la valeur perturbée de la variable, la moyenne de la valeur aléatoire étant effectuée sur l'ensemble d'une distribution de probabilités des vecteurs d'entrée et sur l'ensemble d'une distribution de probabilités des valeurs de la variable d'entrée. 9. Dispositif selon la revendication 8, caractérisé en ce qu'il inclut également un moyen associé mettant en oeuvre ledit modèle, ce moyen associé étant constitué par un réseau de neurones.