Önszervező hálózatok formális nyelvi megközelítése Tézisfüzet Lázár Katalin Anna
Eötvös Loránd Tudományegyetem, Informatikai Doktori Iskola vezető: Dr. Demetrovics János Információs rendszerek doktori program vezető: Dr. Benczúr András
Témavezetők: Dr. Csuhaj Varjú Erzsébet Magyar Tudományos Akadémia Számítástechnikai és Automatizálási Kutatóintézete Eötvös Loránd Tudományegyetem, Informatikai Kar, Algoritmusok és Alkalmazásaik Tanszék Dr. Lőrincz András Eötvös Loránd Tudományegyetem, Informatikai Kar, Programozáselmélet és Szoftvertechnológiai Tanszék
Budapest, 2010. május
1.
Bevezetés
Az önszervező rendszerekkel több tudományterület is foglalkozik [8]. Annak ellenére, hogy a természetben számtalan formában vannak jelen önszervező struktúrák, mégsem alakult ki egységes vélemény az önszervező rendszerek jellemzőit illetően. A disszertációban alkalmazott megközelítés szerint az önszervező rendszerek résztvevői változásnak alávetett egységek. Az egységek között irányított és összefüggő kapcsolat van, interakciójuk a kapcsolatokon keresztül valósul meg. Éppen ezért ezeket a rendszereket hálózatoknak is nevezhetjük. A csoport egységek kitüntetett halmaza. Egy egység több csoporthoz is tartozhat. A csoport memóriája az adott csoporthoz tartozó egységek kapcsolatainak halmaza. A csoport működése alatt a csoport által nyerhető jutalmak optimalizálását elősegítő szabályok gyűjteménye értendő. A csoport működése magában foglalja a jutalomelosztást meghatározó szabályokat is. Ezek a szabályok versenyt gerjeszthetnek a csoport tagjai között (szelektív tulajdonság). Az önszervező (hierarchikus) tulajdonság azt jelenti, hogy a csoport működése alatt létrejöhetnek új típusú függőségek az egységek közvetlen kölcsönhatásai vagy az egységek által gyűjtött jutalmak alapján is. A disszertációban az önszervező hálózatok modellezésével foglalkozunk. Szintaktikus leírásuk mellett bizonyos jellemzőiket szemantikus és kísérleti szempontból is megvizsgáljuk. A szintaktikus megközelítés során az önszervező hálózatok tulajdonságait a grammatikarendszerek elméletében használt eszközök segítségével tanulmányozzuk. A grammatikarendszerek elmélete az elosztott, decentralizált kiszámítás modellezésére alkalmas formális nyelvi konstrukciókkal foglalkozik [10]. A konstrukciókban a komponensek, amelyek a legtöbb esetben Chomsky vagy Lindenmayer típusú grammatikák, közösen dolgoznak, kommunikálnak és együttműködnek egymással valamilyen előre rögzített, vagy csupán működés közben kibontakozó protokoll szerint. A kooperációt vezérlő protokoll a modellek lényeges része. Megmutatható, hogy egyszerű komponensek egyszerű stratégiát követő együttműködése is eredményezhet összetett viselkedést [10]. A disszertációban szereplő önszervező hálózatok viselkedését a grammatikarendszerek két fontos osztályával, a nyelvprocesszor hálózatokkal és az egyszerű öko–grammatikarendszerekkel fogalmazzuk meg.
1
A nyelvprocesszor hálózatok nyelvfelismerő eszközökből vagy komponensekből állnak, amelyek egy virtuális gráf csomópontjaiban helyezkednek el [13]. A nyelvprocesszorok szavak halmazain vagy multihalmazain végeznek műveleteket, miközben átírási és szövegfeltételeket kielégítő szűrők által adott kommunikációs lépések váltakozva következnek egymás után. A nyelvprocesszor hálózatok rendszerének működése állapot–átmeneteken keresztül valósul meg. A hálózat állapotát a komponenseknél lévő szavak halmaza vagy multihalmaza adja meg minden egyes lépésben. Az egyszerű öko–grammatikarendszerek véges számú ágensből és ezek ún. közös környezetéből álló rendszerek [11]. Az ágenseket környezetfüggetlen szabályok, a környezetet egy Lindenmayer rendszer szabályai reprezentálják. Az egyszerű öko–grammatikarendszer adott időpontbeli viselkedését a környezet állapota határozza meg. A környezet állapotának megváltoztatása a levezetési lépéseken keresztül történik. A levezetési lépések során az ágensek a környezetet leíró szóra alkalmazzák valamely, az adott levezetési lépés során végrehajtható környezetfüggetlen szabályukat, az ágensek által át nem írt betűket pedig a környezet Lindenmayer rendszerének szabályai segítségével, a Lindenmayer rendszerekben szokásos párhuzamos módon írja át. Kísérleti szinten a szelektív tanulás és az értékbecslés módszereit használjuk, miközben megköveteljük az evolúciós kényszerfeltételek kielégítését is [9]. A szelektív tanulás során több alternatív megoldás lehetséges egyszerre és az egyedek területért és erőforrásért folytatott harcában a hatékonyabb megoldások maradnak fenn. A döntéshozatal javítása érdekében a megerősítéses tanulás keretrendszerén belül az evolúciós tanulást alkalmazzuk. Egy tipikus megerősítéses tanulási problémában a tanulási folyamatot az aktuális állapot (állapotérték) vagy az állapot–akció pár (állapot–akció érték) által meghatározott hosszútávon felhalmozható jutalom várható értéke határozza meg [19].
2.
A kutatás célkitűzései
A disszertációban önszervező hálózatok szintaktikai leírására alkalmas keretrendszert hozunk létre. Modellezzük a peer–to–peer (P2P) hálózatokat [15], a hálózati barangolók információkeresését [17] és a klaszterképzésben részt vevő ágensek viselkedését [16]. 2
A következő kérdéseket vizsgáljuk: 1. Leírhatók–e formális nyelvi eszközökkel, mégpedig a grammatikarendszerek segítségével olyan fogalmak, amelyek jellemzőek az önszervező hálózatokra? Milyen eredményekkel gazdagíthatja a grammatikarendszerek terminológiájában adott leírás az önszervező hálózatok bizonyos kurrens tárgyköreinek eszköztárát? Milyen módon bővíthető a disszertációban bemutatott önszervező hálózatok grammatikai leírása, melyek a lehetséges jövőbeni kutatási irányok? 2. Hogyan adhatók meg az önszervező hálózatokat modellező grammatikarendszerek egyes komponensei, melyek a komponensek együttműködésének szabályai? 3. Mekkora az önszervező hálózatokat modellező grammatikarendszerek viselkedése és összetettsége fokmérőjének tekintett generatív erő? A fenti kérdéseknek megfelelően a következő kutatásokat végeztük: 1. A P2P rendszerek viselkedésének leírására multihalmazokat feldolgozó, párhuzamos nyelvprocesszor hálózatokat alkalmaztunk [13]. A formális nyelvi modellben a nyelvprocesszorok csoportokba szerveződnek, az információ küldésére és fogadására csoportszintű (kollektív) és nyelvprocesszor szintű (egyéni) szűrőket használnak [4, 6]. Az információ szűrése szövegfeltételek alapján történik. Megvizsgáltuk, hogy a formális nyelvi modell megfelelően írja–e le a P2P hálózatokat, továbbá azt is, hogy mit mondhatunk az információ dinamikájáról. Kapcsolatot kerestünk a csoportokba szerveződő, kollektív és egyéni szűrőket alkalmazó, multihalmazokat feldolgozó, párhuzamos nyelvprocesszor hálózatok komponenseinél a számítási lépések során megjelenő szavak számának növekedése és bizonyos típusú fejlődő rendszerek (Lindenmayer rendszerek) növekedési függvényei között. 2. A hálózati barangolók információkeresését olyan formális nyelvi modellel írtuk le, amelyben a barangolók közvetlen módon nem kommunikálhattak egymással. Vizsgálatainkat kiterjesztettük arra az esetre is, amelyben a barangolók közvetlen módon is kommunikálhattak. A kommunikáció hatékonyságát számítógépes szimulációk segítségével elemeztük. 3
(a) A hálózati barangolók információkeresését a grammatikarendszerek keretein belül egyszerű öko–grammatikarendszerekkel fogalmaztuk meg [1, 2, 3]. Az egyszerű öko–grammatikarendszerek fontos jellemzője az, hogy milyen típusú szabályokkal reprezentáljuk az ágenseket. Az egyszerű öko–grammatikarendszerek eredeti definícióját úgy módosítottuk, hogy az ágensek keresési stratégiájának leírására speciális környezetfüggetlen szabályokra épülő előfordulás–ellenőrzéses reguláris átírási eszközöket alkalmaztunk [14]. A reguláris átírási eszközök közül a programozott grammatikákkal foglalkoztunk. Megvizsgáltuk az így kapott grammatikarendszer generatív erejét, tárgyaltuk az egyéb reguláris átírási eszközök és a barangolók keresési stratégiájának bizonyos jellemzői közötti összefüggéseket is. (b) A hálózati barangolók kommunikációjának hatékonyságát különböző gráftopológiákban vizsgáltuk [2, 7]. A barangolók viselkedését valós adatokon, skálamentes világokban, skálamentes kisvilágokban és véletlen világokban is teszteltük [16]. A szelektív tanulási algoritmust hasonlítottuk össze a lineáris függvényapproximáció alapú megerősítéses tanulási algoritmussal. A [17] cikkben szereplő vizsgálatokat, amelyben a barangolók közvetlen módon nem kommunikálhattak és a keresés sem volt témaspecifikus, terjesztettük ki a mostani esetre. Keretrendszerünkben a kommunikáció közvetlen és közvetett módon történhet. A közvetett kommunikációt a jutalomelosztó rendszer motiválja: az információ első beküldője pozitív jutalmat kap. 3. A klaszterekbe szerveződő ágensek viselkedésének leírására olyan egyszerű öko–grammatikarendszereket vezettünk be, amelyek az egyidejűleg aktív ágensek csoportjának meghatározását különböző feltételekhez kötik. Kutatásainkat a [12] cikkben bevezetett csoportképzési módok általánosítása motiválta. A csoportképzési módok meghatározásához szükséges az ágensek kompetenciaszintjének definiálása, amely azt fejezi ki, hogy az adott ágens a környezetet reprezentáló szóból hány szimbólumot képes átírni. Az aktív ágensek csoportképzésének három változatával foglalkoztunk. Az első esetben (d♦q –mód, ♦ ∈ {≤, =, ≥}, q ∈ N0 ) a csoport létrejöttének feltétele az, hogy a csoportot alkotó ágensek kompetenciaszintje legfeljebb/pontosan/legalább q, q ∈ N0 , számú szimbólumban térjen el egymástól. A második esetben (c♦q –mód, ♦ ∈ {≤, =, ≥}, q ∈ N0 ) azon ágensek alkotnak egy csoportot, amelyek által felismerhető szim4
bólumok száma és az ágensek kompetenciaszintje között legfeljebb/pontosan/legalább q, q ∈ N0 , a különbség. A harmadik esetben (t4VB –mód, 4 ∈ {⊆, =, ⊇}, ∅ 6= VB 4VC , VC ⊆ V , ahol V a környezet ábécéje) a csoport alkotásának feltétele az, hogy azon szimbólumok, amelyek az adott halmaz részhalmazaiban/az adott halmazban/az adott halmazt tartalmazó halmazokban és a környezeti szóban is szerepelnek, szerepeljenek az ágensek által felismerhető betűkből képezhető nemüres sorozatokban is. Ezen egyszerű öko–grammatikarendszerek által generált nyelvek kapcsolatát vizsgáltuk a Chomsky–hierarchia nyelvosztályaival és a Lindenmayer rendszerek által generált nyelvosztályokkal, valamint azt, hogy vannak–e ezen csoportképzési feltételek alapján szerveződő egyszerű öko–grammatikarendszerek között olyanok, amelyek a rekurzívan felsorolható nyelvek egy alkalmas reprezentációját adják?
3.
A disszertáció eredményei
Az előző fejezetben vázolt céloknak megfelelően mind a modellfejlesztésben, azaz a grammatikarendszerek fogalomkörének új, az önszervező hálózatokban előforduló jelenségek által motivált elemekkel való bővítésében, mind a már létező modellek nyelvleíró erejének és szintaktikai bonyolultságának megismerésében értünk el eredményeket. Az önszervező hálózatokban előforduló jelenségek bizonyos aspektusait kísérleti módon is alátámasztottuk. Az elért eredmények a következőképpen foglalhatók össze: 1. Létrehoztuk a P2P hálózatok formális nyelvi modelljét (3.2. fejezet 11. definíció). Leírtuk a formális nyelvi modell működését (3.2. fejezet 12. és 13. definíció). Megvizsgáltuk az információ dinamikáját (3.2. fejezet 14. definíció). Megállapítottuk, hogy kapcsolat áll fenn a csoportokba szerveződő, kollektív és egyéni szűrést alkalmazó, multihalmazokat feldolgozó, párhuzamos nyelvprocesszor hálózatok komponenseinél a számítási lépések során megjelenő szavak számának növekedése és bizonyos típusú fejlődő rendszerek (Lindenmayer rendszerek) növekedési függvényei között (3.2.1. fejezet 1. tétel, 1., 2. és 3. korollárium, [4]). A P2P rendszerek formális nyelvi megfogalmazása több szempontból is előnyösnek bizonyult: a tanonc peerek (apprentice peers) fogalmának bevezetése lehetővé tette az adaptívitás meg5
fogalmazását, valamint a feladatalapú dinamikus konfigurálás és a pipeline számítások végrehajtását a P2P hálózatokban. Azt is megmutattuk, hogyan építhetők be biztonsági követelmények a matematikai modellbe (3.3. fejezet [6]): hogyan modellezhető és detektálható a SYN csomagokkal történő elárasztásos támadás (SYN flooding attack) és hogyan valósítható meg a Discretionary Access Control [18]. Formális nyelvi feltételeket alkalmaztunk a hibás üzenetek kiszűrésére. Ezen feltételek lokális kielégítése garantálja a rendszer globális tesztelhetőségét. A tesztelés az adott peerre és a peerrel kommunikációt folytató peerekre vonatkozik, így a kombinatorikus tesztelés elkerülhető. 2. Bevezettük az egyszerű öko–barangolórendszerek fogalmát, amelyek speciális környezetfüggetlen szabályokra épülő előfordulás–ellenőrzéses reguláris átírási eszközöket mint komponenseket tartalmazó egyszerű öko–grammatikarendszerek (4.4.1. fejezet 15. és 16. definíció, 4.4.3. fejezet 20. és 21. definíció). Leírtuk ezen rendszerek működését (4.4.1. fejezet 17., 18. és 19. definíció, 4.4.3. fejezet 22., 23. és 24. definíció). A barangolók hatékonyságát számítógépes szimulációkkal teszteltük, vizsgálatainkat arra az esetre is kiterjesztettük, amelyben a barangolók közvetlen módon kommunikálhattak egymással (4.5. fejezet). Az alábbi megállapításokra jutottunk: (a) Az egyszerű öko–grammatikarendszerek környezetének viselkedését, azaz a környezet által meghatározott nyelvosztályt befolyásolhatja az ágens–környezet interakció létrejöttét előíró feltételek minősége is. Igazoltuk, hogy minden véges indexű, rendezetlen szétszórt szövegfeltételekkel adott grammatika (unordered scattered context grammar) által generált nyelv és minden rekurzívan felsorolható nyelv előállítható egyszerű öko–barangolórendszerek környezetei által meghatározott nyelvek adott ábécé feletti szavainak halmazaiként, amelyekben a környezet változását különböző szabályrendszer írja le (4.4.2. fejezet 2. tétel, 4.4.4. fejezet 3. tétel, [1, 2, 3]). Illusztráltuk a reguláris átírási eszközök széles körű alkalmazhatóságát is. (b) Valós és szimulált környezetben végzett kísérletek segítségével bebizonyítottuk, hogy a kombinált tanulási algoritmust alkalmazó témaspecifikus barangolóknál az algoritmus relatív teljesítménye skálamentes kisvilágban, skálamentes világban és véletlen gráfok esetében is javult (4.5. fejezet [2, 7]). Amikor a feladat 6
összetettebbé vált és a környezet a munkamegosztást szükségessé tette, akkor a kombinált tanulási algoritmus teljesítménye a legtöbb esetben legalább annyira jónak, ha nem jobbnak bizonyult, mint akár a szelektív tanulásé, akár a megerősítéses tanulásé. Továbbá a kommunikáció a teljesítményt is növelte és az adaptáció az esetek többségében előnyös volt. 3. Létrehoztuk a klaszterekbe szerveződő ágensek viselkedésének formális nyelvi modelljét (5.2. fejezet 27., 28., 29. és 30. definíció). Leírtuk a rendszer működését (5.2. fejezet 31. és 32. definíció). A következő megállapításokat tettük: (a) Kapcsolat áll fenn a különböző csoportképzési feltételek alapján szerveződő egyszerű öko–grammatikarendszerek között (5.3.1. fejezet 4. tétel, [5]). Következésképpen az ágensek száma lényeges paraméter a klaszterképzés szempontjából a különböző derivációs módokban. (b) A különböző csoportképzési feltételek esetében a környezet fejlődése jelentősen eltérhet bizonyos Lindenmayer rendszerek, valamint bizonyos Chomsky típusú grammatikák viselkedésétől. Bizonyos csoportalkotási feltételek esetében a kiterjesztett, azaz terminális ábécét megkülönböztető egyszerű öko–grammatikarendszerek a rekurzívan felsorolható nyelveket generálják. A nyelvosztályokból, amelyeket ezen rendszerek határoznak meg, az ágensek által megoldható feladat nehézségére következtethetünk. Ezen állítások alapjául a következők szolgálnak: • az egyszerű öko–grammatikarendszerek által generált nyelvosztályok egyik csoportképzési mód esetében sem hasonlíthatók össze sem a reguláris, sem a környezetfüggetlen, sem a T0L nyelvek osztályával (5.3.3. fejezet 6. tétel, 5.3.4. fejezet 7. tétel, [5]); • minden, egy adott ábécé feletti rekurzívan felsorolható nyelv előállítható egy a c♦0 , c=q , c≤q , d=q , ♦ ∈ {≤, =, ≥}, q ∈ N, feltételek mellett működő egyszerű öko–grammatikarendszer környezete által meghatározott nyelvnek az adott ábécé feletti szavainak halmazaként (5.4. fejezet 8. és 9. tétel, [5]); • minden, egy adott ábécé feletti rekurzívan felsorolható nyelvhez létezik olyan egyszerű öko–grammatikarendszer és VB , ∅ 6= VB ⊆ V , halmaz, hogy a nyelv előállítható egy a t=VB , t⊇VB feltételek mellett működő egyszerű öko– 7
grammatikarendszer környezete által meghatározott nyelvnek az adott ábécé feletti szavainak halmazaként (5.4. fejezet 10. tétel, [5]).
4.
Kitekintés
A disszertációban kapcsolatot kerestünk és kapcsolatot építettünk az önszervező hálózatokban használt alkalmazások és a formális nyelvi eszközök között. A disszertáció eredményei gazdagítják a grammatikarendszerek elméletét, hozzájárulnak a nyelvprocesszor hálózatok és az egyszerű öko–grammatikarendszerek tulajdonságainak jobb megértéséhez. A disszertációban vázolt konstrukciók és technikák segítséget nyújtanak adott tulajdonsággal rendelkező formális nyelvi eszközök tervezéséhez is. Amellett, hogy az értekezés megválaszol számos, az önszervező rendszerek elméletében felmerült kérdést, hozzájárul a formális nyelvek elméletének fejlődéséhez azzal is, hogy egyes nyelvosztályok új reprezentációit vezeti be.
Hivatkozások A tézisek alapjául szolgáló közlemények [1] Lázár, K.: A Language Theoretic Approach to the Crawlers’ Problem. In: Ueda, K., Monostori, L., Márkus, A. (Eds.): Proceedings of the 5th International Workshop on Emergent Synthesis (IWES’04), 2004, 19–26. [2] Lázár, K., Csuhaj–Varjú, E., Lőrincz, A.: A Combined Theoretical and Experimental Approach to Goal–Oriented Herds of Internet Crawlers. Proceedings of the European Conference on Complex Systems (ECCS 2009), The University of Warwick, Egyesült Királyság, 2009, 134. [3] Lázár, K., Csuhaj–Varjú, E., Lőrincz, A.: On Eco–Foraging Systems. (beküldve)
8
[4] Lázár, K., Csuhaj–Varjú, E., Lőrincz, A.: Peer–to–Peer Networks: a Language Theoretic Approach. Computing and Informatics 27 (2008), 403–422. [5] Lázár, K. A., Csuhaj–Varjú, E., Lőrincz, A., Vaszil, Gy.: Dynamically Formed Clusters of Agents in Eco–Grammar Systems. International Journal of Foundations of Computer Science 20(2) (2009), 293–311. [6] Lázár, K. A., Farkas, Cs.: Security in Tci NMP Systems. In: Yagüe, M. I., Fernández– Medina, E. (Eds.): Proceedings of the 5th International Workshop on Security in Information Systems (WOSIS 2007), INSTICC PRESS, Portugália, 2007, 95–104. [7] Lőrincz, A., Lázár, K. A., Palotai, Zs.: Efficiency of Goal–Oriented Communicating Agents in Different Graph Topologies: a Study with Internet Crawlers. Physica A: Statistical Mechanics and its Applications 378(1) (2007), 127–134.
Külső hivatkozások [8] Ashby, W. R.: Principles of the Self–Organizing Dynamic System. Journal of General Psychology 37 (1947), 125–128. [9] Clark, C. W., Mangel, M.: Dynamic State Variable Models in Ecology: Methods and Applications. Oxford University Press, Oxford, Egyesült Királyság, 2000. [10] Csuhaj–Varjú, E., Dassow, J., Kelemen, J., Păun, Gh.: Grammar systems. A Grammatical Approach on Distribution and Cooperation, Gordon and Breach, London, 1994. [11] Csuhaj–Varjú, E., Kelemen, J., Kelemenová, A., Păun, Gh.: Eco–Grammar Systems: A Grammatical Framework for Studying Lifelike Interactions. Artificial Life 3 (1997), 1–28. [12] Csuhaj–Varjú, E., Mitrana, V.: Dynamical Teams in Eco–Grammar Systems. Fundamenta Informaticae 44 (2000), 83–94.
9
[13] Csuhaj–Varjú, E., Salomaa, A.: Networks of Parallel Language Processors. In: Păun, Gh., Salomaa, A. (Eds.): New Trends in Formal Languages, Control, Cooperation and Combinatorics. Lecture Notes in Computer Science 1218 (1997), 299–318. [14] Dassow, J., Păun, Gh.: Regulated Rewriting in Formal Language Theory, Springer– Verlag, New York, 1996. [15] Flenner, R., Abbott, M., Boubez, T., Cohen, F., Krishnan, N., Moffet, A., Ramamurti, R., Siddiqui, B., Sommers, F.: Java P2P Unleashed. Sams Publishing, 2001. [16] Newman, M., Barabási, A. L., Watts, D. J.: The Structure and Dynamics of Networks. Princeton University Press, Princeton, NJ, 2006. [17] Palotai, Zs., Farkas, Cs., Lőrincz, A.: Is Selection Optimal for Scale–Free Small Worlds? European Conference on Complex Systems 2005, Paris, 2005. november, ComPlexUs 3 (2006), 158–168. [18] Pfleeger, Ch. P., Pfleeger, Sh. L.: Security in Computing. Prentice–Hall, New Jersey, USA, 2003. [19] Sutton, R., Barto, A.: Reinforcement Learning: An Introduction, MIT Press, Cambridge, 1998.
10
