Jel-jelentéspárok egyeztetése többágenses környezetben. Görög Márton

Jel-jelentéspárok egyeztetése többágenses környezetben

Görög Márton Diplomaterv

Konzulensek Lőrincz András, Feldhoffer Gergely

Műszaki Informatika szak Információs Technológiai Kar Pázmány Péter Katolikus Egyetem Budapest, 2010

Alulírott Görög Márton, a Pázmány Péter Katolikus Egyetem Információs Technológiai Karának hallgatója kijelentem, hogy ezt a diplomatervet meg nem engedett segítség nélkül, saját magam készítettem, és a diplomamunkában csak a megadott forrásokat használtam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben, de átfogalmazva más forrásból átvettem, egyértelműen a forrás megadásával megjelöltem. Ezt a diplomamunkát más szakon még nem nyújtottam be.

Görög Márton

Tartalomjegyzék 1. fejezet

Tartalmi összefoglaló ............................................................................................. 1

2. fejezet

Abstract................................................................................................................... 2

3. fejezet

Bevezetés ................................................................................................................ 3

3.1

Kooperáció ................................................................................................................. 4

3.2

Kommunikáció ........................................................................................................... 5

3.3

A dolgozat felépítése .................................................................................................. 7

4. fejezet

A feladatkiírás pontosítása, elemzése ..................................................................... 8

5. fejezet

A felhasznált eszközök ........................................................................................... 9

5.1

Pacman ....................................................................................................................... 9 Szabályalapú vezérlés ....................................................................................... 10

5.1.1 5.2

Nyelvi emergencia algoritmus .................................................................................. 10 Az optimalizációs algoritmus ........................................................................... 12

5.2.1

Módszer, a munka részletes ismertetése ............................................................... 14

6. fejezet

A Pacman és a nyelvi emergencia összeillesztése .................................................... 14

6.1

Szoftverarchitektúra.......................................................................................... 14

6.1.1 6.2

A hiba mérése ........................................................................................................... 16

6.3

Leállási feltétel ......................................................................................................... 17

6.4

Összehangolódási stratégiák ..................................................................................... 18

6.4.1

Nyelvi emergencia algoritmus .......................................................................... 18

6.4.2

Fix súlymátrixokból választó............................................................................ 18

6.4.3

Win-Stay, Loose-Random ................................................................................ 21 Random üzenetküldő és ennek kiszűrése ................................................................. 22

6.5

Terhelési módszerek, eredmények........................................................................ 24

7. fejezet 7.1

Reprodukálás ............................................................................................................ 24

7.2

Zajtűrés: különböző világlátás, zárt kommunikáció ................................................. 25

7.2.1

A leképezés eltérésének mérése........................................................................ 25

7.2.2

CE alapú nyelvi emergencia ............................................................................. 26

7.2.3

Fix súlymátrix ................................................................................................... 28

7.2.4

Összehasonlítás................................................................................................. 30

7.3

Zajtűrés: különböző világlátás, nyílt kommunikáció................................................ 31

7.4

Zajtűrés: zajos kommunikációs csatorna .................................................................. 33

7.5

Zajtűrés: eltűnő üzenetek .......................................................................................... 33

7.6

Zajtűrés: Eltolódva érkező üzenetek......................................................................... 34

7.7

Szimuláció közben beszálló – kilépő játékosok ....................................................... 36 Összehasonlítás komplex algoritmusokkal ........................................................... 39

8. fejezet 8.1

Rekonstrukciós elv nélküli tanuló ............................................................................ 39

8.2

Orthogonal Matching Pursuit ................................................................................... 39

8.3

Subspace ................................................................................................................... 40

8.4

Feed-forward ............................................................................................................ 41

8.5

Összehasonlítás......................................................................................................... 41

8.5.1

Zavaró körülmények nélkül .............................................................................. 41

8.5.2

Csatorna zaj ...................................................................................................... 42

8.5.3

Ágensek száma zárt kommunikációban............................................................ 43

8.5.4

Késve érkező üzenetek ..................................................................................... 44

9. fejezet

Összefoglaló ......................................................................................................... 45

10. fejezet

Köszönetnyilvánítás.......................................................................................... 47

11. fejezet

Irodalomjegyzék ............................................................................................... 48

1. fejezet Tartalmi összefoglaló

Egyre több környezetben találkozhatunk kommunikációra képes ágensekkel akár a virtuális térben szoftverek formájában, akár a valós környezetünkben gépek formájában. Ezek legtöbbször csak ugyanolyan típusú ügynökökkel, vagy más típusúakkal előre megadott módon kommunikálnak rugalmasság, bővíthetőség nélkül. Adaptív módon viselkedni kommunikáció közben kétféle szereposztásban lehet: tanár-diák szerepekben tanulni, vagy egyenrangú felekként felépíteni a jel-jelentés párokat. A dolgozat a másodikkal, az emergens nyelv-építéssel foglalkozik, melynél nincsenek előre rögzített jeljelentés megfeleltetések, a kommunikáció résztvevőiről a legkevesebb feltételezést tesszük. A másik félnek lehet más a célja, lehet más felépítésű, máshogy működő ágens. A közös „szavak” megtalálásához elég egy környezetben lenni (hasonló érzékelés a világról) és nem végleges jelek üzengetésével közösen elnevezni ezeket az észlelt tárgyakat, cselekvéseket, jellemzőket. A nyelvi emergencia folyamatára már léteznek algoritmusok, Lőrincz András és Gyenes Viktor munkáját [1] vettem alapul. Ez a jel-jelentéspár egyeztető módszer a Cross-Entropy nevű kombinatorikus optimalizációs algoritmusra épül. Az átvett implementációt egy keretrendszerbe ültettem, a jól ismert Pacman játék egy kissé módosított változatába, melyben például egyszerre több – szövetséges – Pacman is tartózkodhat a pályán. Egy játék azért hasznos az algoritmus köré, mert így nem egyenletes eloszlású, ideális, könnyen tanulható környezetben tanul, hanem a majdani felhasználásoknak megfelelő, valósághű, kevésbé tiszta jelekkel kell megbirkóznia. Az egyszerre jelen lévő ügynökök alakítanak ki a pályán való mozgás alatt egy közös szótárat, ennek a folyamatnak a sebességét, robosztusságát vizsgálom különböző szempontokból. A CE-alapú algoritmust összehasonlítottam a keretrendszerbe illesztett egyszerű játékelméleti stratégiákból származó módszerekkel és komplexebb optimalizációs eljárásokkal is. A mérések alatt megmutatkozik az összevetett módszerek hibatűrése többek közt a következő esetekben: részlegesen észlelt környezet, zajos üzenettovábbító csatorna, sok jelenlévő ágens, késve érkező üzenetek.

1

2. fejezet Abstract

We can see agents with ability to communicate in more and more environments, let it be a virtual environment as software or a machine in our real world. Most often these agents can communicate only with another one from the same type or with someone else based on a built-in communication process. These communication-scenarios do not need and therefore the agents lack any kind of flexibility or expansibility. There are two ways of adaptive communication: teaching and learning in teacher-student roles of building the sign-meaning pairs as peers. This thesis deals with the second one. The plan is to agree on sign-meaning pairs as a result of the emergent language-building process. There aren‟t any previously fixed sign-meaning pairs and we make as few assumptions about the other agent – what‟s more, about the number of other agents – as possible. The goals, the structure, working mechanism of the other agent can be different, there‟s no need to have the same ones. To harmonize the vocabulary it‟s enough to be in the same environment (to sense the same things) and with messaging the agents give name to objects, properties, actions they observe. With pointing and naming something a meaning and a symbol (sign, word) can be associated. There already exist some algorithm for this “language emergence” problem; I started out with the paper and implementation of András Lőrincz and Viktor Gyenes [1]. This learning method uses „Cross-Entropy‟ combinatorial optimization algorithm. To test the method in a “real” environment, I put it into a variant of Pacman computer game which enables us to put several cooperating Pacman agents to the same map. With this framework, the communication has real inputs, not only the ideal, too clear randomly generated inputs. The agents, who are present at the same environment, build up a dictionary during their movement in the labyrinth, which should contain the same symbols and meaning for each of them. I measure the speed and robustness of the vocabulary-building procedure. I compared the Cross-Entropy based algorithm with other methods inserted to the framework: there are simple strategies from game theory and more advanced optimization procedures too. The tests included the following strains: partially observed environment, noisy medium for messages, high number of communicating agents, delayed messages and some more.

2

3. fejezet Bevezetés Bármilyen valós vagy virtuális világban tevékeny ágenst a közelmúltig a környezetét megfigyelő, tervező és beavatkozó képességekkel láttunk el, melyben a megfigyelés robotok esetén a saját mozgásának és a környezet akadályainak észlelését, szoftver esetén egy meghatározott adatfolyam vizsgálatát jelentette. Sok helyzet létezik, amikor más hasonló komplexitású ügynökökkel kell együttműködni akár egy közös cél érdekében (például gyorsabb együttes feladatvégzés vagy eleve többszereplős feladatbeli együttműködés), akár az egymástól

független

sikeres

működés

érdekében

(zavarok, ütközések

elkerülése).

Amennyiben a találkozó felek egyező típusúak, bizonyára beléjük van kódolva az együttműködés mikéntje, gondolhatunk például az elmúlt évek számítógépes játékainak gépi játékosaira vagy a hálózatok csomópontjaiban forgalmat irányító router-ekre. Könnyen elképzelhető ugyanakkor olyan helyzet is, amikor különböző ágensek kerülnek egy térbe, melyeknek nincsen mindenre kiterjedő szabályozásuk az üzenetküldésre, ezért nem is alakul ki semmilyen kooperativitás. Mit tud kezdeni virtuális környezetben egymással egy letöltő és egy levelező kliens? Semmit, a gyors levélküldéshez az adatforgalom visszafogása érdekében emberi beavatkozásra van szükség ahelyett, hogy a szoftveres ügynökök háttérben zajló kooperációja eredményeképp a levélküldés idejére szünetelnének a sávszélesség-igényes alkalmazások. Valós körülmények közti kooperáció-hiány például, hogy az elektronikával telezsúfolt autók nem beszélnek a garázsnyitók nyelvén. A kooperáció feltétele egy közös szótár, mely a felek közti kommunikáció szabályzata is. Nem szükséges, hogy az ügynökök szótáraiban csak ugyanazok a jel-jelentés párok szerepeljenek, hiszen megértethetem magam egy speciális probléma kapcsán a lehetőségeim töredékével, de ennek a töredéknek közösnek kell lennie. Ilyen különböző ágenseknek viszont nincs feltétlen beépített „szótára”, tehát az általános kooperációhoz hozzátartozik a szótár kialakításának, módosításának képessége, a nyelvi adaptivitás. Ezzel a folyamattal foglalkozik a dolgozat, az egyszerű kommunikációs formák kialakításának módszereivel. Egyszerű eset lenne, ha a kooperáló felek egyike mindig tudná, milyen tudást kell átadnia, ha ismerné a másik fél pontos képességeit, célját. Ebben a tanár-diák szerepben az adaptivitást egyik részről a szótár megfelelő sorainak elküldése, másik részről ezek fogadása és használata lenne. Ez megfelel a szülő-gyerek szerepeknek, alapvetően az emberek is így tanulják meg a nyelvet. Különbözőágensek esetén azonban a másikról nem rendelkezünk információval, sokszor a tanár-diák szerepek nem alakíthatók ki. Az adaptivitás következő lépcsőfoka a nyelv emergens kialakítása: egyenrangú ágensek próbálják meg kialakítani a jel-jelentés összerendeléseket a lehető legkevesebb feltételezéssel.

3

Ekkor egy új, előre nem fixált, bizonyos szempontból logikátlan rendszer alakul ki a résztvevők közös igyekezetésből. A dolgozat különböző „nyelvi emergencia” módszereket hasonlít össze a robosztusság, sikeresség, gyorsaság sokféle mérésével. A legmélyebben tesztelt algoritmus Lőrincz András csoportjának, első szerzőként Gyenes Viktor munkáján alapszik. Ez volt az első publikált módszer, mely sok ágens esetén is 100%os gyakorisággal nyújtott az együttes tanulási folyamat végére összehangolódott ágenseket, esetünkben egyező kommunikációs súlyokat. A módszer publikációjában különböző méréseket közöl, de ezek feltételezik a zaj nélküli környezetet és az állapotok egyenlő eloszlását, ami valós felhasználás esetén nem garantálható. Munkám részeként életszerűbb környezetben tesztelem az összehangolódás sebességét, zajtűrését.

