Aktywne uczenie maszynowe z algorytmem K-najbliższych sąsiadów
- Autor metody
- Settles, B. (active learning framework); Fix & Hodges (KNN base)
- Rok
- 1951–2010
- Typ
- Active learning with KNN base learner
- Rodzina
- Machine learning
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Aktywne uczenie maszynowe z algorytmem K-najbliższych sąsiadów (KNN) łączy predykcję opartą na instancjach z iteracyjną strategią zapytań, która wybiera najbardziej informatywne nieoznaczone przykłady do adnotacji.
Model żąda etykiet tylko dla instancji, w których marginesy głosów sąsiedztwa są najwęższe, osiągając konkurencyjną dokładność przy znacznie mniejszej liczbie oznaczonych przykładów niż w pełni nadzorowany KNN na danych tabelarycznych.
Intuicja stojąca za metodą
KNN klasyfikuje punkt, analizując jego k najbliższych oznaczonych sąsiadów i przyjmując głos większości. Gdy sąsiedzi są prawie równo podzieleni między klasy, model jest autentycznie niepewny — i ta niepewność wskazuje, który nieoznaczony przykład byłby najbardziej wartościowy do oznaczenia. Aktywne uczenie wykorzystuje ten sygnał: w każdej iteracji algorytm znajduje nieoznaczony punkt, którego sąsiedztwo jest najbardziej równomiernie podzielone, prosi wyrocznię o jego oznaczenie, dodaje go do puli oznaczonych danych i powtarza proces. W rezultacie wysiłek związany z etykietowaniem koncentruje się w pobliżu granic decyzyjnych, gdzie nowe etykiety dostarczają najwięcej informacji.
Historia
Klasyfikator K-najbliższych sąsiadów wywodzi się z prac Fixa i Hodgesa (1951) i został sformalizowany przez Covera i Harta (1967). Aktywne uczenie maszynowe jako ugruntowana metodologia zostało systematycznie omówione przez Burra Settlesa (2010), który udokumentował próbkowanie niepewności oparte na puli, zapytania przez komitet i strategie ważone gęstością. KNN był wykorzystywany jako bazowy algorytm w testach aktywnego uczenia opartego na puli co najmniej od fundamentalnej pracy Cohna, Atlasa i Ladnera (1994), ceniony za przejrzysty sygnał niepewności i zerowy koszt ponownego trenowania na iterację.
Kiedy stosować
Używaj aktywnego uczenia z KNN, gdy dane oznaczone są rzadkie lub kosztowne do uzyskania, nieoznaczone instancje są liczne, przestrzeń cech ma umiarkowaną wymiarowość, a granica decyzyjna jest oczekiwana jako lokalnie gładka. Jest to szczególnie praktyczne w początkowych fazach projektów klasyfikacyjnych, gdzie etykietowanie musi być racjonowane. Unikaj go, gdy zbiór danych jest bardzo wysokowymiarowy (metryki odległości KNN pogarszają się w wysokich wymiarach, przekleństwo wymiarowości), gdy pula oznaczonych danych jest już duża (wystarczy pasywny KNN), gdy wymagana jest predykcja o niskim opóźnieniu na dużą skalę (predykcja KNN jest O(n) w zbiorze oznaczonych danych) lub gdy budżet etykiet jest tak mały, że estymacje sąsiedztwa są niewiarygodne.
Ograniczenia i uwagi
- Koszt predykcji skaluje się liniowo z rozmiarem zbioru oznaczonych danych, co spowalnia wnioskowanie w miarę wzrostu puli w kolejnych iteracjach.
- Niepewność oparta na odległości gwałtownie pogarsza się w przestrzeniach wysokowymiarowych z powodu przekleństwa wymiarowości.
- Pułap dokładności KNN jest niższy niż w przypadku metod zespołowych; strategia aktywna nie może zrekompensować ograniczonej pojemności bazowego uczącego się.
- Wrażliwy na wybór k i metryki odległości; słabe wartości domyślne prowadzą do niewiarygodnych estymacji niepewności.
- Wszystkie oznaczone punkty są przechowywane w pamięci; duże budżety skutkują wysokim zużyciem pamięci.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Nieparametryczny i wolny od założeń: nie są wymagane żadne założenia dotyczące rozkładu danych.
- Estymacja niepewności jest naturalna i interpretowalna — bezpośrednio odzwierciedla podział głosów wśród najbliższych sąsiadów.
- Leniwe uczenie oznacza brak kosztów ponownego trenowania na iterację; rozszerzony zbiór oznaczonych danych jest zaktualizowanym modelem.
- Skuteczny w koncentrowaniu etykiet w pobliżu granic decyzyjnych, co zapewnia dobrą rozdzielczość granic przy niewielkiej liczbie adnotacji.
- Dobrze sprawdza się na umiarkowanie wymiarowych danych tabelarycznych z cechami zarówno ciągłymi, jak i binarnymi.
Zastosowania
- Adnotacja dokumentacji medycznej lub obrazów, gdzie czas eksperta na etykietowanie jest ograniczony, a granice decyzyjne są lokalnie gładkie.
- Klasyfikacja tekstu lub dokumentów z małymi oznaczonymi korpusami i obfitymi nieoznaczonymi dokumentami przy użyciu odległości opartych na osadzaniu.
- Zadania wykrywania usterek w czujnikach i przemyśle, gdzie tylko ułamek zdarzeń może być ręcznie zweryfikowany.
- Badania ekologiczne, gdzie terenowe potwierdzenie etykiet gatunków jest kosztowne i lokalnie skupione.
- Wczesne prototypy klasyfikatorów przed przejściem na model o większej pojemności po zebraniu wystarczającej liczby etykiet.
Jak to działa
Jak to działa
Niewielki początkowy zestaw oznaczonych instancji jest gromadzony w celu zainicjowania procesu, wraz z większą pulą nieoznaczonych instancji. Zaleca się stratyfikowany losowy wybór, aby zapewnić obecność co najmniej jednego przykładu dla każdej klasy, co daje KNN znaczące początkowe sąsiedztwo przed rozpoczęciem aktywnej pętli.
Klasyfikator KNN jest dopasowywany do bieżącego zbioru oznaczonych danych przy użyciu wybranego k i metryki odległości (zazwyczaj euklidesowej lub cosinusowej). Ponieważ KNN jest algorytmem leniwym i przechowuje wszystkie punkty treningowe, dopasowanie jest natychmiastowe, ale koszt predykcji skaluje się liniowo z rozmiarem zbioru oznaczonych danych — co jest istotnym czynnikiem, gdy pula rośnie w kolejnych iteracjach.
Każda nieoznaczona instancja jest oceniana za pomocą kryterium informatywności. Próbkowanie marginesowe oblicza różnicę między udziałami głosów dwóch najlepszych klas wśród k sąsiadów; próbkowanie entropijne oblicza H(y-hat | x) dla wszystkich proporcji klas. Instancja z najmniejszym marginesem lub najwyższą entropią jest zapytana: x* = argmax H(y-hat | x).
Wzór
x^* = \arg\max_{x \in U} H(\hat{y} \mid x)Zapytana instancja jest wysyłana do wyroczni — ludzkiego adnotatora lub zautomatyzowanego mechanizmu etykietowania — w celu uzyskania jej prawdziwej etykiety. Etykieta jest dodawana do zbioru treningowego, a instancja jest usuwana z puli nieoznaczonych danych. Należy monitorować wiarygodność adnotatora, ponieważ zaszumione etykiety gwałtownie pogarszają wydajność KNN w pobliżu granic.
Ponieważ KNN jest algorytmem leniwym, nie jest wymagane jawne ponowne trenowanie; rozszerzony zbiór oznaczonych danych natychmiast stanowi nowy model. Cykl zapytanie-ocena-etykieta powtarza się, aż do wyczerpania budżetu etykietowania, osiągnięcia progu dokładności walidacji lub osiągnięcia maksymalnej liczby iteracji. Ostateczna wydajność jest raportowana na niezależnym, odłożonym zbiorze testowym.
Częste pułapki
- Brak normalizacji cech przed obliczeniem odległości, co powoduje, że cechy o dużej wartości dominują w sąsiedztwie.
- Używanie zbioru testowego do kierowania lub oceny wyboru zapytań, co stanowi wyciek danych.
- Ustawienie zbyt małego k (k=1) w pobliżu granicy decyzyjnej, co prowadzi do bardzo zmiennych wyników niepewności, które nie odzwierciedlają prawdziwej dwuznaczności.
- Ignorowanie braku równowagi klas w zbiorze początkowym, co prowadzi do stronniczości wczesnych zapytań w kierunku granic klasy większościowej.
- Traktowanie dokładności aktywnego uczenia jako równoważnej z w pełni nadzorowaną linią bazową bez raportowania użytej liczby etykiet.
Najczęściej zadawane pytania
Dlaczego używać KNN zamiast potężniejszego modelu jako podstawy aktywnego uczenia?
Niepewność podziału głosów w KNN jest tania w obliczeniu i nie wymaga ponownego trenowania — dodanie nowego oznaczonego punktu natychmiast aktualizuje model. To sprawia, że jest atrakcyjny, gdy liczy się koszt obliczeniowy na iterację. Dla maksymalnej dokładności przy stałym budżecie etykiet, bazowe algorytmy zespołowe, takie jak las losowy lub wzmacnianie gradientowe, zazwyczaj przewyższają KNN.
Jak wybrać k dla aktywnego uczenia?
Często stosowany zakres początkowy to k = 5 do 15. Mniejsze wartości k dają bardziej zaszumione estymacje niepewności; większe wartości k wygładzają granicę, ale mogą pomijać subtelne dwuznaczności. Przeprowadź walidację krzyżową k na początkowym zbiorze oznaczonych danych i dostosuj je w miarę wzrostu puli oznaczonych danych.
Czy skalowanie cech ma znaczenie?
Tak, krytyczne. Odległość KNN jest zdominowana przez cechy o dużej wartości, jeśli cechy nie są znormalizowane. Zawsze stosuj skalowanie min-max lub standaryzację z-score przed obliczeniem odległości i wyników niepewności.
Ile początkowych oznaczonych przykładów jest potrzebnych?
Minimalnie wymagana jest jedna lub dwie oznaczone instancje na klasę, aby KNN mógł utworzyć sąsiedztwa dla wszystkich klas. W praktyce 5–20 oznaczonych instancji zapewnia bardziej stabilne początkowe estymacje niepewności; mniej ryzykują zdegenerowane sąsiedztwa, które generują nieinformatywne wczesne zapytania.
Kiedy powinienem zatrzymać aktywną pętlę?
Ustaw budżet etykietowania z góry lub monitoruj dokładność walidacji i zatrzymaj się, gdy poprawa na nową etykietę spadnie poniżej znaczącego progu. Nigdy nie używaj zbioru testowego jako sygnału zatrzymania, ponieważ to powoduje wyciek informacji do procesu zapytań.
Pokrewne metody
Źródła
Settles, B. (2010). Active Learning Literature Survey. Computer Sciences Technical Report 1648, University of Wisconsin-Madison.
Otwórz odnośnik do publikacjiSkopiowano.Zhu, X., Lafferty, J., & Ghahramani, Z. (2003). Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions. Proceedings of the ICML 2003 Workshop on the Continuum from Labeled to Unlabeled Data, 58–65.
Otwórz odnośnik do publikacjiSkopiowano.