Maszyna wektorów nośnych - Support-vector machine

W uczenia maszynowego , maszyn support-wektorów ( SVMs , również sieci wsparcia wektor ) są nadzorowane uczenia modele z powiązanych uczących się algorytmów , które analizują dane dotyczące klasyfikacji i analizy regresji . Opracowane w AT&T Bell Laboratories przez Vladimira Vapnika wraz z kolegami (Boser et al., 1992, Guyon et al., 1993, Vapnik et al., 1997) SVM są jedną z najbardziej niezawodnych metod przewidywania, opartą na statystycznych ramach uczenia się lub VC teoria zaproponowana przez Vapnika (1982, 1995) i Chervonenkisa (1974). Biorąc pod uwagę zestaw przykładów szkolenia, każdy oznaczony jako należące do jednej z dwóch kategorii, algorytm SVM trening buduje model, który przypisuje nowe przykłady do jednej lub drugiej kategorii, co czyni go nie- probabilistyczny binarny liniowy klasyfikator (choć metody, takie jak Platt skalowanie istnieje, aby używać SVM w ustawieniu klasyfikacji probabilistycznej). SVM odwzorowuje przykłady treningowe na punkty w przestrzeni, aby zmaksymalizować szerokość luki między dwiema kategoriami. Nowe przykłady są następnie mapowane w tej samej przestrzeni i przewiduje się, że będą należeć do kategorii na podstawie tego, po której stronie luki się znajdują.

Oprócz przeprowadzania klasyfikacji liniowej maszyny SVM mogą wydajnie przeprowadzać klasyfikację nieliniową za pomocą tak zwanej sztuczki jądra , niejawnie mapując dane wejściowe w wielowymiarowe przestrzenie cech.

Gdy dane są nieoznaczone, nadzorowane uczenie się nie jest możliwe i wymagane jest podejście nienadzorowanego uczenia się, które próbuje znaleźć naturalne grupowanie danych w grupy, a następnie mapować nowe dane do tych utworzonych grup. Klastrów wsparcie wektor algorytm stworzony przez Hava Siegelmann i Vladimir Vapnik , stosuje statystyk wektorów wspierających, opracowanych w wektorze wsparcia algorytm maszyny, do klasyfikowania danych nieopisane, i jest jednym z najczęściej używanych algorytmów grupowania w zastosowaniach przemysłowych.

Motywacja

H 1 nie rozdziela klas. H 2 tak, ale tylko z niewielkim marginesem. H 3 oddziela je maksymalnym marginesem.

Klasyfikowanie danych jest typowym zadaniem w uczeniu maszynowym . Załóżmy, że każdy z podanych punktów danych należy do jednej z dwóch klas, a celem jest podjęcie decyzji, w której klasie będzie znajdować się nowy punkt danych . W przypadku maszyn wektora nośnego punkt danych jest postrzegany jako wektor dwuwymiarowy (a listy liczb) i chcemy wiedzieć, czy możemy oddzielić takie punkty za pomocą dwuwymiarowej hiperpłaszczyzny . Nazywa się to klasyfikatorem liniowym . Istnieje wiele hiperpłaszczyzn, które mogą klasyfikować dane. Jednym rozsądnym wyborem jako najlepsza hiperpłaszczyzna jest ta, która reprezentuje największą odległość lub margines między dwiema klasami. Więc wybieramy hiperpłaszczyznę tak, aby odległość od niej do najbliższego punktu danych z każdej strony była zmaksymalizowana. Jeśli taka hiperpłaszczyzna istnieje, jest znana jako hiperpłaszczyzna maksymalnego marginesu, a klasyfikator liniowy, który definiuje, jest znany jako klasyfikator maksymalnego marginesu ; lub równoważnie, perceptron o optymalnej stabilności .

Definicja

Bardziej formalnie, maszyna wektora nośnego konstruuje hiperpłaszczyznę lub zbiór hiperpłaszczyzn w przestrzeni wysoko- lub nieskończenie wymiarowej, które można wykorzystać do klasyfikacji , regresji lub innych zadań, takich jak wykrywanie wartości odstających. Intuicyjnie, dobrą separację uzyskuje się dzięki hiperpłaszczyźnie, która ma największą odległość do najbliższego punktu danych treningowych dowolnej klasy (tzw. margines funkcjonalny), ponieważ generalnie im większy margines, tym mniejszy błąd uogólnienia klasyfikatora.

