łączenie równoległe modeli klasyfikacji otrzymanych metodą

Michał Trzęsiok

ŁĄCZENIE RÓWNOLEGŁE MODELI KLASYFIKACJI OTRZYMANYCH METODĄ WEKTORÓW NOŚNYCH Wprowadzenie Konstruowanie funkcji klasyfikujących przez łączenie wielu modeli skła­ dowych stanowi główny nurt badań naukowych nad metodami klasyfikacji w ciągu ostatnich pięciu lat. Powodem tak dynamicznego rozwoju metod agre­ gujących są ich dobre własności, gdyż klasyfikacja danych na podstawie modeli zagregowanych daje na ogół mniejsze błędy klasyfikacji niż którakolwiek poje­ dyncza funkcja dyskryminująca, będąca składową modelu zagregowanego. Narzędziem, które umożliwia wyjaśnienie przewagi modeli łączonych nad po­ jedynczymi, a także pozwala na porównywanie oraz kreowanie nowych metod łączenia modeli, jest analiza błędu klasyfikacji podlegającego dekompozycji na obciążenie, wariancję i szum. Zakładamy, że w zadaniu dyskryminacji dany jest zbiór uczący w postaci D = {(xl , y ‘),...,(xN, y /v)}, gdzie x‘ e

oraz y ‘ - realizacje zmiennej opi­

sującej klasę obiektu. Modele składowe / , , . . . , / fl są otrzymywane w wyniku zastosowania metody klasyfikacji do B prób uczących D X, . . . , D B, wyodrębnio­ nych z podlegającego dyskryminacji zbioru uczącego D. Jedną z metod agregacji jest metoda łączenia równoległego modeli ( bag­ ging ) zaproponowana przez Breimana [1], w której obserwacje do każdej z prób uczących (bootstrap sam ples) są losowane ze zwracaniem ze zbioru D, przy czym liczebność każdej próby jest równa liczebności zbioru D, równa N, a prawdopodobieństwo wejścia do próby dla każdej obserwacji jest w każdym losowaniu stałe, równe — . W kolejnym kroku są wyznaczane funkcje dyskryminujące

N f B , odpowiadające próbom uczącym D

,D B w ten sposób,

że wartości parametrów modelu składowego /■ wybierane są tak, aby błąd klasyfikacji był najmniejszy. Zagregowany model końcowy / * łączy wskaza­ nia modeli składowych zgodnie z zasadą majoryzacji:

130

Michał Trzęsiok

/ * (x) = arg max

] I ( j ) (x) = k)

( 1)

Pojedyncze modele otrzymane metodą wektorów nośnych mają dobre własności statystyczne: są odporne na występowanie w zbiorze uczącym ob­ serwacji błędnie sklasyfikowanych oraz charakteryzują się dużym stopniem uogólnienia wyznaczanej funkcji dyskryminującej. W opracowaniu przedsta­ wiono próbę empirycznego zweryfikowania hipotezy, iż model klasyfikacji zbudowany na podstawie metody łączenia równoległego wielu modeli uzyska­ nych metodą wektorów nośnych, generuje mniejsze błędy klasyfikacji niż każdy z pojedynczych modeli składowych.

