Vis kilden til Q-læring

'''Q-læring''' er en [[algoritme]] som brukes i [[kunstig intelligens]] og [[maskinlæring]], mer spesifikt [[forsterkende læring]], til å lære en [[Programvareagent|agent]] handling-nytte-funksjonen, som gir informasjon om nytteverdien til en gitt handling i en gitt tilstand i et delvis eller helt ukjent miljø. Handlingen som gir den høyeste verdien til denne funksjonen representerer en regel som agenten skal følge neste gang den havner i samme tilstand. Denne regelen kalles en politikk (eng. ''policy''). Når en slik handling-nytte verdi er lært, kan den optimale politikken konstrueres ved å velge handlingen som gir høyest nytteverdi i hver tilstand på vei mot målet. En av Q-lærings styrker er at teknikken er i stand til å sammenligne forventet nytte av de handlingene som er tilgjengelig, uten kunnskap om miljøet. I tillegg kan algoritmen håndtere problemer med [[Stokastisitet|stokastiske]] overganger og belønninger, uten å kreve noen tilpasninger. 

== Algoritmen ==

=== Introduksjon ===
   
Problemmodellen, kalt ''Markov Decision Process'' (MDP), består av en agent, tilstander <math>S</math> og et sett med tilgjengelige handlinger <math>A</math> ved hver tilstand. Agenten kan endre tilstand ved å utføre en handling <math>a \in A</math>. Ved å utføre en handling i en spesifikk tilstand blir agenten belønnet med en verdi (et [[Reelt tall|reelt]] eller [[Naturlig tall|naturlig]] tall). Målet for agenten er å maksimere dens totale belønning. Dette gjøres ved å lære hvilken handling som er optimal for hver tilstand. Denne læringsprosessen benytter et estimat for total belønning av alle fremtidige handlingsvalg fra gjeldende tilstand, ikke bare den umiddelbare belønningen agenten får ved valgt handling i tilstanden den er i.  
 
Algoritmen har derfor en funksjon som kalkulerer kvaliteten (eng. ''Quality'') av en kombinasjon av tilstand og handling: 
 
:<math>Q: S \times A \to \mathbb{R}</math>

=== Definisjon ===

Før læringsprosessen starter, returnerer ''Q'' en tilfeldig verdi. Deretter velger agenten en handling, og observerer en belønning og en ny tilstand som kan påvirkes av forrige tilstand og den valgte handlingen. Algoritmens kjerne er en enkel oppdatering av verdier den returnerer av gitte tilstander og handlinger. Den betrakter den gamle verdien og utfører en korrigering basert på den nye informasjonen: 
 
:<math>Q_{t+1}(s_{t},a_{t}) = \underbrace{Q_t(s_t,a_t)}_{\rm gammel~verdi} + \underbrace{\alpha_t(s_t,a_t)}_{\rm learning~verdi} \times \left[ \overbrace{\underbrace{R_{t+1}}_{\rm reward} + \underbrace{\gamma}_{\rm diskonteringsfaktor} \underbrace{\max_{a}Q_t(s_{t+1}, a_t)}_{\rm estimat~av~optimal~fremtidig~verdi}}^{\rm learned~verdi} - \underbrace{Q_t(s_t,a_t)}_{\rm gammel~verdi} \right]</math>
 
der ''<math>R_{t+1}</math>'' er den observerte belønningen etter å ha utført handling <math>a_{t}</math> i tilstand <math>s_{t}</math>, og der <math>\alpha_t(s, a)</math> (<math>0 < \alpha \le 1</math>) er læringssraten som gir informasjon om hvor stor grad den nye informasjonen skal overskrive den gamle informasjonen. Læringsraten kan være identisk for alle par i læringsprosessen. Diskonteringsfaktoren (eng. ''Discount factor'') <math>\gamma</math> (<math>0 \le \gamma \le 1</math>) gir informasjon om viktigheten av fremtidige belønninger. 
 
En gjennomkjøring (kalt ''episode'') av algoritmen ender når tilstanden <math>s_{t+1}</math> er i måltilstanden. 

