CHAPITRE 12

Conclusions

En étudiant ce livre, le lecteur aurapu constater la richesse des méthodes proposées pour résoudre des problèmes aussi variés. Dans ce dernier chapitre nous tenterons un bilan très provisoire de ce sujet en plein développement, en indiquant quelques-unes des voies d'accès bibliographiques vers les nombreuses applications des réseaux d'automates. Mais une petite mise au point s'impose peut-être maintenant concernant la portée des modèles biologiques construits à partir des réseaux d'automates, de même que sur l'évaluation de leur utilité dans les applications.

12-1 DU BON USAGE DES RESEAUX

12-1-1 Portée des modèles

Comme nous l'avons laissé entendre dans l'introduction, les "grands" réseaux (grands par le nombre de leurs automates)sont utilisés dans une perspectivede systèmes désordonnés. Nous avons évoqué dans ce livre des modèles du système nerveux ou du génome qui restent très simplifiés, non seulement par rapport à la réalité biologique, mais même par rapport à ce que nous savons aujourd'hui de ces systèmes. Notre excuse est claire:

*Nous ne connaissons pas, et nous avons très peu d'espoir de jamais connaître le détail complet des interactions entre les différents éléments du système.

*Même si celles-ci nous étaient connues, il faudrait des temps exponentiellement longs pour décrire l'espace des configurations accessibles au système.

La question qui se pose est alors d'apprécier la portée de modèles construits sur des approximations aussi brutales. La justification que nous apportons est une conjecture basée sur le concept de classes d'universalité. Cette idée est issue de la méthode du groupe de renormalisation appliquée aux transitions de phase. Que le lecteur se rassure, il n'est pas question de décrire ici cette méthode, mais de discuter ses résultats. La physique donne l'exemple de nombreuses transitions de phases: fusion, liquéfaction, transition dans les systèmes magnétiques,transition métal- isolant, supraconductivité... A une température déterminée, la température de transition, plusieurs grandeurs physiques caractéristiques du système varient d'une manière discontinue. Le paradoxe est que les lois d'échelle décrivant la variation de ces grandeurs au voisinage du point critique sont les mêmes pour des transitions de nature apparemment très différentes, alors que les températures de transition, elles, semblent imprévisibles. L'ensemble des transitions obéissant aux mêmes lois d'échelle forme une classe d'universalité. La méthode du groupe de renormalisation a permis de prédire ces classes d'universalité, ainsi que les lois d'échelle observées. Ces classes ne dépendent que de la dimension de l'espace et de la dimension du paramètre d'ordre. Une des conséquences de cette universalité est que tout modèle mathématique respectant ces dimensions permet de prédire le comportement qualitatif du système réel ainsi que les lois d'échelle auxquelles il obéit. Ces notions ont été étendues aux systèmes désordonnés (transitions de percolation par exemple) et aux systèmes dynamiques continus (transitions vers le chaos).

Notre conjecture, en appliquant les réseaux d'automates aux systèmes vivants, est que la description mathématique simplifiée et le système réel appartiennent à la même classe d'universalité. En conséquence, certaines propriétés prédites par le modèle restent indépendantes des détails de la description complète du système. Parmi ces propriétés "universelles" figurent les propriétés qualitatives, par exemple l'existence d'attracteurs ou de régimes chaotiques, ainsi que les propriétés semi-quantitatives comme les lois d'échelle. Dans l'expression d'une loi d'echelle du type

m = A Na

l'exposant a a de bonnes chances d'être correctement prédit par la théorie. Par contre le préfacteur A lui n'est pas universel et dépend des détails de la modélisation.

Après avoir déterminé ce que l'on peut légitimement attendre de ces modèles, il est facile de préciser le type d'information qu'ils ne pourront jamais donner. Dans la mesure où les propriétés prédites sont peu sensibles à la nature des interactions, aucune conclusion ne pourra être obtenue sur celles-ci. Le fait qu'un modèle mathématique basé sur certaines hypothèses anatomiques de connectivité entre cellules "marche", c'est-à-dire qu'il prédise des comportements qualitatifs ou des lois d'échelle vérifiées expérimentalement, ne valide donc pas ces hypothèses.

On peut, dans ce sens, considérer la modélisation par réseaux d'automates comme complémentaire de l'approche de la biologie moléculaire, dans la mesure où cette dernière s'attache justement à mettre en évidence les mécanismes précis des interactions au niveau moléculaire.

12-1-2 Conditions d'application des algorithmes

L'approche des réseaux d'automates permet d'aborder des applications aussi variées que le traitement du signal, l'optimisation combinatoire ou les systèmes experts. Pour chaque cas particulier le réseau utilisé peut être différent, mais bien des concepts utilisés sont communs à toutes ces méthodes. Les avantages essentiels de cette approche, outre cette unité conceptuelle, sont la relative facilité de programmation et la possibilité d'utiliser des algorithmes parallèles.

Cela ne veut pas dire qu'il s'agisse d'une panacée universelle, applicable sans discernement. Quelques mises en garde s'imposent:

*Il n'existe pas d'algorithme universel, optimum quelle que soit l'application.

*Pour un problème particulier, un algorithme classique peut être plus performant que les algorithmes réseaux:l'algorithme de Lin-Kernighan pour le voyageur de commerce sembletoujours actuellement le meilleur.

*Les algorithmes "canoniques", comme celui de Hopfield ou comme le recuit simulé, sont rarement adaptés aux problèmes concrets de taille réelle. On utilise plutôt dans ces cas des variantes mieux adaptées.

*Rappelons que la mise en pratique d'un algorithme nécessite le choix d'une architecture, un codage efficace des données qui peut nécessiter un prétraitement approprié, l'ajustement des paramètres de contrôle de l'algorithme (température pour le recuit simulé, multiplicateurs pour la méthode du gradient).

Autrement dit, l'idée d'appliquer un algorithme de réseau à un problème déterminé peut être excellente, mais l'expertise en réseaux d'automates sansconnaissance du domaine d'application reste insuffisante à assurer la réussite du projet.



12-2 ETAT DE L'ART ET PERSPECTIVES

Les exemples donnés dans ce livre ne sont qu'un échantillonnage très incomplet d'un très grand nombre d'études et de propositions sur les réseaux. Une réalisation déterminée correspond à un ensemble de choix binaires parmi des possibilités dont nous avons déjà discuté:

unités digitalesou analogiques

déterministes ou probabilistes

fonctions booléennes ou fonctions à seuil

connexions aléatoires ou cellulaires

symétriques ou non symétriques

réseau homogène ou réseau à couches

itération série ou parallèle

un seul passage par le réseau ou itération jusqu'à ce que l'attracteur soit atteint.

Nous n'avons certes pas cherché à donner un exemple de chacun des choix multiples possibles, mais la littérature publiée en comprend un grand nombre. Citons par exemple:

*l'utilisation de réseaux booléens pour des tâches de reconnaissance et de mémorisation (I. Aleksander dans Neural Computers, pp. 189-197, op. cit. plus loin);

*l'existence de plusieurs types de réseaux en couches (K. Fukushimaet S. Mikaye, Biol. Cyber., 28, 201-208 (1978), B. Huberman et T. Hogg, Phys. Rev. Let. 52, 1024 (1984));

*un modèle de J. Hopfield et D.Tank (dans Disordered Systems and Biological Organization (1986), pp. 155-170, op. cit.) utilisant des unités analogiques et une règle d'apprentissage à la Hebb;

*un modèle de C. von der Malsburg et E. Bienenstock (dans Disordered Systems and Biological Organization, pp. 247-272 (1986), op. cit.) basé sur une dynamique des connexions variables au cours du processus de reconnaissance, et possédant des propriétés de reconnaissance invariante.

En ce qui concerne la biologie, la modélisation du système immunitaire ouvre des perspectives intéressantes. Voici trois références:

*M. Kaufman, J. Urbain et R. Thomas, J. Theor. Biol., 114, pp. 527-561, (1985).

*G. Weisbuch et H. Atlan, J. Phys. A, 21, L189-192 (1987).

*G. Parisi dans Chaos and Complexity, édité par R. Livi, S. Ruffo, S. Ciliberto et M. Bulatti,World Scientific (1988).

Nous n'avons traité dans ce livre que de modèles utilisant des "grands réseaux". Les "petits" réseaux sont aussi utilisés, en biologie cellulaire par exemple. Voir l'ouvrage collectif édité par R. Thomas "Kinetic Logic, Lecture Notes" in Biomathematics, volume 29, Springer Verlag (1979).

Pour les applications technologiques, on pourra se reporter à la bibliographie citée plus loin. Disons d'abord quelques mots des problèmes qui intéressent plus les informaticiens et que nous n'avons pas abordés jusqu'ici.

12-2-1 Problèmes d'informatique

Les réseaux systoliques

Il s'agit de réseaux d'automates cellulaires dont chacun effectue la mêmeopération arithmétique simple permettant de réaliser en parallèle des tâches répétitives. Dans le cas de la multiplication de deux matrices par exemple, chaque unité effectue le produit de deux des entrées et ajoute le résultat à la troisième entrée pour déterminer le signal de sortie. Ces réseaux permettent la réalisation aisée sur silicium de processeurs dédiés (c'est-à-dire utilisables pour une seule fonction), extrêmement rapides grâce au parallélisme, que l'on utilise à partir d'un ordinateur hôte. Le chapitre 8 du livre classique de C. Mead et L. Conway Introduction aux systèmes VLSI, InterEditions (1983), est une bonne introduction. L'article de Y. Robert "Systolic Algorithms and Architectures", dans Automata Networks in Computer Science (op. cit. plus loin), est plus récent (1987).

Coopérativité entre processeurs

Une des premières applications des réseaux d'automates a été le problème du partage des ressources dans un système informatique entre les différents processeurs et les ressources mémoires, imprimantes et périphériques variés. Ces problèmes se retrouvent aujourd'hui dans la conception des systèmes parallèles généraux MIMD (MultipleInstruction Multiple Data). Les réseaux de Petri sont l'un des formalismes utilisés pour modéliser ces systèmes (G.W. Brams, Réseaux de Petri: théorie et pratique, Masson (1983).)

12-2-2 Machines spécialisées

Tous ces algorithmes parallèles appellent la construction de machines parallèles pour que l'on puisse utiliser pleinement leurs possibilités. Ces machines n'apparaissent que très timidementsur le marché. Le premier obstacle est que la machine parallèle la plus efficace pour implémenter un algorithme particulier serait très spécifique de cet algorithme. Or tous ces algorithmes sont encore en plein développement et il ne semble guère raisonnable de fixer dès aujourd'hui l'architecture d'une machine sans être sûr de l'algorithme. La plupart des études faites aujourd'hui sur des réseaux d'automates le sont sur des machines classiques. Même lorsque l'on utilise une machine vectorielle comme le CRAY, c'est toujours dans le cadre d'une programmation traditionnelle, en Fortran par exemple. Citons néanmoins quelques machines particulièrement adaptées aux calculs sur réseaux.

Architecture pipe-line

Les architectures pipe-line sont très bien adaptées aux automates cellulaires. Le pipe-line est constitué d'une série de processeurs spécialisés simples dans lesquels les informations circulent d'un processeur à l'autre. C'est en somme un réseau d'automates à une dimension. Dans les machines CAM (du MIT) et RAP (de l'Ecole Normale Supérieure) les états des automates sont rangés dans des plans mémoire et entrés séquentiellement dans un processeur qui fonctionne comme un décodeur d'adresse. L'adresse calculée est celle de la table de vérité de l'automate cellulaire étudié. Le contenu de cette adresse constitue donc une sortie du deuxième processeur. Ce signal est envoyé vers les plans mémoire pour mettre à jour l'état de l'automate et vers un processeur d'image pour la visualisation simultanée du réseau.

La programmation d'une telle machine consiste principalement à charger la table de vérité en fonction de l'automate cellulaire étudié à partir de l'ordinateur hôte, en général un simple micro-ordinateur. Ces machines permettent la mise à jour et l'observation, à la cadence du défilement des images de télévision (50 par seconde), de réseaux de 256 par 512 automates. Ces machines sont décrites dans le livre de T. Toffoli et N. Margolus, Cellular Automata machines, MIT Press (1987), ou Physica D, 10, pp.185-204 (1984), et dans A. Clouqueur et D. d'Humières, Complex Systems, 1, pp. 585-597 (1987).


Systèmes multiprocesseurs

Des machines comprenant un grand nombre de processeurs identiques connectés en réseau ont été réalisées récemment et utilisées pour implémenter des réseaux d'automates. La "Connection Machine" proposée par D. Hillis comprend 65 536 processeurs connectés dans un hyper-cube à 16 dimensions. Elle est décrite dans The Connection Machine, par D. Hillis, MIT Press (1985) ou Physica D, 10, pp. 213-228 (1984). Dans le même esprit, des processeurs arithmétiques spécialement conçus pour être utilisés en réseau, les transputers sont produits par la firme INMOS. Leur principe est décrit par exemple dans "The Transputer" par D. May et R. Shepherd, dans Neural Computers, voir plus loin.

Chips et machines optiques

Enfin, les plus hardis s'engagent dans la réalisation matérielle de dispositifs à semi-conducteurs ou optiques permettant, par exemple, l'implémentation directe de réseaux à la Hopfield. Plusieurs chips expérimentaux ont déjà été construits aux laboratoires Bell ou au Caltech (voir les articles de l'équipe de la Bell, pp.182-187 et pp. 227-234, et de celle du Caltech pp. 408-413, dans Neural Networks for Computing, op. cit. plus bas). L'une des voies les plus prometteuses est l'ordinateur optique. En effet, des opérations élémentaires comme la transmission du signal lumineux, la multiplication par un poids synaptique et la sommation s'effectuent très simplement en optique par, respectivement, la transmission dans l'air, le passage par un milieu absorbant, photographie ou hologramme, et la focalisation. La matrice des connexions synaptiques est réalisée par un hologramme où sont superposées les contributions des différents patterns. Changer de réseau se fait simplement en changeant d'hologramme. Les opérations non linéaires, comme le seuillage, sont réalisées par des matrices de dispositifs optiques non linéaires. Les itérations successives ne nécessitent que la réalisation d'un trajet lumineux fermé par des miroirs et des lames semi-réfléchissantes. Le grand intérêt de l'ordinateur optique est sa capacité de traitement en parallèle, plus grande que celle d'un chip, et le fait que les images à traiter puissent être envoyées directement sur l'ordinateur, sans dispositif opto-électronique de lecture, ni digitalisation. L'article de D. Psaltis, C. Park et J. Hong dans Neural Networks, 1, pp. 149-163 (1988) contient en deuxième partie une introduction à ces techniques. Celui du Scientific Americande Mars 1987 par Y. Abu-Mostafa et D. Psaltis est plus descriptif.

12-3 BIBLIOGRAPHIE

Livres

Il n'existe pas à notre connaissance de traité complet sur les réseaux d'automates. Les quelques titres qui suivent abordent tel ou tel aspect du sujet.

Citons deux livres "historiques":

Les travaux de von Neumann ont été publiés après sa mort par A. Burks dans J. von Neumann: Theory of Self-Reproducing Automata. A. Burks Ed., Univ. of Illinois Press (1966).

Le livre classique de M. Minsky et S. Papert sur le perceptron vient d'être réédité:

M. Minsky, S. Papert: Perceptrons, MIT Press (1988).

Les ouvrages suivants sont cités dans l'ordre des chapitres du livre.

Le livre de S.Wolfram, Theory and Applications of Cellular Automata (1986), est en fait un recueil d'articles comme d'autres livres publiés chez World Scientific.

Le livre de T. Kohonen: Self-Organization and Associative Memory, Springer Series in Information Sciences, vol 8, Springer Verlag (1988), donne un grand nombre d'applications des méthodes algébriques.

L'ouvrage collectif Automata Networks in Computer Science, édité par F. Fogelman-Soulié, Y. Robert et M. Tchuente, Manchester University Press (1987), développe bien des aspects qui ne sont pas traités ici, qu'il s'agisse d'outils mathématiques, ou des réseaux systoliques. Ce livre rédigé dans un formalisme mathématique traite aussi des formalismes linéaires et de la rétro-propagation en donnant quelques évaluations comparatives des différents algorithmes.

Le livre collectif Parallel Distributed Processing, édité par J. Rumelhart, J. McClelland et The PDP Research Group,2 vol., MIT Press (1986), est représentatif de l'intérêt des chercheurs en sciences cognitives pour le "connexionnisme" (modélisation des systèmes cognitifs par les réseaux d'automates). Plusieurs approches y sont décrites. Le troisième volume (1988) contient des indications sur la programmation des différents algorithmes, plus une disquette de programmes.

Autre recueil commenté d'articles, Spin Glass Theory and Beyond, par M. Mézard, G. Parisi et M. Virasoro,World Scientific (1988), est très représentatif de l'approche des réseaux d'automates et de l'optimisation combinatoire par les physiciens. Les articles les plus classiques y sont inclus.

Enfin, un livre discute plus spécialement d'algorithmes, Computer Simulation and Computer Algebra, par D. Stauffer, F. Hehl, V. Winkelmann et J. Zabolitzky, Springer Verlag (1988).

Comptes rendus de conférences

Les comptes rendus publiés des workshops (petites conférences sur invitations) permettent de se tenir au courant du sujet. Citons:

D. Farmer, T. Toffoli, S. Wolfram Eds, "Cellular Automata". Physica 10D, North-Holland (1984).

J. Demongeot, E. Goles, M. Tchuente Eds, "Dynamical Systems and Cellular Automata", Academic Press (1985).

E. Bienenstock, F. Fogelman-Soulié, G. Weisbuch Eds, "Disordered Systems and Biological Organization", Springer Verlag, NATO ASI Series in Systems and Computer Science, n°F20 (1986).

J. Denker Ed., "Neural Networks for Computing", Conf. Proceedings n°151, Snowbird, Utah (1986), American Institute of Physics (1986).

R. Eckmiller et C. v.d. Malsburg Eds, Neural Computers,Springer Verlag, NATO ASI Series in Systems and Computer Science, n°F41 (1988).

Revues

L'une des difficultés d'établir une bibliographie sur ce sujet tient au fait que les publications y sont dispersées dans des revues très diverses. Seules quelques revues très récentes sont spécialisées dans les réseaux d'automates:

Complex Systems, publié par Complex Systems Publications, est orienté vers les automates cellulaires.

Neural Networks, publié par Pergamon, est orienté vers les réseaux de neurones formels. Les articles des deux premiers numéros complètent assez bien les exemples que nous avons discutés dans les chapitres de ce livre.

Cependant, le plus souvent encore, les physiciens publient dans les revues de physique et les informaticiens dans les Proceedings des I.E.E.E.