Huttegger és Zollman munkáiból [6], [7] megismertem a gyakran használt egyszerűbb kooperációs stratégiákat, melyek alkalmazhatók a közös nyelv kialakításánál is. A fent említett nyelvi emergencia algoritmusát ezekkel versenyeztetem, hogy demonstráljam a komplex algoritmus erősségét az alternatív módszerekhez képest.

3.1 Kooperáció A kooperációnak négy motivációját különböztetik meg biológia környezetben [12], ezek: 

rövid távú kölcsönösség (mutualism), mely egy adott helyzetben biztosít előnyt együttműködés esetén



rokonság segítése (kin selection), mely első látásra altruista viselkedésnek tűnik, valójában a hasonló gén / viselkedés elterjesztésében segít



hosszú távú kölcsönösség, befektetés a kooperativitásba (reciprocity), melynek megtérülése esetleg nem belátható, nem biztosított



büntetés (sanctioning), melynél a motiváció a büntetés elkerülése.

Ezek közül a bemutatott algoritmust felhasználó alkalmazás dönti el, milyen célból alakítana ki közös nyelvet, ám a kommunikáció nagyon erősen a „hosszú távú kölcsönösséghez” kötődik. Befektetést igényel, mert energiát, időt kell fektetni a nyelv megtanulásába. A legtöbb rendszerben a nyelvtanulás a különféle nyersanyagok, pontok gyűjtésének rovására megy rövidtávon. A „Mind model seems necessary for the emergence of communication” [19] cikk keretei közt az összehangolódást sokszor megakadályozza, ha mindkét fél felteszi, hogy a másik fél

4

egyszerű módon a saját környezete alapján hoz döntést és nem veszi figyelembe a másik résztvevő legvalószínűbb lépését. Az biztosít gyors és biztos konvergenciát, ha az csak az egyik ágens veszi figyelembe a másik lehetséges lépését. A később ismertetett CE alapú nyelvi emergencia algoritmus olyan kooperációs módszer, ahol cselekvéskor figyelembe tudom venni a fogadó felek valószínűsíthető kommunikációs mátrixát. Ez egy kisebb feladat, mint az egész cselekvését feltételezni, de mégis tekintettel tudnak lenni egymásra egyenlően komplex döntési mechanizmussal is. A dolgozatbeli kooperáció üzenetekre korlátozódik, ezt a következő fejezetben részletezem.

3.2 Kommunikáció Minden többszereplős cselekvéssorozatnak alapvető eleme a cselekvőket összekötő kommunikáció, enélkül egymás mellett, de egymástól függetlenül cselekvő szereplők lennének csak. Manapság hangsúlyozzák a kis csoportok fontosságát mind az egyénre, mind a társadalomra nézve; szinte eltűnnek már az egyszereplős PC-s játékok és a leggyorsabban növekvő internetes portálok és programok (wiw, facebook, skype) is mind a közösségi fórumok, együttműködés, kommunikáció új formáit terjesztették el. Ilyen trendek mellett fontossá válnak a kommunikáció kialakulását, stabilitását, fajtáit vizsgáló kutatások és algoritmusok. A kutatások motivációja lehet az emberi kommunikáció jobb megértése szimulációkon keresztül (például: mi hogyan alakulhatott ki?) vagy a virtuális ágensek hasonló képességeinek kifejlesztése ember-módra. A kommunikáció részeit szolgáló algoritmusok általában nem öncélúak, készek kiszolgálni egy felsőbb célt a lehető legkevesebb megkötéssel. Beépíthetők más tudományos kísérlet szimulációjába, emberek szórakoztatására készülő játékba vagy üzleti alkalmazások széles körébe. Az emberi nyelvtanulásról tudjuk, hogy nagyon kevéssé „bedrótozott”, erősen tanult képesség: míg egyértelmű, hogy a szavainkat nem ismerjük születésünkkor, a nyelvtani szerkezetetek, a nyelv leglassabban változó részei is tanulással rögzülnek. Sok élőlény „nyelve” genetikusan rögzített (még ha nem is pontosan ugyanaz egyedről egyedre), az embernél a világ nyelveinek teljes különbözősége elegendő bizonyíték arra, hogy senki sem születik meglévő érzékkel a helyes szórendre vagy a jó hangsúlyozásra. Az agyi területek között elsők közt azonosított beszéd (Broca) és beszédértés (Wernicke) központok mérete, kapcsolatrendszerének sűrűsége és épsége segít jó nyelvérzékkel megáldottnak lenni és gyorsan tanulni. Újabb bizonyítéka a nyelv gyenge genetikus rögzítettségének, hogy még a nyelv struktúrája is sokkal gyorsabban változik, mint ahogy azt genetikai alapú

5

kiválasztódással követni lehetne: az indoeurópai nyelvcsalád kevesebb, mint 10.000 év alatt diverzifikálódott [13]. A nyelv tanulására képessé tesz a dedikált agyi terület (Broca, Wernicke), amelyek létrejötte valószínűleg a Baldwin-effektusnak köszönhető: azok a képességek, amik először teljesen tanultak, de jobb túlélési / szaporodási lehetőségeket biztosítanak az egyednek, a generációk alatt a genetikai állományban is rögzülhetnek [13]. Így gyorsabb tanulást és kiemelkedő adottságokat biztosít azokhoz képest, akik még mindig előröl kezdik a tanulást életük során. Ha elfogadjuk a Baldwin-effektust, mint a nyelv kialakulását erősítő tényezőt, akkor következik, hogy a közös nyelv nem biológiai folyamat eredménye, hanem kulturális eredmény, ami aztán támogatást kapott a gének felől is. A nyelv tanulása fajtól függetlenül tanár-diák szerepben történik: a szülők, nagyobb testvérek tanítják meg a nyelvet a kicsiknek. Ez a természetes folyamat biztosítja a kialakult komplexitás megőrzését és a nagyobb közösség nyelvének stabilitását: ha családon belül egy gyerek születésekor új nyelvet találnának ki, a társadalom csak egymás melletti családokból állna. Létrejöhet ugyanakkor a nyelv egy egyeztetési folyamat végeredményeként is, amikor a folyamat elején senki sem ismeri a végleges szabályokat (szintaktika) vagy szókincset és ezek értelmét (szemantika), hanem minimális közös tudásra építkezve alakítják ki azt. Hogy ilyen hol fordul mégis elő? Aki sokat volt fiatal ikrek közelében, hallhatta a sehonnan sem tanult, mégis kialakuló saját szavaikat, melyek ugyan a „zavaró” felnőttek miatt nem teljesedik ki nyelvvé, de építőelemek létrejönnek így. A kevés szükséges előfeltétel miatt a legkülönfélébb környezetben kialakulhat kommunikáció egymástól különböző ágensek között is. Nincs szükség arra, hogy egyező céljaik, egyező képességeik legyenek a feleknek, így „kompatibilis” egymással bármelyik két, nyelv-alakítása hajlamos kommunikáló egyed. Ilyen kialakuló, emergens módon szótárat építő módszerekkel foglalkozik a dolgozat is. Luc Steels [14] szerint a nyelv két irányból nézve is emergens jelenség. Egyrészt senki sem ismeri teljesen, nem irányítja és nem felelős érte. A nyelvet használói birtokolják és alakítják, a kis hatások összege sodorja. Másodszor spontán módon kialakul, ha teljesülnek a szükséges pszichológiai, szociális és élettani feltételek. Ezek a megállapítások se [14]-ra, se ezen dolgozat szimulációra nem érvényesek, mert nagyon leegyszerűsített módon modellezik a nyelvet. A kommunikáció kritériumai [19] szerint: 

opcionális (bővebben a következő bekezdésekben)



szándékos

6



üzenetük van, tehát jelentést szimbolizálnak



sikeres akkor, ha a részt vevő felek ugyanazt a jelentést társítják egy üzenethez

Az emergens kommunikációnak feltétele továbbá a kétirányúság, ami tanár-diák szerepek esetén nem kötelező. A kifejlesztett szimulációs környezetben az ágensek akkor „szólalnak meg”, ha van bármi üzenni valójuk: ha bármelyik kommunikált jellemző igaz értékű. Mivel az ágens mozgását az elküldött és fogadott üzenetek nem befolyásolják, a kommunikáció jelen rendszerben nincs hatással a pontszámra. Ebből az következik, hogy az ágens nem hozhat döntést arról, megéri-e kommunikálni, magasabb szinten tehát nincs jelen az opcionalitás (fenti kritériumok első pontja), csak az egyes üzenetek szintjén. A többi kritérium teljesül, az üzenetek jelentést hordoznak (bővebben: 5.1.1 fejezet), az egyenrangú szerepben lévő algoritmusok célja pedig pontosan az, hogy ugyanazt jelentse minden ágensnek egy adott üzenet.

3.3 A dolgozat felépítése A témabejelentőn megjelölt feladatokat a következő, 4. fejezetben pontosítom. A készen kapott, felhasznált szoftveres eszközöket az 5. fejezetben mutatom be: például a keretrendszert és a dolgozat központi algoritmusát, a Cross-Entry optimalizációra épülő szótár-készítő módszert. A szimulációs keretrendszer saját fejlesztésű részeit a dolgozat 6. fejezetében ismertetem. Itt a szimulációt biztosító eszközök mellett azokról a kommunikációs stratégiákról lesz szó, amelyekkel a Cross-Entropy alapú módszert a 7. fejezetben össze is hasonlítom. A 8. fejezetben komplexebb matematikai hátterű algoritmusokat vezetek elő, majd még ebben a fejezetben sok szempontból össze is hasonlítom ezeket. A 9. fejezetben foglalom össze a kapott eredményeket.

7

4. fejezet A feladatkiírás pontosítása, elemzése A feladat egy virtuális térbeli kommunikáció kialakítására való algoritmus tesztelése különböző helyzetekben. Az algoritmust (nyelvi emergencia Cross-Entropy optimalizációval) Lőrincz András és Gyenes Viktor publikálta [1], [2]-ben. Először meg kell ismernem munkájukat, a csoport ehhez kapcsolódó korábbi írásait illetve a nemzetközi kutatás ide kapcsoló eredményeit. Szintén a csoport korábbi műve egy számomra hozzáférhető forráskódú, Java nyelven írt Pacman játék variáns, ennek működését, felépítését is meg kell ismernem a munka elkezdése előtt. Ez a játék szolgál majd keretrendszerként a kommunikáció kialakításához, a Pacman ágensek szótárának összehangolását ebben a környezetben fogom tesztelni. Mivel a játékban egyelőre a kommunikáció ilyen formájának nincs helye, ki kell bővíteni. Az ágensek üzenetei a játéktér különböző magas szintű jellemzői lesznek, melyek már implementálva vannak a Pacman szabályalapú irányítása miatt. Ezt vezérlést használom fel és ezt bővítem ki egy kommunikációs modullal. Amint kialakításra került az ágens-kommunikáció a fent említett keretrendszerben, futtatásokat kell végezni a kommunikációs módszer sebességének, robosztusságának kimutatására. Meg kell keresni az összefüggéseket a közös szótár kiépítésének sebessége (összehangolódás) és a közlés gyakorisága, a belső reprezentáció számszerűsíthető eltérései között. Ezek a kimutatások sokszor futtatott szimulációt igényelnek, hogy a kapott eredmények átlagából általánosítani lehessen az összehangolódás más paraméterektől való függésére. Amennyiben váratlan eredmények születnek, azok okait ki kell deríteni (elméleti úton vagy további futtatásokkal) és be kell mutatni.

8

5. fejezet A felhasznált eszközök 5.1 Pacman Az

[1],

[2]

hivatkozásban

részletezett

nyelvtanuló algoritmust egyenletes eloszlású bemenetekkel, tesztelték,

vegytiszta

ezúttal

