Direktna primena metoda nosećih vektora na učenje pravila odlučivanja u berzanskom trgovanju

Apstrakt—U radu se opisuje pristup induktivnom učenju pravila odlučivanja u berzanskom trgovanju na osnovu istorijata berzanskih transakcija. Algoritam učenja direktno koristi model odlučivanja na osnovu vremenskih sekvenci finansijskih indikatora izvedenih iz vremenskih sekvenci kretanja cena akcija. Direktna primena metoda nosećih vektora na ovu vrstu problema omogućena je kreiranjem kernel funkcije zasnovane na Furijeovom razvoju. Namenska kernel funkcija je implementirana u programskom okruženju R/Revolution. U radu se demonstrira uspešna primena ovog metoda na aktuelnim istorijskim podacima o kretanju berzanskih indeksa na Njujorškoj berzi.

I.  UVOD

U radu se predlaže jedan metod induktivnog učenja pravila odlučivanja u berzanskom trgovanju na osnovu istorijata berzanskih transakcija. Istorijat trgovanja na berzi je vremenska sekvenca dana trgovanja, koji su opisani [1]: datumom, cenom (početnom, najvećom postignutom, najnižom, cenom na kraju dana, prilagođenom cenom) i obimom trgovanja.
Za potrebe automatizovanog kreiranja pravila predviđanja kretanja vrednosti cena akcija i donošenje odluka o kupovini ili prodaji, ovakve vremenske sekvence se proširuju informacijama dobijenim metodima analize finansijskih vremenskih serija [1].

Pri tome relevantnost novih atributa nije unapred poznata i razlikuje se za konkretne sekvence, odnosno pakete akcija. Zbog toga se vrši eksperimentalna korekcija modela problema metodima selekcije optimalnog podskupa atributa (feature selection) [2], [3], koji mogu biti spoljašnji (filter, wrapper) ili ugrađeni u same algoritme učenja (embedded).

Metod nosećih vektora (support vector machines, SVM) [4], [5] ima ugrađenu sposobnost selekcije atributa, ali je njena efikasnost ograničena i za dobre rezultate učenja se ipak koristi i neki metod spoljašnje selekcije atributa [4], [5], [6]. Selekcija atributa metodima kao što su metodi probnog učenja (wrapper method) je tipično eksponencijalne složenosti [3], [7]. Metod nosećih vektora omogućava uključivanje analize vremenskih sekvenci u sam proces učenja korišćenjem pogodnih kernel funkcija [4], [8].

Direktna primena metoda nosećih vektora na vremenske sekvence indikatora pojednostavjuje proces učenja, jer se učenje vrši direktno na osnovu ulaznog modela vremenske sekvence. Potencijalno se time skraćuje vreme izvršavanja, jer se izbegava složena spoljašnja selekcija atributa.

Cilj trgovanja akcijama na berzi je ostvarivanje maksimalnog profita na osnovu naloga za kupovinu i prodaju. Na osnovu početnog kapitala, nastoji se postići maksimalni profit u budućem periodu akcijama prodaje, kupovine i držanja akcija. Predviđanje kretanja indeksa vrši se na osnovu modela koji se induktivno nauči na osnovu istorijata kretanja cena akcija u prošlosti. Osnovni kriterijum učenja je tačnost predviđanja naučenog znanja, ali je kod ovakvih problema neophodno uvesti važniji kriterijum, finansijski efekt primene odluka koje daje naučeni model.

U radu se razmatra problem trgovanja pojedinačnim paketom akcija, koji se ilustruje na primerima berzanskih indeksa, sintetičkih pokazatelja kretanja cena određenih grupa paketa akcija.

II.  MAŠINSKO UČENJE NA OSNOVU VREMENSKIH SERIJA

Sekvence su uređeni nizovi događaja, npr. uzorci signala ili istorijat finansijskih transakcija, koji mogu biti jednodimenzionalni (univariate) ili višedemenzionalni (multivariate) [9].

