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

Propagacja etykiet

Autor metody
Zhu, X. & Ghahramani, Z.
Rok
2002
Typ
Graph-based semi-supervised classification

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

Rozmiar czcionki

Do czego służy?

Propagacja etykiet (Label Propagation) to algorytm uczenia maszynowego z częściowym nadzorem (semi-supervised learning), oparty na grafach, wprowadzony przez Zhu i Ghahramani w 2002 roku.

Rozprowadza on etykiety klas z niewielkiego zbioru węzłów oznakowanych do dużej liczby węzłów nieoznakowanych poprzez iteracyjne dyfuzję informacji o etykietach wzdłuż krawędzi grafu podobieństwa, wykorzystując strukturę rozmaitości (manifold structure) danych.

Intuicja stojąca za metodą

Wyobraźmy sobie sieć społeczną, w której kilku osobom przypisano już pewną kategorię. Plotka rozchodzi się naturalnie: każda osoba ma tendencję do przyjmowania etykiety najczęściej występującej wśród jej bliskich sąsiadów. Propagacja etykiet formalizuje tę intuicję — buduje ważony graf, w którym podobne punkty danych są połączone silnymi krawędziami, a następnie pozwala znanym etykietom płynąć krok po kroku, aż każdy nieoznakowany punkt wchłonie wystarczająco dużo sygnału, aby zostać sklasyfikowanym. Ponieważ dyfuzja podąża za geometrią danych, a nie arbitralnymi granicami decyzyjnymi, może ona dawać bardzo dokładne predykcje, nawet gdy oznakowanych przykładów jest niewiele.

Historia

Xiaojin (Jerry) Zhu i Zoubin Ghahramani wprowadzili Propagację Etykiet w raporcie technicznym Carnegie Mellon University z 2002 roku (CMU-CALD-02-107). Rok później Zhu, Ghahramani i John Lafferty opublikowali blisko powiązane ramy pól Gaussa i funkcji harmonicznych na konferencji ICML 2003, dostarczając probabilistyczną interpretację poprzez losowe spacery i Gaussa-markowskie pola losowe. Prace te zapoczątkowały falę grafowych metod uczenia maszynowego z częściowym nadzorem w połowie lat 2000. Dengyong Zhou i współpracownicy zaproponowali w 2004 roku Propagację Etykiet (Label Spreading) — wariant z regularyzacją, który pozwala informacji o etykietach częściowo nadpisywać przycięte etykiety, oferując odporność na szum w anotacjach. Obie metody są obecnie standardowymi punktami odniesienia w benchmarkach uczenia maszynowego z częściowym nadzorem i są zawarte w powszechnie używanych bibliotekach uczenia maszynowego. Wraz z pojawieniem się grafowych sieci neuronowych w latach 2010., Propagacja Etykiet stała się koncepcyjnym prekursorem i konkurencyjnym punktem odniesienia, nadal cytowanym za swoją prostotę i gwarancje rozwiązania w postaci zamkniętej.

Kiedy stosować

Propagacja etykiet jest odpowiednia, gdy oznakowanych przykładów jest niewiele w stosunku do całkowitego rozmiaru zbioru danych, dane mają podstawową strukturę klastra lub rozmaitości, którą może uchwycić graf podobieństwa, i istnieją powody, by sądzić, że założenie o gładkości (smoothness assumption) jest spełnione — że bliskie punkty (w przestrzeni cech) mają tendencję do dzielenia tej samej etykiety. Typowe scenariusze obejmują kategoryzację tekstu z niewielką liczbą anotowanych dokumentów, klasyfikację obrazów z rzadkimi ludzkimi etykietami oraz klasyfikację węzłów sieci. Metoda wymaga, aby graf był spójny (lub przynajmniej aby każdy nieoznakowany węzeł był osiągalny z oznakowanego węzła). Nie nadaje się, gdy przestrzeń cech nie odzwierciedla podobieństwa semantycznego, gdy granica decyzyjna przecina gęste regiony, lub gdy wszystkie dane są już oznakowane.

