Dans le paragraphe précédent, nous avons mentionné différentes méthodes pous estimer a posteriori que le résultat de l'apprentissage a une certaine valeur prédictive. Mais, il est également souhaitable d'avoir certaines garanties a priori, pour ne pas faire tourner longuement un système d'apprentissage pour constater après coup que la valeur prédictive de la procédure de classification induite est faible. En effet, certains systèmes d'apprentissage sont très couteux en temps de calcul (par exemple, les réseaux de neurones) et il n'est pas envisageable, en général, de recommencer plusieurs fois la phase d'apprentissage. Malheureusement, les résultats théoriques sont peu nombreux et les garanties a priori restent faibles.
Soit 
la procédure de classification induite par la règle de décision de Bayes, la probabilité d'erreur 
est une borne indépassable (voir Théorème 1) qui représente d'une certaine manière la difficulté intrinsèque du problème. Soit 
l'ensemble des procédures de classification devant être explorées par le système d'apprentissage.
L'ensemble des procédures de classification est fixé. Dans la
plupart des cas pratiques n'appartient pas .
Soit 
la procédure optimale de au sens de la
probabilité d'erreur. étant fixé, le problème est de
trouver ou d'approcher , ce qui n'est pas facile en raison du
biais inductif. En effet, si on sélectionne 
qui minimise le
taux d'erreur apparent 
, on n'a que peu d'indication
sur l'erreur réelle 
et donc sur la proximité de
et . Les seuls résultats théoriques dont on dispose sont des
résultats de convergence (en probabilité) de vers
lorsque la taille de l'échantillon tend vers l'infini,
sous certaines conditions sur . Ces conditions sont :
l'ensemble des procédures de classification est fini ou
possède une dimension de Vapnik Chervonenkis finie (Vapnik
Chervonenkis [16]).
Choisir l'ensemble des procédures de classification. Il est
important de bien choisir pour que le système puisse
inférer une ``bonne'' solution. Mais, si l'ensemble est
trop petit (ou sa dimension de Vapnik Chervonenkis trop petite),
peut être éloignée de et donc, il sera
impossible que le système donne de bons résultats. Si l'ensemble
est trop grand (ou sa dimension de Vapnik Chervonenkis trop
grande), la recherche de devient plus complexe (le problème
est alors un problème algorithmique, les problèmes sont souvent NP
complets) et le biais inductif devient trop important (erreur
apparente trop optimiste). Dans la plupart des situations pratiques,
on peut considérer des suites emboitées d'ensembles de procédures de
classification
où k représente une mesure de
complexité (taille des arbres de décision, taille du réseau de
neurones, ...). Il faut alors trouver la valeur du paramètre de
complexité k telle que 
, la procédure de 
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 
diminue lentement, se
stabilise, puis croit 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
2.2).