KDD MLG Workshop, 2010 - Hírek másodkézből

.
Sajnos nem lehettem ott a neves eseményen, ahol az akadémiai és üzleti világ körülbelül 900 embere tolongott információért. Viszont láttam olyan embert, aki ott lehetett. :o)

Előszöris, MLG! Ez nem más mint Mining and Lerning Graph, azaz gráfok (adat)bányászata. A Workshop igen szellemesen fogalmazta meg a legfontosabb 'hot topic'-okat, tulajdonképpen ennek leírásáért is születik ez a blog-bejegyzés.

(1) Időben változó gráfok tanulása, modellezése
(2) Rejtett változós modellek gráfoknál
(3) Skálázás nagy gráfokra (lásd még bioinformatika)
(4) Gráfok vizualizációja
(5) Gráfalgoritmusok validálása
(6) Gyakori részgráfok keresése.

A poén az, hogy általánosságban is ezek a 'hot topic'-ok, a 'gráf' szó elhagyásával.

Így első ránézésre, meg az információs sokk csillapodása után, az én szőrszálhasogató vénám azt súgja /nemkicsit képzavar? :o)/, hogy a fenti témák nem egyforma súlyúak. Miközben az (1), (3), (6)-ról maximálisan elhiszem, hogy komoly fejlődési pontenciált tartalmaznak, nehéz és létező problémák, addig a többivel vannak horderő és kiérleltségi problémák.

Az (1) időben változó gráfoknál, ahol az idővel egyszerre változhat (szünhet meg illetve keletkezhet) csúcs, él, topic/cimke, sőt a topic-ok korrelációja is változhat, ezt lemodellezni, az valós probléma és nem kis kihívás. Az egyik Workshopon előadó cikkíró performanciális gondok miatt a legdurvább esetet kénytelen volt 2000 gráfcsúcsról 500 gráfcsúcsra leredukálni. Miközben úgy tűnt a párhuzamosításban rejlő lehetőségekkel nem foglalkozott.

(2) Rejtett változós gráfoknál nem igazán fogtam fel a "rejtett változó" értelmét. Én értem, hogy a gráfélekhez valószínűségek voltak rendelve, meg SVD(=Singular Value Decompsition) analógia miatt a látens szemantikiai indexelés is képbekerül, meg az LDA(=Latent Dirichlet Allocation)-ban is ott a rejtett kulcsszó. De nekem valahogy csak az jött le, hogy itt gráfklaszterezésről van szó, ahol a klaszterek kezdetben nyílvánvalóan rejtettek, azt' mondhatni semmi több. Valahogy csak terminológiai különbségeket bírtam felfedezni, ha próbáltam az alapproblémát hétköznapira lefordítani. Persze ez túlzott szimplifikáció, azért ennél szinesebb a téma.

Ami még lejött nekem, hogy míg egy neurális hálónál csak az elgoritmus fekete doboz, itt gyakorlatilag minden. A klaszterek, az algoritmus, sőt maga a végeredmény kiértékelése sem ad túl sok fogodzót. Magyarán csomó adatból számolunk valamit, amit mind interpretálni, mind mérni, nagyon nehéz. Elképzeltem, hogy egy ilyen modellt, ha el kéne adnom az üzleti életben, hát lehet, hogy felkopna az állam. :o) De legyünk optimisták, fejlődhet ez még emberbarátibb irányba.

(3) A gráfok vizualizációja egyértelműen nem az én témám (se régen, se aktuálisan, se a jövőben). :o) Én már ott megvagyok lőve, hogy ugye eleve képernyőn akarjuk megjeleníteni a gráfokat. Ott eleve nem lehet sok gráfcsúcsot megjeleníteni. Magyarán kisméretű a probléma, azt számol ki az ember, amit akar (megjelenítési koordinátákhoz). Ilyenekre vannak függvénykönyvtárak; egész egyszerűen nem látom a fejlődési potenciált az ügyben. De ha ezen továbblépünk is, az hogy egy gráfot hogyan jelenítünk meg, mi szép és mi nem szép, az annyira szubjektív, hogy már fájdalmas.

Az alapprobléma megfogalmazása azért szép:
* Gráfcsúcsok ne legyenek egymáshoz se túl közel, se túl távol
* Gráfcsúcsok egyenletesen oszoljanak el a képen
* Az élhosszak is egyenletesen oszoljanak el.
* Minél kevésbé messék egymást az élek.

Fizikai analógia: legyen rugó minden él, ha elengedjük a rendszert, amit felvesz formát, közel úgy nézzen ki a gráf. Számolási műveletigénye ennek a legtragikusabb, de optimalizálás után is köbös. Egy trendi módi: SSN-LDA.

Érdekes ötlet: vizualizáció, mint információ-visszakeresési probléma (arra való visszavezetés)

Érdekes és szellemes - objektíven számolható - minőségmérés, a gráfvizualizációra:
Közelebb kerül, aminek távolabb kéne kerülni (precision)
Távolabbra kerül, aminek közelebbnek kéne (recall)
Bennem némileg analógiát kelt a klaszterezés minőség mérésére (klaszteren belüli és klaszterek közötti távolságok aránya)

Számomra új távolság fogalom: Hellinger távolság.

Én ehhez azt tenném hozzá, szubjektíve, hogy amit én elvárok egy gráfvizualizációtól, az nem más, mint
* Nagyon gyorsan lehessen mindkét irányba zoomolni
* Könnyen lehessen csúcsokba beleklikkelni, további információkért.
Ennek szép példáját láttam a Sixtepben

(5) A gráf algoritmusok validálása témában én már ott meg voltam lőve, hogy mi volt a KDD Worshopon gráfspecifikus, sőt magát az egész témafelvetést nem értettem. Úgy látszik ma nehézfejű napom volt. De a legfőbb problémám ott volt, hogy fekete dobozként kellett elképzelni, mind a problémát, mind a rajta dolgozó algoritmust. Csak az képezte vizsgálat tárgyát, hogy a végeredmény mennyire jó. Ahol én már azt sem értettem, hogy ez miért validálás.

Azért sikerült egy idevágó alapproblémát kicsikarni, hogy némileg el lehessen az egészet képzelni: képzeljük el, hogy van diákok hálózata, ahol a diákok a csúcsok, az élek reprezentálják, mondjuk a barátságot. Akkor van él valamilyen súllyal/valószínűséggel, ha két diák barát. Cimkézzük meg a csúcsokat aszerint, hogy dohányzik-e a diák vagy sem. Kezdetben pár csúcs cimkézett, feladat cimkézzük meg a maradékot. A feladat értelmes gráfon belül is, meg gráfok között is.