Optimisation d’ensembles de classifieurs non paramétriques

La classification est un domaine d’application et de recherche où des automates, souvent des programmes informatiques, ont à prendre des décisions quant à 1′ appartenance d’un objet à une classe. Ce problème est considéré être un sous-domaine de la RF, cette dernière étant une branche de l’intelligence artificielle [37]. Un système de reconnaissance de visage permet de décider si celui-ci appartient ou non à une personne donnée, tandis que certains moteurs de recherche tentent de déterminer la langue dans laquelle un texte électronique a été écrit. Ces deux exemples sont des domaines où l’être humain excelle à reconnaître des formes. D’autres applications ne sont cependant pas envisageables sans automatisation: la recherche de patrons répétitifs dans des séquences d’ADN en est un exemple. Même lorsque l’humain est performant à reconnaître certains types de formes, il peut être avantageux d’automatiser la tâche surtout en cas de fort volume de données à traiter : le tri des enveloppes postales en est une bonne illustration.

L’émergence des ordinateurs et de l’informatique au milieu du XXe siècle a permis au domaine de la RF d’évoluer parallèlement. Un des premiers problèmes à faire surface concerne la représentation du monde réel. En effet, tout dans un ordinateur est ultimement représenté par une série d’unités binaires, ce qui n’est pas nécessairement la façon dont l’humain procède. Dans les années 50, Glantz se demande s’il ne faudrait pas tenter de mieux comprendre les processus mentaux sous-jacents à la reconnaissance de formes par l’humain pour faire progresser la RF automatique [26]. Dans les années 60, Bledsoe fait apparaître le problème de la RF dans le contexte très fréquent et très réel où un grand nombre de classes sont possibles: contrairement aux lettres de l’alphabet latin, le nombre d’empreintes digitales ou de visages humains différents est énorme [5]. À la même époque, Prather [61] explore des méthodes d’induction et d’apprentissage automatique dans le but de créer un éventuel automate de reconnaissance «tout usage.»  .

Les problèmes de Bongard, popularisés par Hosfstadter [34], synthétisent à eux seuls tous ces aspects du problème de la reconnaissance de formes . Ils posent à la fois le problème de la représentation des objets, de l’apprentissage et du nombre illimité de formes possibles. À la fin des années 60, Mikhail Moiseevich Bongard proposa 100 problèmes qui devaient être un défi pour l’intelligence artificielle [7]. La résolution de ces problèmes par des automates demeure toujours très délicate [52]. Ces derniers se présentent sous la forme de deux ensembles de six images. Celles du côté gauche sont toutes conformes à une même règle ou sont créées à partir d’un même patron, alors que l’ensemble des figures du côté droit n’obéissent pas à cette règle. L’objectif du reconnaisseur de formes (humain ou machine) est de trouver cette règle, c’est-à-dire de déterminer en quoi un ensemble de formes est différent d’un autre.  il n’en est pas de même pour un automate. Les problèmes de Bongard, par leur généralité, nous renvoient à l’essence même de l’intelligence humaine.

Le problème de l’intelligence artificielle en général et de la RF en particulier est si vaste qu’il est nécessaire de l’aborder par sous-problèmes. La classification est le domaine de la RF auquel le présent travail s’est intéressé. Dans ce domaine, on appelle classifieur  , parfois expert, un programme informatique dont le rôle est de décider de quel type est un objet (quelle est sa classe) en fonction des données fournies en entrée. Par exemple, en communication numérique, le classifieur détermine quel symbole a été émis en observant le signal capté par le récepteur, tandis qu’en reconnaissance de chiffres manuscrits, il doit décider quel est le chiffre qui lui est présenté à partir d’une image.

Pour prendre une décision, l’expert doit se baser sur de la connaissance a priori qui prend souvent la forme d’exemples connus, appelés prototypes. L’ensemble des prototypes est appelé la base d’apprentissage ou base d’entraînement. Ces prototypes sont souvent représentés par des vecteurs de caractéristiques où chaque composante est une mesure faite sur les objets réels (amplitude et phase d’un signal électrique, nombre de pixels noirs d’une image, hauteur d’un vérin dans un système mécanique) ou un attribut qualitatif (vert, rond, chaud, etc.). Chaque caractéristique devient donc un axe dans un espace ayant autant de dimensions que la cardinalité de l’ensemble des caractéristiques, tandis qu’un prototype est un point dans cet espace.

Le livre de Duda, Hart et Stork constitue une excellente référence sur le domaine de la RF [21].

Le problème de la reconnaissance de formes 

Le système de reconnaissance peut être décomposé en plusieurs étapes . Les différentes parties du système sont décrites ci-dessous.

La détection
La détection consiste à convertir en signaux électriques, à l’aide de transducteurs, des grandeurs physiques mesurées sur l’objet à reconnaître. Par exemple, un microphone convertit une variation de pression de l’air en tension électrique. Ce signal, une fois numérisé, sert d’entrée au système. L’étude et la conception de transducteurs est un vaste domaine regroupant plusieurs disciplines, dont la physique et l ‘ingénierie.

