Hidasi Balázs. Gravity R&D BME-TMIT február 20. Budapest

Hidasi Balázs Gravity R&D BME-TMIT ML@Bp, 2012. február 20. Budapest

Tartalom Bevezetés Idősorok Idősor-osztályozás

Az alap ShiftTree algoritmus Felépítés Címkézés Tanulás Futási idő Modellek értelmezése Előnyök, hátrányok

Kiegészítések Nyesés Többszörös modellezés Heurisztikák a tanulásban Stream-ShiftTree Futási idő csökkentés Konfidenciák Online tanulás Modellek kombinálása

Néhány eredmény Merre tovább?

Idősorok Félig strukturált adatok Idő szerinti rendezettség Egy vagy több változó Idősor-szerű adatok Több időtengely

Jelen tárgyalásban: Egy idő tengely Egy vagy több változó Változók egyenletes mintavétele

Motiváció Olcsó szenzorok elterjedése Jelentős mennyiségű idősor jellegű adat Előtérbe kerülő alkalmazási területek Nyomkövetés Hangfelismerés Gesztusfelismerés Diagnosztika Stb.

Idősorokhoz kapcsolódó feladatok Előrejelzés Klaszterezés Szakaszok felismerése Osztályozás Stb.

Idősorok osztályozása Klasszikus osztályozás, idősor bementtel Ismert címkéjű példányokkal tanítás Tanítás

Modell

Ismeretlen címkéjű pontok felcímkézése Modell Osztályozás

Idősor-osztályozó módszerek Klasszikus módszerek Változó(k) értékei függetlenek Nem használja ki a struktúrát Nem tudja kezelni az eltérő hosszakat

Példány alapú módszerek (1-NN (k-NN)) Valamilyen mérték használatával Nincs tanulás Nagyon lassú az osztályozás Indexelés

Alacsony általánosító képesség Nem kell sok tanítóminta

Rejtett Markov modellek (HMM) Kell ismeret a problémáról (nem domain független) Állapotátmenet mátrix, alap struktúra definiálása

Tanuláshoz sok minta kell

Célok Modell alapú megoldás Nagyobb általánosító képesség Címkézés gyors Viszont: több tanítóminta kell

Értelmezhető modell Leírás az osztályokról Bizalom az algoritmussal szemben

Kellő pontosság Domain függetlenség Szakértői tudás beépíthetősége

Általános koncepció Nem idősor specifikus Idősor Más félig strukturált adat Gráfok

Kurzor (szem) Dinamikus attribútumok Két kérdés „Hova nézzünk?” „Mit nézzünk?”

Operátor családok EyeShifter Operator(s) (ESO) ConditionBuilder Operator(s) (CBO)

F(x)

Modell: egyszerű operátorok / szabályok sorozata Elágazások lehetségesek

Koncepció alkalmazása idősorokra Dinamikus attribútumok idősorokhoz EyeShifter Operator (ESO): „Hova nézzünk?” A szemet az időtengely mentén mozgatja Az idősor egy meghatározott pontjához Pl.: „Következő lokális minimum”, „100 egységgel előre”, etc. Megj.: a hely függ(het) a teljes operátor sorozattól

ConditionBuilder Operator (CBO): „Mit nézzünk?” F(x)

Kiszámolja az attribútum értéket Pl.: „Változó értéke”, „Ugrás hossza”, etc.

Súlyozott átlag

Bináris döntési fa, mint alap modell Jól együttműködik a dinamikus attribútumok rendszerével A gyökértől a levelekig tartó operátor sorozatok

Egy csomópont felépítése Θ

ESOj VE változón

Θ

CBOk VC változón

CV I

ChildL

H

CV < TV ?

ChildR

Néhány példa operátor ESO Következő lokális maximum Globális minimum Vissza 25 egységgel Legközelebbi szélsőértékre

CBO Pontbeli érték Pont körüli súlyozott átlag Ugrás hossza Értékek átlaga az átugrott tartományban

Címkézés 0. szint ESOMax CBOSimple Felt: 2,028

1. szint

1. szint ESONext(25) CBOSimple

Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15

Címkézés 0. szint ESOMax CBOSimple Felt: 2,028 Érték: 1,89136

1. szint


Levél

Felt: 0,201982

Érték: 2,15333

Érték: 2,97557

2. szint

2. szint

Levél

Levél

15