Mašinsko učenje se može posmatrati kao ustanovljavanje nepoznate zavisnosti u raspoloživim podacima [2]. Formalno, induktivno mašinsko učenje na osnovu primera vrši estimaciju nepoznate zavisnosti između ulaza (podataka) i izlaza sistema (klasifikacije) na osnovu raspoloživih primera ispravnog preslikavanja. Nakon procesa učenja, dobijeno preslikavanje se koristi za predviđanje budućih izlaza posmatranog sistema na osnovu budućih ulaznih vrednosti.

Izlaz sistema može biti numerička vrednost, kada se uče pravila regresije, ili nenumerička vrednost, kada je u pitanju učenje klasifikacija.
Mašinsko učenje pravila regresije na osnovu vremenskih sekvenci, kao što je npr. istorijat finansijskih podataka, bavi se učenjem pravila regresije koje predviđa vrednost izlaza sistema u izabranom vremenskom trenutku, koji nastupa nakon perioda izabranog za učenje. Cilj učenja klasifikacija na osnovu vremenskih sekvenci je učenje pravila klasifikacije uređenih sekvenci vrednosti u unapred definisane diskretne klase.

A.  Osnovni pristupi učenju na osnovu vremenskih sekvenci

Različiti pristupi učenju na osnovu vremenskih sekvenci su [9], [10]:

1. Ekstrakcijom atributa (feature based), kada se sekvenca transformiše u model opisan skupom atributa koji agregiraju informacije o sekvenci, na koji se zatim primene standardni metodi mašinskog učenja (stabla odlučivanja/regresije, klasifikaciona/ regresiona pravila, veštačke neuronske mreže, noseći vektori i sl.).
2. Na osnovu sličnosti sekvenci (sequence distance based), kada se prvo definiše funkcija međusobnog rastojanja sekvenci, a zatim primene metodi kao što je metod najbližeg suseda (k-nearest-neighbour, kNN).

3. Na osnovu modela (model based), kada se koriste statistički i generativni modeli, npr. skriveni Markovljevi modeli (Hidden Markov Model, HMM).
Proces ekstrakcije atributa (feature extraction) [3] ima za cilj predstavljanje problema u novom modelu, tako da se sačuvaju važne informacije, a ukloni šum i korelacije između atributa.

Drugačiji pristup učenju sekvenci je pomoću generativnih modela [5], kod kojih se model opisuje nizom operacija umesto nizom vrednosti. Klasični metod su skriveni Markovljevi modeli (HMM), ali se može koristiti i metod nosećih vektora, tako što se relacije iz sekvence uključuju u definiciju kernel funkcije [4],[5].

B. Metod nosećih vektora (support vector machines)

Metod nosećih vektora [4] je veoma uspešan metod učenja na osnovu primera. Obučavajući primeri se preslikavaju iz prostora vrednosti atributa (input space) u novi prostor veće dimenzionalnosti (feature space), u kome se potencijalno mogu linearno razdvojiti. Metod pronalazi optimalnu hiperpovršinu, koja obučavajuće primere razdvaja s maksimalnom marginom [4], [5], [11] opisanom sa:

w,  (x)   b  0

gde je w matrica koeficijenata, Φ(x) je funkcija preslikavanja u novi prostor, a b je konstanta. Za jednostavni slučaj dveju klasa sa oznakama iz skupa {+1,-1}, klasifikacija se može realizovati pomoću funkcije

f (x)  sign ( w,  (x)   b)

Metod nosećih vektora bira mali skup kritičnih graničnih primera (noseći vektori, support vectors) svake od razmatranih klasa i gradi linearnu funkciju koja ih najbolje razdvaja.

Optimalna hiperpovršina se konstruiše pomoću iterativnog algoritma, koji minimizuje funkciju ocene greške:

1 N
wTw  C    i
2
i 1

tako da važi

yi (wT (xi ) b) 1 i , i 1,..N i 0 , i 1,..N

gde je w vektor koeficijenata, b konstanta, ξ tolerancija preklapanja linearno neseparabilnih klasa primera, N broj obučavajućih primera, a C regularizacioni parametar funkcije greške.

Rešenje problema optimizacije se može prikazati u obliku

N

w i yi   (xi )

i 1

gde su αi koeficijenti, koji su veći od nule kada tačka (xi, yi) zadovoljava ograničenja, odnosno predstavlja noseći vektor. Ovi koeficijenti se dobijaju rešavanjem dualnog problema, maksimizovanjem izraza

N 1 N
i i   j yi y j K (xi , x j )

i 1 2 i, j 1
uz uslove
0   i    C, i  1..N

N

i yi 0 i 1

Pri tome metod nosećih vektora koristi linearne funkcije za izgradnju nelinearnih granica razdvajanja klasa u hiperprostoru koristeći nelinearne transformacije. Povratkom u originalni prostor, dobije se nelinearna funkcija razdvajanja klasa (kernel trick). Funkcija preslikavanja Φ(x) se ne mora eksplicitno poznavati, jer je neophodno samo računanje skalarnog proizvoda.

C.  Uloga kernel funkcije (kernel trick)

Različite kernel funkcije i vrednosti njihovih parametara proizvode različite modele. Neke od često korišćenih osnovnih kernel funkcija su linearna, polinomska, Gausova i sigmoid funkcija [4]. Gausova kernel funkcija (radial basis function, RBF) oblika

K (x1, x2 )  exp(     x1   x2    2 )

se često koristi, jer je primenjiva je na veoma široku klasu problema; linearna kernel funkcija je njen specijalni slučaj.

Posebne kernel funkcije su razvijene za rad sa strukturama koje nisu vektori, kao što su npr. stringovi, grafovi, tekstualni dokumenti, opšte rekurzivne strukture i deterministički i probabilistički generativni modeli [5].

Generativne kernel funkcije, kao što su npr. k-spectrum/string i Fisher kernel, te Furije/Fejer kernel [11],
[12], [8] se, osim za učenje, istovremeno koriste i za ekstrakciju vremenskih informacija iz posmatrane sekvence.

Znatno opštiji pristup je istovremeno automatizovano učenje kompozitne kernel funkcije i parametara SVM metoda (Multiple Kernel Learning) [5], [13]. Jedna klasa ovih metoda bavi se učenjem kernela koji predstavljaju linearne kombinacije zadanih bazičnih kernel funkcija, s težinskim koeficijentima [13], [14].

III.  PRIMENA METODA NOSEĆIH VEKTORA NA VREMENSKE SERIJE

Cilj mašinskog učenja je da se u modelu upotrebi što više informacija iz predznanja o problemu, gde spadaju i informacije o povezanosti elemenata sekvence/serije.

A.  Direktno učenje na osnovu vremenskih serija

Metod nosećih vektora omogućava izdvajanje ovih informacija u okviru kernel funkcije, tako da se učenje može izvršiti direktno nad originalnim podacima vremenske serije, bez dodatnog procesiranja, koje značajno menja originalni model problema i utiče na rezultate učenja.

Prema [4], skalarni proizvod Furijeovog razvoja dve vremenske serije se može direktno računati na osnovu regularizovane Furijeove kernel funkcije, odnosno Fejer kernela KF:

1  q2
KF (x1, x2 )  2(1  2q cos(x1    x2 )  q2 ) , 0  q  1

gde su x1 i x2 primeri dveju jednodimenzionalnih vremenskih serija, a q regularizacioni parametar, koji omogućava upravljanje potiskivanjem viših frekvencija u Furijeovom razvoju serija: njegove veće vrednosti odgovaraju jače izraženim visokim frekvencijama i složenijem modelu, a manje vrednosti smanjenom učešću visokih frekvencija i jednostavnijem modelu.

B.  Finansijski model trgovanja akcijama

Trgovanje akcijama nastoji da se postigne maksimalni profit u budućem periodu putem prodaje, kupovine i držanja akcija.

Predviđanje kretanja berzanskih indeksa se vrši na osnovu modela koji se induktivno nauči na osnovu istorijata kretanja cena akcija u prošlosti. Osnovni element predviđanja je trend promene cena akcija u posmatranom periodu od k dana u odnosu na tekuću cenu, koja je postignuta na kraju dana [1]. Npr. porast od p% iznad trenutne cene u narednom periodu je indikator za kupovanje, dok je promena na niže indikator za prodaju akcija.

Prosečna dnevna cena akcija se može računati kao

Pi 1 (Closei Highi Lowi ) 3

a promena tekuće cene Close u narednih k dana je tada

Vi    ((Pi  j    Closei ) / Closei )k
Indikator trenda Ti je suma promena tekuće cene Vi u posmatranom periodu od k dana

Ti         v  Vi : (v   p%)  (v    p%)

v

C.  Problem odlučivanja u berzanskom trgovanju

U radu je, kao u [1], usvojeno da indikator Ti identifikuje periode od k dana u kojima su promene prosečne dnevne cene jasno iznad postavljenih granica, pa se u slučaju visoke pozitivne vrednosti Ti očekuje porast, a u slučaju negativne pad cena. U skladu s tim je definisano pravilo odlučivanja o akciji koju treba preduzeti:

sell Ti      0,1 (1)
0,1 Ti    0,1
di      hold
buy T 0,1
Predviđanje promena cena u određenom periodu se razmatra kao predviđanje vrednosti indikatora Ti u narednih k dana. Osim ovog indikatora, postoji niz drugih numeričkih pokazatelja promena cena u vremenskim serijama, kao što su tzv. tehnički indikatori različitih svojstava promena cena (stepen varijacije, sleđenje specifičnih trendova i sl.). Izbor dobrog podskupa indikatora je otvoren problem, koji se u ovom radu realizuje metodima selekcije atributa [3],[7].

Inicijalni skup atributa kojima se opisuje svaki dan dan trgovanja se sastoji od

(1) stope povrata cena u poslednjih h dana

Ri  h    (Closei    Closei  h ) / Closei  h  za h=1..10

(2) niza tehničkih indikatora, koji su na raspolaganju u okviru paketa TTR (Technical Trading Rules) sistema R [15].

Indikator trenda Ti je se može uzeti kao prediktivni atribut, čija vrednost se predviđa pomoću regresionog modela, koji se uči metodom nosećih vektora.

Predviđanje neposredne odluke se može izvršiti i učenjem klasifikacionog modela, tako što se obučavajući skup proširi diskretnim klasifikacionim atributom, čija vrednost se određuje na osnovu indikatora odluke di u izrazu (1), na osnovu indikatora trenda promene Ti. Prednost numeričkog predviđanja je mogućnost da se proceni obim i/ili vrednost akcija kojima će se trgovati.

IV.  EKSPERIMENTI

U radu je izvršena eksperimentalna provera tačnosti učenja metodom nosećih vektora na osnovu vremenskih sekvenci, na standardni način (sa i bez selekcije atributa) i predloženom metodom direktnog učenja. Za analizu finansijskih efekata odluka neophodno je prethodno usvojiti strategiju trgovanja, koja se koristi za kreiranje konkretnih naloga za kupovinu i prodaju akcija, a zatim obezbediti ostale elemente za realizaciju naloga, što je moguće realizovati stohastičkom simulacijom, što nije tema ovog rada.

Prema modelu iz [1], prvo je kreiran regresioni model za predviđanje cena akcija u periodu od k dana u budućnosti u odnosu na posmatrani dan trgovanja. Ekstrakcija skupa atributa kao što su povrat cene u poslednjih k dana i niz finansijskih pokazatelja i indikatora iz paketa TTR [15], izvršena je nad elementima originalne sekvence.

Zatim je izvršeno učenje pravila regresije za predviđanje kretanja cena u narednom periodu. Za obučavajući skup je izabran period od oko 3.000 dana istorijata trgovanja, isti za sve probleme, a zatim su performanse odlučivanja izmerene u testnom periodu od narednih 1.500 dana.

Klasifikacioni model je kreiran za učenje pravila neposrednog donošenja odluka u dnevnom trgovanju, sa tri mogućnosti: prodati (sell), zadržati (hold) i kupiti akcije (buy). Ispravne odluke su za primere iz testnog skupa generisane na osnovu vrednosti indikatora trenda Ti prema heuristici ranije opisanoj u izrazu (1).

A.  Korišćeni softver

Metod učenja i predloženi kernel su realizovani u programskom okruženju R/Revolution [11], [16], koji je prema anketama [17] i [18] najčešće korišćen programski alat na području istraživanja podataka metodima mašinskog učenja. Upotrebljen je metod ksvm iz paketa kernlab, koji predstavlja jednu implementaciju poznatog algoritma

Sequential Minimization Optimization (SMO) [11].

U paketu kernlab se nova korisnička kernel funkcija može definisati direktno u jeziku R, kao funkcija sa dva vektorska argumenta, koja vraća njihov skalarni proizvod [11], [8]:

myKernel <- function (x1, x2) { (sum(x1*x2)+1)*exp(-0.001*sum((x1-x2)^2))

}

class(myKernel) <- "kernel"

Nova funkcija klase "kernel" se zatim koristi kao argument metoda nosećih vektora ksvm:

m<-ksvm(X,Y,type="C-svc",kernel=myKernel,..)

Korišćene objektne biblioteke (paketi) iz sistema R su:

- kernlab - metod nosećih vektora, koja omogućava programiranje korisničke kernel funkcije direktno u jeziku R;

- randomForest - metod učenja ansambala u obliku slučajnih šuma [19], koji se u radu koristi za rangiranje i selekciju optimalnog podskupa atributa metodom filtriranja;
- TTR (Technical Trading Rules) - metodi tehničke analize u jeziku R, za evaluaciju hartija od vrednosti;
- xts, quantmod, DMwR - dodatni paketi opisani u [1], [15].

B.  Podaci

Provera predloženog metoda izvršena je pomoću javno dostupnih podataka o istorijatu cena akcija dveju kompanija iz oblasti informacionih tehnologija i berzanskih indeksa

S&P500, NASDAQcomp i Russel2000:
1) S&P500 predstavlja stanje akcija 500 vodećih kompanija na Njujorškoj berzi, prema oceni kompanije Standard&Poor; istovremeno je i pokazatelj stanja američke ekonomije [1].
2) NASDAQcomp je mešoviti indeks, koji obuhvata stanje akcija svetskih, pre svega tehnoloških i kompanija koje rastu.
3) Russell2000 je indeks performansi 2.000 izabranih kompanija u SAD s manjim kapitalom.
Istorijat berzanskih transakcija, koje se može preuzeti na

[20] imaju originalne atribute: Date, Open, High, Low, Close, Volume, Adj Close. Ovi osnovni dnevni podaci o kretanju cena akcija zamenjeni su [1]:
1) grupom od 10 atributa, koji za svaki dan trgovanja pokazuju povrat sredstava za cene akcija ostvarene u prethodnih 10 dana (n-grami).
2) grupom od 17 dodatnih atributa, čije vrednosti se računaju metodima iz R paketa TTR [15].

Pregled svojstava kreiranih obučavajućih vremenskih serija dat je u Tabeli I.

V.  REZULTATI

Metodom nosećih vektora na osnovu vremenskih serija berzanskih indeksa naučena su (1) pravila predviđanja kretanja cena i (2) pravila odlučivanja (sell/hold/buy).

Kretanje cena kompozitnog indeksa S&P500 u periodu januar-mart 2013 prikazano je na Sl. 1, a u donjem delu je za isti period prikazana promena vrednosti indikatora trenda cena Ti. Vidi se da su periodi pogodni za kupovinu i prodaju akcija retki (Ti >0,1 i Ti <-0,1).
Sl. 1. Prikaz kretanja (a) cena akcija i (b) vrednosti indikatora trenda, za indeks S&P500 u tromesečnom periodu.

Tabelarni i grafički prikaz tačnosti predviđanja je na Sl. 2. Vidi se da je tačnost direktnog metoda konzistentno visoka.

Sl. 2. Prikaz kretanja (a) cena akcija i (b) vrednosti indikatora, za indeks NYSEcomp po danima u tromesečnom periodu.

Na Sl. 3 je prikaz tačnosti predviđanja direktnog metoda u zavisnosti od regularizacionog parametra q. Vidi se da se u većini primera bolji rezultati dobijaju za manje vrednosti parametra, kada je manji uticaj visokih frekvencija, odnosno veoma čestih promena, što istovremeno daje i jednostavnije modele.
Sl. 3. Prikaz uticaja vrednosti regularizacionog parametra q na tačnost predviđanja predloženog direktnog metoda za razmatrane indekse.

VI.  ZAKLJUČAK

Osnovni cilj rada je provera performansi direktne primene metoda nosećih vektora na vremenske sekvence finansijskih indikatora u oblasti berzanskog trgovanja.

Razmotrena je situacija kada algoritam učenja direktno koristi vremenske sekvence finansijskih indikatora izvedenih iz vremenskih sekvenci kretanja cena akcija, bez vremenski veoma zahtevne selekcije atributa.

Direktna primena metoda nosećih vektora na ovu vrstu problema je realizovana pomoću generativne kernel funkcije zasnovane na Furijeovom razvoju.
Metod nosećih vektora s kreiranom kernel funkcijom je tačniji na punom modelu problema učenja, a približno je iste tačnosti na redukovanom modelu modelu od 8 atributa, koji je dobijen selekcijom atributa metodom slučajnih šuma. Osim toga, direktna primena metoda nosećih vektora daje daje po pravilu jednostavnije modele, tipično oko 30% manje složenosti.
LITERATURA

[1] L. Torgo, Data Mining with R: Learning with Case Studies, Chapman & Hall/CRC, 2011

[2] V. Cherkassky, F. M. Mulier, Learning from Data: Concepts, Theory, and Methods, 2nd Ed, John Wiley - IEEE Press, 2007
[3] I. Guyon, S. Gunn, M. Nikravesh, L. Zadeh (editors), Feature extraction, foundations and applications, Springer, 2006
[4] V. Vapnik, Statistical Learning Theory, John Wiley&Sons, 1998
[5] J. Shawe-Teylor, N. Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, 2004
[6] V. Miškovic, M. Milosavljević, "Ugrađeni metodi selekcije atributa u algoritmima induktivnog učenja", Zbornik radova 54. konferencije ETRAN, Donji Milanovac, Srbija, jun 2010
[7] V. Miškovic, "Induktivno učenje razumljivog znanja na osnovu oskudnih obučavajućih skupova", Ph.D. dissertation, Univerzitet Singidunum, Beograd, Srbija, 2008
[8] V. Miškovic, "Primena metoda nosećih vektora u klasifikaciji vremenskih sekvenci", Zbornik radova 56. konferencije ETRAN, Zlatibor, Srbija, jun 2012
[9] Mitsa, Temporal Data Mining, Chapman & Hall/CRC, 2010
[10] Z. Xing, J. Pei, E. Keogh, "A Brief Survey on Sequence Classification",

ACM SIGKDD Explorations Newsletter, vol. 12, no. 1, 2010

[11] A. Karatzoglou, D. Meyer, K. Hornik, "Support Vector Machines in R",

Journal of Statistical Software, vol. 15, no. 9, 2006
[12] S. Rüping, "SVM Kernels for Time Series Analysis", in LLWA 01 - Tagungsband der GI-Workshop-Woche Lernen - Lehren - Wissen - Adaptivität, pp. 43-50, Dortmund, Germany, 2001
[13] M.  Gönen,  E.  Alpaydin,  "Multiple  Kernel  Learning  Algorithms",

Journal of Machine Learning Research, vol. 12, pp. 2211-2268, 2011

[14] Miškovic V., "Learning kernels for Time Sequences Classifications", Telecommunications Forum (TELFOR), 2012 20th, IEEE Conference Publications, pp. 1377-1380, November 2012
[15] The Comprehensive R Archive Network [You must be registered and logged in to see this link.]
[16] Revolution Analytics  http://www.revolutionanalytics.com

[17] KDNuggets [You must be registered and logged in to see this link.]
[18] Rexer Analytics [You must be registered and logged in to see this link.]
[19] L. Breiman, "Random Forests", Machine Learning, 45, pp. 5-32, 2001

[20] Yahoo!Finance [You must be registered and logged in to see this link.]

ABSTRACT

The paper describes an approach to machine learning of decision rules in stock exchange trading from time sequences of transactions history. The learning algorithm directly uses a decision model based on financial indicators derived from time sequences of stock prices changes. Direct application of the support vector classification method to this type of problems is possible by creating an appropriate kernel function based on Fourier transformation. The specialized kernel function was implemented using R/Revolution programming environment. Successful application of the method to actual historical data of stock indices on the New York Stock Exchange is demonstrated.

Direct Application of Support Vector Machines to Learning Decision Rules in Stock Exchange Trading