Démonstration : Soit n+1 le nombre d'entrées du perceptron. On suppose que chaque exemple possède une n+1-ème coordonnée égale à 1.
On note 
(resp. 
) l'ensemble des exemples de S pour lesquels le
perceptron doit calculer la valeur 1 (resp. 0).
L'hypothèse signifie qu'il existe un hyperplan
de l'espace 
qui sépare de .
Il existe donc un vecteur 
tel que :
et
Comme S est fini, cela implique qu'il existe un réel d strictement positif tel que :
Pour tout Y de S, on a donc :
Figure 3.6: d est inférieur à la distance minimale d'un point de l'échantillon
à l'hyperplan séparateur.
Soit M un majorant de 
.
Soit 
les valeurs d'initialisation des
poids synaptiques.
Supposons que l'algorithme d'apprentissage ne s'arrête pas. Nous allons montrer que cette hypothèse est absurde.
On note 
les états successifs différents des coefficients
synaptiques (c'est-à-dire que pour tout i, on a 
). Comme
on a supposé que la présentation des exemples est
équitable et que l'algorithme ne s'arrête pas, cela implique en
particulier qu'il y a un nombre infini de .
Nous allons calculer des bornes pour 
et 
.
Passage de à 
:
pour lequel 
.
Donc V.Y > d et 
(renforcement).
D'où
D'autre part,
pour lequel 
.
On a donc : V.Y < -d et 
(inhibition).
D'où
et
Finalement, quelque soit le cas envisagé et pour tout 
,
On en déduit que pour tout 
,
Comme d>0, il existe un entier 
tel que 
pour
tout 
.
Donc, pour ,
ce qui est impossible. En effet, le terme de gauche est un polynôme de degré 2 en i alors que le terme de droite est linéaire en i.
L'inconvénient majeur de cet algorithme est que si l'échantillon présenté n'est pas linéairement séparable, l'algorithme ne convergera pas et l'on aura aucun moyen de le savoir. On pourrait penser qu'il suffit d'observer l'évolution des poids synaptiques pour en déduire si l'on doit arrêter ou non l'algorithme. En effet, si les poids et le seuil prennent deux fois les mêmes valeurs sans que le perceptron ait appris et alors que tous les exemples ont été présentés, cela signifie d'après le théorème précédent que l'échantillon n'est pas séparable. Et l'on peut penser que l'on peut borner les poids et le seuil en fonction de la taille de la rétine. C'est vrai mais les résultats de complexité énoncés ci-dessous (sans démonstration) montrent que cette idée n'est pas applicable en pratique.
Ces résultats sont assez décevants. Le premier montre que l'on peut borner les poids synaptiques en fonction de la taille de la rétine, mais par un nombre tellement grand que toute application pratique de ce résultat semble exclue.
Le dernier résultat montre en particulier que l'algorithme d'apprentissage peut nécessiter un nombre exponentiel d'étapes (en fonction de la taille de la rétine) avant de s'arrêter. En effet, les poids ne varient qu'au plus d'une unité à chaque étape.
Deux idées pour accélérer la vitesse d'apprentissage :
et
remplacer 
par 
. On peut prendre par
exemple décroissant vers 0 au fur et à mesure du
déroulement de l'apprentissage.
On peut remarquer que ces deux méthodes impliquent l'utilisation de poids réels.
Même lorsque l'algorithme d'apprentissage du perceptron converge, rien ne garantit que la solution sera robuste, c'est-à-dire qu'elle ne sera pas remise en cause par la présentation d'un seul nouvel exemple.
Figure 3.7: Un nouvel exemple peut remettre en cause le perceptron appris.
Pire encore, cet algorithme n'a aucune tolérance au ``bruit'' : si du bruit, c'est-à-dire une information mal classée, vient perturber les données d'entrée, le perceptron ne convergera jamais. En particulier, les problèmes non-déterministes, c'est-à-dire pour lesquels une même description peut représenter des éléments de classes différentes ne peuvent pas être traités à l'aide d'un perceptron.
Figure 3.8: Apprentissage en présence de bruit
On peut souhaiter qu'un perceptron ait la capacité d'apprendre ``approximativement'' des classes qui ne sont pas linéairement séparables.