Stratégies multi-classes

Classification hiérarchique

 Les méthodes présentées jusqu’ici sont basées sur des combinaisons de classifieurs indépendants qui peuvent être traités en parallèle. Nous présentons ici quelques méthodes multi-classes où l’ordre des classifieurs est déterminant. Celles-ci sont basées sur une structure d’arbre (graphes connexes acycliques) dont les nœuds représentent les différents classifieurs ; on parlera également de classification hiérarchique.

Graphe Acyclique Direct (DAGSVM) 

La première contribution basée sur les graphes de décision s’appuie sur une structure particulière proposée par Platt et al. [186], qui réduit le nombre de classifications dans le processus de décision. On associe au nœud racine l’ensemble des classes. Chaque nœud décrit un classifieur portant sur la première et la dernière des classes associées. La règle de décision implique deux branches, associées chacune à la négation d’une classe, qui est ôtée de la liste du noeud fils. La figure 5.3 clarifie cette structure pour un exemple à 4 classes. Figure 5.3 – Structure du Graphe Acyclique Direct (DAGSVM) défini pour un problème à 4 classes. À chaque nœud est associé un discriminateur (n vs m) et la liste des classes restantes (agencée verticalement à gauche du nœud). Les auteurs nomment ce modèle DAGSVM (pour Direct Acyclic Graph SVM ). Celui-ci repose sur l’élimination d’une classe à chaque nœud de discrimination. La feuille terminale de l’arbre indique l’unique classe restante, résultat de la classification. On voit que cette structure implique exactement les mêmes classifieurs par paires que l’approche OVO. Si l’ordre des éliminations successives a théoriquement une influence sur les résultats, les auteurs avancent, d’après leurs observations empiriques, que celle-ci est très modérée et non systématique. Cette approche a le mérite de se baser sur les classifieurs par paires, supposés plus robustes que les classifieurs OVA, tout en n’impliquant que C classifications pour la prise de décision, au lieu des C(C − 1)/2 nécessaires pour l’approche OVO. Néanmoins, comme la méthode OVO avec vote majoritaire, elle ne fournit aucune estimation des probabilités a posteriori. 5.1.5.2 Dendogrammes (DSVM) La structure d’arbre de classification permet également la mise en place d’un algorithme [21] par discriminations successives sur des unions de classes, à l’aide d’un dendogramme. Les auteurs du DSVM (Dendogram SVM ) regroupent itérativement les classes par clustering bottom-up sur les exemples d’apprentissage. Le processus, basé sur une mesure de proximité entre les groupes de classes, permet ainsi la construction d’un dendogramme décrivant le processus top-down de classification, illustré par l’exemple figure 5.4. La structure du dendogramme renseigne sur les classifieurs nécessaires à la classification. Ceuxci associent aux nœuds les plus profonds des paires de classes, et aux autres nœuds des paires impliquant des unions de classes (qui regroupent les exemples de plusieurs classes). On trouve une formulation équivalente sous le nom de « Half against Half » [130], où le dendogramme est construit sur un paradigme top-down, où chaque nœud de classification est choisi de manière à équilibrer les deux groupes de classes discriminées. Cette approche implique un très net gain en complexité puisque la classification n’implique que dlog2 Ce discriminations successives. Toutefois elle ne fournit qu’un indice de classe estimée et ne permet pas d’estimer les probabilités a posteriori. 5.1.5.3 Dendogrammes hybrides Nous proposons une extension du cadre de l’approche par dendogramme en combinant ce dernier à l’approche One-vs-One. On peut en effet étendre l’arbre de classification à des arbres non-binaires en traitant d’éventuels nœuds non-binaires (c’est-à-dire à plus de deux branches filles) par une approche multi-classes non hiérarchisée. Le cadre One-vs-One est ici le mieux indiqué puisqu’il nous permet, contrairement à l’approche One-vs-All, d’estimer les probabilités a posteriori des classes 76 5.1. COMBINAISONS DE SVM Figure 5.4 – Dendogramme de classification top-down sur un exemple de problème à 9 classes. Chaque noeud du dendogramme est associé à un classifieur binaire fn. impliquées. Cette approche constitue ainsi ce que nous appelons le dendogramme hybride. 5.1.5.4 Probabilités a posteriori par pondérations successives La plupart des méthodes multi-classes présentées jusque-là se focalisent sur le problème de l’estimation de la classe des exemples, laissant de côté la question des probabilités a posteriori. Nous proposons une méthode simple permettant d’estimer ces probabilités sur l’approche par dendogramme. Celle-ci est basée sur un parcours récursif de l’arbre de classification. On supposera qu’à chaque nœud est associé un index n unique et un classifieur fn. Le résultat probabilisé du classifieur fn sur l’exemple x est noté f ∗ n (x). Le nœud racine est associé à l’index 1. La figure 5.5 fournit un exemple de dendogramme indexé pour un problème à 6 classes (les index de nœuds sont en gris clair et les index de classes en bleu). 

