Brevet FR2826143A1 — publié le 20021220

La présente invention concerne un procédé adaptatif d'apprentissage de distributions de probabilité conditionnelle, pour établir une correspondance entre des vecteurs d'entrée appartenant à un espace d'entrée et des étiquettes appartenant un espace de sortie. Un tel procédé fait partie d'un ensemble de techniques cognitives appelées machines ou systèmes d'apprentissage supervisé et qui établissent une correspondance entre leurs entrées et leurs sorties. Les entrées modélisent des données à traiter, ou environnement, et les sorties sont les réponses, ou étiquettes, renvoyées par la machine, correspondant à ces données. Généralement une machine comporte plusieurs entrées, recevant des valeurs numériques. L'ensemble de ces valeurs d'entrée constitue un vecteur d'entrée. De même la machine possède en général plusieurs sorties numériques, qui constituent un vecteur de sortie, ou étiquette. Si l'on considère par exemple à titre d'application pratique un système de reconnaissance de caractères, le vecteur d'entrée est constitué par l'état des pixels d'une rétine sur laquelle se projette la forme d'un caractère. Le vecteur de sortie ou étiquette est composé d'un ensemble de bits qui donne le code ASCII de ce caractère. Cette correspondance entre entrée et sortie est établie dans une phase d'apprentissage durant laquelle la structure de la machine se configure automatiquement pour réaliser la tâche demandée. Au cours de cette phase, on présente au système un grand nombre d'exemples de correspondances sous forme de couples entrée présentée-sortie désirée . L'objectif à atteindre, pendant l'apprentissage, est la modélisation des relations existant entre entrées et sorties. Pendant la phase d'utilisation, qui succède à la phase d'apprentissage, des vecteurs d'entrée issus de l'environnement et n'ayant pas servi à l'apprentissage sont présentés à la machine qui fournit pour chacun d'eux une réponse associée en sortie. Cette réponse dépend de la configuration de la machine qui a été déterminée au cours de l'apprentissage. Une telle machine doit être capable de généraliser correctement, c'est à dire de fournir des réponses correctes en phase d'utilisation. Si on reprend l'exemple du système de reconnaissance de caractères, la présentation sur la rétine d'une forme de caractère qui n'a pas servi à l'apprentissage doit fournir le code ASCII correspondant sur sa sortie. Le problème de la généralisation est un problème central dans les systèmes d'apprentissage. Il est aujourd'hui mal résolu. Formellement, un système d'apprentissage supervisé établit une correspondance entre des vecteurs d'entrée x et des vecteurs de sortie y. Cette correspondance est établie à l'aide d'une base d'apprentissage comportant de nombreux exemples de couples (x, d) où x est l'entrée présentée et d représente la sortie désirée pour la machine correspondant au vecteur x. Le vecteur d'entrée x appartient à un espace d'entrée dont la dimension est égale au nombre d'entrées de la machine. On définit d'une façon similaire l'espace de sortie. Les procédés à apprentissage supervisé classiques sont fondés sur l'approximation et la recherche d'une fonction déterministe y tel que d = f (x). Un cas particulier important d'apprentissage supervisé se rapporte à la classification automatique pour laquelle les valeurs de sortie sont discrètes. C'est le cas de l'exemple de la reconnaissance de caractères où les images de caractères projetées sur la rétine sont classées selon leurs codes. Une machine de classification doit partitionner l'espace d'entrée de façon à associer une étiquette de classe à chaque partie de cet espace. Ces parties sont séparées par des frontières de décision. Par exemple, la figure 1 montre comment on associe la classe d=o à l'ensemble des points d'entrée dont les coordonnées a et b vérifient l'inéquation a + b 1, la classe d=l étant attribuée aux autres points. La frontière de décision pour cet exemple est une droite d'équation a + b = 1. On réalise ainsi de part et d'autre de cette droite, une zone d'étiquette 0 constituée par tous les points de coordonnées a + b 1. Dans un cas réel d'apprentissage, la frontière est inconnue et seule une base d'exemples (old) est disponible. La phase d'apprentissage a alors pour but de configurer la machine de façon à ce que la frontière de décision soit correctement ajustée, à l'aide de nombreux couples (x, d). Il est possible d'approximer une fonction bornée quelconque par une fonction en escalier. Lorsque cette approximation convient, toute tâche d'apprentissage supervisé peut être ramenée à une tâche de classification. Cette approche est utilisée dans la présente invention. Dans le cas où la sortie est une fonction aléatoire du vecteur d'entrée, on considère implicitement, dans le cadre classique de l'apprentissage déterministe de données aléatoires, qu'il s'agit d'une fonction déterministe bruitée : d + v = f (x) où v représente un bruit que l'apprentissage doit éliminer dans la mesure du possible afin d'approcher au mieux d. Cette vision déterministe de l'apprentissage à partir de données issues d'un processus stochastique n'est plus adaptée lorsque ce processus ne peut pas être réduit à la somme d'une fonction déterministe avec un bruit parasite. Dans ce cas, il est utile d'estimer une distribution de probabilité conditionnelle P (ylx) d'obtenir la valeur de sortie y pour un vecteur x présenté à l'entrée du système d'apprentissage. Les machines capables d'estimer des distributions P (ylx) à partir d'exemples sont appelés machines d'apprentissage de distributions de probabilité conditionnelle. C'est une machine d'apprentissage de ce type qui est l'objet de la présente invention. Parmi les systèmes d'apprentissage connus, il existe notamment des réseaux de neurones artificiels. Cependant, les réseaux de neurones artificiels à apprentissage supervisé classique, tel que celui de type rétropropagation du gradient, ne renvoient qu'une valeur unique pour chaque sortie et sont mal adaptés aux traitements de données aléatoires autres que ceux d'une classification binaire. De plus, la détermination de leurs architectures optimales peut s'avérer délicate et leur relative complexité calculatoire conduit à des temps d'apprentissage le plus souvent longs. Par ailleurs, la détermination des caractéristiques statistiques des distributions conditionnelles, telles que la moyenne ou la variance, qui utilisent une méthode d'intégration de Monte Carlo, est malaisée avec ce type d'approche. On connaît également le système d'apprentissage des k plus proches voisins qui a des propriétés de généralisation similaires à la présente invention. Des adaptations simples pourraient sans doute lui permettre également l'apprentissage de distributions de probabilité conditionnelle. Cependant, la complexité algorithmique élevée des calculs, mis en oeuvre pendant sa phase d'utilisation, en limite l'usage. Il n'est par ailleurs pas trivial d'estimer le paramètre k a priori. Un algorithme d'apprentissage supervisé classique, qui met en oeuvre une méthode de partitionnement, tend à optimiser les positions des frontières entre les classes de telle sorte que chaque région obtenue soit la plus homogène possible du point de vue des variables de sortie associées aux vecteurs d'entrée qu'elle contient. Cette optimisation, obtenue en minimisant une erreur de classification, n'a pas de sens dans le cadre d'un apprentissage de densité de probabilité. Par ailleurs, même si la machine devait apprendre une correspondance déterministe y = j (x), le placement optimal des frontières au sens de la minimisation d'une erreur de classification serait néfaste à une bonne capacité de généralisation. En effet, dans le cas où la base d'apprentissage serait trop petite en regard de la complexité du système d'apprentissage, une séparation optimale des exemples de la base conduirait à un phénomène de sur-apprentissage. La présente invention a donc pour but principal de remédier à tous ces inconvénients et, pour ce faire, elle a pour objet un procédé d'apprentissage du type susmentionné qui se caractérise essentiellement en ce qu'il consiste à partitionner l'espace des entrées en régions, où chaque région est telle que les distributions de probabilité conditionnelle de l'étiquette pour tout vecteur de cette région ne soient pas significativement différentes de la distribution de probabilité conditionnelle de l'étiquette dans cette région, et chaque région contient un sousensemble de vecteurs d'apprentissage suffisamment grand de façon qu'il soit possible de lui appliquer un test statistique de comparaison de distributions. Selon une autre caractéristique de l'invention, on regroupe les régions en super-régions, de manière que la distribution des étiquettes connaissant leurs vecteurs d'entrée associés d'une super-région donnée ne soit pas significativement différente de celles contenues dans chacune de ses régions composantes. De préférence, le regroupement de régions en surper-régions s'effectue à l'aide de comparaisons de distributions, par l'intermédiaire de tests statistiques d'hypothèses existants. Si un arbre de classification est utilisé pour réaliser le partitionnement récursif de l'espace d'entrée, son fonctionnement doit répondre aux critères suivants : - le partitionnement d'une région associée à un noeud de l'arbre ne prend pas en compte les étiquettes ; - l'opération de partitionnement est réitérée pour chacun des noeuds des nouveaux niveaux (de-Marbre) construits tant que sa région associée contient un nombre de vecteurs d'entrée suffisamment grand pour permettre l'utilisation d'un test statistique de comparaison de distributions, ou encore que ses vecteurs d'entrée ne sont pas confondus ou ne sont pas tous associés à la même valeur de sortie ; et - le regroupement en super-régions (S) est permis par l'élagage de sous-arbres de l'arbre de classification construit, et n'intervient que si les distributions associées à tous les noeuds d'un tel sous-arbre ne sont pas significativement différentes, selon les tests statistiques. Une forme d'exécution de l'invention est décrite ci-après à titre d'exemple, en référence aux dessins annexés dans lesquels : - la figure 1, déjà décrite, est un schéma illustrant un procédé de partitionnement classique simplifié avec deux zones de classement séparées par une frontière de décision constituée par une droite ; - la figure 2 est un schéma illustrant le procédé de partitionnement conforme à l'invention pour deux gaussiennes dans un espace bidimensionnel ; - la figure 3 est un schéma illustrant le procédé de partitionnement conforme à l'invention dans sa version améliorée avec regroupement de régions voisines en super-régions, toujours pour deux gaussiennes dans un espace bidimensionnel ; - la figure 4 est un schéma illustrant un arbre de classification binaire à 4 classes ; - la figure 5 est un schéma illustrant le partitionnement en régions correspondantes par l'arbre de classification de la figure 4 dans un espace bidimensionnel ; - les figures 6a et 6b sont des schémas illustrant deux stratégies de recherche des sous-arbres candidats ; et - les figures 7a et 7b sont des schémas illustrant deux stratégies de recherche des sous-arbres à élaguer. La présente invention concerne un nouveau système d'apprentissage automatique établissant une correspondance entre ses entrées et ses sorties durant une phase d'apprentissage. Lors de son utilisation le système doit être capable de généraliser ses réponses en présence de données non apprises. La capacité de généralisation étant difficile à estimer durant la phase d'apprentissage des systèmes classiques, on propose ici une solution technique qui permet de prévoir et de contrôler cette capacité de généralisation. Plus précisément, le procédé d'apprentissage de distributions de probabilité conditionnelle conforme à l'invention est fondé sur une technique originale de partitionnement de l'espace des entrées qui permet la construction de régions, indépendamment des variables de sorties ou étiquettes associées aux données d'apprentissage. Ces régions comportent chacune un minimum contrôlé d'exemples. On peut également, grâce à la mise en oeuvre de tests statistiques d'hypothèses, regrouper les régions en super-régions, de façon à améliorer la capacité de généralisation et à minimiser la quantité de ressources utilisées par le procédé. Schématiquement, le procédé de l'invention peut être analysé en trois phases successives : 1. Dans la première phase, on partitionne l'espace des vecteurs d'entrés x en régions R dont la distribution de probabilité de la variable de sortie ou étiquette y, soit P (ylx), conditionnée par la connaissance de son vecteur d'entrée associé x en est indépendante. De cette façon, P (y lx) n'est pas significativement différent de P (yIR). Pour qu'une distribution puisse être correctement estimée, avec un risque d'erreur donné, il faut disposer d'un échantillon comportant un minimum de n vecteurs d'entrée. La valeur de n dépend de la nature de l'outil statistique adopté et aussi de la nature du problème. L'algorithme de partitionnement s'arrête lorsque chaque partition contient au moins n points ou encore est constituée de vecteurs d'entrée tous confondus ou associés à la même étiquette. Un exemple d'un tel partitionnement, dans un espace bidimensionnel, est illustré par la figure 2 pour deux distributions gaussiennes appartenant chacune à une classe différente, la gaussienne 1 étant représenté par des + et la gaussienne 2 par des . . 2. Dans la deuxième phase, on estime les distributions de probabilité conditionnelle P (yIR) P (ylx) associées aux régions R. Ces distributions peuvent être estimées, par exemple, à l'aide d'histogrammes. 3. Enfin, dans la troisième phase, on regroupe les régions voisines en super-régions afin que la distribution de y sachant x P (ylx) p (yIS) d'une super-région S donnée ne soit pas significativement différente de celles contenues dans chacune de ses régions composantes. Ces comparaisons de distributions mettent en oeuvre un procédé existant, comme un test statistique d'hypothèses. La qualité de l'estimation obtenue en est ainsi accrue et la complexité du système réduite. Un exemple de partitionnement, obtenu après avoir appliqué ce type de regroupement sur les partitions de l'exemple de la figure 2, est représenté sur la figure 3. Dans cette figure : - les zones repérées 1 représentent les partitions composées de points de la gaussienne 1 ; - les zones repérées 2 représentent les partitions composées de points de la gaussienne 2 ; et les zones repérées 3 représentent les partitions matérialisant une frontière floue séparant les deux gaussiennes. On va maintenant décrire, à titre d'exemple non limitatif, un procédé adaptatif d'apprentissage de distributions de probabilité conditionnelle mettant en oeuvre, conformément à l'invention, les trois phases mentionnées ci-dessus. Ce procédé d'apprentissage, connu sous l'appellation CDDT (Conditional Distribution Discrimination Tree), est fondé sur une technique du type arbre de classification. Un arbre de classification, est une structure arborescente dont la racine et chaque noeud interne constituent une décision, c'est-à-dire un test de partitionnnement sur les données à traiter (les vecteurs d'entrée). Dans le cas binaire, chaque noeud de l'arbre peut avoir au plus deux descendants (noeuds fils). Ses arêtes peuvent être étiquetées suivant le résultat du test de décision effectué à son niveau. Toutes les feuilles de l'arbre sont associées à des classes différenciées par une étiquette. A chaque classe correspond une région de l'espace des entrées. Un exemple d'arbre de classification binaire à 4 classes A, B, C, D est représenté sur la figure 4 et le partitionnement en régions correspondant dans un espace à deux dimensions est représenté par la figure 5. La structure de classification d'un arbre de classification est hiérarchique. Les données, vecteurs d'entrée à traiter, sont récursivement partitionnées. De cette façon il devient facile de trouver la classe associée à un vecteur d'entrée en parcourant l'arbre, de la racine jusqu'aux feuilles, en fonction du résultat du test de décision de chacun des noeuds traversés. Ainsi, la réponse en sortie qui sera renvoyée pour ce vecteur d'entrée sera l'étiquette associée à la feuille correspondante. Un arbre de classification est construit en utilisant un ensemble d'apprentissage, constitué de vecteurs d'entrée x à classer et éventuellement de la variable de sortie ou étiquette y qui leur est associée si l'apprentissage est supervisé. Sa construction automatique niveau par niveau, de la racine jusqu'aux feuilles, est appelée induction. Cette dernière est en fait la procédure d'apprentissage de l'arbre de classification. On va maintenant décrire les trois phases de fonctionnement du système d'apprentissage selon l'invention pour un arbre de classification. Phase 1 : méthode de partitionnement et induction de l'arbre CDDT L'apprentissage CDDT consiste à partitionner de façon récursive 1 niveau par niveau, l'espace E des vecteurs d'entrée de façon que chaque sommet s de l'arbre de classification corresponde à une région Rs de E. Au départ de la phase de construction de l'arbre, ou induction, ce dernier n'est constitué que d'un noeud r, auquel est associé l'espace E et l'ensemble X formé par tous les vecteurs d'entrée de la base d'apprentissage. Un algorithme de partitionnement est alors appliqué à E, en utilisant les vecteurs de X, pour construire les k nouvelles sous-régions Rj (j E [l, k]) de E, associées au k noeuds successeurs de r. On en déduit les k sousensembles Xj formés des vecteurs de X appartenant aux sous-régions Rj et qui sont associés à chacun de ces noeuds. Cette opération de partitionnement est réitérée, pour tous les nouveaux noeuds, tant que les sous-ensembles Xj obtenus sont divisibles, au sens des critères généraux d'arrêt du partitionnement de la phase 1 décrite supra. En pratique, pour que le partitionnement de X soit effectué indépendamment des variables de sorties y associées aux vecteurs d'entrée de X, des méthodes de partitionnement non supervisées existantes peuvent être utilisées, comme par exemple une décomposition en cellules de Voronoi par l'algorithme LBG. Phase 2 : estimation d'une distribution de probabilité pour le CDDT A chacun des sommets s de l'arbre est associé un histogramme Hiss (y) à N classes des valeurs prises par la variable de sortie y, les vecteurs d'apprentissage contenus dans Rs étant connus. Dans le cas du problème d'approximation de fonction, dans un espace continu, l'utilisation d'histogrammes impose la discrétisation des valeurs prises par la sortie y. Pour cela, il faut diviser l'intervalle de variation de y en N classes consécutives de limites notées Yi et Yii pour 1'V. A une classe i est ainsi associé le nombre d'occurrences de y compris entre les deux bornes YI et YI+1 de cette classe. Cette discrétisation permet aussi de ramener le problème d'approximation de fonctions à un problème de classification. Phase 3 : procédure d'élaGaGe de l'arbre CDDT Lorsque l'induction est terminée, une procédure d'élagage est appliquée à l'arbre obtenu, afin d'en simplifier sa structure tout en n'hypothéquant pas la qualité de l'estimation de la distribution de probabilité conditionnelle P (ylx). Pour satisfaire aux critères de la phase 3, il est nécessaire de garantir que P (yins) d'une super-région S n'est pas significativement différente de toutes celles de ses régions composantes. Une feuille de l'arbre étant associée à une région, ses ancêtres sont associés à des super-régions la contenant. Ainsi une procédure originale d'élagage est définie. Elle met en oeuvre un critère fondé sur la comparaison des distributions de probabilité estimées (leurs histogrammes) de la variable de sortie y, associées à des noeuds de l'arbre, en se servant d'un test statistique d'hypothèses. La méthode de comparaison utilisée peut être fondée, par exemple, sur le test de Kolmogoroff-Smirnoff. Cependant, ce test ne peut être appliqué, avec un risque de seconde espèce acceptable, que si les distributions à comparer ont des effectifs au moins égaux à 30 lorsqu'elles sont inconnues a priori. Ceci entraîne la fixation de la limite n (définie avec les règles générales de partitionnement de la phase 1) à la valeur 30. D'autres critères peuvent être utilisés pour réaliser cette comparaison. Le principe de fonctionnement de l'algorithme d'élagage proposé est le suivant : - les histogrammes de la distribution des valeurs possibles en sortie, associés à tous couples de noeuds (noeud courant, noeud ancêtre), sont comparés à l'aide de tests statistiques de Kolmogoroff-Smirnoff ; - un sous-arbre, dont toutes les feuilles sont des feuilles de l'arbre, est supprimé si les distributions associées à tous ses noeuds, comparés deux à deux, ne sont pas significativement différentes. Comme les arbres obtenus à la fin de l'induction peuvent être de taille importante, le nombre de comparaisons peut être rédhibitoire. Pour réduire la complexité des calculs de la procédure d'élagage, il est possible de mettre en oeuvre des stratégies ne faisant plus intervenir l'ensemble de tous les couples possibles de noeuds de l'arbre. Par exemple, la procédure d'élagage proposée est décomposée en deux étapes : - recherche de sous-arbres candidats à l'élagage en effectuant des comparaisons partielles de couples de noeuds. Ces sous-arbres ne sont que candidats et seuls des tests de comparaisons plus complets de tous leurs noeuds permettront, à l'étape suivante, de prendre la décision de les supprimer. Diverses stratégies sont envisageables à cet égard ainsi qu'on le verra par la suite ; - tests de comparaison plus complets des noeuds des sous-arbres candidats et suppression de ces sous-arbres si les histogrammes comparés ne sont pas significativement différents. Là encore, plusieurs stratégies sont possibles, ainsi qu'on le verra plus loin. Exemples de stratéqies de recherche des sous-arbres candidats Une première stratégie est fondée sur des comparaisons d'histogrammes effectuées entre les noeuds adjacents de l'arbre. Un sous-arbre est candidat si les histogrammes de tous ses noeuds adjacents ne sont pas significativement différents. Cette stratégie est illustrée par la figure 6a, sur laquelle les comparaisons à mettre en oeuvre entre histogrammes de noeuds du sous-arbre sont figurées par des arcs en pointillé. Une seconde stratégie met en oeuvre des comparaisons qui sont effectuées entre la distribution des feuilles (distribution de référence) et celle de tous leurs ancêtres, jusqu'à la rencontre d'un ancêtre associé à une distribution significativement différente. Un sous-arbre de sommet s est candidat à l'élagage si son histogramme n'est pas significativement différent de ceux de toutes ses feuilles. Cette stratégie est illustrée par la figure 6b, sur laquelle les feuilles de référence sont noircies. Exemples de stratéqies de recherches des sous-arbres à élaquer Il faut déterminer maintenant, au sein de l'ensemble des sous-arbres candidats, ceux qui doivent être élagués. Pour cela, deux options sont envisageables : - soit tous les sous-arbres candidats sont élagués de façon à réduire au maximum la complexité des calculs, mais c'est au détriment de la fiabilité du procédé ; - soit des stratégies de comparaison entre noeuds internes d'un sous-arbre, plus complètes que celles employées pendant la phase de recherche des candidats et réduisant le risque de seconde espèce à une valeur acceptable, permettent de déterminer s'il doit être élagué. Là encore, deux stratégies de comparaisons possibles sont présentées ci-après à titre d'exemples. La première stratégie met en oeuvre des comparaisons deux à deux de tous les noeuds d'un sous-arbre candidat. Ce dernier pourra ainsi être élagué si tous les histogrammes comparés deux à deux ne sont pas significativement différents. Cette stratégie est illustrée par la figure 7a, sur laquelle les comparaisons à mettre en oeuvre entre histogrammes de noeuds du sous-arbre sont figurées par des arcs en pointillé et le sommet du sous-arbre est noirci. La deuxième stratégie, illustrée par la figure 7b, consisterait à comparer la distribution associée à la racine du sous-arbre aux distributions de tous ses noeuds descendants. Il serait alors possible de supprimer un sous-arbre si la distribution de sa racine et les distributions de tous ses descendants n'étaient pas significativement différentes. On voit donc en définitive que le procédé d'apprentissage conforme à l'invention qui vient d'être décrit est rapide et simple à mettre en oeuvre. De plus, il traite avec la même efficacité aussi bien des données déterministes qu'aléatoires et permet d'obtenir efficacement des estimations de paramètres statistiques. Les résultats obtenus en prédiction, modélisation et génération de séries temporelles de débits de trafics ATM et Ethernet par CDTT augurent bien de son potentiel à traiter les applications de télécommunications telles que, par exemple, l'optimisation des procédures de redimensionnement dynamique des ressources. Mais ce procédé d'apprentissage peut trouver aussi des applications dans de nombreux autres domaines tels que, entre autres, l'analyse, la classification et la prédiction de données, le traitement du signal, la robotique, la finance, l'astronomie, etc... REVENDICATIONS 1. Procédé adaptatif d'apprentissage de distributions de probabilité conditionnelle, pour établir une correspondance entre des vecteurs d'entrées (x) appartenant à un espace d'entrée et des étiquettes (y) appartenant à un espace de sortie, caractérisé en ce qu'il consiste à partitionner l'espace des entrées en régions (R), où chaque région (R) est telle que les distributions de probabilité conditionnelle [P (ylx)] de l'étiquette (y) pour tout vecteur (x) de cette région ne soient pas significativement différentes de la distribution de probabilité conditionnelle [P (ylR) l de l'étiquette (y) dans cette région (R), et chaque région (R) contient un sousensemble de vecteurs d'apprentissage (x) suffisamment grand de façon qu'il soit possible de lui appliquer un test statistique de comparaison de distributions. 2. Procédé d'apprentissage selon la revendication 1, caractérisé en ce qu'il consiste à regrouper les régions (R ) en super régions (S), de manière que la distribution des "étiquettes (y) connaissant leurs vecteurs d'entrée associés (x)"d'une super-région donnée ne soit pas significativement différente de celles contenues dans chacune de ses régions composantes. 3. Procédé d'apprentissage selon la revendication 2, caractérisé en ce que le regroupement de régions (R) en super-régions (S) s'effectue à l'aide de comparaisons de distributions, par l'intermédiaire de tests statistiques d'hypothèses existants. 4. Procédé d'apprentissage selon les revendications 1 à 3, dans lequel on utilise un arbre de classification pour réaliser le partitionnement récursif de l'espace d'entrée, caractérisé en ce que le fonctionnement de cet arbre de classification répond aux critères suivants : - le partitionnement d'une région (R) associée à un noeud de l'arbre ne prend pas en compte les étiquettes (y) ; - l'opération de partitionnement est réitérée pour chacun des noeuds des nouveaux niveaux (de 1'arbre) construits tant que sa région associée contient un nombre de vecteurs d'entrée suffisamment grand pour permettre l'utilisation d'un test statistique de comparaison de distributions, ou encore que ses vecteurs d'entrée ne sont pas confondus ou ne sont pas tous associés à la même valeur de sortie ; et - le regroupement en super-régions (S) est permis par l'élagage de sous-arbres de l'arbre de classification construit, et n'intervent que si les distributions (P (y|R)] associées à tous les noeuds d'un tel sous-arbre ne sont pas significativement différentes, selon les tests statistiques.