=== Formell beskrivelse === 

    Gitt: Tilstandsdiagram med et mål tilstand (representert ved matrise R)
    Finn: Minste sti fra enhver opprinnelige tilstand til måltilstand (representert ved matrisen Q)
    Fremgangsmåte:
    1. Sett parameter γ og miljøbelønning matrise R
    2. Initialiser matrise Q som nullmatrise
    3. For hver episode:
    Velg en tilfeldig opprinnelig tilstand
    Gjør mens måltilstand ikke er nådd
    Velg ett blant alle mulige tiltak for den nåværende tilstanden
    Bruke denne mulige handlingen, vurder å gå til neste tilstand
    Få maks Q-verdi av denne neste stat basert på alle mulige tiltak
    Q (stat, action) = R (stat, action) + γ * Max [Q (neste tilstand, handlinger)]
    Sett neste tilstand som den nåværende tilstand

== Algoritmens variabler ==         
 
=== Læringsrate ===
[[Læringsrate]]n bestemmer i hvor stor grad den nye tilegnede informasjonen skal erstatte den gamle informasjonen, og er <math>0 < \alpha \le 1</math>. Dersom raten <math>\alpha = 0</math>, skal ingenting av den nye versjonen erstatte den gamle, og agenten har derfor ikke lært noe. Derimot, dersom <math>\alpha = 1</math>, skal all gammel informasjon erstattes av den nye, og agenten har da fått maksimalt læringsutbytte. Derfor er en læringsrate på 1 optimal i fullt deterministiske miljøer. I praksis er vanligvis en læringsrate av en konstant verdi benyttet, for eksempel <math>\alpha_t(s,a) = 0.1</math> for alle <math>t</math>.<ref>[http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html Reinforcement Learning: An Introduction]  {{Wayback|url=http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html |date=20090904194934 }}. Richard Sutton and Andrew Barto. MIT Press, 1998.</ref>

=== Diskonteringsfaktor ===

Diskonteringsfaktoren <math>\gamma</math> bestemmer viktigheten av fremtidige belønninger. Dersom <math>\gamma = 0</math> vil agenten ha en oppførsel liknende en [[grådig algoritme]], hvor kun de umiddelbare belønningene evalueres i bestemmelse av optimal handling i en tilstand. Derimot, dersom <math>\gamma = 1</math>, vil agenten heller ønske en maksimal langsiktig total belønning. Dersom dette er tilfellet, og agenten ikke befinner seg i et miljø med en terminaltilstand (sluttilstand), eller at agenten aldri når en slik tilstand, vil alle episoder av algoritmen være uendelig lange. Dette fordi agenten får høyere belønning jo flere tilstander den besøker.

=== Initielle forhold === 

