Précédent Index Suivant
Chapitre 1 Apprentissage à partir d'exemples : présentation de la problématique

Ce chapitre présente la problématique générale de la classification supervisée. Il emprunte des notations et différents éléments aux articles [GG96] et [CL96] auxquels le lecteur est invité à se rapporter.

1.1 Approche probabiliste

Établir un diagnostic dans le domaine médical, signifie être capable d'associer le nom d'une maladie à un certain nombre de symptômes présentés par des malades. On repère, dans ce problème, trois objets essentiels : les malades, les maladies et les symptômes. Les malades forment la population, les symptômes sont les descriptions des malades, les maladies sont les classes. On suppose qu'il existe un classement correct, c'est-à-dire qu'il existe une application qui associe à tout malade une maladie. Apprendre à établir un diagnostic, c'est associer une maladie à une liste de symptômes de telle manière que cette association corresponde au classement défini ci-dessus. Pour formaliser notre propos, nous utiliserons les notations suivantes :

Le but de l'apprentissage est alors de rechercher une procédure de classification C telle que C° X = Y ou, de manière plus réaliste, telle que C° X soit une bonne approximation de Y. En effet, supposons que nous ayons un ensemble de patients dont nous souhaitons savoir s'ils sont malades ou pas. Un patient est décrit par une liste de symptômes et de mesures. Il est alors possible que les descriptions ne permettent pas toujours de différencier un patient malade d'un patient sain. En effet, il se peut que deux patients, l'un malade, l'autre pas, aient les mêmes descriptions. Dans ce cas, on ne peut espérer trouver une procédure de classification exacte, le but sera donc de trouver une << bonne >> procédure de classification dans un sens qui reste à préciser.



Figure 1.1 : Apprendre, c'est trouver une fonction C

Dans la pratique, on dispose souvent d'un ensemble d'attributs A1, ..., An logiques, symboliques ou numériques qui prennent leurs valeurs dans des domaines D1, ..., Dn. Décrire un élément de la population consiste alors à attribuer une valeur à chacun de ces attributs. L'espace de description D est alors égal au produit cartésien D1 × ... × Dn. Par exemple, on décrira un patient par un ensemble de symptômes (mal de tête, douleurs abdominales , ...) et une suite de mesures (tension, température, ...) ; on décrira un client par un ensemble de données que l'on possède sur lui (âge, sexe, catégorie socioprofessionnelle, ...).

Comment exprimer le fait que C° X doit être une bonne approximation de Y ? Intuitivement, cela signifie que C° X est rarement différent de Y. Une manière de formaliser cela consiste à supposer l'existence d'une distribution de probabilité sur l'ensemble P et à dire que C° X est une bonne approximation de Y s'il est peu probable que ces deux fonctions diffèrent. On supposera donc que l'ensemble P est probabilisé. Nous supposerons également, pour simplifier la présentation, que l'ensemble D est discret. Soit P la probabilité définie sur la population P. On peut alors définir les probabilités et notations suivantes :

La formule de Bayes s'écrit alors :

P(k/d)=
P(d/k)P(k)
P(d)
    (1.1)

Supposons que nous soyons dans la situation idéale où nous pouvons évaluer les quantités P(d), P(k) et P(d/k) pour toutes les valeurs d de D et k de {1,...,c}. Comment choisir la fonction C ? Pour étudier ce choix, considérons un exemple simpliste :

Exemple 1   P est la population française. On dispose, en outre, d'un échantillon représentatif de la population française. On décrit les individus par un attribut logique répondeur qui vaut vrai si l'individu possède un répondeur téléphonique et faux sinon. L'espace de description est donc l'ensemble {répondeur, répondeur}. On souhaite répartir les individus en deux classes {aisé, aisé}, la classe aisé correspond aux individus ayant un revenu supérieur à la moyenne. On dispose des informations suivantes : 40 pour cent de la population dispose de revenus supérieurs à la moyenne, 80 pour cent des personnes aisées ont un répondeur, alors que 45 pour cent de la population restante dispose d'un répondeur. Ce qui peut être résumé dans le tableau suivant :


classe k aisé 3ex aisé
P(k) 0.4 0.6
P(répondeur/k) 0.8 0.45



Une première règle possible pour le choix de la fonction de classement C pourrait être : << attribuer à chaque description la classe majoritaire >>, c'est-à-dire celle pour laquelle P(k) est maximum. La fonction Cmaj correspondante attribuerait à tout individu, qu'il possède un répondeur ou pas, la classe aisé. Le défaut principal de cette règle est qu'elle ne fait jouer aucun rôle à la description. Cette fonction de classement ne peut être en général que très grossière.

