Calcul souple, calcul réel, etc., sont des noms courants de certaines formes de traitement de l’information dont les formes originelles sont tirées de la biologie. La logique floue et probabiliste, les réseaux de neurones, les algorithmes génétiques, de leur côté, renvoient à différents formalismes théoriques par lesquels des modèles informatiques et des algorithmes peuvent être définis pour accomplir ces tâches.
Teuvo Kohonen1

QU’EST-CE QU’UN RÉSEAU DE NEURONES ?

1Lorsque nous avons évoqué plus haut l’importance des réseaux de neurones, nous n’avons pas fait allusion aux assemblages biologiques de cellules nerveuses qu’on trouve dans les organismes vivants. Ces réseaux naturels accomplissent un grand nombre de tâches complexes, depuis la reconnaissance des sons et des images jusqu’à la mémorisation et à la prise de décision. L’exemple par excellence est le cerveau humain, lequel d’ailleurs est bien plus qu’un simple réseau ou même un réseau de réseaux.

2Étant donné que les réseaux biologiques emmagasinent et traitent l’information, ils exécutent un genre de calcul dont les caractéristiques principales sont une interconnexion massive d’éléments simples—les neurones—et la faculté de s’auto-modifier par un processus semblable à de l’apprentissage. C’est cette capacité de calcul que les modèles artificiels cherchent à reproduire.

3Un réseau de neurones artificiel apparaît d’abord comme une sorte de graphe, une notation commode pour représenter certaines opérations sur des données numériques. Des noeuds symbolisant les unités de calcul de base sont reliés par des lignes qui représentent le flot de l’information ou des données (figure 3.1). D’un point de vue mathématique, un réseau de neurones donné calcule une certaine application ou fonction/ ; autrement dit, il associe aux données d’entrée, généralement un vecteur (x₁, x₂,..., x_n) numérique, une donnée de sortie f(x₁, x₂,..., x_n) qui, elle aussi, est numérique. Dès lors, on peut voir dans le réseau une manière de définir l’application f, lorsqu’il ne semble pas possible de la spécifier d’une autre façon. Pour paraphraser Marshall McLuhan, le réseau est alors l’application. Les réseaux de neurones sont donc, à l’origine, des objets mathématiques. S’ils sont mis en œuvre en tant qu’algorithmes, en tant que circuits électroniques ou en tant que réseaux physiques formés de cellules interconnectées, on parle alors de ces systèmes comme de réseaux de neurones. Mais puisque ces réseaux « réels » sont des réalisations concrètes de réseaux idéaux, ces derniers deviennent le véritable objet d’investigation.

4La création de réseaux de neurones artificiels s’inspire peut-être de la nature, mais la performance qui en résulte est encore loin d’équivaloir celle que l’on retrouve dans la réalité. Toutefois, les modèles artificiels fournis sent une solution de rechange aux méthodes de calcul classiques pour résoudre certains types de problèmes, surtout là où un procédé de solution exacte est inconnu, voire impossible à encoder en tant que programme. Un exemple typique de ce genre de problèmes est la classification des structures. Celle-ci comprend la reconnaissance des sons et des images, ainsi que beaucoup d’autres situations. À cet effet, on peut considérer un fichier informatique comme une configuration (pattern), la classification consistant à déterminer si le fichier est « propre » ou s’il a été attaqué par un virus informatique. Le réseau de neurones ayant été « entraîné » (comme on l’expliquera plus loin) à reconnaître les fichiers infectés parmi ceux qui figurent dans un ensemble d’apprentissage, on peut s’attendre à ce qu’il détecte aussi de nouveaux fichiers contaminés qui se présentent à lui. (Cet exploit aura été accompli sans que nous ayons eu à préciser ce qu’est un virus informatique.) Cette approche n’est pas différente de celle adoptée dans le dressage des chiens en vue de la détection des drogues. Le chien finit par apprendre à reconnaître une odeur comme étant celle d’une « drogue » sans qu’on lui en ait jamais fourni une définition exacte. Cette faculté d’apprendre par les exemples est également présente dans les réseaux de neurones lorsqu’ils sont utilisés comme classificateurs.

FIGURE 3.1

5De même qu’il y a un grand nombre de genres d’automobiles ou d’horloges, de même il existe une grande variété de réseaux de neurones. Des choix arbitraires président à toute tentative pour les classer. Parmi les nombreuses possibilités, nous avons choisi de distinguer entre les réseaux de propagation, ou réseaux ordinaires, et les réseaux de rétroaction. Les premiers agissent sur certaines données d’entrée et, après avoir accompli une série d’opérations, produisent une donnée de sortie ; dans les derniers, les réponses des neurones sont connectées—alimentées en retour—au réseau. On décrit mieux les réseaux de rétroaction en les assimilant à des systèmes dynamiques ayant des « états » et des « transitions ». Pour une entrée donnée, le réseau traverse une séquence d’états, à des intervalles de temps discrets ou de façon continue. Quand—et si—le réseau atteint un certain état stable, cette dernière configuration est considérée comme étant la réponse du réseau. Dans la partie qui va suivre, nous allons analyser surtout les réseaux de propagation, nous réservant le soin de traiter des réseaux de rétroaction dans une autre section.

6Les deux types de réseaux sont composés d’unités de calcul interconnectées appelées neurones (artificiels), lesquels imitent le comportement des neurones biologiques—ou tout au moins prétendent le faire. La première tentative pour donner une définition d’un neurone synthétique remonte à 1943. Dans leur célèbre article « A Logical Calculus of the Ideas Immanent in Nervous Activities » [« Un calcul logique des idées immanentes dans les activités nerveuses »]2, W. S. McCulloch et W. Pitts énoncèrent une élégante définition mathématique d’un neurone ayant n données d’entrée binaires et une seule donnée de sortie binaire. Organisés en réseaux, ces éléments de base pouvaient calculer des fonctions logiques simples (c’est-à-dire des fonctions booléennes).

7Plus d’une décennie plus tard, F. Rosenblatt introduisit le perceptron3, précurseur de beaucoup de modèles de réseaux de neurones actuels. La principale motivation de Rosenblatt pour la mise au point du perceptron fut de fournir un modèle à certaines fonctions des systèmes biologiques, et, plus spécialement, de modéliser la façon dont ces systèmes mémorisent et retrouvent l’information, ainsi que la façon dont l’information enregistrée agit sur la reconnaissance et le comportement. Rosenblatt était convaincu que les réseaux de neurones (les vrais), avec leurs myriades d’interconnexions aléatoires, ne pouvaient pas être représentés convenablement par la logique symbolique et l’algèbre de Boole. Son modèle par conséquent était un modèle probabiliste, destiné à fournir une analyse mathématique de l’organisation globale du réseau nerveux. Toutefois, Rosenblatt était très conscient que son modèle ne représentait que des simplifications extrêmes du système nerveux central.

FIGURE 3.2

DU NEURONE BIOLOGIQUE AU NEURONE ARTIFICIEL

8Il y a deux sortes de neurones artificiels à partir desquels sont construits la plupart des réseaux. Les deux modèles diffèrent surtout par le type de données qu’ils peuvent traiter, ces données pouvant être soit binaires soit continues. Dans le premier cas, plusieurs nombres binaires—disons, x₁, x₂ et x₃,—entrent dans le neurone artificiel comme données d’entrée (voir la figure 3.2). Prenant pour guide la cellule nerveuse biologique, ces nombres peuvent être interprétés comme des signaux envoyés au neurone par d’autres neurones. Après un bref intervalle, le neurone biologique va répondre à l’ensemble de ses données d’entrée en émettant une impulsion neuronale. Dans notre modèle mathématique, l’ensemble des données d’entrée est représenté par la somme pondérée

s = w₁x₁ + w₂x₂ + w₃x₃

où les « poids » w₁, w₂, et w₃, qui peuvent être n’importe quels nombres réels, mesurent la force de la connexion de chaque donnée d’entrée au corps du neurone. Ces nombres sont aussi appelés poids synaptiques— de synapse, qui est le nom de l’organe de contact en biologie.

9Pour que se produise l’émission du neurone biologique, les données d’entrées combinées doivent excéder une valeur critique. Dans le neurone artificiel, une valeur critique type est zéro, si bien que celui-ci « émet », c’est-à-dire produit, la valeur de sortie f(s) = 1, si s est plus grand que zéro ; autrement, il n’émet pas f(s) = 0). La fonction/est appelée fonction d’activation du neurone (figure 3.3(a)).

