Zpětnovazební učení

Zpětnovazební učení je technika strojového učení pomocí zpětné vazby.^[1] Po celý svůj život dostáváme ze svého okolí nepřetržitě zpětnou vazbu. Často ji ale sami neregistrujeme a naše budoucí chování pak není ovlivněno, protože jsme mezi své zkušenosti a znalosti nepřidali informace získané zpětnou vazbou. Kritickým faktorem zpětnovazebního učení je tedy uvědomění zpětné vazby. V praxi se k tomu využívá často lektor, který nám zpětnou vazbu pomůže identifikovat,nebo nám ji podá.

Vlastnosti zpětné vazby a informací ve vztahu k učení

• Objektivní zpětná vazba – na základě objektivity zpětné vazby nevznikají při učení pochyby. jak naše chování ovlivnit.
• Subjektivní zpětná vazba – vznikají pochyby, zda zpětná vazba má patřičný význam, důležitost či pravdivost.

• Intrizitivní informace – vlastní. neboli vnitřní proprioceptivní (zrak, sluch);
• Extrinzitivní informace – vnější. neboli exteroceptivní (poskytnutí zpětné vazby druhým člověkem, nebo záznamem na videu)

Zpětnovazební učení v agentních systémech

Inspirováno behavioristy psychologie. Zpětnovazební (zesilující) učení je oblast informatiky tykající se chování agentů. Agenti jsou umísťování do nějakého prostředí a jejich cílem je naučit se chovat tak, aby bylo dosaženo maximálního užitku. U řady komplexních prostředí je to jediný efektivní způsob, jak navrhovat agenty a jejich funkce. Díky své obecnosti je zohledňován v mnoha dalších oborech, jako je například teorie řízení, operační výzkum, teorie informace, simulačně založené optimalizace, statistiky a genetické algoritmy. Operační výzkum a kontrola literatury jsou oblasti, kde metody zpětnovazebního učení se odrážejí především v dynamickém programování. Zpětnovazební učení je tak jedním ze základních východisek umělé inteligence. V operativním výzkumu a řízení existují oblasti jejichž zkoumání se nazývá aproximační dynamické programování a jež přináší problém výzkumu v teorii optimálního řízení. Většina existujících studií se zabývá existencí optimálních řešení a jejich charakterizace ale již se nezabývá zpětnovazebním učením nebo jejich aproximačních aspektů. V ekonomice a teorii her je zpětnovazební učení často spojováno s vysvětlením na základě rovnováhy omezené racionality. Ve strojovém učení je prostředí obvykle formulována jako Markovův rozhodovací proces a mnoho algoritmů zpětnovazebního učení se díky této souvislosti vztahuje k technikám dynamického programování.

Model zpětnovazebního učení se většinou skládá:

1. množiny stavů prostředí ${\displaystyle S}$
2. množiny možných akcí ${\displaystyle A}$
3. pravidel přechodových funkcí
4. pravidla, která určují bezprostřední odměnu přechodu do jiného stavu
5. pravidla, definují cíle agenta

Pravidla jsou často stochastická. Pozorování často zahrnují bezprostřední odměna spojenou s posledním přechodem z jednoho stavu do druhého. V závislosti na možnosti zkoumání aktuálního stavu životního prostředí někdy případě hovoříme o plné pozorovatelnosti, zatímco v druhém případě hovoříme o částečné pozorovatelnosti. Soubor akcí které má agent k dispozici může být omezen omezena (např., nemůže utratit více peněz, než má).

Se svým prostředím reaguje agent v diskrétním čase. A v každém kroku ${\displaystyle t}$ získá agent informace o prostředí či situaci ${\displaystyle o_{t}}$,které často obsahují hodnotu užitku.${\displaystyle r_{t}}$. Následně provede volbu akce ${\displaystyle a_{t}}$ z množiny přípustných akcí a po jejím provedení je tato akce zaslána do prostředí. Prostředí se tak dostává do nového stavu ${\displaystyle s_{t+1}}$ s užitkem ${\displaystyle r_{t+1}}$ spojeným s přechodem ${\displaystyle (s_{t},a_{t},s_{t+1})}$. Cílem zpětnovazebního učení agentů je získat co největší užitek.

Síla zpětnovazebního učení je dána především díky použití vzorků k optimalizaci výkonu a aproximaci chování ve velkých prostředích. Díky těmto dvěma klíčovými vlastnostem, může být zpětnovazební učení použito ve velkých prostředích za některý z následujících situací:

• Model životního prostředí je známý, ale analytické řešení není k dispozici
• Je uveden pouze simulační model životního prostředí
• Jediný způsob, jak sbírat informace o životním prostředí je interakcí s ním.

První dva z těchto případů, je možné považovat za problémy při plánování. Nicméně podle metodiky zpětnovazebního učení metodiky mohou být převedeny do problémů strojového učení. Poslední zmíněný případ by mohl být považován za skutečný problém při učení.

Algoritmy zpětnovazebního učení