Maszyna jądra

Podczas gdy pierwotny problem można sformułować w przestrzeni skończenie wymiarowej, często zdarza się, że zbiory do dyskryminowania nie są w tej przestrzeni liniowo separowalne . Z tego powodu zaproponowano, aby oryginalna przestrzeń o skończonych wymiarach została zmapowana do przestrzeni o wiele wyższych wymiarów, prawdopodobnie ułatwiając separację w tej przestrzeni. Aby utrzymać rozsądne obciążenie obliczeniowe, mapowania używane przez schematy SVM są zaprojektowane tak, aby zapewnić, że iloczyny skalarne par wektorów danych wejściowych mogą być łatwo obliczone pod względem zmiennych w oryginalnej przestrzeni, poprzez zdefiniowanie ich w kategoriach wybranej funkcji jądra aby dopasować się do problemu. Hiperpłaszczyzny w przestrzeni wyższego wymiaru definiuje się jako zbiór punktów, których iloczyn skalarny z wektorem w tej przestrzeni jest stały, gdzie taki zbiór wektorów jest ortogonalnym (a więc minimalnym) zbiorem wektorów definiującym hiperpłaszczyznę. Wektory definiujące hiperpłaszczyzny mogą być wybrane jako kombinacje liniowe z parametrami obrazów wektorów cech występujących w bazie danych. Z tym wyborem hiperpłaszczyznę punkty w przestrzeni cech , które są przypisane do odpowiednich hiperpłaszczyznę są zdefiniowane przez relację pamiętać, że jeśli staje się mały jak rośnie dalej od , każdy termin w środkach suma stopień bliskości punktu testowego do odpowiedni punkt bazy danych . W ten sposób suma jąder powyżej może być użyta do pomiaru względnej bliskości każdego punktu testowego do punktów danych pochodzących z jednego lub drugiego zestawu, który ma być rozróżniany. Zwróć uwagę na fakt, że zbiór punktów odwzorowanych na dowolnej hiperpłaszczyźnie może być w rezultacie dość zawiły, co pozwala na znacznie bardziej złożone rozróżnianie zbiorów, które nie są wcale wypukłe w oryginalnej przestrzeni.

Aplikacje

Maszyny SVM mogą być używane do rozwiązywania różnych rzeczywistych problemów:

  • SVM są pomocne w kategoryzacji tekstu i hipertekstu , ponieważ ich zastosowanie może znacznie zmniejszyć potrzebę oznakowanych instancji szkoleniowych zarówno w standardowych ustawieniach indukcyjnych, jak i transdukcyjnych . Niektóre metody płytkiego analizowania semantycznego są oparte na maszynach wektorów nośnych.
  • Klasyfikację obrazów można również przeprowadzić za pomocą maszyn SVM. Wyniki eksperymentalne pokazują, że SVM osiągają znacznie wyższą dokładność wyszukiwania niż tradycyjne schematy doprecyzowania zapytań po zaledwie trzech do czterech rundach informacji zwrotnych o trafności. Dotyczy to również systemów segmentacji obrazu , w tym systemów wykorzystujących zmodyfikowaną wersję SVM, która wykorzystuje uprzywilejowane podejście sugerowane przez Vapnika.
  • Klasyfikacja danych satelitarnych, takich jak dane SAR, przy użyciu nadzorowanej SVM.
  • Znaki odręczne można rozpoznać za pomocą SVM.
  • Algorytm SVM znalazł szerokie zastosowanie w naukach biologicznych i innych. Zostały one wykorzystane do klasyfikacji białek, w których do 90% związków sklasyfikowano prawidłowo. Jako mechanizm interpretacji modeli SVM zaproponowano testy permutacyjne oparte na wagach SVM. W przeszłości do interpretacji modeli SVM wykorzystywano również wagi wektora nośnego. Interpretacja posthoc modeli maszyn z wektorem nośnym w celu identyfikacji cech wykorzystywanych przez model do prognozowania jest stosunkowo nowym obszarem badań o szczególnym znaczeniu w naukach biologicznych.

Historia