Une seconde règle consiste à raisonner ainsi : << si j'observe d, je choisis la classe pour laquelle cette observation est la plus probable >>, c'est-à-dire celle pour laquelle P(d/k) est maximum. C'est la règle dite du maximum de vraisemblance. La fonction de classement Cvraisemblance correspondante attribuerait la classe aisé à tout individu possédant un répondeur et la classe aisé à tous les autres. On voit que cette fonction de classement est plus fine que la précédente et qu'elle correspond d'avantage à ce que l'on attend intuitivement. Son principal défaut apparaît dans l'exemple suivant : supposons que l'ensemble Cl soit composé des trois classes employé des Télécom, médecins, ouvriers et que la probabilité pour qu'un employé des télécom ait un répondeur soit égale à 1. La règle du maximum de vraisemblance associerait alors la classe employé des Télécom à tout individu possédant un répondeur, ceci sans tenir compte des proportions des différentes classes à l'intérieur de la population.

Une troisième règle consiste à attribuer à une description d la classe k qui maximise la probabilité P(k/d) qu'un élément ayant d pour description soit de classe k. En utilisant la formule de Bayes ??, en remarquant que P(d) est constant, il suffit donc de choisir la classe k qui maximise le produit P(d/k)P(k).
P(répondeur/aisé)× P(aisé) = 0.8 × 0.4 = 0.32
P(
répondeur
/aisé)× P(aisé) = 0.2 × 0.4 = 0.08
P(répondeur/
aisé
)× P(
aisé
) = 0.45 × 0.6 = 0.27
P(
répondeur
/
aisé
)× P(
aisé
) = 0.55 × 0.6 = 0.33

La fonction CBayes ainsi choisie associe à toute personne possédant un répondeur la classe aisé et à toute personne n'en possédant pas la classe aisé. On voit sur cet exemple que la fonction CBayes est égale à la fonction Cvraisemblance mais ce n'est pas toujours le cas (exercice ??).

Nous avons introduit à l'aide de cet exemple différents choix possibles pour la procédure de classification lorsque l'apprenant a accès aux quantités P(d), P(k) et P(d/k) pour toutes les valeurs d de D et k de {1,...,c}. Nous définissons maintenant ces règles :

Définition 1   Règles de choix des fonctions de classement.

On peut facilement vérifier que la règle de Bayes se ramène à la règle du maximum de vraisemblance lorsque les classes sont équiprobables. Pour comparer des procédures, nous allons définir l'erreur de classification :

Définition 2   Soit C une fonction de classement, l'erreur E(d) pour une description d est la probabilité qu'un élément de la population P de description d soit mal classé par C, i.e.
E(d) = P(Y ¹ C / X=d).
L'erreur de classification E(C) d'une fonction de classement est la moyenne pondérée des erreurs sur les descriptions d, i.e.
E(C)=
 
å
d Î D
E(d)P(X=d).

Exemple 2   En calculant les erreurs sur l'exemple des répondeurs téléphoniques, nous obtenons pour la procédure majoritaire E(Cmaj)=0.4. En effet, cette procédure ne se trompe que pour les personnes de la classe aisé. Pour la procédure obtenue à l'aide de la règle du maximum de vraisemblance, nous avons

E(Cvraisemblance)= E(répondeur) P(répondeur) + E(répondeur) P(répondeur)

, soit encore en utilisant les définitions d'erreur et la règle de Bayes

E(Cvraisemblance)= P(répondeur/aisé)× P(aisé) + P(répondeur/aisé)× P(aisé)

, soit E(Cvraisemblance)= 0.27 + 0.08 = 0.35.

Le résultat suivant nous permet d'affirmer que, sous nos hypothèses, il existe une fonction de classement optimale au sens de l'erreur de classification.

Théorème 1   L'ensemble P étant probabilisé, le langage de représentation étant fixé, la règle de décision de Bayes est celle dont l'erreur de classification est minimale.

Démonstration : Soit C une fonction de classement. Pour toute description d, on a

E(d) = P(Y ¹ C / X=d) = 1 - P(Y = C / X=d)

Or CBayes est la fonction de classement qui associe à d la classe k qui maximise P(Y = k / X=d), donc, pour toute description d, CBayes est la fonction de classement qui minimise E(d).

L'erreur E(C) d'une fonction de classement est la moyenne pondérée des erreurs sur les descriptions d donc
" C   E(CBayes) £ E(C).
car CBayes minimise l'erreur pour toute description d de D.

La règle majoritaire (la plus grossière) et la règle de Bayes (la plus fine) constituent donc deux bornes naturelles en apprentissage.

