FR 2719399 A1 19951103 FR 9405323 A 19940502 "Procédé et dispositif d'extraction d'un sous-ensemble d'objets optimisant une mesure, en utilisant un réseau de neurones" DESCRIPTION Domaine technique La présente invention concemrne un procédé et un dispositif d'extraction d'un sous-ensemble d'objets optimisant une mesure, en utilisant un réseau de neurones. Etat de la technique antérieure Les réseaux neuromimeétiques ont largement été étudiés depuis plusieurs années et des applications diverses ont été développées, notamment pour la résolution de problèmes d'optimisation, et de reconnaissance de formes. Les réseaux neuromimétiques utilisent une information numérique et sont des systèmes qui effectuent des calculs inspirés du comportement des neurones physiologiques. Un modèle neuromimétique est caractérisé par trois constituants de base: un réseau de neurones formels, une règle crd'activation et une dynamique d'évolution. Le réseau est composé d'un ensemble de neurones formels. Un neurone formel est une unité de calcul constituée d'une entrée, appelée potentiel (noté u) et d'une sortie, correspondant à un niveau d'activation numérique (noté p). A chaque instant, le niveau d'activation de chaque neurone est communiqué aux autres neurones. Les neurones sont en effet connectés ensemble par des connexions pondérées, appelées poids synaptiques. Le poids de la connexion entre la sortie du neurone i et rentrée du neurone j est noté w. La quantité totale d'activation en entrée u, que le neurone j reçoit des autres neurones à chaque instant est utilisée par ce neurone pour mettre à jour sa sortie. On rl'appelle parfois potentiel (ou potentiel d'activation) du neurone j. La règle d'activation d'un modèle neuromimétique est une procédure locale que chaque neurone suit en mettant à jour son niveau d'activation en fonction du contexte d'activation des autres neurones. La sortie d'un neurone est ainsi donnée par une fonction de transfert non-linéaire appliquée au potentiel. Cette fonction non-linéaire peut être une fonction à seuil, appelée aussi fonction de Mac-Cullogh et Pitts, et définie, pour le neurone i considéré à la date t, par: IPi(t) = 1 si u (t) > 0 pi (t) = 0 si u,(t) aléatoirement ( 0 ou 1). Puis le réseau évolue en mettant à jour ses neurones. Pour mettre à jour un neurone i à rinstant t, on calcule son potentiel à cette date; % (t) = u (t - 1) + A (t) (2) La variation de potentiel au; (t) va correspondre à la dynamique d'évolution. Différents modèles existent dans rart connu pour définir cette dynamique. Suivant le signe de *u, (t) entre deux mises à jour du neurone i, on dit que le neurone est inhibé (variation de potentiel négative qui tend à mettre la sortie à 0) ou excité (variation de potentiel positive qui tend à mettre la sortie à 1). Si son potentiel est strictement positif, le neurone met sa sortie à 1: il est activé. Si son potentiel est strictement négatif, il met sa sortie à 0: il est désactivé. Si son potentiel est nul, la valeur de la sortie reste inchangée. Ainsi, la sortie du neurone i peut être amenée à changer entre deux mises à jour. On dit que le réseau a convergé si, pour chaque neurone, aucune mise à jour ne modifie le potentiel du neurone. Le mode de convergence est défini par l'ordre dans lequel sont mis à jour les neurones. Son choix est de grande importance pour la qualité de la convergence. Le mode de convergence peut être: - asynchrone: un neurone est mis à jour à la fois. La nouvelle sortie calculée lors de sa mise à jour sert à la mise à jour des autres neurones. Les neurones peuvent être mis à jour séquentiellement dans un ordre fixé (on parle de mode asynchrone séquentiel) ou aléatoirement (on parle de mode asynchrone aléatoire); - synchrone: tous les neurones sont mis à jour simultanément; - synchrone par bloc: on met à jour de façon synchrone des blocs de neurones. On va à présent présenter quelques dynamiques d'évolution conçues pour résoudre des problèmes d'optimisation. Le modèle ayant servi de base aux principaux algorithmes neuronaux d'optimisation est le modèle présenté par J. Hopfield et D. Tank dans rarticle intitulé "Neural computation of decizions in optimization problems" (Biological Cybemetics, vol. 52, pages: 141-152, 1985). Ils définissent une fonction énergie E: E = _É w; p, pi - l, P. (3) 2i=1 j=l *=1 Les sorties neuronales p, sont analogiques, comprises entre 0 et 1, et I; représente un biais d'entrée. Cette énergie peut être vue comme rénergie physique d'un système de verres de spins. L'énergie E codant le problème, le problème revient à minimiser cette énergie à la convergence du réseau. J. Hopfield, dans un article intitulé Neural networks and physical systems with emergent collective computational abilities" (proceedings of the National Academy of Sciences, vol. 79, pages 2554-2558, 1982) démontre (théorème de Hopfield) que: - si la dynamique d'évolution du réseau est: Ap, - si la règle d'activation utilisée est celle de Mc Culloch-Pitts, -et si la matrice des poids synaptiques est symétrique (w; =wA), - alors, pour tout neurone i, et à toute date t: àE(t):gO Ainsi l'énergie va décroître, au cours de l'évolution du système, jusqu'à atteindre un minimum. L'objet de l'invention est de proposer un procédé et un dispositif d'extraction d'un sous-ensemble d'objets issus d'un ensemble, deux à deux non en relation ou en relation et optimisant une mesure qui peuvent avantageusement utiliser un réseau neuromimétique original. Obiet de rinvention L'invention concerne un procédé d'extraction crun sous- ensemble d'objets, tels que des trajectoires potentielles dans une application de vélocimétrie, optimisant une mesure, en utilisant un réseau de neurones, caractérisé en ce qu'il comprend les étapes suivantes: - une étape de construction d'un réseau de neurones récursif à partir des objets et des relatons entre les objets en associant à chaque objet la sortie binaire d'un neurone formel pj(t) à une date t: p1(t) = 1 =l'objet appartient au sous-ensemble recherché. p1(t) = 0 = l'objet n'appartient pas au sous-ensemble recherché; - une étape d'utilisation d'un procédé d'inhibition afin d'obtenir des sousensembles d'objets deux à deux non en relation ou en relation, et de passer d'un sous-ensemble à un autre en essayant d'augmenter la qualité de la solution; - une étape d'initialisation de la sortie et du potentiel associé à chaque neurone; -une étape d'exploitation dynamique récursive du réseau; - une étape de choix parmi les sous-ensembles listés du meilleur par comparaison des qualités. Avantageusement, I'étape d'initialisation de la sortie et du potentiel associée à chaque neurone est telle que la sortie et le potentiel associé à chaque neurone vérifient, pour chaque neurone, les conditions suivantes: -sur les sorties des neurones: si on initialise un neurone i avec une sortie qui vaut I (neurone activé), alors les neurones j correspondant à des objets en relation avec l'objet i (e,. = 1) doivent être désactivés. (pi(t=0)=1) =:> (Vje{l.... N} e,=1=>p1(t=O)=O) - sur les potentiels: p,(t=o)= l u,(t=o) (Vje{l....N} e,=O=> pj(t=O)=O) - sur les potentiels: p,(t=O)=l≤u,(t=o)_o p,(t=O)=O)=u,(t =o) désactivés au même instant. L'invention concerne également un dispositif qui comprend un réseau de neurones comportant: - un circuit de choix d'un entier i entre 1 à N; une première mémoire table des valeurs des sorties pi des neurones reliée à la sortie du circuit de choix d'un entier; - une seconde mémoire table des voisins de chaque neurone reliée à la sortie du circuit de choix d'un entier; - une troisième mémoire des relations entre les objets reliée à rentrée de la seconde mémoire; - une quatrième mémoire des potentiels des neurones reliée à la sortie de la seconde mémoire, à la sortie du circuit de choix d'un entier; - une cinquième mémoire contenant la valeur courante de la fonction qualité E à optimiser reliée à la sortie de la première mémoire; - un premier circuit de calcul permettant de calculer la variation de potentiel à appliquer au neurone i relié à la sortie du circuit de choix d'un entier, à la sortie de la cinquième mémoire, à la sortie de la troisième mémoire et à la sortie de la première mémoire; - un second circuit de calcul permettant de calculer la variation de potentiel à appliquer aux neurones voisins du neurone i relié aux sorties du circuit de choix et des cinquième, troisième et première mémoires; - un premier additionneur recevant les sorties du premier circuit de calcul et de la quatrième mémoire et relié en entré à la quatrième mémoire; -au moins un second additionneur recevant les sorties du second circuit de calcul et de la quatrième mémoire et relié en entrée à la quatrième mémoire; - au moins deux circuits fonctions de seuillage binaire F reliés respectivement aux sorties de ces deux additionneurs et à l'entrée de la première mémoire. Ce réseau de neurones s'applique aux procédés de gestion optimale de moyens au cours du temps concernant de faç,on générale: - la vélocimétrie; - la résolution des problèmes de routage dans les réseaux de télécommunication; - roptimisation des communications entre satellites; -roptimisation de géométrie de disposition de composants dans la C.A.O.; la planification des horaires de trains de vols; - la planification de la production industrielle. Brève description des dessins - La figure 1 illustre les différentes étapes du procédé de l'invention; la figure 2 illustre rétape d'exploitation dynamique; - la figure 3 illustre un réseau de neurones associé au dispositif de mise en oeuvre du procédé de l'invention. Exposé détaillé de modes de réalisation Le lexique situé en fin de description fait partie de la description. Pour faciliter la description on présentera dans la suite le cas o ron cherche des sous-ensembles deux à deux non en relation. Bien entendu le procédé de rinvention s'applique également à la recherche de sous- ensembles d'objets deux à deux en relation en substituant à la matrice (e.) des relations, matrice (1-e,). Le procédé de rinvention comprend plusieurs étapes, illustrées sur la figure 1. On utilise un réseau de neurones formels et apte à déterminer un sousensemble d'objets deux à deux non en relation de qualité maximum, o io la qualité est mesurée par une fonction quelconque E({p,}) des sorties des neurones. On a les étapes suivantes: - construction d'un réseau de neurones récursifs à partir des objets et des relations entre les objets en associant à chaque objet la sortie binaire drun neurone formel p, (t): p, (t) =1 => robjet appartient au sous-ensemble recherché, p,(t) =0=> l'objet n'appartient pas au sous-ensemble recherché; - utilisation d'un procédé d'inhibition afin d'obtenir des sous- ensembles drobjets deux à deux non en relation. On passe d'un sousensemble à un autre en essayant d'augmenter la qualité de la solution; initialisation de la sortie et du potentiel associé à chaque neurone de telle sorte qu'ils vérifient, pour chaque neurone, les conditions suivantes: 25. sur les sorties des neurones: si on initialise un neurone i avec une sortie qui vaut 1 (neurone activé), alors les neurones j correspondant ài des objets en relation avec robjet i (e, = 1) doivent être désactivés, (p(t=0)= 1)=> (Vj e{,...,N} e, =lpj(t=O)=O) sur les potentiels: p,(t =o)= I U,(t =o)o p (t=o)=O sorties des autres neurones et des relations existant entre les objets. L'expression mathématique de la correction à appliquer au potentiel d'un o neurone diffère suivant qu'il est considéré comme centre d'un bloc ou comme voisin crd'un centre crd'un autre bloc. Les corrections sont définies de telle sorte que dès qu'un neurone i est activé, tous les neurones j vérifiant e, = 1 sont désactivés au mérme instant L'exploitation dynamique génère des sous- ensembles d'objets deux à deux en relation, chacun des sous-ensembles pouvant être associé à un maximum local de la fonction qualité. A chaque fois que le réseau a convergé, on obtient après décodage des sorties des neurones, un sous-ensemble d'objets deux à deux non en relation maximisant (localement) la fonction qualité. On mémorise chacun de ces sous-ensembles. Globalement on obtient une liste de sous- ensembles solutions. - choix parmi les sous-ensembles listés du meilleur par comparaison des qualités. Exdloit dvnamique récursive de ce second réseau de neurones On met à jour le 'bloc" de neurones ( i et les neurones j en relation avec i) correspondant de façon synchrone (tous les neurones du bloc sont mis à jour simultanément) en considérant le neurone i comme centre du bloc et les neurones j comme voisins du centre. L'exploitation dynamique consiste donc à balayer rensemble des blocs de neurones dans un certain ordre (dynamique asynchrone) et à mettre à jour les neurones de chaque bloc de manière synchrone: on parle de dynamique synchrone par bloc ou bloc-synchrone. Détermination de la correction à aoppliquer au potentiel u, d'un neurone i à une date t Elle diffère suivant que le neurone dont on veut corriger le potentiel est considéré comme centre d'un bloc ou comme voisin d'un autre centre. Quand on considère un bloc de neurone de centre i et de voisins V = {j} (pour tout j dans V, e, = 1) à la date t, on regarde si le neurone i est activé ou non: - si le neurone i est activé, on laisse le bloc inchangé; -si le neurone i est désactivé, on exécute les étapes qui suivent: * on mémorise la valeur de la mesure de la qualité obtenue à ladate t-: E{,(t-}); * on teste l'évolution suivante du réseau: on active le neurone i et on désactive les neurones j voisins si ceux- ci sont activés. On en déduit la variation de la mesure de la qualité correspondante E({p (t - l)}). A) La correction à appliquer au potentiel du neurone i est donnée par une combinaison linéaire de deux termes: - un terme qui a pour but d'exciter le neurone i, s'il est désactivé, avec une certaine probabilité en fonction de la valeur de E({p,(t -1)}). Par exemple rexcitation peut être donnée par: * max(O,AE({p, (t - 1)1)), * (i - p (t)). max(O, AE(p, (t -,)})), * une procédure de Metropolis à une certaine température dans une méthode de recuit simulé, * une procédure de Creutz à une certaine énergie dans une méthode de recuit microcanonique. Si le réseau a été mis à jour moins d'un certain nombre de fois depuis la dernière convergence, alors on applique une inhibition pour essayer d'augmenter, à la convergence suivante, la qualité du sous-ensemble d'objets déterminé lors de la dernière convergence du réseau. Autrement un procédé crd'interruption stoppe la prise en compte de cette inhibition. Par exemple, cette inhibition peut consister à: * inhiber un certain nombre de neurones, fixé par rutilisateur, tirés aléatoirement, * inhiber un nombre aléatoire de neurones tirés aléatoirement, * inhiber des neurones parmi ceux qui correspondent à des objets incompatibles avec beaucoup d'autres. Globalement, le réseau alterne des phases de pulsation (quand cette dernière inhibition est prise en compte) et des phases de relaxation (quand le procédé d'interruption stoppe la prise en compte de rinhibition). Au cours de la phase de relaxation, le réseau converge. Une fois que le réseau a convergé, on applique à nouveau une inhibition (phase de pulsation). On alterne ainsi des phases de pulsation et de relaxation un certain nombre de fois, fixé par rutilisateur (en fonction du temps qu'il a pour trouver une solution, de la qualité de la solution qu'il recherche). A rissue de chaque phase de relaxation, c'est-à- dire à chaque convergence, les neurones dont la sortie vaut I codent un sous- ensemble d'objets deux à deux non en relation. B) La correction à appliquer au potentiel de neurone j voisin de i à la date test donnée par un terme qui a pour but d'inhiber le neurone j crd'une quantité égale à rexcitation reçue par le neurone i à la même date. Par exemple, rinhibition peut être donnée par: a -e,.max(O, iE({pj(t-)})) si rexcitation sur i à t vaut max(o, AE({pi (t- l)})) -( lp,(t)).e.max(O,AE({p,(t -l)})) si l'excitation sur i à t vaut (I-p(t)). max(O,&E({pj(t-1)) Avantageusement on borne le potentiel de chaque neurone entre deux valeurs fixées par rutilisateur pour accélérer la convergence. Par exemple: - on borne le potentiel entre des valeurs de rordre de grandeur des corrections à appliquer au potentiel quand le neurone est mis à jour; - on borne les valeurs des potentiels entre -10 et 10-=: ainsi toute correction strictement négative à appliquer sur le potentiel d'un neurone activé le désactive et toute correction strictement positive à appliquer sur le potentiel d'un neurone désactivé l'active. La figure 3 donne un dispositif associé à ce réseau de neurones en phase de relaxation. Ce réseau comprend: - une première mémoire 55 table des valeurs des sorties pi des neurones; - une seconde mémoire table 56 liste des voisins de chaque neurone; - une troisième mémoire 57 des relations entre les objets; - une quatrième mémoire 58 des potentiels des neurones; - une cinquième mémoire 67; - un premier circuit de calcul 59 permettant de calculer la variation de potentiel à appliquer au neurone i; -un second circuit de calcul 60 permettant de calculer la variation de potentiel à appliquer aux neurones voisins du neurone i; - un premier additionneur 61 recevant les sorties du premier circuit de calcul et de la quatrième mémoire; - au moins un second additionneur 62 recevant les sorties du second circuit de calcul et de la quatrième mémoire; - au moins deux circuits 64 et 65 fonctions de seuillage binaire F reliés respectivement aux sorties de ces deux additionneurs. Dans le cas d'un dispositif numérique, ces différents éléments sont connectés (directement ou indirectement) à une horloge. LEXIQUE Objet Un objet est une trajectoire potentielle dans une application de vélocimétrie. Neurone Un neurone iest défini par un potentiel u, et par une sortie binaire p,. Quand, au cours de l'exploitation dynamique du réseau, le neurone est considéré à la date t, alors: - on calcule une correction Au, (t) à appliquer au potentiel u, (t + 1) = u,(t) + Aou(t); on met à jour la sortie: si u,(t+I)>o alors p,(t+l)=l si u,(t+l) dans une application de vélocimétrie. On a un ensemble d'objets dont on cherche à extraire un sous- ensemble vérifiant une certaine propriété basée sur des relations entre les objets. Considérés deux par deux, il existe ou non une relation (issue d'une application) entre les objets. Si un objet i est en relation avec un objet j, alors e, = 1. Sinon e,. = 0.(ej) est la matrice des relations entre les objets. Remarque: Le procédé est équivalent à rechercher le sous-ensemble d'objets maximisant la mesure E. Il suffit pour cela de considérer la matrice (i-e,) et d'utiliser le procédé décrit dans la présente invention. REVENDICATIONS 1. Procédé d'extraction d'un sous-ensemble d'objets, tels que des trajectoires potentielles dans une application de vélocimétrie, optimisant une mesure, en utilisant un réseau de neurones, caractérisé en ce qu'il comprend les étapes suivantes: - une étape de construction d'un réseau de neurones récursif à partir des objets et des relations entre les objets en associant à chaque objet la sortie binaire d'un neurone formel p, (t) à une date t: p, (t) = 1 => l'objet appartient au sous-ensemble recherché. p, (t) =0 I'objet n'appartient pas au sous-ensemble recherché; - une étape d'utilisation d'un procédé d'inhibition afin d'obtenir des sous- ensembles d'objets deux à deux non en relation ou deux à deux en relation, et de passer d'un sous-ensemble à un autre en essayant d'augmenter la qualité de la solution; - une étape d'initialisation de la sortie et du potentiel associé à chaque neurone; - une étape d'exploitation dynamique récursive du réseau; -une étape de choix parmi les sous-ensembles listés du meilleur par comparaison des qualités. 2. Procédé selon la revendication 1, caractérisé en ce que dans le cas de recherche d'objets deux à deux non en relation l'étape d'initialisation de la sortie et du potentiel associés à chaque neurone est telle que la sortie et le potentiel associé à chaque neurone vérifient, pour chaque neurone, les conditions suivantes: - sur les sorties des neurones: si on initialise un neurone i avec une sortie qui vaut 1 (neurone activé), alors les neurones j correspondant à des objets en relation avec l'objet i (es = 1) doivent être désactivés. (p(t =0)= 1) = (Vje{1.....N} ee = 1= pj(t=0)=0) - sur les potentiels: pi(t =O)= I =u.(t = o)>o p,(t = O)=O u,(t = O) s O 3. Procédé selon la revendication 1, caractérisé en ce que dans le cas de recherche d'objets deux à deux en relation rétape d'intialisation de la sortie et du potentiel associés à chaque neurone est telle que la sortie et le potentiel associé à chaque neurone vérifient, pour chaque neurone, les conditions suivantes: - sur les sorties des neurones: si on initialise un neurone i avec une sortie qui vaut I (neurone activé), alors les neurones j correspondant à des objets non en relation avec robjet i (e% = 0) doivent être désactivés. (p,(t = O)= 1) = (Vj E{1.....N} e. = 0=> pj(t = O)=0) - sur les potentiels: pj( =0)= l u, (t = o)>o0 p,(t = O)= O u (t =O) 4. Procédé selon rune quelconque des revendications prédees, caractérisé en ce que retape d'exploitation dynamique récursive du réseau comprend une mise à jour de rensemble des neurones du réseau dans un certain ordre (par exemple aléatoire ou séquentiel) en considérant simultanément les neurones d'un bloc constitué d'un neurone i (centre) et les neurones j voisins associés aux objets en relation avec robjet (neurones j pour lesquels es = 1), pour mettre à jour ce bloc, en ce qu'on applique aux potentiels des divers neurones des corrections, corrections dépendantes des valeurs des sorties des autres neurones et des relations existant entre les objets, rexpression mathématique de la correction à appliquer au potentiel d'un neurone différant suivant au'il est considéré comme centre d'un bloc ou comme voisins d'un centre d'un autre bloc, et en ce que les corrections sont définies de telle sorte que dès qu'un neurone i est activé, tous les neurones j vérifiant e. = 1 sont désactivés au même instant. 5. Dispositif d'extraction d'un sous-ensemble d'objets deux à deux non en relation ou en relation issus d'un ensemble d'objets en relation et optimisant une mesure, en utilisant un réseau de neurones, caractérisé en ce que ce réseau de neurones comprend: - un circuit (50) de choix d'un entier i entre 1 et N; - une première mémoire (55) table des valeurs des sorties p, des neurones relfiée à la sortie du circuit (50) de choix d'un entier; - une seconde mémoire (56) table des voisins de chaque neurone reliée à la sortie du circuit (50) de choix d'un entier; - une troisième mémoire (57) des relations entre les objets reliée à rentrée de la seconde mémoire (56); - une quatrième mémoire (58) des potentiels des neurones reliée à la sortie de la seconde mémoire (56), à la sortie du circuit (50) de choix d'un entier; - une cinquième mémoire (67) contenant la valeur courante de la mesure à optimiser reliée à la sortie de la première mémoire (55); - un premier circuit de calcul (59) permettant de calculer la variation de potentiel à appliquer au neurone i relié à la sortie du circuit (50) de choix crun entier, à la sortie de la cinquième mémoire (67). à la sortie de la troisième mémoire (57) et à la sortie de la première mémoire (55); - un second circuit de calcul (60) permettant de calculer la variation de potentiel à appliquer aux neurones voisins du neurone i relié aux sorties du circuit de choix et des cinquième, troisième et première mémoires; - un premier additionneur (61) recevant les sorties du premier circuit de calcul et de la quatrième mémoire et relié en entrée à la quatrième mémoire; - au moins un second additionneur (62) recevant les sorties du second circuit de calcul et de la quatrième mémoire et relié en entrée à la quatrième mémoire; - au moins deux circuits fonctions de seuillage binaire F (64, ) reliés respectivement aux sorties de ces deux additionneurs et à rentrée de la première mémoire.