Machine à couverture d’ensembles

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; xFIGURE 2.1 – Exemple de méthode à noyau. On projette les exemples comportant deux dimensions dans un espace de dimensionnalité supérieure, soit trois dans cet exemple, afin de pouvoir y tracer un séparateur linéaire. Ce séparateur devient non linéaire dans l’espace source des exemples.

L’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.

Machine à couverture d’ensembles

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. On obtient la forme xlité est définie comme le nombre d’exemples négatifs qui sont bien classés moins le nombre d’exemples positifs qui sont mals classés par cette règle, pondérée par un paramètre p qui est déterminé par validation croisée.

L’algorithme du SCM a donc un avantage clair pour le projet décrit ici qui est sa parcimonie et son interprétabilité. La parcimonie du SCM résulte en un très petit nombre de caractéristiques, soit des pics dans un spectre de masse dans notre cas, qui établit un lien prédictif entre les classes. De plus, l’algorithme fournit une organisation logique entre les caractéristiques utilisées par la classification. Effectivement, les deux types d’organisations logiques des règles du SCM fonctionnent très bien dans un contexte biologique. Une conjonction de caractéristiques indique que plusieurs molécules sont nécessaires afin de faire la différence entre les deux classes, ce qui est un cas courant en biologie. Le cas d’une disjonction est aussi très compatible. De trouver un classificateur ayant une disjonction entre deux pics par exemple pourrait indiquer que deux voies métaboliques distinctes sont impliquées dans la différence entre les classes.