Przejdź do treści
Wróć do wyników wyszukiwania

Drzewo decyzyjne z uczeniem częściowo nadzorowanym

Autor metody
Various (Levin & Shapiro; Zhu & Goldberg lineage)
Rok
2000s
Typ
Semi-supervised classifier / regressor
Rodzina
Machine learning

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Drzewo decyzyjne z uczeniem częściowo nadzorowanym rozszerza standardową indukcję drzew decyzyjnych — taką jak CART czy C4.5 — o wykorzystanie nieetykietowanych obserwacji obok etykietowanego zbioru treningowego.

Poprzez iteracyjne przypisywanie tymczasowych etykiet do nieetykietowanych danych i włączanie ich do procesu budowy lub podziału drzewa, algorytm może osiągnąć lepszą dokładność niż w pełni nadzorowane drzewo wytrenowane wyłącznie na etykietowanym podzbiorze, co jest szczególnie cenne, gdy etykietowanie jest kosztowne lub czasochłonne.

Intuicja stojąca za metodą

Etykietowanie każdej obserwacji jest kosztowne, a jednak nieetykietowane dane nadal zawierają użyteczne informacje strukturalne o przestrzeni cech. Drzewo decyzyjne z uczeniem częściowo nadzorowanym wykorzystuje to, poprzez najpierw zbudowanie drzewa z niewielu etykietowanych przykładów, użycie tego drzewa do tymczasowego etykietowania nieetykietowanych danych, a następnie ponowne trenowanie na rozszerzonym zbiorze. Powtarzane iteracje jednocześnie udoskonalają zarówno tymczasowe etykiety, jak i strukturę drzewa, dzięki czemu model uczy się z ogólnego rozkładu danych, nawet gdy etykiety prawdy absolutnej są rzadkie.

Historia

Uczenie częściowo nadzorowane wyłoniło się pod koniec lat 90. XX wieku, gdy badacze starali się wykorzystać obfitość nieetykietowanych danych dostępnych w domenach takich jak klasyfikacja stron internetowych i biologia obliczeniowa. Warianty samo-uczenia drzew decyzyjnych, w których drzewo iteracyjnie etykietuje własne nieetykietowane dane, były jednymi z najwcześniejszych implementacji. Formalne ujęcie pojawiło się w przeglądzie Zhu & Goldberg (2009), który umieszcza samo-uczenie oparte na drzewach w szerszej taksonomii uczenia częściowo nadzorowanego. Od tego czasu podejścia zostały rozszerzone na ustawienia zespołowe, produkując lasy losowe i drzewa gradientowe z uczeniem częściowo nadzorowanym.

Kiedy stosować

Drzewa decyzyjne z uczeniem częściowo nadzorowanym są odpowiednie, gdy etykietowane dane są rzadkie i kosztowne do uzyskania, ale dostępna jest duża pula nieetykietowanych obserwacji — co jest częste w anotacji obrazów medycznych, klasyfikacji tekstu i monitorowaniu opartym na czujnikach. Są one szczególnie użyteczne, gdy ogólny rozkład cech jest dobrze uchwycony przez pulę nieetykietowanych danych i gdy wymagany jest model interpretowalny przez człowieka (drzewo). Należy unikać tej metody, gdy etykietowany przykład jest tak mały, że początkowe drzewo jest wysoce niewiarygodne, gdy nieetykietowane dane nie są reprezentatywne dla rozkładu testowego, lub gdy proces pseudoetykietowania ma propagować systematyczne błędy (błąd potwierdzenia). W takich przypadkach czysto nadzorowane metody na czystych etykietowanych danych lub alternatywne podejścia częściowo nadzorowane, takie jak propagacja etykiet lub współuczenie, mogą być bezpieczniejsze.

Ograniczenia i uwagi

  • Błędy pseudoetykiet z niewiarygodnego początkowego drzewa mogą być wzmacniane w kolejnych iteracjach, pogarszając wydajność w porównaniu z w pełni nadzorowaną bazą.
  • Metoda zakłada, że nieetykietowane dane pochodzą z tego samego rozkładu co dane etykietowane; przesunięcie rozkładu narusza to założenie.
  • Koszt obliczeniowy rośnie z każdą iteracją, ponieważ drzewa są ponownie trenowane na coraz większych efektywnych zbiorach danych.
  • Wybór progu pewności dla włączenia pseudoetykiet wymaga starannego dostrojenia i walidacji krzyżowej.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Wykorzystuje nieetykietowane dane do poprawy dokładności, gdy etykietowane przykłady są nieliczne, zmniejszając koszt anotacji.
  • Zachowuje interpretowalność drzew decyzyjnych: wynikowy model to czytelny dla człowieka zbiór reguł typu jeśli-wtedy.
  • Naturalnie obsługuje mieszane typy cech — ciągłe, kategoryczne, binarne — bez wstępnego przetwarzania i normalizacji.
  • Iteracyjne samo-uczenie jest proste do zaimplementowania na dowolnym istniejącym algorytmie uczenia drzew.
  • Potrafi wychwycić nieliniowe granice i interakcje cech, których brakuje modelom liniowym z uczeniem częściowo nadzorowanym.

Zastosowania

  • Klasyfikacja obrazów medycznych i zapisów medycznych, gdzie anotacja ekspercka jest kosztowna, a istnieją duże archiwa nieanotowane.
  • Kategoryzacja tekstu i dokumentów z małymi korpusami etykietowanymi i dużymi kolekcjami nieetykietowanymi.
  • Analiza danych z czujników i IoT, gdzie tylko ułamek segmentów szeregów czasowych jest ręcznie etykietowany.
  • Zadania bioinformatyczne, takie jak przewidywanie funkcji genów, z niewielką liczbą eksperymentalnie potwierdzonych etykiet.
  • Wykrywanie oszustw, gdy etykietowane przypadki oszustw są rzadkie w porównaniu z wolumenem nieetykietowanych transakcji.

