Doktoraty Wydziału IET

mgr inż. Marcin Orchel

Promotor: prof. dr hab. inż. Witold Dzwinel (AGH)
Dyscyplina: Informatyka

Praca ta dotyczy maszyn wektorów wspierających (SVM), nowoczesnej metody maszynowego uczenia się, która wyszukuje zależności w danych. Ostatnimi czasy SVMy stały się pełnoprawną dziedziną naukową, która obejmuje nie tylko teorię maszynowego uczenia się, ale także teorię optymalizacji, geometrię wielowymiarową oraz teorię funkcji liniowych. Podstawowymi problemami maszynowego uczenia się są klasyfikacja i regresja, dla obu problemów powstały efektywne warianty SVM. Powstało również wiele rozszerzeń SVM, a wśród nich rozszerzenia umożliwiające włączanie dodatkowej wiedzy.

Badania objęte tematyką pracy doprowadziły do opracowania nowoczesnej metody regresji, która rozwiązuje problem regresji za pomocą binarnej klasyfikacji. Metoda ta, oraz koncepcja stojąca za nią rzuca nowe światło na relację miedzy dwoma najważniejszymi problemami maszynowego uczenia się. Drugim elementem badań była analiza dodatkowej wiedzy w postaci wielkości marginesu per przykład. Jest to naturalne rozszerzenie SVM, ponieważ podstawową koncepcją SVM jest margines. Trzecim elementem badań była analiza implementacji SVM oraz zastosowanie w tematyce finansowej.

Streszczenie

W niniejszej pracy, proponujemy metodę, zwaną δ regresja wektorów wspierających (δ-SVR), która polega na zamianie problemu regresji w problemy binarnej klasyfikacji, które są rozwiązywane za pomocą maszyny wektorów wspierających (SVM). Analizujemy statystyczną równoważność problemu regresji z problemem binarnej klasyfikacji. Pokazujemy potencjalną możliwość ulepszenia ograniczeń błędu generalizacji opartych na wymiarze Vapnik-Chervonenkisa (VC), w porównaniu do SVM. Wykonaliśmy eksperymenty porównujące δ-SVR z ε regresją wektorów wspierających (ε-SVR) na syntetycznych i rzeczywistych zbiorach danych. Rezultaty wskazują, że δ-SVR osiąga porównywalny błąd generalizacji, mniej wektorów wspierających oraz mniejszy błąd generalizacji dla różnych wartości ε i δ. Metoda δ-SVR jest szybsza dla liniowych jąder używając metody minimalnej optymalizacji sekwencyjnej (SMO), dla nieliniowych jąder rezultaty szybkości zależą od zbioru danych. W niniejszej pracy proponujemy metodę zwaną ϕ klasyfikacja wektorów wspierających (ϕ-SVC) do włączania wiedzy marginesowej per przykład do problemów klasyfikacji i regresji. Proponujemy dwie aplikacje dla ϕ-SVC: zmniejszenie błędu generalizacji modeli zredukowanych przy zachowaniu podobnej liczby wektorów wspierających, oraz włączenie nieliniowego warunku specjalnego typu do problemu optymalizacyjnego. Metoda była przetestowana dla klasyfikatora SVM, oraz dla metody regresji ε-SVR. Eksperymenty na danych rzeczywistych pokazują zmniejszony błąd generalizacji modeli zredukowanych dla liniowych i wielomianowych jąder. W tej pracy proponujemy dwa usprawnienia w implementacji SVM, pierwsze w szybkości trenowania SVM, drugie w uproszczeniu implementacji SVM. Pierwsze usprawnienie, zwane heurystyką alternatyw (HoA), dotyczy nowej heurystyki wyboru parametrów do zbioru roboczego. Bierze ona pod uwagę nie tylko spełnienie warunków Karush-Kuhn-Tuckera (KKT), ale również zmianę wartości funkcji celu. Testy na rzeczywistych zbiorach danych pokazują, ze HoA prowadzi do zmniejszenia liczby iteracji, i może prowadzić do zmniejszenia czasu trenowania SVM, porównując do heurystyki standardowej. Drugie usprawnienie, zwane wielowymiarową, sekwencyjną metodą rozwiązywania podproblemów (SMS), dotyczy nowego sposobu rozwiązywania podproblemów o więcej niż dwóch parametrach: zamiast stosowania skomplikowanych metod rozwiązujących problemy z zakresu programowania kwadratowego, używamy do tego celu metodę SMO. Otrzymujemy prostszą implementację, z podobnymi wynikami szybkościowymi. W tej pracy proponujemy zastosowanie regresji wektorów wspierających (SVR) do wykonywania zleceń na rynkach akcyjnych. Używamy SVR do predykcji funkcji partycypacji w wolumenie. Proponujemy ulepszenie przewidywania funkcji partycypacji używając SVM z włączonym dodatkowym warunkiem nieliniowym do problemu optymalizacyjnego. Pokazujemy, że jakość przewidywania wpływa na koszty egzekucji. Ponadto pokazujemy jak możemy włączyć wiedzę o cenach akcji. Porównaliśmy ε-SVR i δ-SVR z prostymi predyktorami takimi jak średnia cena wykonania z poprzednich dni. Testy zostały przeprowadzone na danych dla spółek z indeksu NASDAQ-100. Dla obu metod otrzymaliśmy lepszą predykcję partycypacji w wolumenie.

Hipotezami pracy są:

1. Zaproponowana metoda regresji δ-SVR pozwala na zmniejszenie liczby wektorów wspierających oraz poprawienie elastyczności SVM.
2. Wiedza o marginesie per przykład prowadzi do zmniejszenia błędu generalizacji dla modeli zredukowanych dla problemów klasyfikacji i regresji.
3. Wiedza o marginesie per przykład może zostać użyta do włączenia warunku równościowego, nieliniowego do rozwiązania.
4. Zaproponowana heurystyka alternatyw HoA prowadzi do przyspieszenia heurystyki w metodzie SMO.
5. Zaproponowana sekwencyjna metoda rozwiązywania podproblemów wielowymiarowych SMS pozwala na ominięcie konieczności używania ogólnych bibliotek do programowania kwadratowego do rozwiązania SVM w metodach opartych na zbiorze roboczym.
6. Wiedza o marginesie per przykład może zostać użyta w finansach do przewidywania funkcji partycypacji w wolumenie.

Dłuższa wersja autoreferatu tutaj.

Ważniejsze publikacje doktoranta:

1. Marcin Orchel, Support vector regression based on data shifting, Neurocomputing, vol. 96 spec. iss. s. 2–11.
2. Marcin Orchel, Incorporating a priori knowledge from detractor points into support vector classification, ICANNGA 2011 : Ljubljana, Slovenia, April 14–16, 2011, Lecture Notes in Computer Science, S. 332–341.
3. Marcin Orchel, Regression based on support vector classification, ICANNGA 2011 : Ljubljana, Slovenia, April 14–16, 2011, Lecture Notes in Computer Science, S. 353–362.
4. Marcin Orchel, Support vector regression as a classification problem with a priori knowledge in the form of detractors, Man-Machine Interactions 2, Advances in Intelligent and Soft Computing, S. 351–358.
5. Marcin Orchel, Support vector regression with a priori knowledge used in order execution strategies based on VWAP, ADMA 2011 : Beijing, China, December 17–19, 2011, Lecture Notes in Computer Science. Lecture Notes in Artificial Intelligence, S. 318–331.
6. Marcin Orchel, Incorporating detractors into SVM classification, ICMMI 2009 : September 25-27, 2009, Advances in Intelligent and Soft Computing, S. 361–369.