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

Półnadzorowana maszyna wektorów nośnych

Autor metody
Joachims, T.
Rok
1999
Typ
Semi-supervised classifier
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?

Półnadzorowana maszyna wektorów nośnych (S3VM) rozszerza klasyczną SVM poprzez włączenie dużej ilości danych nieetykietowanych obok małego zbioru treningowego danych etykietowanych.

Dąży ona do znalezienia hiperpłaszczyzny o maksymalnym marginesie, która nie tylko rozdziela przykłady etykietowane, ale także przechodzi przez obszary o niskiej gęstości pełnego rozkładu danych, co prowadzi do lepszej generalizacji, gdy próbki etykietowane są rzadkie.

Intuicja stojąca za metodą

Standardowa SVM uczy się granicy wyłącznie na podstawie punktów etykietowanych. S3VM obserwuje, że nieetykietowane dane nadal niosą informację geometryczną o tym, gdzie skupiska danych są gęste, a gdzie rzedną. Wymagając, aby granica decyzyjna unikała obszarów o wysokiej gęstości — niezależnie od tego, czy punkty te mają etykiety, czy nie — model może wykorzystać nieetykietowaną większość do wyostrzenia granicy, którą w przeciwnym razie narysowałby na podstawie garstki samych etykietowanych przykładów. Wynikiem jest margines, który uwzględnia podstawową strukturę danych, a nie tylko znane etykiety.

Historia

Podstawy S3VM zostały położone przez Vapnika w jego wczesnych pracach nad wnioskowaniem transdukcyjnym, ale metoda zyskała szerokie zastosowanie po tym, jak Joachims (1999) zademonstrował jej skuteczność w klasyfikacji tekstu pod nazwą Transductive SVM. Kompleksowe omówienie w Chapelle, Scholkopf i Zien (2006) skonsolidowało S3VM obok innych podejść półnadzorowanych i pozostaje standardowym odniesieniem. Kolejne prace wprowadziły wypukłe relaksacje i skalowalne solvery, aby rozwiązać problemy obliczeniowe i lokalnych optimów oryginalnej metody.

Kiedy stosować

S3VM jest właściwym wyborem, gdy dane etykietowane są drogie lub rzadkie (np. mniej niż kilkaset przykładów), ale dostępne są obfite dane nieetykietowane — co jest częstym scenariuszem w klasyfikacji tekstu, bioinformatyce lub w każdej dziedzinie, gdzie anotacja jest kosztowna. Działa najlepiej, gdy założenie o klastrach jest spełnione: klasy tworzą odrębne skupiska, a granica decyzyjna leży w obszarze o niskiej gęstości. Unikaj S3VM, gdy dane etykietowane są już obfite (standardowa SVM dorówna lub przewyższy ją przy niższych kosztach), gdy założenie o klastrach jest naruszone (klasy mocno się nakładają w przestrzeni cech) lub gdy rozkład nieetykietowany dryfuje od rozkładu etykietowanego, co może skierować granicę w złym kierunku.

Ograniczenia i uwagi

  • Optymalizacja jest niewypukła z powodu pseudo-etykiet, co czyni ją wrażliwą na inicjalizację i podatną na lokalne optima.
  • Koszt obliczeniowy słabo skaluje się z liczbą przykładów nieetykietowanych — duże pule nieetykietowane stają się kosztowne.
  • Opiera się na założeniu o klastrach; jeśli klasy nie tworzą dobrze rozseparowanych skupisk, dane nieetykietowane mogą pogorszyć wydajność.
  • Wymaga starannego dostrojenia wagi straty na danych etykietowanych C i wagi straty na danych nieetykietowanych C*, co zwiększa złożoność wyboru modelu.

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

Mocne strony

  • Skutecznie wykorzystuje duże zbiory danych nieetykietowanych do poprawy generalizacji, gdy przykłady etykietowane są rzadkie.
  • Dziedziczy gwarancje maksymalnego marginesu i elastyczność jądra (kernel) standardowych SVM.
  • Dobrze nadaje się do danych o wysokiej wymiarowości i rzadkich, takich jak tekst, gdzie korpusy nieetykietowane są obfite.
  • Istnieją ugruntowane probabilistycznie rozszerzenia (Gaussian Process S3VM) i warianty jądrowe dla nieliniowych granic.
  • Konkurencyjna dokładność w reżimach z małą ilością danych etykietowanych w porównaniu z czysto nadzorowanymi alternatywami.

Zastosowania

  • Klasyfikacja tekstów i dokumentów przy niewielkiej liczbie etykietowanych przykładów treningowych.
  • Zadania bioinformatyczne, takie jak przewidywanie funkcji białek, gdzie anotacja eksperymentalna jest kosztowna.
  • Kategoryzacja stron internetowych z wykorzystaniem dużych, zaindeksowanych, ale nieanotowanych korpusów.
  • Analiza obrazów medycznych, gdzie etykietowanie przez ekspertów jest czasochłonne i kosztowne.
  • Każdy problem klasyfikacji o wysokiej wymiarowości z obfitymi danymi nieetykietowanymi i rzadkimi etykietami.

Jak to działa

Jak to działa

1