Oryginalny algorytm SVM został wynaleziony przez Vladimira N. Vapnika i Alexeya Ya. Chervonenkis w 1963. W 1992 Bernhard Boser, Isabelle Guyon i Vladimir Vapnik zaproponowali sposób tworzenia nieliniowych klasyfikatorów poprzez zastosowanie sztuczki jądra do hiperpłaszczyzn z maksymalnym marginesem. Wcielenie „miękkiego marginesu”, jak powszechnie używane pakiety oprogramowania, zostało zaproponowane przez Corinnę Cortes i Vapnik w 1993 roku i opublikowane w 1995 roku.

Liniowa SVM

Hiperpłaszczyzna i marginesy maksymalnego marginesu dla maszyny SVM wytrenowanej przy użyciu próbek z dwóch klas. Próbki na marginesie nazywane są wektorami nośnymi.

Otrzymujemy treningowy zbiór punktów formularza

gdzie są 1 lub -1, z których każdy wskazuje klasę, do której należy punkt . Każdy jest dwuwymiarowym wektorem rzeczywistym . Chcemy znaleźć „hiperpłaszczyznę z maksymalnym marginesem”, która dzieli grupę punktów dla których od grupy punktów dla których , która jest zdefiniowana w taki sposób, że odległość między hiperpłaszczyzną a najbliższym punktem z dowolnej grupy jest zmaksymalizowana.

Dowolną hiperpłaszczyznę można zapisać jako zbiór punktów spełniających

gdzie jest (niekoniecznie znormalizowanym) wektorem normalnym do hiperpłaszczyzny. Jest to bardzo podobne do postaci normalnej Hesse , z tym wyjątkiem, że niekoniecznie jest wektorem jednostkowym. Parametr określa odsunięcie hiperpłaszczyzny od początku wzdłuż wektora normalnego .

Twarda marża

Jeśli dane ucząceliniowo separowalne , możemy wybrać dwie równoległe hiperpłaszczyzny, które oddzielają dwie klasy danych, tak aby odległość między nimi była jak największa. Obszar ograniczony przez te dwie hiperpłaszczyzny nazywany jest „marginesem”, a hiperpłaszczyzna maksymalnego marginesu to hiperpłaszczyzna leżąca w połowie odległości między nimi. Przy znormalizowanym lub znormalizowanym zbiorze danych te hiperpłaszczyzny można opisać równaniami

(wszystko na tej granicy lub powyżej tej granicy należy do jednej klasy, z etykietą 1)

oraz

(wszystko na tej granicy lub poniżej tej granicy należy do innej klasy, z etykietą −1).

Geometrycznie odległość między tymi dwoma hiperpłaszczyznami wynosi , więc aby zmaksymalizować odległość między płaszczyznami, chcemy zminimalizować . Odległość jest obliczana na podstawie odległości od punktu do równania płaszczyzny . Musimy również zapobiec wpadaniu punktów danych do marginesu, dodajemy następujące ograniczenie: dla każdego albo

, jeśli ,

lub

, jeśli .

Te ograniczenia stanowią, że każdy punkt danych musi leżeć po właściwej stronie marginesu.

Można to przepisać jako

Możemy to połączyć, aby uzyskać problem optymalizacji:

„Minimalizacja zastrzeżeniem dla ”.

I że rozwiąże ten problem określenia naszego klasyfikatora, gdzie jest funkcja znak .

Ważną konsekwencją tego opisu geometrycznego jest to, że hiperpłaszczyzna z maksymalnym marginesem jest całkowicie określona przez te, które leżą najbliżej niej. Są to tak zwane wektory wsparcia .

Miękka marża

Aby rozszerzyć SVM na przypadki, w których danych nie da się oddzielić liniowo, pomocna jest funkcja utraty zawiasów

Zauważ, że jest to i -ty cel (tzn. w tym przypadku 1 lub -1) i jest i -tym wyjściem.

Ta funkcja ma wartość zero, jeśli warunek (1) jest spełniony, innymi słowy, jeśli leży po właściwej stronie marginesu. Dla danych po niewłaściwej stronie marginesu wartość funkcji jest proporcjonalna do odległości od marginesu.

Celem optymalizacji jest więc minimalizacja

gdzie parametr określa kompromis między zwiększeniem rozmiaru depozytu zabezpieczającego a zapewnieniem, że leży on po właściwej stronie depozytu zabezpieczającego. Tak więc, dla wystarczająco dużych wartości , będzie zachowywać się podobnie do SVM z twardym depozytem, ​​jeśli dane wejściowe można klasyfikować liniowo, ale nadal będzie się uczyć, czy reguła klasyfikacji jest wykonalna, czy nie. (Ten parametr jest również nazywany C, np. w LIBSVM .)

