Errefortzu bidezko ikaskuntzari sarrera. 1. zatia: beso anitzeko bidelapurraren problema.

Beso anitzeko bidelapurraren problema

Artikulu hauetan, ingelesez idatzitako terminologiari egingo diot erreferentzia, ezagunena delako eta bibliografian erreferentziak eta informazioa bilatzeko era onena delako.

Errefortzu bidezko ikaskuntzaz (Reinforcement Learning, ingelesez) arituko gara artikulu hauetan. Hau adimen artifizialaren barnean sartzen den teknika edo arlo bat da. Agente adimendun (agent) batek ingurune (environment) batekin elkarreragin behar du, ingurunearen egoera (state) posible bakoitzean eskuragarri dauden ekintzetako (action) bat aukeratuz, eta ekintza horien ondorioz ahalik eta saririk (reward) handiena lortzen saiatuz.

Hasieran, agenteak ez du ingurua batere ezagutzen. Beraz, ausaz hartuko ditu ekintzak. Ekintza batek sari positiboa ekartzen badu, agenteak ekintza hori maizago aukeratzen ikasi beharko du; ekintza batek sari negatiboa ekartzen badu, ordea, agenteak ekintza hori sahiesten ikasi beharko du. Honela, agenteak jasotako sarien batura maximizatzen duten ekintzak aukeratzen ikasi beharko du. Hori itzulera (return) bezala ere ezagutzen da.

Beso anitzeko bidelapurraren problema (multi-armed bandit problem)

Irudiaren jatorria

Beso anitzeko bidelapurraren problema txanpon-makinen arazo gisa ikus daiteke, kasino batean bezala. N txanpon-makina baditugu, eta bakoitzak p probabilitatearekin sari positibo bat ematen badigu, eta (1-p) probabilitatearekin inolako saririk ez badigu ematen, sor al dezakegu sariak maximizatuko dituen agenterik, beti onura handiena ekarriko digun txanpon-makinan jokatzea aukeratuz? Izan ere, problema hau gauza berbera da, N besoko bidelapur bat dugu, eta beso bakoitzak sari positibo bat emateko probabilitate ezberdina du. Helburua sari horiek maximizatuko dituen agente bat sortzea da.

Artikulu honetarako, N=5 besoko bidelapur bat (5-armed bandit) erabiliko dugu. Hauek izango dira beso bakoitzak sari positiboa emateko dituen probabilitateak: [0.1, 0.3, 0.05, 0.55, 0.4]. Ikus dezakegun bezala, bost horien arteko ekintzarik onena laugarren besotik tira egitea da. Agenteak, ordea, ez dauka informazio hori. Beraz, agenteak hainbat aldiz probatu beharko du beso guztietatik tira egiten, eta denetatik onena zein den ikasten joan beharko du. Informazio gehiago pilatzen duenean, erabaki hobeak hartzen hasiko da, eta sari hobeak jasoko ditu.

ε-jale politika (ε-greedy policy)

Hori izango da gure agenteak zein ekintza hartuko duen erabakiko duen politika (policy). ε-jale politika honetan datza: agenteak ahalik eta ekintzarik onena hartuko du ia beti, daukan informazioa baliatuz. Hala ere, noizean behin, ε (epsilon) balioko probabilitate batekin, agenteak ausaz hartuko du ekintza bat. Horrela, ekintza bakar bat hartu ondoren agenteak sari positiboa lortu badu, agentea ez da trabatuta geratuko ekintza hori bera hautatzen denbora guztian. ε probabilitatez, agenteak beste aukera batzuk esploratuko ditu. Balio hori guk erabakiko dugu, eta esplorazio eta esplotazio arazoa orekatzeko modua izango da (exploration vs. exploitation). Esplorazioa ekintza posible guztiak hainbat aldiz probatzean datza, onena zein den ikusteko, nahiz eta esplorazio horretan sari oso onak lortu ez. Esplotazioa sariak maximizatzean datza, eta beraz agenteak ekintza onena aukeratuko du beti. Horregatik, garrantzitsua da esplorazioa eta esplotazioa orekatzea. Alde batetik, bost ekintzetatik bi bakarrik esploratzen baditugu, ez dugu inoiz jakingo probatu ez ditugun ekintzek sari handiagoak ekarriko dizkiguten, eta, beraz, esplorazioa beharrezkoa da. Bestetik, denbora guztia aukera guztiak behin eta berriz probatzen jarduten bagara, ez dugu inoiz ezagutza hori erabiliko ekintzarik onena aukeratu eta ahalik eta saririk handiena lortu ahal izateko.

Kodea

Beso anitzeko bidelapurraren problema ebatziko duen agente bat sortuko dugu. Kodea zuk zeuk urratsez urrats exekutatu nahi baduzu, egin klik esteka honetan. Bestela, irakurtzen jarrai ezazu, kodea exekutatu gabe ikusteko.

Has gaitezen kodearekin. Bost besoetako bat aukeratzeko aukera emango digun funtzio bat idatziko dugu, eta sari bat itzuliko digu, beso horren probabilitatearen arabera.

1 algoritmoa. Bidelapurraren beso batetik tira egiteko funtzioa.

Orain, agenteak zein ekintza hartu behar duen erabakitzen duen funtzioa idatziko dugu. Epsilon probabilitatearekin ausazko ekintza bat hartuko du, eta bestela, sarien batazbesteko altuena duen ekintza hartuko du.

2 algoritmoa. ε-jale politika.

Azkenik, definitu ditzagun besoen probabilitateak, lehen aipatu dugun bezala, eta definitu ditzagun epsilon parametroaren balioa eta iterazio kopurua. Zehaztu ditzagun, halaber, hiru lista, orain arte hartutako ekintzei eta beso bakoitzarentzat lortutako sariei buruzko informazioa gordetzeko.

Algoritmoa exekutatuko dugu funtzio desberdinei deituz, eta sariak gordeko ditugu.

3 algoritmoa. Begizta nagusia exekutatu eta sariak inprimatu.

Amaieran, hau idatziko du:

Average reward for bandits is [0.19, 0.31, 0.04, 0.55, 0.40]
Best bandit is 3 with an average observed reward of 0.55
Total observed reward in the 1000 episodes has been 493

Beso bakoitzak sortu dituen sarien batazbestekoarekin osaturiko lista eta beso bakoitzarentzat definitu ditugun probabilitateen listak konparatuz, oso antzekoak direla ikusiko dugu. Hau da, 1.000 iteraziorekin beso bakoitzak arrakasta izateko probabilitatea aurkitu dugu, eta orain badakigu laugarren besoa dela onena (3 indizea Pythoneko listan). Prozesu horretan, 493 sari positibo lortu ditugu. Oso zenbaki altua da, kontuan hartuta hasieratik beso onena aukeratuta 550 sari positibo lortuko genituzkeela (0.55eko probabilitatea duelako). Epsilon balioa eta iterazio kopurua alda ditzakegu, balio horiek jasotako sari totalari nola eragiten dioten ikusteko.

Kodea guztia ikusi eta exekutatu nahi baduzu, egin klik esteka honetan.

Erreferentziak:

Sutton, R. S., & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.

Multi-armed bandit problem (Wikipedia)

Errefortzu bidezko ikaskuntzari sarrera serie osoa:

1. zatia: beso anitzeko bidelapurraren problema
2. zatia: Q-Learning
3. zatia: Q-learning sare neuronalekin, DQN algoritmoa
4. zatia: Double DQN eta Dueling DQN