Kollektív tanulás milliós hálózatokban
Jelasity Márk
2012/05/16
MTA, Budapest
2
2012/05/16
MTA, Budapest
3
Motiváció ●
Okostelefon platform robbanásszerű terjedése és
●
Szenzorok és gazdag kontextus jelenléte, ami
●
●
Kollaboratív adatbányászati alkalmazások lehetőségét teremti meg –
Egészségügy: járványok nyomon követése, előrejelzése, egyéni diagnosztika
–
Smart city: forgalom optimalizálása, balesetveszélyes helyzetek előrejelzése
–
Földrengés előrejelzés, pénzügyi alkalmazások, stb
P2P hálózatok, grid, stb, is releváns platformok
2012/05/16
MTA, Budapest
4
P2P rendszermodell ●
Nagyon sok (több millió) eszköz (számítógép) –
●
●
●
Ezentúl csomópontnak hívjuk őket (node)
Csomagkapcsolt hálózat segítségével kommunikálnak –
Minden csomópont hálózati címmel rendelkezik
–
A cím ismeretében a csomópont számára üzenet küldhető bármely másik csomópontból
Az üzenetek a hálózatban késhetnek, és el is veszhetnek, sorrendjük sem garantált Formalizálhatjuk is, pl. a kaotikus modell érdekes és releváns
2012/05/16
MTA, Budapest
5
Teljesen elosztott adatmodell ● ●
●
Horizontális elosztottság Minden csomóponton kevés, esetleg csak egy adatrekord (innen feltesszük hogy pont egy) Nem engedjük meg az adat mozgatását, csak lokális feldolgozást –
●
Privacy preservation (adatvédelem)
Az előállított modellek használata olcsó és minden csomópont számára elérhető legyen –
2012/05/16
Demokratikus feltétel MTA, Budapest
6
Illusztráció: átlagolás 12
3 7
6
2
2012/05/16
8
MTA, Budapest
7
Illusztráció: átlagolás 12 kérés
3 6
2
2012/05/16
7
6
8
MTA, Budapest
8
Illusztráció: átlagolás 12
3 12
válasz
6
2
2012/05/16
7
8
MTA, Budapest
9
Illusztráció: átlagolás 9
3 7
9
2
8 (12+6)/2=9
2012/05/16
MTA, Budapest
10
Osztályozási probléma ●
●
●
●
Adott (xi,yi) példák egy halmaza, ahol yi xi osztálya (yi pl. -1 vagy 1, kétosztályos esetben) Egy f() modellt szeretnénk, amelyre f(xi)=yi (ill. f(xi)≈yi) minden i-re f() gyakran paraméterekkel addott: f w(), így a tanulási probléma hibaminimalizálásra vezethető vissza w-ben. A hiba gyakran a példák feletti hibák összege
2012/05/16
MTA, Budapest
11
Osztályozás lineáris modellel
+
2012/05/16
+
+
-
+
+
-
+ + + + + + + + +
+ + + + + + + + +
-
-
+ -
- - -
-
MTA, Budapest
-
12
Teljesen elosztott osztályozás ●
●
●
●
A probléma tehát olyan optimalizáló algoritmust találni, amely jól illeszkedik a rendszer- és adatmodellünkbe A legtöbb ismert elosztott módszer felteszi, hogy lokálisan is építhető modell, majd ezeket a modelleket kombinálja (ensemble learning) Az online módszerek azonban –
Egyszerre csak egy adatrekordot igényelnek
–
Ezzel a rekorddal frissítik a modellt
A sztochasztikus gradiens módszer egy gyakori online módszer, ezt alkalmazzuk a lineáris modellekre (az SVM módszer hibafüggvényének primál alakjára)
2012/05/16
MTA, Budapest
13
Sztochasztikus gradiens n ●
Tegyük fel hogy a hiba:
●
Ennek gradiense:
●
●
Err w = ∑ Err w , x i i=1 n
Tehát a teljes gradiens módszer az lenne hogy: De csak egy példát veszünk egyszerre, szóval a módszer:
2012/05/16
∂ Err w , xi ∂ Err w =∑ ∂w ∂w i=1 n
w t 1=w t −t ∑ i =1
∂ Err w , x i ∂w
∂ Err w , xi w t 1=w t −t ∂w
MTA, Budapest
14
A pletyka tanulás
2012/05/16
MTA, Budapest
15
A „merge” függvény ●
Legyen z=merge(x,y)=(x+y)/2 (x, y lineáris modellek)
●
Adaline perceptron stochasztikus gradiens módszerével
●
●
–
z frissítése egy példával u.olyan hatású mint x és y frissítése az adott példával, majd ezek átlagolása
–
z-vel predikálni u.az, mint x és y predikcióját súlyozottan átlagolni
Ez azt jeleni, hogy effektíve egy exponenciálisan növekvő számú modellt propagálunk, és ezek szavaztatása a predikciónk! Az lineáris SVM algoritmusra ez nem teljesül pontosan, de a hasonlóság heurisztikusan motiválja a módszert
2012/05/16
MTA, Budapest
16
Lokális predikció ●
Csak helyben meglévő modelleket használunk –
Vagy csak az aktuális modellt
–
Vagy az „ingyen” összegyűlt modellek szavaztatását is elvégezhetjük
2012/05/16
MTA, Budapest
17
Kísérleti kiértékelés ●
●
Az ismert Pegasos algoritmust alkalmaztuk (lineáris SVM sztochasztikus gradiens módszerrel) a pletyka keretben Ismert adatbázisokon értékeltük ki a módszert –
●
Teljesen elosztott adatmodell, egy rekord egy csomóponton
Extrém kísérleti beállításokat is használtunk a robosztusság tesztelésére (kaotikus modell) –
50% üzenetvesztés
–
1-10 ciklusnyi késleltetés
2012/05/16
MTA, Budapest
18
Tanuló adatbázisok
●
●
A kísérletekben felhasznált adatbázisok statisztikái Néhány ismert algoritmus teljesítménye
2012/05/16
MTA, Budapest
19
Véletlen séta alapú módszer
2012/05/16
MTA, Budapest
20
Átlagolt modellek
2012/05/16
MTA, Budapest
21
További eredmények ●
●
A többosztályos boosting algoritmust is implementáltuk a pletyka tanulás sémájában, a boosting elméleti tulajdonságainak megtartásával A módszert alkalmassá tettük adaptív környezetben való használatra (concept drift) –
Folyamatosan fut a rendszer
–
A modellek életkoreloszlását fixen tartjuk
–
Minden időpillanatban egy jó modell rendelkezésre áll
2012/05/16
MTA, Budapest
22
Adaptivitás
2012/05/16
MTA, Budapest
23
Publikációk ●
●
●
Róbert Ormándi, István Hegedűs, and Márk Jelasity. Asynchronous peer-to-peer data mining with stochastic gradient descent. In Emmanuel Jeannot, Raymond Namyst, and Jean Roman, editors, Euro-Par 2011, volume 6852 of Lecture Notes in Computer Science, pages 528–540. Springer-Verlag, 2011. Róbert Ormándi, István Hegedűs, and Márk Jelasity. Gossip learning with linear models on fully distributed data. Concurrency and Computation: Practice and Experience, 2012. to appear. István Hegedűs, Róbert Busa-Fekete, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Peer-to-peer multi-class boosting. In Euro-Par 2012, Lecture Notes in Computer Science. Springer-Verlag, 2012. to appear.
2012/05/16
MTA, Budapest
24
Megjegyzések ●
●
●
Ha a megvalósított véletlen séta garantáltan uniform, akkor az összes modell bizonyíthatóan az optimális modellhez konvergál Ha a késleltetés és üzenetvesztés statisztikailag független a csomópontoktól, akkor függetlenül a késleltetésektől és az üzenetvesztés mértékétől a véletlen séta továbbra is uniform marad A gyakorlatban természetesen nem kritikus az uniformitás, de ez függ az adatbázis komplexitásától, a hálózat méretétől, és a „bias” természetétől is
2012/05/16
MTA, Budapest
25
