SVM, Nadmierne dopasowanie, przekleństwo wymiarowości

37

Mój zestaw danych jest niewielki (120 próbek), jednak liczba funkcji jest duża i waha się od (1000-200 000). Chociaż dokonuję wyboru funkcji, aby wybrać podzbiór funkcji, może się ona nadal nadpisywać.

Moje pierwsze pytanie brzmi: w jaki sposób SVM radzi sobie z nadmiernym dopasowaniem, jeśli w ogóle.

Po drugie, kiedy studiuję więcej na temat nadmiernego dopasowania w przypadku klasyfikacji, doszedłem do wniosku, że nawet zestawy danych z małą liczbą funkcji mogą się pokrywać. Jeśli nie mamy funkcji skorelowanych z etykietą klasy, to i tak występuje nadmierne dopasowanie. Zastanawiam się teraz, jaki jest sens automatycznej klasyfikacji, jeśli nie możemy znaleźć odpowiednich funkcji dla etykiety klasy. W przypadku klasyfikacji dokumentów oznaczałoby to ręczne przygotowanie tezaurusa słów, które odnoszą się do etykiet, co jest bardzo czasochłonne. Myślę, że próbuję powiedzieć, że bez ręcznego wyboru odpowiednich funkcji bardzo trudno jest zbudować model uogólniony?

Ponadto, jeśli wyniki eksperymentów nie wykażą, że wyniki mają niskie / brak przeregulowania, staje się bez znaczenia. Czy istnieje sposób, aby to zmierzyć?

użytkownik13420
źródło

Odpowiedzi:

41

W praktyce powodem, dla którego SVM są odporne na nadmierne dopasowanie, nawet w przypadkach, gdy liczba atrybutów jest większa niż liczba obserwacji, jest to, że stosuje regularyzację. Kluczem do uniknięcia nadmiernego dopasowania jest staranne dostrajanie parametru regularyzacji, , aw przypadku nieliniowych maszyn SVM, ostrożny wybór jądra i dostrajanie parametrów jądra.C

SVM jest przybliżoną implementacją ograniczenia błędu generalizacji, który zależy od marginesu (zasadniczo odległość od granicy decyzji do najbliższego wzorca z każdej klasy), ale jest niezależny od wymiarów przestrzeni cech (dlatego użycie sztuczki jądra do zmapowania danych w przestrzeń o bardzo dużych wymiarach nie jest takim złym pomysłem, jak mogłoby się wydawać). Zatem w zasadzie maszyny SVM powinny być wysoce odporne na nadmierne dopasowanie, ale w praktyce zależy to od starannego wyboru i parametrów jądra. Niestety, nadmierne dopasowanie może również wystąpić dość łatwo przy dostrajaniu hiper-parametrów, co jest moim głównym obszarem badań, patrzC

GC Cawley i NLC Talbot, Zapobieganie nadmiernemu dopasowaniu w wyborze modelu poprzez bayesowską regularyzację hiperparametrów, Journal of Machine Learning Research, tom 8, strony 841-861, kwiecień 2007. ( www )

i

GC Cawley i NLC Talbot, Nadmierne dopasowanie w wyborze modelu i późniejsze odchylenie wyboru w ocenie wydajności, Journal of Machine Learning Research, 2010. Research, vol. 11, s. 2079–2107, lipiec 2010 r. ( Www )

Oba te dokumenty używają regresji grzbietu jądra, a nie SVM, ale ten sam problem pojawia się równie łatwo z SVM (również podobne ograniczenia dotyczą KRR, więc w praktyce nie ma wiele do wyboru). W pewnym sensie maszyny SVM tak naprawdę nie rozwiązują problemu nadmiernego dopasowania, po prostu przenoszą problem z dopasowania modelu do wyboru modelu.