Ograniczenia i uwagi

  • Skalowalność: przechowywanie i operowanie na macierzy wag n x n jest niewykonalne dla dużych zbiorów danych bez aproksymacji rzadkich macierzy.
  • Konstrukcja grafu jest wrażliwa na wybór szerokości pasma jądra sigma i rozmiaru sąsiedztwa k; złe wybory znacząco obniżają dokładność.
  • Zakłada założenie o gładkości (klastrowaniu): jego naruszenie — gdy granice decyzyjne przechodzą przez gęste regiony — prowadzi do systematycznych błędnych klasyfikacji.
  • Domyślnie transdukcyjna: predykcje dla nowych, nieznanych punktów testowych wymagają ponownego uruchomienia algorytmu lub rozszerzenia indukcyjnego.
  • Szum etykiet na niewielu oznakowanych węzłach propaguje się i może zanieczyścić dużą część grafu.

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

Mocne strony

  • Efektywnie wykorzystuje dane nieoznakowane, zapewniając wysoką dokładność przy bardzo niewielu oznakowanych przykładach.
  • Gwarancja zbieżności do rozwiązania w postaci zamkniętej: iteracyjna aktualizacja zawsze osiąga unikalny punkt stały.
  • Naturalnie obsługuje problemy wieloklasowe bez modyfikacji.
  • Intuicyjna interpretacja geometryczna oparta na dyfuzji grafów i analizie harmonicznej.
  • Brak parametrów modelu do optymalizacji poza wyborami dotyczącymi konstrukcji grafu (szerokość pasma jądra, rozmiar sąsiedztwa).

Zastosowania

  • Klasyfikacja tekstów i dokumentów, gdy tylko niewielka część dokumentów zawiera etykiety przypisane przez człowieka.
  • Anotacja obrazów lub wideo, gdzie ręczne etykietowanie jest kosztowne, a nieoznakowane obrazy są liczne.
  • Klasyfikacja węzłów w sieciach społecznościowych i grafach cytowań (np. wnioskowanie o zainteresowaniach użytkowników lub tematach artykułów).
  • Bioinformatyka: przewidywanie funkcji genów lub ról interakcji białek na podstawie częściowo anotowanych sieci biologicznych.
  • Wykrywanie anomalii z częściowym nadzorem poprzez propagację znanych etykiet normalnych/anomalnych przez graf podobieństwa.

Jak to działa

Jak to działa

1

Buduje się ważony graf podobieństwa obejmujący wszystkie n punktów danych — zarówno oznakowanych, jak i nieoznakowanych. Powszechnym wyborem jest jądro Gaussa (RBF): waga krawędzi W_ij jest malejącą funkcją kwadratu odległości euklidesowej między punktami i oraz j, kontrolowaną przez parametr szerokości pasma sigma. Zachowuje się tylko k najbliższych sąsiadów lub sąsiadów w promieniu epsilon, aby graf pozostał rzadki.

Wzór
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

Macierz wag W jest normalizowana kolumnowo, aby uzyskać macierz przejścia T o sumie wierszowej równej jeden (row-stochastic), gdzie każdy element T_ij reprezentuje prawdopodobieństwo przepływu informacji o etykiecie z węzła j do węzła i. Zapewnia to, że całkowity wpływ otrzymany przez każdy węzeł sumuje się do jednego.

Wzór
T_{ij} = \frac{W_{ij}}{\sum_k W_{kj}}
3

Algorytm rozpoczyna się od początkowej macierzy etykiet F (jedna kolumna na klasę) i iteruje: mnoży F przez T, a następnie przycina wiersze odpowiadające oznakowanym węzłom z powrotem do ich prawdziwych etykiet one-hot Y_L. To przycinanie zapobiega dryfowaniu znanych etykiet i działa jako warunek brzegowy absorbujący. Iteracje powtarza się do momentu zbieżności nieoznakowanych wpisów F.

Wzór
F^{(t+1)} = T F^{(t)}, \quad F_L = Y_L \text{ (clamp labeled rows after each step)}
4

Rozwiązanie w punkcie stałym dla nieoznakowanego bloku F_U* jest dane w postaci zamkniętej jako (I - T_UU)^{-1} T_UL Y_L, gdzie T_UU jest podmacierzą przejść między nieoznakowanymi węzłami, a T_UL przechwytuje przejścia z węzłów oznakowanych do nieoznakowanych. W praktyce wersja iteracyjna jest preferowana dla dużych grafów, ponieważ pozwala uniknąć odwracania macierzy; obie ścieżki dają to samo unikalne rozwiązanie.