Klasyfikacja nieliniowa

Maszyna jądra

Oryginalny algorytm hiperpłaszczyznowy maksymalnego marginesu zaproponowany przez Vapnika w 1963 roku skonstruował klasyfikator liniowy . Jednak w 1992 roku Bernhard Boser , Isabelle Guyon i Vladimir Vapnik zasugerowali sposób tworzenia nieliniowych klasyfikatorów poprzez zastosowanie sztuczki z jądrem (pierwotnie zaproponowanej przez Aizermana i in.) do hiperpłaszczyzn z maksymalnym marginesem. Wynikowy algorytm jest formalnie podobny, z wyjątkiem tego, że każdy iloczyn skalarny jest zastępowany nieliniową funkcją jądra . Pozwala to algorytmowi dopasować hiperpłaszczyznę maksymalnego marginesu w przekształconej przestrzeni cech . Transformacja może być nieliniowa, a przekształcona przestrzeń wielowymiarowa; chociaż klasyfikator jest hiperpłaszczyzną w przekształconej przestrzeni cech, może być nieliniowy w oryginalnej przestrzeni wejściowej.

Warto zauważyć, że praca w wielowymiarowej przestrzeni cech zwiększa błąd uogólnienia maszyn z wektorem nośnym, chociaż przy wystarczającej liczbie próbek algorytm nadal działa dobrze.

Niektóre popularne jądra to:

  • Wielomian (jednorodny) : .
  • Wielomian (niejednorodny): .
  • Radialna funkcja bazowa Gaussa : for . Czasami sparametryzowana za pomocą .
  • Tangens hiperboliczny : dla niektórych (nie dla każdego) i .

Jądro jest powiązane z transformacją równaniem . Wartość w jest również w przestrzeni przekształconej, z . Iloczyny skalarne z w dla klasyfikacji można ponownie obliczyć za pomocą sztuczki jądra, tj . .

Obliczanie klasyfikatora SVM

Obliczenie klasyfikatora (miękkiego marginesu) SVM sprowadza się do minimalizacji wyrażenia formy

Skupiamy się na klasyfikatorze z miękkim marżem, ponieważ, jak wspomniano powyżej, wybranie wystarczająco małej wartości daje klasyfikator z marżą twardą dla danych wejściowych, które można klasyfikować liniowo. Klasyczne podejście, które obejmuje sprowadzenie (2) do kwadratowego problemu programowania , jest szczegółowo opisane poniżej. Następnie omówione zostaną nowsze podejścia, takie jak zejście pod-gradientowe i zejście współrzędne.

Pierwotny

Minimalizowanie (2) można przepisać jako problem optymalizacji z ograniczeniami z różniczkowalną funkcją celu w następujący sposób.

Dla każdego wprowadzamy zmienną . Zauważ, że jest to najmniejsza nieujemna liczba spełniająca

W ten sposób możemy przepisać problem optymalizacji w następujący sposób:

Nazywa się to problemem pierwotnym .

Podwójny

Rozwiązując dla podwójnego Lagrange'a powyższego problemu, otrzymujemy uproszczony problem

Nazywa się to podwójnym problemem. Ponieważ problem podwójnej maksymalizacji jest funkcją kwadratową obiektu podlegającego ograniczeniom liniowym, można go skutecznie rozwiązać za pomocą algorytmów programowania kwadratowego .

Tutaj zmienne są zdefiniowane w taki sposób, że

.

Co więcej, dokładnie kiedy leży po właściwej stronie marginesu, a kiedy leży na granicy marginesu. Wynika z tego, że można to zapisać jako liniową kombinację wektorów nośnych.

Przesunięcie, , można odzyskać, znajdując na granicy marginesu i rozwiązując

(Zauważ, że od .)

Sztuczka jądra

Przykład uczący SVM z jądrem podanym przez φ(( a , b )) = ( a , b , a 2 + b 2 )

Załóżmy teraz, że chcielibyśmy nauczyć się nieliniowej reguły klasyfikacji, która odpowiada liniowej regule klasyfikacji dla przekształconych punktów danych. Ponadto, otrzymaliśmy funkcję jądra, która spełnia .

Wiemy, że wektor klasyfikacyjny w przestrzeni transformowanej spełnia

gdzie otrzymuje się je rozwiązując problem optymalizacyjny

Współczynniki można rozwiązać za pomocą programowania kwadratowego, jak poprzednio. Ponownie możemy znaleźć indeks taki, że , tak że leży na granicy marginesu w transformowanej przestrzeni, a następnie rozwiązać

Wreszcie,

Nowoczesne metody

Najnowsze algorytmy znajdowania klasyfikatora SVM obejmują opadanie podgradientowe i opadanie współrzędnych. Obie techniki okazały się mieć znaczną przewagę nad tradycyjnym podejściem w przypadku dużych, nielicznych zbiorów danych — metody podgradientowe są szczególnie wydajne, gdy istnieje wiele przykładów uczących, a koordynacja zejścia, gdy wymiar przestrzeni cech jest wysoki.

Zejście pod-gradientowe

Algorytmy opadania sub-gradientowego dla SVM działają bezpośrednio z wyrażeniem

Należy pamiętać, że jest to funkcja wypukła z i . Jako taki, tradycyjne metoda gradientu prostego (lub SGD ) sposób może być dostosowany, gdzie zamiast przy krok w kierunku gradientu danej funkcji, etap jest robione w kierunku wektora wybranego z funkcyjnego sub-gradientu . Takie podejście ma tę zaletę, że w przypadku niektórych implementacji liczba iteracji nie jest skalowana z liczbą punktów danych.

Współrzędne zejścia

Algorytmy opadania współrzędnych dla SVM działają z podwójnego problemu

Dla każdego , iteracyjnie, współczynnik jest dostosowywany w kierunku . Następnie otrzymany wektor współczynników rzutowany jest na najbliższy wektor współczynników, który spełnia podane ograniczenia. (Zazwyczaj stosuje się odległości euklidesowe.) Proces jest następnie powtarzany aż do uzyskania bliskiego optymalnego wektora współczynników. Powstały algorytm jest niezwykle szybki w praktyce, chociaż udowodniono niewiele gwarancji wydajności.

Minimalizacja ryzyka empirycznego

Opisana powyżej maszyna wektorów nośnych miękkiego marginesu jest przykładem empirycznego algorytmu minimalizacji ryzyka (ERM) dla utraty zawiasu . Widziane w ten sposób maszyny wektorów nośnych należą do naturalnej klasy algorytmów wnioskowania statystycznego, a wiele z ich unikalnych cech wynika z zachowania utraty zawiasów. Ta perspektywa może zapewnić dalszy wgląd w to, jak i dlaczego działają SVM, a także pozwolić nam lepiej analizować ich właściwości statystyczne.

Minimalizacja ryzyka

W uczeniu nadzorowanym otrzymuje się zestaw przykładów treningowych z etykietami i chce się przewidzieć dane . W tym celu stawia się hipotezę , , taką, która jest „dobrym” przybliżeniem . A „dobre” przybliżenie definiuje się zwykle przy pomocy funkcji straty , , która charakteryzuje, jak źle jest w przewidywaniu . Następnie chcielibyśmy wybrać hipotezę, która minimalizuje oczekiwane ryzyko :

W większości przypadków nie znamy wprost wspólnego rozkładu . W takich przypadkach powszechną strategią jest wybór hipotezy, która minimalizuje ryzyko empiryczne:

Przy pewnych założeniach dotyczących sekwencji zmiennych losowych (na przykład, że są one generowane przez skończony proces Markowa), jeśli zbiór rozważanych hipotez jest wystarczająco mały, minimalizator ryzyka empirycznego będzie ściśle zbliżony do minimalizatora ryzyka oczekiwanego jak rośnie. Takie podejście nazywa się empiryczną minimalizacją ryzyka lub ERM.

Uregulowanie i stabilność

Aby problem minimalizacji miał dobrze zdefiniowane rozwiązanie, musimy nałożyć ograniczenia na zbiór rozważanych hipotez. Jeżeli jest przestrzenią unormowaną (jak w przypadku SVM), szczególnie skuteczną techniką jest rozważenie tylko tych hipotez, dla których . Jest to równoznaczne z nałożeniem kary na regularyzację i rozwiązanie nowego problemu optymalizacji

Takie podejście nazywa się regularyzacją Tichonowa .

