TimeToLive 2010.12.22 18:03:44

@Haibane:
Szerintem ennél azért egy kicsivel bonyolultabb a helyzet.Ugyanis meglepő módon az önző viselkedés magában foglalhatja a kooperációt is.

Hogy részletesebb legyek, vizsgáljuk meg a játékelméleti modelleket közelebbről. A játékelméletben minden játékos racionális döntéseket hoz, azaz mindig arra törekszik, hogy az adott helyzetben a lehető legjobb lépést tegye meg. Ezt hívják best response (BR) stratégiának. Ez a BR stratégia egyébként az önző viselkedés modellje (maga az önzés mint kifejezés csak sokkal később, az autonóm ágenseknél kerül először elő).

Most vegyük szemügyre az általános klasszikus játékelméleti modellt. Itt minden játékos csak a jelen állapot szerint hoz döntést, azaz senki sem rendelkezik memóriával. Ilyenkor a BR döntés az aktuális állapothoz képest BR.
Most, ha sokáig játszanak, akkor jobb esetben a játék konvergál egy egyensúlyi állapothoz, ezt hívják Nash egyensúlyi pontnak (NEP).
Viszont a NEP lehet hogy a szükséges rossz megoldás mindenki számára, és más stratégia profilok sokkal jobb összeredményt hozhatna (Pareto-hatékony). Azaz mindenki az adott körülményekhez képest a BR-t választja, viszont ezáltal mindenki rosszul jár. Tipikus példa erre a cikkben is megemlített fogolydilemma.

Vagyis a klasszikus modellben teljesen igazad van, hogy az önzés megöli a közös sikert.
De amint látjuk, a klasszikus modell nagyon messze áll a valós modellektől, így manapság már érdemben nem is nagyon foglalkoznak vele. Ellenben különféle kiterjesztett modelleket dolgoztak ki az utóbbi 30 évben.

Az egyik ilyen modell a memóriával rendelkező játék. Ebben minden játékos megjegyzi, hogy a többiek milyen döntéseket hoztak az elmúlt "k" körben. Ennek segítségével képesek az ellenfelek stratégia policy-jét "megtanulni" (ilyen tanulási módszer pl. a bounded reasoning - "én úgy gondolom hogy te úgy gondolod hogy én úgy gondolom stb", a fictitious play, vagy a Bayes tanulás). Miután a játékos megtanulta az ellenfelei policy-eit, képes lesz olyan BR döntést hozni, ami nem csak rövid távon, hanem hosszú távon is eredményes. Na most, ha minden játékos ily módon tanul és figyeli a többit, a tanulási folyamat során óhatatlanul egyfajta metakommunikációt folytatnak egymással ( a döntéseiken keresztül kommunikálnak egymással) .
Ilyenkor az az érdekes dolog történik, hogy hiába mindenki a saját BR stratégiáját követi, ebben a BR-ban már implicite kódolva van az együttmüködés.
Tehát külsőre mindenki önző, mert BR-t választ, de közben belül már bizonyos szintű kooperáció zajlik.Ez azért egy kicsit más mint az 1. kijelentésed, mert ott te explicit szabály segítségével kényszeríted a játékosokat kooperációra, míg az általam leírt modellben maga a játékos még mindig azt hiszi, hogy önző.

Amúgy ez az önzésbe kódolt együttmüködés még nagyon új, és tiszta elméleti eredmények még nem születtek, csak hipotésizek és számos sikeres alkalmazás (főként szenzorosak).

Végül még vmi: a 2. kijelentéseddel a matematika és a számításelmélet egy (sztem viszonylag fontos, de sajnos alulértékelt) területe, a stabilitáselmélet foglalkozik. Itt a kérdés az, hogy ha adott 1 függvény (játék), melynek az optimális pontját (pl. NEP) kell megkeresni, akkor ha a függvény paramétereit kis mértékben módosítjuk, akkor mennyire változik az optimális pont.
Erre már született számos szép eredmény, szal érdemes utánanézni.

