Étude de la classification dans un très grand nombre de catégories

Classification extrême et Big Data

Apprentissage automatique

Toute tâche d’apprentissage statistique est basée sur l’exploitation de données. Nous allons ainsi commencer par définir cette donnée qui constitue la brique de base sur laquelle s’appuient tous les algorithmes d’apprentissage. Une donnée représente une information. Cette information peut prendre diverses formes comme la valeur des pixels d’une image, les lettres et les mots formant un document textuel ou les caractéristiques telles que l’âge ou le sexe d’un être humain. Ces données sont produites constamment et en très grand nombre tous les jours. Un individu surfant sur internet laisse derrière lui un sillon d’informations par l’intermédiaire de cookies que stockent les sites visités dans le but de vendre des espaces publicitaires adaptés. Un capteur de pollution sur un toit parisien va enregistrer une information de pollution de l’air (dioxyde de carbone, ozone) à un certain moment de la journée et pour un endroit spécifique dans Paris. Ces données brutes ne sont pas utilisables directement, un traitement est requis pour extraire une information spécifique qui sera ensuite utilisable selon les besoins du problème.

Le fait de traiter ces données a un coût. Il est nécessaire d’utiliser du temps de processeur pour analyser, trier et extraire une information utile à partir d’une masse de données brutes. Une donnée brute venant d’un capteur d’appareil photo numérique ne sera qu’une succession de nombres venant de la mesure de la quantité de lumière qui arrive sur chacun des pixels constituant le capteur. En l’état, cette succession de nombres n’est pas utilisable. Le simple fait d’afficher cette image sur un écran constitue un premier traitement simple de ces données où une correspondance entre la donnée brute du capteur et la valeur de l’intensité du pixel doit être déterminée. Un traitement plus complexe consisterait à augmenter l’information de l’image en annotant les différents éléments qui sont visibles sur la photo (visages, voitures, arbres).

Ce traitement permet d’ajouter de la valeur et de l’interêt à cette matrice de valeurs de pixels qui constitue une donnée. Grâce à ce processus d’annotation, un utilisateur pourra par exemple trier ses photos en fonction des personnes présentes sur chacune d’elles. La famille des algorithmes d’apprentissage statistique supervisé regroupe un ensemble de méthodes permettant d’automatiser une tâche particulière de traitement de données en apprenant à généraliser à partir d’un ensemble d’exemples dits d’apprentissages préannotés (le plus souvent à la main). Il faut ensuite réussir à modéliser au mieux le processus d’inférence permettant d’augmenter l’information de la donnée. Une fois les paramètres du modèle appris grâce à l’ensemble d’apprentissage, le modèle est supposé être capable de reproduire l’inférence d’information pour de nouvelles données jamais vues auparavant.

Big Data

Il apparaît que la vitesse d’enregistrement de ces données connaît de nos jours un accroissement exponentiel. Il est reconnu partout aujourd’hui l’importance ainsi que la valeur de la donnée et il est devenu coutumier d’en enregistrer le plus possible même sans savoir exactement quoi en faire. De plus, avec la multiplication des smartphones et des objets connectés, chaque individu de nos sociétés informatisées crée un volume de données toujours plus important. Ces différents facteurs font que le différentiel grandit entre notre capacité à enregistrer de la donnée et notre capacité à la traiter. Cet écart va se creuser de plus en plus au point où il ne sera pas possible de juste doubler ou tripler la taille des clusters de calculs. L’idée d’adapter nos algorithmes de calcul pour faire face à ces volumes de données est un enjeu crucial pour les années à venir. Ainsi, notre capacité à traiter des données plus rapidement que leur vitesse de création est devenu un objectif fondamental actuel.

Temps d’inférence et complexité computationnelle

La tâche de classification

Parmi la multitude de tâches liées à l’apprentissage statistique, nous allons nous intéresser ici à la tâche de classification multi-classes, et plus particulièrement à la tâche de classification multi-classes avec un (très) grand nombre de classes. La tâche de classification consiste à catégoriser des éléments parmi plusieurs classes ou familles d’objets. La tâche qui consiste à trouver la catégorie d’un texte est un exemple de problème de classification. Il s’agit alors d’automatiser le processus permettant d’étiqueter le document textuel comme étant un texte parlant de voitures, du Siècle des Lumières où de la géographie de Paris. Une fois que le processus de traitement est appris, il est possible d’utiliser le modèle pour catégoriser automatiquement une nouvelle donnée.

Problèmes avec la Classification Extrême

La particularité de la tâche ici est de s’intéresser au cas où le nombre de catégories est beaucoup plus important que la normale. On parle ici de classification avec 1000, voire 10000 classes alors que les problèmes multi-classes classiques ne dépassent pas habituellement la centaine de classes. Aujourd’hui, il existe même des problèmes dépassant le million de catégories. Il n’est pas difficile d’imaginer des tâches pouvant atteindre le milliard de catégories dans le cas de reconnaissance de visages humains par exemple. Cette particularité engendre de nouvelles problématiques spécifiques au grand nombre de classes. Tout d’abord la tâche est plus complexe étant donné le nombre de choix plus importants. En effet, un simple classifieur aléatoire pourra espérer obtenir un taux de bonne classification de 50% pour un problème à deux classes, mais seulement de 0.01% pour un problème à 10000 classes. Ensuite, le temps de classification est plus important pour un problème avec un plus grand nombre de classes. Avec les approches classiques, ce temps de classification évolue généralement de façon linéaire avec le nombre de classes. Ceci s’explique par le fait que le classifieur classique multi-classes à besoin d’établir un score par classe. S’il y a beaucoup de classes, cela nécessite de faire intervenir la fonction de score un grand nombre de fois ce qui peut être problématique dans les problèmes de classification extrême.

Ainsi, ce travail est motivé par le besoin de produire des algorithmes de classification capables de classifier avec une complexité sous-linéaire en fonction du nombre de classes. Nous parlons ici du temps de classification d’un exemple et non du temps d’apprentissage du modèle. La problématique du temps d’apprentissage n’est pas à mettre au second plan pour autant et il apparaît évident qu’un modèle se doit de pouvoir être appris et entraîné en un temps raisonnable. Ce raisonnable est directement dépendant du contexte et des contraintes liées au problème à résoudre. Le modèle a-t-il besoin d’être mis à jour régulièrement (et donc ré-appris) ? Le travail présenté ici s’est concentré sur des algorithmes avec un temps de classification sous-linéaire (en fonction du nombre de classes) mais avec des temps d’apprentissage similaires aux méthodes classiques (c’est-à-dire au pire linéaire avec le nombre de classes du problème).

Accélérer le processus de classification

Nous avons ainsi notre but clairement énoncé : réduire la complexité du processus de classification. Habituellement, le schéma de modèle multi-classes le plus connu est le UnContre-Tous (ou plus communément désigné par l’acronyme OAA pour One-AgainstAll). Il s’agit simplement d’apprendre une fonction de score pour chaque classe. Lors de la classification d’un nouvel exemple, il suffit de calculer le score de chaque classe pour cet exemple. L’algorithme prédit ensuite la classe ayant obtenu le meilleur score. Le choix de la fonction de score est libre. Ainsi, le schéma de classification OAA nécessite d’utiliser K fois la fonction de score, où K représente le nombre de classes du problème. Comme expliqué précédemment, notre but est de faire mieux que cette complexité de classification en O(K) et de viser des complexités en O(log K). Il est nécessaire alors de réduire le nombre de fonctions de
score à utiliser.

Pour ce faire, il existe principalement deux types de modèle :
• Le modèle hiérarchique
• Le modèle ensembliste

Le modèle hiérarchique : ce type de modèle vise à organiser hiérarchiquement les fonctions de décision dans une structure arbre. Classiquement, les feuilles représentent les classes. Chaque nœud possède un classifieur. L’exemple à classifier commence au nœud racine, puis descend dans l’arbre en suivant les résultats des classifieurs de chacun des nœuds rencontrés jusqu’à atteindre un nœud feuille. La classe prédite pour cet exemple correspond à la classe associée à ce nœud feuille. Ainsi, le nombre de classifieurs utilisé sera égal à la profondeur de l’arbre (en supposant l’arbre équilibré). De par la caractéristique naturelle des arbres, la profondeur d’un arbre équilibré est logarithmique en fonction du nombre de feuilles, et donc du nombre de classes. Une classification avec un tel modèle possède ainsi une complexité en O(log K).

Le modèle ensembliste. L’idée des méthodes ensemblistes est d’agréger les réponses d’une multitude de classifieurs et de prédire la classe avec une majorité de votes positifs. Une méthode de type OAA utilise des classifieurs spécialisés dans la reconnaissance d’une classe unique. À la différence d’une méthode OAA, une méthode de la famille des codes correcteurs d’erreurs (ou ECOC pour Error Correcting Output Codes) utilise un ensemble de classifieurs dont chacun d’entre eux est entraîné à reconnaître un nombre limité de classes largement inférieur à K, le nombre de classes à reconnaître. L’objectif est d’obtenir un nombre final de classifieurs (pour obtenir une prédiction), moindre qu’avec une méthode de type OAA. La difficulté est alors de bien contrôler le nombre de ces classifieurs car un trop petit nombre ne permettra pas d’obtenir une classification suffisamment précise.

Le problème de la classification multi-classes

Nous allons présenter dans ce chapitre le problème de la Classification Multi-Classes ainsi que les principales méthodes qui ont été développées pour le résoudre. Dans un premier temps, nous allons formaliser le problème de classification et définir les notations que nous allons utiliser. Dans un second temps, nous allons présenter l’état de l’art du domaine, et plus particulièrement les méthodes applicables dans un contexte de classification extrême avec beaucoup de catégories. Tout d’abord, nous verrons les modèles ensemblistes utilisant un ensemble de classifieurs. Ensuite, nous présenterons les travaux relatifs à l’apprentissage de hiérarchies de classifieurs. Ces méthodes sont naturellement adaptées à la problématique de classification extrême. Nous verrons ensuite une troisième famille de méthodes cherchant à apprendre un espace latent pour les classes permettant de résoudre plus facilement le problème de classification dans un grand nombre de classes.

Formalisation de la tâche de classification

La tâche de classification est une tâche d’apprentissage statistique qui cherche à assigner une classe y à des exemples x représentés sous la forme d’un vecteur. Les exemples xi sont de dimension D : xi ∈ RD ; et à chaque exemple xi est associée une classe yi tel que : yi ∈ L avec L = {lk}k∈(1,K) où K représente le nombre de classes différentes du problème. Le problème d’optimisation peut s’écrire d’une façon générale comme la minimisation du risque associé théorique de classification :

h∗ = arg min hR(h)

Le modèle linéaire

La résolution de la tâche de classification multi-classes est principalement basée sur les travaux développés pour résoudre la tâche de classification binaire. Ce problème fondamental de l’apprentissage statistique a été très étudié et de nombreux travaux ont permis de le modéliser de façon précise. Les schémas de classification multi-classes classiques sont essentiellement constitués d’un ensemble de classifieurs binaires simples qui sont combinés de façon à former un classifieur plus complexe capable de classifier parmi plus que deux classes.

Les SVM (pour Support Vector Machine) [Cortes and Vapnik, 1995] utilisent le Hinge loss comme fonction de coût de substitution. Le problème d’optimisation peut être résolu par descente de gradient stochastique [Bottou and Bousquet, 2008]. Les SVM linéaires et la regression logistique sont souvent utilisés comme briques de base pour les modèles plus complexes nécessaires à la classification multi-classe. Les deux briques ont des performances similaires sur les problèmes de classification binaires. Les schémas de classification comme l’OAA (pour One-Against-All — Un Contre-Tous), l’OAO (pour One-Against-One — Un-Contre-Un) ou les ECOC (pour Error Correcting Output Code — Codes Correcteurs d’Erreurs) sont des exemples courants de méthodes ensemblistes utilisant des classifieurs binaires simples dans le but de former un classifieur plus complexe multi-classe. Il a ainsi été montré [Rifkin and Klautau, 2004] comment l’utilisation de SVM comme classifieurs simples de ces méthodes permet d’établir les performances de l’état de l’art sur des problèmes variés. Nous verrons plus tard en détail ces schémas ensemblistes de classification multi-classe.

Table des matières

1 Introduction
1.1 Classification extrême et Big Data
1.1.1 Apprentissage automatique
1.1.2 Big Data
1.2 Temps d’inférence et complexité computationnelle
1.2.1 La tâche de classification
1.2.2 Problèmes avec la Classification Extrême
1.2.3 Accélérer le processus de classification
Le modèle hiérarchique
Le modèle ensembliste.
1.3 Contributions
1.4 Plan
2 Le problème de la classification multi-classes
2.1 Introduction
2.2 Formalisation de la tâche de classification
2.2.1 Le modèle linéaire
2.2.2 Limites dans le contexte d’extreme classification
2.2.2.1 Caractérisation du Big Data
Nombre d’exemples.
Espace dimensionnel.
Nombre de classes.
2.2.2.2 Exemple de bases de données
2.2.2.3 Un nouveau paradigme
2.2.2.4 Limites des méthodes usuelles
2.2.3 Le classifieur simple
2.3 Méthodes ensemblistes
2.3.1 One-Against-All
2.3.2 One-Against-One
2.3.3 Error Correcting Output Codes
2.3.4 Discussion
2.4 Approches hiérarchiques
2.4.1 Formalisation du modèle hiérarchique
2.4.1.1 Structure d’un arbre
2.4.1.2 Affectation des classes
2.4.1.3 Fonctions de décision
2.4.2 Apprentissage d’une hiérarchie de labels
2.4.2.1 Méthodes Top-Down
Partitionnement par clustering spectral.
Partitionnement redondant.
2.4.2.2 Agrégation Bottom-up
2.4.3 Apprentissage des fonctions de décision dans les nœuds de la hiérarchie
2.4.3.1 Apprentissage indépendant des modèles
2.4.3.2 Apprentissage joint des modèles
2.4.3.3 Apprentissage itératif des modèles
2.4.4 Apprentissage global
2.5 Méthodes d’Embedding
3 Caractérisation des Schémas de Classification
3.1 Introduction
3.2 Schéma de classification
3.2.1 Formalisme du schéma de classification
3.2.1.1 Création de l’ensemble de classifieurs simples
3.2.1.2 Processus de classification
3.2.2 Complexité du processus de classification
3.3 Étude des schémas de classification
3.3.1 Étude des schémas de classification classiques
3.3.2 Expérimentations
3.3.3 Étude de l’erreur
3.3.4 Étude du compromis Complexité-Précision
3.4 Conclusion
4 Création de hiérarchie et partitionnement de classes
4.1 Introduction
4.2 Construction de hiérarchie et mesure d’agrégation
4.2.1 Algorithme d’agrégation
4.2.2 Mesure d’agrégation
4.3 Construction de hiérarchie par dichotomie (DSAA)
4.3.1 Présentation de l’approche
4.3.2 Algorithme de sélection du nœud à développer
4.3.3 Algorithme de partitionnement des classes
4.4 Expérimentations
4.4.1 Protocole
4.4.2 Résultats
4.4.3 Discussion
4.4.4 Étude de la hiérarchie obtenue
4.5 Conclusion
5 Conclusion

Télécharger le rapport complet