Når algoritmen først starter, har ikke den lært noe. Derfor må Q-learning ha noen initielle verdier å benytte i de første kalkuleringene. Den forventer et initielt forhold før den første oppdateringen foretas. Et høyt initielt forhold fremmer utforskning: uansett hvilken handling som foretas, vil den nye kalkulerte verdien av Q-funksjonen erstatte gammel informasjon. Dermed, første gang en handling blir gjort, vil belønningen bli brukt til å sette den nye verdien til <math>Q</math>.<ref>{{cite book|author1=[[Stuart J. Russell]]|author2=[[Peter Norvig]]|title=Artificial Intelligence: A Modern Approach|date=2010|publisher=[[Prentice Hall]]|isbn=978-0136042594|page=649|edition=Third|url=http://51lica.com/wp-content/uploads/2012/05/Artificial-Intelligence-A-Modern-Approach-3rd-Edition.pdf|accessdate=17. oktober 2014|url-status=dead|archiveurl=https://web.archive.org/web/20141020191456/http://51lica.com/wp-content/uploads/2012/05/Artificial-Intelligence-A-Modern-Approach-3rd-Edition.pdf|archivedate=2014-10-20|tittel=Arkivert kopi|besøksdato=2014-10-17|arkivurl=https://web.archive.org/web/20141020191456/http://51lica.com/wp-content/uploads/2012/05/Artificial-Intelligence-A-Modern-Approach-3rd-Edition.pdf|arkivdato=2014-10-20|url-status=død}} {{Kilde www |url=http://51lica.com/wp-content/uploads/2012/05/Artificial-Intelligence-A-Modern-Approach-3rd-Edition.pdf |tittel=Arkivert kopi |besøksdato=2014-11-06 |arkiv-dato=2014-10-20 |arkiv-url=https://web.archive.org/web/20141020191456/http://51lica.com/wp-content/uploads/2012/05/Artificial-Intelligence-A-Modern-Approach-3rd-Edition.pdf |url-status=unfit }}</ref>

== Implementasjon ==

En enkel implementasjon av Q-learning algoritmen benytter tabeller for å lagre data. Problemet med denne tilnærmingen er raskt tap av levedyktighet med økning av [[Kompleksitetsteori|kompleksiteten]] til systemet den kontrollerer. En løsning er å bruke et [[nevralt nettverk]] som en funksjonsapproksimator. Mer generelt kan Q-learning kombineres med funksjonsapproksimering. Dette gjør det mulig å anvende algoritmen til større problemer, som for eksempel [[NP-komplett|NP-komplette]] problemer med [[Eksponentiell vekst|eksponentiell kjøretid]]. Samtidig kan den forbedre hastigheten til problemer med [[Polynom|polynomisk]] kjøretid, grunnet algoritmens evne til å generalisere tidligere erfaringer til tidligere usette tilstander.<ref>[http://www.ncbi.nlm.nih.gov/pubmed/22924882 The Role of First Impression in Operant Learning. Shteingart H, Neiman T, Loewenstein Y. J Exp Psychol Gen. 2013 May; 142(2):476-88. doi: 10.1037/a0029550. Epub 2012 Aug 27.]</ref> 
 
== Eksempel ==

[[Fil:Q-læring eksempel med løsning.png|miniatyr|Eksempel på et miljø etter utforsking. Ved algoritmens start var inngangene til rommene merket med 0, grunnet agentens mangel på kunnskap om miljøet. Unntakene er innganger og utganger i tilstand G.]]
 
Miljøet i figuren betraktes. Miljøet består av seks rom, hvor hvert av rommene har innganger til alle motstående naborom. Hver av disse inngangene har blitt tildelt samme initielle verdi. Denne verdien er satt til 0 fordi agenten som skal orientere seg i miljøet i starten av algoritmen ikke enda har lært noe om hvilke innganger som er mest gunstig å velge i et rom for å raskest nå terminaltilstanden G. Målet er å tildele hver av disse inngangene/utgangene en verdi som gir informasjon om hvor gunstig det er å velge akkurat den inngangen i et rom, i prosessen av å nå målet G ved færrest mulige besøk av rom. I dette eksempelet benytter vi diskonteringsfaktoren <math>\gamma = 0.8</math>. 
 
Algoritmen tar i bruk verdier definert i en matrise <math>R</math>, som for hver tilstand <math>S</math><sub>y</sub> gir informasjon om den umiddelbare belønningen agenten får ved å velge handling <math>H</math> og deretter havne i tilstand <math>S</math><sub>x</sub> (i dette tilfellet ved å velge inngang til et rom). Rom som ikke er forbundet med en inngang/utgang tildeles den tomme verdien <math>-</math>. 

:<math>
R = \begin{pmatrix}    
    - & 0 & 0 & - & - & - \\
    0 & - & - & 0 & - & 100 \\
    0 & - & - & 0 & - & - \\
    - & 0 & 0 & - & 0 & - \\
    - & - & - & 0 & - & 100 \\
    - & - & - & - & - & 100 \\
  \end{pmatrix} 
</math>

Under læringsprosessen skal algoritmen oppdatere og korrigere Q-verdiene som er tildelt hver handling <math>H</math> tilgjengelig i hver tilstand <math>S</math>. Disse verdiene lagres i en matrisen <math>Q</math>, som gir informasjon om nyttigheten av å velge en bestemt handling i en bestemt tilstand.  
 
For hver tilstand, kalkulerer algoritmen Q-verdien av å velge handling <math>A</math> i tilstand <math>S</math>: 

:<math>Q(S,A) = R(S,A) + {\gamma} * {\max\left[ Q(neste S, alle A) \right]}</math>
 
Grunnet det faktum at Q-læring benytter sin egen definisjon i kalkuleringene, gjør algoritmen [[Rekursjon|rekursiv]]. Dette betyr at for å kalkulere en Q-verdi av handlingen <math>H</math> i en tilstand <math>S</math>, må først de nødvendige Q-verdier tilhørende fremtidige tilstander kalkuleres. Algoritmen starter i en tilfeldig rom <math>S</math> og kalkulerer Q-verdien av å velge alle tilgjengelige utgangene fra dette rommet etter tur. Deretter kalkuleres Q-verdien av valg av utganger fra disse rommene. Denne prosessen gjentas helt til agenten er i rommet representert av terminaltilstanden (målet) G.  
 
For illustrative formål, er det nyttig å observere en metode for kalkulering av Q-verdiene til utganger tilhørende et rom raskest mulig. Da plasseres agenten først i tilstanden <math>S = G</math> og Q-verdien til dette rommet kalkuleres. Deretter kalkuleres verdien til rommene <math>S = S2</math> og <math>S = S5</math>, så verdien tilhørende rommene som er naboene til <math>S2</math> og <math>S5</math>. Denne prosessen fortsetter helt til alle innganger har blitt tildelt en verdi som forblir uendret ved videre utforsking. Nytteverdien av å velge inngangen til rom <math>S</math><sub>y</sub> fra et rom <math>S</math><sub>x</sub> er definert i matrisen <math>Q</math>:

:<math>
Q = \begin{pmatrix}    
    0 & 80 & 51.2 & 0 & 0 & 0 \\
    64 & 0 & 0 & 64 & 0 & 100 \\
    64 & 0 & 0 & 64 & 0 & 0 \\
    0 & 80 & 51.2 & 0 & 80 & 0 \\
    0 & 0 & 0 & 64 & 0 & 100 \\
    0 & 0 & 0 & 0 & 0 & 100 \\
  \end{pmatrix} 
</math> 
 
Algoritmens læringsprosess er nå fullført, og algoritmen avslutter. Ved å benytte verdiene gitt i matrise <math>Q</math>, kan agenten nå i et rom observere Q-verdiene tilhørende hver inngang gitt i matrisen <math>Q</math>, og enkelt velge den utgangen med høyest verdi. Det er nettopp denne utgangen som bringer agenten raskest målet <math>S = G</math>. Dersom to eller flere utganger har samme Q-verdi, bringer de agenten til målet like raskt, og agenten kan da tilfeldig velge én av disse.

== Referanser ==
<references/>

== Eksterne lenker ==
* [http://www.cs.rhul.ac.uk/~chrisw/thesis.html Watkins, C.J.C.H. (1989). Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England.]
* [http://portal.acm.org/citation.cfm?id=1143955 Strehl, Li, Wiewiora, Langford, Littman (2006). PAC model-free reinforcement learning]
* [https://web.archive.org/web/20090904160457/http://www.cs.ualberta.ca/~sutton/book/the-book.html ''Reinforcement Learning: An Introduction''] by Richard Sutton and Andrew S. Barto, an online textbook. See [https://web.archive.org/web/20081202105235/http://www.cs.ualberta.ca/~sutton/book/ebook/node65.html "6.5 Q-Learning: Off-Policy TD Control"].
* [http://sourceforge.net/projects/piqle/ Piqle: a Generic Java Platform for Reinforcement Learning]
* [http://ccl.northwestern.edu/netlogo/models/community/Reinforcement%20Learning%20Maze Reinforcement Learning Maze] {{Wayback|url=http://ccl.northwestern.edu/netlogo/models/community/Reinforcement%20Learning%20Maze |date=20110927003442 }}, a demonstration of guiding an ant through a maze using Q-learning.
* [http://www.research.ibm.com/infoecon/paps/html/ijcai99_qnn/node4.html Q-learning work by Gerald Tesauro]
* [https://web.archive.org/web/20080529074412/http://citeseer.comp.nus.edu.sg/352693.html Q-learning work by Tesauro Citeseer Link]
* [http://github.com/sandropaganotti/processing.org-q-learning-td-lambda-/tree/master Q-learning algorithm implemented in processing.org language]
* [http://toki.burn3r.de/html5-projects/cityfighter-for-html5.html Q-learning with lambda and a feed-forward-neural-net implementation in JavaScript for a martial arts game]{{død lenke|dato=august 2017 |bot=InternetArchiveBot }}

{{Autoritetsdata}}

[[Kategori:Algoritmer]]