Amúgy a változtatás amit említettél a cikkben, az nem kis változtatás. Ugyanis azáltal hogy másképp osztod szét a pénzt, az eredeti játékmodellt átalakottad egy másik típusú játékká. Ezt az új modellt úgy hívják hogy koalíciós játékmodell, és teljesen más dinamikával és jellemzőkkel bír, mint az eredeti klasszikus modell.

TimeToLive 2011.01.08 20:08:51

@Haibane: Szervusz!
"Természetesen nem volt célom egy blogpostban az egész játékelméleti hátteret bemutatni, mert gondolom belátod, hogy ez nem lehetséges"

Persze, nem is az volt a célom, hogy kritizáljalak. Csak egy diszkussziót akartam kezdeményezni, miszerint az önzés akár hosszú távon is hasznos lehet, és nem feltétlenül káros a köz számára. Továbbá eddigi kutatásaim során számomra nagyon is úgy tűnik, hogy az önzés önmagában is hordoz együttmüködést (meta szinten), ha az ágens képes tanulni és a környezeti változásokhoz adaptálni.
Vagyis az önzés nem fehér-fekete valami. Erre mondtam az elején hogy a helyzet kicsit bonyolultabb (szerintem), mint amit te állítasz.

TimeToLive 2012.11.13 12:36:01

@Haibane: Bocsánat a késői válasszért, de rég nem jártam erre :)

Szóval ha érdekel a téma, akkor érdemes körülnézned a köv. területeken:

1. klasszikus game theory esetén fictitious play, amikor az ellenfelek stratégiáját lemodellezzük, és asszerint számítjuk ki a BR-t. Ez önmagában is hordozhatja a lehetséges együttmüködést

2. Evolutional game theory - elég sok cikk azzal foglalkozik hogy stabil populációk esetén a csupa önző ill. csupa kooperatív egyedekből álló halmazok összteljesítménye nem mindig a legjobb. Így kell vmilyen egyensúly. Persze ehhez a modellt kicsit módosítani kell, pl. bevezetni a befolyásolhatósági tényezőt: egy ágens sikeres stratégiáját mennyire akarja adoptálni a szomszédjai.

3. Behavioural game theory: ez egy nagyon új és érdekes területe a játékelméletnek. Itt mivel az ágensek nem feltétlenül hasonló szintű racionálitással tudnak gondolkodni (korlátozott info vagy erőforrás miatt), az önzés néha jól jön (pl. nem szimmetrikusak a célok). Erre egy nagyon érdekes példa a pár éve Martin Zinkevich (Yahoo/Google) és Mike Bowling (univ. of Alberta) által elindított Lemonade Stand Game (dl.acm.org/citation.cfm?id=1978730)

A játékban 3 játékos található, akiknek vmilyen célfv-t kell maximalizálniuk úgy, hogy nem kommunikálhatnak egymással. Viszont együttmükődés nélkül nem lehet a játékot megnyerni. Így az igazi (hosszútávú) önző stratégiáknak figyelembe kell venniük a rövidtávú együttmüködést :)

érdemes elolvasni a 2010es verseny nyertes csapatának az UAI-s cikkét:
eprints.soton.ac.uk/271215/1/ECAI-604.PDF

TimeToLive 2010.09.09 16:26:38

Szvsz a kvazi-random kereses vmi egyszeru koordinacioval kombinalva nem is olyan rossz modszer ebben az esetben.
Ugyanis az olajfoltok viszonylag nagy egybefuggo feluletek, igy ha az agens olajfoltot eszlel egy adott ponton, akkor nagy valoszinuseggel egy hatalmas olajfolt kozeleben van. Azaz erdemes az adott pont kornyekere koncentralni.

Amugy sok esetben a random local search meglepoen sokkal jobban teljesit mint sok mas csili-vili technikaval felszerelt modszer (pl. Bayes tanulassal, modell predikcioval stb).
Tipikus pelda erre a legutobbi Robocup Rescue Simulation verseny, ahol mas, de az olajfoltok tisztitasahoz hasonlo komplexitasu koordinacios feladatokat kellett az agenseknek megoldaniuk.

