Czy można obsługiwać maszynę wektorową w dużych danych?

Mając ograniczoną wiedzę na temat SVM, jest to dobre dla krótkiej i grubej macierzy danych (wiele funkcji i niezbyt wielu instancji), ale nie dla dużych zbiorów danych.$X$

Rozumiem, że jednym z powodów jest to, że macierz jądra jest macierzą , gdzie to liczba wystąpień w danych. Jeśli powiemy, 100K danych, macierz K jądra będzie miała 10 10 elementów i może zająć ~ 80G pamięci.$K$$n \times n$$n$$K$$10^{10}$

Czy jest jakaś modyfikacja SVM, której można użyć w dużych danych? (Powiedz w skali od 100K do 1M punktów danych?)

Jak wspomniałeś, przechowywanie macierzy jądra wymaga pamięci, która skaluje się kwadratowo z liczbą punktów danych. Czas szkolenia dla tradycyjnych algorytmów SVM również skaluje się superliniowo z liczbą punktów danych. Dlatego te algorytmy nie są wykonalne w przypadku dużych zestawów danych.

$K_{ij}$$x_i$$x_j$$K_{ij} = \Phi(x_i) \cdot \Phi(x_j)$$\Phi$jest domyślnie zdefiniowany przez funkcję jądra, a maszyny SVM w jądrze nie obliczają jawnie reprezentacji przestrzeni cech. Jest to wydajne obliczeniowo w przypadku zestawów danych o małych i średnich rozmiarach, ponieważ przestrzeń cech może być bardzo wielowymiarowa, a nawet nieskończona. Ale, jak wyżej, staje się to niemożliwe dla dużych zestawów danych. Zamiast tego możemy jawnie odwzorować dane nieliniowo na przestrzeń cech, a następnie skutecznie trenować liniową SVM na reprezentacjach przestrzeni cech. Mapowanie przestrzeni cech można skonstruować w celu przybliżenia danej funkcji jądra, ale używać mniejszej liczby wymiarów niż „pełne” mapowanie przestrzeni cech. W przypadku dużych zestawów danych może to nadal zapewniać nam bogatą reprezentację przestrzeni cech, ale z wieloma mniejszymi wymiarami niż punkty danych.

Jedno podejście do aproksymacji jądra wykorzystuje aproksymację Nyström (Williams i Seeger 2001). Jest to sposób na przybliżenie wartości własnych / wektorów własnych dużej matrycy przy użyciu mniejszej submatrix. Inne podejście wykorzystuje funkcje losowe i jest czasami nazywane „losowymi zlewami kuchennymi” (Rahimi i Recht 2007).

Kolejną sztuczką do szkolenia SVM na dużych zestawach danych jest przybliżenie problemu optymalizacji za pomocą zestawu mniejszych podproblemów. Na przykład użycie stochastycznego spadku gradientu na pierwotnym problemie jest jednym podejściem (wśród wielu innych). Dużo pracy wykonano na froncie optymalizacji. Menon (2009) daje dobrą ankietę.

Bibliografia

Williams and Seeger (2001). Wykorzystanie metody Nystroem do przyspieszenia maszyn jądra.

Rahimi and Recht (2007). Losowe funkcje dużych maszyn jądra.

Menon (2009) . Wielkoskalowe maszyny wektorowe wsparcia: Algorytmy i teoria.