Wstępna SVM jest dopasowywana do dostępnych przykładów etykietowanych, ucząc się wstępnej granicy decyzyjnej i marginesu. Stanowi to model początkowy i wstępne predykcje dla puli nieetykietowanej, ugruntowując późniejszą optymalizację półnadzorowaną w rozwiązaniu nadzorowanym.

2

Wstępna SVM przypisuje tymczasowe etykiety klas (pseudo-etykiety) wszystkim nieetykietowanym przykładom na podstawie tego, po której stronie obecnej granicy się znajdują. Te pseudo-etykiety pozwalają punktom nieetykietowanym uczestniczyć w maksymalizacji marginesu, mimo że ich prawdziwa klasa jest nieznana.

3

Główny cel S3VM wspólnie minimalizuje stratę zawiasową (hinge loss) na przykładach etykietowanych i pseudo-stratę zawiasową na przykładach nieetykietowanych, jednocześnie maksymalizując margines. Parametr równoważący C* kontroluje, jak silnie punkty nieetykietowane wpływają na granicę, balansując między wykorzystaniem struktury w danych nieetykietowanych a dopasowaniem do prawdziwych danych etykietowanych.

Wzór
\min_{w,b,y^*} \frac{1}{2}\|w\|^2 + C\sum_{i}\xi_i + C^*\sum_{j}\xi_j^*
4

Ponieważ pseudo-etykiety mogą być błędne, algorytm iteruje: ponownie przypisuje pseudo-etykiety przy użyciu zaktualizowanej granicy i ponownie rozwiązuje wspólną optymalizację. Zamiana błędnie przypisanych przykładów nieetykietowanych na przeciwną klasę i ponowna optymalizacja stopniowo przesuwają granicę w luki o niższej gęstości w danych.

5

Po osiągnięciu zbieżności nowe przykłady są klasyfikowane przez znak nauczonej liniowej funkcji decyzyjnej. Wynikowa hiperpłaszczyzna jest umieszczona w obszarze o niskiej gęstości pełnego rozkładu danych, co zapewnia lepszą generalizację na przykładach odłożonych na bok niż czysto nadzorowana SVM wytrenowana na tym samym małym zbiorze etykietowanym.

Wzór
f(x) = \text{sign}(w^\top x + b)

Częste pułapki

  • Zakładając, że dane nieetykietowane zawsze pomagają — jeśli założenie o klastrach jest naruszone, S3VM może działać gorzej niż nadzorowana SVM.
  • Używanie bardzo dużego C* w stosunku do C, nadmiernie ważąc punkty nieetykietowane i pozwalając granicy oddalić się od sygnału etykietowanego.
  • Zaniechanie walidacji na odłożonym zbiorze etykietowanym, co uniemożliwia wykrycie, kiedy dane nieetykietowane zaszkodziły wydajności.
  • Stosowanie S3VM, gdy dane etykietowane i nieetykietowane pochodzą z różnych rozkładów (przesunięcie kowariancji), co narusza założenia metody.

Najczęściej zadawane pytania

Czym S3VM różni się od standardowej SVM?

Standardowa SVM wykorzystuje tylko dane etykietowane do umieszczenia swojej granicy decyzyjnej. S3VM dodatkowo włącza przykłady nieetykietowane, wymagając, aby granica przechodziła przez obszary o niskiej gęstości pełnego rozkładu danych, poprawiając generalizację, gdy dane etykietowane są rzadkie.

Czym jest założenie o klastrach i dlaczego jest ważne?

Założenie o klastrach stwierdza, że granica decyzyjna leży w obszarze niskiej gęstości danych, co oznacza, że klasy tworzą rozdzielne skupiska. S3VM wykorzystuje to, kierując granicę z dala od obszarów gęstych. Jeśli klasy mocno się nakładają, to założenie zawodzi, a dane nieetykietowane mogą wprowadzić model w błąd.

Jak wybrać wagę dla danych nieetykietowanych C*?

C* kontroluje, jak silnie przykłady nieetykietowane wpływają na margines. Powszechną strategią jest rozpoczęcie od C* znacznie mniejszego niż C i stopniowe zwiększanie go przy jednoczesnym monitorowaniu dokładności walidacji na małym odłożonym zbiorze etykietowanym, zatrzymując się przed pogorszeniem wydajności.

Czy S3VM może obsługiwać nieliniowe granice?

Tak. Podobnie jak standardowe SVM, S3VM obsługuje funkcje jądra (RBF, wielomianowe itp.), które niejawnie mapują dane do przestrzeni o wyższym wymiarze, gdzie liniowa granica staje się nieliniowa w oryginalnej przestrzeni cech.

Kiedy powinienem wybrać self-training lub propagację etykiet zamiast S3VM?

Self-training jest prostszy w implementacji i lepiej skaluje się do dużych pul nieetykietowanych; wybierz go, gdy zasoby obliczeniowe są ograniczone. Propagacja etykiet działa dobrze na danych o strukturze grafu. S3VM jest preferowany, gdy chcesz gwarancji maksymalnego marginesu i założenie o klastrach jest prawdopodobnie spełnione.

Pokrewne metody

Źródła

  1. Joachims, T. (1999). Transductive Inference for Text Classification using Support Vector Machines. Proceedings of the 16th International Conference on Machine Learning (ICML), 200–209.

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

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