10Un neurone continu admet n’importe quel nombre réel comme donnée d’entrée et peut répondre avec n’importe quel nombre entre 0 et 1 en tant que donnée de sortie—une échelle continue de valeurs ou réponse graduée. L’activation/(s) du neurone continu est aussi une fonction de la somme pondérée s. Son graphe (figure 3.3 (b)) est une sorte de version adoucie du graphe de la figure 3.3 (a). Un choix fréquent de f est

connu sous le nom de sigmoïde ; cependant, toute fonction, continue et croissante, qui prend des valeurs entre 0 et 1 peut servir de fonction d’activation.

FIGURE 3.3

11Pour résumer, le neurone binaire et le neurone continu calculent la fonction y =f(w₁x₁+w₂ x₂ +... + w_n x_n) pour des données d’entrée (x₁, x₂,..., x_n), accomplissement plutôt modeste après tout. Considérons alors une seule cellule nerveuse à l’état isolé. Aurait-on pu imaginer ce qui se produit lorsque des millions de ces cellules primitives sont interconnectées ? Par lui-même, un neurone artificiel élémentaire ne peut pas arriver à grandchose. Ce n’est que lorsque beaucoup de ces unités fondamentales de calcul sont mises ensemble qu’apparaissent de nouvelles propriétés totalement inattendues et potentiellement utiles. John Hopfield, pionnier du calcul neuronal, a bien fait ressortir ce point dans son article décisif de 1982 (sur lequel nous reviendrons plus loin)4 : « Une bonne partie de l’architecture des régions cérébrales des animaux supérieurs doit être constituée d’une prolifération de circuits locaux simples aux fonctions bien définies. Le pont entre les circuits simples et les propriétés de calcul complexes des systèmes nerveux plus développés peut être l’apparition spontanée de nouvelles capacités de calcul à partir du comportement collectif d’un grand nombre d’éléments simples de traitement. »

LES RÉSEAUX COMME ALGORITHMES OUVERTS

12Si nous voulons résoudre un problème sur un ordinateur numérique, il faut fournir à celui-ci une stratégie de solution sous forme d’instructions précises, à savoir un programme. L’une des caractéristiques essentielles du calcul neuronal est l’absence d’un tel ensemble fixe de commandes. Cela étant, on peut voir un réseau de neurones comme un programme incomplet, ou algorithme « ouvert », dans le sens où certains paramètres numériques—les poids—ne sont pas précisés par le programmeur. Les poids sont calculés pendant une « phase d’entraînement », un procédé graduel qui requiert certaines données (l’ensemble d’entraînement) et un autre programme (l’algorithme d’apprentissage). Au cours de la phase d’entraînement, le réseau « apprend » à répondre d’une certaine façon aux données qui lui sont présentées. Des termes tels qu’« entraînement » et « apprentissagesage » pourraient laisser croire que l’on est en présence d’un processus semblable à celui de l’apprentissage animal ou humain ; en réalité, il ne s’agit que de pures analogies, fort pratiques mais plus ou moins trompeuses. Ce que les praticiens des réseaux de neurones appellent « apprentissage » n’est, en fait, qu’un « calcul », aussi éloigné de l’apprentissage humain réel que peut l’être d’un neurone biologique un neurone mathématique.

13La raison pour laquelle les poids ne peuvent pas être précisés d’emblée est qu’on ne dispose normalement d’aucun indice de nature causale, autrement dit, on ne sait pas quels effets les différentes valeurs de poids ont sur le calcul du réseau. Cet état de choses résulte de l’essence même des réseaux de neurones, lesquels sont fondamentalement des « boîtes noires » dont le comportement est en grande partie imprévisible. L’utilisateur peut sélectionner l’« architecture » du réseau—le nombre et le type de neurones, la façon dont ils sont interconnectés et ainsi de suite-, mais les poids ne peuvent pas, en général, être établis rationnellement ou même devinés : ils ne peuvent qu’« être appris » (une exception remarquable est le réseau de rétroaction de Hopfield—le sujet d’une section à venir—dont les poids sont établis d’avance).

14Cette approche de résolution des problèmes par la boîte noire comporte des inconvénients, car il est presque impossible de faire appel à notre intuition comme nous le faisons pour écrire ou modifier un programme informatique—par exemple pour réparer un bogue. Mais elle comporte un avantage évident, qui est de pouvoir faire exécuter au réseau des tâches qu’on ne pourrait pas transcrire sous une forme algorithmique explicite.

15Ramené à l’essentiel, un réseau de neurones transforme des données d’entrée en données de sortie ; sous cet angle, il s’agit d’un appareil de calcul. L’entrée comme la sortie sont généralement des chaînes finies [x₁, x₂,..., x_n] de nombres appelées vecteurs à n dimensions. Les nombres x, peuvent varier sur un certain intervalle, par exemple-1 ≤ x_i ≤ 1, auquel cas nous parlons de données continues, ou ils peuvent ne prendre que deux valeurs, telles que 0 et 1 (données binaires). Le type de données utilisées dépend de l’objet du calcul. Ceci nous amène à la question pratique de savoir de quoi est vraiment capable un réseau de neurones.

LA RECONNAISSANCE DES CONFIGURATIONS

16Les réseaux de neurones sont très efficaces pour effectuer des tâches de classification et de reconnaissance de configurations. Une configuration (pattern en anglais) est un concept très général qui inclut aussi bien des images que des sons, voire des formes telles que les caractères d’imprimerie (lettres, chiffres ou signes de ponctuation). Prenons comme exemple un ensemble de 95 caractères d’imprimerie. Chacun de ceux-ci peut être représenté physiquement comme une grille rectangulaire appelée grille de pixels. Si une grille de 7 x 10 est utilisée, alors chacune des 70 positions peut être noire ou blanche (figure 3.4). Ce qui offre une quantité astronomique de configurations possibles de points, alors que nous n’en avons besoin que de 95 pour représenter nos caractères d’imprimerie. Pour le traitement par le réseau, un caractère est encodé comme une chaîne de 70 bits, soit un vecteur binaire, un 1 ou un 0 signifiant dans une position donnée que le point correspondant sur la grille des pixels est noir ou blanc. Le réseau de neurones possède alors 70 neurones d’entrée, un pour chaque position de bit (ou pixel) et 95 neurones de sortie, correspondant aux 95 « classes » de caractères (ceci est une situation plutôt spéciale—dans la plupart des problèmes de classification, une classe sera composée de plus d’une structure). Le reste des neurones dans le réseau, les soi-disant neurones « cachés », est utilisé uniquement pour les besoins du calcul.

FIGURE 3.4

17Lorsqu’un caractère encodé comme un vecteur binaire de dimension 70 se présente au réseau de neurones, celui-ci répond en donnant la valeur 1 à exactement un de ses 95 neurones de sortie, signalant ainsi le résultat de la classification. De cette manière, le réseau associe—correctement ou incorrectement — chaque caractère typographique à une « classe ». Pendant l’étape d’entraînement, le réseau de neurones « apprend » les bonnes associations, un peu à la manière d’un enfant qui reconnaît ses fiches (ceci est un chien, un chat, etc.) sous la supervision d’un instituteur. Les 95 caractères (l’ensemble d’entraînement) sont fournis au réseau un par un. Le réseau répond en retournant un nombre de classe pour chacun d’entre eux. Chaque fois qu’un caractère est mal classé, l’algorithme d’apprentissage règle les poids de telle façon que la probabilité d’une bonne classification augmente la fois suivante (ce qui comporte l’usage intelligent de techniques mathématiques, comme nous l’expliquerons par la suite). Le cycle d’entraînement continue jusqu’à ce que le réseau reconnaisse correctement tous les caractères. Ceci peut requérir que l’ensemble d’entraînement soit présenté au réseau des centaines sinon des milliers de fois. Les valeurs des poids à la fin de l’entraînement seront adoptées définitivement, et le réseau sera alors prêt à fonctionner.

