Nieliniowy klasyfikator SVM¶

Zaletą liniowych metod klasyfikacji jest prostota uzyskiwanego modelu. Niestety w przypadku rzeczywistych zbiorów danych rzadko kiedy mamy do czynienia z liniową separowalnością próbek w przestrzeni cech. W takich przypadkach stosowanie liniowych metod klasyfikacji nie daje satysfakcjonujących wyników z racji tego, że powierzchnie rozdzielające klasy w przypadku większości rzeczywistych zbiorów danych mają charakter nieliniowy. Na znalezienie takich powierzchni rozdzielających pozwala klasyfikator nieliniowy.

Jednym ze sposobów zapewnienia odpowiednio dobrej jakości klasyfikacji w przypadku zbioru liniowo nieseparowalnego jest nieliniowa transformacja zbioru wektorów wejściowych do przestrzeni o wyższym wymiarze niż przestrzeń wejściowa [Stapor2005], w której to problem klasyfikacyjny daje się rozwiązać w sposób liniowy. Mówimy wtedy, że przekształcenie \(\Phi\) transformujące próbki uczące w przestrzeń wysokowymiarową ma własność \(\Phi\)-separowlaności. Pojęcie to wprowadzamy poniżej:

Definicja 24

Niech dany będzie problem klasyfikacyjny dwuklasowy (dychotomii) ze zbiorem próbek uczących \({{X}_{train}}=\left\{ \left( {{x}_{1}},{{y}_{1}} \right),...,\left( {{x}_{N}},{{y}_{N}} \right)\in {{R}^{p}}\times \left\{ -1,+1 \right\} \right\}\) oraz niech \(\Phi:\mathbb{R}^p\to\mathbb{R}^d\) będzie pewnym nieliniowym odwzorowaniem. Mówimy, że przekształcenie \(\Phi\) ma własność \(\Phi\)-separowalności jeśli dla każdej próbki uczącej:

\[\begin{split}w^T\Phi(x_i)>0 \quad\text{dla}\quad y_i=1,\\ w^T\Phi(x)<0 \quad\text{dla}\quad y_i=-1.\end{split}\]

Uzasadnieniem dla tego podejścia jest poniższe twierdzenie Covera (por. [Ripley1996]).

Twierdzenie 5

Niech \(X=[x_1, \ldots, x_n]\) będzie zbiorem \(n\) próbek w przestrzeni \(\mathbb{R}^{p}\) wymiaru \(p\). Ponadto, niech \(\Phi:\mathbb{R}^p\to\mathbb{R}^d\) będzie nieliniowym odwzorowaniem elementów zbioru \(X\) w przestrzeń \(\mathbb{R}^{d}\) dla \(p\leq d\). Wówczas prawdopodobieństwo, że losowo wybrana dychotomia jest \(\Phi\)-separowalna wynosi

\[P(n,d)=\left(\frac{1}{2}\right)^{n-1}\sum_{i=0}^{n-1}\binom{d-1}{i}.\]

Twierdzenie 5 daje odpowiedź jakie jest prawdopodobieństwo \(P(n,d)\) dychotomii liniowoseparowalnych \(n\)-elementowego zbioru w \(d\) wymiarowej przestrzeni. Zauważmy, że przy \(d\to\infty\) prawdopodobieństwo \(P(n,d)\to 1\).

Podstawowym problemem w omawianym podejściu jest znalezienie takiego nieliniowego odwzorowania \(\Phi\) zbioru danych wejściowych, dzięki któremu obiekty z dwóch klas \(C_1\) oraz \(C_2\) będą liniowo separowalne w nowej \(d\)-wymiarowej przestrzeni.

Podejście to realizuje właśnie nieliniowy klasyfikator SVM wykorzystując koncepcję optymalnej hiperpłaszczyzny rozdzielającej, jednak jej wyznaczenie jest realizowane w nowej wysoko-wymiarowej przestrzeni cech, uzyskanej za pomocą nieliniowego przekształcenia \(\Phi\).

W praktyce dzięki zastosowaniu tak zwanej funkcji jądra nie ma potrzeby podania postaci odwzorowania \(Phi\) i operowania na obrazach w sposób jawny. Wartości funkcji jądra są iloczynami skalarnymi pary wektorów w nowej przetransformowanej przestrzeni cech. Pojęcie to definiujemy poniżej.

Twierdzenie 6 (Mercer, 1909)

Niech \(X\) będzie zwartym podzbiorem \(\mathbb{R}^p\). Przypuśćmy, że \(K\) jest ciągłą symetryczną funkcją taką, że operator całkowy \(T_K\colon L_2(X)\rightarrow L_2(X)\) dany wzorem

\[(T_Kf)(\cdot)=\int_XK(\cdot,x)f(x)dx\]

jest dodatni, tj.

\[\int_{X\times X}K(x,z)f(x)f(z)dxdz\geq 0\]

dla wszystkich \(f\in L_2(X)\). Wówczas możemy rozwinąć \(K(x,z)\) w szereg jednostajnie zbieżny na \(X\times X\) o wyrazach będących funkcjami własnymi \(\Phi_i\in L_2(X)\) operatora \(T_K\), znormalizowanymi w ten sposób, że \(\|\Phi_i\|_{L_2}=1\) oraz związanych dodatnich wartości własnych \(\lambda_j\geq 0\), tzn.

\[K(x,z)=\sum_{j=1}^{\infty}\lambda_j\Phi_j(x)\Phi_j(z).\]

Definicja 25

Funkcją jądra nazywamy każdą funkcję \(K\colon\mathbb{R}^p\times\mathbb{R}^p\rightarrow\mathbb{R}\) spełniającą założenia twierdzenia 6 taką, że

\[K(x_i,x_j)=\Phi(x_i)^T\Phi(x_j).\]

Warunki, jakie musi spełniać funkcja jądra podaje twierdzenie Mercera [Vapnik1998]. W praktyce znana jest postać szeregu funkcji, które spełniają warunki twierdzenia Mercera i mogą być stosowane w charakterze funkcji jądra. Przykładami takich funkcji są między innymi:

Jądro wielomianowe

\[K(x_i,x_j)=(x_i^Tx_j+b)^p,\]

gdzie \(b, p\) są stałymi określającymi odpowiednio wyraz wolny, stopień wielomianu\
Jądro Gaussa

\[K(x_i,x_j)=\exp{\left(-\frac{1}{2\sigma^2}\|x_i-x_j\|^2\right)}\!,\]

gdzie \(\sigma\) jest parametrem rozkładu normalnego.

W przypadku gdy odwzorowanie \(\Phi\) jest identycznością \((\Phi(x)=x)\) funkcja jądra jest postaci

\[K(x_i,x_j)=\Phi(x_i)^T\Phi(x_j)=x_i^Tx_j,\]

co sprowadza nas z powrotem do przypadku klasyfikatora liniowego. Użyta funkcja jądra jest podstawowym parametrem nieliniowego klasyfikatora SVM, w zależności od jej doboru, uzyskuje różne algorytmy klasyfikacji. Algorytm uczenia nieliniowego klasyfikatora SVM składa się z 2 kroków:

wyboru funkcji jądra z odpowiednimi parametrami, a przez to niejawnie wybór nieliniowej transformacji wektorów uczących
konstrukcji optymalnej hiperpłaszczyzny rozdzielającej w nowej przestrzeni cech.

Zadanie dualne optymalizacji dla problemu wyznaczenia optymalnej hiperpłaszczyzny rozdzielającej w przestrzeni wtórnej można sformułować podobnie jak zadanie (?) rozważając iloczyny skalarne próbek uczących w nowej przestrzeni cech. Zadanie to sprowadza się do wyznaczenia mnożników Lagrange’a \(\alpha\) tak, aby maksymalizować następującą funkcję celu:

\[Q(\alpha)=\sum_{i=1}^{N}\alpha_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_iy_jK(x_i,x_j)\]

względem \(\alpha=[\alpha_1\ldots\alpha_{n_{train}}]\) przy ograniczeniach

\[\sum_{i=1}^{N}\alpha_iy_i=0\quad\textrm{ dla } 0\leq\alpha_i\leq C.\]

Wartość współczynników określających OSH dana jest w tym przypadku wzorem

(1)\[w=\sum_{i=1}^{N}\alpha_iy_i\Phi(x_i),\]

gdzie \(\Phi(x_i)\) jest obrazem wektora uczącego poprzez nieliniową funkcję \(\Phi\). Funkcja dyskryminacyjna nieliniowego klasyfikatora SVM określona jest wzorem

\[g(x)=w^T\Phi(x)+w_0,\]

co po wstawieniu (1) sprowadza funkcję dyskryminacyjną do postaci:

\[g(x)=\sum_{i=1}^{N}\alpha_iy_iK(x_i,x_j)+w_0,\]

przy czym wartość \(w_0\) może być obliczona z odpowiedniego warunku Kuhna-Tuckera wg. wzoru

\[w_0=\frac{1}{n_{sv}}\sum_{j=1}^{N}\left[y_j-\sum_{i=1}^{N}\alpha_iy_iK(x_i,x_j)\right]\!,\]

gdzie \(n_{sv}\) jest liczbą wektorów podpierających uzyskanych w procesie uczenia. Proces uczenia nieliniowego klasyfikatora SVM ilustrujemy schematem 13.

Algorytm 14 Nieliniowy algorytm SVM

Dane: zbiór uczący \((x_1,y_i)\in X_{train}\times \{-1,1\}\)

Wyniki: Wektor wag \(w\) oraz przesunięcie \(w_0\) optymalnej hiperpłaszczyzny rozdzielającej OSH w uzyskanej za pomocą przekształcenia \(\Phi\) przestrzeni cech

Wybierz postać funkcji jądra \(K(x_i,x_j)\).
Wyznacz współczynniki Lagrange’a na podstawie wektorów zbioru uczącego \(X_{train}\) rozwiązując problem maksymalizacji funkcji kosztu danej poniższym wzorem:

\[Q(\alpha)=\sum_{i=1}^{N}\alpha_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_iy_jK(x_i,x_j)\]

względem \(\alpha=[\alpha_1,\ldots, \alpha_{N}]\) przy ograniczeniach postaci:

\[\sum_{i=1}^{N}\alpha_iy_i=0,\quad 0\leq\alpha_i\leq C.\]
Na powstawie uzyskanych mnożników Lagrange’a wag \(w\) optymalnej hiperpłaszczyzny rozdzielającej OSH wyraża się wzorem:

\[w=\sum_{i=1}^{N}\alpha_iy_i\Phi(x_i).\]
Wartość przesunięcia \(w_0\) wyrażona jest za pomocą poniższego wyrażenia:

\[w_0=\frac{1}{n_{sv}}\sum_{j=1}^{N}\left[y_j-\sum_{i=1}^{N}\alpha_iy_iK(x_i,x_j)\right]\!,\]

gdzie \(n_{SV}\) jest liczbą wektorów podpierających uzyskanych w procesie uczenia.

Zauważmy, że w przypadku nieliniowego klasyfikatora SVM postaci wektora wag optymalnej hiperpłaszczyzny rozdzielającej również nie podajemy w sposób jawny - wektor ten ma tyle składowych ile wynosi wymiar nowej przestrzeni cech, a tej wartości nie znamy i znać nie musimy dzięki zastosowaniu funkcji jądra. O ile postaci samego wektora wag nie znamy, jednak potrafimy dokonać klasyfikacji obliczając wartość funkcji dyskryminacyjnej \(g\left( x \right)={{w}^{T}}\Phi \left( x \right)+{{w}_{0}}\), w której to wektor wag jest przemnażany skalarnie przez obraz klasyfikowanego wektora, co można wyrazić za pomocą funkcji jądra, mamy bowiem:

\[g\left( x \right)={{\left( \sum\limits_{i=1}^{{{N}}}{{{\alpha }_{i}}{{d}_{i}}\Phi \left( {{x}_{i}} \right)} \right)}^{T}}\Phi \left( x \right)+{{w}_{0}}=\sum\limits_{i=1}^{{{N}}}{{{\alpha }_{i}}{{d}_{i}}\Phi {{\left( {{x}_{i}} \right)}^{T}}\Phi \left( x \right)}+{{w}_{0}}\]

skąd ostatecznie otrzymujemy:

\[g\left( x \right)=\sum\limits_{i=1}^{{{N}}}{{{\alpha }_{i}}{{d}_{i}}K\left( {{x}_{i}},{{x}_{{}}} \right)}+{{w}_{0}}\]

Przykład 15

W tym przykładzie prezentujemy działanie nieliniowego klasyfikatora SVM z jądrem Gaussowkim oraz wielomianowym dla kilku wartości parametrów. Na potrzeby przykładu generujemy zbiór danych uczących XOR. Definiujemy kilka klasyfikatorów z jądrem gaussowkim oraz wielomianowym i testujemy je na wygenerowanym zbiorze testowym. Uzyskane powierzchnie decyzyjne oraz sprawność klasykikacji umieszczamy każdorazowo na wykresie.

import numpy as np
import matplotlib.pyplot as plt
from sklearn import svm
from sklearn.svm import SVC
from sklearn.cross_validation import train_test_split
from matplotlib.colors import ListedColormap

xx, yy = np.meshgrid(np.linspace(-3, 3, 300),np.linspace(-3, 3, 300))
Data = np.random.randn(500, 2)
Classes = np.logical_xor(Data[:, 0] > 0, Data[:, 1] > 0)

TrainData, TestData, TrainClasses, TestClasses = train_test_split(Data, Classes, test_size=.5)

#Parametry przykłądowych klasyfikatorów
klasyfikatory = [
    SVC(kernel="rbf", gamma=3, C=10),
    SVC(kernel="rbf", gamma=0.5, C=0.1),
    SVC(kernel="rbf", gamma=0.05, C=0.5),
    SVC(kernel="poly", degree=2, coef0=0, C=1),
    SVC(kernel="poly", degree=3, coef0=1, C=0.1)]

cm = plt.cm.RdBu
cm_bright = ListedColormap(['#FF0000', '#0000FF'])
#Iterujemy po klasyfikatorach
for svm in klasyfikatory:
    #Uczenie klasyfikatora
    svm.fit(TrainData, TrainClasses)
    #Sprawność
    score = svm.score(TestData, TestClasses)

    #Wykres powierzchni rozdzielających
    Z = svm.decision_function(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, cmap=cm, alpha=.8)

    #Wykres próbek uczących
    plt.scatter(TrainData[:, 0], TrainData[:, 1], c=TrainClasses, cmap=cm_bright)
    #Wykres próbek testowych
    plt.scatter(TestData[:, 0], TestData[:, 1], c=TestClasses, cmap=cm_bright,alpha=0.6)
    #Tytuł wykresu zawierający uzyskaną sprawność i parametry klasyfikatora
    plt.title(str(svm) + ' Score='+str(score))
    plt.show()

Następna część - Test do rozdziału