Podręcznik

Niezależnie od zastosowanego jądra i rodzaju zadania (klasyfikacji czy regresji) główny problem obliczeniowy w sieciach SVM sprowadza się do rozwiązania zadania programowania kwadratowego z ograniczeniami liniowymi. Jakkolwiek jest to temat stosunkowo dobrze opracowany w teorii optymalizacji [14,51] i dostępnych jest wiele profesjonalnych pakietów do rozwiązania tego zadania, pojawiły się trudności związane ze skalą zadania. Liczba danych uczących $p$ w problemach praktycznych sięga niekiedy setek tysięcy. Koresponduje z nią bezpośrednio liczba zmiennych optymalizowanych (mnożników Lagrange'a). Przy takich wymiarach pojawiają się trudne problemy związane z gospodarowaniem pamięcią i złożonością obliczeniową algorytmów. W efekcie nawet współczesne komputery nie są w stanie efektywnie, w akceptowalnym przez użytkownika czasie rozwiązać problemów o bardzo dużej skali przy zastosowaniu klasycznych metod programowania kwadratowego.

W efekcie prac pojawiło się wiele specjalizowanych procedur sekwencyjnych rozwiązania problemu programowania kwadratowego dostosowanych do sieci SVM i stosujących dekompozycję zbioru uczącego na szereg podzbiorów mniejszych. Większość z nich stosuje strategię ograniczeń aktywnych [43,52]. W strategii tej wszystkie ograniczenia dzieli się na dwa rodzaje: aktywne (ograniczenie ze znakiem równości), biorące udział w rozwiązaniu, i nieaktywne, nie mające w danej chwili wpływu na rozwiązanie (znak nierówności ograniczenia). W kolejnych iteracjach następuje przemieszczanie się poszczególnych ograniczeń z jednego zbioru do drugiego. Powstało wiele suboptymalnych rozwiązań stosujących takie podejście. Do najlepszych należą programy implementujące różne wersje algorytmu programowania sekwencyjnego (BSVM) Platta, program SVM_Light Joachimsa czy program LSVM Mangasariana.

Algorytm SVM_Light stosuje w rozwiązaniu metodę ograniczeń aktywnych, dobrze znaną i stosowaną w programowaniu kwadratowym [31]. Ze względu na duże rozmiary zbioru danych dzieli się go na mniejsze podzbiory: aktywny, dla którego poszukuje się rozwiązania optymalnego oraz nieaktywny, dla którego wszystkie warunki ograniczeń powinny być z góry spełnione. W każdej iteracji zmienne optymalizowane są zaliczane do 2 kategorii: zmienne wolne (aktywne), poddane aktualizacji i zmienne nieaktywne o wartościach ustalonych przez ograniczenia dolne bądź górne, nie podlegające zmianie. Jeśli wszystkie warunki optymalności są spełnione, rozwiązanie z danej iteracji jest uważane za optymalne. W przeciwnym wypadku algorytm dokonuje przegrupowania zmiennych z obu zbiorów i odpowiednich zmian w macierzy hesjanu przegrupowując jednocześnie podmacierze odpowiadające zmiennym aktywnym i nieaktywnym. Postęp w optymalizacji jest uzależniony od właściwego przypisania zmiennych do obu zbiorów. Stąd istotnym problemem jest wcześniejsze ustalenie, które mnożniki zmierzają do swoich ograniczeń. Pozwala to wyeliminować je ze zbioru zmiennych aktywnych i z góry ograniczyć liczbę zmiennych podlegających aktualizacji. T. Joachims w programie SVM^Light skutecznie zaimplementował algorytm heurystyczny estymacji mnożników, pozwalający na szybką redukcję liczebności zmiennych aktualizowanych i znaczne przyśpieszenie procesu uczenia przy bardzo dużej liczbie danych uczących. Szczegóły rozwiązania można znaleźć w pracy [31].

Algorytm SMO (ang. Sequential Minimal Optimization) należy do grupy programowania sekwencyjnego i polega na dekompozycji zadania programowania kwadratowego na mniejsze podzadania, rozwiązywane sekwencyjnie aż do spełnienia wszystkich warunków optymalności Kuhna-Tuckera. W rozwiązaniu zaproponowanym przez Platta [51] i zmodyfikowanym przez Hsu i Lina [28] zwanym dalej algorytmem BSVM, w każdym kroku iteracyjnym rozwiązywane jest podzadanie drugiego rzędu (dwa mnożniki Lagrange'a) przy sekwencyjnej wymianie par mnożników. Optymalizacja dwu mnożników na raz jest najmniejszym możliwym zadaniem posiadającym rozwiązanie analityczne typu jawnego. Dzięki temu algorytm nie wymaga zastosowania dużych pamięci nawet przy ogromnej liczbie danych uczących, a jego zbieżność jest zapewniona przez specjalną metodę wymiany i doboru par mnożników, gwarantującą redukcję wartości funkcji celu w każdym kroku iteracyjnym.

Platt zaproponował dwie pętle przeszukujące dane: zewnętrzną i wewnętrzną. Pętla zewnętrzna dokonuje selekcji pierwszego mnożnika $\alpha_1$ a pętla wewnętrzna - mnożnika drugiego $\alpha_2$ w taki sposób, że następuje maksymalizacja funkcji celu w problemie dualnym. Pętla zewnętrzna przebiega przez wszystkie pary danych uczących selekcjonując te, dla których $0 \leq \alpha_i \leq C$. Następnie sprawdza spełnienie warunków Kuhna-Tuckera dla wyselekcjonowanych przypadków i przyjmuje pierwszą parę danych $(\mathbf{x}_1, d_1)$, dla której warunki te są naruszone. Mnożnik Lagrange'a odpowiadający tak wyselekcjonowanej parze danych staje się $\alpha_1$. Po jego wyselekcjonowaniu pętla wewnętrzna przeszukuje wszystkie przypadki danych dla których $0 \leq \alpha_i \leq C$ poszukując takiego $\mathbf{x}_2$, dla którego moduł różnicy błędów $\left|\left(y\left(\mathbf{x}_1\right)-d_1\right)-\left(y\left(\mathbf{x}_2\right)-d_2\right)\right|$ jest największy. Dla tak wyselekcjonowanych przypadków przeprowadzana jest optymalizacja obu mnożników $\alpha_1$ i $\alpha_2$. Proces powtarzany jest wielokrotnie aż do spełnienia warunków Kuhna-Tuckera [14] dla wszystkich par uczących. Takie rozwiązanie algorytmu programowania sekwencyjnego jest bardzo skuteczne nawet przy liczbie danych dochodzących do setek tysięcy. Algorytm BSVM jest aktualnie uważany obok SVM_Light za jedną z najskuteczniejszych metod uczenia sieci SVM. Najważniejszą zaletą przedstawionych tu implementacji znanych wcześniej rozwiązań zadania dualnego jest ograniczenie wymagania pamięci, wzrastające tylko liniowo (proporcjonalnie do liczby danych uczących) i liczby wektorów podtrzymujących. Każdy z tych programów przewyższa zwykle standardowe rozwiązania programowania kwadratowego stosowane dotychczas. Tym nie mniej różnią się one między sobą również w sposób znaczący, zarówno pod względem czasu działania jak i skuteczności (wyznaczenia minimum globalnego funkcji celu).

Należy podkreślić, że choć teoretycznie każdy z algorytmów znajduje minimum globalne funkcji celu, to jakość rozwiązania zależy od tak zwanych "hiperparametrów" ustalanych arbitralnie przez użytkownika, na przykład szerokości funkcji radialnej $\sigma = 1/\gamma$ i wartości stałej regularyzacji  $C$. Parametry te nie podlegają adaptacji w procesie uczenia i ich niewłaściwe wartości mogą spowodować otrzymanie rozwiązania dalekiego od minimum globalnego, przy czym każda z odmian algorytmu może być w różnym stopniu czuła na założone wartości "hiperparametrów". Aby uniezależnić się od arbitralnego doboru tych parametrów powstało szereg rozwiązań sieci SVM, które pozwalają na dobór tych parametrów w procesie uczenia na podstawie określonych kryteriów przyjętych na wstępie. Do takich rozwiązań należą między innymi nu-SVM, itp.