Indargarri bidezko ikaskuntza
Indargarri bidezko ikaskuntza edo ikaskuntza indartua (ingelesez: reinforcement learning) ikaskuntza automatikoaren (AA) arlo bat da, psikologia konduktistan inspiratua. Haren zeregina software-agente batek ingurune jakin batean aukeratuko dituen ekintzak zehaztea da, "sari" edo irabazi metatu bat maximizatzeko helburuarekin. Arazoa orokorra denez, beste diziplina askotan aztertzen da, hala nola joko-teoria, kontrolaren teoria, ikerkuntza eragilea, informazio-teoria, simulazioetan oinarritutako optimizazioa, estatistika eta algoritmo genetikoak. Beste ikerketa-eremu batzuetan, non indargarri bidezko ikaskuntzako metodoak aztertzen diren, programazio dinamiko gerturatua esaten zaio. Arazoa kontrol optimoaren teorian aztertu da, baina ikerketa gehienak soluzio optimoen existentzian eta horien karakterizazioan zentratzen dira, ez ikasketa edo hurbilketa alderdietan. Ekonomian eta joko-teorian, indargarri bidezko ikaskuntza erabil daiteke arrazionaltasun mugatuko baldintzetan oreka nola sor daitekeen azaltzeko. Makinaren ikaskuntzan, ingurumena Markoven erabaki-prozesu (MDP) gisa formulatzen da normalean, eta indargarri bidezko ikasketako algoritmo askok lotura estua dute programazio dinamikoko teknikekin. Teknika klasikoen eta indargarri bidezko ikaskuntzako algoritmoen arteko alde nagusia da azken horietan ez dela beharrezkoa MDPak ezagutzea, eta MDP handietara zuzentzen direla, non metodo zehatzak ez-bideragarri bihurtzen diren. Indargarri bidezko ikaskuntza ez dator bat ikasketa gainbegiratuaren estandarrarekin, non sarrera / irteera pare zuzenak ez diren inoiz agertzen, eta ekintza suboptimoak ez diren esplizituki zuzentzen. Gainera, lineako errendimenduan ikuspegi bat dago, esplorazioaren (lurralde ezezagunen) eta explotazioaren (oraingo ezagutzen) harteko oreka aurkitzea deula helburu.
Sarrera
[aldatu | aldatu iturburu kodea]Indargarri bidezko ikaskuntzaren oinarrizko eredua honakoa da:
- Inguruneko egoeren multzo bat;
- Ekintzen multzo bat;
- Egoeren arteko trantsizioaren arauak;
- Trantsizio baten berehalako saria zehazten duten arauak;
- Agenteak sumatzen duena deskribatzen duten arauak.
Arauak estokastikoak dira askotan. Behaketak, normalean, azken trantsizioarekin lotutako berehalako saria esan nahi du. Ereduetan, agenteak pentsatuko du ingurunearen egungo egoera osoa behatzen duela; kasu horretan, erabateko behagarritasunaz hitz egiten da, eta, kontrako kasuetan, berriz, partzialki behagarritasunaz; adibidez, xake partida batean agentea bere inguruneko osagai guztitaz ageri da, baina karta partida batean, agenteak ez daki bere etsaiek zein karta dituzten. Batzuetan, agentearentzat eskuragarri dauden ekintza batzuk mugatuta daude; adibidez, ezin dugu gastatu duguna baino diru gehiago gastatu. Ikaskuntza indartuko agente batek bere ingurunearekin denbora-pauso diskretuetan elkarreragingo du. Agenteak denbora-tarte bakoitzean behaketa bat jasotzen du, normalean saria barne edukiko duena. Orduan, ekintza-multzoko ekintza bat aukeratzen da, eta, ondoren, ingurunera bidaltzen da. egoera berri batera mugitzen da ingurunea, eta trantsizioarekin lotutako saria zehaztu egiten da. Indargarri bidezko ikaskuntzako agente baten helburua ahalik eta sari gehien jasotzea da. Agenteak edozein ekintza aukeratu dezake bere ekintza istorioaren arabera, eta ausaz ere egin dezake bere ekintzen hautaketa. Agentearen errendimendua hasiera-hasieratik modu optimoan jarduten duen agente batenarekin alderatzen denean, agente horien arteko aldeak damuaren nozioa sortzen du. Kontuan izan behar da, era optimoan jardun ahal izateko, agenteak bere ekintzen epe luzerako ondorioei buruz arrazoitu behar duela: «etorkizuneko diru-sarrerak maximizatzeko asmoz, hobe litzateke eskolara orain joatea, ekintza horrekin lortutako diru-sarrera negatiboa izan daitekeen arren». Beraz, indargarri bidezko ikaskuntza bereziki egokia da epe luzeko eta epe laburreko arrazoiketak barne hartzen dituzten arazoetarako. Arrakastaz aplikatu da hainbat arazotan, besteak beste, erroboten kontrolean, telekomunikazioetan, backgammon-en eta dametan. Bi osagaik egiten dute indargarri bideko ikaskuntza irismen handikoa: laginen erabilera errendimendua optimizatzeko eta hurbiltze-funtzioaren erabilera tamaina handiko inguruneei aurre egiteko. Funtsezko bi osagai horiei esker, indargarri bidezko ikaskuntza tamaina handiko inguruneetan erabil daiteke, ondorengo ingurune edozeinetan:
- Inguruanearen eredua ezaguna da, baina soluzio analitiko bat ez dago eskuragarri;
- Ingurunearen simulazio-eredu bakarra ematen da (simulazioan oinarritutako optimizazioaren gaia);
- Inguruneari buruzko informazioa biltzeko modu bakarra harekin elkarrekintzan aritzea da.
Lehenengo bi inguruneak plangintza-problematzat har daitezke (moduren batean edo bestean, eredua eskuragarri badago), eta azkena, berriz, ikaskuntza klasikoko problematzat. Hala ere, indargarri bidezko ikaskuntza metodologiaren menpean, plangintza-arazoak ikasketa automatikoko (AA) arazo bihurtzen dira.
Esplorazioa
[aldatu | aldatu iturburu kodea]Ikaskuntza indartuaren arazoa, deskribatu den bezala, esplorazio adimenduneko mekanismoak eskatzen dituela da. Ekintzak ausaz hautatzeak, ezagutzen den probabilitate-banaketa estimatu bat oinarri gisa erabili gabe, oso errendimendu eskasa ematen du. MDP (txiki) finituen kasua nahiko ondo ulertzen da oraingoz. Hala ere, egoera kopuruarekin ondo eskalatzen duten algoritmorik ez dagoenez, praktikan jendeak esplorazio metodo sinpleetara jotzen du. Metodo horietako bat -greedy deiturikoa da, agenteak epe luzerako irabazi onena duen ekintza aukeratuko du probabilitate batekin, eta, bestalde, probabiltateariekin, uniformeki ausazkoa den ekintza bat aukeratuko du. Hemen, balioa doikuntza parametro bat da, batzuetan aldatu egiten dena, bai ordutegi finko baten arabera (beraz, agenteak gutxiago esploratuko du denbora pasatzen joaten den bitartean), bai modu moldakor batean, heuristiko batzuetan oinarrituta (Tokic eta Palma, 2011).
Ikaskuntza kontrolatzeko algoritmoak
[aldatu | aldatu iturburu kodea]Esplorazioaren gaia kontuan hartuta, eta egoera behagarria izanda ere (hemendik aurrera asumituko duguna), zain ekintza hartu iraganean edukitako esperientzien arabera da oraindik gure arazo nagusia, honetarako, hainbat algoritmo proposatu dira arazoari soluzioa emateko:
Optimotasun-irizpidea
[aldatu | aldatu iturburu kodea]Sinplifikatzeko, esango dugu aztertzen ari garen arazoa egaerakakoa dela, egoera terminal batera iristean amaituko dena. Demagun, gainera, agenteak egiten dituen ekintzak ez diotela axola, egoera terminal batean bei bukatuko duela. Erregulartasun gehigarriko baldintza jakin batzuetan, ongi definituta dago sari osoaren itxaropena edozein politikarentzat eta egoeren gaineko hasierako edozein banaketarentzat. Sentzu horretan, politika bat egoera posible guztiei ekintzen gaineko probabilitate-banaketa jakin bat esleitzea da. Beraz, hasierako banaketa finkoa emanda, espero dugun itzulera eslei diezaiokegu : politikari non zorizko aldagaiak irabazia adierazten duen eta honela definitzen den:non -garren pausoaren ondoren jasotako saria den tokian, hasierako egoera banaketaren zorizko laginketa bidez egiten da eta ekintzak politikak aukeratzen ditu. Hemen, -k egoera terminal batera iristeko behar den ausazko denbora adierazten du, hau da, arazoa amaitzen den unea. Episodikoak ez diren arazoen kasuan, itzulera deskontatu egiten da maiz honela: eta honela deskontu totalerako espero den sariaren irizpidea sortzen da. balioari deskontu-faktorea deitzen zaio. Honek nahiko xaloa dirudien arren, deskontua arazo bat da lineako errendimenduaz arduratzen bazara. Izan ere, deskontuaren ondorioz, garrantzia hasierako urratsen denboran jartzen baita. Ikaskuntza-agente batek "bizitza" hasi ondorengo lehen urratsetan akatsak egin ditzakeenez, informaziorik gabeko ikaskuntza-algoritmo batek ezin du errendimendu optimorik lortu deskontuan, ezta inguruneen klasea PDM finituen klasera mugatuta badago ere. (Horrek ez du esan nahi, hala ere, denbora nahikoa emanik, ikaskuntzako agente batek ezin duela ikasi nola jokatu modu ia optimoan, denbora berrabiarazi bada). Orduan, arazoa da algoritmo bat zehaztea, eta algoritmo horrek espero den etekinik handiena duen politika bat aurkitzea. PDM-ren teoriatik badakigu, orokortasunik galdu gabe, politika geldikor deritzen multzora murriztu daitekeela. Politika bat geldikor deitzen da, itzultzen duen ekintza-banaketa bisitatutako azken egoeraren araberakoa bada (agentearen behaketaren historiaren zati bat dena, gure sinplifikazio honetan). Gainera, bilaketa are gehiago murritz daiteke politika geldikor deterministeta bada. Politika geldikor determinista egungo egoeran oinarritutako ekintzak modu deterministan aukeratzen dituena da.
Indar gordina
[aldatu | aldatu iturburu kodea]Indar gordin bidezko ikuspegiak bi etapa hauek ditu:
- Politika posible bakoitzerako, emaitzen laginketa egin.
- Irabazi handiena espero duen politikia hautatu.
Ikuspegi honen arazo bat da politika kopurua izugarri handia izan daitekeela, edo amaigabea ere bai. Beste kontu bat da errendimenduaren bariantza handia izan litekeela; kasu horretan, lagin kopuru handia behar da politika bakoitzaren itzulera zehaztasunez zenbatesteko. Arazo horiek arindu egin daitezke egituraren bat erabiliz, eta laginak politika batetik abiatuta sortzea ahalbidetu, beste batek egindako estimazioetan eragiteko. Hori lortzeko bi ikuspegi nagusiak balioaren funtzioen estimazioa eta politika zuzenen bilaketa dira.
Balioaren funtzioen estimazioa
[aldatu | aldatu iturburu kodea]Balio-funtzioak irabazia maximizatzen duen politika bat bilatzen saiatzen dira, politikaren batek espero dituen etekinen estimazio bat mantentzean (bai oraingo poltika, edo politika alternatibo bat). Metodo horiek PDM-en teorian oinarritzen dira, non optimotasuna aurrekoak baino indartsuagoa den zentzu batean definitzen den: Politika bat optimoa deitzen da edozein hasierako egoeratan espero den errendimendu hoberena lortzen bada (hau da, hasierako egoeren banaketek ez dute inolako zerikusirik definizio horretan). Aurretik esan bezala, politika geldikorren artean beti aurki daiteke politika optimoa. Optimitatea modu formal batean definitzeko, politika baten balioa honela definitu behar da: non -k hasierako egoeratik hurrengo egoerei lotutako ausazko irabazia esan nahi duen. balioa -k artu ahal duen balio maximo posible gisa definitzen da, non politikari aldatzeko aukera ematen zaion: Egoera bakoitzean balio optimo horiek lortzen dituen politikari optimoa deritzo. Balio funtzio bat ere ekintzen baitan kalkula daiteke: egoera, ekintza eta politika emanda, bikotearen balio-funtzioa politikaren menpean honela definitzen da:non balioak ekintzak egoeran itzuliko deun irabazia esan nahi duen. PDMen teoriatik abiatuta ezaguna da norbaitek politika optimorako ematen badigu, beti aukera dezakegula ekintza optimoak egoera bakoitzean balio altuena duen ekintza aukeratuz. Politika optimoaren ekintza-balio funtzioari ekintza-balio funtzio optimoa deitzen zaio, eta honela adierazten da: . MDP.a erabat ezagutzen dela jota, oinarrizko bi algoritmo daude balio optimoa kalkulatzeko: balio iterazioa eta politika iterazioa. Bi algoritmoek funtzioen () sekuentzia bat kalkulatzen dute, balioan bat egiten dutenak
MonteCarlo metodoa
[aldatu | aldatu iturburu kodea]MonteCarlo Metodo sinpleenak iterazio politikak imitatzen dituen algoritmo batean erabil daitezke. Politika iterazioa bi fasez osatuta dago: ebaluazioa eta hobetzea. MonteCarlo Metodoak ebaluazio fasean erabiltzen dira. Fase honetan, π politika determinista estatikoa emanda, helburua Q^π (s,a) funtzioaren balioak (edo ongi hurbildutako balioa) kalkulatzea da estatu-ekintzako bikote guztientzat (s,a). Suposatuko dugu (sinpleago egiteko), MDP finitua dela eta egoeren arabera ekintzen taula memorian dagoela suposatuko dugu. Horrez gain, arazoa episodikoa dela suposatzen da, eta episodo bakoitzaren ondoren, episodio berri bat hasten da egoera hasierako aleatorio batetik. Beraz, (s,a) estatu-ekintzako bikote baten balioaren estimazioa (s,a), sor daiteken lagin errendimenduen batez bestekoa kalkulatuz lor daiteke. Denbora nahikoa emanda, prozedura honek Q ekintza-balio funtzioaren estimazio zehatza eraiki dezake. Hemen amaitzen da politikaren ebaluazio fasearen deskribapena. Politiken hobetze fasean, iterazio algoritmoan egiten den bezala, hurrengo politika Q araberako greedy politika bat erabiliz lortzen da: egoera s emanda, politika berri honek Q(s,⋅) maximizatzen duen ekintza bat itzultzen du. Praktikan, askotan, politika berriaren kalkulua eta biltegiratzea saihesten da, baina ekintzak maximizatzen dituztenak benetan kalkulatzea behar denean, ebaluazio nagia erabiltzen da. Prozedura honek honako arazo batzuk ekar ditzake:
- Politika suboptimo baten ebaluazioan denbora asko galdu daiteke;
- Laginen erabilera ez da eraginkorra;
- Ibilbideek bariantza handia dutenean, konbergentzia motelagoa izango da;
- Arazo episodikoetan bakarrik funtzionatzen du;
- MDP txiki eta finituetan bakarrik funtzionatzen du.
Denbora-aldeen metodoak
[aldatu | aldatu iturburu kodea]Lehen arazoa erraz konpon daiteke, prozedurak politika aldatu ahal izatea baimenduz (egoera guztietan edo batzuetan) balioak ezarri aurretik. Onegia dirudien arren, arriskutsua izan daiteke, konbergentzia galaraz dezakeelako. Hala ere, egungo algoritmo gehienek ideia hori ezartzen dute, politika-iterazio orokortuaren algoritmo klaseari bide emanez. Pasadan ohartarazten gara, kritikoak diren aktore metodoak kategoria honetan sartzen direla. Bigarren arazoa algoritmoan konpon daiteke, ibilbideei estatuko-ekintzako bikote bakoitzari laguntzen uzten zaienean. Honek, neurri batean, hirugarren arazoari ere lagun diezaioke, nahiz eta errendimenduak bariantza handia dutenean, soluzio hobe bat Sutton-en denbora-diferentziaren (TD) metodoak erabiltzea izan daiteke, Bellman-en ekuazio errekurtsiboan oinarritzen dena. Kontuan izan TD metodoen kalkulua inkrementala (memoria trantsizio bakoitzaren ondoren aldatzen da eta trantsizioa baztertu egiten da) edo multzoetan (trantsizioak jasotzen dira eta estimazioak behin kalkulatzen dira trantsizio kopuru handi batean oinarrituta) izan daitekeela. Multzo-metodoak, zeinetan adibide bikaina Bradtke eta Barto-k (1996) proposatutako karratu minimoen denbora-diferentzia metodoa den, laginen informazioa hobeto erabil dezakete, metodo inkrementalak aukera bakarra diren arren, prozesu-batch metodoak bideraezinak bihurtzen direnean konplexutasun handia edo memoria eskatzen dutelako. Gainera, bi ikuspegien abantailak bateratzen saiatzen diren metodoak daude. Aurreko paragrafoan aipatutako azken gaiari heltzeko, funtzioak hurbiltzeko metodoak erabiltzen dira. Funtzio linealaren hurbilketa batean, dimentsio finituko bektore bat egoera-ekintza bikote bakoitzari esleitzen zaio. Orduan, egoera-ekintza bikote baten ekintza-balioak lortzen dira ϕ bektorearen osagaiak konbinatuz ϕ(s,a) pisu batzuekin θ: Q(s,a)=∑i=1dθiϕi(s,a). Funtzioaren hurbilketa lineala ez da aukera bakarra. Gertuago, estatistika ez-parametrikoaren ideietan oinarritutako metodoak aztertu dira (zeintzuk beren ezaugarriak eraikitzen dituztela ikus daitezke). Orain arte, eztabaida politikaren iterazioa erabiltzeko moduaz mugatu da, ikasketa indargarriaren algoritmoak diseinatzeko oinarri bezala. Garrantzitsua da ere, balioaren iterazioa abiapuntutzat har daitekeela, Q-ikaskuntza algoritmoa (Watkins 1989) eta bere hainbat aldaera sortuz. Ekintza-balioak erabiltzen dituzten metodoen arazoa da litekeena dela ekintza-lehiakidearen balioaren estimazio zehatzak behar izatea, eta zaila izan daiteke errendimenduak zaratatsuak direnean lortzea. Arazo hori, nolabait, denbora-diferentzia metodoek arintzen dute, eta bateragarriak diren funtzioak hurbiltzeko metodoa erabiltzen bada, asko dago egiteko orokortasuna eta eraginkortasuna handitzeko. Denbora-diferentzia metodoen arazo espezifiko bat Bellman-en ekuazio errekurtsiboarekiko duten menpekotasunetik dator. Denbora-diferentzia metodo gehienek λ parametroa dute (0≤λ≤1), Monte-Carlo metodoen (Bellman-en ekuazioetan oinarritzen ez direnak) eta oinarrizko denbora-diferentzia metodoen artean jarraian interpolatu ahal izateko aukera ematen duena (ekintza horiek Bellman-en ekuazioetan soilik oinarritzen dira), beraz, arazo hau arintzeko eraginkorra izan daiteke.
Politika bilaketa zuzena
[aldatu | aldatu iturburu kodea]Politika on bat aurkitzeko metodo alternatibo bat politika espazioaren (submultzo baten) barruan bilatzea da, kasu honetan arazoa optimizazio estokastiko baten adibide bihurtzen delako. Eskuragarri dauden bi hurbilketak, gradienteetan eta gradiente libreko metodoetan oinarritzen dira. Gradienteetan oinarritutako metodoek (politika gradiente metodoak deitzen direnak) dimentsio mugatuko (parametro) espazio bat politikaren espazioari esleitzen diote: Parametro bektorea θ emanda, π_θ erabiliz θ-ri loturiko politika adierazteko. Errendimendu funtzioa honela definitzen da: ρ(θ) = ρ^(π_θ). Baldintza leunetan funtzio hau diferentziagarria izango da parametroen bektorearen funtzio gisa. ρ-ren gradientea ezagutzen bada, gradiente igoera erabil daiteke. Gradientea zehazki eskuratzeko adierazpen analitikorik ez dagoenez, estimazio zaratatsu baten menpe egon behar da. Estimazio hori era askotara eraiki daiteke, Williams' Reinforce metodoa bezalako algoritmoak emanez. Metodoen klase handi batek gradiente informazioaren menpe egotea saihesten du. Horien artean simulatutako erretzea, entropia gurutzatuko bilaketa edo eboluzio konputazionaleko metodoak daude. Gradiente libreko metodo askok (teorian eta muga batean) optimo globala lortu dezakete. Kasu batzuetan, benetan errendimendu nabarmena erakutsi dute. Bilaketa metodoen arazoa da informazio zaratatsuari jarraitzen badio, poliki konbergitzen direla. Adibidez, hori arazo episodikoetan gertatzen da, ibilbideak luzerakoak direnean eta irabazien aldagaitza handia denean. Lehenago adierazi den bezala, denbora aldagaietan oinarritutako balio funtzioetan oinarritutako metodoek lagundu dezakete kasu honetan. Azken urteetan ideia honen inguruan hainbat algoritmo aktore eta kritiko proposatu dira, eta arazo desberdinetan errendimendu ona erakutsi dute.
Teoria
[aldatu | aldatu iturburu kodea]MDP txikien teoria, finitua denean, nahiko heldua dago. Algoritmo gehienen portaera asintotikoa zein lagin finituko portaera ondo ulertuta daude. Aurretik aipatu bezala, linea bidezko errendimendu ona duten algoritmoak ezagunak dira. MDP handien teoria gehiago landu behar da. Azterketa eraginkorra ia ukitu gabe dago (bandidoen arazoak salbu). Azken urteotan, denbora finituko errendimendu mugak dituzten algoritmo asko agertu diren arren, espero da mugak hobetzea, nahiko zehaztugabeak baitira, eta, beraz, gehiago lan egin behar da algoritmo hauen abantaila erlatiboak eta mugak hobeto ulertzeko. Algoritmo inkrementalentzat, asintotikoen bategite arazoak konpondu dira. Azkenaldian, denborazko diferentzietan oinarritutako algoritmo inkremental berriak agertu dira, eta baldintza askoz zabalagoetan bategiten dute lehen baino.
Erreferentziak
[aldatu | aldatu iturburu kodea]- Sutton, Richard S.. (1988). «Learning to predict by the method of temporal differences» Machine Learning (Springer) 3: 9–44. doi: ..
- Bradtke, Steven J.; Andrew G. Barto. (1996). «Learning to predict by the method of temporal differences» Machine Learning (Springer) 22: 33–57. doi: ..
- Kaelbling, Leslie P.; Michael L. Littman; Andrew W. Moore. (1996). «Reinforcement Learning: A Survey» Journal of Artificial Intelligence Research 4: 237–285..
- Peters, Jan. (2003). Reinforcement Learning for Humanoid Robotics. .
- Auer, Peter; Thomas Jaksch; Ronald Ortner. (2010). «Near-optimal regret bounds for reinforcement learning» Journal of Machine Learning Research 11: 1563–1600..
- Szita, Istvan. (2010). Model-based Reinforcement Learning with Nearly Tight Exploration Complexity Bounds. Omnipress, 1031–1038 or..
Kanpo loturak
[aldatu | aldatu iturburu kodea]- Reinforcement Learning and Artificial Intelligence (Sutton's lab at the University of Alberta) (ingelesez)
- Autonomous Learning Laboratory (Barto's lab at the University of Massachusetts Amherst) (ingelesez)
- RL-Glue (ingelesez)
- Software Tools for Reinforcement Learning (Matlab and Python) (ingelesez)
- The UofA Reinforcement Learning Library (texts) (ingelesez)
- The Reinforcement Learning Toolbox from the (Graz University of Technology) (ingelesez)
- Hybrid reinforcement learning (ingelesez)
- Piqle: a Generic Java Platform for Reinforcement Learning (ingelesez)
- A Short Introduction To Some Reinforcement Learning Algorithms (ingelesez)
- Reinforcement Learning applied to Tic-Tac-Toe Game (ingelesez)
- Scholarpedia Reinforcement Learning (ingelesez)
- Scholarpedia Aldi Baterako Difference Learning (ingelesez)
- Stanford Reinforcement Learning Course (ingelesez)
- Real-world reinforcement learning experiments at Delft University of Technology (ingelesez)
- Reinforcement Learning Tools for Matlab (ingelesez)
- Stanford University Andrew Ng Lecture on Reinforcement Learning (ingelesez)
- Relative Entropy Policy Search (ingelesez)