MISKOLCI EGYETEM GÉPÉSZMÉRNÖKI ÉS INFORMATIKAI KAR
Megerősítéses tanulási módszerek és alkalmazásaik
Tompa Tamás tanársegéd Általános Informatikai Intézeti Tanszék
Miskolc, 2017. szeptember 15.
Tartalom
Gépi tanulás története Gépi tanulás típusai A megerősítéses tanulás Q-learning SARSA FRIQ-learning FRIQ-learning Maze, Pong alkalmazás példák
A gépi tanulás története
1947-ben Arthur Lee Samuel
dáma játék, ami képes legyőzni a világbajnokot motiváló okok: szimbolikus számítás hatékonyságának bemutatása szükség van PC-re az egyetemeken
20 évnyi fejlesztés
gépi tanulás alappillérjeinek megalkotása
A gépi tanulás
A gépi tanulás alapgondolata
egy ágens képességeinek javítása
A gépi tanulás egy eljárás, amely
a rendszerben változásokat hoz létre a változtatások következtében a problémát a rendszer már helyesebben oldja meg
A gépi tanulás formái
Felügyelt (ellenőrzött)
Felügyelet nélküli (nem ellenőrzött)
supervised learning
unsupervised learning
Megerősítéses
reinforcement learning
A megerősítéses tanulás
Egy módszer, amely
megerősítési információk alapján tanul a környezetből érkező visszajelzések a megerősítések (reward)
jutalmak/büntetések (sikerek/kudarcok)
cél: várható jutalmak maximalizálása (optimális stratégia keresése)
Pl.: egy ismeretlen játék játszása
A megerősítéses tanulás típusa
Passzív
rögzített stratégia -> viselkedés cél: stratégia jóságának megtanulása
Aktív
nincs rögzített stratégia cselekvés választásának eldöntése (mohó például) cél: cselekvésérték-függvény tanulása
A megerősítéses tanulás elemei
állapot (s), akció (a), jutalom (r) politika (policy) jutalom függvény (reward function) értékelő függvény (value funciton) környezet modellje (model of the environment)
8
Ágens-környezet modell
Ágens-környezet modell – példa
Ágens-környezet modell
ágens
lehet bármi, ami (érzékelőivel) érzékeli a környezetét és (beavatkozóival) megváltoztatja azt
környezet
determinisztikus: következő állapota, csakis a jelenlegi állapotától és a végrehajtott cselekvéstől függ nem determinisztikus: következő állapotát nem határozza meg az előző állapot és a végrehajtott cselekvés
Ágens-környezet modell
állapot (s), akció (a), jutalom (r), politika (π) állapot: az ágens megfigyelése a környezetről akció: cselekvés, ez hat a környezetre jutalom: egyetlen szám politika: állapot-akció leképezés
Ágens-környezet modell
diszkrét idő ( t=1, 2, 3, …) minden egyes t időpillanatban az ágens megkapja a környezet ez alapján választ egy akciót a választott akció függvényeként kap egy jutalmat majd egy új állapotba kerül az ágens célja: hosszú távon maximalizálja az összegyűjtött jutalmakat epizódikusság
Ágens-környezet modell at st
st+1 rt+1
st:
állapot a t időpillanatban at: a végrehajtott akció a t időpillanatban rt+1: a kapott jutalom a t+1 időpillanatban st+1: az új állapot Πt(s, a): s-ben a lépés a t időpontban 14
Ágens-környezet modell
Az összegyűjtött jutalmak összegét hozamnak nevezzük:
ahol T, az utolsó időpillanat ha nem beszélhetünk utolsó időpillanatról akkor:
gond: Rt végtelen lehet
megoldás: diszkontálás, a diszkontált hozam:
Ágens-környezet modell
Összefoglalva, a hozamfüggvény a következő formában írható fel:
γ a diszkontálási paraméter: a jelen állapot jövőre vetíthetőségének mértéke.
mekkora súllyal vegyük figyelembe egy későbbi állapot hasznosságát értéke: [0;1]
Ágens-környezet modell
A feladat realizálása:
interakció a környezet modellje: az átmeneti valószínűségek és jutalmak
cél: maximális várható jutalom, optimális stratégia megtalálása
A Markov-feltevés
Feltesszük, hogy a múlt nem számít
Markov-tulajdonság : egy folyamat jövőbeli feltételezett állapota csak a jelenlegi állapottól függ, még akkor is, ha ismerjük a korábbi történéseket nincs „emlékezés” az átmeneti valószínűség megadja az s′ állapotba kerülés valószínűségét s állapotból a akció választása mellett: a várható jutalom: azokra a feladatokra alkalmazható a megerősítéses tanulás módszere, amelyek Markov-tulajdonságúak
Az állapot értékelő függvény
Eπ jelöli a π politika követése melletti várható értéket, a t tetszőleges időpillanatban.
Megadjuk az s állapotban a akció választásának értékét a π politika mellett. Ezt Qπ (s,a) -val jelöljük:
A Bellman-egyenlet
Az előzőek alapján a következő egyenlet a Vπ -re vonatkozó Bellman-egyenlet:
egy állapot hasznosságának meghatározása egy állapot hasznossága, az állapotban tartózkodás jutalmának és a következő állapot várható hasznosságának összege az állapotok hasznosságai a Bellman-egyenletek egy rendszerének egyértelmű megoldásai
A Bellman-egyenlet
Optimális:
V*(s): s-ből indulva Q*(s,a): s-ben a
A Bellman-egyenlet megoldása:
dinamikus programozással
értékiteráció
minden egyes állapot hasznosságának számítása -> optimális cselekvés választása
eljárásmód-iteráció
ha egy akció jobb mint a többi -> a releváns állapotok hasznosságainak nagyságát nem szükséges precízen tudni >értékelés;javítás. Leáll ha nincs hasznosságváltozás.
Megerősítéses tanulási algoritmusok
Q-learning SARSA Fuzzy Q-learning FRI based Q-learning Stb.
Q-learning
az egyik leggyakrabban alkalmazott megerősítéses tanulási módszer Q – quality érték Q(s,a): s-ben a végrehajtásának jósága -> Q(s,a) párok ->Q-függvény; Q-tábla
Update formula:
Q-learning - algoritmus
Q-learning - algoritmus
SARSA
Szintén megerősítéses tanulási algoritmus State-Action-Reward-State-Action A Q-learning hasonló módszer
Update formula:
26
SARSA - algoritmus
27
Q-learning vs. SARSA
28
Q-learning hátrány
lehetséges állapotok exponenciálisan sok száma állapottér növekedése Q-tábla növekedése konvergenciája exponenciálisan lassú lehet Kb. 10000 a kezelhető állapotok száma Pl. n db állapotleíró, k részre osztva: kn az állapotok száma
29
RL alkalmazások
TD-Gammon (Tesauro, 1992) Robotirányítási alkalmazások
inverz inga (cart-pole) mountain- car maze pong rc drift autó: video és számos egyéb...
30
FRIQ-learning
Az előzőleg bemutatott Q-learning módszer
diszkrét állapot-akció térre alkalmazható fuzzy modell bevezetésével azonban kiterjeszthető folytonos állapot- és akciótérre
A fuzzy szabály interpoláció alapú Q-tanulás (FRIQ-learning)
az FQ-learning (fuzzy Q-learning) kiegészítése ritka szabálybázisok alkalmazhatósága
FRIQ-learning
A diszkrét Q-learning fuzzy modell alkalmazásával kiterjeszthető folytonos állapot-akció térre Fuzzy Q-learning (FQ-learning)
E.g. 0-order Takagi-Sugeno Fuzzy Inference model
Probléma: a szabályszám exponenciálisan nő az állapot dimenzió (antecedens) számával
Lehetséges megoldás: Fuzzy Rule Interpolation (FRI) FQ-learning + FRI FIVE: FRIQ-learning
FRIQ-learning példák
Nézzünk működő alkalmazásokat : )
Maze Pong
FRIQ-learning példák - Maze
2 állapot leíró
x pozíció: 0-8 y pozíció: 0-5
1 akció: elmozdulás (fel, le, jobbra, balra)
FRIQ-learning példák - Pong
4 állapot leíró labda x pozíció labda y pozíció labda iránya (6 eset) ütő pozíciója 1 akció: elmozdulás (fel, le, semerre)
FRIQ-learning példák
Matlab bemutató : )
Felhasznált irodalom
Richard S. Sutton and Andrew G. Barto – Reinforcement Learning: An Introduction Peter Norvig, Stuart J. Russel – Mesterséges intelligencia – Modern megközelítésben http://project.mit.bme.hu/mi_almanach/books/aima/index
37
Köszönöm a figyelmet!
