tomaszkacmajor.pl

Ze względu na to, że przy operacji oddzielania tła od obrazu w projekcie Flover używam algorytmu Support Vector Machine (SVM), postaram się go dzisiaj przystępnie opisać. To bardzo popularna metoda znana ze swojej skuteczności w dziedzinie Machine Learning. Ma za zadanie jak najlepiej odseparować od siebie elementy różnego typu ze zbioru uczącego, czyli umieścić je w optymalnie oddzielonych grupach.

Jak to wytłumaczyć pięciolatkowi?

O modelu SVM, który w tłumaczeniu trochę dziwnie brzmi: Maszyna Wektorów Nośnych, są nawet całe książki (linki na dole), lecz niestety zazwyczaj w takich formalnych opisach znajduje się bardzo dużo matematyki. Zastanawiałem się jak ten temat w miarę łatwo przekazać. Bardzo podoba mi się pytanie zadane na Reddicie w dziale Machine Learning: Wyjaśnijcie mi proszę Support Vector Machine, żebym zrozumiał gdybym był pięcolatkiem. Proste przykłady są najlepsze, zatem przytoczę następującą odpowiedź:

Wyobraźmy sobie, że na stole są poustawiane piłki o dwóch kolorach. Czerwone po jednej stronie stołu a niebieskie po drugiej. Naszym zadaniem jest takie położenie kijka na stole, żeby oddzielał te dwie grupy. Trzeba to tak zrobić, aby odległość między kijkiem a każdą piłką była możliwie największa. A więc to proste! Jednak po chwili ktoś dokłada niebieską kulkę w miejsce czerwonych. No to teraz nie znajdziemy na świecie takiego kijka, który by nam rozdzielił te dwie grupy. Musiałby być niesamowicie wygięty. Ale na szczęście możemy zrobić pewną sztuczkę: wywrócimy stół, a gdy wszystkie piłki będą w powietrzu przetniemy je kartką papieru ruchem sprawnego wojownika Ninja. W ten sposób rozdzielimy piłki na dwie grupy. Poważni dorośli ludzie na piłki mówią dane, na kijek i kartkę – klasyfikator albo hiperpłaszczyzna, na ułożenie kijka w największej odległości od piłek – optymalizacja, a na wywrócenie stołu – transformacja za pomocą funkcji jądrowych.

Przenoszenie danych do wyższych wymiarów

Przedstawiony problem jest bardzo ogólny i sama klasyfikacja może być wykonywana na wiele różnych sposobów. Support Vector Machine cechuje się, tym że próbuje oddzielić dane funkcją liniową, a jeśli to nie wychodzi przenosi dane do wyższych wymiarów (wywraca stół) i wtedy jeszcze raz próbuje znaleźć taką funkcję. Poniżej świetna wizualizacja tego procesu.

Optymalne oddzielenie grup

Wracając do naszego dwuwymiarowego problemu, należy podkreślić, że linia, która oddziela dane musi znajdować się w optymalnym miejscu. Odległości pomiędzy linią a najbliższymi punkami ze zbiorów powinny być jak najmniejsze. Te odległości to właśnie Support Vectors.

Oczywiście wszystkie te zasady można przełożyć na wyższe wymiary. Przecież zazwyczaj spotykamy się z wektorami cech jakiegoś obiektu (np. superpiksela), które są wielowymiarowe. Gdy mamy do czynienia z danymi, które nie można podzielić używając funkcji liniowej w danej przestrzeni mamy dwie opcje. O wyborze, którą zastosować decydują odpowiednie parametry algorytmu. Albo zignorujemy niektóre punkty uznając je za nieistotnych outsiderów w grupie albo przenosimy dane do jeszcze wyższych wymiarów na co mówi się nawet kernel trick 🙂 Faktycznie, aby tego dokonać, dane muszą być odpowiednio przetransformowane przy użyciu tzw. funkcji jądrowych (kernel functions). Niektóre z nich to np. funkcja wielowymiarowa, funkcja Gaussa, hiperboliczna… Ale o tym już może kiedy indziej.

Implementacja

Poniżej przedstawiam kod uruchamiający naukę klasyfikatora SVM wykorzystujący bibliotekę Accord.MachineLearning.

//    wcześniej zainicjalizowane i zapełnione tablice wejścia i wyjścia klasyfikatora
//    double[][] features;
//    int[] outputs;

// Wybór funkcji jądrowej wykorzystywanej w SVM
IKernel kernel = new Gaussian(sigmaParam);

// Stworzenie klasyfikatora SVM dla danych wejściowych
KernelSupportVectorMachine machine = new KernelSupportVectorMachine(kernel, features[0].Length);

// Inicjalizacja algorytmu nauki 
SequentialMinimalOptimization smo = new SequentialMinimalOptimization(machine, features, outputs);

// Ustawienie parametrów algorytmu - Complexity oznacza dokładność algorytmu
smo.Complexity = 85;

// Uruchomienie algorytmu nauki 
double error = smo.Run();

Uzyskanie odpowiedzi dla nowego wektora double[] FeatureVec będzie wyglądało następująco:

int answer = machine.Compute(FeatureVec)

Zalety SVM

• Znajduje maksymalne odległości (marginesy) pomiędzy grupami punktów
• Efektywne obliczeniowo – złożoność rośnie tylko liniowo wraz z liczbą wymiarów
• Rozwiązuje problemy liniowe jak i nieliniowe

Źródła:
Jeden z bardziej przystępnych wykładów na YT (od 2:27) – https://www.youtube.com/watch?v=YsiWisFFruY
Wykłady o SVM: http://videolectures.net/site/search/?q=support+vector+machine
Książki:
– Neural Networks and Learning Machines – polecam – opisuje wiele metod Machine Learning, SVM również
– An Introduction to Support Vector Machines…
– Learning with Kernels: Support Vector Machines…
Zdjęcia: http://docs.opencv.org/2.4/doc/tutorials/ml/introduction_to_svm/introduction_to_svm.html