Neberou v úvahu pozorovatelnost prostředí a to i v případě,kdy byl stav pozorovatelný. Problémem zůstává na základě minulých zkušeností zjistit, jaké akce jsou dobré. Mezi nejznámější algoritmy patří:

• Kritérium optimality (Criterion of optimality)
  • Algoritmus jenž stanovuje vlastnosti(parametry) kritérii optimálních rozhodnutí, zužující výběr následující akce.
• Hrubá síla (Brute force)
  • Skládá se ze dvou hlavních kroků:
    • Pro každou možnou strategii zjisti její užitek
    • Zvol strategii s největším užitkem
  • Velkou nevýhodou této metody je, že počet strategií může být extrémně velký nebo také nekonečný.
• Přístup založený na užitkových funkcích (Value function approaches)
  • Přístup založený na užitkové funkci.
• Metody Monte Carlo
  • Založen na ohodnocování stavů metodou Monte Carlo.
• Temporální diference (Temporal difference methods)
• Přímé hledání strategie (Direct policy search)

Zpětnovazební učení a umělá inteligence

Zpětnovazební učení je také jedním ze základních stavebních kamenů umělé inteligence. Při zpětnovazebném učení agentů dva základní přístupy. Prvním je pasivní učení a druhým aktivní.

Pasivní učení

Je takové učení, kde je pevně dána strategie a učení je založeno na užitku z dosahovaných stavů a vykonaných akcí. Při procesu učení je tady cílem ohodnotit kvalitu zvolené strategie na základě očekávaného užitku. Protože však ale agent nezná přechodový model a ani užitkovou funkci, snaží se procházet prostředím za použití dané strategie a v každém stavu pak získá ocenění stavu formou vlastního vjemu.

Přímý model

Založen na principu (reward-to-go). Pro stavy v každém vzorku vypočte ocenění stavů cesty od počátku do cíle. Protože jeden stav se může vyskytovat ve více vzorcích, ohodnotíme stav tak uděláme průměr ocenění cest. V podstatě se jedná o učení s učitelem, kdy vstupem jsou všechny stavy a výstupem je očekávaný užitek. Hlavním problémem je, že stavy oceňujeme jako kdyby byly nezávislé, ale mezi stavy je vztah daný Bellmanovými rovnicemi. π(s) = R(s) + γ Σ P(s‘|s, π (s)) U π(s‘) V přímém modelu pak prohledáváme zbytečně velký prostor hypotéz (i ty hypotézy, které nesplňují Bellmanovy rovnice) a tím je dosaženo pomalejší konvergence k optimální strategii.

Adaptivní dynamické programování pro pasivní učení

Založeno na tom, že oproti přímému modelu bere navíc v úvahu Bellmanovy rovnice. Užitek se z Bellmanových rovnic dopočítává například iterací hodnot nebo strategií.

Temporální diference

Přístup založený na úpravě hodnot stavů. Místo učení se přechodové tabulky, přímo provádíme úpravy užitku jednotlivých stavů tak, aby odpovídal Bellmanovým rovnicím.

Adaptivní dynamické programování vs Temporální diference

Adaptivní dynamické programování i temporální diference provádějí lokální změny tak, aby užitek daného stavu odpovídal užitku okolních stavů. Hlavní rozdíly jsou následující:

Temporální diference:

• nepotřebuje přechodový model
• pro update používá pozorovaného následníka
• v kroku dělá jedinou změnu

Adaptivní dynamické programování:

• pro update používá všechny následníky
• změnu propaguje, aby byla udržena konzistence

Aktivní učení

Při výše zmíněném pasivním učení je předem dána strategie určující chování agenta. U aktivního učení se agent učí (učí se strategii) co má dělat a zkoumá k tomu prostředí. Aktivní agent se sám rozhoduje, jaké akce provede (a tím určuje i strategii).

Hladový agent

Rozšířením pasivního agenta adaptivního dynamického programování o model přechodů dostaneme tzv. hladového agenta. Protože užitek je definován optimální strategií danou dle Bellmanových rovnic

Uπ(s) = R(s) + γ max Σs‘ P(s‘|s, a) Uπ(s‘)

následně pak můžeme přímo použít ve funkci výpočtu užitku v adaptivního dynamického programování. Obecně tak v každém kroku agent provádí následující:

• na základě vypočteného užitku U zvolí nejlepší akci
• vykoná akci doporučenou optimální strategií
• Ověří zda neexistuje nějaká lepšího varianta

To že není jisté zda agent nalezne optimální strategii je dáno následujícími vlastnostmi:

• Důvody proč výběr optimální akce nedává optimální strategii
  • akce je vybrána podle naučeného prostředí ne podle skutečného prostředí
  • akce přispívá nejen do funkce užitku, ale také do zdokonalení modelu světa (tento aspekt ADP agent ignoroval)
  • zlepšením modelu můžeme v budoucnu získat větší užitek než ten ,který se v současném prostředí jeví jako nejlepší
• Agent potřebuje do jisté míry dělat průzkum prostředí.

Aspekty průzkumu prostředí

