11 · Prawa i prawdy · 3 min czytania · Interaktywne · aktualizacja
Dlaczego dodawanie cech może pogorszyć klasyfikator przy małej liczbie danych?
W skrócie
Przy stałej liczbie przykładów dokładność klasyfikatora najpierw rośnie z liczbą cech, a potem spada, bo parametrów do oszacowania przybywa szybciej niż danych.
Co to jest
Przy ustalonej liczbie przykładów treningowych dokładność klasyfikatora rośnie wraz z liczbą cech tylko do pewnego punktu, a potem zaczyna spadać. Zjawisko opisał Gordon F. Hughes w 1968 roku w pracy o średniej dokładności statystycznych klasyfikatorów; nazywa się je też efektem szczytowania (peaking).
Paradoks polega na tym, że każda nowa cecha teoretycznie nie może zaszkodzić: klasyfikator idealny, znający prawdziwe rozkłady, z dodatkowej informacji zawsze skorzysta albo ją zignoruje. Problem w tym, że my tych rozkładów nie znamy — musimy je oszacować z danych. Każda cecha to dodatkowe parametry do oszacowania z tej samej skromnej próbki.
Szczyt przesuwa się w prawo, gdy danych przybywa. Przy dużych zbiorach można więc bezpiecznie używać wielu cech; przy małych optymalna liczba cech bywa zaskakująco mała.
Mechanizm — dlaczego tak działa
Zysk z nowej cechy to dodatkowa informacja o klasie. Koszt to błąd oszacowania: klasyfikator gaussowski z d cechami musi oszacować d średnich na klasę i około d²/2 kowariancji. Gdy d zbliża się do liczby przykładów na klasę, macierz kowariancji staje się źle uwarunkowana lub osobliwa, a oszacowania — przypadkowe.
Pierwsze cechy zwykle niosą najwięcej informacji, więc zysk maleje z każdą kolejną, a koszt rośnie. W pewnym momencie krańcowy koszt przewyższa krańcowy zysk — to jest szczyt. G. V. Trunk w 1979 roku pokazał prosty przykład: dwie klasy gaussowskie, w których każda kolejna cecha jest coraz mniej informatywna; przy znanych parametrach błąd spada do zera, przy szacowanych — rośnie do 50%.
Zjawisko jest silne dla modeli, które szacują wiele parametrów bez regularyzacji (LDA, QDA, pełna kowariancja), i słabsze dla modeli z wbudowaną kontrolą złożoności (regresja z karą, drzewa z ograniczeniami, naiwny Bayes z niewielką liczbą parametrów na cechę). Nie jest więc sztywnym prawem dla każdego algorytmu, tylko ostrzeżeniem o relacji „cechy kontra dane”.
Na przykładzie
Zbiór Wine: 178 win, 3 odmiany, 13 cech chemicznych. Losowaliśmy mały zbiór treningowy, dokładaliśmy cechy w ustalonej losowej kolejności i mierzyliśmy dokładność LDA na pozostałych winach (średnia z 200 losowań).
Przy 15 przykładach treningowych (5 na odmianę) dokładność rośnie od 0,44 dla jednej cechy do szczytu 0,86 przy siedmiu cechach, po czym spada: 0,82 przy dziesięciu i 0,69 przy dwunastu. Przy 30 przykładach szczyt przypada na 10 cech (0,95), a spadek przy 13 jest już mały (0,93). Przy 60 przykładach — szczyt 0,975 przy dziesięciu cechach i ledwo zauważalny spadek do 0,97. Te same cechy, ta sama metoda: im mniej danych, tym wcześniej i boleśniej dodatkowe cechy zaczynają szkodzić.
Dane: Wine (wina z Piemontu)
W praktyce
- Przy małych zbiorach licz cechy w stosunku do przykładów; dla LDA/QDA kilka–kilkanaście przykładów na cechę w każdej klasie to rozsądne minimum.
- Używaj regularyzacji kowariancji:
LinearDiscriminantAnalysis(solver='lsqr', shrinkage='auto'). - Selekcję cech (
SelectKBest,RFECV) wykonuj wewnątrz walidacji krzyżowej, wPipeline. - Zamiast wyrzucać cechy, możesz je skompresować (
PCA) — mniej parametrów, większość informacji. - Wykres „dokładność vs liczba cech” rób na kilku podziałach danych; pojedynczy podział przy małym n jest bardzo szumny.
Najczęstsze pytania
- Czy zjawisko Hughesa występuje w głębokim uczeniu?
- W czystej postaci rzadko, bo sieci uczy się na dużych zbiorach z regularyzacją, a cechy wyprowadza sam model. Wraca jednak przy małych zbiorach tabelarycznych i w obrazowaniu hiperspektralnym, gdzie pasm jest więcej niż oznaczonych pikseli.
- Skąd wiedzieć, gdzie jest szczyt?
- Empirycznie: krzywa walidacyjna dokładności w funkcji liczby cech, policzona w walidacji krzyżowej. Teoretycznie szczyt zależy od modelu, rozkładu informacji między cechami i liczby przykładów.
- Czy to ten sam problem co przeuczenie?
- To jego szczególny przypadek: złożoność modelu rośnie tu przez liczbę cech. Mechanizm jest ten sam — więcej parametrów do oszacowania niż dane są w stanie unieść.
Źródła
- Hughes G. F. (1968). On the Mean Accuracy of Statistical Pattern Recognizers. IEEE Transactions on Information Theory, 14(1), 55–63.
- Trunk G. V. (1979). A Problem of Dimensionality: A Simple Example. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1(3), 306–307.
- Duda R. O., Hart P. E., Stork D. G. (2001). Pattern Classification, 2nd ed. Wiley, rozdz. 3.7.
- Hastie T., Tibshirani R., Friedman J. (2009). The Elements of Statistical Learning, 2nd ed. Springer, rozdz. 4.3.