1. Metoda wektorów nośnych Metoda wektorów nośnych (SVM - Support Vector Machines) polega na nieliniowym przekształceniu oryginalnej przestrzeni danych w przestrzeń unitarną Z o dużo większym wymiarze, w której obserwacje są rozdzielane hiperpłaszczyznami. Ze względu na nieliniowość transformacji przestrzeni da­ nych, liniowemu rozdzieleniu danych w nowej przestrzeni cech odpowiada nieliniowa ich dyskryminacja w przestrzeni pierwotnej. Oznaczmy przez 0 , którego wartość ustala użytkownik, określa kompromis między dokładnością dopasowania funkcji dyskryminującej do da­ nych ze zbioru uczącego a zdolnością uogólniania modelu, rozumianą jako po­ prawne klasyfikowanie nowych obiektów ze zbioru rozpoznawanego. Zmienne > 0 zostały wprowadzone w celu umożliwienia błędnego klasyfikowania niektórych obserwacji ze zbioru uczącego, co zwiększa odporność metody na występowanie szumu w tym zbiorze. Rozwiązań zadania (4) poszukujemy metodą mnożników Lagrange’a, przekształcając problem w postać dualną. Otrzymane rozwiązanie (optymalna hiperpłaszczyzna rozdzielająca klasy) definiuje funkcję dyskryminującą w po­ staci: (5) która jest opisana tylko przez te wektory x' ze zbioru uczącego, dla których odpowiadające im współczynniki Lagrange’a w rozwiązaniu zadania optymali­ zacyjnego (4) są większe od zera ( a , > 0 ) . Obserwacje te nazywamy wektora­ mi nośnymi. Postać funkcji transformującej ę nie musi być znana. Wystarczy bowiem postać iloczynu skalarnego K(u, v) = ę {a ) • ę { \ ) w przestrzeni Z. W metodzie wektorów nośnych najczęściej wykorzystuje się funkcje z rodziny funkcji jądrowych: a)

Gaussa:

K(u, v) = exp(-^||u - v||2) ,

b)

wielomianową:

K(u, v) = y(u ■v + S )d , d - 1,2,...,

c)

sigmoidalną:

K(u, v) = tanh(^u • v + S ) ,

d)

liniową:

K(u, v) = u • v.

Wobec powyższych uwag funkcję dyskryminującą można zapisać w postaci: (6)

gdzie Isv ={/e{l,...,W}:a(. >0}. Zatem nieliniowe przekształcenie ę pierwotnej przestrzeni danych jest realizowane w algorytmie metody przez pewną funkcję jądrową, definiującą iloczyn skalamy w pewnej nowej przestrzeni cech. Jak wiadomo, zdefiniowanie iloczynu skalarnego w pewnej przestrzeni (zdefiniowanie przestrzeni unitarnej) implikuje możliwość liczenia normy wektorów w tej przestrzeni, odległości

132

Michał Trzęsiok

między punktami oraz kątów między wektorami - podstawowe narzędzia do określania miar podobieństwa między obiektami. Wybór funkcji jądrowej defi­ niującej iloczyn skalarny w pewnej przestrzeni, a także wybór wartości para­ metrów tej funkcji oznacza więc ustalenie miary podobieństwa obiektów ze zbioru uczącego i ma istotne znaczenie dla postaci oraz jakości otrzymanej kla­ syfikacji. Ponadto jakość dyskryminacji zależy również od wartości parametru C metody ( C > 0). Jak zostało wykazane w [6], na ogół najmniejszy błąd klasy­ fikacji występuje przy zastosowaniu metody wektorów nośnych z wielo­ mianową funkcją jądrową i stopniem wielomianu nieprzekraczającym 5.

2. Dekompozycja błędu klasyfikacji W dalszych rozważaniach wykorzystamy dekompozycję błędu klasyfika­ cji dla modeli zagregowanych na obciążenie, wariancję i szum, pochodzącą od Domingosa [4]. Niech t będzie rzeczywistą klasą obiektu x. Jeżeli oznaczymy przez f (x) wskazane klasy wyznaczone przez metodę dyskryminacji dla obiektu x, to błąd klasyfikacji takiego modelu będzie równy E ,[L (t,f(x ))], gdzie:

jest funkcją straty. Jednakże wskazanie klasy / (x) nie jest funkcją determini­ styczną, gdyż zależy od zbioru uczącego Dj, który został wykorzystany w meto­ dzie do wyznaczenia funkcji dyskryminującej f więc / ( x ) = f D ( x ) . Biorąc więc jednocześnie pod uwagę losowość wynikającą zarówno z wyboru zbioru uczącego, jak i z wyboru obiektu (x, t) ze zbioru testowego, średni błąd klasyfi­ kacji można zapisać jako: (8 ) Celem tej części opracowania jest przedstawienie analizy średniego błędu klasyfikacji () oraz jego dekompozycja na obciążenie, wariancję i szum. Do zdefiniowania składowych błędu klasyfikacji potrzebne są pojęcia: „klasyfikator optymalny” oraz „klasyfikator główny”. Klasyfikatorem optymalnym będziemy nazywać taką funkcję dyskrymi­ nującą j ;*(x) = f { \ ) , która minimalizuje błąd klasyfikacji: (9)

ŁĄCZENIE RÓWNOLEGŁE MODELI...

133

Zatem dla każdego punktu x, klasyfikator optymalny można zapisać jako: v*(x) = arg niin £ ,[/,(/,£ )]

(10)

Klasyfikator główny definiujemy jako funkcję dyskryminującą, minima­ lizującą dla każdego punktu x, wartość oczekiwaną funkcji straty po wszystkich próbach uczących D ],..., D H: W = arg min E Dj [ L ( f j (x), A:)]

(11)

Zatem klasyfikator główny wskazuje klasę dla obiektu x zgodnie z najczęściej występującym wskazaniem klasyfikatorów składowych Obciążenie w punkcie x definiujemy jako wartość funkcji straty dla kla­ syfikatora optymalnego i głównego: B(x) = L { y , y n')

(12)

Wariancję w punkcie x definiujemy jako wartość oczekiwaną funkcji straty między klasyfikatorem głównym a klasyfikatorami składowymi: F ( x) = £ dJ A / , « , / " ) ]

(13)

Wariancja pokazuje, jak bardzo wskazania klasyfikatorów składowych różnią się w zależności od zbioru uczącego Dj. Szum w punkcie x definiujemy jako: N (x ) = E , [ L ( t , / ) }

(14)

Przy tak zdefiniowanych składowych (12), (13) i (14) błędu klasyfikacji, można przedstawić jego dekompozycję w postaci: E Dj [E ,[L (t , f D (x))]] = c,JV(x) + B (x) + c 2V (x)

(15)

Powyższa dekompozycja nie jest addytywna, gdyż stała c, przyjmuje wartość ujemną dla obciążonych obserwacji x [4], Metoda łączenia równoległego jest techniką redukującą przede wszyst­ kim wariancję modelu. Ponieważ metoda wektorów nośnych jest skonstruowa­ na tak, iż jej algorytm zawiera mechanizm redukcji wariancji, dlatego uzasad­ niona wydaje się potrzeba empirycznego sprawdzenia, czy model zagregowany, uzyskany metodą łączenia równoległego funkcji dyskryminujących wyznaczo­ nych metodą wektorów nośnych, będzie się charakteryzować mniejszym błę­ dem klasyfikacji niż każdy z modeli składowych. W dalszej analizie porównamy średnie błędy klasyfikacji wyliczone dla zbioru testowego w przypadku: a) najlepszego pojedynczego modelu (SVM ),

134

Michał Trzęsiok

b) modelu zagregowanego (AGRSt\t), otrzymanego w wyniku zastosowania metody łączenia równoległego z minimalizacją błędu klasyfikacji na pró­ bach uczących D t.

3. Procedura badawcza Procedura badawcza obejmuje następujące kroki: 1. Zbiór danych jest dzielony na dwie części - zbiór uczący D i zbiór testowy S w stosunku 2:1. Zbiór testowy posłuży do wyznaczenia średnich błędów klasyfikacji dla pojedynczych modeli oraz modelu zagregowanego, w celu ich porównania. 2. Ze zbioru uczącego jest losowanych ze zwracaniem B = 100 prób uczących D ,,..., D b , przy czym liczebność każdej próby jest równa liczebności zbio­ ru D, równa N, a prawdopodobieństwo inkluzji dla każdej obserwacji jest w każdym losowaniu stałe, równe — . N

3.

Dla każdej próby uczącej D . oraz każdego układu parametrów (d, y, C ) , gdzie d to stopień wielomianowej funkcji jądrowej, przebiega zakres od 2 do 4, Y e {0,5; 5} oraz C e {0,1; 10; 100}, wyznaczana jest, metodą wekto­

4.

rów nośnych, funkcja dyskryminująca fj (pojedynczy model SVM). Spośród wszystkich wyznaczonych funkcji dyskryminujących wyodrębnio­ ne zostają: a) model, któremu odpowiada najmniejszy średni błąd klasyfikacji, b) grupa modeli

takich, że funkcja /"""En charakteryzuje się

najmniejszym błędem klasyfikacji na próbie uczącej

D j , wśród

wszystkich funkcji dyskryminujących wyznaczonych dla tej próby. 5. Zbiór testowy S zostaje poddany dyskryminacji klasyfikatorami z punktu 4a) oraz 4b). 6. Wskazania klas zbioru funkcji z punktu 4b) zostają połączone w jeden model zagregowany, zgodnie z zasadą majoryzacji. 7. Na podstawie wskazań klas z punktu 6. zostają wyznaczone (dla modelu zagregowanego): klasyfikator główny, średni błąd klasyfikacji oraz obcią­ żenie i wariancja. 8. Dla najlepszego modelu pojedynczego, zidentyfikowanego w punkcie 4a), zostaje wyznaczony średni błąd klasyfikacji, obciążenie i wariancja na zbio­ rze testowym S. 9. Obliczone błędy klasyfikacji oraz jego składowe, dla najlepszego modelu pojedynczego oraz modelu zagregowanego, przedstawia tab. I.

135

ŁĄCZENIE RÓWNOLEGŁE MODELI..,

Ponieważ dla zbiorów danych rzeczywistych wyznaczenie wartości szu­ mu jest trudne (gdyż dysponując jedynie obserwacjami zaburzonymi szumem, nie znamy rzeczywistej przynależności danego obiektu do klas), będziemy roz­ ważać dekompozycję średniego błędu klasyfikacji na dwie składowe - obciąże­ nie i wariancję. Tym samym wartości obciążenia będą nieco zawyżone.

4. Zbiór danych i wyniki analizy Metodę łączenia równoległego składowych modeli otrzymanych metodą wektorów nośnych zilustrowano na zbiorze danych Vehicle, standardowo wy­ korzystywanym do badania i porównywania własności metod wielowymiarowej analizy statystycznej. Zbiór ten zawiera 846 obserwacji charakteryzowanych przez 19 zmiennych, z których jedna opisuje klasę obiektu. Liczba klas jest równa 4. Zbiór Vehicle zawiera dane rzeczywiste i pochodzi z ogólnodostępnej bazy „UCI Repository O f Machine Learning Databases” zlokalizowanej na Uniwersytecie Kalifornijskim1. Do obliczeń wykorzystano program kompute­ rowy napisany przez autora w języku pakietu statystycznego R z wykorzysta­ niem dodatkowej biblioteki e l 0 7 1 , zawierającej implementację metody wekto­ rów nośnych. Do zbioru danych Vehicle zastosowano procedurę opisaną powyżej. Tabela I Średni błąd klasyfikacji i jego składowe dla najlepszego modelu pojedynczego oraz modelu zagregowanego, wyznaczone na zbiorze testowym zbioru danych Vehicle (zł) Pojedynczy model

Model zagregowany

SVM

AGRsyM

Średni błąd klasyfikacji

0,19

0,17

Obciążenie

0,12

0,11

Wariancja

0,13

0,12

Nazwa

Tabela 1 przedstawia średnie Wędy klasyfikacji wyliczone na zbiorze te­ stowym dla najlepszego pojedynczego modelu (SVM) oraz modelu zagregowa­ nego (AGR svm), otrzymanego w wyniku zastosowania metody łączenia równo­ ległego z minimalizacją błędu klasyfikacji na próbach uczących D y.

1 D o s tę p n e p rz e z : ft p :/ / fip .ic s .u c i.e d u / p u b / m a c liin e - le a n iin g - c la u ib a s e s

lm p :/ / iv u \ v .ic s .u e i e d u '- i i i l e a n i 'M [ .R e p o s it o r y .Iilin l

136

Michał Trzęsiok

Dla analizowanego zbioru danych łączenie wielu modeli składowych w jeden końcowy model zagregowany polepszyło jakość klasyfikacji obserwa­ cji ze zbioru testowego - błąd klasyfikacji modelu zagregowanego jest mniejszy od tegoż błędu dla najlepszego z pojedynczych modeli składowych. Łączenie modeli spowodowało zmniejszenie zarówno wariancji, jak i obciążenia.

Podsumowanie Koncepcja Breimana polepszania jakości dyskryminacji przez metody łą­ czenia równoległego wielu modeli składowych została pozytywnie zweryfiko­ wana metodami empirycznymi, w przypadku zastosowania do konstrukcji modeli składowych metody wektorów nośnych. Powyższy wniosek jest zgodny z wynikami badań nad metodą łączenia równoległego modeli składowych w postaci drzew klasyfikacyjnych. Jednak polepszenie jakości klasyfikacji nie było znaczne. Wydaje się, iż lepsze rezultaty będzie można osiągnąć, jeśli wy­ korzysta się zmodyfikowaną metodę agregacji, a mianowicie adaptacyjną me­ todę łączenia równoległego (adaptive bagging ). Modyfikacja ta polega na tym, aby przy wyborze funkcji składowych nie kierować się minimalizacją błędu klasyfikacji na danej próbie uczącej, lecz na pewnej próbie testowej, zawierają­ cej obiekty, które nie uczestniczyły w procesie wyznaczania zbioru klasyfikato­ rów. Do stworzenia prób testowych można wykorzystać konsekwencje losowa­ nia obiektów do próby ze zwracaniem, polegające na tym, że w każdej próbie uczącej D j znajduje się około 63,2% obserwacji ze zbioru uczącego D. Pozo­ stałe 36,8% obserwacji można łatwo zidentyfikować i utworzyć z nich próbę testową Tj {out-of-bag), T} - D \ D j , odpowiadającą próbie uczącej D j .

Literatura 1.

Breiman L.: Bagging Predictors. „Machine Learning” 1996, nr 24.

2.

Cristianini N., Shawe-Taylor J.: An Introduction to Support Vector Ma­ chines (and Other Kernel-Based Learning Methods). Cambridge University Press, Cambridge 2000.

3.

Dietterich T.G., ValentiniG.: Bias-Variance Analysis o f Support Vector M achines fo r the Development o f SVM -Based Ensemble Methods. „Journal o f Machine Learning Research” 2000.

4.

Domingos P.: A Unified Bias-Variance Decomposition and Its Applications. Proceedings of the Seventeenth International Conference on Machine Learning, Stanford 2000.

137 ŁĄCZENIE RÓWNOLEGŁE MODELI...

5.

Smolą A., Scliölkopf B.: Learning with Kernels. Support Vector Machines, Regularization. Optimization, and Beyond. MIT Press, Cambridge 2002.

6.

Trzqsiok M.: Analiza wybranych własności m etody dyskryminacji wy­ korzystującej w ektoiy nośne. W: Postępy ekonometrii. Red. A.S. Barczak. AE, Katowice 2004.

7.

Vapnik V.: Statistical Learning Theory. John Wiley & Sons, New York 1998.

PARALLEL UNIFICATION OF THE CLASSIFICATION MODELS OBTAINED THROUGH SUPPORT VECTORS' METHOD Summary The paper presents a unified bias-variance decomposition o f zero-one loss and its appli­ cation to ensemble method using Support Vector Machines. We have used Breim an’s bagging technique to aggregate base learners trained on the repeated bootstrap samples. Then, we present a numerical experiment to compare bagged ensemble o f SVMs versus single SVMs.