Uczenie Maszynowe od podstaw - SVM

W świecie uczenia maszynowego Support Vector Machine (SVM) to jedna z najpopularniejszych metod klasyfikacji danych, szczególnie skuteczna przy rozdzielaniu obserwacji przynależących do dwóch klas. W tym wpisie przedstawię, jak korzystając z interaktywnego skryptu LiveScript w MATLAB-ie można zrozumieć działanie metody SVM oraz przeprowadzić własne eksperymenty, aby lepiej zgłębić tę technikę. Prezentowany skrypt wykorzystuję m.in. na wykładzie z przedmiotu „Uczenie Maszynowe w Internecie Rzeczy” na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej.

Aby ułatwić naukę, do artykułu dołączyłem serię nagrań, które prezentują działanie LiveScript oraz zaimplementowane funkcjonalności. Po obejrzeniu tych nagrań dowiesz się, jak wyświetlać dane oraz samodzielnie eksperymentować z parametrami SVM.

Przykładowy zbiór danych

Na początku skrypt przedstawia przykładowy, liniowo separowalny zbiór danych zawierający obserwacje dwóch klas (oznaczone kolorami niebieskim oraz czerwonym).

Następnie, aby lepiej zrozumieć naturę tych danych, wyświetlamy przykładowe punkty reprezentujące obserwacje obu klas. Każdy punkt posiada dwie cechy, które mogłyby być przykładowo parametrami przy detekcji, czy dany mail jest SPAM-em (np. średnia liczba wystąpień wyrazów danej kategorii w treści analizowanej wiadomości).

Jak rozdzielić obie klasy?

W dalszej części skryptu mamy możliwość manualnego dopasowania hiperpłaszczyzny (prostej linii) rozdzielającej te dwie klasy. Dostrajając parametry równania, możemy zaobserwować, jak wpływają one na margines separujący, którego szerokość chcemy maksymalizować.

Możemy także sprawdzić na wykresie zmianę szerokości marginesu w zależności od nachylenia prostej. Widać na nim maksimum szerokości, które jest kluczowe dla efektywnej klasyfikacji.

Support Vector Machine – Maszyna Wektorów Podpierających

Następnie możemy sprawdzić, jak SVM automatycznie dopasowuje optymalną hiperpłaszczyznę do tego samego zbioru danych, a także porównać ją z hiperpłaszczyzną manualnie dopasowaną przez użytkownika.

Jak można zauważyć, metoda SVM znalazła lepsze rozwiązanie – było ono widoczne na poprzednim nagraniu jako maksimum szerokości marginesu. Nasza hiperpłaszczyzna jest jednak niewiele mniejsza, poszło nam więc całkiem dobrze.

Na nagraniu (na granicy marginesu po obu stronach) widoczne są trzy punkty z podwójną czarną obwódką – są to tak zwane punkty podpierające. Znajdują się one najbliżej hiperpłaszczyzny separującej i to od nich metoda bierze swoją nazwę.

SVM do znalezienia optymalnej hiperpłaszczyzny wykorzystuje wyłącznie punkty podpierające, podczas gdy inne punkty, które nie leżą blisko marginesu, nie wpływają na model. Dlatego punkty podpierające są tak istotne – mają bezpośredni wpływ na przebieg hiperpłaszczyzny, co decyduje o jakości klasyfikacji.

Ponadto, hiperpłaszczyzna jest zawsze umieszczona pośrodku marginesu separującego, co zapewnia równą odległość od najbliższych punktów obu klas (tzw. wektorów podpierających).

Brak separacji liniowej

Co zrobić, jeśli mamy do czynienia z danymi, których nie da się rozdzielić prostą lub hiperpłaszczyzną? Możemy wprowadzić karę za naruszenie marginesu lub nawet błędną klasyfikację – w MATLAB-ie jest to parametr BoxConstraint.

Parametr ten kontroluje kompromis między maksymalizacją marginesu, a minimalizacją błędów klasyfikacji. Większa wartość oznacza bardziej restrykcyjne dopasowanie do danych, co może prowadzić do nadmiernego dopasowania (overfittingu), ale nie zawsze musi. Sterując wartością tego parametru, możemy wpływać na orientację i rozmieszczenie hiperpłaszczyzny, co pozwala na lepsze dostosowanie do danych, w tym również do danych odstających.

Wprowadzenie w nieliniowe funkcje jądra

BoxConstraint to nie jedyny sposób na radzenie sobie z brakiem możliwości liniowej separacji klas w zbiorze danych. Nieliniowe funkcje jądra pozwalają na wprowadzenie liniowości tam, gdzie początkowo może to być trudne do wyobrażenia. Wszystko dzięki dodaniu nowych cech, które odpowiednio przekształcają analizowane dane. Zobaczmy, jak to działa na prostym przykładzie nieliniowo separowalnego zbioru.

