Skip to content
Retour aux résultats

Arbre de décision semi-supervisé

Introduite par
Various (Levin & Shapiro; Zhu & Goldberg lineage)
Année
2000s
Type
Semi-supervised classifier / regressor
Famille
Machine learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Un arbre de décision semi-supervisé étend l'induction standard des arbres de décision — tels que CART ou C4.5 — pour exploiter des observations non étiquetées aux côtés de l'ensemble d'entraînement étiqueté.

En attribuant itérativement des étiquettes provisoires aux données non étiquetées et en les incorporant dans le processus de croissance ou de division, l'algorithme peut atteindre une meilleure précision qu'un arbre entièrement supervisé entraîné uniquement sur le sous-ensemble étiqueté, ce qui est particulièrement précieux lorsque l'étiquetage est coûteux ou prend du temps.

L’intuition derrière la méthode

L'étiquetage de chaque observation est coûteux, pourtant les données non étiquetées contiennent toujours des informations structurelles utiles sur l'espace des caractéristiques. Un arbre de décision semi-supervisé exploite cela en construisant d'abord un arbre à partir des quelques exemples étiquetés, en utilisant cet arbre pour étiqueter provisoirement les données non étiquetées, puis en réentraînant sur l'ensemble élargi. Des itérations répétées affinent simultanément les étiquettes provisoires et la structure de l'arbre, de sorte que le modèle apprend de la distribution globale des données même lorsque les étiquettes de vérité terrain sont rares.

Histoire

L'apprentissage semi-supervisé a émergé à la fin des années 1990 alors que les chercheurs cherchaient à exploiter l'abondance de données non étiquetées disponibles dans des domaines tels que la classification web et la biologie computationnelle. Les variantes d'auto-entraînement des arbres de décision, où un arbre étiquette itérativement ses propres données non étiquetées, ont été parmi les premières instanciations. Un traitement formel est apparu dans l'enquête de Zhu & Goldberg (2009), qui situe l'auto-entraînement basé sur des arbres dans la taxonomie plus large de l'apprentissage semi-supervisé. Depuis lors, les approches se sont étendues aux paramètres d'ensemble, produisant des forêts aléatoires semi-supervisées et des arbres à gradient boosté.

Quand l’utiliser

Les arbres de décision semi-supervisés sont appropriés lorsque les données étiquetées sont rares et coûteuses à obtenir, mais qu'un grand pool d'observations non étiquetées est disponible — courant dans l'annotation d'images médicales, la classification de textes et la surveillance basée sur des capteurs. Ils sont particulièrement utiles lorsque la distribution globale des caractéristiques est bien capturée par le pool non étiqueté et lorsqu'un modèle interprétable par l'homme (un arbre) est requis. Évitez cette méthode lorsque l'échantillon étiqueté est si petit que l'arbre initial est très peu fiable, lorsque les données non étiquetées ne sont pas représentatives de la distribution de test, ou lorsque le processus de pseudo-étiquetage est susceptible de propager des erreurs systématiques (biais de confirmation). Dans ces cas, des méthodes purement supervisées sur des données étiquetées propres, ou d'autres approches semi-supervisées telles que la propagation d'étiquettes ou le co-entraînement, peuvent être plus sûres.

Limites et points d’attention

  • Les erreurs de pseudo-étiquetage d'un arbre initial peu fiable peuvent être amplifiées au fil des itérations, dégradant les performances par rapport à une base de référence entièrement supervisée.
  • La méthode suppose que les données non étiquetées partagent la même distribution sous-jacente que les données étiquetées ; un décalage de distribution brise cette hypothèse.
  • Le coût de calcul augmente à chaque itération car les arbres sont réentraînés sur des ensembles de données effectifs de plus en plus grands.
  • La sélection du seuil de confiance pour l'inclusion des pseudo-étiquettes nécessite un réglage minutieux et une validation croisée.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Exploite les données non étiquetées pour améliorer la précision lorsque les exemples étiquetés sont peu nombreux, réduisant ainsi le coût d'annotation.
  • Conserve l'interprétabilité des arbres de décision : le modèle résultant est un ensemble de règles si-alors lisibles par l'homme.
  • Gère naturellement les types de caractéristiques mixtes — continues, catégorielles, binaires — sans normalisation préalable.
  • L'auto-entraînement itératif est simple à implémenter sur n'importe quel apprenant d'arbre existant.
  • Peut capturer des frontières non linéaires et des interactions de caractéristiques que les modèles semi-supervisés linéaires manquent.

Applications

  • Classification d'images et de dossiers médicaux où l'annotation experte est coûteuse et où il existe de grandes archives non annotées.
  • Catégorisation de textes et de documents avec de petits corpus étiquetés et de grandes collections non étiquetées.
  • Analyse de données de capteurs et d'IoT où seule une fraction des segments de séries temporelles est étiquetée manuellement.
  • Tâches de bioinformatique telles que la prédiction de la fonction génique avec peu d'étiquettes vérifiées expérimentalement.
  • Détection de fraude lorsque les cas de fraude étiquetés sont rares par rapport au volume des transactions non étiquetées.