TimeToLive 2010.08.27 11:40:36

@pannonfunk: Sajnos a spanyolviasz jelenseg eleg gyakori a tudomany vilagaban. Ugyanis a kulonbozo tudomanyagak muveloi nem nagyon kommunikalnak egymassal.
Pl. siman elofordulhat, hogy neves MI konferenciakon olyan eredmenyeket mutatnak be ujnak, melyeket mar publikaltak par evvel elotte jatekelmeleti forumokon.

Mondjuk ez azert annyira nem rossz hir, mert ez azt jelenti, hogy bar a koncepcio azonos, es a konkluzio is hasonlo, maguk a modszerek masok lehetnek. Ezen kivul azt is mutatja, hogy az adott problemat tobb szemszogbol is meg lehet kozeliteni, es ilyenkor tudomanyagak kozti egyuttmukodesek johetnek letre. Ezt pedig nagyon szeretik az emberek :)

TimeToLive 2010.08.27 12:45:27

Hogy a bejegyzeshez is hozzaszoljak:

Sajnos en csak a cikk kivonatat olvastam, de az alapjan erdekesnek tunik.
Amugy a konkluzio nem ujdonsag az agensvilagban, ugyanis ha az agensek dontesei befolyasoljak a kornyezetuket, akkor egy-egy dontes kovetkezmenyei visszahatnak az adott agens kesobbi teljesitmenyere is. Igy elkerulhetetlen, hogy vmilyen szinten az agens megtanulja, hogy figyelembe kell vennie a tobbi agenst is, ha hosszutavon akar sikeres lenni.

TimeToLive 2010.08.23 00:49:46

@wmiki: pedig az ember is algoritmusok szerint mukodik :)
Mas kerdes, hogy mennyire bonyolult egy-egy algoritmusnak a leirasa (a bonyolultsagot tobbek kozott pl a Kolmogorov bonyolultsaggal lehet leirni), illetve annak hardveres megvalositasa.
Ezen kivul az is kerdeses, mennyire hatekony a leirt algoritmus (pl. idobeli koltseget nezve stb.)

Igy tehat az igazi kerdes nem az, hogy akkor algoritmussal (mechanizmussal, policy-vel stb) le lehet-e irni a kivant viselkedesi format, hanem az, hogy mennyire bonyolultan tudjuk csak megtenni a jelenlegi tudasunkkal.

Magyaran szolva az altalad emlitett intelligencia meg kreavititas is tobbe-kevesbe algoritmizalhato, csak kerdes hogy az mennyire lesz megvalosithato, leven hogy perpillanat korlatosak a kapacitasaink szoftver es hardver szinten is.

TimeToLive 2010.04.29 00:06:59

@stnksrbtks:azert nincs olyan messze az a nyugat :) Lehet hogy mar ismered, de Andrew Ng honlapjan jo dolgokat talalhatsz inverse RL-lel kapcsolatban.

TimeToLive 2010.04.23 18:59:56

"Gondoljunk csak arra, hogy még egy igen jól megprogramozott és tanított számítógépes program sem képes vetekedni az idősebb, tapasztaltabb orvosok képességeivel."

Véleményem szerint pedig még ez is lehetséges, mert a gépek is tudnak "tapasztalatot" gyűjteni. Viszont tény, hogy ez nem lesz egyerű. Ugyanis a tapasztalat nem más, mint egy megtanult "hatékony "módszer alkalmazása más helyzetekre. Ehhez viszont a következőket kell tennie a gépnek:

1. Egy tapasztalati tudásbázist felépíteni, humán szakértők segítségével.
2. Egy új helyzetről felismerni, hogy miben "hasonló" az eddig tapasztaltakhoz.
3. Kiválasztani a "leghatékonyabbat".
4. Az új tapasztalatokat beépíteni az adatbázisba.

A fenti lépések iteratív végrehajtásával képes lesz a gép önálló döntések meghozatalára.

Bár ezt egyszerű leírni, de a megvalósítás nagyon nehéz.
Ugyanis a következó problémákkal kell szembenéznie egy ilyen gépnek:

1. Hogyan kell felépíteni a kezdeti tudásbázist. Azaz hogyan tanítsuk meg a gépet, mi a jó módszer, ha az egy bonyolult folyamat (elég a fent említett orvosi, sebészeti példára gondolni - itt nem lehet mindent paramétert megtanítani, mert még mi emberek sem tudjuk, milyen paraméterekre, környezeti változókra kell figyelni).

2. Hogyan lehet felismerni, hogy egy új helyzet miben hasonló a régiekhez. Ha teljesen új, akkor ahelyett, hogy egy ismert módszerhez folyamodjon, meg kell tanulnia, mi az új hatékony megoldás. Ez viszont nagyon költséges lehet. Tehát létfontosságú a hasonlóságok megtalálása, és a létező tudás kihasználása.

Mindkét téma nagyon friss még, bár már vannak (egész jó) kezdeményezések: az első probléma megoldására pl ott van a reverse reinforcement learning, míg a másodikra a transfer learning.

TimeToLive 2010.04.26 01:34:25

@stnksrbtks: Mar nem is emlekszem, de valoszinuleg anno egy ismerosom beszelt rola :) Amugy ez a reward shaping egy fajtaja, ismeretlen kornyezetben. Sajnos ezt a teruletet sem ismerem igazan, de a kollegaim kozul sokan reward shaping-gel foglalkoznak.

Amugy te vmilyen robot tanitasra hasznalod az inverse RL-t? :)

TimeToLive 2010.04.21 11:56:46

A legtobb neuralis halo MSE-t (vagy vmi globalis fv-t ) minimalizal, viszont ez nem elegseges a rendszer dinamikus viselkedesenek a leirasahoz. Pl ha sokat es gyorsan valtozik a megtanulando parameter, akkor MSE minimalizalasa ertelmetlen, hiszen nehezen tudjuk megtanulni az aktualis erteket.

Dinamikus problemaknal alt. idoablakot hasznalnak, ill felejtesi egyutthatot. Mint ahogy emlitettem, nem ismerem a neural halos temat annyira, de gondolom akkor hogy ott is vmi hasonlo modszert alkalmaznak.

Viszont a masik problema az, hogy a neuralis haloknal (talan a Kohonen-nel nem) szukseges a tanitasi minta. Sajnos nagyon sok esetben ez nem all rendelkezesunkre (mert mi sem tudjuk, mi a "jo" kimenet). Ezzel ellentetben nagyon sok tanulasi modszer (pl. markov processek es tsai) kepes tanitasi minta nelkul is tanulni.

Osszesegeben nem azt mondom, hogy nem jo a neuralis halo, csak azt, hogy onmagaban nem eleg. Ugy gondolom, hogy arra pl jo, hogy knowledge reasoning-t tamogassa (pl data classification), ezaltal egy robusztus info bazist kepezve a tobbi absztraktabb tanulasi modszernek.

TimeToLive 2010.04.21 13:23:06

Ez persze csak sajat velemeny, es lehet hogy nincs igazam :)

TimeToLive 2010.04.21 16:25:30

@brlv24: Ha nem tevedek nagyot, akkor jelenleg azert kevesbe elfogadott a neuralis halos modszer meg, mert nagyon sokaig (Minskynek koszonhetoen) a perceptronos vonalat zsakutcanak tekintettek.

Szerintem sok potencial van benne, plane ha kombinaljuk mas tanulasi modszerekkel is :)

TimeToLive 2009.04.07 14:51:39

Bezzeg a Cernben strandpapucs és megsárgult fehér trikó a hivatalos dress code (főleg 80 éves Nobel-díjasoknál) ;)