FR 2719400 A1 19951103 FR 9405324 A 19940502 "Procédé et dispositif d'extraction d'un plus grand sous-ensemble d'objets, utilisant un réseau de neurones" DESCRIPTION Domaine technique La présente invention concemrne un procédé et un dispositif d'extraction d'un plus grand sous-ensemble d'objets, utilisant un réseau de neurones. Etat de la technique antérieure Les réseaux neuromimé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 d'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 a 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 l'entrée du neurone j est noté w.. La quantité totale d'activation en entrée uj que le neurone j reçoit des autres neurones à chaque instant est utilisée par ce neurone pour mettre à jour sa sortie. On rappelle parfois potentiel (ou potentiel d'activation) du neurone j. La règle d'activation d'un réseau 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: I p,(t) = 1 si u, (t) > 0 p,(t) =0 si u,(t) aléatoirement ( O ou 1). Puis le réseau évolue en mettant à jour ses neurones. Pour mettre à jour un neurone i à l'instant t, on calcule son potentiel à cette -5 date; t)=u(t =a -1) + Au,(t) (2) La variation de potentiel Aui (t) va correspondre à la dynamique d'évolution. Différents modèles existent dans rart connu pour définir cette dynamique. Suivant le signe de Au, (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 Cybemrnetics, vol. 52, pages: 141-152, 1985). Ils définissent une fonction énergie E: E = - 2 ÉEwj p, p1-LIa pj (3) i=l j=l i=l 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èmrne, 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: AE api - si la règle d'activation utilisée est celle de Mc Culloch-Pitts, -et si la matrice des poids synaptiques est symétrique (we =w,), - alors, pour tout neurone i, et à toute date t: AE (t)SO Ainsi ré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 du plus grand sous-ensemble d'objets issus d'un ensemble d'objets en relation et deux à deux non en relation ou en relation qui peuvent avantageusement utiliser un réseau neuromimétique original. Exposé de Irnvention L'invention concerne un procédé d'extraction crun plus grand sous-ensemble d'objets, tels que des trajectoires potentielles dans une application de vélocimétrie, 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) = => robjet appartient au sous-ensemble recherché. p, (t) =0 =: robjet n'appartient pas au sous-ensemble recherché; - une étape d'utilisation d'un procédé d'interruption afin d'obtenir des sousensembles d'objets deux à deux non en relation ou en relation tels que chaque sous-ensemble trouvé ne peut pas être indus dans un plus grand, et que ron passe d'un sous-ensemble à un autre en essayant d'augmenter sa taille; - une étape d'initialisation de la sortie et du potentiel de chaque neurone de telle sorte qu'ils vérifient, pour chaque neurone: p(t)= l u,(t = o) > o pi (t)=O I(t = 1) O - une étape crd'expoitation dynamique récursive du réseau; - une étape de choix parmi les sous-ensembles listés du plus grand par comparaison des tailles. Avantageusement rétape d'exploitation dynamique récursive du réseau comprend une mise à jour asynchrone (par exemple aléatoire ou séquentielle) de rensemble des neurones du réseau, en balayant les neurones les uns après les autres en appliquant à leur potentiel une correction préalablement calculée, correction dépendant des valeurs des sorties des autres neurones et des relations existant entre les objets de telle manière que globalement, après décodage des sorties des neurones, ron obtient une liste de sous-ensembles d'objets deux à deux non en relation, chacun de ces sous- ensembles ne pouvant être inclus dans un plus grand. L'invention concerne également un dispositif qui comporte un réseau de neurones qui comprend: -une première mémoire table des sorties pi des neurones recevant la sortie d'un circuit de choix d'un entier allant de 1 à N; - une seconde mémoire des relations entre objets; - une troisième mémoire table des potentiels des neurones reliée à la sortie du circuit de choix d'un entier; - une quatrième mémoire table des dernières variations des poentiels des neurones reliée à la sortie du circuit de choix d'un entier; -un premier circuit de calcul penrnettant de calculer -un second circuit de calcul permettant de calculer B.(1 - pi) Pjl); - un troisième circuit de calcul permettant de calculer C.R({pj 1); ces trois circuits de calculs étant reliés aux sorties des deux premières mémoires et à la sortie du circuit de choix d'un entier; - un dispositif d'interruption relié à la sortie du troisième circuit de calcul et aux sorties de la quatrième mémoire; -un premier additionneur recevant les sorties des deux premiers circuits de calcul et du dispositif d'interruption et relié à rentrée de la quatrième mémoire; - un second additionneur recevant les sorties de la troisième mémoire et du premier additionneur et relié à l'entrée de la troisième mémoire; - un circuit de fonction de seuillage à sortie binaire recevant la sortie du second additionneur et relié à l'entrée de la première mémoire. Avantageusement ce réseau de neurones s'applique: - aux procédés de gestion optimale de moyens au cours du temps; - à 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. Briève description des dessins -La figure I illustre les différentes étapes du procédé de rinvention; la figure 2 illustre rétape d'exploitation dynamique récursive; -les figures 3 et 4 illustrent un neurone et un réseau de neurones associés au dispositif de mise en oeuvre du procédé de rinvention. 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 l'on cherche des sous-ensembles deux à deux non en relation. Bien entendu le procédé de rinvention s'applique également à la recherche de sousensembles crd'objets deux à deux en relation en substituant à la matrice (e.) des relations, la matrice (1-eï). Le procédé de l'invention comprend plusieurs étapes, illustrées sur la figure 1. On utilise un réseau de neurones formels et apte à déterminer un sous-ensemble d'objets deux à deux non en relation de qualité maximum, o la qualité est mesurée comme le nombre d'objets dans le sous-ensemble trouvé. On a les étapes suivantes: -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): p, (t)= 1 = l'objet appartient au sous-ensemble recherché Pi (t) = 0 => r'objet n'appartient pas au sous-ensemble recherché; - utilisation d'un procédé d'interruption afin d'obtenir des sous- ensembles d'objets deux à deux non en relation tels que chaque sousensemble trouvé ne peut pas être inclus dans un plus grand. On passe d'un sous- ensemble à un autre en essayant d'augmenter sa taille; - initialisation de la sortie (par exemple à O) et du potentiel de chaque neurone de telle sorte qu'ils vérifient, pour chaque neurone i: A(t)= 1 ≤ (t =0)>0 Pi(t)= O comparaison des tailles. Le dispositif illustré à la figure 4 correspond au rectangle 10 en pointillés sur la figure 1. Exploitation dynamique récursive de ce premier réseau de neurones. Cette exploitation dynamique récursive est illustrée à la figure 2. On détermine la correction à appliquer au potentiel u, d'un neurone i à une date t. Elle est donnée oar une combinaison linéaire de deux termes: - un terme a pour but d'inhiber le neurone i si celui-ci est activé et que robjet associée est en relation avec au moins une des objets correspondant aux neurones activés à la date o il est considéré. Autrement dit, sila sortie p, du neurone i à la date t vaut l(p,(t)= 1). alors cette correction est donnée par: o T est une fonction des sorties pj(t) des neurones à la date t qui correspondent à des objets en relation avec robjet associé au neurone i. Par exemple: i{pj(t)}) =-1 +h eu..pi(t) avec N le nombre d'objet e. = 1 si les objets i et j sont en relation e = 0 si les objets iet j ne sont pas en relation h: R-- {0,1} x-h(x)=l six=0 =0 si xO0 OU: T({p,(t)})=-[ e.p,(t) /deg(i) o deg(i) est le nombre J=I d'objets avec lesquels l'objet i est en relation; - un terme a pour but d'exciter le neurone si celui- ci est désactivé et que robjet associé n'est pas en relation avec tous les objets correspondant aux neurones activés à la date o il est considéré. Autrement dit. si la sortie p, du neurone i considéré vaut O à la date t(pj(t)=o0), alors cette correction est donnée par: (l- pi(t)).I{P(t)}) o S est une fonction des sorties p,(t) des autres neurones à la date t qui correspondent à des objets en relation avec robjet associé au neurone i. Par exemple: S({ pi (t) h ve.p(t h:/R-{0,1} I R étant rensemble des réels x--h(x)=l six=0 =0 si x*O -ensuite, si le réseau a été mis à jour moins d'un certain nombre de fois préalablement fixé depuis la demière convergence, alors on applique une excitation pour essayer d'augmenter, à la convergence suivante, la taille du sous-ensemble d'objet déterminé lors de la dernmière convergence du réseau. Autrement, un procédé d'interruption stoppe la prise en compte de cette excitation. Cette excitation peut s'écrire sous la forme: Par exemple: Par exemple: en t).(- p, (t)).N -deg(i),{p,(t}) o: 8 retourne I si le réseau de neurones a été mis à jour moins d'un certain nombre de fois fixe depuis la dernière convergence, I retourne 1 si N - deg(i) est supérieur à la plus grande taille des sous-ensembles d'objets trouvés jusqu'à la date t; 0 sinon. Le réseau alterne donc des phases de pulsation (quand cette dernière excitation est prise en compte) et des phases de relaxation (quand le procédé d'interruption stoppe la prise en compte de rexcitation). Au cours de la phase de relaxation, le réseau converge. Une fois que le réseau a convergé, on applique à nouveau une excitation (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 (à la convergence), les neurones dont la sortie vaut 1 codent un sous-ensemble d'objets deux à deux non en relation. D'une façon générale, les équations de variation de potentiels peuvent s'écrire, pour tout i appartenant à {I,N}: (t) = A.pi(t).{pj(t)) + B.(I p+(t)).Spj(t) (})+ it).R({pi(t}) o A, B et C sont des réels positifs. Avantageusement, on prend A = B = C = 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 l'ordre de grandeur des corrections à appliquer au potentiel quand le neurone est mis à jour; - on borne les valeurs des potentiels entre -10-" et 10-o: ainsi toute correction strictement négative à appliquer sur le potentiel crd'un neurone activé le désactive, et toute correction strictement positive à appliquer sur le potentiel crd'un neurone désactivé l'active. La figure 3 illustre un neurone i. La figure 4 donne le réseau de neurones associé au dispositif de mise en oeuvre du procédé de l'invention. Ce réseau comprend: lo - une première mémoire 40 table des valeurs des sorties p, des neurones recevant la sortie d'un circuit 39 de choix crd'un entier allant de I à)V; - une seconde mémoire 41 des relations entre objets; - une troisième mémoire 42 table des potentiels des neurones; une quatrième mémoire 51 table des dernières variations des potentiels des neurones; - un premier circuit de calcul 43 permettant de calculer - un second circuit de calcul 44 permettant de calculer B(1- pj).fpj}); - un troisième circuit de calcul 45 permettant de calculer C.R({pJ); ces trois circuits de calculs étant reliés aux sorties des deux premières mémoires; - un dispositif d'interruption 46 relié à la sortie du troisième circuit de calcul et aux sorties de la quatrième mémoire; - un premier additionneur 47 recevant les sorties des deux premiers circuits de calcul et du dispositif d'interruption; - un second additionneur 48 recevant les sorties de la troisième mémoire et du premier additionneur; - un circuit de fonction de seuillage à sortie binaire 49 recevant la sortie du second additionneur. Dans le cas d'un dispositif numérique, ce réseau comprend également une horloge reliée à tous les éléments (directement ou indirectement) du dispositif. Le réseau de neurones évolue en mode asynchrone: un neurone est mis à jour à la fois. On peut démontrer qu'un réseau de neurones ainsi défini converge (c'est-à-dire qu'il existe une date t pour laquelle Vi,Vt'>t,, "(t')= 0), en mode asynchrone à rissue de chaque phase de relaxation et qu'à la convergence, les objets associés aux neurones activés sont deux à deux non en relation. LEXIQUE Objet Trajectoire potentielle dans une application de vélocimétrie. Neurone Un neurone i est 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 Auj(t) à appliquer au potentiel (t + =.,(,)+^U() - on met à jour la sortie: si u,(t+1)>0 alors p,(t+l)=l i5 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 et = 1. Sinon eV = 0.(e.) est la matrice des relations entre les objets. Remaraue: le procédé est équivalent à rechercher le plus grand sousensemble d'objets en relation. Il suffit pour cela de considérer la matrice en relation (1 -e e) et d'utiliser le procédé décrit dans la présente invention. - 14 REVENDICATIONS 1. Procédé d'extraction d'un plus grand sous-ensemble d'objets, tels que des trajectoires potentielles dans une application de vélocimétrie, 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 p,(t) à une date t: pi (t)= 1 => I'objet appartient au sous-ensemble recherché. pi (t)= 0 => l'objet n'appartient pas au sous-ensemble recherché; -une étape d'utilisation d'un procédé d'interruption afin d'obtenir des sousensembles d'objets deux à deux non en relation ou en relation tels que chaque sous-ensemble trouvé ne peut pas être indclus dans un plus grand, et que l'on passe d'un sous-ensemble à un autre en essayant d'augmenter sa taille; - une étape d'initialisation de la sortie et du potentiel de chaque neurone de telle sorte qu'ils vérifient, pour chaque neurone: pi(t) = = o) o p,(t) = O:: ut(t = 1) grand par comparaison des tailles. 2. Procédé selon la revendication 1, caractérisé en ce que l'étape d'exploitation dynamique récursive du réseau comprend une mise à jour asynchrone (par exemple aléatoire ou séquentielle) de l'ensemble des neurones du réseau, en balayant les neurones les uns après les autres en appliquant à leur potentiel une correction préalablement calculée, correction dépendant des valeurs des sorties des autres neurones et des relations existant entre les objets de telle manière que globalement, après décodage des sorties des neurones, l'on obtient une liste de sousensembles d'objets deux à deux non en relation ou en relation, chacun de ces sous-ensembles ne pouvant être inclus dans un plus grand. 3. Dispositif d'extraction du plus grand sous-ensemble d'objets deux à deux non on relation ou en relation issus d'un ensemble d'objets on relation, utilisant un réseau de neurones, caractérisé en ce que ce réseau de neurones qui comprend: - une première mémoire (40) table des sorties pi des neurones recevant la sortie d'un circuit (39) de choix d'un entier allant de 1 à N; - une seconde mémoire (41) des relations entre objets; une troisième mémoire (42) table des potentiels des neurones reliée à la sortie des circuits (39) de choix d'un entier; - une quatrième mémoire (51) table des demrnières variations des potentiels des neurones reliée à la sortie du circuit (39) de choix d'un entier; - un premier circuit de calcul (43) permettant de calculer tp.{}) -un second circuit de calcul (44) permettant de calculer :.(1,- j-l,) -un troisième circuit de calcul (45) permettant de calculer C.Ripl); ces trois circuits de calculs étant reliés aux sorties des deux premières mémoires et à la sortie du circuit (39) de choix d'un entier; - un dispositif d'interruption (46) relié à la sortie du tromsie circuit de calcul et aux sorties de la quatrième mémoire; - un premier additionneur (47) recevant les sorties des deux premiers circuits de calcul et du dispositif dinmlerruption et relié à rentrée de la quatrième mémoire (39); - un second additionneur (48) recevant les sortis de la trosiènme mémoire et du premier additionneur et relié à rentrée de la trasième mémoire; - un circuit de fonction de seuillage à sortie binaire (49) recevant la sortie du second additionneur et relié à rentrée de la première mémoire.