FR 2678407 A1 19921231 FR 9108066 A 19910628 "Procédé et dispositif avec un réseau neuronal pour classer des données, et appareil d'authentification de signatures' La présente invention concerne un procédé pour le classement de vecteurs de données selon une ou plusieurs classes, faisant appel à un réseau de neurones à plusieurs couches, les coefficients ou poids synaptiques étant déterminés, pour obtenir le classement désiré, par apprentissage sur la base de spécimens dont on connaît la classe, et la dimension du réseau étant adaptée en fonction du nombre de spécimens et de classes appris. Elle concerne aussi un dispositif pour classer des données, présentées sous la forme de vecteurs de données, qui fournit une valeur estimant la probabilité qu'un vecteur de données appartienne à une classe parmi une ou plusieurs classes qui ont été apprises au moyen de spécimens d'apprentissage, et qui comporte pour le traitement d'un vecteur de données un réseau neuronal à plusieurs couches. On considère un exemple à classer, exemple qui est défini par un ensemble de données, comme un "vecteur de données" dans un hyper-espace, vecteur dont les coordonnées sont les valeurs des données de l'exemple On emploiera dans la suite le mot "spécimen" pour désigner un vecteur de données particulier, celui qui définit un spécimen d'apprentissage (le dispositif apprend à définir une classe lorsqu'on lui fournit des spécimens faisant partie de cette classe). L'invention s'applique particulièrement à l'authentification de signatures, mais il est clair qu'elle s'applique aussi, entre autres, dans des domaines o les données disponibles pour l'apprentissage du dispositif sont en petit nombre (fusion de données, détection de signal) ou quand se présente un problème de classement à une classe (tel que estimation de probabilité ou détection de signal dans du bruit) o lorsqu'il y a évolution dans le temps (vieillissement). Un dispositif neuronal de ce type est connu par l'article intitulé "Neural networks with dynamic capacity allocation and quadratic function neurons", de Petri A Jokinen, dans "Proceedings of Neuronimes", 1990, pages 351-363 Ce dispositif stocke une matrice de covariance dans un neurone, ce qui est donc très compliqué à réaliser. L'invention se propose de fournir un procédé qui puisse être mis en oeuvre dans un dispositif simple à plusieurs couches de type dit MLP ("Multi Layer Perceptron"), qui permette l'apprentissage d'une ou de plusieurs classes pour ensuite estimer la probabilité qu'un vecteur de données appartienne à une ou plusieurs classes parmi celles qui ont été apprises, dont le mécanisme d'apprentissage ne soit pas itératif et donc soit rapide, dont l'apprentissage incrémental soit possible (c'est- à-dire que le système puisse "apprendre" des spécimens supplémentaires sans avoir à reprendre tout son apprentissage antérieur), et qui en outre procure une fiabilité du classement supérieure à celle de l'art antérieur. Ces buts sont atteints du fait que, pour l'apprentissage, on recherche des domaines de décision qui contiennent un nombre fixé de spécimens, au lieu de chercher des domaines de décision qui soient définis par les limites de leur zone d'influence (comme c'est le cas pour l'algorithme connu d'apprentissage par rétropropagation) On appelle domaine de décision un domaine tel que, pour tous les vecteurs de données qui s'y trouvent, le dispositif prend la même décision de classement. Un dispositif selon l'invention est remarquable en ce qu'il comporte un nombre de neurones et des poids synaptiques qui ont été déterminés par le procédé selon l'invention. Le dispositif neuronal selon l'invention met ainsi en oeuvre un procédé d'apprentissage qui, pour classer les données, s'appuie sur des comportements statistiques. Dans un tel dispositif, dont le réseau neuronal a trois couches une couche d'entrée, une couche interne, et une couche de sortie, les poids des liaisons entre la couche d'entrée et la couche interne sont avantageusement égaux aux coefficients aij et bi de l'équation ? xiaijxj + i xibi c matrice de covariance de ladite distribution. Avantageusement, chaque neurone de sortie étant relié aux neurones internes correspondants aux spécimens d'apprentissage d'une classe, le dispositif comporte un neurone dont la valeur est fixée à "-1 ", qui est relié à tous les neurones de sortie, et dont le poids synaptique de la liaison vers chaque neurone de sortie est adapté en présentant au réseau, après la définition des groupes de neurones internes correspondant aux classes, les spécimens d'apprentissage d'une classe, et en essayant successivement différents poids entre le neurone dont la valeur est fixée à '-1 " et le neurone de sortie correspondant à la classe, de façon à trouver le poids qui minimise l'erreur moyenne pour la classe, ce processus étant répété pour chacune des classes. Le dispositif comporte en outre avantageusement, afin de fournir des données requises pour le réseau de neurones, un module d'entrée qui ajoute au vecteur des données d'entrée un vecteur dont les composantes sont les produits deux à deux des composantes du vecteur de données d'entrée, ce module remplaçant donc N termes par N + n(n+ 1)/2 termes, fournis chacun sur une sortie, lesquelles sorties sont reliées chacune à un des neurones de la première couche de neurones. Enfin un appareil d'authentification de signatures voit ses performances améliorées lorsqu'il comporte un dispositif selon l'invention. La description qui va suivre, en regard des dessins annexés décrivant des exemples non limitatifs fera bien comprendre comment l'invention peut être réalisée. La figure 1 représente un réseau neuronal selon l'invention. La figure 2 illustre des amas d'échantillons répartis en deux classes. La figure 3 montre comment une classe peut être divisée en distributions locales gaussiennes. La figure 4 illustre l'analyse selon ses principales composantes d'une distribution locale. La figure 5 représente un organigramme des étapes mises en oeuvre pour l'établissement des valeurs de synapse. La description ci-après sera faite en prenant comme exemple l'authentification de signatures, qui consiste en la recherche d'une probabilité qu'un échantillon (une signature à authentifier) appartienne à une classe qui a été définie par d'autres échantillons (un groupe de signatures authentiques appelées 'spécimens" qui ont été fournies au préalable) Il faut noter cependant que le dispositif peut aussi s'appliquer à d'autres activités que l'authentification de signatures, comme cela a été indiqué en préambule. La signature manuscrite est un des moyens les plus habituels pour identifier des personnes Il existe deux catégories de méthodes et de dispositifs pour l'analyse et la vérification de signatures, c'est à dire pour déterminer si une signature est véritable ou si elle est contrefaite (imitée): les méthodes par examen d'une signature préalablement portée sur un document, considérée comme une forme à analyser. les méthodes dans lesquelles le processus d'écriture de la signature est analysé durant la réalisation de la signature. La première catégorie s'est jusqu'à présent révélée inadaptée pour une vérification automatique et fiable L'invention concerne donc un appareil basé sur la seconde catégorie. On utilise une tablette sur laquelle est posé le papier qui reçoit la signature Cette tablette (qui ne fait pas partie de l'invention) est équipée de capteurs de pression, qui fournissent à chaque instant la position (par exemple coordonnées x, y) et la force d'appui du stylo sur le papier On enregistre à intervalles réguliers des échantillons de ces diverses grandeurs L'ensemble des valeurs de chaque grandeur en question constitue les coordonnées d'un vecteur dans un hyper-espace. Ces valeurs sont ensuite normalisées La normalisation procure des données qui sont indépendantes du temps total mis à réaliser la signature, de sa situation globale sur la tablette, de son inclinaison par rapport à l'horizontale, et de sa dimension globale. Le dispositif mesure la différence entre une signature B à analyser et les spécimens de signatures A véritables qui ont été enregistrées lors de l'apprentissage. Cette différence est exprimée par un ensemble de distances d(B,A) d(BA) = | ZB(t) ZA*(t) | O z B*(t) et ZA*(t) sont des vecteurs correspondants respectivement à la signature B et à une des signatures A, respectivement La distance est un scalaire Il y a autant de distances que de signatures A. La distance ainsi définie est malheureusement sensible aux fluctuations instantanées de la vitesse d'écriture, qui sont différentes d'une signature à l'autre pour une même personne On la corrige donc en introduisant une distorsion du temps ("warping function") qui est déterminée par des moyens connus de façon à minimiser d(B,A) L'allure de la distorsion de temps qui a été nécessaire pour minimiser la distance est elle même une donnée signifiante concernant la différence entre deux signatures Pour plus - de détails concernant ces techniques de normalisation et de distorsion du temps on pourra se reporter par exemple à l'article de Yukio Sato et Kiyoshi Kogure intitulé "Online signature vérification based on shape, motion, and writing pressure" dans Proceedings of 6th International Conférence on Pattern Recognition, Munich ( 1982), pages 823, 826. En fin de compte, on peut retenir trois distances significatives comme distances entre un vecteur représentant une signature A de l'ensemble des signatures vraies et le vecteur représentant une signature B à vérifier Ces trois distances concernent: la position du stylo (normalisée et corrigée par distorsion du temps) la pression d'appui du stylo (normalisée et corrigée par distorsion du temps en simultanéité avec la correction concernant la position) la fonction de distorsion du temps elle même. Ces trois distances constituent elles-mêmes un vecteur à trois dimensions qui exprime la différence entre les signatures On pourrait aussi retenir en plus, par exemple, le temps global pour réaliser la signature, et/ou n'importe quel autre paramètre, ce qui fournirait un vecteur à quatre dimensions ou plus Il y a autant de ces vecteurs qu'il y a de spécimens de signatures vraies correspondant à une signature B donnée. Le dispositif neuronal de la figure 1 traite un vecteur appliqué à des entrées 1 Les coordonnées de ce vecteur sont traitées dans un _ module d'entrée 2 que l'on appellera nquadrateur" et qui sera décrit plus loin Ce quadrateur 2 comporte des sorties qui sont reliées aux neurones 3 d'une première couche, dite couche d'entrée, dont les neurones seront appelés neurones "quadratiques" Chaque neurone de cette couche est relié à tous les neurones d'une deuxième couche interne de neurones 4, qu'on appellera neurones "hyper-ellipsoides". Les neurones de cette couche sont répartis en groupes dont chacun correspond à une classe de la classification à réaliser, et les neurones d'un groupe sont reliés à un neurone de sortie 5 Enfin deux neurones 6 et 7 dont la valeur est fixée à 1 " sont reliés, l'un à tous les neurones hyper-ellipsoides, l'autre à tous les neurones de sortie Le rôle de ces neurones 6 et 7 sera expliqué plus loin. Puisqu'on ne peut représenter facilement un vecteur à trois dimensions, on a représenté sur les figures 2 à 4 des points qui représentent chacun un vecteur dans un plan (deux dimensions), mais il faut bien comprendre qu'il s'agit de symboles figurant des vecteurs dans un hyper- espace avec un nombre de dimensions quelconque, ce nombre variant selon le problème à résoudre Chaque point sur une de ces figures représente donc un vecteur représentant les différences entre une signature inconnue et une signature authentique donnée à titre d'exemple. Le dispositif neuronal considère des vecteurs de données se trouvant dans un espace de caractéristiques qui peut être partagé en classes, un tel espace étant illustré par la figure 2, o l'on peut voir un amas de points faisant partie d'une classe indiquée n CLASS 1 ", et un autre amas de points faisant partie d'une autre classe indiquée 'CLASS 2 " On suppose qu'il existe dans chaque classe des -distributions sous-jacentes La figure 3 illustre ceci en montrant comment à partir de l'amas de points illustré sur le diagramme du haut, on peut reconnaître sur le diagramme du bas des ensembles de points, chacun des ensembles obéissant au même type de distribution que ses voisins (on modélise ces distributions par des Gaussiennes). Pour clarifier les idées, supposons par exemple qu'on ait dix signatures authentiques disponibles à titre de spécimens, c'est à dire dix vecteurs de données, chacun à trois dimensions Pour l'instant on n'a pas encore de signature à authentifier, et il s'agit de faire l'apprentissage du dispositif On calcule toutes les distances deux à deux entre les dix vecteurs, ce qui procure quarante-cinq distances qui sont chacune un vecteur à trois dimensions Ce sont des distances de ce genre qui sont symbolisées par-les points sur les figures 2 et 3. Ensuite, pour chacun des quarante-cinq points on calcule les quarante-quatre distances vis-à-vis des autres points, et on prend les k plus petites Les points correspondants constituent un ensemble de points sensés répondre à la même loi de distribution Chacun de ces ensembles est symbolisé par une ellipse sur la figure 3. Pour faciliter la description plus précise de l'algorithme utilisé par le dispositif, quelques généralités concernant les statistiques vont être rappelées maintenant. Soit P(X) la probabilité Gaussienne qu'un ensemble X appartienne à la distribution centrée sur p, avec la matrice de covariance r P(X) = 1 e-e(X-p)T F-1 (X-p) r( 2,,)n;I r I soit:1 soit P(X) = e% 5 (x) ( 2 r)n avec *vc L(X) = -(X-p)T Fr-(X-p) lniri ( 1) L'exposant T indique un vecteur transposé, et N est la dimension de l'hyper-espace. Le calcul des termes de l'équation ( 1) est possible dès que p et r sont connus. On peut remarquer que la relation L(X) est quadratique La condition ("de Bayes") pour qu'un ensemble X appartienne à une telle distribution est L(X) volume de l'hyper-ellipsoïde. Le "quadrateur" 2 prévu à l'entrée du réseau de neurones réalise l'opération suivante: (Xl xn) >(xi,,xn,xixi,xlxz,,xlxnx 2 x 2, Xn Xn) L'homme du métier sait réaliser matériellement un tel quadrateur Ce quadrateur remplace donc N termes par N + n(n+ 1)/2 termes fournis chacun sur une sortie Les n + n(n+ 1)/2 sorties du quadrateur sont reliées chacune à un des neurones de la première couche de neurones "quadratiques" Ainsi les termes xixj de l'équation ( 2) sont fournis aux premiers neurones. La détermination des coefficients aij, bi et c est faite par identification entre les équations ( 1) et ( 2). Le calcul de L(X) S requiert finalement le produit "matrice vecteur" de la sortie du quadrateur par une matrice spécifique, comprenant les coefficients aij, bi On sait qu'un produit "matrice x vecteur" peut être réalisé par une couche d'un réseau de neurones. Ainsi, les moyens pour le calcul de L(X) S sont implantés dans la deuxième couche de neurones 4 hyper-ellipsoides Il y a autant de neurones 4 qu'il y a de spécimens d'apprentissage L'entrée de chacun de ces neurones 4 est reliée aux sorties des neurones quadratiques 3, et les poids des liaisons sont égaux aux coefficients aij, bi afférents Les poids entre le neurone 6 de valeur fixe "-1 " et les neurones 4 sont proportionnels à la différence S c définie plus haut. La non linéarité appliquée à L(X)-S par la présence du quadrateur 2 lisse la réponse de la couche des hyper-ellipsoides quand X est près de la bordure de l'hyper-ellipsoide représenté par L(X)-S = O. La couche de sortie a pour rôle de donner une réponse (probabilité que la signature fournie à l'entrée soit authentique) en fonction des sorties des neurones internes 4 Un neurone de sortie 5 est relié à tous les neurones internes 4 qui correspondent à des spécimens d'une même classe, ils constituent donc un groupe correspondant à cette classe Par exemple, dans le cas de l'authentification de signature, il y aurait en principe deux classes, celle des signatures imitées et celle des signatures véritables, donc deux neurones 5 de sortie, l'un délivrant un signal correspondant à la probabilité que la signature soit imitée, et l'autre à la probabilité que la signature soit véritable En pratique, comme on ne dispose pas en général de spécimens de signatures imitées, on ne peut faire l'apprentissage de la classe des signatures imitées, et il n'y a qu'un seul neurone de sortie qui donne la probabilité que la signature soit véritable. La couche de sortie réalise une moyenne de tous les neurones internes d'un groupe, corrigée par la sortie du neurone 7 Les poids entre les neurones internes 4 et les neurones de sortie 5 sont tous fixés à UN - Le neurone 7 de valeur fixe I-lj permet de prendre en compte le décompte cumulatif des valeurs de sortie cumulées de tous les neurones internes 4 d'une classe, c'est-à-dire la somme des valeurs de sortie de ces neurones, pondérés par leurs poids synoptiques respectifs A cet effet, le poids synaptique entre le neurone 7 et le neurone de sortie d'une classe déterminée est ajusté de la manière suivante: après la définition des groupes correspondant aux classes, on présente la totalité des spécimens d'apprentissage au réseau (comme s'il s'agissait de signatures à évaluer), et on essaye successivement différents poids 109 entre le neurone 7 et chaque neurone de sortie de façon à trouver les poids respectifs qui minimisent l'erreur moyenne pour chaque classe. Cette procédure peut être soit manuelle soit implantée dans des moyens d'automatisme: L'apprentissage du réseau consiste donc dans l'estimation de chaque loi locale (une par spécimen de la base d'apprentissage) et dans le calcul des poids synoptiques Pour le calcul de la distribution locale, une solution adaptative est employée: on recherche des régions selon une métrique Euclidienne et l'on construit ces régions de façon qu'elles contiennent un nombre fixé de spécimens, au lieu de leur imposer une-définition topologique, comme cela serait naturel. Autrement dit, au lieu de diviser l'espace en régions arbitraires délimitées par des frontières fixes, on définit comme région une surface contenant un nombre donné de spécimens. L'apprentissage incrémental du réseau (tel que défini dans l'introduction) comporte l'addition d'un nouveau neurone 4 pour chaque nouveau spécimen, et éventuellement d'un nouveau neurone 5 de sortie s'il y a une nouvelle classe. Pour chaque classe sous-jacente Cm dans la base d'apprentissage, les opérations suivantes sont réalisées: * Pour chaque spécimen P appartenant à Cm * Calcul du voisinage de P à partir des spécimens de la classe Cm. Cette région est déterminée par l'algorithme ndes k plus proches voisins": 1/ calcul des distances entre tous les spécimens de la classe Cm et le spécimen P, 2/ classement de ces distances selon leur grandeur, 3/ les k plus proches voisins sont les points de Cm qui donnent les k plus petites distances. * Calcul des caractéristiques statistiques de la distribution locale r (matrice de covariance de la distribution normale dont k échantillons sont les k voisins) et p (centroide de la distribution). * Calcul des axes principaux de la distribution (voir figure 4, qui donne un exemple dans un plan, avec deux axes principaux 8 et 9, mais il y a en réalité autant d'axes que de dimensions) A cet effet une analyse "des composantes principales" est réalisée Cette méthode connue donne directement les vecteurs propres de la matrice de covariance de la distribution Les vecteurs propres donnent les direction des axes principaux En décrivant la matrice de covariance dans la base définie par ses axes principaux, on fait l'approximation qu'elle est diagonale. * Calculer les poids entre la sortie du quadrateur et les neurones hyperellisoïdes, correspondant au spécimen P Cette étape réalise le calcul des coefficients aij et bi. * Calculer c. * Mettre à UN le poids synaptique entre les neurones hyper-ellisoides correspondant à tous les spécimens de Cm et le neurone de sortie de la classe Cm. * Incrémenter Nm (Nm est le nombre de neurones hyper-ellisoides créés jusque là, c'est-à-dire le nombre de spécimens pris en compte). *** Si on désire la détermination automatique des poids synoptiques entre le neurone 7 et les neurones de sortie: * pour chaque spécimen P appartenant à Cm, et pour les valeurs entières du poids dans la suite lNm,, +Nml, calcul du "décompte cumulatif" défini plus haut correspondant à la classe Cm Calcul de l'erreur sur la valeur de sortie de la classe Cm. *** Conserver la valeur du poids qui minimise l'erreur moyenne sur la classe Cm. Le diagramme d'opérations de la figure 5 illustre le calcul des hyperellipsoides Le matériel nécessaire pour la réaliser s'en déduit aisément: on peut voir qu'il nécessite quatre modules fonctionnels A partir d'une mémoire principale 10 dans laquelle sont stockées toutes les données disponibles, et via une mémoire tampon 11, une mémoire vive 12 marquée "Ex-RAM" est chargée avec les spécimens disponibles. * le module 20 marqué "k-NN" charge un spécimen à partir d'un registre 21, réalise la recherche de ses k plus proches voisins et mémorise leur k adresses dans un registre 19. * le module 13 marqué "PC An réalise l'analyse des composantes principales sur les k plus proches voisins et calcule les paramètres statistiques Les coordonnées des axes principaux, le produit des termes de la diagonale de la matrice de covariance et le centroide de la distribution locale sont alors enregistrés dans un registre 18. * le module 17 marqué "H ELLIPS" calcule les poids synaptiques et les mémorise dans une mémoire vive 14, marquée "synap RAM". * le processeur de commande générale 24 marqué 'process' commande les communications et le déroulement des tâches Il commande d'abord le chargement d'une base de données de spécimens dans la mémoire vive 12, puis il remplit le pipeline (k-NN, PCA, H ELLIPS) et il le décharge quand tous les hyper-ellipsoides ont été calculés. Un compteur 23 enregistre le nombre de spécimens qui est chargé dans la mémoire 12, et un multiplexeur 22 permet au module 13 d'accéder directement aux spécimens. Un compteur 16 enregistre le nombre de classes et le nombre de neurones créés, qui sont fournis par le module 17 à la mémoire 14, et un multiplexeur 15 permet à l'utilisateur d'accéder directement aux poids synaptiques dans la mémoire 14, pour les y lire et les appliquer au réseau de neurones. REVENDICATIONS: 1 Procédé pour le classement de vecteurs de données selon une ou plusieurs classes, faisant appel à un réseau de neurones à plusieurs couches, les coefficients ou poids synoptiques étant déterminés, pour obtenir le classement désiré, par apprentissage sur la base de spécimens dont on connaît la classe, et la dimension du réseau étant adaptée en fonction du nombre de spécimens et de classes appris, caractérisé en ce que, pour l'apprentissage, on recherche des domaines de décision, c'est-à-dire des domaines tels que, pour tous les vecteurs de données qui s'y trouvent, le dispositif prend la même décision de classement, qui contiennent un nombre fixé de spécimens. 2 Dispositif pour classer des données, présentées sous la forme de vecteurs de données, qui fournit une valeur estimant la probabilité qu'un vecteur de données appartienne à une classe parmi une ou plusieurs classes qui ont été apprises au moyen de spécimens d'apprentissage, et qui comporte pour le traitement d'un vecteur de données un réseau neuronal à plusieurs couches, caractérisé en ce qu'il comporte un nombre de neurones et des poids synaptiques qui ont été déterminés par un procédé selon la revendication 1. 3 Dispositif selon la revendication 2, caractérisé en ce que, le réseau neuronal ayant trois couches: une couche d'entrée, une couche interne, et une couche de sortie, chacun des neurones internes correspondant à un spécimen d'apprentissage et chacun des neurones de sortie correspondant à une classe, les poids des liaisons entre la couche d'entrée et la couche interne sont égaux aux coefficients au et bi de l',équation: E xiaijxj + i xibi c ( S dans laquelle "S" est un coefficient prédéterminé exprimant le volume donné au domaine considéré, les coefficients 'aij", 'bi", et lic' étant déterminés par identification avec la relation: L(X) = -(X-g)T r-1 (X-p) lnlrl dans laquelle p est le centre de ladite distribution et r est la matrice de covariance de ladite distribution. 4 Dispositif selon la revendication 3, caractérisé en ce que, chaque neurone de sortie étant relié aux neurones internes correspondants aux spécimens d'apprentissage d'une classe, le dispositif comporte un neurone dont la valeur est fixée à "-1 ", qui est relié à tous les neurones de sortie, et dont le poids synaptique de la liaison vers chaque neurone de sortie est adapté en présentant au réseau, après la définition des groupes de neurones internes correspondant aux classes, les spécimens d'apprentissage d'une classe, et en essayant successivement différents poids entre le neurone dont la valeur est fixée à "-1 " et le neurone de sortie correspondant à la classe, de façon à trouver le poids qui minimise l'erreur moyenne pour chaque classe, ce processus étant répété pour chacune des classes. Dispositif selon l'une quelconque des revendications 2 à 4, caractérisé en ce qu'il comporte un module d'entrée qui ajoute au vecteur des données d'entrée un vecteur dont les composantes sont les produits deux à deux des composantes du vecteur de données d'entrée, ce module remplaçant donc N termes par N + n(n+ 1)/2 termes, fournis chacun sur une sortie, lesquelles sorties sont reliées chacune à un des neurones de la première couche de neurones. 6 Appareil d'authentification de signatures, caractérisé en ce qu'il comporte un dispositif selon l'une quelconque des revendications 2 à 5.