An novel efficient method of multi-class support vector machine with weighted multiple kernel learning

Imaginez que vous essayez d'apprendre à un robot à reconnaître différents animaux dans un zoo bondé. Vous pourriez lui montrer la photo d'un lion et dire : « Ça, c'est un lion », puis lui montrer un tigre et dire : « Ça, c'est un tigre ». Mais qu'en est-il si le robot doit trier des milliers d'animaux à la fois, dont certains se ressemblent beaucoup, ou si les photos sont floues ou prises sous des angles étranges ? C'est le monde de l'apprentissage automatique (machine learning), plus précisément d'une branche appelée classification, où les ordinateurs apprennent à trier des données en groupes.

Pour faire cela, les ordinateurs utilisent souvent un outil ingénieux appelé Machine à Vecteurs de Support (Support Vector Machine ou SVM). Voyez le SVM comme un arbitre super intelligent qui trace des lignes invisibles dans l'air pour séparer différents groupes. Si les animaux sont mélangés dans un tas désordonné, l'arbitre cherche le chemin le plus large et le plus clair pour séparer les lions des tigres. Généralement, l'arbitre utilise une seule « lentille » ou noyau (kernel) pour observer les données. Une lentille peut être bonne pour voir les formes, ou bonne pour voir les couleurs, mais elle est rarement parfaite pour les deux à la fois. Si les données sont complexes — comme un zoo avec des animaux qui ont des rayures, des taches et de la fourrure à la fois — une seule lentille pourrait manquer des détails.

C'est là qu'intervient l'Apprentissage par Noyaux Multiples (Multiple Kernel Learning ou MKL). Au lieu de s'appuyer sur une seule lentille, le MKL permet à l'ordinateur d'utiliser tout un kit photographique avec différentes lentilles en même temps, en les mélangeant pour obtenir l'image la plus claire possible. Cependant, il y a un piège : utiliser toutes ces lentilles sur une masse énorme de données est incroyablement lent et coûteux en termes de calcul. C'est comme essayer de trier tout le zoo à la main, un animal à la fois, en utilisant chaque loupe possible. La question que les scientifiques se posent est la suivante : Pouvons-nous obtenir la vision ultra-claire de plusieurs lentilles sans le processus lent et épuisant de vérifier chaque animal ?

---

Le nouveau « Super-Arbitre Tout-en-Un »

Dans cet article, les chercheurs Zijie Dong, Xingrui Gong et Fen Chen proposent une nouvelle façon plus rapide d'entraîner ces classificateurs multi-classes. Ils appellent leur méthode AIO-MSVM-WMK (ce qui est un peu long à prononcer, alors appelons-la simplement l'« Arbitre Pondéré Tout-en-Un »).

Leur grande idée consiste à combiner deux stratégies puissantes en une seule opération fluide :

1. Apprentissage par Noyaux Multiples Pondérés : Au lieu d'utiliser une seule lentille, ils mélangent plusieurs lentilles différentes (comme des noyaux linéaires, polynomiaux et RBF) ensemble. Mais voici l'astuce : ils ne les mélangent pas de manière égale. Ils attribuent un « poids » à chaque lentille en fonction de son efficacité pour la tâche donnée. Si la lentille « forme » est excellente pour repérer les lions, elle reçoit un vote plus important. Si la lentille « texture » est meilleure pour les tigres, elle reçoit plus de poids. Cela se produit automatiquement pendant que l'ordinateur apprend, plutôt que d'être configuré au préalable.
2. Optimisation des Échantillons : C'est le booster de vitesse. Au lieu de forcer l'ordinateur à étudier chaque animal du zoo (ce qui prend un temps infini), l'algorithme choisit intelligemment les plus importants. Il se concentre sur les animaux qui se trouvent juste sur la limite des groupes — ceux qui sont difficiles à distinguer — tout en ignorant les plus évidents qui sont faciles à trier. Cela permet de gagner un temps précieux.