Często jest pokusa, aby ułatwić sobie życie SVM, dokonując najpierw wyboru funkcji. Zasadniczo pogarsza to sytuację, ponieważ w przeciwieństwie do SVM, algorytmy wyboru cech wykazują tendencję do nadmiernego dopasowania w miarę wzrostu liczby atrybutów. O ile nie chcesz wiedzieć, jakie są atrybuty informacyjne, zwykle lepiej jest pominąć krok wyboru funkcji i po prostu użyć regularyzacji, aby uniknąć nadmiernego dopasowania danych.

Krótko mówiąc, nie ma nieodłącznego problemu z użyciem SVM (lub innego modelu regulowanego, takiego jak regresja kalenicy, LARS, Lasso, siatka elastyczna itp.) Na problemie ze 120 obserwacjami i tysiącami atrybutów, pod warunkiem, że parametry regularyzacji są odpowiednio dostrojone .

Dikran Torbacz
źródło
Czy są jakieś dokumenty pokazujące metody wyboru funkcji, takie jak ranking oparty na zdobywaniu informacji, które są bardziej skłonne do nadpisania?
user13420,
1
Nie wiem o tym, chodziło o to, że SVM ma pewne teoretyczne wyniki, które sugerują, że są odporne na nadmierne dopasowanie ze względu na liczbę atrybutów, ale metody wyboru cech nawet tego nie mają. FWIW, monografia Millera na temat „wyboru podzbioru w regresji” zaleca stosowanie metod regularyzacji, jeśli wymagana jest wydajność predykcyjna. Odnotowano kilka otwartych na wyzwania wyboru funkcji, które sugerują, że uregulowanie osiąga lepsze wyniki selekcji cech (patrz nipsfsc.ecs.soton.ac.uk i causality.inf.ethz.ch/challenge.php ).
Dikran Marsupial
Jak stwierdzono w akapicie pierwszym, maszyny SVM mają tendencję do bycia odpornym na nadmierne dopasowanie, czy wykorzystuje regularyzację (parametr C) , więc domyślnie svmczy parametry regularyzacji C ? I nie jestem pewien, jakie zmienne kontrolowane przez to C , masz na myśli te zmienne luźne ?
awokado
10

Zacznę od drugiego i ostatniego pytania.

Problem uogólnienia jest oczywiście ważny, ponieważ jeśli wyników uczenia maszynowego nie można uogólnić, to są one całkowicie bezużyteczne.

Metody zapewniania uogólnienia pochodzą ze statystyk. Zazwyczaj zakładamy, że dane są generowane z pewnego rozkładu prawdopodobieństwa, który pochodzi z rzeczywistości. Na przykład, jeśli jesteś mężczyzną urodzonym w 2000 roku, istnieje rozkład prawdopodobieństwa, jaka jest twoja waga / wzrost / kolor oczu po osiągnięciu 10, co wynika z dostępnej puli genów w 2000 roku, możliwych czynników środowiskowych itp. mamy wiele danych, możemy powiedzieć coś o tych podstawowych rozkładach, na przykład że z dużym prawdopodobieństwem są one gaussowskie lub wielomianowe. Jeśli mamy dokładny obraz rozkładów, a następnie biorąc pod uwagę wzrost, wagę i kolor oczu 10-letniego dziecka w 2010 roku, możemy uzyskać dobre przybliżenie prawdopodobieństwa, że ​​dziecko będzie mężczyzną. A jeśli prawdopodobieństwo jest bliskie 0 lub 1, możemy uzyskać dobry obraz tego, czym naprawdę jest dziecięcy seks.

Bardziej formalnie, zwykle próbujemy powiedzieć, że jeśli błąd szkolenia wynosi to z dużym prawdopodobieństwem ( ) błąd niektórych danych generowanych z tego samego rozkładu będzie mniejszy niż . Znane są zależności między rozmiarem zestawu treningowego, epsilon a prawdopodobieństwem błędu testu przekraczającego . Podane przeze mnie podejście jest znane jako Prawdopodobnie prawidłowe nauczanie i jest ważną częścią obliczeniowej teorii uczenia się, która dotyczy problemu uogólnienia algorytmów uczenia się. Istnieje również wiele innych czynników, które mogą obniżyć epsilon i zwiększyć deltę w tych granicach, tj. złożoność przestrzeni hipotez.δ k + ϵ k + ϵkδk+ϵk+ϵ