S'il existe une fonction de classement correcte, i.e. qui classifie sans erreur tous les individus au vu de leur description, on a alors E(CBayes)=0. Autrement dit, la fonction de classement définie par la règle de Bayes est correcte. On remarque qu'une fonction d'erreur nulle existe si et seulement si la probabilité que des individus appartenant à des classes différentes aient des descriptions identiques est nulle. On dit dans ce cas que le problème est déterministe. Cette situation est très rare en pratique. En effet, il est rare que les paramètres descriptifs dont on dispose soient suffisants pour classifier correctement tous les individus de la population. Par exemple, deux patients peuvent avoir les mêmes symptômes et des maladies différentes, deux clients ayant les mêmes profils peuvent ou non répondre à un même mailing. De plus, on dispose rarement de données exactes et il suffit d'ajouter un peu de << bruit >> à un problème déterministe pour le transformer en un problème non déterministe.

Nous avons donc démontré dans cette section qu'il existe une règle optimale au sens de l'erreur de classification. Cependant, pour pouvoir appliquer cette règle, il faut que l'apprenant puisse disposer de probabilités que dans la plupart des problèmes réels, il est difficile d'estimer. Néanmoins, de nombreuses méthodes statistiques reposent sur la règle de Bayes, en se basant sur différentes techniques d'estimation des probabilités utiles à son application. Il est important de remarquer que ces méthodes sont parmi les plus performantes en << text mining >> (recherche d'informations dans les documents texte).

1.2 La classification supervisée
Nous commençons par préciser la distinction avec l'apprentissage non supervisé (classification, clustering), puis précisons tous les présupposés et enfin définissons la classification supervisée.

1.2.1 Apprentissage supervisé et non supervisé
Nous avons supposé que l'ensemble des classes était défini : ce n'est pas toujours le cas. Un enfant apprend à catégoriser, c'est-à-dire à associer une classe à un objet alors même que la classe en question n'a pas de définition bien précise. Comment définir ce qui relève de la catégorie << chaise >> ? Le fait de supposer qu'il existe une application Y associant une classe à chaque individu de la population P revient à éliminer ce problème.

Même lorsque l'espace des classes est bien défini, il est parfois naturel de supposer que le système apprenant doit les retrouver au cours du processus d'apprentissage. On peut par exemple espérer qu'un enfant mis en présence de mammifères (à pattes), de reptiles, d'oiseaux et de poissons saura faire les regroupements adéquats et apprendra d'un coup les classes et le moyen de les différencier. On parle dans ce cas d'apprentissage non supervisé, autrement dit, sans professeur. Nous ne nous intéresserons ici qu'au problème de l'apprentissage supervisé, c'est-à-dire pour lequel les exemples fournis au système sont déjà classés.
1.2.2 Choix du langage de description
Dans les situations réelles, il faut souvent choisir le langage de description, c'est-à-dire être capable de dégager les attributs susceptibles d'être pertinents pour le problème considéré. C'est un fait maintenant bien connu des médecins généralistes qu'on peut attraper le paludisme sans avoir jamais voyagé : il suffit pour cela d'avoir été piqué par un moustique qui a profité d'un vol direct entre une zone infestée et la France. Certains symptômes peuvent donc rendre la question << habitez-vous près d'un aéroport >> pertinente (ainsi que l'attribut correspondant). Cet attribut n'est pas le plus immédiat à dégager !

En météorologie, on peut multiplier à l'infini les attributs susceptibles d'être pertinents : considérer quelques variables physiques telles que la température, la pression atmosphérique, ...et les mesurer à autant d'endroits et de moments qu'on le souhaite. Mais se pose alors le problème de sélectionner parmi ces mesures un sous-ensemble << raisonnable >> d'attributs essentiels à la tâche qu'on s'est fixée : comment les choisir ?

La question du choix des attributs et donc du langage de description est abordée lorsqu'il faut extraire des connaissances à partir de données ou de textes [GT00].

1.2.3 la classification supervisée
Un langage de description D=D1 × ... × Dn est fixé. Les éléments de D seront notés x®, y®, ...L'ensemble {1,...,c} est lui aussi choisi. On suppose l'existence d'une loi de probabilité P sur D, cette loi est fixée mais inconnue. Elle matérialise la probabilité de rencontrer une description dans l'environnement du problème. De même, on suppose l'existence d'une loi de probabilité conditionnelle P(./.), fixée mais inconnue, qui représente la probabilité d'appartenir à une classe sachant la description. On considère donc un cadre non déterministe, en effet, à une même description peuvent correspondre plusieurs classes avec une certaine probabilité.

Définition 3   On dispose d'un échantillon S de m exemples (x®,c(x®)) tirés selon P(.,.) définie par P(x®,y)=P(x®)P(y/x®). La classification supervisée consiste à inférer une fonction de classement dont l'erreur de classification (au sens de la définition ??) est minimale.