Le prétraitement
Lors de l’étape de prétraitement, les signaux d’entrées sont mis en forme et traités de façon à rendre possible l’étape subséquente d’extraction de caractéristiques. Par exemple, c’est à cette étape qu’un signal sera filtré, qu’une image sera binarisée, normalisée ou redimensionnée. Avant de passer à l’étape suivante, on devra aussi très souvent segmenter le signal. La segmentation consiste à séparer le signal en unités de base indivisibles. Par exemple, en reconnaissance de la parole, la segmentation se fait souvent au niveau des phonèmes qui constituent les mots à reconnaître alors qu’en reconnaissance d’écriture cette segmentation pourrait se faire au niveau des lettres. On comprend tout de suite que l’étape de segmentation est intrinsèquement liée à tout le processus de RF. En effet, comment peut-on segmenter un mot en lettres sans reconnaître d’abord un ensemble de pixels comme étant une lettre? Prendre les arêtes ou toute autre unité de base plus petite ne fait que repousser le problème à un autre niveau. L’étape de segmentation est donc elle même un processus de reconnaissance de formes de plus bas niveau; processus qui, à son échelle, devra sans doute lui-même passer par une étape de segmentation. Ce paradoxe fait de la segmentation un des grands problèmes de la RF puisqu’il pose celui ontologique de l’ existence a priori d’unités indivisibles dans les formes à reconnaître. Et si de telles unités n’existent pas, une question épistémologique s’impose : «Quel est le rôle de la segmentation?» Or, expérimentalement, on sait que cette étape, bien que nécessairement imparfaite, facilite généralement le processus de RF. Ces questions dépassent les domaines généralement abordés par les membres de la communauté de la RF mais constituent le coeur du problème. Bien qu’une branche de la philosophie, appelée méréologie, se penche spécifiquement sur l ‘étude des relations entre les touts et leurs parties, en pratique l’automatisation de la segmentation se fait généralement à partir d’heuristiques déterminées empiriquement pour maximiser la performance d’un système.

L’extraction de caractéristiques
Dans les années 70, Zobrist réfléchissait à la question de la représentation des données [79] et concluait que la reconnaissance de formes serait mieux servie par des machines utilisant une représentation interne des objets à reconnaître qui leur est propre, en opposition avec représentation compréhensible par les humains. Bien que la question ne soit certainement pas entièrement réglée, c’est aujourd’hui la façon de faire la plus courante. L’extraction de caractéristiques consiste donc à transformer une forme en une représentation interne à l’automate de classification. Elle est constituée plus précisément d’une série de mesures faites sur des objets (où des segments d’objets) à reconnaître. Par exemple, on peut mesurer la puissance d’un signal à des fréquences bien définies de son spectre, on peut aussi compter le nombre de pixels d’une certaine intensité ou calculer les moments statistiques d’une distribution (une distribution spatiale de pixels ou une distribution temporelle de fréquences par exemple). L’ensemble de ces mesures forme une représentation des objets qui sera utilisée à l’étape de classification. La difficulté ici est de trouver de bonnes caractéristiques. De « bonnes » caractéristiques permettent aux classifieurs de reconnaître facilement les différentes classes d’objets; on dit alors qu’elles sont discriminantes. Elles doivent aussi être invariantes à certaines transformations (la lettre A appartient à la même classe quelle que soit sa taille). À la limite, des caractéristiques parfaitement discriminantes permettraient de déterminer automatiquement à quelle classe appartient un objet. Mais alors, le module d’extraction de caractéristiques deviendrait lui-même un module de classification. En fait, la distinction entre la partie d’extraction de caractéristiques et de classification est arbitraire d’un point de vue conceptuel mais utile en pratique dans l’implantation de systèmes réels. Un extracteur de caractéristiques peut alors prendre la forme d’un programme qui produira des représentations de données qu’un classifieur pourra utiliser ultérieurement. Ainsi, pour comparer différents classifieurs on choisira la même représentation des même données ; pour comparer le pouvoir discriminant de différentes caractéristiques, on utilisera les mêmes classifieurs avec différentes représentations d’une même base de données.

La classification
Le classifieur a pour fonction d’assigner une étiquette de classe à l’objet qui lui est présenté par l’extracteur de caractéristiques. Un avantage pratique de la séparation entre l’extraction de caractéristiques et la classification est que de cette façon, il est possible d’étudier les classifieurs hors de leur domaine d’application spécifique; ceci grâce au niveau d’abstraction suffisamment élevé produit par la représentation des objets sous forme de vecteurs de caractéristiques. Le travail du classifieur consiste à séparer l’espace de représentation par des frontières  et à assigner des étiquettes de classe aux régions ainsi formées. La région où se trouve un vecteur de caractéristiques détermine donc sa classe d’appartenance. Généralement, il n’est pas possible de bâtir une partition parfaite de l’espace, aussi le rôle du classifieur sera souvent de donner une probabilité d’appartenance d’un objet à une classe. De plus, dans les applications réelles, le système doit composer avec un certain bruit ou biais (qu’il soit gaussien et dû aux transducteurs de l’étape de détection, ou qu’il soit de toute autre nature comme un dérèglement progressif, une interférence avec un autre appareil, etc). Souvent, il prendra la forme de caractéristiques absentes (un capteur peut être défectueux, une donnée peut ne pas être disponible). Le classifieur doit pouvoir gérer ces imperfections, et la façon d’entraîner des classifieurs pour y faire face est un domaine de recherche en soi.

Le post-traitement
L’étape ultime du processus de RF, appelée post-traitement, regroupe toutes les actions à prendre lors de la classification ou non de l’objet à classer (fusion des sorties de plusieurs classifieurs, évaluation d’un seuil de confiance, décision de classer ou de rejeter un objet). S’il y a classification, on assignera l’objet à une classe alors qu’on le rejettera dans le cas contraire. Cette décision peut se prendre à partir des probabilités émises par le classifieur mais aussi grâce à d’autres sources d’information émanant du contexte par exemple. Le post-traitement peut aussi être l’étape de fusion de multiples résultats de classification dans un contexte d’ensembles de classifieurs.