Uczenie maszynowe i sztuczne sieci neuronowe/Wykład 8

powrót

Wstęp: Maszyny Wektorów Wspierających

W tym wykładzie omówimy jeden z najbardziej popularnych algorytmów uczenia maszynowego: algorytm: Maszyny Wektorów Wspierających (ang. Support Vector Machines (SVM)). Bazuje on an koncepcji rozdzielenia danych należących do różnych klas możliwie dużą ”przerwą”. Aby wprowadzić tą koncepcję zajmiemy się najpierw wypracowaniem pojęcia marginesu.

Marginesy

Zacznijmy od wyrobienia sobie intuicji co do pewności predykcji. Rozważmy regresję logistyczną. Prawdopodobieństwo przynależności do klasy 1 [math]p(y=1|x;\theta )[/math] dane jest tu przez hipotezę [math]h_{\theta }(x) = g(\theta ^{T}x) = \frac{1}{1+ \exp (-\theta ^{T}x)}[/math]. Umówimy się, że klasę 1 przypiszemy danym [math]x[/math] jeśli [math]h_{\theta }(x) \ge 0.5[/math], co odpowiada [math]\theta ^{T}x \ge 0[/math] (w przeciwnym razie klasę 0). Dla wektora [math]x[/math] z klasy 1 jesteśmy tym bardziej pewni jego przynależności do tej klasy, im większe będzie [math]h_{\theta }(x)[/math] czyli, czym większe będzie [math]\theta ^{T}x[/math]. Tak więc dla [math]\theta ^{T}x \gg 0[/math] jesteśmy bardzo pewni, że [math]x[/math] należy do klasy 1, zaś dla [math]\theta ^{T}x \ll 0[/math] jesteśmy bardzo pewni, że [math]x[/math] należy do klasy 0.

Tak więc mając zbiór uczący wydaje się pożądane znalezienie takich parametrów [math]\theta [/math], że dla każdego elementu tego zbioru jeśli należy on do klasy 1 ([math]y^{(j)}=1[/math]) to mamy [math]\theta ^{T}x^{(j)}\gg 0[/math], zaś jeśli należy on do klasy 0 ([math]y^{(j)}=0[/math]) to mamy [math]\theta ^{T}x^{(j)}\ll 0[/math]. Tą intuicję sformalizujemy za chwilę w postaci koncepcji marginesów funkcjonalnych.

Na zagadnienie klasyfikacji możemy też spojrzeć geometrycznie. Na zbiór uczący patrzymy jako na zbiór punktów w przestrzeni wejść oznaczonych etykietkami '1' lub '0'. Konstrukcja klasyfikatora polega na znalezieniu prostej (w dwóch wymiarach, w ogólności hiperpowierzchni) możliwie dobrze separującej elementy oznaczone różnymi etykietkami. Równanie hiperpowierzchni dane jest przez [math]\theta ^{T}x = 0[/math]. Jeśli teraz dostaniemy nowy punkt [math]x[/math] do klasyfikacji to jesteśmy tym bardziej pewni decyzji, im dalej ten punkt leży od owej hiperpowierzchni. Zatem intuicyjnie wydaje się sensowne szukanie takiej hiperpowierzchni, aby elementy zbioru uczącego leżały możliwie daleko od niej. Tą intuicję sformalizujemy za chwilę w postaci koncepcji marginesów geometrycznych.

Uwaga o notacji

Łatwiej będzie myśleć o hiprepowierzchniach jeśli listę parametrów [math]\theta [/math] rozdzielimy na [math]w[/math] i [math]b[/math] tak, że [math]\theta ^{T}x = w^{T}x + b[/math]. W tej wersji notacji nie potrzebujemy też [math]x_{0}=1[/math].

Z kolei łatwiej będzie się liczyło jeśli zmienimy etykietki klas z '0' i '1' na '-1', '1'. Zatem na potrzeby opisu SVM przyjmiemy, że [math]y \in \lbrace -1,1\rbrace [/math].

Zmienimy też hipotezę na funkcję perceptronową. Zamiast zwracać prawdopodobieństwa przynależności [math]x[/math] do klas, które musielibyśmy progować i następnie przydzielać [math]x[/math]-om etykietki zastosujemy funkcję która od razu zwraca etykietki:

[math] h_{w,b}(x) = g(w^{T}x+b) = \left\lbrace \begin{array} {rcl} 1 & dla & w^{T}x+b \ge 0 \\ -1 & dla & w^{T}x+b \lt 0 \\ \end{array} \right. [/math]

Marginesy funkcjonalne i geometryczne

Marginesy funkcjonalne

Dla przykładu ze zbioru uczącego [math](x^{(j)},y^{(j)})[/math] definiujemy margines funkcjonalny jako:

[math] \hat{\gamma }^{(j)} = y^{(j)}(w^{T}x^{(j)} + b) [/math]

Zauważmy, że dla [math]y^{(j)}=1[/math] mamy duży margines funkcjonalny jeśli [math]w^{T}x^{(j)} +b[/math] jest dużą dodatnią liczbą. Podobnie [math]y^{(j)}=-1[/math] mamy duży margines funkcjonalny jeśli [math]w^{T}x^{(j)} +b[/math] jest dużą ujemną liczbą. Ponadto jeśli klasyfikacja jest prawidłowa to margines funkcjonalny jest dodatni. A zatem dobre parametry [math]w[/math] i [math]b[/math] powinny dawać duże wartości marginesów funkcjonalnych. Jedynym problemem takiej definicji marginesów funkcjonalnych jest to, że można je uczynić dowolnie dużymi przez przemnożenie [math]w[/math] i [math]b[/math] przez odpowiednio dużą liczbę. Wydaje się zatem rozsądne aby do powyższej definicji dodać warunek normalizacji zamieniając [math](w,b)[/math] na [math]\left( \frac{w}{||w||},\frac{b}{||w||}\right)[/math].

Definicję marginesu funkcjonalnego dla całego zbioru uczącego otrzymujemy wybierając najgorszy przypadek spośród wszystkich marginesów funkcjonalnych dla poszczególnych elementów zbioru:

[math] \hat{\gamma }= \min _{j=1,\dots ,m} \hat{\gamma }^{(j)} [/math]

Marginesy geometryczne

Margines geometryczny [math]\gamma ^{(j)}[/math] to odległość danego punktu [math]x^{(j)}[/math] od hiperpowierzchni rozdzielającej. Aby ją znaleźć trzeba obliczyć długość wektora prostopadłego do hiperpowierzchni, o który należy przesunąć punkt [math]x^{(j)}[/math] aby znalazł się on na hiperpowierzchni. Jednostkowy wektor prostopadły do hiperpowierzchni ma współrzędne: [math]\frac{w}{||w||}[/math]. Przesunięcie punktu [math]x^{(j)}[/math] w kierunku tego wektora otrzymujemy jako [math]x^{(j)} + \alpha \frac{w}{||w||}[/math]. Jeśli nasz przesunięty punkt ma się znaleźć na hiperpowierzchni separującej to musi spełniać jej równanie (długość tego wymaganego przesunięcia to poszukiwany margines geometryczny [math]\gamma ^{(j)}[/math]). Dla przypadku [math]y^{(j)}=1[/math] mamy:

[math] w^{T}\left(x^{(j)} - \gamma ^{(j)} \frac{w}{||w||} \right) +b=0 [/math]

Rozwiązując to równanie ze względu na [math]\gamma ^{(j)}[/math] dostajemy:

[math] \gamma ^{(j)} = \frac{w^{T}x^{(j)} +b}{||w||} = \left( \frac{w}{||w||} \right)^{T} x^{(j)}+\frac{b}{||w||} [/math]

Przypadek [math]x^{(j)}[/math] z klasy [math]y^{(j)} = -1[/math] wymagałby przesunięcia w kierunku zgodnym z wektorem normalnym do hiperpowierzchni czyli aby uwzględnić oba przypadki jednocześnie możemy zapisać:

[math] \gamma ^{(j)} = y^{(j)}\left( \left(\frac{w}{||w||}\right)^{T}x^{(j)} + \frac{b}{||w||}\right) [/math]

Zauważmy, że dla znormalizowanego [math]w[/math] ([math]||w||=1[/math]) dostajemy, że margines funkcjonalny równy jest marginesowi geometrycznemu. I podobnie jak dla marginesów funkcjonalnych, definiujemy margines geometryczny względem zbioru uczącego jako najgorszy przypadek:

[math] \gamma = \min _{j=1,\dots ,m} \gamma ^{(j)} [/math]

Klasyfikator optymalny pod względem marginesów - podstawowa wersja SVM

Chwilowo zajmiemy się tylko problemami liniowo separowalnymi. W języku wprowadzonych powyżej definicji możemy powiedzieć, że optymalny jest ten klasyfikator, który daje możliwie największy margines geometryczny (wtedy dane ze zbioru uczącego rozseparowane są przerwą o szerokości co najmniej dwóch marginesów). Jak wyznaczyć jego parametry?

Dla ustalonego zbioru uczącego możemy sformułować następujący problem optymalizacyjny:

[math]\begin{matrix} \max _{\gamma ,w,b} \gamma && \\ &\textrm {pod warunkiem:} &y^{(j)}(w^{T}x^{(j)}+b) \ge \gamma , \; j = 1,\dots ,m \\ &&||w|| =1 \end{matrix}[/math]

oznacza to, że chcemy zmaksymalizować [math]\gamma [/math] ale pod warunkiem, że margines funkcjonalny dla każdego przykładu ze zbioru uczącego jest nie mniejszy niż [math]\gamma [/math]. Dodatkowy warunek [math]||w||=1[/math] z jednej strony gwarantuje, że nie osiągniemy poprzedniego warunku przez przeskalowanie parametrów w marginesie funkcjonalnym, a z drugiej strony gwarantuje, że marginesy funkcjonalne i geometryczne są sobie równe. Taka formulacja problemu optymalizacyjnego jest jednak bardzo niewygodna. W szczególności warunek [math]||w||=1[/math] powoduje, że problem nie jest wypukły (cechą wypukłych problemów optymalizacyjnych jest to, ze mają jedno ekstremum, zatem jest to ekstremum globalne). Spróbujmy zatem przeformułować ten problem. Skorzystajmy z zależności między marginesem funkcjonalnym a geometrycznym: [math]\gamma = \hat{\gamma }/||w||[/math]. Rozważmy:

[math]\begin{matrix} \max _{\gamma ,w,b} \frac{\hat{\gamma }(w,b)}{||w||}&& \\ &\textrm {pod warunkiem:} &y^{(j)}(w^{T}x^{(j)}+b) \ge \hat{\gamma }, \; j = 1,\dots ,m\end{matrix}[/math]

czyli chcemy znaleźć parametry maksymalnego znormalizowanego marginesu funkcjonalnego. Pozbyliśmy się dzięki temu niewygodnego warunku [math]||w||=1[/math], ale za to mamy niewygodną funkcję celu. Musimy jeszcze trochę popracować.

Pamiętamy, że skalując współczynniki [math]w[/math] i [math]b[/math] możemy uzyskać dowolną wartość marginesu funkcjonalnego. Weźmy zatem takie skalowanie, żeby dla zadanego zbioru uczącego otrzymać:

[math] \hat{\gamma }=1 [/math]

Możemy takie skalowanie bez zapewnić, bo gdybyśmy znali jakieś [math]w[/math] i [math]b[/math] będące rozwiązaniem problemu optymalizacyjnego, które dają margines funkcjonalny [math]\gamma ^{*}[/math] to dzieląc to [math]w[/math] i [math]b[/math] przez [math]\gamma ^{*}[/math] dostajemy margines funkcjonalny równy 1.

Wstawmy zatem [math]\hat{\gamma }= 1[/math] do formulacji (%i 1):

[math]\begin{matrix} \max _{w,b} \frac{1}{||w||}&& \\ &\textrm {pod warunkiem:} &y^{(j)}(w^{T}x^{(j)}+b) \ge 1, \; j = 1,\dots ,m \end{matrix}[/math]

Zauwżmy, że:

[math] \max _{w,b} \frac{1}{||w||} = \min _{w,b} ||w||=\min _{w,b}||w||^{2} [/math]

Dzięki tej obserwacji możemy nasz problem optymalizacyjny zapisać w wygodnej formie:

[math]\begin{matrix} \min _{w,b} ||w||^{2}&& \\ &\textrm {pod warunkiem:} &y^{(j)}(w^{T}x^{(j)}+b) \ge 1, \; j = 1,\dots ,m \end{matrix}[/math]

Ta postać jest znacznie bardziej dogodna, gdyż funkcja celu jest funkcją wypukłą i w związku z tym posiada dokładnie jedno minimum, zatem jest to minimum globalne. Co więcej do przeprowadzenia takiej minimalizacji wypukłej z więzami istnieje wiele gotowych bibliotek numerycznych.

W zasadzie w tym miejscu można by powiedzieć, że mamy rozwiązany problem.

Zrobimy jednak w tym miejscu dygresję o mnożnikach Lagrangea, które to pozwolą na uzyskanie jeszcze dogodniejszej postaci problemu i rozszerzenia metody SVM na bardzo wielowymiarowe wektory cech.

Mnożniki Lagrangea

Metoda mnożników Lagrangea jest ogólnym sposobem rozwiązywania problemów optymalizacyjnych z więzami. Mogliście już o niej słyszeć np. na mechanice klasycznej.

Dla przypomnienia: Niech nasz problem optymalizacyjny będzie dany przez:

[math]\begin{matrix} \min _{w}f(w)&\\ \textrm {pod warunkiem: }&h_{i}(w) =0, i =1,\dots ,l \end{matrix}[/math]

Aby go rozwiązać budujemy tzw. lagrangian:

[math] \mathcal {L}(w,\beta ) = f(w) + \sum _{i=1}^{l} \beta _{i}h_{i}(w) [/math]

współczynniki [math]\beta _{i}[/math] to właśnie mnożniki Lagrangea. Rozwiązaniem wspomnianego wyżej problemu minimalizacyjnego jest rozwiązanie równań:

[math] \frac{\partial \mathcal {L}}{\partial w_{i}} = 0; \quad \frac{\partial \mathcal {L}}{\partial \beta _{i}} = 0 [/math]

Podejście to można rozszerzyć na problemy optymalizacyjne posiadające więzy w postaci nierówności, tzn takich jak poniższy:

[math]\begin{matrix} \min _{w} = f(w) && \\ \textrm {pod warunkiem:} & g_{i}\le 0 , &i = 1,\dots ,k \\ & h_{i} (w) = 0 ,& i = 1,\dots , l \end{matrix}[/math]

Aby rozwiązać ten problem musimy najpierw zdefiniować uogólniony lagrangian z mnożnikami [math]\alpha _{i}[/math] i [math]\beta _{i}[/math]:

[math] \mathcal {L}(w,\alpha ,\beta ) = f(w) + \sum _{i=1}^{k} \alpha _{i}g_{i}(w) + \sum _{i=1}^{k} \beta _{i}h_{i}(w) [/math]

Rozważmy wielkość [math]\theta _{p}(w)[/math] zdefiniowaną:

[math] \theta _{p}(w) = \max _{\alpha ,\beta :\alpha _{i} \ge 0} \mathcal {L}(w,\alpha ,\beta ) [/math]

Ma ona tę własność, że jeśli któryś z warunków nie jest spełniony to wybucha ona do nieskończoności (np. dla [math]g_{3}(w)\gt 0[/math] maksymalizacja [math]\theta _{p}[/math] po parametrze [math]\alpha _{3}[/math] dałoby [math]\alpha _{3} = \infty [/math] a co za tym idzie cały [math]\mathcal {L} = \infty [/math]. Podobnie dla naruszenia warunku [math]h_{i}(w) = 0[/math] dla jakiegoś [math]i[/math] spowoduje, że odpowiednie [math]\beta _{i} = \infty [/math] i [math]\mathcal {L} = \infty [/math].) Natomiast jeśli wszystkie warunki są spełnione to [math]\theta _{p} = f(w)[/math]:

[math] \theta _{p} = \left\lbrace \begin{array}{ll} f(w)& \textrm {jesli } w \textrm { spełnia warunki} \\ \infty &\textrm {w przeciwnym wypadku} \end{array} \right. [/math]

Zatem rozwiązanie naszego pierwotnego problemu [math]p^{*}[/math] może być zapisane w zwarty sposób tak:

[math] p^{*} = \min _{w} \theta _{p}(w) = \min _{w} \max _{\alpha ,\beta : \alpha _{i }\ge 0 } \mathcal {L}(w,\alpha ,\beta ) [/math]

A teraz przyjrzyjmy się innemu problemowi, który nazywa się dualnym do pierwotnego. Definiujemy wielkość [math]\theta _{d}[/math]:

[math] \theta _{d} (\alpha ,\beta ) = \min _{w} \mathcal {L}(w,\alpha ,\beta ) [/math]

O ile wielkość [math]\theta _{p}[/math] była wartością lagrangianu zmaksymailzowanego względem [math]\alpha [/math] i [math] \beta [/math] to wielkość [math]\theta _{d}[/math] jest wartością tego lagrangianu zminimalizowanego po [math]w[/math]. Dualny problem optymalizacyjny polega na znalezieniu takiego [math]d^{*}[/math], że:

[math] d^{*} = \max _{\alpha ,\beta : \alpha _{i}\ge 0} \theta _{d} = \max _{\alpha ,\beta : \alpha _{i}\ge 0} \min _{w} \mathcal {L}(w,\alpha ,\beta ) [/math]

Widać, że problem pierwotny różni się od dualnego kolejnością operacj max i min. Można też zauważyć, że w ogólności zachodzi relacja:

[math] d^{*} = \max _{\alpha ,\beta : \alpha _{i}\ge 0} \min _{w} \mathcal {L}(w,\alpha ,\beta ) \le \min _{w} \max _{\alpha ,\beta : \alpha _{i}\ge 0} \mathcal {L}(w,\alpha ,\beta ) =p^{*} [/math]

Pod pewnymi warunkami zachodzi nawet coś ciekawszego a mianowicie:

[math] d^{*} = p^{*} [/math]

czyli zamiast rozwiązywać pierwotny problem, możemy rozwiązać problem dualny i stwierdzić, że jest on rozwiązaniem problemu pierwotnego. Równość ta zachodzi pod następującymi warunkami: [math]f[/math] i [math]g_{i}[/math] muszą być wypukłe, zaś [math]h_{i}[/math] muszą być afiniczne (tzn. postaci [math]h_{i}(w) = a_{i}^{T}w + b_{i}[/math]), oraz dla pewnego [math]w[/math] zachodzi [math]g_{i}(w) \lt 0[/math]. Pod tymi warunkami istnieją [math]w^{*},\alpha ^{*},\beta ^{*}[/math], dla których [math]p^{*}=d^{*}=\mathcal {L} (w^{*},\alpha ^{*},\beta ^{*})[/math]. Ponadto [math]w^{*},\alpha ^{*},\beta ^{*}[/math] spełniają warunki Karush-Kuhn-Tucker'a (KKT):

[math]\begin{matrix} \frac{\partial }{\partial w_{i}} \mathcal {L} (w^{*},\alpha ^{*},\beta ^{*})&=& 0 , \quad i = 1,\dots ,k \\ \frac{\partial }{\partial \beta _{i}} \mathcal {L} (w^{*},\alpha ^{*},\beta ^{*})&=& 0 , \quad i = 1,\dots ,l \\ \alpha _{i}^{*} g_{i}(w^{*}) &=&0, \quad i = 1,\dots ,k \\ g_{i}(w^{*}) &\le & 0, \quad i =1,\dots ,k \\ \alpha ^{*} &\ge & 0, \quad i=1,\dots ,k \end{matrix}[/math]

Prawdziwe jest też twierdzenie odwrotne. Jeśli jakieś parametry [math]w^{*},\alpha ^{*},\beta ^{*}[/math] spełniają warunki KKT to są też rozwiązaniem problemu pierwotnego i dualnego. Zwróćmy uwagę na warunek (%i 4). Mówi on tyle, że jeśli dla jakiegoś [math]i[/math] [math]\alpha_{i}\gt 0[/math] to [math]g_{i}(w^{*}) =0[/math]. Warunek ten przyda się później do pokazania, że wektorów wspierających w SVM jest niewiele i do pokazania zbieżności wydajnego algorytmu budowania SVM.