Címkézés 0. szint ESOMax CBOSimple Felt: 2,028 Érték: 1,89136

1. szint


Levél

Felt: 0,201982

Érték: 2,15333

Érték: 2,97557

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

Érték: -0,953538

Érték: 1,32432

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

Érték: -0,953538

Érték: 1,32432

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15


1. szint


Levél

Felt: 0,201982

2. szint

2. szint

Levél

Levél

15

Modell tanulás 0. Operátor halmazok definiálása (ESO, CBO). 0. Üres gyökér csomópont felvétele, az összes tanítóminta hozzárendelése a gyökérhez. Minden mintánál a szem beállítása az idősor elejére. Gyökér berakása a kifejtési sorba. 1. A következő üres csomópont vétele a kifejtési sorból. 1.A. Ha teljesül a leállási feltétel, az aktuális csomópont legyen levél. GOTO 1. 1.B. Egyébként a csomópontba kerülő tanítóminták két részre bontása a legjobban szeparáló dinamikus attribútum szerint. (Csomópont tanulás.)

2. A kiválasztott ESO szerint a szem beállítása a tanítómintákon. 3. Két gyermek csomópont létrehozása, a mintahalmazok hozzárendelése, csomópontok hozzá vétele a kifejtési sorhoz. GOTO 1.

Csomópont tanulás Kiindulási állapot Szem az idősor elején Előre definiált ESO halmaz

Lehetséges szem pozíciók

F(x)

Csomópont tanulás Előre definiált CBO halmaz Elérhető dinamikus attribútumok

A lehetséges szem pozíciók „körül” Minden ESO-CBO kombináció

Választunk egy… Attribútumot Küszöbértéket

Ami minimalizálja a gyermek csomópontokban az osztályok eloszlásának entrópiáinak az összegét

Csomópont tanulás Legjobb vágás kiválasztása Szem mozgatása Elérhető pozíciók megváltoznak! Minták kétfelé osztása Gyermek csomópontok létrehozása Homogén csomópont esetén leállás

Csomópont tanulás Definiált operátorok

ES

ESONextMax ESONextMax

Ugrás a következő lokális maximumhoz

ESONext100 ESONext100

Ugrás 100 hellyel előre

ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató

Ugrás a maximumhoz Pontbeli érték visszaadása

ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: ESONextMax ESONext100 ESOMax CBO: CBOSimple Feltétel: -0,739969 -0,700739 -0,332858 0,390093 1,02775 -

M

Jelen beállításnál a legjobb vágási feltétel: -0,739969 -0,700739 -0,332858 0,369887 0,390093 2,48622 0,77183 -1,16155 1,02775 Jelen beállításnál a legjobb jóság érték: 0,985078 0,983634 0,805777 0,600131 1,32624 Inf 0 Eddigi legjobb jóságérték: 0,985078 0,983634 0,805777 Inf 0 Eddigi legjobb rendezés:

20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M

Jelen beállításnál a legjobb vágási feltétel: -0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 -1,16155 1,02775 Jelen beállításnál a legjobb jóság érték: 0,983634 0,805777 0,600131 1,32624 Inf 0 Eddigi legjobb jóságérték: 0,985078 0,983634 0,805777 Inf 0 Eddigi legjobb rendezés:

20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


M


20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító


Jelen beállításnál a legjobb vágási feltétel: Jelen beállításnál a legjobb jóság érték: Eddigi legjobb jóságérték: Eddigi legjobb rendezés:

M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 1,02775 0,983634 0,805777 0,600131 Inf 0 0,983634 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: ESONextMax ESONext100 ESOMax CBO: CBOSimple Feltétel: -0,739969 -0,700739 0,390093 1,02775 -


M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 1,02775 0,983634 0,805777 0,600131 Inf 0 0,983634 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: ESONextMax ESONext100 CBO: CBOSimple Feltétel: -0,739969 -0,700739 0,390093 -


M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 1,02775 0,983634 0,805777 0,600131 Inf 0 0,983634 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,739969 -0,700739 0,369887 0,390093 2,48622 0,77183 0,805777 0,600131 Inf 0 0,805777 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 0,390093 2,48622 0,77183 0,600131 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: ESONextMax ESONext100 CBO: CBOSimple Feltétel: -0,700739 0,390093 -


M