felhasználásnak környezetben

környezetben

azonban

egy

jobban szimuláltam.

valós

megfelelő A

közlendő

állapotokat egy közismert játék, a Pacman ágensei

szolgáltatták:

ezek

a

játszma

előrehaladtával más és más valószínűséggel

5-1. ábra

vették fel az értékeket: mivel például az ágens a

A felhasznált Pacman játék grafikus felülete

megehető

pontok

felé

megy,

gyakrabban

kommunikálja a „erre sok megehető pont van még” állapotot, mint az ellentétét, főleg a játszmák elején. A régen elterjedt játéknak nagyban megfelelő szabályokkal működik az általam használt JAVA-implementáció is, fő és fontos különbség azonban, hogy egyszerre több Pacman is játszhat kooperációban a pályán. Kommunikálhatnak, összejátszhatnak. Az ágenseket irányíthatja emberi játékos vagy például egy szabály-alapú [3] vezérlő is. Ez utóbbit módosítottam, bővítettem egy kommunikáló modullal, mely az említett algoritmust és egyéb stratégiákat használ. A játék menete, kimenetele munkám szempontjából nem lényeges, csak a kommunikációs modult mértem. Az ágensek viselkedése az első eredményekig nem is függ a kommunikációtól: a vezérlő nem ad szemantikát a megtanult szintaxis fölé / a szabályalapú vezérlő nem függ a fogadott információktól. Gondolkoztam a jelzések kihasználásáról („erre sok megehető pont van még”), többfordulós információkérésről, információcseréről (párbeszéd-kezdemények: „megegyem most a közeli power dot-ot?” „várj kicsit, szellem közelébe megyek”), de mivel a dolgozat elsődleges célja a tanulási stratégiák tesztelése volt, a vezérlésbe egyelőre nem avatkoztam bele. Fontos, hogy az ágensek nincsenek egymással versenyhelyzetben, a megszerzett pontszámot is közösen gyarapítják. Mind az implementáció különböző szakaszai, mind a mérések „etikus Pacman-t” terveztek, aki az igazi környezetét és céljait kommunikálja, nem vezeti félre a társait. Így minden üzenetből tanulni lehet, nem kell az ismert részigazságok alapján

9

ellenőrzéseket végezni. Az idilli képet bizonyos mérésekben a beiktatott zaj rontja el, ilyen esetekben erre külön kitérünk. A felhasznált implementáció használható a grafikus megjelenítés nélkül, így megfelelően gyors sok játszma lefuttatásához.

5.1.1

Szabályalapú vezérlés

A játék ágensének, a Pacman figuráknak a mozgását egy szabályalapú vezérlő végzi, melynek létrejöttét a szerzők [16]-ben mutatják be. Kézzel létrehoztak a játékteret jellemző magas szintű jellemzőket illetve magas szintű célokat, majd ezekből szintén kézzel összeírtak 42 „if [feltételek] then [célok]” formájú szabályt. A célok ki-be kapcsolhatóak, a célok közül a bekapcsolt legnagyobb prioritású határozza meg az ágens mozgását. A 42 szabályból aztán a cross entropy optimization algoritmus összeválogatta és prioritással ellátta az optimális szabálygyűjteményt, mindössze 6 darabot a 42-ből: [1] if NearestGhost<3

then FromGhost+

[1] if MaxJunctionSafety>3

then FromGhost-

[2] if NearestEdGhost>99

then ToPowerDot+

[2] if NearestEdGhost<99

then ToEdGhost+

[2] if GhostDensity<1.5 and NearestPowerDot<5

then FromPowerDot+

[3] if Constant>0

then ToCenterofDots+

Az így kapott vezérlés nagyon magas átlagos pontszámot szerez, magasabbat a legtöbb más gépi vezérlőnél és magasabbat a gyakorlatlan emberi játékosnál is. Dolgozatom szempontjából egyébként nem szükséges a lehető legjobb Pacman-irányítót használni, csak arra van szükség, hogy a játék állapotterét minél teljesebben bejárja, a feltételeket jó, ha teljesülve és kielégítetlenül is megtapasztalja az ágens. Erre azért van szükség, mert ezeknek a fenti feltételeknek az értékét üzenik a játékosok, és ha egy feltétel mindig teljesül, nem lehetne megtanulni, hogy az üzenet azon része mitől függ, milyen esetekben „igaz” értékű. Az optimális politika keresését a [16]-ban mutatják be.

5.2

Nyelvi emergencia algoritmus

A tanuló eljárások általában egy már meglévő, ismeretlen struktúrát igyekeznek felfedezni, kitapasztalni. Nyelvet is tanulhatunk ilyen módon: az alárendelt fél megtanulja a tanár birtokában lévő tudást. A tanulás egyirányú, az elsajátítandó tudás létezik a tanító ágensnél, azt csak át kell venni tőle és már tudnak is kommunikálni. Ez a megoldás önmagában nem

10

rugalmas, újítást csak a tanártól fogad el, megegyezést igényel két különböző módon kommunikáló „tanár” találkozásakor a tanár-tanuló szerepekről. A másik lehetőség a nyelv közös kialakítása. Ekkor nem válik külön a tanár-tanuló szerep, minden, a kommunikációban részt vevő ágens tanító a közléskor és tanuló másik ügynökre figyeléskor. Gyenes Viktorék munkája egy ilyen egyenrangú felekből álló csoport összehangolódásával foglalkozik, egy módszert kínál a közös nyelv létrehozására, feltéve, hogy a környezet egy része közösen észlelt.

5-2. ábra A CE alapú nyelvi emergencia algoritmus leképezései

A kommunikáló modul felfogható egy háromrétegű neuronhálónak. Az

első

(input)

réteg

jellemzőiből

a

fontosakat

kiválogatva,

azokat

egy-egy

küszöbparaméterrel összevetve („kisebb 0.5-nél?”) vagy más függvénynek paraméterként adva kapjuk a bináris belső reprezentációt (‟h). Jellemzően ez tartalmazza a környezet az ágens viselkedését meghatározó paramétereit, aktuális értékeit. Ezt a transzformációt G-vel jelöltük. A második leképezés az üzenet generálása és értelmezése: milyen ‟u‟ üzenetet küldök egy ‟h‟ belső állapot esetén? Milyen h belső állapotot jelent az érkezett ‟u‟ üzenet? A publikáció újdonsága a rekonstrukciós elv alkalmazása, mely a feladó nem egyszerűen leképezi a belső állapotot a Q transzformációval ‟u‟ üzenetté, hanem egy optimalizációs eljárással olyan üzenetvektort keres és választ ki, melyet ő maga a ‟W‟ dekódoló mátrixszal a lehető legkisebb hibával a helyes belső állapottá dekódolna:

11

Ugyanezt az elvet használja egy érkezett üzenet értelmezéséhez: megkeresi azt az állapotvektort, mely a fogadó a lehető legkisebb hibával képezne a fogadott üzenetté:

5.2.1

Az optimalizációs algoritmus

A fent említett optimalizáció bináris vektorokon van értelmezve, így az általános optimalizációs algoritmusok helyett alkalmazható egy speciálisabb, kombinatorikus algoritmus is, a szerzők a cross-entropy (CE) [18] algoritmust használták. A dolgozat későbbi részében bemutatom az Orthogonal Matching Pursuit [9] és a Subspace [10] algoritmusokat, melyeket a 418.5 részben összehasonlítottam többféle szempontból a CE-vel. A CE eredeti verziója [18] egy többdimenziós Bernoulli eloszlást tart fent, mely alapján véletlenszerűen generál vektorokat. Ezek közül kiválasztja a legkisebb hibájú 5%-ot és ezekkel módosítja az eloszlást. Ahhoz, hogy tanulás közben is könnyen elérhető legyen az aktuálisan legvalószínűbbnek tartott leképezés – hogy online algoritmus legyen – nem szabad elvárni, hogy minden iterációban sok mintát generáljon az algoritmus, ez ugyanis sebességcsökkenést eredményez. Az online változat akkor használ fel egy vektort a Gauss eloszlás módosítására, ha annak rekonstrukciós hibája az eloszlás 95%-os percentilisénél1 magasabb, ez pedig eldönthető sok próba-üzenet generálása nélkül is. Így használja ezt a „nyelvi emergencia” [1], [2] implementációja is. Minden iterációban a valószínség-eloszlás alapján sorsol az algoritmus egy vektort (küldő esetén üzenetvektort), melynek segítségével frissíti a generált vektorok átlagát és szórását, majd az minimalizálás célfüggvényét kiszámolja (távolsági metrika az állapotvektor és a sorsolt üzenetvektor dekódolásából kapott állapotvektor között). Ez az érték a generált vektor jóságát jelzi (genetikus algoritmusok esetén fitnesz-értéknek nevezik), amely ha a legkisebbek között van, frissíti a valószínűség-eloszlást. Az algoritmus pszeudo-kódja az alábbi:

1

Egy adatsor p%-os vagy p percentilise az az eleme, amelynél az adatsor elemeinek p%-a kisebb. Nem a Gauss-eloszlás felől nézve a „95%-os percentilisnél magasabb” azt jelenti, hogy a legmagasabb 5%ba esik.

12

5-3. ábra Az online CE pszeudokódja

Ez a rekonstrukciós algoritmus nagy léptékben meggyorsítja az összehangolódás sebességét, lecsökkenti az ehhez szükséges üzenetek számát. Ahogy egy tanár egyszerre több diákot taníthat, úgy emergens tanulásnál is megkaphat egy üzenetet több ágens, így egy üzenetből akárhány ágens tanulhat. A szimulációban beállítható, hogy egy címzettje legyen-e egy üzenetnek, vagy mindenki megkapja. Az optimalizációs algoritmusokban nem válik el egymástól a felfedezés és kiaknázás (mint a megerősítéses tanulás bizonyos eseteiben), tehát a szimuláció bármelyik részén ugyanúgy képes az ágens módosítani a szótárán és nincsen megkülönböztetve olyan szakasz, amikor szívesebben próbál ki eddig ismeretlen kombinációkat vagy választ inkább biztosat. Optimalizációkor mindig a lehető legjobbat, az aktuálisan legjobbnak gondoltat választjuk.

13

6. fejezet Módszer, a munka részletes ismertetése 6.1

A Pacman és a nyelvi emergencia összeillesztése

A Java nyelven implementált Pacman játékot és a közös nyelv emergens kialakítását végző algoritmust úgy illesztettem össze, hogy minden ágensek minden döntéshozáskor kommunikálhatnak. Nem kell mindig üzenniük, ezt eldönthetik minden alkalommal. A szimuláció elején beállítható, hogy egy kimondott üzenetet mindenki halljon vagy csak egy valaki. Ha csak ketten profitálnak egy üzenetből – csak egy fogadó van – akkor a következő indexű ágens kapja meg az üzenetet. Ennek előnye, hogy triviális módon biztosítja, hogy ne alakulhasson ki egymással beszélő csoport, mely a többieket kizárja a kommunikációból. Ez esetben lényegében csak kevesebb ágenssel futtatnánk a szimulációt. Mivel a dolgozat egyik célja az algoritmus tesztelése változatos, és valós körülmények között, a zárt kommunikáció eme címzési módját idővel kicseréltem egyenletes eloszlású véletlenszerűre, ebben az esetben sem jöhetnek létre hosszú távon csak egymással kommunikáló csoportok.

6.1.1

Szoftverarchitektúra

A Pacman játék Java nyelvű programkódja magas szinten alkalmazza az objektum-orientált programtervezés lehetőségeit öröklődések, interfészek, okos szétválasztás használatával. A játék grafikus felületének rugalmasságára jellemző, hogy játék közben lehet megjelenítése formát változtatni: egyik pillanatról a másikra átváltani a hagyományos felülnézetből first person nézetbe. Eközben a játékállapot változatlan, a pillanatszerű nézetváltás után folytatódik a játék. Az architektúra kommunikációs részét hasonló eszközökkel alakítottam ki a könnyű bővíthetőség, rugalmasság érdekében. A 6-1. ábra ábra tetején lévő ObjectController és ObjectState interfészek, illetve a MacroController, RuleBasedController és AgentState megvalósítások adottak voltak, ezeket bővítettem ki és adtam a Pacman-eknek kommunikációs képességet. A PacMan mozgásának irányításával nem foglalkoztam, azt a Szita Istvánék szabály alapú vezérlője (RuleBasedController) végezte [15], ebből öröklődik a SpeakingAgentController. Erről a gépi tanulással készült szabálygyűjteményről az 5.1.1 pontban írtam. Az osztály kibővítése során felüldefiniálás nem történt, mert a pályán navigálásra a kommunikáció nincs hatással, csak új lehetőségek adtam hozzá. A SpeakingAgentController menedzseli az új

