Zum Inhalt springen
Zurück zu den Suchergebnissen

Halb-überwachtes Entscheidungsbaumverfahren

Eingeführt von
Various (Levin & Shapiro; Zhu & Goldberg lineage)
Jahr
2000s
Typ
Semi-supervised classifier / regressor
Familie
Machine learning

Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen

Schriftgröße

Was leistet sie?

Ein halb-überwachtes Entscheidungsbaumverfahren erweitert Standard-Entscheidungsbauminduktionsverfahren – wie CART oder C4.5 –, um neben dem gelabelten Trainingsdatensatz auch ungelabelte Beobachtungen zu nutzen.

Durch iterative Zuweisung vorläufiger Labels zu ungelabelten Daten und deren Einbeziehung in den wachsenden oder teilenden Prozess kann der Algorithmus eine höhere Genauigkeit erzielen als ein rein überwachter Baum, der allein auf dem gelabelten Teil-Datensatz trainiert wurde. Dies ist besonders wertvoll, wenn das Labeling kostspielig oder zeitaufwendig ist.

Die Intuition hinter der Methode

Jede Beobachtung zu labeln ist kostspielig, doch ungelabelte Daten enthalten immer noch nützliche strukturelle Informationen über den Merkmalsraum. Ein halb-überwachtes Entscheidungsbaumverfahren nutzt dies, indem es zunächst einen Baum aus den wenigen gelabelten Beispielen aufbaut, diesen Baum verwendet, um die ungelabelten Daten vorläufig zu labeln, und dann auf dem erweiterten Datensatz neu trainiert. Wiederholte Iterationen verfeinern sowohl die vorläufigen Labels als auch die Baumstruktur gleichzeitig, sodass das Modell aus der gesamten Datenverteilung lernt, auch wenn Ground-Truth-Labels knapp sind.

Geschichte

Das halb-überwachte Lernen entstand Ende der 1990er Jahre, als Forscher versuchten, die Fülle ungelabelter Daten in Bereichen wie Webklassifikation und Computerbiologie zu nutzen. Self-Training-Varianten von Entscheidungsbäumen, bei denen ein Baum iterativ seine eigenen ungelabelten Daten labelt, gehörten zu den frühesten Instanziierungen. Eine formale Behandlung erschien in der Übersichtsarbeit von Zhu & Goldberg (2009), die baumbasiertes Self-Training in die breitere Taxonomie des halb-überwachten Lernens einordnet. Seitdem wurden Ansätze auf Ensemble-Einstellungen erweitert, die halb-überwachte Random Forests und Gradient-Boosted Trees hervorbringen.

Wann wird sie eingesetzt?

Halb-überwachte Entscheidungsbäume sind geeignet, wenn gelabelte Daten knapp und teuer zu beschaffen sind, aber ein großer Pool ungelabelter Beobachtungen verfügbar ist – häufig bei der Annotation medizinischer Bilder, der Textklassifikation und der sensorbasierten Überwachung. Sie sind besonders nützlich, wenn die allgemeine Merkmalsverteilung durch den ungelabelten Pool gut erfasst wird und wenn ein menschenlesbares Modell (ein Baum) erforderlich ist. Vermeiden Sie diese Methode, wenn die gelabelte Stichprobe so klein ist, dass der anfängliche Baum höchst unzuverlässig ist, wenn ungelabelte Daten nicht repräsentativ für die Testverteilung sind oder wenn erwartet wird, dass der Pseudo-Labeling-Prozess systematische Fehler (Bestätigungsfehler) verstärkt. In diesen Fällen können rein überwachter Methoden auf sauberen gelabelten Daten oder alternative halb-überwachte Ansätze wie Label Propagation oder Co-Training sicherer sein.

Grenzen und Hinweise

  • Pseudo-Label-Fehler eines unzuverlässigen anfänglichen Baumes können sich über Iterationen hinweg verstärken und die Leistung im Vergleich zu einem rein überwachten Basismodell verschlechtern.
  • Die Methode geht davon aus, dass die ungelabelten Daten dieselbe zugrundeliegende Verteilung wie die gelabelten Daten aufweisen; eine Verteilungsverschiebung bricht diese Annahme.
  • Die Rechenkosten steigen mit jeder Iteration, da Bäume auf immer größeren effektiven Datensätzen neu trainiert werden.
  • Die Auswahl des Konfidenzschwellenwerts für die Einbeziehung von Pseudo-Labels erfordert sorgfältige Abstimmung und Kreuzvalidierung.

Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.

Stärken

  • Nutzt ungelabelte Daten zur Verbesserung der Genauigkeit bei wenigen gelabelten Beispielen, wodurch die Annotationskosten reduziert werden.
  • Behält die Interpretierbarkeit von Entscheidungsbäumen bei: das resultierende Modell ist eine menschenlesbare Menge von Wenn-Dann-Regeln.
  • Verarbeitet natürlich gemischte Merkmalstypen – kontinuierlich, kategorisch, binär – ohne Vorverarbeitungsnormalisierung.
  • Iteratives Self-Training ist einfach auf jedem vorhandenen Baumler zu implementieren.
  • Kann nichtlineare Grenzen und Merkmalsinteraktionen erfassen, die lineare halb-überwachte Modelle übersehen.

Anwendungen

  • Klassifikation medizinischer Bilder und Datensätze, bei denen die Expertenannotation teuer ist und große, nicht annotierte Archive existieren.
  • Text- und Dokumentenkategorisierung mit kleinen gelabelten Korpora und großen ungelabelten Sammlungen.
  • Analyse von Sensor- und IoT-Daten, bei denen nur ein Bruchteil der Zeitreihensegmente manuell gelabelt ist.
  • Bioinformatik-Aufgaben wie die Vorhersage von Genfunktionen mit wenigen experimentell verifizierten Labels.
  • Betrugserkennung, wenn gelabelte Betrugsfälle im Vergleich zum Volumen ungelabelter Transaktionen selten sind.