Reformulation des SVM

 Nous avons décrit plusieurs méthodes pour combiner les résultats de différents classifieurs biclasses pour une tâche multi-classes. Plusieurs auteurs ont cependant tenté de reformuler directement les Machines à Vecteurs de Support sur ce type de problèmes. Cette tâche est loin d’être évidente puisque, comme nous l’avons vu, les SVM reposent sur le principe de la maximisation de la marge, dont la définition même repose sur le principe de la séparation linéaire. On trouve ainsi plusieurs alternatives dans la littérature, dont les références [197] et [95] couvrent un large éventail. Nous présentons ici brièvement les principales d’entre elles. 78 5.3. DISCUSSION ET CONCLUSION La première approche est introduite en 1998 par Weston et Watkins [246]. Elle consiste à déterminer simultanément les C fonctions de décision « un contre tous » fc : fc(x) = Xn i=1 αc,i yi k(x, xi) + bc. L’idée de base est de contraindre les variables d’écart, non plus indépendamment pour chaque fonction, mais relativement aux résultats des autres. Ainsi, le problème comprend n × (C − 1) variables d’écart ξic (où n est le nombre d’exemples) relatives à chaque classe c 6= yi , où yi est la classe de l’exemple xi , avec les contraintes suivantes : fyi (xi) ≥ fc(xi) + 1 − ξic et ξic ≥ 0 Si la formulation du problème est simple, elle pose plusieurs difficultés pour sa mise en application. En premier lieu la formulation du problème dual (non présentée ici) ne permet pas de se débarrasser des constantes introduites dans le problème primal, comme c’est le cas pour les SVM bi-classes. De plus, les auteurs ne proposent aucune implémentation efficace de l’algorithme d’optimisation, qui ne peut tirer partie des techniques permettant de rendre efficace l’apprentissage SVM traditionnel. Le problème posé est donc beaucoup plus complexe, du fait de la multiplication du nombre de variables d’écart, et donc difficilement applicable sur des données réelles. Bredensteiner et Bennett ont proposé, sans lien avec Weston et Watkins, une approche [37] basée sur les mêmes contraintes liant les fonctions de décisions entre elles : fyi (xi) ≥ fc(xi) + 1 − ξic. Soit, dans le cas linéaire : (wyi − wc) T xi ≥ (bc − byi ) + 1 − ξic. Cette relation les mène à proposer la valeur 2 kwc−wdk comme mesure de séparabilité entre les classes c et d. Ils suggèrent donc la minimisation du terme kwc − wdk sur toutes les paires (c, d), regularisée par le terme PC c=1 kwck 2 .L’expression duale du problème permet de substituer aux produits scalaires la fonction noyau. L’équivalence formelle avec l’approche de Weston et Watkins a par la suite été démontrée par différents auteurs .

Discussion et Conclusion

Le bilan essentiel de la courte présentation précédente est qu’il n’existe pas à l’heure actuelle de formulation multi-classes des SVM qui fasse consensus au sein de la communauté. Celle-ci se limite encore essentiellement aux méthodes par combinaisons présentées dans la section 5.1, beaucoup plus simples à mettre en place et bien moins coûteuses en temps de calcul. En vérité, on peine à trouver dans la littérature des résultats qui justifient l’usage des SVM reformulées plutôt que celui des méthodes par combinaisons. Les résultats expérimentaux de Weston et Watkins [246] ne montrent pas d’amélioration des performances par rapport à une simple approche OVA ou OVO, et se focalisent surtout sur la réduction du nombre de vecteurs de support. 79 CHAPITRE 5. STRATÉGIES MULTI-CLASSES On trouvera de plus dans [107] un test comparatif impliquant les méthodes de Weston & Watkins, de Crammer & Singer, OVO, OVA et les DAGSVM, duquel il ne ressort pas d’avantage particulier pour les méthodes reformulées. Rifkin et Klautau [197] ont également écrit un plaidoyer très didactique en faveur de la méthode un contre tous (OVA), souvent dédaignée dans la littérature. Reproduisant avec rigueur les expériences de nombreux articles, ils montrent que cette méthode, de loin la plus simple de toutes, est tout à fait comparable en performances aux alternatives considérées (OVA, ECOC avec diverses configurations, ainsi que les méthodes reformulées présentées précédemment). En définitive, leur constat est que les méthodes se valent globalement, si l’on prend la peine d’affiner avec soin les paramètres des classifieurs SVM impliqués dans le processus. Cette conclusion justifie donc l’attention particulière que nous portons à cette question dans le chapitre 4. Les implémentations libres de méthodes par SVM réformulées sont pour l’instant rares et très coûteuses en temps de calcul. Aussi, au vue des résultats expérimentaux énoncés ci-dessus, nous n’avons porté notre attention que sur les méthodes multi-classes par combinaisons de SVM. Il est difficile d’évaluer les méthodes multi-classes en dehors d’un contexte applicatif, aussi nous reportons l’évaluation comparée de ces dernières au chapitre d’évaluation 10, dont la section 10.3 présente une comparaison de différentes taxonomies de classification sur des corpus audio. Toutefois, le résultat théorique essentiel de ce chapitre réside dans notre proposition d’une méthode de classification hybride combinant l’approche one-vs-one aux arbres de classification hiérarchiques, couplé à une procédure d’estimation des probabilités a posteriori. Cette dernière contribution démarque l’approche proposée de la plupart des méthodes de l’état de l’art (comme l’approche one-vs-all ou les DAGSVM), qui ne permettent pas d’estimer ces probabilités.