Jak można zauważyć na powyższym nagraniu, wprowadzenie nowej cechy może sprowadzić zbiór danych do postaci liniowo separowalnej. Zastosowanie nieliniowych funkcji można przećwiczyć w kolejnym punkcie, gdzie mamy do czynienia z bardziej skomplikowanym przykładem – wykorzystując funkcję sinus z odpowiednimi parametrami. Zachęcam do samodzielnej próby dostrojenia parametrów funkcji tak, by umożliwić liniową separację – uzyskanymi wartościami parametrów można podzielić się w komentarzu.

Nieliniowe funkcje jądra są domyślnie zaimplementowane w MATLAB-owej funkcji fitcsvm, którą w prezentowanym skrypcie wykorzystuję do wizualizacji działania algorytmu SVM. Poza liniowym jądrem, które wykorzystywaliśmy do tej pory, możemy wykorzystać nieliniowe jądro wielomianowe (ang. polynomial) oraz jądro RBF, których działanie prezentuje poniższe nagranie. Warto zwrócić uwagę, że działanie każdego jądra można modyfikować za pomocą odpowiednich parametrów (PolynomialOrder dla jądra wielomianowego oraz KernelScale dla jądra RBF).

Eksperymenty ze zbiorami danych

Aby nabrać intuicji oraz zdobyć doświadczenie w posługiwaniu się metodą SVM w zagadnieniach uczenia maszynowego, warto nie tylko zapoznać się z działaniem funkcji jądrowych w praktyce, ale także wykonać eksperymenty na większej liczbie zestawów danych – najlepiej jak najbardziej zróżnicowanych. Prezentowany skrypt umożliwia także ten aspekt. Możemy przetestować działanie SVM na syntetycznych zbiorach (koncentryczne okręgi, spirale, znane zagadnienie XOR) oraz na części danych ze zbioru Fisher's Iris.

Overfitting

Jeden przykład z powyższego nagrania – wykorzystanie jądra RBF przy małym parametrze KernelScale (dla zbioru XOR), pokazuje zjawisko overfittingu, czyli nadmiernego dopasowania modelu do danych treningowych. Możemy na nim zauważyć, że przy takich parametrach algorytmu udaje nam się uzyskać 100% dokładności, jednak finalny wygląd obszarów klasyfikowanych jako nie-SPAM (kolor niebieski) zdecydowanie nie wygląda tak, jakbyśmy tego oczekiwali.

Jak sobie poradzić ze zjawiskiem overfittingu? Przede wszystkim warto podzielić zbiór danych na zbiór treningowy, na którym model uczy się zagadnienia klasyfikacji, oraz na zbiór testowy – taki, którego model przy dostrajaniu swoich parametrów nie widział, a na którym możemy sprawdzić, czy nie dopasował się zbyt mocno do obserwacji ze zbioru treningowego. Ważna jest także walidacja krzyżowa, która pomaga w ocenie zdolności modelu do generalizacji i w optymalnym doborze parametrów. Więcej o przeciwdziałaniu zjawisku overfittingu można przeczytać tutaj oraz tutaj.

Podsumowanie

Prezentowany w tym wpisie LiveScript jest dostępny tutaj. Istnieje możliwość uruchomienia udostępnionych plików w MATLAB Online, do czego zachęcam – jest to bardzo wygodny sposób uruchamiania MATLAB-owych interaktywnych skryptów.

Poniżej prezentuję przykład wywołania funkcji fitcsvm, dla której:

· X to macierz cech obserwacji ze zbioru treningowego,
· y to etykiety (klasy) dla każdej obserwacji (w naszym przypadku, może to być SPAM lub nie-SPAM),
· użyto wielomianowej funkcji jądra trzeciego stopnia (‘PolynomialOrder’ = 3),
· wartość funkcji kary za naruszenie ograniczeń wynosi 10 000 (‘BoxConstraint’ = 1e5)

SVMModel = fitcsvm(X, y, 'KernelFunction', 'polynomial', 'PolynomialOrder', 3, 'BoxConstraint', 1e5)

Na koniec warto wspomnieć o alternatywie do ręcznego wywoływania funkcji fitcsvm – aplikacji Classification Learner, która automatyzuje wiele etapów pracy z klasyfikatorami, ułatwia pracę z danymi oraz wizualizacją wyników. Szczegóły dotyczące aplikacji, przykłady wykorzystania oraz nagranie wprowadzające dostępne są tutaj oraz tutaj.

Kluczowe wnioski na temat SVM, które warto zapamiętać po przeczytaniu tego wpisu:

· SVM znajduje optymalną hiperpłaszczyznę, która maksymalizuje margines między klasami, co zapewnia skuteczną klasyfikację,
· w przypadku danych nieliniowo separowalnych stosujemy funkcje jądra, takie jak jądro wielomianowe czy RBF (aby odpowiednio przekształcić przestrzeń cech),
· parametr BoxConstraint pozwala kontrolować kompromis między maksymalizacją marginesu a minimalizacją błędów klasyfikacji (co ma wpływ na dopasowanie modelu),
· ważnym wyzwaniem jest overfitting, który można kontrolować przez walidację krzyżową i odpowiedni podział danych na zbiory treningowe i testowe.

W następnym wpisie omówię kolejną popularną metodę klasyfikacji danych – drzewa decyzyjne.

Autor: Michał Hałoń