14

funkciók zömét, melyhez adatokat a SpeakingAgentState osztály, különböző algoritmusokat a LanguageLearner interfész szolgáltat. Ugyanez a helyzet a „State” oldalon is: a „beszélő Pacman-nek” teljes mértékig szüksége van az AgentState ős funkcióira, adattagjaira, de azokból nem építkezik tovább, hanem újakkal bővíti. Itt lehet hozzáférni a játéktér állapotából generált magas szintű jellemzőkhöz (pl.: „szellemsűrűség”), melyeket az ágensek megüzenik egymásnak. Itt generálódik és tárolódik a „világnézetet”

meghatározó paraméter-lista,

mely meghatározza,

mikortól

nagy a

szellemsűrűség (bináris állapotokat kommunikálnak!). Ugyanitt tárolom a többi ágens üzeneteinek sikeres megértésének arányát, amiről a 6.5 fejezetben lesz szó. A LanguageLearner interfészem fogja össze a különböző kommunikáció-összehangoló algoritmust. A SpeakingAgentController osztály ezen keresztül éri el a kiválasztott módszert, amelyik elvégzi üzenetküldéskor az állapot => üzenet, üzenetfogadáskor az üzenet => állapot leképezést, illetve minden alkalommal hangolja a súlymátrixát a többiektől jött üzenetek függvényében.

6-1. ábra A kommunikációt végző osztályok UML diagramja

Ha a különböző nyelvtanulós megoldásoknak lennének közös adattagjaik és függvényeik, az interfész helyett az ismétlés elkerülése miatt lehetne egy ősosztályt helyezni föléjük, még a

15

súlymátrix sem emelhető ki: a nyelvi emergencia algoritmus 1 mátrixot, a véletlenszerű üzenetküldő nullát, a fix súlymátrixokból választó pedig hármat használ és máshogy is kezelik.

6.2

A hiba mérése

A hiba mérésére eredetileg egy mozgó átlag szolgált, mely a jól megértett üzenetek arányán alapult. Ez a 6-2. ábran pirossal jelölt görbe nem volt alkalmas az összehangoltság mértékének megállapítására, mivel az egyenlőtlen állapotok eloszlása miatt a játék egy fázisában előforduló állapotokat jól megtanulhatta (400 és 800 között a grafikonon), ekkor ez a mozgó hiba-átlag már nulla hibához is lesüllyedhet, ám később még nagyon sok súlymódosítás szükséges, hogy minden helyzetben megértsék egymást. Ha igen lassan lecsengő mozgó átlagot számolunk, az megbízhatóbb lehet a teljes összehangoltság jelzésére, de azt pedig jóval tovább kell futtatni.

6-2. ábra Hibamérési módszerek összehasonlítása két ágens esetén

Implementáltam egy másik hibamérési módszert, amely jobban mutatja az összehangoltság mértékét: ez az összes ágens súlymátrixának egyfajta szórását számolja. Első lépésként a mátrixok átlagát veszi, majd összeadja az ettől való eltéréseket egyetlen számmá. Miután ezt normálja a mátrix méretével és az ágensek számával, megkapjuk az ábrákon kékkel jelölt hibagörbét. Feltettük, hogy teljes összehangoltság csak ugyanolyan mátrixokkal érhető el, tehát a belső reprezentáció ugyanazokból a jellemzőkből épül föl. Amíg a belső állapotvektor bitjei ugyanabban a sorrendben jelentik egy-egy magas szintű jellemző teljesültségét, ez a feltételezés nem jelent megszorítást az összehangolt mátrixokra vonatkozóan.

16

6-3. ábra Hibamérési módszerek összehasonlítása több ágens esetén, nyílt kommunikációnál

6-4. ábra Hibamérési módszerek összehasonlítása zárt kommunikáció esetén

Látható, hogy a súlyokon alapuló kék görbe jobban korrelál az előrehaladottsággal, mint a korábbi mérőszám. Két játékos esetén (6-2. ábra), vagy ha a kommunikáció nyílt (mindenki hall mindenkit, 6-3. ábra) a súly-alapú mérce monoton is, 1-1 kommunikáció esetén (6-4. ábra) már nem feltétlen. Ekkor két ágens összehangolódása jelenthet távolodást a többiektől, de mivel nincsenek elszigetelve, ezek az esetleges eltávolodások idővel megszűnnek. A két görbe ugyanott változik: amely esetben nem értik meg teljesen egymást az ágensek, a piros görbe definíció szerint növekszik. Hiba esetén viszont a súlyok is változnak, tehát ilyenkor változik a kékkel jelölt is. Ez az összefüggés jól látszik az első ábrán a 200. üzenet előtt: amikor nő a „félreértéseket” jelző görbe, akkor csökken a súlyok közötti távolságot jelző is. Azonban mert 1-1 kommunikáció esetén a súlyváltoztatás növelheti az átlagtól való távolságot – bár itt is egyszerre változik a kettő – a változás iránya lehet ellentétes is.

6.3 Leállási feltétel Mivel a szimuláció futását megállító feltétel sokat fejlődött a futtatások során, ezt a változatás-sorozatot is bemutatom.

17

A keretrendszer átvételekor a leállási feltétel az üzenetek megfejtésekor tapasztalt bithibákból álló mozgóátlagra vonatkozó felső korlát volt, tehát sikeres kommunikációnak a megértett üzenetek magas arányát tekintette. Ez nem volt megfelelő, ugyanis, mint például a 6-3. ábrán látszik – és 6.2-ben említettem - sok egymást követő megértett üzenet nem jelenti, hogy az állapottér megváltozásával is sikeresen kommunikálnának. A leállási feltételt a súlymátrixok hasonlóságához kötöttem: ha a súlymátrixok értékeinek különbsége egy határérték alá süllyedt (jellemző érték: 0,0001), a szimuláció sikeres volt és leállt. A feltételt megtoldottam egy kritériummal: a sikeres leálláshoz szükséges a hasonló mátrixon túl a stabilitás is: az utolsó 100 üzenetet teljesen, hiba nélkül kellett dekódolnia. Ez biztosította, hogy nem egy átalakulás közepén épp egybeeső mátrixokról van szó, hanem egy konvergálódott állapotról. Gondoskodni kellett a leállításról, ha a konvergencia nem következik be valamiért, ezért 100.000 üzenet után a szimuláció sikertelen eredménnyel leállt. A hibátlan 100 utolsó üzenet elvárása lehetetlenné tette szimuláció sikeres lezárását akkor, ha az üzenetre terhelésképp mesterséges zaj rakódik, ugyanis az ebből következően hibásan dekódolt jellemzők miatt nem volt 100 egymást követő, helyesen megértett üzenet. Foltozott megoldás lehetett volna a „100 hibátlan üzenet” kikötése csak azokban az esetekben, amikor nem rakódik rá zaj, de ennél szebb megoldásra cseréltem le. Minden üzenethez a zaj megjelenésekor eltároltam a zaj által módosított biteket, így az üzenetek feldolgozásakor, amikor kiderültek az üzenetből hibásan dekódolt bitek, tudni lehetett, melyik bitek hibásak a mesterséges zaj miatt és melyik bitek hibásak az összehangolatlan szótárak miatt. Az összehangolatlanság miatti hibák arányából egy mozgó átlagot képeztem és ennek egy felső korlátot írtam elő a szimuláció sikeres lezárásához. Így a mesterséges hibák nélkül követhetővé vált az üzengetés stabilitása.

6.4 6.4.1

Összehangolódási stratégiák Nyelvi emergencia algoritmus

Az első számú tesztelt algoritmus a fentebb bemutatott „nyelvi emergencia” eljárás [1], [2], melyet Gyenes Viktor implementált.

6.4.2

Fix súlymátrixokból választó

Ez a stratégia nem a szokásos értelemben vett tanuló algoritmus: a finom súlyváltoztatások nem közvetlenül az akciót (vagy kommunikációnál a nyelv jeleit) szabályozzák, hanem az előre megadott döntési rendszerek közül választanak.

18

Az 1970 óta létező „Herrnstein matching law”-ra épül az a „végtelen memóriás” döntés, mely számon tartja minden akcióra (döntésre) a kapott jutalmat a szimuláció kezdete óta. Az ismerős helyzetben pedig a mellett az akció mellett dönt, melyre a legtöbb jutalmat kapta a játék kezdete óta. ωa x ωx (wa: összes eddigi jutalom ‟a‟ akció választásakor, wx: összes eddigi jutalom ‟x‟ akció választásakor) Ha a jutalom mindenképp pozitív, ez az értékelő függvény sosem próbál ki olyan akciókat, melyek ugyan eddig kevesebb jutalmat gyűjtöttek (kevesebbszer választottuk ezt), de esetleg mégis nagyobb jutalmat biztosítanak. Ezt úgy módosítottam, hogy a legnagyobb átlagos jutalommal járó akciót válassza. Ha több mátrixnak is ugyanakkora a hasznossága, ezek közül véletlenszerűen sorsolok egyet. Ha például fixen az elsőt választanám holtverseny esetén, az első körben a nem túl sikeres első üzenetek után sok ágens az első mátrixszal kommunikálna és ez az algoritmikai egyenlőtlenség pillanatokon belül összehangolt állapotot teremtene. Az eddig ki nem próbált akcióknak pozitív bias-szal előnyt adtam, különben az eddigi nulla átlagos jutalom miatt sosem próbálná ki őket az algoritmus. ωa na Ez a nyilvánvalóan kötöttebb, kevésbé rugalmas stratégia azonban előnyöket is hordoz: jóval gyorsabban kialakulhat az összehangoltság, továbbá a játéktér és a belső reprezentáció közötti küszöbparaméter-különbségekre és más zajokra is robosztusabb lehet. A valóságban ez az egyeztetési típus megfelel annak, amikor egy idegennel találkozva felmérjük, milyen közös nyelvet beszélünk. Szóba sem jön, hogy a másik kedvéért megtanuljunk vagy együtt kialakítsunk egy új nyelvet, csak megszólalunk minden ismert nyelven, hátha az egyiken tudunk beszélgetni. Itt 1-1 kiragadott példán a legszembetűnőbb jellegzetességeit mutatom be, a precíz mérések a 7. fejezet. „Terhelési módszerek, eredmények” fejezetben találhatók.

19

6-5. ábra A Fix súlymátrixokból választó módszer hibagörbéje

A fenti (6-5. ábra) ábrán 3 Pacman összehangolódásának folyamata látható, mind a három a fent bemutatott stratégiát használta. A „nyelvi emergenciához” (NyE) képest itt sokkal nagyobb ugrások figyelhetők meg a hiba-görbében, ami következik is a fix súlymátrixokból. Az összehangolódás nagyságrendekkel gyorsabb a másik stratégiánál tapasztaltaknál (több száz üzenet – öt üzenet). Következő kísérletként két fix mátrixú és egy „nyelvi emergencia” [1], [2] lassan hangolódó ágenst mértem, most tehát különböző stratégiájú ügynökök kerestek közös nyelvet:

2.5 DecodedBitErrors Weights

Hiba (1/Összehangoltság)

2

1.5

1

0.5

0

0

100

200

300

400 500 Üzenetek száma

600

700

800

900

6-6. ábra Fix súlymátrixokból választó és NyE ágensek összehangolódása

A gyors ugrások itt is szembetűnőek, de a 300. üzenettől megfigyelhető finomabb változás is: az adaptívabb NyE igyekszik idomulni a fix szókincsekhez. Ez nem járhat sikerrel, míg a két fix szótárú PacMan különböző szótárból dolgozik. Amint ez a kettő megegyezik (500. üzenet), a harmadik is hozzájuk tanul.

20

6.4.3

Win-Stay, Loose-Random

Az előző „végtelen memóriájú” stratégia után egy memória nélkülivel foglalkoztam: a játékelmélet szakirodalma sok esetben megbízható választásnak tartja az egyszerű „Win-Stay, Loose-Random” stratégiát. Ha egy populációban különböző stratégiák léteznek, konvergens az a stratégia, mely siker esetén az aktuális döntési rendszere szerint működik tovább, sikertelen kooperativitás esetén (itt: félreértett üzenet) véletlenszerűen változtat a stratégiáján. Implementáltam ezt az egyszerű stratégiát is, annyi könnyítéssel, hogy nem teljesen véletlen vektorok alkotják a kommunikáció súlymátrixát, hanem bináris vektor, amilyet az n db fix mátrixszal dolgozó stratégia is használ. Ha feltesszük, hogy egy üzenet-elem egy játéktérjellemzőből képeződik le, a súlymátrix egy permutáció-mátrix lesz, és az oszlopok cserélgetésével lehet keresni a közös leképezést. Mivel korlátos számú sorrendben lehet az oszlopokat összerakni, végül is itt is fix lehetőségeink vannak, de a memória nélküliség más jellegű algoritmussá teszi. Kipróbáltam 3 és 5 darab Pacman esetén zárt kommunikációval:

4 DecodedBitErrors Weights

3.5


3 2.5 2 1.5 1 0.5 0

0

500

1000

1500

2000 2500 3000 Üzenetek száma

3500

4000

4500

5000

6-7. ábra Win-Stay, Loose-Random stratégia összehangolódási görbéje

1-1 ‟privát‟ kommunikációval nagyon lassan talált összhangra még a három ágens is (fenti grafikon), öt Pacman még nyílt kommunikációval sem tudott legtöbb esetben 100.000 üzenet alatt közös nyelvet kialakítani. Ez részint abból fakad, hogy ez a memória nélküli stratégia a nehezen kialakított részeredményeket is könnyen megváltoztathatja később: nincs súlya, előnye a régebben meglévő részelemeknek.

21

A konvergencia zaj nélküli esetben nem vitatható (véletlenszerű teljes bejárás), de gyakorlatilag használhatatlan a sok kombinatorikus lehetőség miatt, ezért a mérésekben ezt a módszert nem fogom tesztelni.

6.5 Random üzenetküldő és ennek kiszűrése Az eddig tesztelt ágensek mind kooperatívak voltak, igyekeztek kialakítani a közös nyelvet minél hamarabb. Elképzelhető azonban, hogy egy ágens más nyelvet beszél, és nem akar újat megtanulni, vagy halandzsázik: ezt az esetet szimulálta egy olyan egyszerű ágens, mely megszólaláskor egy véletlenszerű jelsorozatot küld. Ezt teszi minden alkalommal, és nem igyekszik se hasonlóan, se direkt eltérően beszélni, mint a többiek, igazából nem is figyel a többiek jeladásaira. A hiba mérésekor, a súlymátrixok különbségének számolásakor ennek a megtévesztő ágensnek nem vettem figyelembe a mátrixát, mert a grafikonon egy nagyon hevesen ingadozó görbét mutatna, amiből nem lehetne megállapítani, hogy a többi ágens egymáshoz hogyan közelít. Így, a halandzsázó ágens súlymátrixának kihagyásával pontos képet kapunk a kooperatív

ügynökök

közös

nyelv

kialakítási

folyamatának állapotáról és lehetőség van csak a tanulni hajlamos ágensekre vonatkoztatni a leállási feltételt. A felvetett problémára egy egyszerű védelmi eljárást implementáltam: a kooperatív ágensek képesek nyomon követni, melyik társukkal milyen hatékonysággal kommunikálnak. Egy-egy mozgó átlag jellemzőt rendel a többi ágenshez külön-külön, melyben azt tárolja, a kommunikált állapotjelzőket milyen arányban dekódolta helyesen. Ha egy ágens ezen jellemzője egy határérték alá süllyed, a tőle érkező üzenetek alapján nem módosítja feltehetően rossz irányba - a súlymátrixát. Ezzel a lehető legegyszerűbb megoldással a véletlenszerű üzeneteket küldő ágenseket már ki is

lehet

szűrni,

érdekében,

de

hogy

összehangolódás fázisában

annak az kezdeti

kizárt

kooperatív

társaktól

ne

legyen

végleg

elvágva,

a

kommunikációt

minősítő

mozgó

átlagot

a

22

kizárás után is frissíti. Ha például 4 kooperatív ágensből egyet valamiért kizár, de más ágenseken keresztül a súlymátrixaik konvergálnak, egy idő után a határérték fölé kerülhet a helyesen dekódolt állapotjelzők aránya és újra figyelni fogják egymás üzeneteit. A következő futtatásoknál 3 Nyelvi Emergencia típusú és egy Véletlenszerű ágens fut egy pályán nyílt kommunikációval, először a nem-kooperatív ágensek kiszűrése és kizárása nélkül, majd kizárással. Az ábrán látszik, hogy 40.000 üzenet után sem sikerült a három kooperatív ágensnek teljesítenie a leállási kritériumot, mert a Véletlenszerű üzenetküldő ágens jeleit is figyelembe vették és ezek

alapján

rossz

irányba

is

módosították a mátrixaikat. Itt viszont a fenti üzenetváltások töredéke is elég volt az egységes nyelv kialakulásához: felismerték, hogy a Véletlenszerűtől nem érdemes tanulni, ezután a 3 Nyelvi Emergencia példány gyorsan össze tudott hangolódni.

23

7. fejezet Terhelési módszerek, eredmények 7.1 Reprodukálás A „Language Emergence” cikkben Gyenes Viktorék tesztelték az algoritmus tanulási sebességét az ágensek számának függvényében (zaj nélkül), ekkor egy lineáris függést kaptak (lent balra). Fontos megjegyezni, hogy az ágensek 1-1-es kommunikációt, „privát” üzeneteket használtak, így mutatható ki jelentős függés. A kísérletet megismételtem hasonló eredménnyel (jobb oldali), bár a kiegyensúlyozatlanabb környezet, különböző leállási feltétel más értékeket eredményezett.

Összehangolódáshoz szükséges üzenetek

4

5

x 10

4

3

2

1

0

0

5

10

15 20 Ágensek száma

25

30

7-1. ábra Függés az ágensek számától az én implementációmban

7-2. ábra Függés az ágensek számától [1]-ben

Egy ágensre eső üzenetek száma

A grafikon 50 futtatás átlagából készült, az ágensek száma 2,3,4,5,6,7,8,10,13,16,32 volt.

1500

Megvizsgáltam

az

egy

ágensre eső üzenetek számát (lényegében a fenti grafikon 1000

normálva

az

ágensek

számával), mely a tanulás típusának beállása után (~6 500

0

5

10

15 20 Ágensek száma

25

30

35

ágens) szintén nem mutat jelentős növekedést.

7-3. ábra Egy ágensre eső üzenetek száma

24

35

7.2

Zajtűrés: különböző világlátás, zárt kommunikáció

A Pacman ágensek a használt kommunikációs stratégiától független módon szemlélik a világot: belső reprezentációjuk alapesetben megegyezik. Ugyanazt az állapotvektort közölné egy adott helyzetben mindegyik fent említett stratégia, persze a végső üzenet már függ az összehangolódó súlyoktól. Ez összehasonlíthatóságot jelent a felsőbb szintre: ha az első leképezés (játéktér – belső állapot) megegyezően zajlik le, össze tudjuk hasonlítani a második leképezés (a fentebb említett stratégiák, az összehangolódás sebessége) hatásait. Az első leképezés a játéktér jellemzőinek és küszöbparamétereknek segítségével ad bináris kimenetet. A játéktér játékosra vonatkoztatott jellemzői Pacman esetén például a legközelebbi szellem távolsága, ehető szellemek sűrűsége vagy a közelben található ehető pontok száma. Mivel sokszor lényegtelen ezek pontos értéke, tartományokra osztva kommunikáljuk őket, amihez körülbelül egyező tartományok (küszöbparaméterek) szükségesek. Ha a leképezés egyik eleme „a legközelebbi szellem távolsága < 20 távolság-egység”, ebből a mindössze bináris információból már a fogadók tudják, segítségre van-e szüksége a küldőnek. A kommunikációs stratégiák összehasonlításának fontos eleme a robosztusság mérése: most a küszöbparaméterek

eltéréséből

adódó

félreértések

hatását

vizsgálom.

Eltérő

küszöbparaméterek esetén nem alakulhat ki olyan közös nyelv, ami minden esetben ugyanazt jelentené a beszélőnek és a figyelőnek, mert bár megértheti, hogy „közel van hozzám egy szellem”, a „közel” fogalmaik mások. Nem túl nagy eltérések esetén azonban olyan nyelv kialakulását várjuk, amellyel legalább a többi esetben megértik egymást. Méréseim célja az összehangolódás sebességének vizsgálata különböző nagyságú eltérések mellett. Vizsgálom a stratégiákat önmagukban és egymáshoz viszonyítva is.

7.2.1

A leképezés eltérésének mérése

A belső állapotba leképezés mérése azért fontos, mert ennek alapján tudjuk összehasonlítani a kapott eredményeket. Ennek mérésére több egyszerű módszert próbáltam ki. Az eltérések mértékét jelzi a küszöbparaméterekhez adott Gauss-i zaj szórása, hiszen ez generálja az eltéréseket. A valószínűségi jelleg azonban megnehezíti az összehasonlítást: egy nagy szórású leképezés is eredményezhet az átlagtól nulla eltérésű paramétert vagy eredményezhet két ágensnek egyenlő extrém paramétereket, mely esetben a nagy szórás miatt nehéz tanulásra számítanánk, de az egyenlő paraméterek miatt mégsem ez történik. Az eltérést tehát érdemes a paraméterek generálása után azok valós értékének függvényében kifejezni. Első módszerem minden a belső állapotgeneráláskor használt jellemzőhöz tartozó

25

küszöbparaméterhez átlagot számolt az összes ágens e paraméteréből, majd összegzi minden ágens minden paraméterére az átlagtól való eltérés és az átlag hányadosát. Ezt normálva az ágensek és paraméterek számával egy 0 és 1 közötti mérőszámot kaptam, mely a valós paraméterértékeken alapulva jellemezte azokat.

átlag ( p ) 

 ágens (a). paraméter ( p) a

# ágensek

eltérések   (ágens (a). paraméter ( p)  átlag ( p)) p



a

eltérések # ágensek # paraméterek

Ez sem felelt meg azonban minden igénynek: nem függött össze annak az intervallumnak a méretével, amelyiken a jellemzőt igazként észleltük, csak az egyik határát.