18Il est à noter ici qu’au niveau le plus abstrait, il n’y a en jeu ni pixels ni caractères ou classes. Le réseau calcule tout simplement une fonction ; autrement dit, à chaque vecteur binaire de dimension 70 (l’entrée), il associe un vecteur particulier de dimension 95 (la sortie). C’est notre interprétation qui donne sa signification au calcul. Par conséquent, nous voyons, ou interprétons, chaque entrée comme un pixel noir ou blanc et le vecteur d’entrée (c’est-à-dire les 70 pixels considérés dans un certain ordre) comme un caractère d’imprimerie. De la même façon, le neurone de sortie qui est « allumé » (avec la valeur 1) nous indique quel caractère d’entrée le réseau a—exactement ou pas—reconnu. Finalement, c’est nous qui voyons ce calcul particulier comme un processus de classification.

19Dans l’exemple ci-dessus, qui est basé sur une application réelle5, le réseau finit par apprendre à classer correctement chaque configuration d’entrée. Ceci n’est peut-être pas surprenant, étant donné que les membres de chaque classe peuvent être exactement définis. Dans une situation encore plus typique, il y a aura des configurations dont les classes seront très difficiles—voire impossibles—à déterminer, même par un classificateur humain. Tel est le cas lorsque les configurations sont les chiffres écrits à la main figurant dans les codes postaux. Même si ces chiffres peuvent être représentés d’une manière ou d’une autre comme des grilles de pixels, il est impossible de dire précisément quelle configuration de points correspond aux différentes manières que les gens ont d’écrire, par exemple, le chiffre « 5 ». Dans ces circonstances, on ne peut s’attendre à ce qu’un réseau de neurones—ni aucun autre classificateur, d’ailleurs—puisse accomplir une classification avec un taux de réussite de 100 %. Heureusement, un autre caractère utile du calcul neuronal entre en jeu ici : la capacité d’un réseau de neurones à « généraliser ». Ceci veut dire, en quelque sorte, que, si un réseau de neurones a appris à classifier un grand nombre de configurations échantillons qui soient, en un certain sens, typiques, on peut s’attendre à ce qu’il classifie ensuite correctement des configurations nouvelles, inconnues—du moins la plupart du temps.

20Notre prochain exemple comporte une tâche qui déconcerte même les experts : celle de préciser si oui ou non un programme informatique a été contaminé par un virus.

DES VIRUS ET DES HOMMES

21La métaphore est une des meilleures alliées de l’écrivain scientifique. Lorsqu’elle est utilisée judicieusement, elle peut servir à accroître la compréhension d’un concept difficile et à créer dans l’esprit du lecteur une impression qu’il n’oubliera pas de si tôt. Mais cette alliée de l’écrivain peut facilement se transformer en ennemi pernicieux. Les métaphores causeront plus de tort que de bien si elles sont mal choisies, si on abuse d’elles ou si l’auteur les étire trop loin—ou encore si le lecteur les confond avec la chose même.

22Quand il s’agit du mauvais fonctionnement d’un ordinateur, la distinction entre métaphore et réalité s’efface presque totalement—pour le meilleur et pour le pire. Quand la tragédie frappe, un disque dur ou la mémoire de l’ordinateur cessent d’être des objets inanimés pour devenir des organismes vivants qui ont été « infectés » par un « virus ». Ainsi, une disquette « infectée » peut répandre « l’agent pathogène » et faire en sorte que des logiciels alors en bonne santé « attrapent la maladie ». L’« attaque virale », qui peut prendre des proportions « épidémiques », ne pourra être enrayée qu’après que le virus ait été « isolé » et « disséqué » pour étude, et qu’un « remède » ait été finalement trouvé. Le fameux virus de Jérusalem, par exemple, qui est apparu en Israël à la fin de 1987, fut présenté par la presse comme étant un virus « assassin ».

23En fait, un virus informatique, terme inventé par Adleman au début des années 806 est la section d’un programme qui contient des instructions pour l’autoreproduction et qui est capable d’attacher des copies d’elle-même à d’autres programmes ou régions d’un disque. Le fameux virus de Jérusalem se copie d’abord lui-même sur la mémoire lorsqu’un programme où il « vit » est exécuté, et de là il infecte tout programme ultérieurement exécuté par le système hôte. Ces programmes infectés peuvent eux-mêmes se propager de la même façon et finir par contaminer d’autres systèmes informatiques. Les conséquences désagréables d’une attaque virale peuvent aller d’un écran qui défile à la perte de tout le contenu du disque dur, et provoquer la paralysie temporaire—ou permanente, si rien n’est fait— du système de la victime.

24Il est vrai que les similitudes entre le virus biologique et sa contrepartie électronique sont frappantes. Les deux s’attachent à un individu (organisme ou ordinateur) et, dans le processus de reproduction, bouleversent les fonctions vitales de leurs hôtes : destruction des cellules ou même de la vie, dans un cas ; perte de données, de programmes et de la faculté de fonctionner convenablement, dans l’autre. Tandis que la plupart des virus sont spécifiques à une certaine population (les singes ou les fichiers dos), d’autres ont la capacité de sauter la barrière des espèces (du singe à l’homme— comme ce fut le cas du virus du sida—ou du dos aux logiciels Macintosh). Les virus qui causent le plus de dommages aux ordinateurs sont (heureusement) ceux qui sont le moins enclins à se répandre, exactement comme les souches mortelles de virus sont rares tandis que celles qui sont relativement inoffensives—le virus du rhume, par exemple—sont très répandues. Une autre caractéristique commune est la nature aveugle de leurs attaques : une fois lâchés, les virus biologiques comme les virus électroniques frappent n’importe quelle victime potentielle qui se trouve sur leur chemin.

25L’analogie ne tient plus lorsqu’on considère les motivations présentes derrière un tel comportement destructeur. Malgré tous leurs effets dévastateurs, les virus biologiques ne sauraient être accusés de méchanceté ; les virus informatiques, en revanche, sont créés et propagés délibérément par des personnes tout à fait conscientes de leur perfide dessein.

LES CHASSEURS DE VIRUS

26De la Californie à l’Islande, une petite armée d’hommes et de femmes dévoués travaille sans cesse à contrebalancer les effets du fléau que constituent les virus électroniques. Ce sont les chasseurs de virus, une communauté internationale unie dans sa lutte pour déceler et neutraliser ce fléau. Pour ce faire, ils ont principalement recours à des méthodes traditionnelles qui s’appuient sur l’analyse de chaque nouveau virus par des experts. Mais, dans quelques années, cette approche cas par cas sera trop lente pour faire face aux nouveaux virus qui se répandent rapidement dans les réseaux mondiaux comme l’Internet. Il faudra alors que la réponse à une alerte soit beaucoup plus rapide, plus automatique, plus générique.

27Dans sa recherche sur les techniques futures de protection contre les virus, une équipe du High Integrity Computing Laboratory du Thomas J. Watson Research Center de IBM s’est tournée vers la nature pour essayer d’y trouver l’inspiration. Puisque les virus des ordinateurs ressemblent aux virus réels à bien des égards, les experts ont cherché des éléments de solution dans les mécanismes de défense que les organismes vivants ont développés contre les maladies. En exploitant cette approche « biologique », l’équipe dirigée par Steve White et Jeffrey Kephart a mis au point un détecteur de virus basé sur un réseau de neurones. La technique fut plus tard incorporée à un produit commercial : le logiciel Antivirus de ibm.

28Tous comme les personnes malades, les ordinateurs infectés ont besoin, pour recouvrer la santé, d’une assistance spécialisée. Un expert dans la lutte contre les virus doit d’abord désassembler le code du virus pour découvrir comment il fonctionne et ce qu’il fait précisément. Puis, il sélectionne une « signature », ou courte séquence du code (de 16 à 32 octets de long), qui représente une portion des opérations du virus (instructions pour l’autoreproduction ou autre activité suspecte, par exemple) qui sont caractéristiques de l’intrus mais qui ont peu de chances de se retrouver dans le programme normal d’un ordinateur. Cette information peut ensuite être encodée sur des scanneurs de virus, lesquels sont des programmes qui testent des fichiers, de la mémoire et d’autres emplacements pour la présence de virus.

29La détection d’un virus dans un système est normalement suivie d’un processus de désinfection pour restaurer dans leur état originel les programmes contaminés. Un grave inconvénient de ces mécanismes de balayage et de réparation est que leur application est limitée aux virus connus, ou à leur variantes. Pour cette raison, les scanners et désinfecteurs actuels requièrent de fréquentes mises à jour, de nouveaux virus étant constamment découverts. Une fois qu'elle est détectée, chaque souche particulière de virus doit être analysée, afin d’extraire l’information qui va la neutraliser, opération qui peut prendre plusieurs jours.

