Système de classeurs | EPFL Graph Search

Un système de classeurs (Learning Classifier System ou LCS en anglais) est un système d'apprentissage automatique utilisant l'apprentissage par renforcement et les algorithmes génétiques. Ils ont été introduits par Holland en 1977 et développé par Goldberg en 1989 Un système de classeurs (aussi appelé classifiers) est composé d'une base de règles, appelée classeur, associés à un poids. Chaque règle est composée d'une partie condition et d'une partie action. Le classeur commence par être initialisé (aléatoirement ou non). Pour exécuter un système de classeur, on sélectionne l'ensemble des règles applicables pour la situation en cours et l'on effectue un tirage aléatoire proportionnel aux poids de chaque règle. Si l'action est mauvaise, on diminue le poids de la règle ayant été sélectionnée. Si au contraire elle a été bénéfique, on augmente ce poids. L'apprentissage consiste à exécuter un algorithme génétique qui va produire d'autres classeurs avec des règles différentes. Il existe plusieurs types de système de classeurs. On pourra par exemple citer : Type Michigan : L'algorithme génétique est exécuté sur une population de règles. Type Pittsburgh : L'algorithme génétique est exécuté avec des individus représentant un classeur complet et non plus seulement chaque règle. ZCS XCS ACS Système de classeurs flous Cet exemple présente un système de classeurs de type Michigan très simple. Considérons un environnement constitué de cases pouvant être remplies ou vides. Un robot évoluant dans cet environnement peut se déplacer sur une des cases adjacentes si celle-ci est vide. En numérotant les cases entourant le robot de 1 à 8 (par exemple en partant de la case en haut à gauche et en tournant dans le sens des aiguilles d'une montre), on peut écrire une condition de huit éléments binaires (0 ou 1), où le ième élément représente si la ième case adjacente est pleine ou vide. Par exemple, la condition 01000000 est vraie si le robot n'a qu'une seule case remplie autour de lui (la case au "dessus", voir figure).

Classification with class-independent quality information for biometric verification

Krzysztof Kryszczuk

Biometric identity verification systems frequently face the challenges of non-controlled conditions of data acquisition. Under such conditions biometric signals may suffer from quality degradation due to extraneous, identity-independent factors. It has been demonstrated in numerous reports that a degradation of biometric signal quality is a frequent cause of significant deterioration of classification performance, also in multiple-classifier, multimodal systems, which systematically outperform their single-classifier counterparts. Seeking to improve the robustness of classifiers to degraded data quality, researchers started to introduce measures of signal quality into the classification process. In the existing approaches, the role of class-independent quality information is governed by intuitive rather than mathematical notions, resulting in a clearly drawn distinction between the single-, multiple-classifier and multimodal approaches. The application of quality measures in a multiple-classifier system has received far more attention, with a dominant intuitive notion that a classifier that has data of higher quality at its disposal ought to be more credible than a classifier that operates on noisy signals. In the case of single-classifier systems a quality-based selection of models, classifiers or thresholds has been proposed. In both cases, quality measures have the function of meta-information which supervises but not intervenes with the actual classifier or classifiers employed to assign class labels to modality-specific and class-selective features. In this thesis we argue that in fact the very same mechanism governs the use of quality measures in single- and multi-classifier systems alike, and we present a quantitative rather than intuitive perspective on the role of quality measures in classification. We notice the fact that for a given set of classification features and their fixed marginal distributions, the class separation in the joint feature space changes with the statistical dependencies observed between the individual features. The same effect applies to a feature space in which some of the features are class-independent. Consequently, we demonstrate that the class separation can be improved by augmenting the feature space with class-independent quality information, provided that it sports statistical dependencies on the class-selective features. We discuss how to construct classifier-quality measure ensembles in which the dependence between classification scores and the quality features helps decrease classification errors below those obtained using the classification scores alone. We propose Q – stack, a novel theoretical framework of improving classification with class-independent quality measures based on the concept of classifier stacking. In the scheme of Q – stack a classifier ensemble is used in which the first classifier layer is made of the baseline unimodal classifiers, and the second, stacked classifier operates on features composed of the normalized similarity scores and the relevant quality measures. We present Q – stack as a generalized framework of classification with quality information and we argue that previously proposed methods of classification with quality measures are its special cases. Further in this thesis we address the problem of estimating probability of single classification errors. We propose to employ the subjective Bayesian interpretation of single event probability as credence in the correctness of single classification decisions. We propose to apply the credence-based error predictor as a functional extension of the proposed Q – stack framework, where a Bayesian stacked classifier is employed. As such, the proposed method of credence estimation and error prediction inherits the benefit of seamless incorporation of quality information in the process of credence estimation. We propose a set of objective evaluation criteria for credence estimates, and we discuss how the proposed method can be applied together with an appropriate repair strategy to reduce classification errors to a desired target level. Finally, we demonstrate the application of Q – stack and its functional extension to single error prediction on the task of biometric identity verification using face and fingerprint modalities, and their multimodal combinations, using a real biometric database. We show that the use of the classification and error prediction methods proposed in this thesis allows for a systematic reduction of the error rates below those of the baseline classifiers.

EPFL2008

Classification with class-independent quality information for biometric verification

Krzysztof Kryszczuk

EPFL2008