Teraz wracamy do SVM. Jeśli nie używasz jąder lub nie używasz jąder, które odwzorowują na skończone przestrzenie wymiarowe, tak zwany wymiar Vapnika-Chervonenkisa, który jest miarą złożoności przestrzeni hipotetycznej, jest skończony, a dzięki temu i wystarczającej liczbie przykładów treningowych możesz uzyskać to z wysoką prawdopodobieństwo błąd w zestawie testowym nie będzie znacznie większy niż błąd w zestawie treningowym. Jeśli użyjesz jąder odwzorowanych na nieskończenie wymiarowe przestrzenie cech, wówczas wymiar Vapnika-Chervonenkisa również będzie nieskończony, a co gorsza, same próbki treningowe nie mogą zagwarantować dobrego uogólnienia, bez względu na ich liczbę. Na szczęście wielkość marginesu SVM okazuje się być dobrym parametrem zapewniającym uogólnienie. Dzięki dużemu marginesowi i ustawionemu treningowi możesz zagwarantować, że błąd testowy również nie będzie znacznie większy niż błąd treningowy.

sjm.majewski
źródło
7

Istnieją co najmniej dwa główne źródła nadmiernego dopasowania, które możesz rozważyć.

  1. Nadmierne dopasowanie z algorytmu, który wywnioskował zbyt wiele z dostępnych próbek treningowych. Najlepiej jest to zabezpieczyć empirycznie za pomocą miary zdolności generalizacji modelu. Krzyżowa walidacja jest jedną z takich popularnych metod.

  2. Nadmierne dopasowanie, ponieważ rozkład podstawowy jest niedróbkowany. Zwykle niewiele można na to poradzić, chyba że można zebrać więcej danych lub dodać wiedzę o domenie na temat problemu do modelu.

Ze 120 próbkami i dużą liczbą funkcji najprawdopodobniej popełnisz błąd 2, a także możesz mieć skłonność do 1.

Możesz zrobić coś z 1, uważnie obserwując wpływ złożoności modelu na błędy testu i szkolenia.

image_doctor
źródło
Ale w jaki sposób wykrywamy, czy jesteśmy nadmiernie uzdolnieni? Jeśli modele sprawdzają się całkiem nieźle w walidacji krzyżowej, czy robią to, ponieważ są naprawdę dobre, czy z powodu przeregulowania z powodu 1 lub 2? Również przy tysiącach funkcji ręczne analizowanie każdej funkcji byłoby kłopotliwe. Jeśli nie można stwierdzić nadmiernego dopasowania, w jaki sposób możemy ufać wynikowi weryfikacji krzyżowej?
user13420,
1
Bez dodatkowych danych bardzo trudno jest stwierdzić, czy nadmiernie się dopasowuje się do populacji o niskiej populacji. Możesz podzielić dane na trzy zestawy za pomocą zestawu sprawdzającego poprawność modelu, a następnie osobnego zestawu testowego, aby go przetestować. Innym podejściem jest modyfikacja złożoności modelu i sprawdzenie, jak różnią się dokładności zestawu treningowego i testowego. Wzrost błędu zestawu testowego wskaże pewien stopień nadmiernego dopasowania modelu do danych.
image_doctor,
Zastosowanie powtarzających się prób trzymania 50/50 da ci poczucie, że zestawy treningowe i testowe są zrównoważone. Prawdopodobnie nie będą. Niektóre modele, takie jak KNN, osiągną idealną dokładność na zestawie treningowym, więc są z natury w pewnym sensie przeregulowane. Ale nadal mogą osiągnąć akceptowalną wydajność na zestawie testowym. Podobnie jak w przypadku uczenia maszynowego, ostatecznie wszystko zależy od dokładnej specyfiki danych.
image_doctor,
@image_doctor Czy możesz opracować „modyfikację złożoności modelu”?
Keith Hughitt