Bardziej ogólnie, może być pewną miarą złożoności hipotezy , tak więc preferowane są prostsze hipotezy.

SVM i utrata zawiasu

Przypomnij sobie, że klasyfikator SVM (z miękkim marginesem) został wybrany w celu zminimalizowania następującego wyrażenia:

W świetle powyższej dyskusji widzimy, że technika SVM jest równoważna minimalizacji ryzyka empirycznego z regularyzacją Tichonowa, gdzie w tym przypadku funkcją straty jest strata zawiasowa

Z tej perspektywy SVM jest ściśle powiązany z innymi podstawowymi algorytmami klasyfikacji, takimi jak uregulowane najmniejsze kwadraty i regresja logistyczna . Różnica między tymi trzema polega na wyborze funkcji straty: uregulowane najmniejszych kwadratów sprowadza się do empirycznej minimalizacji ryzyka za pomocą kwadratu straty , ; regresja logistyczna wykorzystuje log-loss ,

Funkcje docelowe

Różnicę między stratą zawiasową a tymi innymi funkcjami strat najlepiej określa się w kategoriach funkcji docelowych – funkcji, która minimalizuje oczekiwane ryzyko dla danej pary zmiennych losowych .

W szczególności niech oznaczają warunkowe zdarzeniu, że . W ustawieniu klasyfikacji mamy:

Optymalnym klasyfikatorem jest zatem:

W przypadku straty kwadratowej funkcją docelową jest warunkowa funkcja oczekiwania, ; Dla strat logistycznych jest to funkcja logitowa . Chociaż obie te funkcje docelowe dają poprawny klasyfikator, ponieważ dostarczają nam więcej informacji, niż potrzebujemy. W rzeczywistości dostarczają nam wystarczająco dużo informacji, aby w pełni opisać rozkład .

Z drugiej strony można sprawdzić, czy funkcją docelową utraty zawiasu jest dokładnie . Zatem w wystarczająco bogatej przestrzeni hipotez — lub równoważnie, dla odpowiednio wybranego jądra — klasyfikator SVM zbiegnie się do najprostszej funkcji (w kategoriach ), która poprawnie klasyfikuje dane. Rozszerza to geometryczną interpretację SVM — w przypadku klasyfikacji liniowej ryzyko empiryczne jest minimalizowane przez dowolną funkcję, której marginesy leżą między wektorami nośnymi, a najprostszym z nich jest klasyfikator z maksymalnym marginesem.

Nieruchomości

SVM należą do rodziny uogólnionych klasyfikatorów liniowych i mogą być interpretowane jako rozszerzenie perceptronu . Można je również uznać za szczególny przypadek regularyzacji Tichonowa . Specjalną właściwością jest to, że jednocześnie minimalizują empiryczny błąd klasyfikacji i maksymalizują margines geometryczny ; stąd są one również znane jako klasyfikatory maksymalnej marży .

Porównanie SVM z innymi klasyfikatorami dokonali Meyer, Leisch i Hornik.

Wybór parametrów

Skuteczność SVM zależy od wyboru jądra, parametrów jądra i parametru miękkiego marginesu . Częstym wyborem jest jądro Gaussa, które ma jeden parametr . Najlepsza kombinacja i jest często wybierana przez wyszukiwanie w siatce z wykładniczo rosnącymi sekwencjami i , na przykład ; . Zazwyczaj każda kombinacja wybranych parametrów jest sprawdzana za pomocą walidacji krzyżowej i wybierane są parametry o najlepszej dokładności walidacji krzyżowej. Alternatywnie, ostatnie prace nad optymalizacją bayesowską można wykorzystać do wyboru i , często wymagając oceny znacznie mniejszej liczby kombinacji parametrów niż wyszukiwanie siatkowe. Ostateczny model, który służy do testowania i klasyfikowania nowych danych, jest następnie uczony na całym zbiorze uczącym przy użyciu wybranych parametrów.

Zagadnienia

Potencjalne wady SVM obejmują następujące aspekty:

  • Wymaga pełnego oznakowania danych wejściowych
  • Nieskalibrowane prawdopodobieństwa przynależności do klasy — SVM wywodzi się z teorii Vapnika, która unika szacowania prawdopodobieństw na danych skończonych
  • SVM ma bezpośrednie zastosowanie tylko do zadań dwuklasowych. Dlatego należy zastosować algorytmy, które redukują zadanie wieloklasowe do kilku problemów binarnych; zobacz sekcję wieloklasową maszynę SVM .
  • Parametry rozwiązanego modelu są trudne do interpretacji.

