Une extension du modèle du perceptron

Le modèle de perceptron étudié par Rosenblatt, Minski et Papert est un peu plus compliqué que celui qui a été présenté dans le cours. Ces auteurs supposent qu'entre la rétine (les cellules d'entrées) et la cellule de décision (cellule de sortie) se trouvent un certain nombre de cellules d'association. Ces cellules intermédiaires effectuent un traitement préliminaire sur certaines cellules de la rétine et transmettent le résultat de ce traitement à la cellule de décision. Les sorties des cellules d'association constituent une nouvelle rétine qui représentent les entrées de la cellule de décision.

Les cellules d'association peuvent calculer a priori n'importe quelle fonction booléenne. Mais si l'on ne restreint pas les traitements qu'elles peuvent effectuer, le modèle du perceptron perd tout son intérêt puisque toute fonction booléenne est disponible directement. Une manière naturelle de restreindre les cellules d'association est de considérer qu'elles ne peuvent dépendre que d'un petit nombre de cellules de la rétine. On peut par exemple supposer que les cellules d'association ne peuvent dépendre que d'au plus d cellules de la rétine (perceptron à ``domaine borné'') ou, dans un contexte géométrique, qu'elles ne peuvent dépendre que de cellules de la rétine au plus distantes de d (perceptron à ``diamètre limité''). Plus précisément, dans le cas d'une rétine rectangulaire, on définira la distance de deux cellules définies par leurs numéros de lignes et de colonnes par d((l,c),(l',c')) = |l-l'|+|c-c'|.

 
Figure 4.3: Un perceptron à domaine borné (d=2) qui reconnaît si une cellule et une seule est active

1. On suppose dans les questions ci-dessous que la rétine est linéaire.
   1. Montrer qu'un perceptron à domaine borné (avec d=2) peut reconnaître des figures symétriques par rapport au centre de la rétine.
   2. Montrer qu'un perceptron à diamètre limité (avec d=1) peut reconnaître des figures connexes.
   3. Montrer qu'un perceptron à domaine borné (avec d=2) peut reconnaître les entrées possédant exactement m cellules actives. On pourra s'inspirer de l'exemple ci-dessus.

   Cette extension semble intéressante puisque des fonctions ``naturelles'' qui ne sont pas calculables dans le modèle de base le deviennent avec cette variante. Malheureusement, on peut montrer que le gain n'est pas aussi important que les résultats précédents pourraient le laisser espérer.

2. Montrer qu'aucun perceptron à diamètre limité ne peut reconnaître les figures connexes (c'est-à-dire dont les entrées à 1 forment un seul morceau) sur une rétine rectangulaire.

   Indication : Supposer qu'un perceptron à diamètre limité d peut reconnaître les figures connexes et considèrer, sur une rétine rectangulaire de dimension au moins 5x(d+2), les quatre figures suivantes (où les entrées à 1 sont figurées en noir) :

    
   Figure 4.4: Aucun perceptron à diamètre limité ne peut apprendre la connexité