Teljesen elosztott adatbányászat alprojekt Hegedűs István, Ormándi Róbert, Jelasity Márk
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Big Data jelenség
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Big Data jelenség
Exponenciális növekedés a(z): −
okos eszközök használatában, és
−
a szenzor- és egyéb “kontextuális” adatok mennyiségében
→ Remek lehetőség az adatbányászatra
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Jelenlegi rendszerek
Főleg felhő alapú megoldások: – Fenntartási költség – Privacy: az adatokat felhasználhatják: • Üzleti döntéstámogatásra • Meglévő software termékek “okosítására”, pl:Google news, Google Now, Gmail SPAM filtering, Evernote tag classification, Siri, Shazam
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Cél
Teljesen elosztott (infrastruktúra nélküli) → nincs központi kontroll Adatvédelmi szempontok szem előtt tartása → nincs harmadik fél, nincs mögöttes érdek Határtalan skálázódás Hasonló vagy jobb minőségű szolgáltatások Nyílt rendszer → nem profit, hanem (köz)haszon orientált
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Rendszer- és adatmodell
Rendszermodell: – Nagyon nagyszámú csomópont (eszköz)
üzenetküldés alapú kommunikáció nincs garancia vagy visszacsatolás az üzenet megérkezéséről (csomagkésés és vesztés)
– NAT −
Aszinkron kommunikáció
−
Felhasználók tetszőlegesen és gyorsan ki- és beléphetnek (churn)
• Elvárás: −
Terhelés elosztás → csomagok mérete, mennyisége kezelhető legyen TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Rendszer- és adatmodell
Adatmodell: – horizontálisan partícionált adatok – eszközönként kevés adat → nem elegendő lokálisan végzett modellépítésre
Elvárások: – az adatrekordok (nyers formában) nem hagyhatják el az eszközt! → privacy – a modellek használata (predikció) lokálisan történjen → skálázódás
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Pletyka alapú tanulás
Előfeltételek: – Overlay hálózat: virtuális hálózat (gráf) ami mentén az eszközök kommunikálnak – Peer sampling service: felsőbb rétegek számára szomszédok biztosítása a fenti rendszermodellben → Ilyen protokollok léteznek, lásd pl. Newscast (Márk korábbi munkáiból)! – Newscast: • Csomópontonként O(1) kommunikációval, nagy valószínűséggel online, uniform véletlen szomszédok biztosítása a fenti rendszermodellben TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Pletyka alapú tanulás - osztályozás
Felügyelt osztályozási probléma: −
Adott: (xi,yi) párok halmaza a csomópontokon
−
Cél: építsünk egy f paraméterezett modellt, hogy fw(x)=y teljesüljön (nem csak a tanítópéldákra!)
−
Megvalósítás: gyakran valamilyen célfüggvény minimalizálásával: Logisztikus/Lineáris regresszió, ANN, SVM, stb...
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Pletyka alapú tanulás - SGD
Tfh. egy osztályozási hiba adott
n
Err ( w )= ∑ Err ( w,x i ) i=1
n ∂ Err w,x ( i) ∂ Err ( w ) =∑ ∂w ∂w i=1 n ∂ Err w,x A teljes grádiens frissítés ( i) (teljes adatbázis ismeretew ( t+ 1 ) =w ( t )−α ( t ) ∑ ∂w i= 1 szükséges)
A hiba grádiense a paraméter függvényében
Grádiens lépés egy tanítópéldával (sztochasztikus változat; uniform mintavételezés kritikus)
w ( t+ 1 ) =w ( t )−α ( t )
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
∂ Err ( w,x i ) ∂w
Pletyka alapú tanulás - GoLF
Pletyka alapú tanulás – Gossip Learning Framework (GoLF): −
Alkalmazzunk online tanulókat (pl. sztochasztikus gradiens)
−
Amely modellek (kezdeményei) véletlen sétákat tesznek a hálózatban
−
A csomópontoknál lévő adatokkal frissítik magukat (pl. sztochasztikus gradiens lépés)
−
Lokális és/vagy globális kombinációs módszerekkel kombinálják a modelleket
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Pletyka alapú tanulás - GoLF
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
Pletyka alapú tanulás - GoLF
Predikció: −
Lokális: egy modell alapján
−
Szavaztatott: több modell többségi döntése mentén
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
GoLF - Eredmények
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
GoLF - 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 Proceedings of 17th International European Conference on Parallel and Distributed Computing, EuroPar'11, Bordeux, France, 2011. Róbert Ormándi, István Hegedűs and Márk Jelasity. Gossip learning with linear models on fully distributed data. In Concurrency and Computation: Practice and Experience, CPE, 2012. István Hegedűs, Róbert Busa-Fekete, Róbert Ormándi, Márk Jelasity and Balázs Kégl. Peer-toPeer Multi-Class Boosting. In Proceedings of 18th International European Conference on Parallel and Distributed Computing, EuroPar'12, Rhodes, Greece, 2012. István Hegedűs, Róbert Ormándi and Márk Jelasity. Gossip-based Learning under Drifting Concepts in Fully Distributed Networks. In Proceedings of 2012 IEEE Sixth International Conference on Self-Adaptive and Self-Organizing Systems, SASO'12, Lion, France, 2012. István Hegedűs, Lehel Nyers and Róbert Ormándi. Detecting Concept Drift in Fully Distributed Environments. In Proceedings of 2012 IEEE 10th Jubilee International Symposium on Intelligent Systems and Informatics, SISY'12, Subotica, Serbia, 2012. Balázs Szörényi, Róbert Busa-Fekete, István Hegedűs, Róbert Ormándi, Márk Jelasity and Balázs Kégl. Gossip-based distributed stochastic bandit algorithms. In Proceedings of The 30th International Conference on Machine Learning (ICML), 3rd Cycle, Atlanta, USA, 2013.
TÁMOP-4.2.2/B-10/1-2010-0012 projekt