30L’équipe de IBM reconnaît que l’idée de se servir d’analogies biologiques pour défendre les ordinateurs contre les virus n’est pas nouvelle—W. H. Murray avait proposé une approche semblable en 19887-, mais elle prétend avoir été la première à prendre l’analogie au sérieux, au point d’avoir effectivement créé une technologie antivirus inspirée de la biologie8.

DES NEURONES ARTIFICIELS POUR COMBATTRE DES VIRUS ARTIFICIELS

31Le problème de savoir si un programme informatique donné comporte un virus est insoluble par la voie algorithmique. En termes plus simples, le parfait détecteur de virus ne peut pas être construit. Les raisons de cet état de fait ne sont pas seulement pratiques mais également théoriques. En effet, un programme universel de détection de virus peut théoriquement être utilisé afin de décider si une machine de Turing arbitraire finira par terminer son calcul ; cependant, comme nous l’avons vu dans le chapitre 3, aucun algorithme ne peut résoudre ce problème de l’arrêt9 ; par conséquent, aucun détecteur de virus universel ne peut non plus exister. Bien sûr, il est toujours possible de concevoir des dépisteurs de virus efficaces qui, même s’ils sont moins radicaux, fonctionnent bien dans la pratique.

32On peut considérer la détection des virus informatiques comme un problème de classification qui ne comporte que deux classes, à savoir « infectée » et « non infectée ». Un sous-problème plus simple, mais important, est la classification des virus démarreurs, lesquels représentent environ 80 % des virus les plus communs. Faire démarrer (to boot, en anglais) un ordinateur, c’est « lui apprendre à se mettre en marche tout seul » ou « à se prendre en main ». Un secteur d’amorce est une petite séquence de code (512 octets de long dans les ordinateurs personnels compatibles avec IBM) qui dit à l’ordinateur comment procéder.

33Guidée par des considérations à la fois pratiques et théoriques, l’équipe de IBM a extrait environ cinquante chaînes de 3 octets, dites caractéristiques, qui apparaissent fréquemment dans les secteurs d’amorce des virus mais peu souvent dans les secteurs normaux. Dans un secteur d’amorce arbitraire de 512 octets, la présence (1) ou l’absence (0) de chaque caractéristique définit un vecteur binaire. Celui-ci devient l’entrée d’un réseau à couche unique avec une fonction d’activation continue. Les poids du réseau furent calculés par rétropropagation (voir la section qui suit) employant quelque 100 échantillons d’entraînement, dont les trois quarts à peu près étaient viraux. Une valeur de sortie du réseau plus grande que zéro indique la présence d’un virus ; sinon, le secteur d’amorce est déclaré sain.

34Comme dans ce cas il n’y a que deux classes, à savoir « infectée » et « saine », deux types d’erreurs de classification sont possibles : le faux-positif (un fichier sain est à tort déclaré infecté) et le faux-négatif (un fichier contaminé passe inaperçu). Pour cette application particulière, il est crucial d’éviter le faux-positif. De fausses alertes fréquentes sur des milliers d’ordinateurs laisseraient les utilisateurs moins insatisfaits qu’ils l’eussent été sans la protection antivirus.

35Des séries de tests appliqués au système ont abouti à un taux de faux-négatifs de 10 à 15 % et à un taux de faux-positifs de 0,02 %. Commentant cette performance, l’équipe a prévu que 85 % des nouveaux virus des secteurs d’amorce seront détectés, avec un taux assez mince de faux-positifs affectant les secteurs d’amorce normaux. Le réseau de neurones classificateur a, en fait, déjà attrapé plusieurs virus et montré une des qualités les plus remarquables dans un logiciel antivirus : la capacité de traiter tout seul les nouveaux virus.

LA QUÊTE DES POIDS IDÉAUX

36Bien qu’extrêmement simple, l’exemple que nous allons présenter illustre parfaitement comment l’intuition géométrique et l’efficacité de l’algèbre linéaire combinées peuvent servir à l’« entraînement » d’un réseau de neurones. Par « entraînement », nous entendons le fait de trouver un ensemble de poids permettant à un réseau d’accomplir une tâche précise. Dans le cas présent, nous aimerions que le réseau—à vrai dire un neurone unique— ne mélange pas les torchons et les serviettes, ou, suivant le jargon du spécialiste, classifie les éléments d’un ensemble donné en deux classes disjointes.

37Supposons que nous ayons cinq nombres, x₁, x₂,..., x₅, divisés en deux classes, x₁ et x₅ étant dans la classe A₀ et le reste dans la classe A₁. Notre but est d’apprendre à un neurone artificiel la classification correcte de ces nombres, en répondant par 0 ou par 1 suivant la classe qui contient le nombre xi qu’on lui présente. Pour des raisons techniques, nous encodons les nombres comme des vecteurs y_i = [x_i, 1] à 2 dimensions dont la seconde coordonnée est toujours 1. Par conséquent, notre neurone aura deux entrées, une pour chaque coordonnée, et une sortie pour donner sa réponse. Entraîner le neurone équivaut alors à trouver les poids w₁ et w₂ qui produisent la bonne classification. En d’autres mots, le neurone doit « apprendre » à calculer la fonction

38Si nous utilisons un neurone avec la fonction d’activation représentée dans la figure 3.3 (a)—c’est-à-dire f(s) = 1 ou 0, selon que s est positif ou non-, alors notre problème peut se formuler comme suit :

Trouver w₁ et w₂ de telle sorte que
w₁x_i + w₂< 0, pour i =1 ou 5
et
w₁ x_i + w₂> 0, pour i =2, 3, ou 4

39Il n’est pas difficile de voir qu’il y a beaucoup de solutions possibles pour w_l et w₂ (en fait, il y en a une infinité), et que ces solutions peuvent être calculées par le seul raisonnement mathématique ; on pourrait donc omettre complètement le procédé d’entraînement. Cependant, dans des situations plus complexes, l’entraînement pourra être le moyen le plus efficace—sinon le seul—pour déterminer les poids appropriés.

40On peut envisager les poids possibles comme les coordonnées des vecteurs de poids W = [w₁ ; w₂]. Ceux-ci sont représentés graphiquement par des points dans un espace à 2 dimensions E² (le plan des coordonnées) ou, alternativement, par des segments dirigés, à la façon dont les vecteurs sont représentés dans les manuels d’algèbre linéaire. Par un simple raisonnement de nature géométrique, on peut montrer que les vecteurs de poids W qui satisfont à la condition (1) de la bonne classification sont tous situés dans une région S de E², laquelle est l’intersection de cinq demi-plans.