Comment ils l'ont testé

Pour voir si leur nouvel arbitre était réellement meilleur, l'équipe a mené des expériences sur 9 jeux de données publics (des collections de données réelles comme des images de chiffres écrits à la main, des articles de presse et des données biologiques). Ils ont comparé leur méthode à quatre autres façons populaires de trier les multi-classes :

• AIO-Mar : Une ancienne méthode « Tout-en-Un ».
• MK-MSVCR : Une méthode qui utilise plusieurs noyaux mais d'une manière différente.
• WMK-OVO : Une méthode qui compare chaque classe à chaque autre classe (One-vs-One).
• WMK-OVA : Une méthode qui compare chaque classe à toutes les autres en même temps (One-vs-All).

Ils ont testé ces méthodes sur deux tailles différentes de données d'entraînement : l'une avec 10 000 échantillons et l'autre avec 26 000 échantillons.

Les Résultats : Plus Rapide et Plus Intelligent

Les résultats ont montré que la nouvelle méthode AIO-MSVM-WMK était la grande gagnante dans deux domaines principaux :

1. Elle commet moins d'erreurs.
Lorsque les données étaient complexes, la nouvelle méthode a trié les animaux avec plus de précision que les autres. Par exemple, sur le jeu de données « Twitter » (qui implique le tri de texte), la nouvelle méthode n'a commis des erreurs que 1,51 % du temps avec 26 000 échantillons. En comparaison, la deuxième meilleure méthode a commis des erreurs 1,78 % du temps, et les autres étaient bien pires, avec des erreurs atteignant 18,16 %. Sur le jeu de données « Mnist » (chiffres manuscrits), la nouvelle méthode présentait un taux d'erreur de 10,36 %, battant les autres qui variaient de 12,37 % à 15,28 %.

2. Elle est nettement plus rapide.
C'est ici que l'« Optimisation des Échantillons » a vraiment brillé. Les chercheurs ont mesuré le temps total nécessaire pour à la fois choisir les échantillons importants et entraîner le modèle.

• Sur le test de 10 000 échantillons, la nouvelle méthode a pris un total de 64 730 secondes (environ 18 heures) pour s'exécuter sur l'ensemble des jeux de données. La méthode la plus rapide suivante a pris 75 796 secondes, et la plus lente 90 162 secondes.
• Sur le test de 26 000 échantillons, l'écart s'est creusé. La nouvelle méthode a pris 119 671,96 secondes, tandis que le concurrent le plus lent a pris 181 262,97 secondes.

Les chercheurs ont utilisé un test statistique appelé le test de rang signé de Wilcoxon pour confirmer que ces différences n'étaient pas dues au hasard. Le test a montré que la nouvelle méthode était statistiquement meilleure que ses quatre concurrents, tant en précision qu'en vitesse.

Ce que cela signifie

L'article suggère qu'en combinant les noyaux multiples pondérés (en utilisant le meilleur mélange de lentilles) avec une sélection intelligente d'échantillons (en se concentrant uniquement sur les cas difficiles), on peut construire un classificateur qui est à la fois plus précis et beaucoup plus rapide que les méthodes actuelles.

Les auteurs notent que cette approche est particulièrement utile pour les « données multi-classes complexes et volumineuses ». Ils n'ont pas prétendu résoudre tous les problèmes du monde, mais ils ont démontré que pour les jeux de données testés, ils surpassaient les techniques existantes sans nécessiter d'étapes de pré-traitement supplémentaires. Ils ont également mentionné que les travaux futurs pourraient consister à appliquer cette idée aux réseaux de neurones profonds ou à utiliser le calcul parallèle pour la rendre encore plus rapide, mais pour l'instant, l'« Arbitre Pondéré Tout-en-Un » constitue une façon plus efficace d'enseigner aux ordinateurs comment trier les données désordonnées du monde.