La construction de bons classificateurs permettant de déterminer si un nouvel objet (ou exemple) appartient à l'une ou l'autre des catégories (ou classes) préalablement définies est un défi omniprésent et d'une grande importance dans presque tous les secteurs en sciences et génie. En effet, les médecins désirent obtenir de bons classificateurs qui puissent déterminer précisément la maladie d'un patient à partir d'une liste de symptômes, les bio-informaticiens désirent obtenir des classificateurs qui puissent déterminer si un profil d'expression de gènes d'une matrice d'ADN provient d'un tissu cancéreux ou non, les ingénieurs en traitement d'image tentent d'obtenir des classificateurs permettant de reconnaître (et de classer) des caractères manuscrits, les informaticiens tentent de construire des classificateurs pouvant déterminer si un courriel est légitime ou non... Dans (presque) tous ces cas, le classificateur final est obtenu en exécutant un algorithme d'apprentissage sur une base de données d'exemples préalablement classifiés (par des humains). L'objectif de cet algorithme d'apprentissage est alors d'obtenir le classificateur (à partir de la base de données) qui puisse prédire avec le plus d'exactitude possible la classe des exemples qui seront observés par la suite. Puisque le succès de cette démarche commune repose entièrement sur la qualité de l'algorithme d'apprentissage utilisé, tout progrès réalisé sur la qualité de ces algorithmes aura un impact immédiat dans plusieurs secteurs en sciences et génie.

Dans cette perspective, Marchand et Shawe-Taylor (2002) ont proposé une classe d'algorithmes d'apprentissage, appelés SCMs (Set Covering Machines), dont l'objectif est de construire un classificateur comprimant le plus possible les données de l'échantillon d'apprentissage (les exemples préalablement classifiés). De plus, ils ont obtenu une garantie formelle sur l'habileté à prédire du classificateur sous la forme d'une borne supérieure sur la probabilité de faire une erreur de classification sur un nouvel exemple. Cette borne indique que la probabilité de faire une erreur sera faible lorsque le classificateur comprime beaucoup les données tout en ne faisant pas trop d'erreurs sur l'échantillon d'apprentissage. Pour tenter d'obtenir de tels classificateurs, Marchand et Shawe-Taylor (2002) ont proposé un algorithme glouton contenant certains paramètres ajustables permettant à l'utilisateur de choisir le compromis, précision (sur l'échantillon d'apprentissage) et compression de données. Parmi tous les classificateurs générés par cet algorithme en utilisant différentes valeurs pour les paramètres ajustables, la borne s'est avérée étonnamment précise à sélectionner le meilleur classificateur: celui prédisant le mieux la classe des exemples d'un échantillon test. Bien que les résultats obtenus par l'algorithme glouton se comparent favorablement à l'algorithme d'apprentissage SVM (Support Vector Machine), généralement considéré comme l'état de l'art, le succès inattendu obtenu par la borne sur le risque de Marchand et Shawe-Taylor suggère de construire un algorithme d'apprentissage qui a pour but de trouver un classificateur minimisant cette borne sur le risque. Or l'algorithme glouton proposé jusqu'ici ne possède pas cette garantie.

Les SCMs sont actuellement parmi les algorithmes d'apprentissage les plus performants, principalement lorsque l'espace des attributs est de faible dimension (moins de 30). Malheureusement, comme la pluspart des autres algorithmes d'apprentissage, à haute dimension, les SCMs souffrent de ce qu'on appelle la malédiction de la dimensionnalité.  L'objectif premier de ce travail de maîtrise sera d'analyser ce problème et d'essayer d'y trouver des correctifs.

L'objectif secondaire est de concevoir un algorithme d'apprentissage, pour classificateurs de type SCM, qui minimise la borne sur le risque de Marchand et Shawe-Taylor. Ce problème d'optimisation est NP-complet car il contient, comme cas particulier, le problème du recouvrement minimal (minimum set cover). Cependant, nos analyses préliminaires nous indiquent qu'une approche "branch-and-bound" nous donnera un classificateur minimisant la borne en un temps "raisonnable" pour des échantillons d'apprentissage de 200 ou 300 exemples. Ces résultats nous permettront d'évaluer la "sous-optimalité" de l'algorithme glouton de Marchand et Shawe-Taylor et de voir comment il est possible de modifier ces algorithmes plus rapides pour qu'ils produisent de meilleurs classificateurs. Ces résultats pourraient également nous suggérer des algorithmes probabilistes de type Monté-Carlo donnant l'optimal avec une probabilité finie en un temps beaucoup plus rapide que celui de l'algorithme "branch-and-bound" . Il est possible également que ces résultats nous suggèrent une borne à minimiser légèrement différente (mais produisant de meilleurs classificateurs) de celle proposée par Marchand et Shawe-Taylor.

L'espace de tous les classificateurs possibles est exponentiellement grand. Ainsi, les implémentations actuelles de l'algorithme des SCMs ne font pas une recherche exhaustive de l'ensemble complet des classificateurs possibles, mais une recherche ciblée par approche gourmande qui en théorie peut choisir un classificateur qui soit très éloigné du classificateur optimal.  Pour vérifier à quel point un classificateur obtenu avec cette approche est différent du classificateur optimal, l'espace des classificateurs pour des problèmes donnés sera exploré avec une approche "branch-and-bound" pour trouver le véritable SCM qui minimise la borne et comparer sa performance.

Les améliation qui seront implémentées à partir de la version des SCMs qui utilisent des hypersphères adapteront des techniques de "réduction de dimensionalité" (comme PCA, KPCA, principal curves, constructions de variétés, etc.) aux SCMs.  Les performances des nouveaux algorithmes seront évaluées théoriquement dans un premier temps, puis comparées entre elles et à celle des SVMs quand ils sont appliqués à des problèmes d'apprentissage à haute dimensionnalité.

Les résultats de mes travaux sont consignés dans mon mémoire.