-0,700739 0,369887 0,390093 2,48622 0,77183 0,600131 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: ESONextMax CBO: CBOSimple Feltétel: -0,700739 -


M

-0,700739 0,369887 0,390093 2,48622 0,77183 0,600131 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 2,48622 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 2,48622 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 2,48622 Inf 0 Inf 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 2,48622 0 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító



M

-0,700739 0,369887 2,48622 0 0 20


ES





ESOMax ESOMax CB

CBOSimple CBSimple

Szemtologató


ShiftTree F(x)

Feltételállító

Döntő Eddigi legjobb vágás a csomópontban ESO: CBO: Feltétel: -


M

-0,700739 0,369887 2,48622 0 0 20

Futási idő - elmélet Címkézés: Operátorfüggően lineáris az idősor hosszában Lineáris a modell szintjeinek számában

Tanítás: Csomópontonként A rendezés miatt N*logN a csomópont mintáinak számában Operátorfüggően lineáris az idősor hosszában Lehetséges dinamikus attribútumok számában lineáris függés

Összességében Függ a kialakult struktúrától Függ a tanítópontok aktuális eloszlásától

Futási idő - gyakorlat Címkézés: nagyon gyors Tanítás: viszonylag gyors A hossztól való függés nem mutatható ki Nagyban függ a probléma nehézségétől Függ a definiált operátoroktól Lineárisan skálázódik 200 180 160

Idő (s)

140 120 100 80 60 40 20 0

Min of 20

Tanítóhalmaz mérete Max of 20

Mean of 20

Modell értelmezés

Operátor függő! Az adatok megértésében is segít Pl.: CBF adatsor 3 osztály: Cylinder, Bell, Funnel Cylinder a globális maximumban különbözik a másik kettőtől Z-normalizált adatsor

Bell és Funnel közti különbség: vissza 25 egységet + zajszűrés (súlyozott átlag) Melyik oldalon van a csúcs

Előnyök Modell alapúság előnyei Értelmezhető Domain független Szakértői tudás bevihető az operátorokon keresztül

Hátrányok Alap operátorkészlet (és paramétereik) definiálása nem triviális Túl sok operátor esetén belassulhat a tanulás Modell alapúság hátrányai

Többváltozós idősorok kezelése Az alap algoritmus működik többváltozóson Változók értékeiből származtathatunk CBE (Condition Builder Extension) A CBO-k által számolt származtatott értékeket kombinálja Pl.: Átlagolás

VVO (Virtual Variable operátor) Az egyes változókból származtat virtuális változókat Pl.: 2. és 3. változó különbsége

Nyesés Utó- vagy előnyesés Bizonyos ágak levágása Kipróbált módszerek: Szignifikancia alapú Komplexitás-hibaarány Egyszerű nyesés A validációs halmazra legjobban illeszkedő részfa

Szintszám limit Csomópontszám limit Mintaszám limit

Bármilyen nyesés csak ront a hatékonyságon

Többszörös modellezés (MM) Több optimális attribútum esetén

Az összeset kiválasztjuk, az összes szerint vágunk Többszörös fát építünk

De csak ott sokszorozunk, ahol kell, nem az egész fát

Címkézés

Többségi szavazás Vagy legjobb illeszkedés kiválasztása validációs halmazzal

Lassú, memóriaigényes Korlátozás kell a maximális elágazás- és/vagy modellszámra Javulás az eredményekben, de rossz a trade-off 1. szint ESONext(25) CBOSimple Feltétel1

Az 1. optimális (25-öt előre)

1. szint ESOPrev(25) CBOSimple Feltétel2

Ez is optimális (25-öt vissza)

2. szint

2. szint

Levél

Levél

2. szint

2. szint

Levél

Levél

Heurisztikák a tanításban Vágási határtól legyenek a az attribútum értékek minél távolabb Operátorok eltérő működési tartománya Normalizálás

Átlagolás a negatív példák miatt nem jó SM+ A határhoz legközelebbi pontok távolsága

SM++

A

Az összes pont távolsága a határtól

SM3+

B

SM+ és SM++ aránya

Az MM-nél jobb eredmények SM+ a leghatékonyabb Nem jelentős a számítási igény növekedés Kombinálható az MM-mel Mely vágásokat dobjuk el MM használata itt már nem jelent javulást

a4 a3 a2 a1

a5

H=A/B

a8 a6 a 7a9

B

a10 H = SUM(ai) / B

ShiftForest: Modellek kombinálása Több modell kombinálása a pontosság növelése végett Értelmezhetőség általában elveszik Kivéve, ha értelmes a modellek metszete

Boosting Iteratív módszer: Miden tanítómintához súly rendelése Tanítás Tanítóhalmazon (súlyozott) hiba mérése Modellsúly kiszámítása Hibásan osztályozott minták súlyának növelése

Problémák: Kell nyesés, különben a tanítási hiba nulla Kisebb adatsorokon nem feltétlenül működik (tökéletesen illeszkedő fa)

„XV” módszer Véletlenszerű felosztása a tanítóhalmaznak Első részen tanítás Másodikon pontosság mérés A modell súly a becsült pontosság érték

Futási idő csökkentése Tanítás során attribútum választás Célfüggvény minimalizálása

Célfüggvény tulajdonságai Adott rendezés mellett minimumok csak az egybefüggő intervallumok szélén lehetnek Minimum előre meghatározható Nem léphetünk ki minimumnál, de… Ha eléri, akkor csak 2-2 helyet kell vizsgálni a további rendezéseknél

Pl.: FordB – 3636 tanítóminta: 214,94s

173,52s (-19,27%)

Pl.: CBF – 30 tanítóminta: 0,246s

0,145s (-41,18%)

Pl.: Beef – 30 tanítóminta 0,574s

0,517s (-9,9%)

Célfüggvény érték

Jelentősen csökken a célfüggvény értékének meghatározásának száma Futási idő átlagosan 22,33%-kal csökkent

0

NI

Konfidenciák Mennyire biztos a modellünk a kimenetben Levél (csomópont) konfidencia Pl. többségi osztály aránya a levélben (nyesés!)

Útvonal konfidencia Osztályozási útvonalon a konfidenciák (súlyozott) összegzése Egyfajta dinamikus nyesési eljárás

Online tanulás Konfidenciák bevezetésével válik lehetővé Teljes modellépítés helyett a modell kisméretű megváltoztatása Konfidencia frissítés az egyes csomópontokban felhasználói visszajelzés alapján

Útvonal konfidencia, mint dinamikus nyesés

Pontosság

Arányok változásával változik a nyesés 75.00% 74.00% 73.00% 72.00% 71.00% 70.00% 69.00% 68.00% 67.00% 66.00% 1

2

3

4

5

Iterációszám

6

7

8

Stream ShiftTree Egy érdekes kiegészítés adatfolyamokban bizonyos jelek felismerésére Idősorokon tanított ShiftTree modellt használ a felismerésre Időablakos megoldás A stream változójának értékei alapján frissül, hogy éppen hol vagyunk a fában Visszafele ugrásokat nem támogatja Elkeni a feldolgozáshoz szükséges számítási igényt

Főbb problémák Alapjel elkülönítése az egyes osztályoktól

Stream ShiftTree példa Attribútum előállítása Ugorj a következő lokális maximumra (ESONextMax(1)), és vedd a 2 sugarú környezet átlagát (CBOAVG(2))

Collector 5 hosszú FIFO sor

21- 23- 43- 2- 3Activator Beérkezett érték: 4 231Előző érték: 4 231Előző előtti érték: 231azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



21- 23- 43- 2- 3Activator Beérkezett érték: 4 231 Előző érték: 4 231Előző előtti érték: 231azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



21 23- 43- 2- 3Activator Beérkezett érték: 4 23 Előző érték: 4 231 Előző előtti érték: 231azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



21 23 43- 2- 3Activator Beérkezett érték: 4 23 Előző érték: 4 23 Előző előtti érték: 231 azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



21 23 43 2- 3Activator Beérkezett érték: 4 2 Előző érték: 43 Előző előtti érték: 23 azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



2 3 4 2- 3Activator Beérkezett érték: 2 Előző érték: 4 Előző előtti érték: 3 azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:


Collector 2 3 4 2- 3Activator Beérkezett érték: 2 Előző érték: 4 Előző előtti érték: 3

Aktiválás

5 hosszú FIFO sor

azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



2 3 4 2 3Activator Beérkezett érték: 2 Előző érték: 4 Előző előtti érték: 3 azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



2 3 4 2 3 Activator Beérkezett érték: 2 Előző érték: 4 Előző előtti érték: 3 azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:



2 3 4 2 3 Activator Beérkezett érték: 2 Előző érték: 4 Előző előtti érték: 3

Attribútum érték kiszámítása

Eredmény: 2,8

azt nézi, hogy az előző beérkezett érték lokális maximum-e

Bemenet:

Teszteléshez használt adatok UCR Time Series Database 20 adatsor Különböző területekről A nagy részük kis méretű

Time Series Classification Challenge 2007 20 adatsor Különböző területekről Csak vak tesztekhez

Ford Classification Challenge 2008 2 nagy méretű adatsor

Többváltozós adatok EEG jelek Hangfelismerés Gesztusfelismerés

ShiftTree eredmények Nincs optimalizálás Alap operátorkészlet használata minden problémánál Ford és UCR adatok Kisebb adatsorokon nem hatékony 100.00%

92.94%

90.00% 80.00%

94.97%

96.52% 83.19%

81.29% 74.67%

73.33%

70.00%

64.93%

69.11%

60.00% 50.00% 40.00% 30.00% 20.00% 10.00% 0.00% Smaller UCR sets (15)

Larger UCR sets (5) 1NN Eucledian

1NN DTW

ShiftTree

Ford (largest) sets (2)

ShiftForest eredmények Jelentős növekedés az alap algoritmushoz képest 100.00%

92.94% 94.97%

90.00% 80.00%

88.87%

85.93%

81.29% 74.67%

96.52% 97.77% 83.19%

73.33%

70.00%

64.93%

69.11%

60.00% 50.00% 40.00% 30.00% 20.00% 10.00% 0.00% Smaller UCR sets (15) 1NN Eucledian

Larger UCR sets (5) 1NN DTW

ShiftTree

Ford (largest) sets (2) ShiftForest

Vak tesztek Time Series Challenge 2007 20 adatsorán Mintha részt vett volna a versenyben Egy-egy futtatás a ShiftTree-vel és a ShiftForest-tel Pontszám a helyezés alapján egy-egy problémánál Eredmény: 13 beadott megoldással (kombinált módszerek) összevetve ShiftTree 8., ShiftForest 6. helyen De az első helyek száma a ShiftTree-nél és a ShiftForest-nél a legmagasabb A kisebb adatsorokon teljesítenek rosszul

Algoritmus megbízhatósága Yoga

100.00%

Pontosság

80.00% 60.00% 40.00% 20.00% 0.00% 0%

10%

20%

30%

Becsült pontosság Min Tényleges pontosság Min

40% 50% 60% Tanítóhalmaz mérete Becsült pontosság Max Tényleges pontosság Max

70%

80%

90%

100%

Becsült pontosság Átlag Tényleges pontosság Átlag

FordB

100.00%

Pontosság

80.00% 60.00% 40.00% 20.00% 0.00% 0% 10% Becsült pontosság Min Tényleges pontosság Min

20%

30%

40% 50% 60% Tanítóhalmaz mérete Becsült pontosság Max Tényleges pontosság Max

70%

80% 90% 100% Becsült pontosság Átlag Tényleges pontosság Átlag

A ShiftTree története Egyetemi feladat + hobbi projekt 2008 (februártól) Május: első verzió és néhány teszt Október: alap modell, kiterjedt tesztek December: MM, nyesés, többváltozós

2009 Alkalmazási kísérletek (EEG adatokon) Stream kiterjesztés kidolgozása Egyéb kísérletek Vak tesztek

2010 Heurisztikus tanítás ShiftForest Kísérleti módszerek Új, fejlettebb implementáció Futási idő csökkentő eljárások

2011 (áprilisig) Konfidenciák Online tanulás

Nyitott kérdések Hogyan lehet tovább javítani a tanításon? Inner boosting Súlyozott MM Valószínűségi modellek MM-nél

Hogyan lehet egy adatsorhoz jó operátorkészletet definiálni?

Kutatási irányok Tanítás fejlesztése Az alapelv kiterjesztése Gráfok Többdimenziós idősorok (képek, videók) Más félig strukturált adatok

Más modell használata Neurális háló szerű megoldás

Alkalmazás

Köszönöm a figyelmet!

További ShiftTree-vel kapcsolatos kutatási anyagok az oldalamon: http://www.hidasi.eu

Hidasi Balázs. Gravity R&D BME-TMIT február 20. Budapest

Recommend Documents