Jak to działa

Jak to działa

1

Standardowe drzewo decyzyjne (np. CART lub C4.5) jest dopasowywane przy użyciu tylko etykietowanej części zbioru danych. Ten początkowy model stanowi pierwsze przybliżenie granic decyzyjnych i służy jako punkt wyjścia dla kolejnych iteracji częściowo nadzorowanych.

2

Każda nieetykietowana obserwacja jest przepuszczana przez bieżące drzewo, a przewidywana klasa (dla klasyfikacji) lub przewidywana wartość (dla regresji) jest przypisywana jako tymczasowa etykieta. Szacunki pewności lub prawdopodobieństwa z liści mogą być użyte do wybrania tylko najbardziej wiarygodnych pseudoetykiet, filtrując przypisania o niskiej pewności.

3

Drzewo jest ponownie trenowane od podstaw przy użyciu zarówno oryginalnych etykietowanych przykładów, jak i nowo pseudoetykietowanych nieetykietowanych obserwacji. Pseudoetykiety o wysokiej pewności przyczyniają się do decyzji o podziale obok prawdziwych etykiet, skutecznie powiększając efektywny zbiór treningowy.

4

Zmodyfikowane kryteria podziału — takie jak entropia lub Gini obliczone dla obserwacji etykietowanych i nieetykietowanych, lub dwukryterialne cele równoważące nadzorowaną czystość z niesuperwizowaną spójnością klastrów — kierują podziałami węzłów, aby uwzględnić podstawowy rozkład danych ujawniony przez nieetykietowane punkty.

5

Iteracja trwa do momentu ustabilizowania się tymczasowych etykiet w kolejnych rundach lub osiągnięcia maksymalnej liczby iteracji. Standardowe strategie przycinania (przycinanie kosztowo-złożonościowe, minimalny rozmiar liścia) są następnie stosowane do końcowego drzewa w celu kontrolowania przeuczenia na danych pseudoetykietowanych.

Częste pułapki

  • Używanie wszystkich pseudoetykiet niezależnie od pewności, co pozwala na dominację niskiej jakości przypisań w późniejszych iteracjach.
  • Nieweryfikowanie, czy nieetykietowane dane pochodzą z tego samego rozkładu co zbiór etykietowany przed treningiem.
  • Traktowanie statystyk liści końcowego drzewa jako czysto nadzorowanych przy raportowaniu metryk wydajności — wymagana jest ocena poza próbką (out-of-bag) lub ocena na wydzielonym etykietowanym zbiorze testowym.
  • Pomijanie przycinania po augmentacji pseudoetykietami, co powoduje poważne przeuczenie na szumnych tymczasowych etykietach.
  • Bezpośrednie porównywanie z w pełni nadzorowanym drzewem wytrenowanym na tym samym etykietowanym podzbiorze, bez uwzględnienia dodatkowych użytych nieetykietowanych danych.

Najczęściej zadawane pytania

Czym drzewo decyzyjne z uczeniem częściowo nadzorowanym różni się od zwykłego klasyfikatora samo-uczącego?

Podstawowa zasada — wykorzystanie predykcji na nieetykietowanych danych do augmentacji treningu — jest taka sama. To, co odróżnia podejścia specyficzne dla drzew, to możliwość modyfikacji samego kryterium podziału w celu uwzględnienia informacji o rozkładzie nieetykietowanym, zamiast tylko iteracyjnego rozszerzania zbioru etykietowanego.

Ile etykietowanych przykładów potrzebuję na początek?

Nie ma uniwersalnego minimum, ale początkowe drzewo nadzorowane musi być wystarczająco wiarygodne, aby wygenerować użyteczne pseudoetykiety. W praktyce często zaleca się co najmniej 20-50 etykietowanych przykładów na klasę; przy mniejszej liczbie ryzyko propagacji błędów jest wysokie i alternatywne podejścia, takie jak propagacja etykiet, mogą działać lepiej.

Czy powinienem użyć wszystkich nieetykietowanych danych, czy wybrać podzbiór?

Wybieranie tylko pseudoetykiet o wysokiej pewności — na przykład tych, dla których prawdopodobieństwo liścia przekracza próg, taki jak 0,85 — zazwyczaj daje lepsze wyniki niż używanie wszystkich nieetykietowanych punktów, zwłaszcza gdy początkowe drzewo jest niedoskonałe.

Czy to zastępuje standardową walidację krzyżową?

Nie. Ponieważ pseudoetykiety są generowane przez sam model, metryki wewnątrz próbki są optymistyczne. Ocena musi wykorzystywać wydzielony etykietowany zbiór testowy lub k-krotną walidację krzyżową stosowaną ściśle do partycji etykietowanej.

Czy mogę połączyć to z metodami zespołowymi?

Tak. Lasy losowe z uczeniem częściowo nadzorowanym i podejścia współ-lasów rozszerzają tę ideę na zespoły, co może zmniejszyć wariancję błędów pseudoetykiet i zazwyczaj przewyższa pojedyncze drzewo z uczeniem częściowo nadzorowanym.

Pokrewne metody

Źródła

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

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Zhu, X. & Goldberg, A. B. (2009). Introduction to Semi-Supervised Learning. Morgan & Claypool Publishers.

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