• Poměr mezi průzkumem prostředí a jeho využitím
  • Čistý průzkum zlepšuje model, ale model se nikdy nevyužije
  • Čisté využití vede k sub-optimální strategii
• Základní princip
  • Zpočátku je lepší více prozkoumávat prostředí s vírou v nalezení lepších cest
  • S větším porozuměním prostředí stačí menší průzkum
• Problém n-rukého bandity
  • herní automat s n-pákami (nebo n automatů)
  • Jakou páku preferovat?
    • páku, kde už jsem někdy vyhrál (ale málo) nebo raději páku,kterou jsem ještě nezkoušel?

Q-učení

Q-učení je technika zpětnovazebního učení založená na užitkové funkci pro nějakou akci, která dává očekávaný užitek provedení dané akce v daném stavu a pro pevné dané politiky. Jednou ze silných stránek Q-učení je schopnost porovnat očekávaný užitek z dostupných akcí bez nutnosti znalosti modelu prostředí. Varianta tzv. zpožděné Q-learning dosahuje mnohem lepších výsledků, a tím se ukazuje jako vhodné učení pro markovské rozhodovací procesy.

Algoritmus

Model problému je dán stavy S a souborem akcí za daného stavu A. Provedením akce ${\displaystyle a\in A}$, může agent přecházet z jednoho stavu do jiného. Každý stav poskytuje agentovi užitek (celé nebo přirozené číslo). Cílem agenta je maximalizovat jeho celkový užitek tak že, se učí, která akce je optimální pro daný stav.

Algoritmus tedy nutně obsahuje funkci, která vypočítá užitek z kombinace stav a akce:

• ${\displaystyle Q:S\times A\to \mathbb {R} }$

Před začátkem učení Q vrací konstantní hodnotu. V každém kroku algoritmu je agentovi dána nová hodnota, vypočtená ze všech kombinací stavů s z množiny S a akcí a z množiny akcí A. Jádrem algoritmu jsou pak staré hodnoty opravovány na základě nových informací.

• ${\displaystyle Q(s_{t},a_{t})\leftarrow \underbrace {Q(s_{t},a_{t})} _{\rm {old~value}}+\underbrace {\alpha _{t}(s_{t},a_{t})} _{\rm {learning~rate}}\times \left[\overbrace {\underbrace {R(s_{t+1})} _{\rm {reward}}+\underbrace {\gamma } _{\rm {discount~factor}}\underbrace {\max _{a}Q(s_{t+1},a)} _{\rm {max~future~value}}} ^{\rm {expected~discounted~reward}}-\overbrace {Q(s_{t},a_{t})} ^{\rm {old~value}}\right]}$

Kde ${\displaystyle R(s_{t+1})}$ je užitek objevený ve stavu ${\displaystyle s_{t+1}}$. Koeficient ${\displaystyle \alpha _{t}(s,a)}$ (${\displaystyle 0<\alpha \leq 1}$) je rychlost učení, často je stejná pro všechny kombinace anebo se snižuje s časem. Konstanta ${\displaystyle \gamma }$ (na obr. discount factor, česky asi koeficient znehodnocení nebo faktor stárnutí) je v rozmezí ${\displaystyle 0\leq \gamma <1}$.

Výše uvedený vzorec tedy odpovídá:

• ${\displaystyle Q(s_{t},a_{t})\leftarrow Q(s_{t},a_{t})(1-\alpha _{t}(s_{t},a_{t}))+\alpha _{t}(s_{t},a_{t})[R(s_{t+1})+\gamma \max _{a}Q(s_{t+1},a)]}$

Každý krok algoritmu končí ve stavu ${\displaystyle s_{t+1}}$, který je stavem koncovým pro daný krok.

SARSA (State-Action-Reward-State-Action)

Je velmi blízký způsob aktivního učení příbuzný Q-učení s následujícím updatovacím pravidlem: Q(s,a) ← Q(s,a) + α (R(s) + γ Q(s‘,a‘) - Q(s,a)) kde použije celou pětici (s,a,r,s‘,a‘) což znamená že, pro update se čeká na další akci.

SARSA vs. Q-učení

Pro hladového agenta jsou Q-učení a SARSA totožné (vybere vždy akci a‘ maximalizující Q(s‘,a‘). Při průzkumu se výrazně liší v tom, že Q-učení se nestará o aktuální strategii a agent funguje dobře i s náhodnou strategií. Naopak SARSA je realističtější, protože se učí Q-funkci na základě toho,co se skutečně stalo, ne co by se mohlo stát a naučí se i reakci na další agenty.

Reference

V tomto článku byl použit překlad textu z článku Reinforcement learning na anglické Wikipedii.

Literatura

• Linhart, Josef. Základy psychologie učení. 1. vyd. Praha : SPN, 1982. 249 s.
• Barták, Roman. Přednáška z předmětu Umělá inteligence II na MFF UK.

Externí odkazy

• Obrázky, zvuky či videa k tématu zpětnovazební učení na Wikimedia Commons