Minden paramétert ezek után egy alsó és egy felső határral, tehát két számmal ábrázoltam, és ezeknek az intervallumoknak az átfedését vizsgáltam. „Mindkét irányból” kiszámoltam az átfedés mértékét: az intervallum hosszának azt a részét, amelyik a másik ágens intervallumába is beleesik (0,5 0,33). Összegzem ezek négyzetét minden ágens-pár minden paraméter-intervallumára, majd normálom 0 és 1 közé ( (#ágens * (#ágens-1) * #paraméter –rel osztok).

   ( FedésAránya    1

2

)

a1 a 2  a1 p

a1 a 2  a1 p

Az átfedéseket négyzetre emelés nélkül is lehetne szummázni, de így a súlyban jobban megjelennek a nehezen tanulható kis átfedések. A kis átfedések nyújtják el a tanulási szakaszt, ezért ezek hangsúlyosabbá tehetők az eltérések jellemzésénél. 7.2.2

CE alapú nyelvi emergencia

A következő mérésben 4 Pacman játszott egy pályán, 4 jellemzőt kommunikáltak. Az üzenet hossza (felhasználható jelek száma) is négy volt, tehát minden jellemzőt külön kommunikálhattak. Első esetben minden ágens a nyelvi emergencia algoritmust használta zárt kommunikációval. Bár algoritmikus lehetősége van a különböző paraméterek tanulásának, most ezt a lehetőséget kikapcsoltam, mivel ez lehetetlenné tenné a stratégiák összehasonlítását zajtűrés szempontjából. A futtatások megállási feltétele 0.001-es felső korlát volt a

26

kommunikáció súlymátrixainak (tehát nem a most említett paramétereknek) különbségeinek elemenként összegére. A 7-4. ábra ábra 480 futtatás eredménye, a piros görbe az adott tengelyfelirathoz legközelebbi pontok átlagából keletkezett. Érdekes észrevenni, hogy igen nagy különbségekig, 0.3-ig nem jelentett nehezebb feladatot, nem igényelt több üzenetet az eltérő „látásmód” ellenére összehangolódni. Ez megváltozhat más leállási feltétel esetén: még kisebb felső korlát a súlymátrixok különbségére valószínűleg már 0.4-nél kisebb paraméter-különbségeknél is többletfeladatot jelent, mivel a leállási feltételnek megfelelő összehangoltság csak több tanulással érhető el nagyobb különbségeknél.

4

11

x 10


10 9 8 7 6 5 4 3 2 1 0

0

0.1

0.2

0.3 0.4 Leképezés különbsége

0.5

0.6

0.7

7-4. ábra Összehangolódáshoz szükséges üzenetek száma a környezet különböző érzékelésének függvényében

Az adatsor átlagának utolsó pontjai (fenti grafikon utolsó előtti pontja) minden bizonnyal a kevesebb átlagolható adatpont milyen ilyen kiugróak. A 100.000 üzenetnél megjelenő pontsor mesterségesen keletkezett: ha 100.000 üzenet elküldése után sincsenek megfelelően összehangolódva, a futtatás megszakad, feltételezve, hogy nem is tud összehangolódni az adott feltételek mellett. Szembetűnő, hogy az esetek többségében vagy sikerül 20.000 üzenet alatt összehangolódni, vagy egészen 100.000-ig nem sikerül. Ez a 20.000-es határ független a leképezés különbségétől (persze több esetben tudják csak 20.000 fölött vagy 100.000-ig sem befejezni nagyobb különbségeknél). A 100.000-es adatpontok nélküli grafikon sokkal enyhébb emelkedést mutat a paraméter-különbségek függvényében.

27

4


10 9 8 7 6 5 4 3 2 1 0

7.2.3

x 10

0

0.1

0.2


0.5

0.6

0.7

Fix súlymátrix

Ugyanilyen zajjal teszteltem a fix súlymátrixokból válogató stratégia képességeit. Ugyanígy 4


ágens igyekezett közös nevezőre jutni, 4 súlymátrix közül válogathattak. 5 DecodedBitErrors Weights

4 3 2 1 0

0

10


40

50

A leállási feltételt módosítani kellett, mert bár olyankor vetett véget a szimulációnak, amikor azonos mátrixot használtak kommunikációra (pl. a 4. üzenet után a grafikonon), ez nem volt stabil állapot, elképzelhető, hogy ezután rögtön stratégiát váltott. Egy ilyen esetet szemléltet a 7-5. ábra. Bár van egy pillanat, amikor mindegyik ágens ugyanazt a szótárat választotta ki, az ekkor kézbesítetlen üzenetek megváltoztathatják a kialakult összhangot. Mivel egy üzenet feldolgozása nem közvetlenül az elküldés után történik meg, csak a címzett ágens lépésének sorra kerülésekor, könnyen előfordulhat ilyen kialakult, majd megbomló összehangolódás.

28

7-5. ábra Illusztráció az instabil összehangoltságra

Ennek elkerülésére a leállási feltételbe bekerült egy alatti változatlanságot. Ez a megnövelt üzenetszám a végeredményből levonódik, ez már nem jelenik meg a statisztikában, grafikonokon.

DecodedBitErrors Weights

3 Hiba (1/Összehangoltság)

„kiváró” tag, amelyik megköveteli az utolsó 30 üzenet

3.5

2.5 2 1.5 1 0.5

1490 futtatás eredményeként kaptam a következő

0

0

1

2


5


grafikont:

10000 Data points Average 8000

6000

4000

2000

0

0

0.1

0.2


0.5

0.6

7-6. ábra Szükséges üzenetek száma a világlátás különbségének függvényében

29

0.7

6

7

Az átlag egészek szűk tartományban mozog, aminek az oka ezen stratégia robosztusságát is magyarázza: ha zajos is a bemenet, a választási lehetőségek közül a legjobb választás könnyen eldönthető. A zaj mértéke jellemzően jóval kisebb a súlymátrixok különbségénél, így a leghasznosabb stratégia hasznosságát nem rontja erősen a zaj.


Lent a fenti ábra x tengelyhez közeli részét mutatom kinagyítva:

1000

Data points Average

800

600

400

200

0

0

0.1

0.2


0.5

0.6

0.7

7-7. ábra Szükséges üzenetek száma a világlátás különbségének függvényében

Összehasonlítás


7.2.4

5

10

Nyelvi Emergencia Fix mátrixok 4

10

3

10

2

10

0

0.1

0.2


0.5

0.6

0.7

Ebben a mérési sorozatban a fix mátrixokból válogató algoritmus két nagyságrenddel jobban teljesített (a fenti ábra y tengelye logaritmikus, könnyen leolvasható ez a különbség). Gyenes Viktor, Lőrincz András algoritmusa sokkal nagyobb feladattal birkózik meg, hiszen kezdetben semmilyen támpontja nincs a lehetséges kommunikációs mátrixokról. További hátrányt jelent

30

ebben a mérésben, hogy a belső állapot különbözősége egy pont után sok esetben megakadályozza a közös nyelv kialakulását, míg a fix mátrixokból válogatásnál – amennyiben a zajjal terhelt jel jobban hasonlít az eredetire, mint egy másikból generált jelre – ez szinte meg sem jelenik az összehangolódás sebességében.

7.3

Zajtűrés: különböző világlátás, nyílt kommunikáció

Az előző méréssor megismétlésénél nyílt kommunikációt használok, ami nagyságrendekkel meggyorsíthatja az összehangolódást mindkét módszer esetén. Először a nyelvi emergencia algoritmust futtattam: körülbelül kétszeresére gyorsította a nyílt


kommunikáció a nyelv kialakításának sebességét. 4

6

x 10

Data points Average

5 4 3 2 1 0 0

0.1

0.2

0.3 0.4 0.5 Leképezés különbsége

0.6

0.7

0.8

7-8. ábra Nyelvi emergencia üzenetszám-igénye eltérő küszöbértékek esetén


Kinagyítva még jobban látszik, hogy az átlag nem függ erősen a zajtól:

10000 Data points Average

8000 6000 4000 2000 0

0

0.1

0.2

0.3 0.4 0.5 Leképezés különbsége

0.6

0.7

7-9. ábra Nyelvi emergencia üzenetszám-igénye eltérő küszöbértékek esetén

31

0.8

Egy átlagos tanulási görbén láthatók a relatíve hosszú egyenes szakaszok, amikor – bár az összehangolódás még messze nem teljes – nincs előrehaladás. A játékban a Pacman ilyenkor sokáig olyan állapottérben mozog, amit már helyesen tud kommunikálni és megérteni, de más környezetben még nem hangolták össze a súlyokat.


1.8


1.6 1.4 1.2 1 0.8 0.6 0.4 0.2 0

0

500

1000

1500

2000 2500 3000 Üzenetek száma

3500

4000

4500

5000

7-10. ábra Illusztráció a szakaszos összehangolódáshoz

A fix mátrixos algoritmus előnye egy nagyságrend, s a fent említettek miatt az átlag-görbe


nem függ erősen a zajtól.

1000 Data points Average

800 600 400 200 0

0

0.1

0.2


0.5

0.6

0.7

7-11. ábra Fix mátrixos módszer üzenetszám-igénye eltérő küszöbértékek esetén

Egy átlagos tanulási szimuláció hibagörbéje elég rendszertelenül mozog, s mivel a véletlennek nagy szerepe van abban, hogy melyik ágens melyik mátrixot használja egy pillanatban, az ágensek számának növelésével hamar nagyon lelassuló összehangolódásra számíthatunk.

32



4

3

2

1

0

0

50

100

150

Üzenetek száma

A pillanatnyilag legjobbnak tűnő mátrixot kiválasztó algoritmusból hiányzik valami, ami fékezné a közel üzenetenkénti mátrixváltást: ha holtverseny van a mátrixok között az eddigi átlagos jutalmat tekintve, és az elsők között szerepel az a mátrix is, amivel mostanáig kommunikáltam, akkor ne véletlenszerű módon válasszon egyet a legjobbak közül, hanem folytassa a kommunikációt az eddigivel. Ettől azt várom, hogy gyorsabban kiválasztják közösen a használt nyelv-prototípust, ehelyett sokkal gyengébben teljesítenek: ragaszkodnak a saját választásukhoz. Ha pedig két mátrix megfelelően hasonló, könnyen kialakulhat a ragaszkodós patthelyzet. Ezt erősebben különböző mátrixokkal (például több paraméterrel és így nagyobb mátrixokkal) vagy csak az esetek 95%-ban ragaszkodó ágensekkel lehetne megoldani.

7.4 Zajtűrés: zajos kommunikációs csatorna Zajt nem csak az előző részekben vizsgált módon, az ágensek környezetének érzékelésében lévő különbségekkel vezethetünk be illetve mérhetünk, hanem az elküldött üzenetre is rakódhat zaj annak megérkezte előtt. Mivel bináris jelekkel kommunikálnak, a „zaj” most átbillenést jelent, nem tetszőleges mértékű és irányú értékváltozást.

7.5 Zajtűrés: eltűnő üzenetek Egy kommunikációs algoritmus tesztelési lehetőségei között felmerül az elvesző üzenetek hatásának vizsgálata. Ha az átviteli réteg nem garantálja az üzenetek (csomagok) megérkezését, a kommunikációs és alkalmazás rétegnek a maga szintjén is kezelnie kell ezt.

33

Az alkalmazás (pl. Pacman játék) újraküldheti az üzenetet visszajelzés hiányában, vagy ha egy gyakran ismétlődő jelentésről van szó, nem is feltétlenül kell ellenőrizni a csomag megérkezését. A kommunikációs rétegnél esetünkben nincsen értelme külön teszteket futtatni az elvesző üzenetek hatásának vizsgálatára, ugyanis egy-egy elvesztett üzenet nem változtatja meg az összehangolódáshoz szükséges üzenetek számát. Ha tehát az állapotjelentések 10%-a nem érkezik meg, akkor is ugyanannyi megérkezett üzenetre van szükség, tehát ez a jellemző nem változik. Az elküldendő üzenetek száma és a futtatási idő növekszik, de a dolgozatban elsődlegesen használt összehasonlítási változó, a szükséges fogadott üzenetek száma nem.

7.6

Zajtűrés: Eltolódva érkező üzenetek

Az eddigi szimulációs mérések feltételezték a pillanatszerű üzenettovábbítást: az elküldés után már meg is fejthette a címzett. Feltételezhető azonban, hogy egy szimulációs lépésnyi időnél lassabban érkezik meg egy üzenet bármilyen valós vagy akár csak számítógépes környezetben is: a hálózatok késleltetése önmagában több tizedmásodperces csúszást jelenthet. A késleltetés is szimulálható a Pacman-be ágyazott kommunikációs ágensekkel, megadható a késleltetés mértéke szimulációs lépésekben számolva. Hogy egy környi csúszás mekkora teher, vagyis hogy egy szimulációs lépés alatt mennyire változik meg a környezet, az függ a szimulációs lépések nagyságától. Míg nagy lépések esetén akár egy környi csúszás esetén sem képesek összehangolódni, finomabb felbontás esetén a vártnak megfelelő görbét kapunk. A késve érkező üzenetekkel nem az az elsődleges baj, hogy késve szerez tudomást valamiről az ágens, legalábbis ezen dolgozatban ez a vonatkozás nem számít. Az összehangolódást két tényező nehezíti: a késve módosuló súlymátrix és az időközben megváltozó állapottér. 

Ha egy üzenet még épp nem ért célba, a címzett a késés mértékének megfelelő lemaradásban van, egy olyan szótár szerint szólal meg, amit a feladó már korábban módosított. Amikor ez a második üzenet célba ér, ez még nem tartalmaz egy a csúszás kétszeresének idejével korábban eldőlt súlymódosítást. Ez azt jelenti, hogy jócskán elavult üzenetek keringenek és ezek alapján a változások irányával ellentétesen módosulnak a súlyok. Ez az első faktor csak a tanulási folyamat közben jelentkezik gátló tényezőként, mert összehangolódás után már nem változnak a súlymátrixok egyik szimulációs lépésről a másikra.

34



Az időközben megváltozó állapottér jelenti a másik nehézséget a késve érkező üzeneteknél, ugyanis egy üzenet érkezésekor a címzett ágens az aktuális állapottérre vonatkoztatja az üzenetet. Ha például a feladott üzenet „közeli powerdotot” jelez, de az üzenet célba éréséig a feladó megszerzi (és ezzel a pályáról leveszi) azt, akkor a címzett azt hiheti, hogy az érkezett szimbólum jelentése: „nincs a közelben powerdot”. Ez a rossz irányú súlyváltoztatás érinti az összehangolódott ágenseket is,

Szükséges üzenetek száma

előfordulása gyakori. 90000 80000 70000 60000 50000 40000 30000 20000 10000 0

Átlagok Mérések

0

5

10

15

20

25

Szükséges üzenetek száma

Üzenetek késése (szimulációs lépés)

90000 80000 70000 60000 50000 40000 30000 20000 10000 0

Átlagok Mérések

0

2

4

6

Üzenetek késése (szimulációs lépés)

35

8

10

7.7

Szimuláció közben beszálló – kilépő játékosok

A kommunikációban részt vevő ágensek számát mindeddig állandónak vettük – még ha nem is figyeltünk valamelyik jelen lévőre -, pedig könnyen elképzelhető akár online játék, akár való életbeli beszélgetés, melybe egy folyamat közepén lép be új kommunikáló fél, vagy éppen eltávozik valaki. A tesztek elvégzésére alkalmas PacMan keretrendszerbe beleépítettem egy rugalmasan paraméterezhető rendszert, melynek a szimuláció indítása előtt megadható az ágensek belépésének és kilépésének időpontja (üzenetszám alapon). Lehetőség van több ágens egyidejű belépésére illetve egy kilépett ágens visszahozására is, ilyenkor a tanulás nem elölről kezdődik, hanem azt a nyelvet beszéli visszalépéskor, amit kilépéskor tudott. Az ideiglenesen kilépett ágensek nem kapnak plusz információt visszalépéskor: az időközben szétkürtölt üzeneteket utólag nem kérdezhetik le és természetesen a többiek – esetleg összehangolt – súlymátrixához sem férhet hozzá. Bonyolult, több részfeladatból álló gépi tanulási feladatoknál sikerrel alkalmazott módszer a részfeladatok egyenkénti tanítása. Gyakran használják ezt a „layered learning” módszert olyankor, amikor a bemenetekből szinte lehetetlen rögtön a teljes feladatot megtanulni, például [11]-ban a robotok fociját bontották fel részfeladatokra: először a sétát, majd a rúgást, végül a kapura rúgást tanulta meg az ágenst vezérlő logika. Pacman-es környezetben is kipróbálták már „növekményes megerősítéses tanulás” néven [17]. Esetünkben nincs mód ilyen feladat-egyszerűsítésre, de azt ki lehet próbálni, gyorsabb-e az összehangolódás, ha nem üzenget minden ágens a kezdetektől, csak egyesével, később lépnek be a már összehangolódott ágensek közé. A közös kommunikációs protokoll kialakítását gyorsíthatja, ha a szimuláció kezdetekor csak két ágens üzenget, majd a kialakult nyelvet tanulja el az újonnan belépő. Időben hosszabb lehet az egymás utáni tanulás miatt, de az üzenetek számát tekintve esetleg gyorsulhat. Nyílt üzenetküldéskor a protokoll kialakulásának sebességét, egy üzenet súlyváltoztatási hatékonyságát rontja, ha csak kevesebb ágens hallja, tehát minden később belépő ágens elvesztegetett jópár üzenetet, ami negatívan hat. Ez a hátrány nem mutatkozik meg zárt kommunikációnál, mert egy üzenetet mindenképp egyvalaki kap meg, nem profitál belőle kevesebb ágens. Az újonnan csatlakozók a kezdeti „artikulálatlan” üzeneteikkel kis mértékben rontják a régiek harmóniáját, mivel tőle is tanulnak. Ez kiküszöbölhető lenne hierarchia felállításával ezekben az esetekben: kinevezhető lenne a régi ágens tanárnak, az új pedig tanulónak. Ez a különbségtétel azonban kivezet a dolgozat témájából, ami éppen az egyenrangú felek kommunikációjával foglalkozik.

36

A következő mérésben öt ágens vett részt, mindegyik a nyelvi emergencia algoritmust használta az összehangolódáshoz. Zárt kommunikációt

Szükséges üzenet száma(átlag)

alkalmaztam, csak egy valaki hallotta az üzenetet. Első esetben mind az ötük jelen volt, második esetben 1000 üzenetenként lépett be egy-egy új ágens. 40 futtatás eredménye alapján nem gyorsabb a tanulási folyamat, ha

Egyszerre megjelenő

15864

Egyesével megjelenő

18156

egyesével belépnek be az ágensek.

7-12. ábra Szimuláció közben belépő ágensek, zárt kommunikáció

A második ábrán a zöld vonal jelzi, mikor léptek be ágensek: az 1000. üzenetnél például látszik egy nagyobb ugrás az súlymátrixok közötti különbségben, ugyanis ekkor lépett be egy más nyelvet beszélő ágens.

7-13. ábra Szimuláció közben belépő ágensek, nyílt kommunikáció

37

Mást volt a helyzet nyílt kommunikációnál, amikor az új ágens szabálytalan üzenetei a már összehangolódott ágenseket ugyanolyan mértékben változtatja meg, így köztük nem romlik az összehangolódás. Ez esetben valamivel gyorsabban alakult ki a nyelv egymás után belépő ágenseknél. Szükséges üzenet száma(átlag) Egyszerre megjelenő

4647

Egyesével megjelenő

3606

38

8. fejezet Összehasonlítás komplex algoritmusokkal Az 5. fejezetben vizsgált algoritmusok mind sokkal egyszerűbbek voltak a CE-n alapuló nyelvi emergencia algoritmusnál, sokszor sokkal könnyebb feladatot kellett csak megoldaniuk például a beépített mátrixok segítségével, súly-hangolásról nem volt szó egyik esetben sem. Az összehasonlítás tehát nem egyenlő feladatokat megoldó módszereket vizsgált. Itt bemutatok három optimalizációs algoritmust, amelyeket a CE helyett alkalmazok és összehasonlítom a sebességüket, zajtűrésüket. Ezek ugyanazt a nehézségű feladatot látják el, egyaránt súly-hangolással érik el az összehangolódást akár más fajta algoritmussal kooperálva is.

8.1 Rekonstrukciós elv nélküli tanuló Egy egyszerű tanuló, mely egy üzenet megfejtésekor egyszerűen a súlymátrix és az üzenet szorzatát adja kimenetként. Nem alkalmazza a rekonstrukciós elvet, mely olyan kimenetet adna, amiből a transzformáció a lehető legjobban működik visszafelé. A rekonstrukciós elv hiányában nagyobb eséllyel alakul ki nem-kombinatorikus nyelv, ahol két bináris érték 4 különböző kombinációját 4 külön jellel fejezik ki. Súlyfrissítésnél (tanulási rész, update) ugyanazt a gradiens alapú súlymódosítást használja, mint a fent bemutatott CE-s megoldás.

8.2 Orthogonal Matching Pursuit Az 1992-es Matching Pursuit algoritmus kibővítését, az Orthogonal Matching Pursuit-et [9] is alkalmaztam a Cross-Entropy versenytársaként a kommunikációs mátrix felépítésében. Ez egy önző (‟greedy‟) iteratív optimalizációs algoritmus, működését a [20] grafikusan is bemutatja. Ez a módosított algoritmus lineárisan független vektorokból rakja össze az üzenet-vektort: abban az esetben is csak az egyik mátrix-oszlopot használja, ha több megegyezik. Némelyik más algoritmus (például az eredeti Matching Pursuit, vagy az egyszerű feed-forward megoldás, lásd 6.3) ilyenkor mindkét oszlopot felhasználhatja, amivel ugyan nem ad helytelen eredményt, de a tanulást lassítja, mert nem részesíti előnyben, nem választja ki egyiket sem a kettő közül.

39

Az algoritmus minden iterációban kiválaszt egy vektort a „szótárból”, esetünkben az állapotüzenet leképezést végző mátrix oszlopaiból, mégpedig azt, amelyik a legnagyobb mértékben csökkenti a hibát. A kiválasztott elemmel csökkenti a hibát, majd következik az új iteráció. Minden vektort legfeljebb egyszer választ ki, mivel lineáris független vektorokból építkezik. A leállási feltétel lehet az összes vektor kiválasztása és súlyozása vagy egy megfelelően alacsony hibaküszöb elérése. Az OMP algoritmus valós számokkal is képes dolgozni, míg a Cross-Entropy csak bináris bemenettel és kimenettel működik. Az

implementációban

külön

8-1. ábra OMP-s tanulás görbéje 3 ágens, 4 kommunikált játékállapot esetén.

figyelmet

kellett fordítani az azonos oszlopok kezelésére. Idő-komplexitása O(KmN), ez a lineáris programozás komplexitásánál gyorsabb, az OMP rekonstrukciója nem bizonyítható úgy, mint az LP-é. A 8.1 ábrán 3 ágens összehangolódási görbéje látható. A jól látszó vízszintes platók idején akár több száz üzeneten keresztül nem közeledik egymáshoz az ágensek kommunikációs mátrixa. Ez nem az algoritmus gyengesége, hanem annak a következménye, hogy bizonyos játékállapot nem következik be hosszú ideig.

8.3 Subspace A [10]-ben 2009-ben bemutatott „Subspace pursuit” algoritmus egy továbbfejlesztése az 1993-as Orthogonal Matching Pursuit algoritmusnak [9]. A bővítés abban áll, hogy míg az OMP minden iterációban egyetlen komponenst választ ki (amelyikkel a legjobban csökkenthető a hiba), addig a Subspace algoritmus a meghatározott ‟k‟ legjobbat választja be egyszerre. Ezzel a módosítással egyszerre van jelen a Matching Pursuit algoritmusok gyorsasága (bizonyos esetekben O(m N log K) ) és az OMP-vel ellentétben a rekonstrukció hibája bizonyíthatóan alacsony. A Subspace algoritmus is valós számokkal dolgozik, esetünkben pedig elegendő a bináris állapottér

kezelése,

így

az

algoritmust

jócskán

egyszerűsített

implementációval

használhattam. Esetemben egy komponens vagy benne foglaltatik a kiválasztott vektorok gyűjteményében, vagy nem, mértéke nincs. Így elegendő sorba rendezni a hiba nagysága

40

szerint a „feedfoward” módon kiszámolt vektorokat és kiválasztani a ‟k‟ legkisebbhez tartozó komponenst.

8.4

Feed-forward

A legegyszerűbb üzenetgenerálás kétségkívül az állapotvektor és a súlymátrix mátrixszorzása. Ezt írja felül az OMP és a CE kifinomultabb módszerekkel, a megértést elősegítő kimenettel. Érdemes azonban összevetni a komplexebb algoritmusokat a legegyszerűbb megoldással. Két változatban futtattam ezeket: 

Mátrixszorzat kerekítése bináris vektorrá: „FeedForward”



Mátrixszorzat eredményéből a ‟k‟ legnagyobb kiválasztása, ezek az üzenetben 1-es bitként, a többi 0-ásként jelenik meg. Ez a „bináris” Subspace megoldás a grafikonokon „FeedForward2” néven szerepel.

8.5 Összehasonlítás 8.5.1

Zavaró körülmények nélkül

A fent ismertetett módszereket a 7. fejezetben bemutatott terhelések alatt hasonlítottam össze. Először zajmentes környezetben mértem meg az összehangolódáshoz szükséges üzenetek számát. Minden alkalommal 4 ágens kereste a közös jel-jelentés párokat nyílt kommunikációval, 4 állapotjelzőt üzentek 4 bites üzenetekben. Zaj nélkül nem mutatkozik nagyságrendbeli eltérés az szükséges üzenetek számában, bár az OMP majdnem kétszer olyan lassan tanul mint a másik három.

8-2. ábra Zajtalan környezet, 4 ágens, 4 kommunikált jel

41

8.5.2

Csatorna zaj

Mielőtt az üzenetek sérülésének hatását vizsgáltam, új leállási feltételt kellett alkalmazni (6.3 fejezet). Az algoritmusok összehasonlításakor az OMP bizonyult jelentősebb lassabbnak a másik három módszernél, 2 százalék zajnál háromszor annyi üzenetre volt szüksége az OMP algoritmusnak. Futtatási környezet: 3 ágens, nyílt kommunikáció, 3 kommunikált ágens, 3 bit hosszú üzenetek. Az alábbi ábra csak a sikeres futtatások eredményéből számolt átlag-görbét.

8-3. ábra Csatorna zaj tűrése, 3 ágens, 3 kommunikált jel.

Az OMP alapú összehangolódás hátránya még erősebb megjelenik a sikertelen játszmák arányát mutató grafikonon: kisebb zajnál kezd hibázni és jóval gyakrabban is teszt.

8-4. ábra Sikertelen játszmák aránya az üzenetek sérülésének függvényében

42

8.5.3

Ágensek száma zárt kommunikációban

Végeztem egy tesztet, melyben az ágensek számának növelésével és zárt kommunikációval (egy üzenet - egy címzett) terheltem az algoritmusokat. Nagyságrendi eltérés nélküli eredményeket kaptam, az OMP alapú tanuló igényelte a legkevesebb mintát, a CE alapú a legtöbbet. Az ágensek számától való függés lineáris. Még a legtöbb ágens esetén (50) sem fordult elő egy alkalommal sem, hogy ne lett volna sikeres az összehangolódás. Futtatási környezet: 3 ágens, nyílt kommunikáció, 3 kommunikált ágens, 3 bit hosszú üzenetek.

8-5. ábra Üzenetek száma az ágensek számának függvényében

43

8.5.4

Késve érkező üzenetek

A 7.6 fejezetben ismertetett terhelést, a késve érkező üzenetekkel összehangolódást érdekes módon az OMP algoritmusa nem igazán tudta követni, igen kevés csúszás elegendő volt a sikeres kommunikáció megakadályozásához. Az első ábrán az összehangolódáshoz szükséges átlagos üzenetszám látható a késés függvényében, a második ábrán a sikertelen összehangolódások aránya. Megfigyelhető a csúszás mértékével alig emelkedő szükséges üzenetszám illetve alig emelkedő sikertelenségi arány (2 és 12 nagyságú csúszások között). Ennek oka, hogy az állapottér könnyen megváltozik már két szimulációs lépés alatt, ennél nem sokkal többet változik tizenkét lépés alatt. A Cross-Entropy alapú módszer bizonyult a leghatékonyabbnak a fent vázolt környezetben.

8-6. ábra Összehangolódáshoz szükséges üzenet száma a késés mértékének függvényében

8-7. ábra Összehangolódáshoz szükséges üzenet száma a késés mértékének függvényében

44

9. fejezet Összefoglaló Lőrincz András csoportjától kaptam a módosítható forráskódú Pacman implementációt, melyet mint környezetet használtam fel kommunikációs stratégiák tesztelésére, mérésére. A fent említett szerzők által publikált és implementált nyelvi emergencia algoritmus „valós” körülmények közti kipróbálása volt a célkitűzés: olyan környezetben mértem a közös nyelv kialakulásának sebességét, ahol nem volt egyenletes eloszlású, optimális tanulási görbét biztosító állapottér, így játék-beli / valós élet-beli helyzetekhez jobban hasonlító körülmények között figyelhettem meg. Ezt a kapott játék és algoritmus kombinálásával, a korábbi eredményeket reprodukáló mérésekkel és új, robosztusságot vizsgáló zajos inputtal végzett mérésekkel tettem meg. Sikeresen beillesztettem a szótár-építő algoritmust a Pacman játékba és reprodukáltam az ágensek számától való függés eredményét az algoritmus eredeti publikációjából. A feladatnak megfelelően futtatásokat végeztem a játék állapotterében, így valós körülmények között mérhettem a zajtűrést, sebességet. A feladatkiírást meghaladva kibővítettem a rendszert más kommunikáló – tanuló stratégiákkal, melyeket a játékelméleti irodalomból vettem át. Ezek közül választottam, implementáltam és mértem a Win-Stay, Loose-Randomize egyszerű módszert, mely azonban az 1-1 „zárt” kommunikáció kör alakú fix elrendezése miatt képtelen volt erős helyi csoportok kialakítására és elterjesztésére. A kör-formában lényegében egy olyan véletlenszerű bejárássá módosult a közös nyelv keresése, mely még viszonylag kevés számú ágenssel és jellemzővel sem konvergált ésszerű üzenetszám alatt. Egy másik játékelméletből átemelt algoritmus viszont jóval gyorsabb összehangolódásra volt képes: ebben az esetben néhány darab (tesztjeimben 4) fix kommunikációs mátrix közül választotta ki az ágens azt, amelyik használatával átlagosan a legtöbb jutalmat szerezte. Ez a módszer a beépített könnyítést ki is használja, két nagyságrenddel gyorsabb konvergenciát mértem zaj nélkül. Érdekes eredmény ennek a módszernek a nagyon erős zajtűrése: mivel a zajos adat nem módosítja rossz irányba (sem) a súlyokat, a választott mátrixszal dekódolt zajjal terhelt jel pedig általában jobban hasonlít az elvárt eredményre, mint egy másik mátrixszal dekódolt jel, a szükséges üzenetek száma lényegében nem függ a hozzáadott zajtól. Ezek után a stratégiák után beillesztettem még a keretrendszerbe három másik, a CE-vel azonos nehézségű feladatot elvégző algoritmust: az eredetileg nem csak bináris környezetben működő OMP-t és az egyszerű feed-forward számolás két változatát implementáltam.

45

A mérési lehetőségeket is a feladatakiírásnál tovább bővítettem: implementáltam a szimulációs környezetet olyan bekapcsolható terhelésekkel, melyekre számítani lehet egy valós környezetben vagy más játékbeli felhasználás esetén. Így került bele a késve érkező üzenetek modellezése, mely biztosan előfordul távoli ágenssel kommunikálás esetén. Mérhetővé vált az összehangolódáshoz szükséges üzenetek száma véletlenszerű üzeneteket küldő ágensek társaságában is, illetve implementáltam egy szűrőt, mely képes kiszűrni ezeket a nem kooperatív ágenseket. Teljes szabadsággal modellezhető már az üzenetküldő felek kibeszállása a csoportba, így szimulálható a lassan bővülő csoport vagy más létszámfüggő kísérlet. Az optimalizációs algoritmusok tesztelése közben nem tapasztaltam nagy eltéréseket, a különböző terhelések alatt az OMP bizonyult a legkevésbé zajtűrőnek, majd a feed-forward megoldások előtt egy kevéssel a CE alapú tanuló tűnt legrobosztusabbnak.

46

10. fejezet Köszönetnyilvánítás Munkám el sem kezdődhetett volna és nem is haladt volna Gyenes Viktor nélkül: a „nyelvi emergencia” cikk egyik szerzője készítette részben a Pacman játék általam használt implementációját is. Ezeken túl sokszor segített tanácsaival, sokszor rendelkezésre állt. A Pacman játékért köszönet illeti Matuz Gábort és Umenhoffer Tamást is, a Subspacealgoritmus tömör ismertetéséért Palotai Zsoltot. Konzulensemnek, az egész kutatócsoportot összefogó Lőrincz Andrásnak mindenkire kiterjedő figyelme segített gyorsan megtalálni és megismerni a feladatot és mindig készen állt a konzultációra. Köszönöm a segítséget belső konzulensemnek, Feldhoffer Gergelynek és a két korábbi félév vezetését Karacs Kristófnak. Köszönöm Varsányi Zitának és Szalai Zoltánnak, hogy elfogadták elfoglaltságomat (még ha elfogultak is).

47

11. fejezet Irodalomjegyzék [1] Gyenes, V. and Lőrincz, A., “Language development among co-learning agents” Sixth IEEE Int. Conf. on Development and Learning,London,pp. 294-299, July 2007. [2] Gyenes, V. and Lőrincz, A., “Co-learning and the Development of Communication” Artificial Neural Networks - ICANN 2007, 17th International Conference, Porto, pp. 827-837, September 2007. [3] Szita, I. and Lőrincz, A., “Learning to Play Using Low-Complexity Rule-Based Policies: Illustrations through Ms. Pac-Man" Journal of Artificial Intelligence Research, Volume 30, pages 659-684, 2007 [4] Lőrincz, A. and Gyenes, V. and Kiszlinger M. and Szita I., “Mind model seems necessary for the emergence of communication”, Neural Information Processing -- Letters and Reviews {http://nipg.inf.elte.hu/}, 2007. [5] Szita, I. and Lőrincz A., “Online variants of the cross-entropy method” , Technical Report {http://nipg.inf.elte.hu/}, 2007. [6] Huttegger, S. M. and Zollman, K. J. S., “Signaling games: dynamics of evolution and learning”, Language, Games, and Evolution, Forthcoming. [7] Zollman, K. J. S., “Talking to Neighbors: The Evolution of Regional Meaning”, Philosophy of Science, 72, pp. 69–85., January 2005 [8] Mathworks, MATLAB, http://www.mathworks.com [9] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad. “Orthogonal Matching Pursuit: Recursive function approximation with applications to wavelet decomposition”. In Proc. of the 27th Annual Asilomar Conference on Signals, Systems and Computers, Nov. 1993. [10] Wei Dai Olgica Milenkovic, “Subspace pursuit for compressive sensing signal reconstruction” IEEE Transactions on Information Theory Volume 55, Issue 5, 2230-2249, May 2009 [11] P. Stone. “Layered Learning in Multi-Agent Systems”. PhD thesis, Carnegie Mellon University, 1998. [12] Stevens, J.R., Cushman, F.A. & Hauser, M.D. “Evolving the psychological mechanisms for cooperation”. Ann. Rev. Ecol. Syst. 36: 499–518., 2005

48

[13] Christiansen, M. H., Chater, N., & Reali, F., “The biological and cultural foundations of language”, Communicative and Integrative Biology, vol 2, Issue 3 June 2009. [14] Steels, L., “Synthesising the Origins of Language and Meaning Using Co-evolution, Self-organisation and Level formation”. In Hurford, J. and Knight, C. and Studdert-Kennedy, M., editors, Approaches to the Evolution of Language: Social and Cognitive Bases, pages 384-404. Edinburgh University Press, 1998. [16] I. Szita and A. Lőrincz, “Learning to play using low-complexity rulebased policies: Illustrations through Ms. Pac-Man,” J. Artif. Intell. Res. (JAIR), vol. 30, pp. 659–684, 2007. [17] Bonet, J. S. D., & Stauffer, C. P. (1999). “Learning to play Pac-Man using incremental reinforcement learning”. [Online; accessed 06 May 2010]. [18] Rubinstein, R. and Kroese, D. “The Cross-Entropy Method”. Springer-Verlag, New York, 2004. [19] A. Lőrincz, V. Gyenes, M. Kiszlinger, and I. Szita. “Mind model seems necessary for the emergence of communication”. Neural Inf. Proc. Lett. Rev., pp. 11:109-121, 2007. [20] T. Blumensath and M. Davies, “On the difference between orthogonal matching pursuit and

orthogonal

least

squares.”

unpublished

manuscript,

http://www.personal.soton.ac.uk/tb1m08/papers/BDOMPvsOLS07.pdf, 2007.

49

available

at:

Jel-jelentéspárok egyeztetése többágenses környezetben. Görög Márton

Recommend Documents