41L’algorithme d’entraînement commence par un vecteur de poids initial W₁ = [w₁₁ ; w_l2] qui peut être arbitrairement choisi (n’importe quel vecteur excepté [0 ; 0] fera l’affaire). En se servant des cinq nombres posés et de leurs classes respectives comme données, l’algorithme doit nous mener de W₁ à un W_n dans S par des étapes successives de calcul—idéalement, de la façon la plus directe. Présenté avec le premier nombre x, (encodé comme [x₁ ; 1], l’algorithme simule le calcul du neurone en calculant f(w₁₁ x₁ + w_l2), répondant ainsi par 0 ou par 1. Si cette réponse classifie correctement x1, alors aucun ajustement des poids n’est nécessaire. Mais si la classification est incorrecte, le vecteur de poids W₁ en cours est remplacé par un nouveau, W₂, afin d’augmenter la probabilité d’une classification correcte la prochaine fois que x, sera examiné par le neurone (le calcul de W₂ est expliqué plus bas). Le procédé est ensuite répété en utilisant comme entrée chacun des autres nombres x₂,..., x₅, et en recommençant le tout avec x₁ x₂,... jusqu’à ce qu’un vecteur de poids W_n qui classifie correctement tous les cinq nombres soit obtenu. Par un argument mathématique, on peut démontrer que la règle suivante pour l’ajustement des poids produira un tel Wn en un nombre fini d’étapes.

42Supposons que xi ait été incorrectement classifié par l’emploi du vecteur de poids W_k = [w₁ ; w₂]. Le nouveau vecteur de poids alors devra être :

W_{k+1 =} [w₁ ± x_i ;w₂±1]

43Autrement dit, W_k+1 est obtenu en ajoutant le vecteur y_i à W_k ou en le soustrayant de celui-ci, le signe + s’appliquant quand le nombre x_i mal classifié est dans la classe A₁ et le signe—quand il est dans la classe A₀.

44La figure 3.5 illustre la géométrie qui sous-tend la règle d’ajustement. Si, par exemple, x₂ =3—lequel est encodé comme le vecteur y₂ = [3 ; 1] —, alors 3w₁ + w₂ = 0 est l’équation d’une ligne droite L perpendiculaire à y₂. Cette ligne divise le plan des coordonnées en deux demi-plans H₀ et H₁, dont les équations sont :

3w₁ + w₂< 0 (H₀) et 3w₁ + w₂ > 0 (H₁)

45Puisque x₂ appartient à la classe A₁, sa bonne classification requiert que 3w₁ +w₂> 0 (pour que la sortie du neurone soit 1). Pour cette raison, tout vecteur de poids [w₁ ; w₂] dans H1 va réaliser la classification correcte, tandis que tous les vecteurs de poids dans H₀ entraîneront une erreur de classification. Supposons que le vecteur de poids en cours est Wk = [-5 ; 1,5]. Or 3(-5)+1,5 =-13,5<0, par conséquent W_k est dans H₀ et nous avons une mauvaise classification. Pour corriger cette erreur, nous devons déplacer W_k vers H₁. Le plus court chemin vers H₁ est dans la direction de la perpendiculaire à L, ce qui est précisément la direction de y₂ = [3 ; 1]. En ajoutant y₂ à W_k, nous déplaçons le vecteur de poids vers H₁—et par le moyen le plus efficace. Si nous devions tomber sur l’autre type de mauvaise classification (le vecteur de poids en cours étant dans H₁, et les bons poids étant ceux qui sont dans H₀), alors la soustraction de y₂ déplacerait W_k dans la direction opposée, puisque que y₂ pointe toujours vers le demi-plan « positif » (H₁).

46Dans une situation plus générale (et réaliste), les entrées seront des vecteurs à n dimensions (x₁, x₂,... x_n) ou « configurations » (les entrées d’un réseau étant généralement appelées configurations, sans tenir compte de leur nature particulière) ; le neurone entraîné devra faire plus que classifier les configurations dans l’ensemble d’entraînement : il devra également être capable, du moins la plupart du temps, de classer correctement les nouvelles configurations qui se présentent. Pour que cela puisse se faire, certaines conditions devront être remplies : par exemple, les configurations devront être disposées à peu près en grappes autour des « échantillons » qui auront servi à l’entraînement.

47La réalisation de tâches plus complexes requerra la puissance combinée de nombreux neurones interconnectés. Ceux-ci sont, en règle générale, disposés en couches, de telle sorte que les sorties de neurones dans une couche deviennent les entrées de neurones de la suivante. Leurs algorithmes d’apprentissage sont, par conséquent, beaucoup plus complexes que celui qui vient d’être exposé.

FIGURE 3.5

48Le cadre mathématique de l’entraînement des réseaux à couches a été établi par le mathématicien américain Paul Werbos dans sa thèse de doctorat de 197410 L’une des méthodes d’entraînement les plus courantes—et les plus efficaces—est l’algorithme de rétropropagation de l’erreur (discuté dans l’appendice 4), algorithme qui modifie systématiquement les poids, de sorte que la sortie du réseau est de plus en plus proche de la réponse désirée.

49La plupart des algorithmes d’apprentissage ont en général le même format, un ensemble de configurations—l’ensemble d’apprentissage—étant soumis au réseau plusieurs fois de suite. Si la réponse du réseau à une configuration donnée est incorrecte, l’algorithme règle les poids de telle sorte que la marge d’« erreur » soit réduite. Étant donné que les bonnes réponses sont connues et qu’elles contribuent à l’amélioration progressive de la performance du réseau, ce type d’entraînement s’appelle l'apprentissage supervisé. La comparaison entre les réponses désirées et les réponses réellement obtenues—et l’ajustement des poids, si cela s’avère nécessaire—continue jusqu’à ce que toutes les configurations dans l’ensemble d’apprentissage aient été « apprises » avec une marge d’erreur globale acceptable. Cette marge globale est généralement calculée en ajoutant les erreurs pour chaque configuration dans l’ensemble d’apprentissage (il est irréaliste de s’attendre à un résultat parfait, à savoir une erreur égale à zéro). Tout le processus se ramène à essayer de résoudre un problème d’optimisation : celui de minimiser l’erreur globale, qui est généralement une fonction d’une complexité désespérante d’un grand nombre de variables.

L’IMPORTANCE D’ÊTRE NOMBREUX

Des capacités de calcul, utiles aux organismes biologiques ou à la construction des ordinateurs, peuvent émerger en tant que propriétés collectives de systèmes ayant un grand nombre d’éléments simples équivalents.
(John J. Hopfield)11.

50Durant les années 70, les limites des réseaux simples basés sur les perceptrons de Rosenblatt émoussèrent l’enthousiasme du début pour les modèles neuronaux.

51Mais, en 1982, l’intérêt pour les réseaux de neurones s’est ravivé à la suite de la publication d’un article capital de l’éminent physicien John J. Hopfield12 Hopfield rassembla un certain nombre d’idées, dont la plupart n’étaient pas forcément nouvelles, avec une analyse mathématique puissante et éclairée. Nous savions déjà que les calculs produisent des nombres. Hopfield, dans son article, soutient que le nombre peut produire spontanément un calcul ou, plus exactement, que le « calcul » peut se révéler une propriété collective de systèmes ayant un grand nombre d’éléments simples en interaction. D’après Hopfield, grâce à notre compréhension des circuits électroniques de base, nous pouvons planifier et réaliser les circuits complexes qui sont indispensables aux grands ordinateurs. « Parce que l’évolution ne peut procéder de la même façon, écrivait-il, il devient pertinent de se demander si la capacité de grands amas de neurones à accomplir des tâches de “calcul” peut, en partie, être une conséquence collective spontanée du fait d’avoir une grande quantité de neurones simples en interaction. » L’auteur propose alors un modèle mathématique—désigné par la suite comme le réseau de Hopfield—dans lequel les propriétés de calcul surgissent de l’interaction de nombreuses cellules élémentaires plutôt que de la configuration du « circuit ». Les propriétés collectives du modèle produisent une mémoire « adressable par contenu » qui peut restaurer de l’information manquante.

52Prenons comme exemple la référence suivante : « T. Denoeux et R. Lengelle, “Initialisation des réseaux de rétropropagation avec prototypes”, Neural Networks 6, n^o 3, pp. 351-363 (1993) ». Cette information peut s’altérer pour devenir, disons : « Denueux et Lenjel, Neural Networks (1993) ». Une mémoire adressable par contenu devra alors pouvoir retrouver la référence complète à partir des données altérées. Du point de vue d’un système dynamique, on peut voir dans une information incomplète ou contenant des erreurs un point instable dans l’espace des états, alors que la bonne entrée correspond à un point stable (ou attracteur). On peut alors retrouver l’information complète et originelle en forçant l’état du système (l’information en cours de traitement) à se diriger vers un point stable à partir de n’importe où à l’intérieur des régions qui l’entourent.

53Hopfield constata que, si la dynamique d’un système physique est dominée par un grande nombre d’états stables vers lequel il est attiré, on peut considérer le système comme une mémoire adressable par contenu. Il conjectura alors que la stabilité des mémoires peut spontanément surgir dans des systèmes constitués de très nombreux éléments simples qui interagissent. Si, de plus, nous pouvons choisir n’importe quel ensemble d’états et facilement les forcer à être des états stables, alors le système devient un dispositif de mémoire potentiellement utile.

LA DYNAMIQUE DES RÉSEAUX

54On peut se servir d’un réseau de Hopfield pour récupérer des configurations telles que les images en noir et blanc, images qui peuvent contenir des erreurs ou avoir subi des pertes d’information. On appelle prototypes les configurations initiales. Nous donnerons un exemple élémentaire d’un réseau de Hopfield dans lequel les prototypes sont les dix chiffres 0, 1, 2,..., 9.

55Au moyen d’une représentation matricielle de 10 × 12 points, chaque chiffre peut être décrit à l’aide d’un mot binaire, c’est-à-dire par un vecteur de 120 nombres binaires :+1, pour représenter un point noir, et-1, un point blanc. Par un choix approprié des poids de connexion (comme ce sera expliqué ci-après), ces prototypes peuvent être « emmagasinés » dans la « mémoire » du réseau. Pendant sa phase d’opération (ou de rappel), le réseau essayera d’associer une configuration d’entrée donnée (c’est-à-dire un vecteur binaire à 120 dimensions) à un prototype—idéalement celui qui cadre le plus étroitement avec l’entrée. À la différence des poids des réseaux dont nous avons parlé jusqu’ici, ceux d’un réseau de Hopfield ne sont pas « appris » mais fournis d’emblée par l’utilisateur. Comme nous l’avons mentionné plus haut, la détermination des valeurs des poids peut être considérée comme l’emmagasinage des prototypes dans la mémoire du réseau. Voici l’idée de base qui guide le choix des poids.

56Supposons que, dans chacun des 10 prototypes, les 15^e et 78^e bits soient identiques, c’est-à-dire soient l’un et l’autre+1 ou-1. En essayant de restaurer une configuration C d’entrée partiellement altérée, le réseau va peu à peu modifier C pour le transformer en un des prototypes (P, disons). Si C doit converger vers P, le neurone 15 devra faire fortement pression sur le neurone 78 pour qu’il adopte son état à lui, puisque dans P ces deux bits doivent être les mêmes. S’il arrive que les bits des deux positions ne concordent que dans 8 prototypes, alors le neurone 15 devra envoyer au neurone 78 un signal de copier son état à lui qui soit un peu plus faible. En général, les bits des positions i et j seront identiques dans certains prototypes et ne le seront pas dans d’autres. La mesure de la force du signal sera alors la différence entre le nombre d’accords et le nombre de désaccords. Par exemple, si les i^ième et le j^ème bits sont concordants dans 8 prototypes et ne le sont pas dans 2, alors w_ij sera égal à 8 - 2 =6 ; s’ils concordent (ou ne concordent pas) dans les 10 prototypes, alors w_ij sera égal à 10-0 = 10 (ou w_ij = 0-10 =-10) ; s’il y a accord dans la moitié des prototypes, alors w_ij sera égal à 5 - 5 = 0.

57Si on exprime par Pi le i^ième bit du prototype P, le produit P_iP_j sera égal à 1 si les bits i et j de P sont identiques, et à—1 s’ils sont différents. Alors, la force de la connexion du neurone j avec le neurone i est donnée par la formule suivante :

58w_ij =∑ P_iP_j (2)

où l’addition s’étend à tous les prototypes P. (La formule ajoute 1 si le i^ième et le j^ième bits d’un prototype sont les mêmes, et soustrait 1 s’ils sont différents.) Les poids w_ij sont considérés comme égaux à zéro, car aucune connexion d’un neurone avec lui-même n’est possible.

59Qu’arrive-t-il durant l’opération du réseau ? Au temps t =0, une configuration d’entrée C (un vecteur binaire à 120 dimensions) est présentée au réseau. Le i^ième bit de C devient l’état initial du neurone i, de sorte que, au moment du démarrage, le réseau enregistre tout simplement l’entrée C. Aux unités de temps subséquentes, à savoir t = 1, 2, 3,..., les neurones vont subir des changements d’état qui correspondent aux modifications graduelles (un bit à la fois) de la configuration d’entrée C.

60Il est important de souligner qu’un seul neurone par unité de temps est autorisé à « déclencher », c’est-à-dire à (peut-être) changer son état. Celui des neurones qui peut « déclencher » est déterminé au hasard, le taux moyen de « déclenchement » étant le même pour tous les neurones. Ce mode « asynchrone » d’actualisation a pour objet de modéliser les délais de propagation aléatoire des signaux nerveux qu’on trouve dans les systèmes biologiques.

61L’état du neurone déclencheur—disons le i^ième neurone—au temps t +1 dépend de l’information qu’il reçoit de tous les autres neurones au temps t. Par exemple, si w_ij est - 8 et j est dans l’état +1, alors le signal d’entrée venant de j à i sera le produit (-8) (+1) = - 8. Des signaux tels que+4, 0, +10, -2 etc. qui arrivent des autres neurones peuvent être interprétés comme des « votes » sur la décision que devra prendre le i^ième neurone par rapport à son prochain état, les votes positifs pressant i de déclencher (c’est à-dire de supposer l’état +1) et les votes négatifs favorisant l’état inactif –1. L’état propre au neurone n’influence pas sa décision, puisqu’il n’y a pas de rétroaction d’un neurone sur lui-même. Le neurone i effectuera ensuite le déclenchement (état+1) si la somme des votes est positive, sinon il ne le fera pas (état-1).

62En résumé, voici la formule dont se sert le i^ième neurone pour calculer son prochain état :

où µ_j(t) désigne l’état du neurone ; au temps t et/est la fonction du seuil (d’activation) :

f(s) = +1, si s est plus grand que 0 ; f (s) =-1, dans le cas contraire

63Le vecteur µ(t) = (µ₁(t), µ₂(t),..., µ_n (t)) représente l’état du réseau de n neurones au temps t. On peut visualiser les états possibles du réseau en les considérant comme les sommets d’un « hypercube » dans un espace à n dimensions. Pour n = 3, les huit vecteurs à trois dimensions avec les composantes+1 ou-1 sont les sommets d’un cube ordinaire. Pour n plus grand que 3, il n’est plus possible de tracer l’hypercube, bien qu’il soit encore possible de l’imaginer. Au fur et à mesure que le temps change de t à t+1, l’état du réseau voyage d’un sommet à un autre sommet qui lui est adjacent (puisqu’un seul neurone peut effectuer un déclenchement au temps t, une seule coordonnée du vecteur d’état peut changer à n’importe quelle unité de temps donnée). On considère que le réseau a convergé quand (et si) ce voyage de sommet à sommet cesse, c’est-à-dire si l’état du réseau devient stable.

64L’état d’équilibre S constitue la mémoire restaurée du réseau, laquelle, en règle générale, correspond au prototype qui ressemble le plus à la configuration d’entrée. Cependant, la nature non déterministe du réseau peut amener celui-ci à converger vers une fausse configuration—qui ne figure pas dans l’ensemble des prototypes—ou à présenter un comportement chaotique et continuer d’errer dans une petite région de l’espace des états.

65Dans une des simulations informatiques de Hopfield, m configurations (pour différentes valeurs de m) furent générées au hasard et emmagasinées selon l’équation (2). Chacun de ces m « prototypes » fut ensuite utilisé comme entrée, et le réseau mis en marche jusqu’à ce qu’il devienne stable. Le raisonnement invoqué par Hopfield pour choisir des prototypes au hasard était que l’information prétraitée par un système nerveux en vue d’une mise en mémoire efficace nous semblerait être aléatoire. À cet effet, il citait l’exemple du caractère aléatoire des séquences de l’ADN. « Les vecteurs de mémoire aléatoires simulent donc l’information réelle efficacement encodée, tout autant qu’ils représentent notre ignorance »13.

66Les résultats des simulations suggéraient que le nombre de prototypes doit être petit en comparaison du nombre de neurones, sinon l’erreur de rappel pourrait s’avérer grave. Hopfield concluait—et l’expérience l’a confirmé—que pour un rappel relativement exact, un taux de 15 prototypes par 100 neurones ne devait pas être dépassé. Ainsi, le rappel de 10 prototypes nécessiterait environ 70 neurones et à peu près 5000 poids.

67Lorsque les neurones peuvent avoir des fonctions d’activation continue (figure 3.3. (b)), les changements d’état du réseau cessent de se produire à des intervalles de temps discrets pour se produire de façon continue. De tels systèmes possèdent en général une dynamique plutôt complexe et l’analyse de leur comportement requiert des outils mathématiques très élaborés.

68L’enthousiasme suscité au départ par le travail de Hopfield durant les années 80 fut suivi d’attentes plus modérées. Dès 1987, les Laboratoires AT & T Bell annoncèrent la mise au point de puces neuronales basées en grande partie sur le réseau de Hopfield14 ; toutefois, les applications du modèle de l’éminent physicien restèrent limitées. En 1992, Jacek M. Zurada, un ardent chercheur dans ce domaine, évalua la situation en ces termes :

Il est difficile de remonter à la source des solutions offertes par les réseaux ou de les expliquer ; souvent, elles sont dues à des facteurs fortuits. [...] Toutefois, on devrait insister sur le fait que l’approche par les systèmes dynamiques des tâches cognitives n’en est encore qu’au début de son développement. L'application des modèles dynamiques à des problèmes réels d’association ou d’optimisation au-delà de leur portée actuelle requerra des progrès scientifiques considérables15.

69Bref, la technique est sans doute prometteuse, mais il ne faut pas s’emballer trop vite.

DÉVELOPPER LE COÛT DES VRAIES FRAMBOISES

70N’importe qui peut reconnaître une framboise fraîche. En revanche, savoir si un échantillon de pulpe est à 100 % de la framboise est une autre paire de manches, surtout si cet échantillon est surgelé ou sulfaté. Nous sommes en présence ici d’un problème commercial auquel les fabricants de confitures doivent faire face lorsqu’ils se servent de pulpes pour préparer des confitures de style maison ou de délicieuses marmelades. Comment s’assurer que le fournisseur n’a pas ajouté du sucre ou des fruits moins chers aux framboises, diluant la pulpe et augmentant du même coup sa marge de profit ?

71Une méthode originale pour détecter les pulpes de framboise frelatées a été mise au point par une équipe de chercheurs de l’Institut de recherche alimentaire de Norwich (Grande-Bretagne). Cette méthode, basée sur les techniques spectroscopiques et s’appuyant sur le puissant outil mathématique qu’est la transformée de Fourier, utilise des sections du spectre infrarouge moyen pour identifier des échantillons. Ces sections sont une sorte d’empreinte digitale moléculaire très sensible à la composition chimique exacte de l’échantillon16 Mais comme différentes pulpes de fruits peuvent avoir des spectres très semblables, les changements résultant du frelatage par ajout d’un autre fruit qui s’opèrent dans le spectre ne sont pas toujours évidents à l’œil nu. J. K. Holland, E. K. Kemsley et R. H. Wilson, trois chercheurs de l’Institut, décidèrent d’entraîner un réseau de neurones pour les aider à différencier les spectres de framboise pure et ceux d’autres pulpes (moins chères), en particulier les framboises frelatées.

72Ils commencèrent par constituer une base de données de quelque 900 spectres des différents types de pulpes de fruits et de pulpes de framboises auxquelles avaient été incorporées de la saccharose, de la pomme ou de la prune, ingrédients potentiellement falsificateurs. La base de données fut ensuite séparée en trois groupes à peu près égaux, à savoir : un ensemble d’apprentissage pour la mise au point du réseau, un ensemble de réglage pour ajuster les paramètres du modèle et enfin un ensemble de vérification pour valider la performance du réseau. Environ les deux tiers des échantillons de chaque ensemble provenaient d’autres fruits que les framboises, le dernier tiers étant également réparti entre les spectres de framboises pures et les spectres de framboises frelatées. Pour les besoins de l’analyse, chaque spectre était représenté par 50 valeurs numériques appelés scores d’éléments principaux.

73Le réseau possède une première couche de 8 neurones, lesquels reçoivent chacun comme entrée les 50 scores d’éléments principaux de l’échantillon. Les données de sortie en provenance de cette couche d’entrée sont alors transmises à un neurone unique qui produit comme donnée de sortie définitive un nombre entre 0 et 1. Afin d’obtenir la réponse désirée du réseau—1 pour la framboise et 0 pour toute autre substance-, les valeurs des 408 poids synaptiques furent ajustées par rétropropagation. À la fin de chaque cycle d’entraînement, l’ensemble de réglage fut utilisé pour calculer les erreurs de prédiction (la différence entre la valeur désirée et la sortie du réseau). Lorsque la somme des erreurs au carré atteint, sur la totalité de l’ensemble de réglage, un minimum—plus précisément, lorsqu’elle augmente pendant 10 cycles successifs-, l’apprentissage est terminé. Ce type de critère d’arrêt se révéla efficace dans la pratique pour éviter un surentraînement du réseau.

74La capacité du réseau à généraliser—c’est-à-dire à classifier correctement de nouveaux spectres de pulpes—fut testée sur des échantillons (l’ensemble de vérification) qui n’avaient pas participé à l’apprentissage. Une réponse du réseau plus grande que 0,5 fut considérée comme indiquant une pulpe de framboise pure, tandis qu’une sortie inférieure à 0,5 était interprétée comme n’étant pas de la framboise. Le réseau ainsi entraîné classifia correctement 97 % des 280 échantillons dans l’ensemble de vérification. On peut voir les résultats de cette classification dans la figure 3.6. La sortie du réseau est tracée en face du numéro de code de l’échantillon (les symboles tracés représentent le type d’échantillon correct)17.

75La puissance de la combinaison spectroscopie infrarouge/réseau de neurones repose sur sa rapidité : le spectre infrarouge moyen d’un échantillon de pulpe peut être recueilli en moins de cinq minutes, le réseau ne prenant que quelques secondes pour effectuer une prédiction. Une méthode semblable avait déjà été employée pour vérifier l’authenticité d’extraits de café18 (Les rumeurs voulant que l’Institut de recherche alimentaire aurait été pressenti par un cartel de la drogue intéressé par leurs services sont sans fondement aucun !)

76Les réseaux de neurones ne constituent pas le seul moyen efficace pour analyser les spectres. Comme le dit Kate Kemsley, membre de l’équipe qui a mis au point la nouvelle technique, « il était amusant d’essayer l’approche neuronale, mais je dois dire qu’il n’était pas indispensable d’utiliser les réseaux de neurones. Dans chacun des deux cas [celui des framboises et celui du café], les méthodes d’algèbre linéaire auraient marché tout aussi bien ».

FIGURE 3.6

UN PROBLÈME D’ITINÉRAIRE

77Le problème du commis voyageur vit le jour aux États-Unis dans les années 30, à propos de questions pratiques venant de l’industrie et de l’administration. Dans les années qui suivirent la crise de 1929, le recours aux modèles mathématiques pour les décisions d’ordre quantitatif, naquit comme une branche indépendante des mathématiques appliquées, ce qu’on appellera plus tard la recherche opérationnelle. De manière tout à fait indépendante, les Britanniques développèrent leurs propres techniques opérationnelles durant la Seconde Guerre mondiale, et l’appliquèrent à la solution de problèmes divers concernant des tactiques, comme l’usage efficace du radar pour suivre la trace des avions ennemis. Personne ne semble savoir de façon précise pourquoi on lui a donné un tel nom [Traveling Salesman]. Durant les années 70—c’était à prévoir—, certains essayèrent de le rebaptiser « problème de la personne itinérante » [Traveling Salesperson Problem]. Mais comme on avait pris l’habitude de désigner ce problème par le sigle TSP en anglais [et PCV (le Problème du Commis Voyageur) en français], la délicate question du sexe du voyageur (ou de la voyageuse) put être évitée !

78Ce que les mathématiciens appellent couramment le PCV est en réalité un problème plus général : étant donné un ensemble {1, 2, 3,..., n} de n « villes » et les « coûts » c(i, j) du déplacement de la ville i à la ville ;, trouvez un ordre des villes—c’est-à-dire un tour—avec le minimum de coûts tel que chaque ville figure une seule fois (le coût d’un tour étant, bien sûr, la somme des coûts résultant du voyage d’une ville à l’autre dans l’ordre donné). Cette version plus simple permet plusieurs variantes. Par exemple, les coûts entre les villes peuvent ne pas être les mêmes dans les deux directions ; s’ils le sont, c’est-à-dire si

c(i,j) = c(j, i)

nous nous trouvons devant un problème symétrique. Aussi, l’inégalité dite « triangulaire » :

c(i, k) ≤ c(i,j) + c(j, k)

qui est vraie automatiquement quand les « coûts » sont des distances réelles, peut cesser de l’être à d’autres occasions. En d’autres termes, cela signifie que le coût pour aller directement d’une ville i à une ville k peuvent excéder ce que cela coûte en faisant un détour par la ville j. Les distances entre les sommets de tout triangle satisfont l’inégalité mentionnée ci-dessus, d’où son nom. Dans ce qui suit, nous supposerons que nous avons affaire au PCV classique (un commis voyageur qui se déplace de ville en ville), et donc que les coûts c(i,j) sont les distances réelles, l’itinéraire le plus économique étant celui qui est le plus court.

79En 1954, trois mathématiciens de la Rand Corporation résolurent le premier PCV de grande envergure en empruntant les méthodes de la programmation linéaire—une technique pour résoudre certains problèmes d’optimisation qui utilise une approche géométrique. Le problème était un pur pcv, car il comportait de vraies villes (Washington et 48 autres grandes villes américaines). George Dantzig, Delbert Fulkerson et Selmer Johnson représentèrent chaque tournée possible par le sommet d’un polyèdre dans un « espace » de plus de 2000 dimensions. Avec cette représentation géométrique, trouver l’itinéraire le plus court devient alors un problème de programmation linéaire standard.

80La recherche des solutions exactes à des PCV de plus en plus grands prit l’allure d’une sorte de concours non officiel parmi les chercheurs. Bien entendu, seuls de « vrais » problèmes furent acceptés, par exemple, ceux qui proviennent de situations réalistes dans l’administration ou l’industrie. Avec les années, l’action conjuguée des algorithmes améliorés et des ordinateurs plus puissants eut pour résultat qu’un record après l’autre fut battu. Le titre mondial est détenu actuellement par une équipe de quatre informaticiens américains19 qui, en 1994, trouvèrent le plus court itinéraire d’un problème comportant 7397 villes20. Cette performance nécessita des ressources informatiques considérables : on a estimé que, pour parvenir à la solution, l’algorithme avait eu besoin d’un temps de machine de 3 à 4 ans sur un réseau d’ordinateurs. Toutefois, comme l’équipe en question fit tourner ses programmes tard dans la nuit, pendant que les ordinateurs restaient fermés, le coût réel fût probablement négligeable. Quoi qu’il en soit, dans ce genre de concours, la vitesse ou le coût comptent moins que la taille du problème (le nombre de villes). Mais, quand il s’agit d’applications réelles, le temps de calcul est un facteur majeur, et la généralité de la méthode de solution l’est tout autant.

LE SENTIER NEURONAL VERS L’OPTIMISATION

81Dans quelle mesure les réseaux de neurones peuvent-ils servir à résoudre les problèmes d’optimisation ? Aux yeux de l’infatigable commis voyageur, aucune des solutions neuronales existantes ne semble faire le poids avec les techniques plus classiques. Le fameux puzzle du commis voyageur est un choix naturel pour tester une méthode d’optimisation, mais comporte aussi certains aspects plus délicats. Regardons cela d’un peu plus près.

82L’approche neuronale du PCV a été proposée la première fois par Hopfield et D. W. Tank en 198521 Pour résoudre un problème à n villes, leur méthode requérait n² neurones continus, connectés chacun à tous les autres. Nous imaginons les neurones disposés comme une grille ou une matrice carrée n par n. Chaque neurone possède une étiquette à deux chiffres (i, ;‘) indiquant sa position sur la matrice : i^ième rangée et j^ième colonne. L’état du neurone (i,j) est une variable x_ij qui peut prendre n’importe quelle valeur entre 0 (ne déclenchant pas) et 1 (déclenchant au maximum).

83L’état du réseau à un moment donné t est entièrement décrit par les n² chiffres x_ij. La valeur de x_ij (entre 0 et 1) représente la force dans la « croyance » que la ville i est dans la position ; de l’itinéraire. Des solutions possibles du problème—c’est-à-dire des itinéraires qui visitent chaque ville une seule fois—sont représentées par certaines matrices binaires : un 1 dans la ligne i, colonne j, et des 0 dans les autres positions de cette ligne, signifient que la ville i est la j^ième ville à visiter. Par exemple, une ligne 5 telle que celle-ci :

0 0 1 0... 0 0

indique que la ville 5 est la troisième dans l’itinéraire. La matrice ci-dessous encode un itinéraire qui visite cinq villes dans l’ordre 2, 1, 5, 3, 4

0 1 0 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 0 1
0 0 1 0 0

84La longueur d’un itinéraire peut s’exprimer comme une fonction L (en fait, un polynôme) à n² variables x_ij. Pour garantir que chaque ville figure une seule fois dans l’itinéraire, il doit y avoir exactement un neurone déclencheur par rangée. Cette condition peut parfaitement s’écrire sous forme d’équation, ou contrainte :

85La condition additionnelle à l’effet que chaque position ; dans l’itinéraire soit occupée par une seule ville conduit à une seconde contrainte

86On peut maintenant formuler le problème du commis voyageur comme un problème de programmation linéaire dans les entiers, à savoir trouver les nombres entiers x_ij qui satisfassent aux contraintes ci-dessus pour lesquelles la valeur de la fonction L est un minimum. C’est précisément ce genre de problème que le réseau de rétroaction à neurones continus de Hopfield et Tank—mis en œuvre comme un circuit analogique ou simulé sur un ordinateur numérique—essaie de résoudre. Son état (stable) final est la réponse du réseau qui, une fois décodée en un itinéraire, correspond (espérons-le) à la solution. La figure 3.7 illustre cette solution neuronale d’un problème comportant 10 villes.

87Pour justifier leur utilisation des neurones continus, Hopfield et Tank invoquèrent la nécessité d’opérations logiques souples ou « floues »22 :

Pendant une convergence analogique, plusieurs solutions ou énoncés conflictuels peuvent être considérées simultanément par l’intermédiaire de variables continues. C’est comme si les opérations logiques d’un calcul pouvaient recevoir des valeurs continues situées entre le « vrai » et le « faux », et n’évoluer vers la certitude que vers la fin du calcul. Cela est évident pendant le processus de convergence du PCV [figure 3.7]. [...] Cet emploi d’une variable continue située entre le vrai et le faux est semblable à la théorie des ensembles flous. Les neurones à deux états ne reproduisent pas cette caractéristique calculatoire.

88Un inconvénient de l’approche qui vient d’être évoquée ci-dessus est l’ampleur des moyens de calcul que cela exige : résoudre, en effet, un problème de 1000 villes requiert un million de neurones, chacun étant connecté à tous les autres—mille milliards de poids de connexions ! Dans un livre récent23, David Johnson, des laboratoires de AT & T, et Lyle McGeoch, de Amherst College, évaluent et comparent les diverses techniques pour résoudre le PCV, y compris les algorithmes génétiques et les réseaux de neurones. Ils constatent que, même si Hopfield et Tank ont trouvé des itinéraires optimaux pour des exemples de 10 villes, leurs réseaux « ne sont pas toujours parvenus à converger vers de vraies solutions [c’est-à-dire des tours] pour n = 30, et la meilleure solution qu’ils aient jamais trouvée était toujours supérieure de 17 % à la solution optimale ».

FIGURE 3.7

89Une approche différente, dans laquelle les neurones sont considérés comme des points du plan, s’est révélée efficace lorsque le problème comporte un grand nombre de villes. Au cours du calcul, les neurones (surnommés « fourmis ») se déplacent peu à peu vers les villes comme s’ils étaient connectés par une longue corde en forme de boucle. Ils finissent par former un polygone qui ressemble à un itinéraire physique, chaque ville étant « occupée » par un neurone. À l’aide d’un tel réseau « géométrique », Shara Amin et José Luis Fernandez, du British Telecom, obtinrent une solution (avec une précision de 4 %) pour un échantillon24 de 30 000 villes sélectionnées au hasard—la solution la plus considérable jamais atteinte par cette méthode, jusqu’à ce jour (1994).

90Les mathématiques qui sous-tendent ces réseaux géométriques s’inspirent des idées de Teuvo Kohonen, de l’Université de Technologie d’Helsinki. En particulier, ses self-organizing maps25 et l’algorithme d’apprentissage qui les accompagne, appelé le gagnant-emporte-tout26. Les contributions les plus originales de Kohonen au calcul neuronal ont trouvé des applications fructueuses dans beaucoup de domaines, tels que la reconnaissance de la parole et le contrôle des robots.

91Johnson et McGeoch concluent leur analyse des solutions neuronales du PCV en s’interrogeant sur leur valeur pratique. Mais ils ne se prononcent pas sur le potentiel de l’optimisation neuronale dans son ensemble : « Si les nombreux travaux de recherche qui ont trait au perfectionnement de ces algorithmes [neuronaux] doivent avoir des conséquences pratiques, ce sera probablement dans d’autres domaines, où les leçons tirées du cas du PCV pourraient produire des résultats plus utiles »27.