Les termes utilisés dépendent de la discipline scientifique ou du domaine d'application, on parle de classification en reconnaissance de formes, de discrimination ou de prédiction en statistiques, d'apprentissage de concepts ou d'apprentissage inductif en Apprentissage automatique.

Dans certains problèmes réels, il faut pondérer les erreurs car celles-ci n'ont pas la même importance quant à la qualité de la procédure de classification. Par exemple, l'erreur consistant à déclarer malade un patient bien portant et l'erreur consistant à déclarer bien portant un patient malade ne doivent pas toujours être considérées comme équivalentes. On peut donc définir des mesures d'erreur introduisant des notions de coût ou de risque (voir exercices ?? et ??). Nous nous limiterons dans ce cours à l'erreur de classification, mais les méthodes étudiées peuvent être adaptées à des mesures de coût.

Il existe également des problèmes de classification supervisée pour lesquels on associe, non pas une classe, mais plusieurs classes. C'est le cas, par exemple, pour la recherche de complications associée à une maladie dans le cas où il peut y avoir plusieurs complications. La fonction cherchée est alors une fonction de l'espace des descriptions D dans l'ensemble des parties de {1, ..., c}. Il existe alors plusieurs façons de définir l'erreur d'une procédure de classification.

Enfin, nous nous sommes limités au problème de la classification supervisée. Il est fréquent de rencontrer des problèmes ou, au lieu de déterminer une classe, on doit estimer une valeur continue. On parle alors d'estimation ou de régression. Il faut alors modifier la définition de l'erreur. Une solution est de considérer l'erreur quadratique (carré de la différence entre valeur prédite et valeur attendue). Nous aborderons ces notions dans la section sur les réseaux de neurones.

1.2.4 bien classer et bien prédire
Au vu d'un échantillon, il s'agit donc d'inférer une procédure de classification. On souhaite inférer une procédure dont l'erreur de classification est minimale, c'est-à-dire telle que la probabilité qu'un exemple tiré aléatoirement soit mal classé par la procédure soit minimale. On s'intéresse, par conséquent, à générer des procédures ayant un bon pouvoir prédictif, soit encore, à des procédures capables de classer de nouveaux exemples (nouveaux au sens de non présents dans l'échantillon). Cependant, l'apprenant n'a pour donnée que l'échantillon et il est possible pour lui de générer une procédure qui classifie bien tous les exemples de l'échantillon mais qui ait un mauvais pouvoir de prédiction. En effet, soit la procédure de classification suivante :

Exemple 3   On mémorise tous les exemples de l'échantillon d'apprentissage dans une table, lorsqu'une nouvelle description est présentée au système, on effectue une recherche dans la table, si la description correspond à une description existante dans la table (description d'un exemple de l'échantillon), on retourne la classe correspondante, sinon on retourne une classe au hasard.

Cette procédure ne fait aucune erreur sur les exemples de l'échantillon, par contre, on se doute que son pouvoir prédictif sera très mauvais. Notons que, pour certains problèmes réels, il peut être intéressant de déterminer une procédure dans le seul but de bien classer l'échantillon. En effet, il peut être utile d'avoir une procédure simple et efficace qui calcule la classe associée à une description en évitant d'effectuer des recherches coûteuses (pour chercher la classe) dans une grande base de données. Ici, l'objectif d'un système d'apprentissage est de construire une procédure de classification qui soit non seulement correcte sur l'échantillon mais ayant en plus un bon pouvoir de prédiction sur de nouveaux exemples. Il sera demandé à la procédure de classification induite au moins de dépasser le pouvoir prédictif de la procédure majoritaire (qui associe à toute description la classe la plus fréquente). Ceci suppose que le langage de description est suffisamment riche pour permettre une prédiction. On dit alors que le langage de représentation possède un << pouvoir prédictif >>. En tout état de cause, un système d'apprentissage automatique ne peut faire mieux que ce que lui permet le langage de description choisi.

Nous introduisons maintenant la définition de l'erreur apparente et étudions les relations entre erreur réelle et erreur apparente.

Définition 4   Soit S un échantillon et C une procédure de classification, le taux d'erreur apparent sur S est Eapp(C)=err/ S où err est le nombre d'exemples de S qui sont mal classés par C et S est le cardinal de S.

Rappelons (Définition ??) que l'erreur réelle ou erreur de classification E(C) est la somme pondérée des probabilités d'erreur sur l'ensemble des descriptions d de D. L'erreur réelle est indépendante de l'échantillon alors que l'erreur apparente est mesurée sur l'échantillon. Apprendre, c'est trouver une procédure de classification C qui minimise E(C), or l'apprenant n'a accès qu'à l'erreur apparente Eapp(C) mesurée sur S. On peut, cependant, démontrer que, lorsque la taille de l'échantillon tend vers l'infini, l'erreur apparente converge -en probabilité car les éléments de S sont supposés tirés aléatoirement - vers l'erreur réelle, soit :
lim
 
S ® ¥
Eapp(C)=E(C)
Mais, en général, on ne dispose que d'un échantillon de taille trop petite pour que ce résultat puisse être utilisé. Le problème est donc de concevoir des méthodes ou algorithmes qui vont générer des procédures de classification d'erreur apparente petite tout en assurant une erreur de classification petite.

1.3 Les méthodes de classification supervisée

La classification supervisée est une tâche difficile pour plusieurs raisons : Commençons d'abord par présenter une méthode simple de classification supervisée basée sur la formule de Bayes.

1.3.1 Le classifieur naïf de Bayes

Soit D un langage de description, soit {1,...,c} l'ensemble des classes, sous les hypothèses usuelles d'existence de lois de probabilité, la règle de classification de Bayes est la procédure qui, à toute description d de D associe :
CBayes(d) = k Î {1,...,c} argmax P(k/d) = k Î {1,...,c} argmax P(d/k)× P(k)     (1.2)
où k argmax f(k) retourne la valeur de k qui maximise f. Mais, en règle générale, les quantités P(d/k) et P(k) ne sont pas connues. On suppose que D est un produit cartésien de domaines, on suppose également disposer d'un échantillon S d'exemples (x®,c(x®)). On souhaite classer un élément d®=(d1,...,dn). La règle de classification de Bayes s'écrit :
CBayes(
®
d
 
) = k Î {1,...,c} argmax P((d1,...,dn)/k)× P(k)     (1.3)

Pour rendre la méthode effective, on souhaite remplacer P((d1,...,dn)/k) et P(k) par des estimations faites sur l'échantillon S. Pour toute classe k, on estime P(k) par P^(k) qui est la proportion d'éléments de classe k dans S. Par contre, l'estimation des P((d1,...,dn)/k) est difficile car le nombre de descriptions possibles peut être très grand et il faudrait un échantillon S de taille trop importante pour pouvoir estimer convenablement ces quantités. On fait donc l'hypothèse simplificatrice suivante : les valeurs des attributs sont indépendants connaissant la classe. Cette hypothèse permet d'utiliser l'égalité suivante :
P((d1,...,dn)/k) =
 
Õ
i Î {1,...,n}
P(di/k)     (1.4)
maintenant, il suffit d'estimer, pour tout i et toute classe k, P(di/k) par P^(di/k) qui est la proportion d'éléments de classe k ayant la valeur di pour le ième attribut. Finalement, le classifieur naïf de Bayes associe à toute description d la classe
CNaiveBayes(
®
d
 
) = k Î {1,...,c} argmax
 
Õ
i Î {1,...,n}
^
P
 
(di/k) ×
^
P
 
(k)     (1.5)
expression dans laquelle les probabilités sont estimées sur l'échantillon S. Cette méthode est simple à mettre en oeuvre. Bien qu'elle soit basée sur une hypothèse fausse en général (les attributs sont rarement indépendants), elle donne cependant de bons résultats dans les problèmes réels. Elle fournit un seuil de performance pour d'autres méthodes. Le domaine pour lequel le classifieur de Bayes naïf est performant est la classification automatique de textes qui est présentée dans l'exercice ??.

1.3.2 Méthodes paramétriques et non paramétriques

Nous avons supposé l'existence de lois de probabilité fixées mais inconnues. Le classifieur naïf de Bayes suppose que les probabilités de certains événements peuvent être estimées par leurs fréquences et fait une hypothèse forte d'indépendance des attributs. En statistiques, on classe habituellement les méthodes d'apprentissage selon les hypothèses que l'on fait sur les lois de probabilité. Si elles font partie d'une famille paramétrée de distributions, on parlera de problèmes ou de méthodes paramétriques. Par exemple, si l'on sait que P est une distribution normale, il suffit de connaître deux paramètres, sa moyenne m et son écart-type s, pour identifier P totalement. Il s'agit alors de mettre en oeuvre des techniques permettant d'estimer ces paramètres pour avoir une bonne approximation de P pour ensuite déterminer une procédure de classification. Les méthodes paramétriques ont été développées en statistiques dans les années 20-30, par Fischer en particulier.

Lorsqu'on ne fait aucune hypothèse a priori sur la distribution P, on parle de problèmes et de méthodes non paramétriques. Les problèmes à résoudre sont alors plus complexes et les premières méthodes développées en statistiques remontent aux années 60. Comme exemple de méthodes non paramétriques, on peut citer les méthodes des k-plus proches voisins et des noyaux de Parzen. Ces deux méthodes sont basées sur des notions de proximité entre éléments de D, la classe attribuée à une nouvelle description se fait en fonction des classes des descriptions proches dans l'échantillon (pour une présentation informelle des plus proches voisins, voir [GT00]). Les méthodes développées en apprentissage automatique (arbres de décision, réseaux de neurones, algorithmes génétiques) sont également non paramétriques.

1.3.3 Minimiser l'erreur apparente

En classification supervisée, il faut choisir une fonction de classement au vu d'un échantillon S. Nous sommes confrontés aux deux difficultés suivantes : Ces deux difficultés nous amènent à limiter la recherche d'une fonction à un espace d'hypothèses C : C est un ensemble de procédures de classification de D dans {1,...,c}. En effet, si on limite le nombre de fonctions, on diminue la complexité des calculs et ceux-ci deviennent envisageables. De plus, restreindre l'espace des hypothèses peut permettre d'éviter des hypothèses trop spécialisées comme le montre les exemples suivants :

Exemple 4   Si l'espace des hypothèses n'est pas restreint, il est toujours possible de choisir la procédure de classification citée précédemment (chercher dans la table et tirer à pile ou face sinon) pour laquelle l'erreur apparente est nulle, alors que l'erreur réelle peut être grande.

Exemple 5   Supposons que l'on recherche une fonction polynôme dont la courbe représentative passe par n points. Supposons que ces n points soient alignés. En raison des erreurs de mesure et des approximations faites sur les coordonnées, la recherche d'une fonction polynôme dont la courbe représentative passe par les n points sera, en général, une fonction de degré n-1 alors qu'il existe une fonction polynôme de degré 1 dont la courbe passe << presque >> par les n points. Si l'espace de recherche est restreint, par exemple, à l'ensemble C des polynômes de degré inférieur ou égal à 2, il est probable que l'on puisse trouver une bonne solution.

Exemple 6   Supposons que l'on dispose d'un programme informatique capable de traduire en français un livre donné d'environ 200 pages écrit en anglais. Si le programme en question comporte 400 pages de code, on peut légitimement soupçonner qu'il contient à la fois les versions françaises et anglaises du livre en question et qu'il ne sera d'aucune aide pour traduire un autre livre. C'est-à-dire qu'il n'aura vraisemblablement rien appris ni du français, ni de l'anglais. Mais si le programme en question ne comporte qu'une vingtaine de pages de code, on peut penser qu'il contient nécessairement certains éléments de connaissance concernant ces deux langages. Autrement dit, si l'on veut concevoir un traducteur automatique à partir d'un échantillon limité de traductions déjà réalisées, on a intérêt à le choisir dans un ensemble restreint de programmes (ceux de moins de 20 pages de code).

Le problème de la classification supervisée peut se réécrire : sélectionner dans un ensemble C de procédures de classification une procédure de classification C telle que l'erreur apparente Eapp(C) soit petite, tout en essayant de s'assurer que l'erreur réelle E(C) soit petite.

Soit CBayes la procédure de classification de Bayes qui est la procédure d'erreur de classification minimale dans l'ensemble de toutes les fonctions de D dans {1,...,c}. L'erreur de classification E(CBayes) est une borne indépassable (voir Théorème ??) qui représente d'une certaine manière la difficulté intrinsèque du problème. Dans la plupart des cas pratiques CBayes n'appartient pas C. Soit Copt la procédure optimale de C au sens de la erreur de classification, c'est-à-dire la procédure appartenant à l'ensemble C qui est d'erreur de classification minimale. C étant fixé, le problème est de trouver ou d'approcher Copt, ce qui n'est pas facile en raison du problème :

Problème de l'estimation du taux d'erreur : << On ne peut, à la fois sélectionner un classifieur à l'aide d'un ensemble d'apprentissage et juger de sa qualité avec ce même ensemble >>.
En effet, pour le choix de C, une solution est :
Choisir la procédure Cemp qui minimise l'erreur apparente
Mais, on n'a alors que peu d'indication sur l'erreur réelle E(Cemp) et donc sur la proximité de Cemp et Copt. Les seuls résultats théoriques dont on dispose sont des résultats de convergence (en probabilité) de Eapp(Cemp) vers E(Copt) lorsque la taille de l'échantillon tend vers l'infini, sous certaines conditions sur C. Ce résultat a peu d'implications pratiques car on ne dispose, en général, que d'échantillons de tailles limitées. La minimisation de l'erreur apparente ne peut donner de bons résultats que lorsque l'espace des hypothèses est bien choisi, choix étudié dans la section suivante.

1.3.4 Choix de l'espace des hypothèses

Il est important de bien choisir C pour que le système puisse inférer une << bonne >> solution. Pour cela, on introduit une notion de << capacité >> d'un espace d'hypothèses. Dans le cas de problèmes discrets, la capacité de C est son cardinal. Dans le cas d'espaces infinis, la capacité peut être définie comme égale à la VC-dimension (ou dimension de Vapnik et Chervonenkis). La définition de cette dimension sort du cadre de ce cours, elle peut être trouvée dans les notes de cours de dea [Den00] et dans l'ouvrage fondamental de Vapnik [Vap98]. Pour le choix de l'espace d'hypothèses, nous sommes confrontés au problème suivant : La plupart des algorithmes utilisés effectuent la recherche d'une procédure qui minimise l'erreur apparente dans un espace d'hypothèses préalablement choisi. La situation est en fait plus complexe car les algorithmes utilisent des heuristiques qui orientent la recherche dans l'espace d'hypothèses. En effet, la recherche de Cemp peut être coûteuse en temps de calcul. Dans le cas des réseaux de neurones (voir Chapitre ??), le choix de l'espace des hypothèses est le choix d'une bonne architecture pour le réseau (capacité ni trop grande, ni trop petite), ensuite, on recherche une bonne solution en cherchant à minimiser l'erreur apparente.

Cependant, dans la plupart des situations pratiques, on peut considérer des suites emboîtées d'ensembles de procédures de classification
C1 Í C2 Í ... Í Ck Í ...
où k représente une mesure de complexité du système d'apprentissage (taille des arbres de décision, taille du réseau de neurones, ...) liée à la capacité : plus k est grand, plus la capacité de l'espace est grande. Il faut alors trouver la valeur du paramètre de complexité k telle que Ck,emp, la procédure de Ck qui minimise l'erreur apparente, ait la plus faible erreur réelle possible. Il existe en général un bon compromis ; en effet, lorsque k augmente, l'erreur réelle E(Ck,emp) diminue lentement, se stabilise, puis croît lentement. Le bon compromis se situe dans la région où l'erreur réelle est stable. Ceci est illustré par une figure représentant l'évolution des erreurs réelle et apparente dans le cas d'un système d'apprentissage pour la reconnaissance de caractères utilisant des arbres de décision (voir figure ??).



Figure 1.2 : Erreur réelle et erreur apparente pour des données réelles de reconnaissance de caractères ([BFOS84])