So funktioniert es

So funktioniert es

1

Ein Standard-Entscheidungsbaum (z. B. CART oder C4.5) wird nur mit dem gelabelten Teil des Datensatzes angepasst. Dieses anfängliche Modell liefert eine erste Annäherung an die Entscheidungsgrenzen und dient als Keimzelle für die nachfolgenden halb-überwachten Iterationen.

2

Jede ungelabelte Beobachtung wird durch den aktuellen Baum geleitet, und die vorhergesagte Klasse (bei Klassifikation) oder der vorhergesagte Wert (bei Regression) wird als vorläufiges Label zugewiesen. Konfidenz- oder Wahrscheinlichkeitsschätzungen aus den Blattknoten können verwendet werden, um nur die zuverlässigsten Pseudo-Labels auszuwählen und Zuweisungen mit geringer Konfidenz herauszufiltern.

3

Der Baum wird von Grund auf neu trainiert, wobei sowohl die ursprünglichen gelabelten Beispiele als auch die neu pseudo-gelabelten ungelabelten Beobachtungen verwendet werden. Pseudo-Labels mit hoher Konfidenz fließen neben den echten Labels in die Teilungsentscheidungen ein und vergrößern effektiv den effektiven Trainingsdatensatz.

4

Modifizierte Teilungskriterien – wie Entropie oder Gini, berechnet über gelabelte und ungelabelte Beobachtungen, oder bi-kriterielle Ziele, die die überwachte Reinheit mit der unüberwachten Cluster-Kohärenz in Einklang bringen – leiten die Knotenteilungen an, um die zugrundeliegende Datenverteilung zu respektieren, die durch ungelabelte Punkte offenbart wird.

5

Die Iteration wird fortgesetzt, bis sich die vorläufigen Labels über aufeinanderfolgende Runden stabilisieren oder eine maximale Iterationsgrenze erreicht ist. Standard-Post-Pruning-Strategien (Kosten-Komplexitäts-Pruning, minimale Blattgröße) werden dann auf den endgültigen Baum angewendet, um Überanpassung an die pseudo-gelabelten Daten zu kontrollieren.

Häufige Fallstricke

  • Verwendung aller Pseudo-Labels unabhängig von ihrer Konfidenz, was zulässt, dass qualitativ minderwertige Zuweisungen spätere Iterationen dominieren.
  • Versäumnis zu überprüfen, ob die ungelabelten Daten vor dem Training aus derselben Verteilung wie der gelabelte Datensatz stammen.
  • Behandlung der Blattstatistiken des endgültigen Baumes als rein überwacht bei der Berichterstattung von Leistungskennzahlen – Out-of-Bag- oder zurückgehaltene gelabelte Auswertung ist erforderlich.
  • Überspringen des Prunings nach der Pseudo-Label-Augmentierung, was zu schwerer Überanpassung an verrauschte vorläufige Labels führt.
  • Direkter Vergleich mit einem rein überwachten Baum, der auf demselben gelabelten Teil-Datensatz trainiert wurde, ohne die zusätzliche Verwendung ungelabelter Daten zu berücksichtigen.

Häufig gestellte Fragen

Wie unterscheidet sich ein halb-überwachtes Entscheidungsbaumverfahren von einem regulären Self-Training-Klassifikator?

Das Kernprinzip – Nutzung von Vorhersagen auf ungelabelten Daten zur Augmentierung des Trainings – ist dasselbe. Was baumspezifische Ansätze unterscheidet, ist die Möglichkeit, das Teilungskriterium selbst zu modifizieren, um ungelabelte Verteilungsinformationen einzubeziehen, anstatt nur den gelabelten Satz iterativ zu erweitern.

Wie viele gelabelte Beispiele benötige ich zum Start?

Es gibt kein universelles Minimum, aber der anfängliche überwachter Baum muss zuverlässig genug sein, um nützliche Pseudo-Labels zu erzeugen. In der Praxis werden oft mindestens 20–50 gelabelte Beispiele pro Klasse empfohlen; bei weniger ist das Risiko der Fehlerfortpflanzung hoch und alternative Ansätze wie Label Propagation können besser funktionieren.

Sollte ich alle ungelabelten Daten verwenden oder eine Teilmenge auswählen?

Die Auswahl nur von Pseudo-Labels mit hoher Konfidenz – zum Beispiel solche, bei denen die Blattwahrscheinlichkeit einen Schwellenwert von z. B. 0,85 überschreitet – übertrifft im Allgemeinen die Verwendung aller ungelabelten Punkte, insbesondere wenn der anfängliche Baum unvollkommen ist.

Ersetzt dies die Standard-Kreuzvalidierung?

Nein. Da Pseudo-Labels aus dem Modell selbst abgeleitet werden, sind In-Sample-Metriken optimistisch. Die Auswertung muss einen zurückgehaltenen gelabelten Testdatensatz oder eine k-fache Kreuzvalidierung verwenden, die streng auf die gelabelte Partition angewendet wird.

Kann ich dies mit Ensemble-Methoden kombinieren?

Ja. Halb-überwachte Random Forests und Co-Forest-Ansätze erweitern die Idee auf Ensembles, die die Varianz von Pseudo-Label-Fehlern reduzieren und typischerweise einen einzelnen halb-überwachten Baum übertreffen können.

Verwandte Methoden

Quellen

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

    Publikationsreferenz öffnen
    Kopiert.
  2. Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.

    ISBN: 978-1-598-29548-9
    Kopiert.