Wzór
F_U^* = (I - T_{UU})^{-1} T_{UL} Y_L

Częste pułapki

  • Użycie w pełni połączonego grafu bez rzadkości, co zaciemnia lokalną strukturę i jest obliczeniowo niewykonalne w dużej skali.
  • Wybór domyślnego sigma bez walidacji krzyżowej na zbiorze oznakowanym, co prowadzi do nadmiernego lub niedostatecznego wygładzenia rozkładów etykiet.
  • Ignorowanie niezbalansowania klas: jeśli jedna klasa dominuje w zbiorze oznakowanym, jej etykieta zalewa graf; potrzebne jest ponowne ważenie lub próbkowanie.
  • Traktowanie predykcji transdukcyjnych jako wytrenowanego modelu i stosowanie ich do nowych punktów bez opakowania indukcyjnego.
  • Niesprawdzenie spójności grafu: nieoznakowane węzły w izolowanych komponentach nie otrzymują sygnału i przyjmują domyślnie równomierne prawdopodobieństwa klas.

Najczęściej zadawane pytania

Jaka jest różnica między Propagacją Etykiet a Propagacją Etykiet (Label Spreading)?

Propagacja Etykiet (Label Spreading), zaproponowana przez Zhou i współpracowników (2004), wprowadza parametr regularyzacji alpha, który kontroluje, w jakim stopniu każdy węzeł zachowuje swoją początkową etykietę w porównaniu do przyjmowania etykiet swoich sąsiadów. W klasycznej Propagacji Etykiet oznakowane węzły są sztywno przycinane, co czyni je w pełni absorbującymi. Propagacja Etykiet (Label Spreading) pozwala na częściowe nadpisywanie oznakowanych węzłów, co czyni ją bardziej odporną na szum etykiet kosztem jednego dodatkowego hiperparametru.

Czy Propagacja Etykiet skaluje się do dużych zbiorów danych?

Naiwne rozwiązanie w postaci zamkniętej wymaga odwrócenia macierzy (n_U x n_U), co jest niewykonalne dla dużego n. W praktyce, rzadki graf k-najbliższych sąsiadów lub graf o promieniu epsilon redukuje pamięć do O(nk), a następnie iteracyjna aktualizacja skaluje się w przybliżeniu liniowo z liczbą krawędzi na iterację. Dla bardzo dużych grafów stosuje się metody przybliżonych najbliższych sąsiadów i warianty mini-batch.

Ile oznakowanych przykładów jest potrzebnych?

Propagacja Etykiet jest specjalnie zaprojektowana dla ekstremalnego reżimu z małą liczbą etykiet. Nawet pojedynczy oznakowany węzeł na klasę może dać znaczące predykcje, jeśli struktura grafu jest zgodna z granicami klas, chociaż posiadanie co najmniej kilku oznakowanych przykładów na klasę jest zdecydowanie zalecane dla niezawodności. Wydajność spada wraz ze wzrostem szumu etykiet lub gdy graf staje się mniej informatywny o przynależności do klasy.

Czy Propagacja Etykiet może przewidywać dla nowych, nieznanych punktów danych?

W swojej standardowej formie transdukcyjnej, nie — algorytm działa na ustalonym grafie i nie ma mechanizmu przewidywania poza tym grafem. Do użytku indukcyjnego, powszechnym podejściem jest połączenie nowych punktów z ich k-najbliższymi sąsiadami w istniejącym grafie i uruchomienie częściowego kroku propagacji, lub użycie zbieżnej macierzy etykiet do wytrenowania standardowego klasyfikatora nadzorowanego jako drugiego etapu.

Pokrewne metody

Źródła

  1. Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the 20th International Conference on Machine Learning (ICML-2003), pp. 912–919.

    Otwórz odnośnik do publikacji
    Skopiowano.
  3. Chapelle, O., Scholkopf, B., & Zien, A. (Eds.) (2006). Semi-Supervised Learning. MIT Press.

    ISBN: 978-0-262-03358-9
    Skopiowano.