Rozszerzenia

Klastrowanie wektorów nośnych (SVC)

SVC to podobna metoda, która również opiera się na funkcjach jądra, ale jest odpowiednia do uczenia nienadzorowanego. Jest uważany za podstawową metodę w nauce o danych .

Wieloklasowa SVM

Multiclass SVM ma na celu przypisanie etykiet do instancji za pomocą maszyn wektora nośnego, gdzie etykiety są rysowane ze skończonego zestawu kilku elementów.

Dominującym podejściem do tego jest redukcja pojedynczego problemu wieloklasowego do wielu problemów klasyfikacji binarnej . Typowe metody takiej redukcji obejmują:

  • Tworzenie klasyfikatorów binarnych, które rozróżniają jedną z etykiet od pozostałych ( jedna kontra wszystkie ) lub każda para klas ( jedna kontra jedna ). Klasyfikacja nowych instancji dla przypadku jeden na wszystkie odbywa się za pomocą strategii zwycięzca bierze wszystko, w której klasyfikator z funkcją o najwyższym wyniku przypisuje klasę (ważne jest, aby funkcje wyjściowe były skalibrowane w celu uzyskania porównywalnych wyników ). W przypadku podejścia jeden na jeden klasyfikacja odbywa się za pomocą strategii głosowania max-wins, w której każdy klasyfikator przypisuje instancję do jednej z dwóch klas, następnie głos na przypisaną klasę zwiększa się o jeden głos, a na końcu klasa z największą liczbą głosów określa klasyfikację instancji.
  • Skierowany graf acykliczny SVM (DAGSVM)
  • Kody wyjściowe korekcji błędów

Crammer i Singer zaproponowali wieloklasową metodę SVM, która przekształca problem klasyfikacji wieloklasowej w pojedynczy problem optymalizacji, zamiast rozkładać go na wiele binarnych problemów klasyfikacji. Zobacz także Lee, Lin i Wahba oraz Van den Burg i Groenen.

Przewodzące maszyny wektorów nośnych

Transdukcyjne maszyny wektora nośnego rozszerzają SVM, ponieważ mogą również przetwarzać częściowo oznakowane dane w częściowo nadzorowanym uczeniu się, przestrzegając zasad transdukcji . Tutaj oprócz zestawu treningowego uczeń otrzymuje również zestaw

przykładów testowych do sklasyfikowania. Formalnie transdukcyjna maszyna wektora nośnego jest zdefiniowana przez następujący problem optymalizacji pierwotnej:

Minimalizuj (w )

podlega (dla dowolnego i dowolnego )

oraz

Transdukcyjne maszyny wektorów nośnych zostały wprowadzone przez Vladimira N. Vapnika w 1998 roku.

Strukturalna SVM

Maszyny SVM zostały uogólnione do ustrukturyzowanych maszyn SVM , w których przestrzeń etykiet jest ustrukturyzowana i ma prawdopodobnie nieskończony rozmiar.

Regresja

Regresja wektora nośnego (prognoza) z różnymi progami ε . Wraz ze wzrostem ε predykcja staje się mniej wrażliwa na błędy.

Wersję SVM do regresji zaproponowali w 1996 roku Vladimir N. Vapnik , Harris Drucker, Christopher JC Burges, Linda Kaufman i Alexander J. Smola. Ta metoda nazywa się regresją wektora nośnego (SVR). Model utworzony przez klasyfikację wektora nośnego (jak opisano powyżej) zależy tylko od podzbioru danych uczących, ponieważ funkcja kosztu budowy modelu nie dba o punkty uczące, które leżą poza marginesem. Analogicznie model stworzony przez SVR zależy tylko od podzbioru danych szkoleniowych, ponieważ funkcja kosztu budowy modelu ignoruje wszelkie dane szkoleniowe zbliżone do przewidywania modelu. Inną wersję SVM, znaną jako maszyna wektora wsparcia najmniejszych kwadratów (LS-SVM), zaproponowali Suykens i Vandewalle.

Szkolenie oryginalnego SVR oznacza rozwiązywanie

zminimalizować
podlega

