Il est possible d'avoir une procédure qui classifie bien tous les exemples de l'échantillon mais qui ait un mauvais pouvoir de prédiction. Soit la procédure de classification suivante :
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. 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 représentation choisi (les descriptions) est suffisamment riche pour permettre une prédiction. On dit alors que le langage de représentation possède un ``pouvoir prédictif''. Ceci peut ne pas être toujours le cas si, par exemple, on dispose de symptômes non pertinents pour une maladie. Le langage de représentation choisi est donc fondamental pour la qualité du système d'apprentissage. Dans le choix de ce langage pour résoudre des problèmes concrets, on est, par exemple, amené à se poser des questions du type : quels sont les paramètres nécessaires pour prédire l'évolution des marchés financiers ? Le problème du choix du langage de représentation n'est pas abordé dans ce cours. Nous supposons que le langage est fixé et possède un certain pouvoir prédictif. En tout état de cause, un système ne peut faire mieux que ce que lui permet le langage choisi.
Nous introduisons maintenant la définition de l'erreur apparente et étudions les relations entre erreur réelle et erreur apparente.
Rappelons (Définition 2) que l'erreur réelle ou
probabilité d'erreur 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). On peut démontrer que :
Mais, en général, on
ne dispose que d'un échantillon de taille trop petite pour que ce
résultat puisse être utilisé. Donc, apprendre, c'est sélectionner dans
un ensemble 
de procédures de classification une procédure
de classification 
telle que l'erreur apparente
soit petite, tout en essayant de s'assurer que
l'erreur réelle 
soit petite. Choisir telle que
soit minimale n'est pas nécessairement la bonne
stratégie comme le prouve l'exemple suivant :
De plus, l'erreur apparente est, en général, une
version très (trop) optimiste de l'erreur réelle . En
effet, on rencontre le problème du biais inductif que l'on peut
énoncer ainsi :
Problème du biais inductif : ``On ne peut, à la fois sélectionner avec un ensemble d'apprentissage et juger avec ce même ensemble''.
Nous nous sommes limités à la probabilité d'erreur. Il faut noter que dans certains problèmes pratiques, il faut pondérer les erreurs car celles-ci n'ont pas nécessairement 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 être toujours 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 4,5). Nous nous limiterons dans ce cours à la probabilité d'erreur, mais les méthodes étudiées peuvent être adaptées à des mesures plus sophistiquées.
Le problème est donc d'extrapoler l'erreur réelle à partir de l'erreur apparente. Nous allons étudier ce problème dans les deux paragraphes suivants.