Une solution est de minimiser l'erreur apparente en complexifiant de plus en plus l'espace de recherche. Par exemple, on peut construire des arbres de décision (voir Chapitre suivant) de plus en plus grand avec l'objectif de minimaliser l'erreur apparente. À la fin de ce processus, l'arbre obtenu est peut être trop spécialisé (erreur apparente faible mais erreur réelle grande). On essaie alors de diminuer sa taille en diminuant l'erreur réelle (étape d'élagage). Ceci suppose que l'on soit capable d'estimer l'erreur réelle (voir section suivante). Une telle technique peut être appliquée aux réseaux de neurones. Enfin, la méthode dite de << minimisation du risque structurel >> consiste à choisir conjointement le bon compromis entre erreur réelle et capacité de l'espace d'hypothèses. Cette méthode est mise en oeuvre par les machines à support de vecteurs (voir [CST00]).

1.4 Estimer l'erreur réelle

Lorsque l'on apprend à partir d'un échantillon, se pose immédiatement la question de la pertinence statistique de la procédure induite. Supposons, par exemple, que nous disposions d'un échantillon de 500 patients tels que 100 d'entre eux soient malades. Une procédure qui prédit toujours << bien portant >> (c'est la procédure majoritaire) fait une prédiction correcte dans 80% des cas. Tout système d'apprentissage qui prétend apporter un éclairage sur les données doit faire mieux. Il faut donc être capable d'estimer la qualité d'une procédure induite par un système à partir d'un échantillon. Nous avons également signalé, dans la section précédente, que l'estimation de l'erreur réelle pouvait être utilisée par les algorithmes pour éviter la surspécialisation.

1.4.1 Utilisation d'un ensemble Test
L'idée est de disposer d'un ensemble permettant de tester la qualité de la procédure de classification induite. On partitionne l'échantillon en un ensemble d'apprentissage S et un ensemble test T. La répartition entre les deux ensembles doit être faite aléatoirement. On effectue l'apprentissage à l'aide de l'ensemble S et on génère une procédure de classification C. L'estimation E^(C) de l'erreur réelle E(C) est alors l'erreur apparente de C mesurée sur l'ensemble test T, soit
^
E
 
(C)=
malclassés(T)
T
    (1.6)
où malclassés(T) est l'ensemble des éléments de T mal classés par la procédure C. L'estimation est faite sur un ensemble indépendant de celui qui a servi à l'apprentissage ce qui permet de supposer que l'erreur apparente sur l'ensemble test est une bonne estimation de l'erreur réelle. Cependant, comme la qualité de l'apprentissage augmente avec la taille de l'ensemble d'apprentissage et que de même, la précision de l'estimation augmente avec la taille de l'ensemble test, cette méthode ne donne de bons résultats que lorsque l'échantillon est << suffisamment >> grand pour pouvoir être divisé en deux échantillons de tailles significatives. Il existe peu de résultats théoriques sur les tailles d'échantillon nécessaires pour utiliser cette méthode, on ne dispose que de résultats empiriques qui dépendent du problème (souvent, plusieurs centaines d'exemples). La répartition de l'échantillon entre les deux ensembles se fait en général dans des proportions 1/2, 1/2 pour chacun des deux ensembles ou 2/3 pour l'ensemble d'apprentissage et 1/3 pour l'ensemble test.

Le lecteur est invité à traiter les exercices ??, ??, ?? et ??. Dans ces exercices sont présentés les résultats statistiques les plus simples sur l'estimation de l'erreur à l'aide d'un ensemble test. En particulier, la notion d'intervalle de confiance est introduite. Cette notion permet de produire des affirmations de la forme : << l'erreur réelle appartient à tel intervalle avec telle confiance >>.

Dans les problèmes réels d'extraction de connaissances à partir de données, on dispose en général de jeux de données de taille suffisante pour utiliser un ensemble test. Si l'algorithme utilisé utilise, pour son fonctionnement, une estimation de l'erreur réelle (élagage, choix de l'architecture du réseau, réglage de paramètres), il est alors nécessaire de posséder trois ensembles : Lorsque, dans l'exécution de l'algorithme, celui-ci sollicite une estimation de l'erreur réelle, on utilise l'ensemble test T. L'ensemble de validation permet, quant à lui, d'estimer la qualité de la procédure produite en sortie.

1.4.2 Techniques de re-échantillonage
La méthode présentée dans la section précédente n'est pas toujours applicable. En effet, pour certains domaines d'applications, les données sont rares. Et donc, il arrive que l'échantillon de travail soit trop petit pour que l'on puisse envisager de sacrifier des éléments pour tester le classifieur. Comment peut-on à la fois apprendre sur tous les exemples et obtenir malgré tout une estimation satisfaisante du taux d'erreur ?

L'objectif est toujours d'estimer l'erreur réelle d'une procédure de classification C produite par un algorithme A sur un échantillon S. Une première méthode pour estimer cette erreur réelle est la validation croisée. Cette méthode est présentée dans l'algorithme suivant où k est un paramètre :

validation croisée - k fois
Partitionner S aléatoirement en k sous-ensembles S1,...,Sk
pour tout i de 1 à k
appliquer A à l'échantillon S - Si et générer Ci
calculer e^i erreur apparente de Ci sur Si
Retourner E^(C)=å1 leq i £ k e^i/k comme estimation de E(C)

Cette méthode est très largement utilisée quoique ses justifications théoriques soient encore discutées en statistique. Les valeurs usuelles pour k sont k=10 (ten-fold cross validation) ; pour les petits ensembles on peut choisir k= S. Il faut noter que la méthode est coûteuse en temps de calcul car il faut effectuer autant k sessions d'apprentissage, ce qui peut être rédhibitoire si le temps de calcul de l'algorithme est long.

La deuxième méthode est celle du bootstrap. Étant donné un échantillon S de taille n, on tire avec remise un ensemble d'apprentissage de taille n (un élément de S peut ne pas appartenir à l'ensemble d'apprentissage, ou y figurer plusieurs fois), l'ensemble test est S. L'estimation de l'erreur réelle est alors la moyenne des erreurs apparentes obtenues pour un certain nombre d'itérations de l'algorithme d'apprentissage.

Ces deux méthodes fournissent de bons estimateurs de l'erreur réelle mais sont très coûteuses en temps de calcul. Elles sont très utiles pour les << petits >> échantillons.

D'autres problèmes, importants pour l'apprentissage automatique, sont étudiés d'un point de vue statistique. Il s'agit par exemple de comparer deux procédures de classification induites à partir d'un même échantillon (voir exercice ??) ou de comparer deux systèmes d'apprentissage.

1.5 Résumons
Précédent Index Suivant