gdzie jest próbka szkoleniowa z wartością docelową . Iloczyn wewnętrzny plus wyraz wolny jest predykcją dla tej próbki i jest swobodnym parametrem, który służy jako próg: wszystkie predykcje muszą znajdować się w zakresie prawdziwych predykcji. Zmienne luźne są zwykle dodawane do powyższego, aby uwzględnić błędy i umożliwić aproksymację w przypadku, gdy powyższy problem jest niewykonalny.

Bayesowski SVM

W 2011 roku Polson i Scott pokazali, że SVM dopuszcza interpretację bayesowską poprzez technikę augmentacji danych . W tym podejściu SVM jest postrzegana jako model graficzny (w którym parametry są połączone rozkładami prawdopodobieństwa). Ten rozszerzony widok umożliwia zastosowanie technik bayesowskich do maszyn SVM, takich jak elastyczne modelowanie cech, automatyczne dostrajanie hiperparametrów i przewidywanie ilościowe niepewności . Niedawno Florian Wenzel opracował skalowalną wersję Bayesian SVM , umożliwiając zastosowanie Bayesian SVM do dużych zbiorów danych . Florian Wenzel opracował dwie różne wersje, schemat wnioskowania wariacyjnego (VI) dla bayesowskiej maszyny wektorów wsparcia jądra (SVM) oraz wersję stochastyczną (SVI) dla liniowej bayesowskiej maszyny SVM.

Realizacja

Parametry hiperpłaszczyzny z maksymalnym marginesem są wyprowadzane przez rozwiązanie optymalizacji. Istnieje kilka wyspecjalizowanych algorytmów do szybkiego rozwiązywania problemu programowania kwadratowego (QP), który powstaje w maszynach SVM.

Innym podejściem jest zastosowanie metody punktu wewnętrznego, która wykorzystuje iteracje typu Newtona , aby znaleźć rozwiązanie warunków Karusha-Kuhna-Tuckera dla problemów pierwotnych i dualnych. Zamiast rozwiązywać sekwencję podzielonych problemów, to podejście bezpośrednio rozwiązuje problem całkowicie. Aby uniknąć rozwiązania liniowego systemu obejmującego dużą macierz jądra, w sztuczce jądra często stosuje się przybliżenie niskiego rzędu do macierzy.

Inną powszechną metodą jest algorytm SMO ( sekwencyjnej optymalizacji sekwencyjnej ) Platta , który rozbija problem na dwuwymiarowe podproblemy, które są rozwiązywane analitycznie, eliminując potrzebę numerycznego algorytmu optymalizacji i przechowywania macierzy. Algorytm ten jest koncepcyjnie prosty, łatwy do wdrożenia, generalnie szybszy i ma lepsze właściwości skalowania dla trudnych problemów SVM.

Specjalny przypadek liniowych maszyn wektorów nośnych można skuteczniej rozwiązać za pomocą tego samego rodzaju algorytmów, które są używane do optymalizacji ich bliskiego kuzyna, regresji logistycznej ; ta klasa algorytmów obejmuje zejście pod-gradientowe (np. PEGASOS) i zejście za pomocą współrzędnych (np. LIBLINEAR). LIBLINEAR ma kilka atrakcyjnych właściwości w czasie treningu. Każda iteracja zbieżności zajmuje liniowo czas w stosunku do czasu potrzebnego na odczyt danych pociągu, a iteracje mają również właściwość zbieżności liniowej Q , dzięki czemu algorytm jest niezwykle szybki.

Ogólne SVM jądra mogą być również rozwiązywane wydajniej przy użyciu sub-gradientowego zejścia (np. P-packSVM), zwłaszcza gdy dozwolona jest równoległość .

Kernel SVM są dostępne w wielu zestawach narzędzi do uczenia maszynowego, w tym LIBSVM , MATLAB , SAS , SVMlight, kernlab , scikit-learn , Shogun , Weka , Shark , JKernelMachines , OpenCV i inne.

Zaleca się wstępne przetwarzanie danych (standaryzacja) w celu zwiększenia dokładności klasyfikacji. Istnieje kilka metod standaryzacji, takich jak min-max, normalizacja przez skalowanie dziesiętne, Z-score. W przypadku SVM zwykle stosuje się odejmowanie średniej i dzielenie przez wariancję każdej cechy.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki