Magamról

Saját fotó
Főiskolai, majd egyetemi diplomamunkáimtól kezdve világ életemben, adatok, adatbázisok, adattárházak (leginkább Oracle) környékén mozogtam. Mostanság adattárházasként, adatbányászként élem napjaimat.

2012. május 19., szombat

Csatolási metrika szoftverekben

Előző blogposztom után ért néhány impulzus, ami további tárgybeli téma-firtatásra sarkallt.
MTA-workshop ~ A nagyság átka: nagyméretű hálózatok, adatok és szoftverek problémái

(1) Kovács Gyula az Andego Kft szineiben publikált egy nagyszerű blogposztot, ha mást nem nézünk csak az ábráját, akkor is sokkal érthetőbb lett a megközelítés és precízebb megvilágításba helyezte az egész témát - pláne adatbányász kontextusban -, mint nekem sikerült a vázlatommal.
Modellek nyugdíjban


(2) Gyula megosztotta az MTA-esemény eredeti meghívó linkjét. Ezt most én is megteszem:a teljesség kedvéért.
Tudományos ülésszak „A nagyság átka: nagyméretű hálózatok, adatok és szoftverek problémái” címmel

A meghívón láthatóan volt tehát a hatodik záróelőadás a friss Akadémia-díjas  előadó által:

Gyimóthy Tibor, az MTA doktora: Karbantartási problémák millió sor felett.

Két további lényeges impulzus ért a témában:

(A) A Java levelezési listán lévő közös gondolkodás, ami odáig "fajult", hogy elkezdtem keresni az eredeti előadás alapját képező cikke(ke)t.

(B) Nagy küzdés után megtalált cikk világos, szép, igényes, módszertana adatbányász szívnek kedves.

Columbus: A Reverse Engineering Approach
New Conceptual Coupling and Cohesion Metrics for Object-Oriented Systems

Akik nem akarnak elmerülni a részletekbe azok számára (meglehet torzított) rövid értelmezésem az alábbi.

A cikk előtt én az alábbit gondoltam a csatolásokról:

Csatolás/Coupling, szoros klasszikus értelemben és OO paradigmában - minden osztályok közötti metódus hívás-, mező/property-elérés-, öröklés-, argumentum/paraméter-, visszatérési érték-, kivétel-érintettség (ha Eiffelben lennénk, akkor ideírnám a szabály-érintettséget is) és ha valamit kihagytam akkor bocs.

Csatolás tágabb értelemben minden, információt hordozó, valamilyen erősséget reprezentáló és adott hatást generáló összefüggés/kapcsolat, számomra a legközelebbi angol terminus: a linking.

Adott a szegedi egyetem által több éve kifejlesztett Columbus nevű, C/C++  - szoftverminőséget 58 db metrikán keresztül mérő - reverse engine framework. Az előadáson vesézett Nokia Symbianra is ezt engedték rá tehát.

Az előadás egy picit félrevezető volt, mert ott sokkal bonyolultabb matek látszott. Ezek a cikkek egyszerűbb matekúak, azaz minden téma iránt érdeklődőt buzdítok olvassa el a cikket, mert tényleg érthető)

Az újabb cikk két új metrikát vezet be a régiekből kiindulva
(1) Conceptual Coupling between Object classes (CCBO)
(2) Conceptual Lack of Cohesion on Methods (CLCOM5)

Folyamat:
* Reverse Engine Columbus-szal (cikkben Mozilla projektre)
* Korpusz-építés az alábbiakra (+stoplista)
(1) comments
(2) local and attribute variable names
(3) user defined types
(4) methods names
(5) parameter lists and
(6) names of the called methods.
* Latent Semantic Indexing (LSI) szövegbányászati metódus alkalmazása
* Metrika-kalkulálás, -alkalmazás
* Ezután megkaphatók a releváns kapcsolatok
* Elő kell venni a Mozilla hibaadatbázisát
* Meg kell nézni, hogy a metrikák (azon belül releváns kapcsolatok) hogyan függnek össze a hibákkal
* Prediktív analitika széles tárházával (Weka, 12 algoritmus) szembesítették az immáron 61 db szoftver metrikát -> melyik metrika a legjobb hibaelőrejelző (hibahajlam-feltáró)
* Ez vezet a végső előadói konklúzióhoz: túl sok csatolás túl sok hibához vezethet, ami jobban valószínűsíti a kiváltást.

Konklúzióm (még ha egyedül is maradok vele a világban)

Tiszta világos gondolatmenet a fenti. Az egyedüli meggondolandó az érvényességi tartomány.

Lehet "lázadni" az ellen, hogy a hibák azért vannak, hogy kiküszöböljük őket, meg amúgy is csak az egyszerű emberek raknak rendet, mint tudjuk a "zsenik uralják a káoszt".

Én mégis azt mondom, ahogy a való életben a túl sok hiba elbocsátáshoz vezet a munkahelyen, úgy a szoftverben lévő kritikus tömegű hiba a szoftver kiváltási presszióját növeli. Ennyi. Nem több és nem kevesebb.

A hibákat meg nemcsak kinyilatkoztatás szintjén kell kerülni, hanem rásegíteni hasznos eszközökkel.

Szükséges, de nem elégségesen hasznos, ha a hibákat elektronikusan dokumentáljuk. Ha "ezrével" rögzítünk be hibákat ezt támogató rendszerekbe, az önmagában már deprimálóan hat és rontja a hibajavítás hatékonyságát. Én voltam nem egyszer résztvevője olyan projekteknek (harmadik legutóbbi itthon Magyarországon(!) 1.400 ETL-job verzióváltásos migrálása, 10.000-es nagyságrendű tárolt eljárással, olykor többezer kódsorral elég kevés emberhónap alatt, de legutóbbi két projektem is ilyen alapokon volt problémás redesignjai elött: valahogy tehát én vonzom ezeket) ==> ahol túl sok hiba merült fel túl kevés idő alatt az egész projektet alapjaiban megrengetve.

A tárgyalt potenciális eredmény/lehetőség, a csatolások számának csökkentése. Egybevág az eddigi szemlélettel (nem kell paradigmaváltás), kárt nem okoz, maximum valamennyi ráfordítási igénye van. Analóg módon, például ahogy egy B+ fába se elég elemet beszúrni, utána a fát ki kell egyensúlyozni.

Mindenki mérlegelheti ezt cost-benefit alapon, támogatja-e ezt a munkájában.

Én a magam részéről letettem a voksomat (már régóta akkor még pusztán csak intuitiv alapon), hogy megéri a "lineáris" erőforrásigényű befektetést, potenciálisan progresszíven növekedő komplexitás és hibaszaporodás elkerülése érdekében.

További elágazás Wikipediából kiindulva:
Coupling
Cohesion
Static code analysis
Dynamic program analysis

2012. május 17., csütörtök

MTA-workshop ~ A nagyság átka: nagyméretű hálózatok, adatok és szoftverek problémái

Tegnap délután volt szerencsém ottlenni a Magyar Tudományos  Akadémia kistermében rendezett félnapos workshopon, amin hat nagyszerű, nagy hatású előadást, prezentációt lehetett élvezni.

Igyekszem (kulcsszavakra, "mémekre" koncentrálva) minél kevesebb betűt írni az elhangzott hatalmas és nehéz információáradatból, ráadásul bulvárosítva, hogy könnyebb legyen olvasni, egyébként is a cél csak a figyelem felkeltése.A mondatokra kiegészítést az olvasóra bízom, akit érdekel az adott téma ezt úgy is megteszi.. Részletekért érdemes az irodalom linkjeire klikkelni.

Ami angolul hangzott el, angolul adom vissza, ami magyarul, azt magyarul, a minél kisebb torzítás érdekében.

Tudományos ülésszak "A nagyság átka: nagyméretű hálózatok, adatok és szoftverek problémái"


Időpont: 2012. 05. 16.
Helyszín: MTA Székház, Kisterem (II. emelet)
Üléselnök: Pálfy Péter Pál osztályelnök

Program

13.30 A Matematikai Tudományok Osztálya 2012. évi díjainak ünnepélyes átadása

Ezen a ponton három fiatal negyven év alatti matematikus kapott díjat, különböző területekről.Részletes 10-10 perces felvezető után.Esély nem volt jegyzetelni....

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

14.00 ifj. Benczúr András, PhD: "Big Data": amikor a probléma az adat mérete maga.

* Nagyságrendek
- Google Sorts 1 PB in 33 minutes - 2011.09.07-i adat
- Amazon Store 726 billion objects  - 2012.01.31-i adat (exponenciálisan nő)
- Walmart 100 million objects real-time monitor - 2011.09.12-i adat
- New Relic (ezt már nem tudtam leírni)

(Blogírói megjegyzés, itt bizony érdekes lett volna mondjuk egy eBay is, pláne üzleti intelligencia vonzata miatt)

* Koordináta-rendszerben függőleges tengelyen a real-time sebesség, vízszintes tengelyen a méret. Nem méretarányosan és csak pár név/márka a 40-50-ből.

^
|          |                  |             |  ITlogs
|          |                  |SPSS    |
|          |                  |SAS      |
|          |Matlab       |Netezza |
|          |R               |Hadoop |
|          |Greenplum |
|          |Progress    |
|MySql|      
---------------------------------------->

* Big Dataról szólt a kötelmúltban:
(1) VLDB 2011 konferencia
(2) SigMod 2011 konferencia
(3) Gartner
Stb.

* Nagy kérdés miért most lett hype?!
- De rossz hír a lineárisnál lassabb algoritmusoknak
- Managing Gigabytes könyv. Régen íródott (1994) ez a címében is látszik :o)), de ma is aktuális dolgok vannak benne.

* Moore-törvény
- Eddig 18 havonta sebesség duplázódás
- Innentől 18 havonta mag-duplázódás (CPU,GPU) /Sebesség már nem tud nőni, elméleti okokból/

* Nevezéktan:
- Multi Core -> CPU
- Many Core -> GPU

* Technológiában még:
- Cloud
- Flash Diskes külső tárak terjedése

* Régóta létező közismert gráf-probléma, minimális feszítőfa keresése
- Még mindig nyitott kérdés, hogy van-e lineáris idejű determinisztikus algoritmus általános élsúlyokra. 
- A feladatot párhuzamosított algoritmussal is sikerült megoldani. 8 processzoron mára már ötször gyorsabb, mint egy optimalizált szekvenciális algoritmus (2003-as adat). 
- A legelső tárgybeli cikk 1980-ra datálódik, de az előadó szerint lehet még ennek is van előzménye.
És hogy miért érdekes a minimális feszítőfa?

* Mert az azonosság-feloldástól (entity-resolution, record linkage,  deduplikálás) a képszegmentálásig csomó probléma erre vezethető vissza. Ezek közös jellemzői, hogy igen sok adat bír fegyülemleni, amit ugye lineáris műveletigénnyel kéne feldolgozni.

* Az előadó csapata egy biztosítónál három módszert is összevetett.
- Distributed key-value store http://project-voldemort.com/
- MapReduce, Hadoop https://hadoop.apache.org/
- Bulk Synchronous Parallel http://en.wikipedia.org/wiki/Bulk_synchronous_parallel

* Vannak még
- Superstep
- Apacha Hama
- Google Pregel
- Graphlab

* Van a híres háromszög a Fox Brewer CAP-tétel kapcsán
http://en.wikipedia.org/wiki/CAP_theorem
A háromszög csúcsaiban
- Elérhetőség
- Konzisztencia
- Particiónálási hibatűrés
Elosztott rendszerben egyszerre csak (bármelyik) kettő garantálható a fenti háromból, mind a három nem.

* Nem jók osztott memóriára
- DeDup közismert blocking algoritmusai
- Locality Sensitive Hashing
Blogírói megjegyzés: ettől még van MapReduce implementáció a deduplikálásr, tudtommal.

* Big Data
- Adatbányászat
- Keresés
- Gépi tanulás
- Hálózatelmélet

* Mai terep jellemzői
- Korlátok
- Hibatűrési problémák
- Adatintenzív műveletek
- Kiforratlan algoritmusok (Hama, Bulk Synchronous Parallel, stb.)

Irodalom:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

14.25 Huszti Andrea PhD: Biztonságos e-alkalmazások.

(1) E-szavazás

* Elvárások:
- Jogosultság
- Titkosság
- Csak egyszer lehessen szavazni
- Individuum-ellenőrzés (megnézhessem, az látszik-e amit adtam)
- Univerzális ellenőrzés (passzív külső szemlélő is ellenőrizhessen)
- Igazságosság
- Megvesztegethetetlenség

(2) E-vizsgáztatás
- Eléggé azonos az e-szavazással
- Demó projekt az egyetemen
- Titkos a vizsgázó is, vizsgáztató is
- Plusz dolog: visszaállítható anonimitás (ki adott végül jegyet -> leckekönyvben már nevesíteni kell)

További lehetőségek:
(3) E-kérdőv
(4) E-közvéleménykutatás
(5) E-aukció
(6) E-pályáztatás (ne lehessen tudni ki a pályázó és ki bírál)

Irodalom:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

14.50 Jelasity Márk PhD: Kollektív tanulás milliós hálózatokban.

* iPhone, iPad exponenciálisan nő 100 milliós nagyságrendben

* Szenzorok, gazdag kontextus. Egyenes út a kollaboratív adatbányászatig és inkrementális tanulásig

* Felhasználási terület
(1) Egészségügy: járványtól akár cukorbetegség-előrejelzésig
(2) Smart City: forgalom optimalizálás, balesetveszélyes helyzetekre előrejelzés
(3) Földrengés előrejelzés
(4) Pénzügyi alkalmazások

* Architektúra: p2p, grid

* Három problémával kalkulálni kell:
(1) Késhet adat kommunikációnál
(2) Veszhet el adat
(3) Cserélődhet a sorrend

* Kaotika megjelenése

* Teljesen elosztott modell. Horizontális az elosztottság
- Kevés adat a csomópontokon, adott esetben egyetlen rekord
- Adatmozgás nincs, se csomopontok között, se big data szerverre fel (adatvédelem)
- Csak modell-adatok (paraméterek) közlekednek, cserélődnek a csomópontok között
- Annyi kell, hogy az újabb csomópontokon a bejövő modelladatok, és az adott csomóponton képződő kevés lokális adat alapján
(1) Rekonstruálható legyen a teljes addigi modell.
(2) Eldönthető legyen, hogy ez új lokális adat javítja-e modellt avagy ignorálandó.
(3) A permanens szavazás (inkrementális tanulás) révén megszülető predikciót meg lehessen tenni a csomópont kijelzőjén.

* Mindezt un. online algoritmussal. Jellemzők:
(1) Egyszerre egyetlen rekord (véletlen)
(2) Modell-javítás például súlyfüggvény módosítással á lá SVM.

* Sztochaisztikus Gradiens módszer közismert módszer

* Az előadó csapata által kidolgozott módszer alapja:
(1) Pletyka tanulás (Gossip Learning)
(2) Véletlen séták (csomópontok között)
(3) Eközben történik a modell javítása

* Algoritmus-részletek:
(1) Például alábbi demo-választással: Z=merge(x,y)=(x+y)/2 (átlagolás)
(2) Adaline Perceptron
(3) Exponenciálisan nöhet a propagált modellek száma, időben lineárisan
(4) Szavaztatás, például többosztályos boosting vonalán

Blogírói megjegyzés: ez az egész valami eszméletlen szép gondolatkör, óriási potenciállal.Időben lineárisan propagált exponenciálisan növekvő számú modellek melleti gépi tanulás, adatvédelem mellett: GYÖNYÖRŰ.

* Hallgatóság soraiból:
Kérdés: mekkora az érzékenység "rémhír" terjesztésre
Válasz: Ez valóban kritikus pont, szakirodalom intenzíven foglalkozik a témával.

Irodalom:
Asynchronous peer-to-peer data mining with stochastic gradient descent.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

15.15 Kávészünet

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

15.45 Pataricza András, az MTA doktora: Modellezés az informatikai rendszerek komplexitásának uralására.

* Tele van a folyamat kőkemény matematikával
- Specification
- Transformation
- Design modell
(1) Parametrization
(2) Simulation
(3) verification, validation (consystency)
(4) optimization
(5) Partitioning
(6) Scheduling
- Communication Synthesis
- Behavior Modell & Implementation, testing - Hardware & Software Synthesis

* Szemantikus modellezés, ontologiák
- Catalog->Glossary->Thesaurus->Informal->...->Metamodell
- A fentire analóg, hogy népi építészet elvei fogásai öröklődtek generációkon át, ezt kéne matematikai formalizmusba önteni
- Kritikus folyamatoknál, repülésirányítás,  megkövetelnek matematikai helyességbiznyítást

* Analóg példa, régen minden gyárnak saját generátortelepe volt, majd jött az áramszolgáltató, ma mindenkinek saját architektúra, jön a Cloud

* Cloudban egyenként sokszor 200 millió rekord, benne ha 6000 rossz, az már panaszt generálhat: hatásában olyan, mint a PC-t hirtelen áramtalanítani.

* Régen minden jól működjön, ha a részek működnek, ma már, ha a részek nem működnek jól, akkor is működjön.

* Dependability
- online algoritmusok, inkrementális tanulás itt is előjött
- "All in the runtime" - nyitott a matekja
- "Be ready for change" - kis változásnál ne kelljen mindent újraszámolni.
- "A matematika az intelligencia forrása"
- Fókusz: test, maintenance, memory, speed, energy

Irodalom:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

16.10 Beszédes Árpád PhD: Függőség elemzés nagy rendszerekben.

* VÁLTOZÁS menedzselése a szoftver életciklusában
(1) Változás igénye, költségbecslés
(2) Változás helyeinek azonosítása a forráskódban
(3) Változás hatásanalízise, ami egy keresési feladat, nincs tutiság (hatékony és egyúttal biztonságos mód, vannak egyszerűbbek és szofisztikáltabb módszerek) rá, rejtett összefüggés is lehet sajnos. (A blogírói olvasat az, hogy dekomponálás és kicsi komponensekre helyességi bizonyítás egy alternatív életképes lehetőség)
(4) Változás elvégzése
(5) Változás propagálása
(6) Ellenörző és regressziós tesztelés

* Függőségelemzés lépései
(1) Entitásazonosítás
(2) Függőségi gráf konstruálása
(3) Függőségi gráf bejárása (programszeletelés=program slicing)
(4) Dinamikus futásidejű infók is gyűjthetők

* Léteznek (nagy) függőségi klaszterek, amiket jó lenne eliminálni tudni

* Hatásanalízis. Irányok:
(1) Felfele milyen hatásokat generál a tesztelés felé.
(2) Lefele: milyen érintett eljárások vannak a változás kapcsán

* Létezik a "tesztkönyvtárban"
(1) Tesztszelekció, csak azt kell tesztelni ami érintve van
(2) Tesztpriorizálás

* Az említett függőségi gráf általánosítható (nem csak programok körében müködik). Blogírói olvasat, ez az említett függőségi gráf/hálózat egy irányított gráf, hálózati analizist is megérdemelhet.

* Mozilla-projekt függőségi gráfjának futási ideje 113 perc, ami már hatékonynak mondható, innentől már az elemzés is gyors.

* Webkit-projekt
(1) 2.000.000 kódsor
(2) 90.000 eljárás
(3) 25.000 teszteset
(4) 113.000 revizió
(5) 33.000 revizió pár (romlott, ami aztán kijavult)

Irodalom:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

16.35 Gyimóthy Tibor, az MTA doktora: Karbantartási problémák millió sor felett.

* A szoftver öregszik, erodálódik.

* OK: folyamatos változás. Az blogíró adatbányász énje ehhez hozzáteszi, hogy az változás nélkül pusztán az adat is tönkremehet az idő során a szoftver/modell alatt. Ezért kell "change point detection", hogy behatárolható legyen az adatbányászati modell invaliddá válása, a legrövidebb időn belük, a veszteségek minimalizálása érdekében.

* Szoftverváltozás fajtái:
(1) Új dolgok
(2) Hibajavítások

* A változást kezelni, uralni kell, a kulcs hozzá a változásmanagement.
- A túl sok változás vége sokszor a szoftver kidobása, kiváltása mással.
- A változások uralásához egy (szellemes) könyvcím: Waltzing with Bears: Keringő a medvékkel.

* Változási gondjai:
(1) Indokolatlan kapcsolatok szaporodása
(2) Felesleges kód
(a) unreachable.
(b) dead code (ami már taposó akna lehet)
(3) Copy-paste arány romlása

* Változás költségét, időigényét nehéz becsülni.

* Symbian, 30 millió C++ kódsor, az indokolatlanul elszaporodott kapcsolatok miatt "halt meg".

* Ha nézünk egy kódsort, akkor ennek a kódsornak
(1) lefelé is van hatása mely kódsorokat érinti a változása, illetve
(2) adott kódsorok változása őt is érinthetik.
Lásd elöző prezi: mindkét irány fontos.

* Pointer tömbök szaftos problémákat tudnak generálni.

* Programszeletelés fajtái
(1) Statikus
(2) Dinamikus, könnyen gyorsan nagyon nagy lehet a kezelendő függőségi gráf

* Programszeletelés nehezen skálázható, 100.000 kódsor felett már gond van.

* METRIKÁK:
(1) Eljárás kódsorainak száma
(2) Komplexitás: hány if jellegű
(3) Kohézió
(4) Csatolási
(5) Bad smell @ copy-paste
(6) Kódolási szabálysértés

* Kérdés melyik metrika a legjobb (hiba)előrejelző? Kijött, hogy a CBO, vagyis a csatolási metrika. Az előadó elmondása szerint, aki most kapott Akadémiai díjat egyébként, óriási azonnali impactja volt ennek. Egy friss konferencia fő cikkei, keynote előadása is hivatkozta az eredményt és azonnali 300 független hivatkozást generált a tudományos kutató közösségben. Magyarán a csatolási metrikára nagyon érdemes odafigyelni. :o)))

* Konkrét projekt: Mozilla
(1) 3000 osztály
(2) 250.000 hiba.

A témának szenteltem egy újabb posztot:
Csatolási metrika szoftverekben

Irodalom:

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *