Brevet FR2754080A1 — publié le 19980403

PROCEDE D'APPRENTISSAGE POUR LA CLASSIFICATION DE DONNEES SELON DEUX CLASSES SEPAREES PAR UNE SURFACE SEPARATRICE D'ORDRE 1 OU 2 DESCRIPTION Domaine technique L'invention concerne un procédé pour apprendre à un neurone à classer des données en deux classes séparées par une surface séparatrice d'ordre 1, c' est-à-dire un hyperplan, ou par une surface séparatrice d'ordre 2, par exemple une hypersphère. Cette invention trouve des applications dans les domaines exploitant les réseaux de neurones et, en particulier, pour le diagnostic médical, la reconnaissance de formes ou encore la classification d'objets ou de données comme des spectres, des signaux, etc. Etat de la technique Les réseaux de neurones, ou réseaux neuronaux, sont des systèmes qui effectuent, sur des informations numériques, des calculs inspirés du comportement des neurones physiologiques. Un réseau neuronal doit donc apprendre à réaliser les tâches que l'on désire lui faire effectuer par la suite. Pour cela, on utilise une base d'exemples, ou base d'apprentissage, qui contient une série d'exemples connus utilisés pour apprendre au réseau de neurones à effectuer les tâches qu'il devra reproduire, par la suite, avec des informations inconnues. Un réseau neuronal est composé d'un ensemble de neurones formels. Les neurones sont connectés les uns aux autres par des connexions qui ont chacune un poids synaptique. Chaque neurone (appelé aussi perceptron généralisé) est une unité de calcul constituée d'entrées et d'une sortie correspondant à un état. A chaque instant, l'état de chaque neurone, pondéré par le poids synaptique de la connexion correspondante, est communiqué aux autres neurones de l'ensemble. Le niveau total d'activation que le neurone reçoit, en entrée, est égal à la somme des états pondérés des autres neurones. A chaque instant, ce niveau d'activation est utilisé par ce neurone pour mettre à jour sa sortie. Il existe actuellement plusieurs algorithmes d'apprentissage permettant d'apprendre à un neurone, destiné à être utilisé au sein d'un réseau de neurones, à effectuer une tâche précise, comme classer des données (ou motifs). La qualité de ces algorithmes est jugée sous deux aspects différents et ceci suivant le type de tâche à réaliser. Un premier cas est celui où les exemples de l'ensemble d'apprentissage peuvent être tous appris par le neurone. Dans ce cas, l'algorithme doit être capable de trouver les poids qui classent correctement, non seulement, les exemples, mais aussi des motifs nouveaux, c'est-à-dire que le neurone doit avoir des poids capables de bien généraliser. Un deuxième cas est celui où il n'est pas possible au neurone d'apprendre tous les exemples. Alors, l'algorithme doit trouver les poids qui minimisent le nombre d'erreurs d'apprentissage. Or, il nty a pas d'algorithme d'apprentissage qui donne les poids satisfaisants dans les deux cas décrits. Un algorithme d'apprentissage d'un neurone est décrit dans le document A thermal perceptron learning rule de Marcus FREAN, dans Neural computation, n" 4, pages 946-957 (1992). Cet algorithme permet de déterminer des poids, mais il ne donne pas la solution optimale au problème à résoudre. En conséquence, un tel algorithme ne minimise pas le nombre d'erreurs d'apprentissage et ne généralise pas optimalement. Un autre algorithme d'apprentissage d'un neurone est décrit dans le document Perceptron-based learning algorithms de S. I. GALLANT, dans IEEE transaction on neural networks, vol. 1, n" 2, Juin 1990. Cet algorithme permet d'obtenir de bons résultats dans le cas de neurones capables d'apprendre tous les exemples d'apprentissage, à condition d'attendre la convergence de l'algorithme. Cependant, dans le cas où l'ensemble d'apprentissage ne peut pas être appris par un seul neurone, cet algorithme ne converge pas. Il est donc impossible de savoir si l'algorithme ne "s'arrête pas T? parce qu'il n'a pas trouvé de solution ou bien parce qu'on n' a pas suffisamment attendu. Exposé de l'invention L'invention a justement pour but de résoudre les inconvénients des techniques proposées précédemment. A cette fin, elle propose un procédé ou algorithme qui converge quel que soit le cas rencontré et qui, de plus, présente des performances optimales. Autrement dit, l'invention propose un procédé permettant d'apprendre à un neurone à classer des données en deux classes séparées par une surface de séparation pouvant être soit linéaire, soit quadratique. Par la suite, on parlera indifféremment de neurone ou de perceptron généralisé, neurone ou perceptron représentant des unités binaires. A titre indicatif, on peut noter, par exemple, qu'un perceptron linéaire est un neurone qui produit des surfaces de séparation linéaires. L'invention concerne, de façon plus précise, un procédé pour apprendre à un neurone à fonction d'activation quadratique à classer des données selon deux classes distinctes séparées par une surface séparatrice, ce neurone étant un neurone binaire ayant N connexions provenant de l'entrée et recevant en entrée N nombres représentant une donnée, ou motif, destinée à être classée en utilisant une base d'apprentissage contenant une pluralité de données connues, chaque entrée du neurone étant affectée par le poids (wi) de la connexion correspondante, caractérisé en ce qu il comporte les étapes suivantes a) définition d'une fonction coût C en déterminant, pour chaque neurone et en fonction d'un paramètre descriptif de la surface séparatrice, une stabilité yp de chaque donnée u de la base d'apprentissage, la fonction coût étant la somme de tous les coûts déterminés pour toutes les données de la base d'apprentissage avec où A est quelconque, B est un réel positif quelconque, P est le nombre de données de la base d'apprentissage, yp est la stabilité de la donnée u ; T+ et T- sont deux paramètres de la fonction coût (appelés "températures" ) ; a prend la valeur +1 si on a choisi que yy > 0 correspond à une classification correcte et yz b) initialisation des poids wi, des rayons ri, des paramètres T+ et T-, avec T+ c) minimisation, par rapport aux poids des connexions Wi et aux rayons, de la fonction coût C par itérations successives au cours desquelles les paramètres T+ et T- décroissent suivant les vitesses de recuit bT+ et bT- jusqu a un critère d'arrêt prédéfini ; d) obtention des valeurs des poids des connexions et des rayons du neurone. Ces valeurs des poids de connexions et des rayons sont, par exemple, affichés sur un écran, enregistrés dans des fichiers informatiques. Selon un mode de réalisation de l'invention, la stabilité de chaque donnée est avec y = +1 ou -1, et où u est l'étiquette du motif, xpi est la valeur du motif u pour la ième entrée, yP est la classe du motif > , N est le nombre d'entrées et de connexions du neurone, Wi est le poids de la connexion entre l'entrée i et le neurone et ri est le paramètre de rayon pour la i-ème entrée. Selon un autre mode de réalisation de l'invention, la stabilité de chaque donnée est avec y = +1 ou -1, et où p est l'étiquette du motif, XPi est la valeur du motif p pour la ième entrée, yP est la classe du motif p, N est le nombre d'entrées et de connexions du neurone, Wi est le poids de la connexion entre l'entrée i et le neurone et ri est le paramètre de rayon pour la i-ème entrée. Brève description des figures - La figure 1 représente schématiquement un ensemble de données classées selon deux classes séparées par la surface quadratique - La figure 2 représente le diagramme fonctionnel du procédé selon l'invention ; et - La figure 3 représente un exemple de surface séparatrice affinée peu à peu au cours de 1 apprentissage. Exposé de modes de réalisation de l'invention L'invention concerne un procédé qui permet d'apprendre à un neurone à classer des données selon deux classes différentes séparées par une surface quadratique. On a représenté sur la figure 1, une pluralité de données classées selon deux classes, appelées Cîl et C12. Ces deux classes sont séparées par la surface séparatrice S. La surface séparatrice S représentée sur cette figure 1 est une surface courbe réalisée, conformément à l'invention. Comme on le voit dans l'exemple montré sur cette figure, la grande majorité des données, représentées par des carrés vides ou par des ronds pleins, sont correctement classées. Seules, trois données dl, d2 et d3 sont mal classées. C'est ce nombre de données de la base de test mal classées, qui permet de déterminer la capacité d'apprentissage de l'algorithme et donc sa performance. Cette figure 1 montre donc des vecteurs d'entrée de deux types, les ronds pleins et les carrés vides, classés par un neurone quadratique de poids w. Le but de l'apprentissage, d'une façon générale, est de trouver les poids synaptiques Wi à partir d'un ensemble de P exemples, de façon à obtenir les sorties désirées. On parle alors d'apprentissage supervisé. Cela correspond à chercher dans l'espace des poids wi et rayons ri, une surface séparatrice S telle qu'elle sépare les exemples dont la sortie est +1 des exemples dont la sortie est -1. La surface séparatrice est de la forme telle que - si S > O, alors la sortie correspondante au motif d'entrée, ou donnée d'entrée, (xi,. ., xi,. ., XN), OÙ Xi est la valeur du motif sur la ième entrée, est +1; - si S Si le rayon est unique, ri = r pour tout i, la surface séparatrice est une hypersphère. Le nombre de paramètres à déterminer est alors N + 1. Le procédé s'applique à toute autre forme de surface d'ordre 2, par exemple, une surface hyperellipsoïdale, hyperboloïdale, etc., dont l'espace de recherche des poids est beaucoup plus grand que dans le cas d'une hypersphère. Une bonne mesure de la qualité de l'apprentissage d'un exemple p est sa stabilité yp qui est une fonction des poids. Le module de la stabilité yp est une mesure de la distance de l'exemple p à la surface séparatrice S. Une grande stabilité positive assure une certaine robustesse de la réponse du neurone. Le procédé de l'invention qui va être décrit s'applique à un neurone. Ce procédé consiste à apprendre à un neurone à classer des données en deux classes Cîl et Cl2 séparées par une surface S quadratique. Cet apprentissage se fait au moyen d'une base d'exemples, appelée "base d'apprentissage", qui comporte une pluralité d'exemples, ou motifs, ou encore données, connus et préalablement répertoriés par des experts. Le neurone reçoit en entrée un motif ("pattern" en terme anglo-saxon) qu'il doit classer l'état du neurone, puisque celui-ci est binaire, est, par exemple, 1 ou -1, suivant la classe attribuée au motif, tout autre codage linéaire pouvant être ramené à ce codage. On précise que chaque neurone a un nombre N d'entrées, prédéfini en fonction du problème à traiter, et des paramètres ri représentatifs des rayons de la surface séparatrice et que chacune des connexions provenant des entrées est caractérisée par un poids w1 (i=1 à N). L'apprentissage des valeurs des poids wi et des rayons ri s'effectue par minimisation d'une fonction coût. Comme montré sur la figure 2, le procédé d'apprentissage selon l'invention consiste en un procédé de minimisation d'une fonction de coût définie dans l'étape 6. Cette fonction de coût est Le procédé de minimisation de cette fonction de coût commence par une première étape d'initialisation 8 des paramètres du procédé d'apprentissage. En particulier, il consiste à initialiser les paramètres , T+ et T-, les poids wi, et les paramètres de rayon ri. Parmi ces paramètres, on trouve également le taux d'apprentissage et les vitesses de refroidissement, appelées vitesses de recuit et qui sont les valeurs de bT+ et bT- de décrémentation des températures T+ et T-, à chaque itération. Il comporte ensuite une étape 10 de minimisation par itérations de la fonction coût. Chaque itération de cette étape de minimisation 10 comporte une première sous-étape 12 qui consiste à déterminer la stabilité yp de chaque motif de la base d'apprentissage et ce, pour les valeurs des poids et des paramètres de rayon du neurone pris à chaque itération. La stabilité de ce motif est calculée aux étapes 14 ou 16, à partir des expressions Avantageusement on peut aussi utiliser la définition suivante où tu est l'étiquette du motif, X4i est la valeur du motif p pour la ième entrée, yp est la classe du motif p avec p allant de 1 à P (P étant le nombre de motifs de la base d'apprentissage), N est le nombre d'entrées et de connexions du neurone, wi est le poids de la connexion entre l'entrée i et le neurone et ri est le paramètre de rayon. Quelle que soit la façon de calculer les stabilités yP, l'étape suivante du procédé (étape 18) consiste à utiliser la fonction de coût pour modifier les poids et rayon afin de faire décroître la fonction de coût jusqu'à un minimum ; cette fonction coût C est donnée par l'expression où A est quelconque, B est un réel positif quelconque, P est le nombre de données de la base d'apprentissage, rp est la stabilité de la donnée u, T+ et T- sont deux paramètres de la fonction coût (appelés températures ), et C est une variable qui peut prendre la valeur +1 ou la valeur -1 : lorsque 6 = +1 les motifs de classe positive sont à l'extérieur de la surface d'ordre 2 et lorsque o= -1 c'est l'inverse, c' est-à-dire que les motifs de la classe positive sont à l'intérieur de la surface d'ordre 2. Cette fonction coût est lentement variable pour les stabilités à grande valeur absolue et rapidement variable pour les stabilités proches de zéro. La région de variation rapide de cette fonction est contrôlée par deux paramètres, appelés "température", et notés T+ et T-, avec T+ pour les stabilités positives et T- pour les stabilités négatives, T+ La stabilité d'un motif correctement appris par le neurone est positive ; au contraire, la stabilité d'un motif mal appris est négative. Le module de la stabilité est une fonction monotone croissante de la distance entre le motif et la surface séparatrice S définie par les poids et le(s) rayon(s) du neurone. Le but de l'invention est donc de proposer un algorithme permettant d'obtenir le plus de motifs à stabilité positive, ce qui correspond à la meilleure qualité d'apprentissage possible. Le procédé selon l'invention consiste à minimiser la fonction coût C. Cette minimisation se fait de façon itérative, par gradient simple dans lequel, à chaque itération, les valeurs T+ et Tdécroissent respectivement de bT+ et 8T- jusqu'à arriver au critère d'arrêt prédéfini (étape 19). Ce critère d'arrêt peut être un critère d'arrêt classique, tel que la dérive de la fonction coût ait une valeur absolue inférieure à un petit nombre appelé degré de tolérance dans la détermination du minimum. L'itération est schématisée, sur la figure 2, par une flèche de retour vers l'étape 12. Lorsque le critère d'arrêt est satisfait, les valeurs des wi et ri sont affichées sur un écran et enregistrées dans un fichier en vue d'une utilisation ultérieure. Ceci est représenté par l'étape 20 sur la figure 2. On a ainsi déterminé les paramètres (poids des connexions et rayons) descriptifs de la surface séparatrice. La surface séparatrice est donc créée. Ainsi, lorsque tous les exemples de la base d'apprentissage ont été traités et ont donné un taux d'erreur minimal, on traite ensuite des cas inconnus par le réseau de neurones ainsi formé, en considérant que si le taux d'erreur obtenu pour les exemples de la base d'apprentissage est bon, alors le classement de motifs inconnus sera effectué correctement. Sur la figure 3, on a représenté schématiquement différents stades de détermination d'une surface séparatrice d'ordre 2 à rayon unique, déterminée par le procédé de l'invention dans un cas où les entrées sont de dimensions N = 2 ; la surface est alors un cercle. Plus précisément, les points pleins et les points vides montrés sur la figure 3, représentent chacun une donnée de l'ensemble d'apprentissage. Le procédé cherche à déterminer la surface séparatrice S4 permettant de séparer les ronds des carrés. Chaque cercle représente la surface séparatrice à une itération différente ; la surface est affinée au fur et à mesure du procédé. Ainsi, la surface S1 représente la première surface déterminée lors des toutes premières itérations du procédé ; la surface S2 montre la surface de séparation déterminée après quelques itérations supplémentaires. La surface S3 est celle déterminée après de nouvelles itérations. Enfin, la surface S4 est obtenue et sépare tout à fait les carrés des ronds. La surface finale étant trouvée, le procédé, tel que décrit précédemment, s'arrête. REVENDICATIONS 1. Procédé pour apprendre à un neurone à fonction d'activation quadratique à classer des données selon deux classes distinctes (cll, c12) séparées par une surface séparatrice (S), ce neurone étant un neurone binaire ayant N connexions en provenance d'une entrée et recevant en entrée N nombre représentant une donnée destinée à être classée en utilisant une base d'apprentissage contenant une pluralité de données connues, chaque entrée du neurone étant affectée par un poids (wi) de la connexion correspondante, caractérisé en ce qu'il comporte les étapes suivantes a) définition d'une fonction coût (Ca) en déterminant, en fonction d'un paramètre descriptif de la surface séparatrice, une stabilité (Y4) de chaque donnée (p) de la base d'apprentissage, la fonction coût étant la somme de tous les coûts déterminés pour toutes les données de la base d'apprentissage avec où A est quelconque, B est un réel positif quelconque, P est le nombre de données de la base d'apprentissage, y12 est la stabilité de la donnée p, et T+, T- et o sont deux paramètres de la fonction coût b) initialisation des poids (wi), des rayons (ri), des paramètres (T+ et T-, avec T+ c) minimisation, par rapport aux poids des connexions (wi) et aux rayons (ri), de la fonction coût (Co) par itérations successives au cours desquelles les paramètres (T+ et T-) décroissent suivant les vitesses de recuit (6T+ et 8T-) jusqu'à un critère d'arrêt prédéfini d) obtention des valeurs des poids des connexions et des rayons du neurone. 2. Procédé selon la revendication 1, caractérisé en ce que la stabilité de chaque donnée est avec y = +1 ou -1, et où p est l'étiquette du motif, x121 est la valeur du motif p pour la ième entrée, yp est la classe du motif wu, N est le nombre d'entrées et de connexions du neurone, wi est le poids de la connexion entre l'entrée i et le neurone et ri le paramètre de rayon pour la i-ème entrée. 3. Procédé selon la revendication 1, caractérisé en ce que la stabilité de chaque donnée est avec y = +1 ou -1, et où p est l'étiquette du motif, x121 est la valeur du motif p pour la ième entrée, yp est la classe du motif u, N est le nombre d'entrées et de connexions du neurone, Wi est le poids de la connexion entre l'entrée i et le neurone et ri est le paramètre de rayon pour la i-ème entrée.