Comment ça marche

Comment ça marche

1

Un arbre de décision standard (par exemple, CART ou C4.5) est ajusté en utilisant uniquement la partie étiquetée de l'ensemble de données. Ce modèle initial fournit une première approximation des frontières de décision et sert de germe pour les itérations semi-supervisées ultérieures.

2

Chaque observation non étiquetée est passée à travers l'arbre actuel, et la classe prédite (pour la classification) ou la valeur prédite (pour la régression) est attribuée comme étiquette provisoire. Les estimations de confiance ou de probabilité des nœuds feuilles peuvent être utilisées pour sélectionner uniquement les pseudo-étiquettes les plus fiables, en filtrant les affectations de faible confiance.

3

L'arbre est réentraîné à partir de zéro en utilisant à la fois les exemples étiquetés d'origine et les observations non étiquetées nouvellement pseudo-étiquetées. Les pseudo-étiquettes de haute confiance contribuent aux décisions de division aux côtés des vraies étiquettes, élargissant efficacement l'ensemble d'entraînement effectif.

4

Des critères de division modifiés — tels que l'entropie ou le Gini calculés sur les observations étiquetées et non étiquetées, ou des objectifs bi-critères qui équilibrent la pureté supervisée avec la cohérence des clusters non supervisés — guident les divisions des nœuds pour respecter la distribution sous-jacente des données révélée par les points non étiquetés.

5

L'itération se poursuit jusqu'à ce que les étiquettes provisoires se stabilisent sur des tours successifs ou qu'une limite d'itération maximale soit atteinte. Des stratégies de post-élagage standard (élagage coût-complexité, taille minimale des feuilles) sont ensuite appliquées à l'arbre final pour contrôler le surapprentissage sur les données pseudo-étiquetées.

Pièges courants

  • Utiliser toutes les pseudo-étiquettes indépendamment de leur confiance, ce qui permet aux affectations de faible qualité de dominer les itérations ultérieures.
  • Omettre de vérifier que les données non étiquetées sont tirées de la même distribution que l'ensemble étiqueté avant l'entraînement.
  • Traiter les statistiques des feuilles de l'arbre final comme purement supervisées lors de la déclaration des métriques de performance — une évaluation hors échantillon (out-of-bag) ou sur un ensemble étiqueté réservé est requise.
  • Sauter l'élagage après l'augmentation des pseudo-étiquettes, provoquant un surapprentissage sévère sur les étiquettes provisoires bruitées.
  • Comparer directement avec un arbre entièrement supervisé entraîné sur le même sous-ensemble étiqueté sans tenir compte des données non étiquetées supplémentaires utilisées.

Questions fréquentes

Comment un arbre de décision semi-supervisé diffère-t-il d'un classifieur d'auto-entraînement régulier ?

Le principe fondamental — utiliser les prédictions sur les données non étiquetées pour augmenter l'entraînement — est le même. Ce qui distingue les approches spécifiques aux arbres, c'est la possibilité de modifier le critère de division lui-même pour incorporer des informations sur la distribution non étiquetée, plutôt que de simplement élargir l'ensemble étiqueté itérativement.

Combien d'exemples étiquetés dois-je avoir pour commencer ?

Il n'y a pas de minimum universel, mais l'arbre supervisé initial doit être suffisamment fiable pour produire des pseudo-étiquettes utiles. En pratique, au moins 20 à 50 exemples étiquetés par classe sont souvent recommandés ; avec moins, le risque de propagation d'erreurs est élevé et des approches alternatives telles que la propagation d'étiquettes peuvent mieux fonctionner.

Dois-je utiliser toutes les données non étiquetées ou en sélectionner un sous-ensemble ?

La sélection uniquement des pseudo-étiquettes de haute confiance — par exemple celles pour lesquelles la probabilité de la feuille dépasse un seuil tel que 0,85 — est généralement plus performante que l'utilisation de tous les points non étiquetés, surtout lorsque l'arbre initial est imparfait.

Cela remplace-t-il la validation croisée standard ?

Non. Parce que les pseudo-étiquettes sont dérivées du modèle lui-même, les métriques intra-échantillon sont optimistes. L'évaluation doit utiliser un ensemble de test étiqueté réservé ou une validation croisée k-fold appliquée strictement à la partition étiquetée.

Puis-je combiner cela avec des méthodes d'ensemble ?

Oui. Les forêts aléatoires semi-supervisées et les approches de co-forêts étendent l'idée aux ensembles, ce qui peut réduire la variance des erreurs de pseudo-étiquetage et surpassent généralement un seul arbre semi-supervisé.

Méthodes associées

Sources

  1. Levin, E. & Shapiro, E. (2000). Learning Decision Trees from Semi-labeled Examples. Proceedings of the ICML Workshop on Attribute-Value and Relational Learning.

    Ouvrir la référence de la publication
    Copié.
  2. Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.

    ISBN : 978-1-598-29548-9
    Copié.