Application de l’apprentissage automatique

Il faut par contre introduire les différents algorithmes utilisés. Un type d’algorithme qui fut utilisé au cours des travaux présentés ici est la classe des méthodes à noyau. Ces méthodes furent utilisées mal- gré le fait qu’elles ne sont pas parcimonieuses et ni interprétables, ce qui est une des caractéristiques recherchées dans ce projet. Par contre, les méthodes à noyau sont aisément adaptées aux problèmes auxquelles elles sont appliquées. Dans ce type de méthode, l’élément principal est la fonction de noyau (kernel function) qui projette les exemples d’apprentissage dans une dimensionnalité supérieure afin de pouvoir mieux séparer les classes d’exemples Boser et collab. (1992). Un exemple de ce procédé est présenté à la figure 2.1. On cherche à avoir une fonction qui permet de faire le produit scalaire entre les vecteurs de caracté- ristiques des exemples sans avoir en mémoire les vecteurs de caractéristiques dans l’espace de dimen- sionnalité supérieure (que l’on dénote usuellement f ), ce qui est une caractéristique additionnelle des méthodes à noyau. On cherche en fait à obtenir directement la matrice de taille n par n, où n est le nombre d’exemples dans l’ensemble d’entraînement. On nomme cette matrice la matrice de Gram. C’est en se basant sur cette matrice que les algorithmes utilisant les méthodes à noyau peuvent faire de la classification. Cette matrice représente en fait une mesure de similarité entre les exemples, c’est- à-dire que si k(x; xL’algorithme utilisant les méthodes à noyau le plus répandu est l’algorithme des machines à vecteur de support (Support Vector Machine, SVM) Cortes et Vapnik (1995); Chang et Lin (2011); Fan et col- lab. (2008). Cet algorithme cherche à tracer un séparateur linéaire entre les exemples de l’ensemble d’entraînement des différentes classes. Un séparateur linéaire est un séparateur ayant une dimension de moins que l’espace des caractéristiques des exemples. Par exemple, un séparateur linéaire est une ligne droite dans le cas où les exemples ont deux dimensions ou caractéristiques. Un séparateur li- néaire est un hyperplan à deux dimensions dans le cas où les exemples ont trois dimensions pour les décrire. Par contre, l’algorithme du SVM tente de tracer le séparateur linéaire dans l’espace du noyau fourni. Comme un noyau est de plus haute dimensionnalité des données, le séparateur devient non- linéaire dans l’espace de base des exemples. On peut voir un exemple de cet effet dans les figures 2.1 et 2.2.

De plus, l’algorithme du SVM cherche à maximiser la marge du séparateur avec les exemples. La notion de marge est une notion importante pour minimiser les risques de surapprentissage. L’algo- rithme cherche à trouver le séparateur linéaire qui divise les deux classes dans l’espace du noyau et qui maximise la marge, soit la distance entre le séparateur et les exemples qui en sont le plus près. Le séparateur se retrouvera donc à une distance égale entre au moins un exemple de chacune des deux classes. Un exemple visuel est présenté dans la figure 2.2. Les exemples qui se retrouvent à la distance minimale du séparateur et qui définissent le séparateur sont appelés les vecteurs de support. Un avantage que comportent le SVM et les algorithmes utilisant les noyaux est qu’il est possible de choisir différents noyaux plus adaptés au problème étudié, voire d’en mettre au point de nouveaux. Par contre, cet algorithme présente aussi un inconvénient. Alors que, dans le projet présent, les algorithmes plus parcimonieux sont privilégiés, l’algorithme du SVM n’est pas du tout parcimonieux. Le fait d’utiliser un noyau fait qu’il faut considérer toutes les caractéristiques d’un exemple et la classification va en fait dépendre de la comparaison d’un nouvel exemple avec les vecteurs de support. Malgré cet inconvénient, cette méthode est répandue et performante, en plus d’avoir l’avantage d’être flexible. Elle a donc été incluse dans les tests de ce projet.L’algorithme qui a été le plus privilégié pour ce projet est sans doute l’algorithme de la machine à couverture d’ensembles (Set Covering Machine, abbrévié SCM) Marchand et Taylor (2002). La force de cet algorithme et la raison pour laquelle il est privilégié dans ces travaux est qu’il met l’accent sur la parcimonie. Cet algorithme est très parcimonieux au niveau du nombre de caractéristiques des exemples utilisés pour la prédiction, ce qui rend la classification facilement interprétable. Le SCM cherche à classifier les exemples en utilisant des règles simples. L’exemple le plus simple de ces règles est la souche de décision, qui a été utilisée au cours de ce projet avec le SCM. Une souche de décision est une règle où l’on prend une caractéristique d’un exemple et on y applique un seuil.