Uceci avtomati

Stohastični sistem

Za stohastični sistem je značilno, da posamezen izhod vrača z določeno verjetnostjo.

Stohastični avtomat je avtomat, pri katerem je vsaj ena matrika (matrika prehajanja stanj ali izhodna matrika) stohastična, kar pomeni, da je vsota verjetnosti v eni vrstici enaka 1, posamezni členi matrike pa se nahajajo na intervalu [0,1]. Njegovega delovanja ne moremo natančno napovedati, lahko določimo le verjetnosti zanj.

Relacija med verjetnostmi stanj in akcij pri učečih avtomatih

Naj bo izhodna matrika, pa vektor verjetnosti stanj v času n. Potem je vektor verjetnosti akcij enak:

.

Razlaga enačbe: verjetnost posamezne akcije je vsota produktov verjetnosti posameznega stanja in verjetnosti da to stanje vrača opazovano akcijo.

Zakaj se deterministični avtomati z naključnimi vhodi obnašajo kot stohastični avtomati

Če damo determinističnemu avtomatu na vhod naključno sekvenco, bo prehajanje med stanji avtomata postalo stohastično. Zaradi tega bo avtomat začel izhode vračati stohastično. Stohastičnost tako prenesemo iz okolja na avtomat.

Markovski procesi

To so procesi pri katerih na naslednje stanje vpliva samo trenutno stanje (procesi brez pomnjenja). Tipičen predstavnik markovskih procesov je avtomat. Avtomat pri prehodu v naslednje stanje upošteva le trenutno stanje (in ne preteklih stanj). Prostor stanj diskretnega Markovskega procesa lahko podamo z Markovsko verigo. Ta veriga je homogena, če je verjetnost prehoda med stanjem v času n in stanjem v času m odvisna le od (m-n), torej ne od absolutnega časa.

Ergodičnost

Markovski proces je ergodičen, če deluje v enem samem režimu. Dovolj dolgo opazovanje delovanja procesa nam da vse potrebne statistične podatke - lahko določimo verjetnosti posameznega stanja v limiti. Če je markovski proces ergodičen, vektor verjetnosti stanj konvergira.

Vektor verjetnosti stanj v časovnem koraku, ki sledi, računamo z enačbo:

.

Če je proces ergodičen lahko verjetnosti stanj v limiti določimo z enačbo:

.

Definicija povprečne kazni

Povprečno kazen računamo kot vsoto produktov verjetnosti posameznega akcije in verjetnosti kaznovanja te akcije. Naj bo c_i verjetnost kaznovanja akcije i, p_i(n) pa verjetnost akcije i v časovnem koraku n. Potem je povprečna kazen definirana kot

.

Za računanje povprečne kazni v limiti vzamemo verjetnosti akcij v limiti, torej mora biti proces ergodičen. Vektor verjetnosti akcij v limiti izračunamo z enaćbo

,

kjer je matrika preslikave stanj v akcije, π pa verjetnosti stanj v limiti.

Norme obnašanja:

• avtomat, ki je v limiti boljši od PCA () je prikladen,
• avtomat, katerega povprečna kazen limitira proti minimalni kazni (c_min = min_i(c_i)), ki jo vrača okolje je optimalen,
• če optimalnosti ne moremo doseči, je avtomat sub-optimalen,
• če je povprečna kazen s časom monotono padajoča funkcija, je avtomat absolutno prikladen. Absolutna prikladnost implicira suboptimalnost v vseh stacionarnih naključnih okoljih.

Kako deluje postopek učenja

Učljivi avtomati s fiksno strukturo

Avtomat izvaja akcije, ki so najmanj kaznovane.

Primeri:

• Avtomat L_2,2 spremeni stanje, če je akcija kaznovana in ga ohrani sicer. Stanje vrača vedno isto akcijo - matrika preslikave stanj v akcije je identiteta. Ta avtomat je prikladen.
• Razširjava L_2,2 - vpeljemo parametra γ₁ in γ₂. Prvi parameter zmanjša verjetnost, da ob nagradi ostanemo v istem stanju, drugi pa da ob kazni spremenimo kaznovano stanje. Avtomat je še vedno prikladen, če sta parametra na intervalu [0,0.5).
• Avtomat L_2N,2 ima za vsako izhodno črko N stanj. Avtomat hrani število uspehov. Maskimalna globina - število pomnjenih zaporednih uspehov, je N. Če dosežemo maksimalno globino, bomo spremenili stanje šele po N + 1 zaporednih kaznovanjih. Glej sliko v skripti na strani 25. Avtomat je optimalen, če limitirano N v neskončnost. Vrednosti za M pa dobimo blizu optimalnih že zelo kmalu. Pogoj za suboptimalnost je, da je vsaj ena verjetnost za kaznovanje akcij manjša ali enaka 0.5.
• Avtomat G_2N,2 odpravlja slabost prejšnega, ki lahko povzroči neželjeno menjavanje med akcijami. Ko avtomat dovolj dolgo kaznujemo, da se akcija, ki jo vrača spremeni, gremo v maksimalno globino avtomata. Glej sliko na strani 26. Sicer ima avtomat manjšo prikladnost kot prejšnji, je pa konvergenčna hitrost večja (odvisnost M od koraka n) - v splošnem velja, da se s povečevanjem hitrosti konvergence zmnajšuje natančnost delovanja. Avtomat je še vedno suboptimalen.

Učljivi avtomati s spremenljivo strukturo

Verjetnosti akcij se ažurirajo v vsakem koraku delovanja avtomata glede na neko korekcijsko shemo. Avtomat torej povečuje verjetnost akcije, ki ima najmanjšo verjetnost kazni.

Korekcijske sheme

Korekcijske sheme delujejo po naslednjem principu:

• če avtomat v času n izbere akcijo α_i in temu sledi željeni odziv okolja (0), potem se verjetnost izbrane akcije poveča, verjetnost ostalih pa se zmanjša,
• če akciji sledi kazen, se pri določenih korekcijskih shemah njena verjetnost zmanjša ostalim pa poveča, pri določenih korekcijskih shemah pa ostanejo verjetnosti nespremenjene.

Splošna korekcijska shema

Če je α(n) = α_i

• β = 0
  • , za vse
  • 
• β = 1
  • , za vse
  • 

Veljati mora:

• g in h sta zvezni funkciji,
• g in h sta nenegativni funkciji,
• 0 < g_j(p) < p_j,
• vsota verjetnosti mora biti vedno enaka 1.

Linearna L_{R − P} shema

Uporablja se v nestacionarnih okoljih. Korekcija se izvaja tako v primeru kazni kot v primeru nagrade. Enačbo za shemo dobimo tako, da za korekcijski funkciji vzmamemo:

• g_j(p(n)) = ap_j(n)
• , pri 2 akcijah
• , pri r akcijah

Popravek je v istem velikostnem razredu ().

L_{R − P} je prikladna shema za vsa okolja, razen za tista, kjer so verjetnosti kaznovanja akcij enake. Njena slabost je, da ni tako natančna kot ostale sheme.

Linearna L_{R − εP} shema

Razlika od prejšnje je v tem, da v primeru kaznovanja naredimo minimalno korekcijo, torej je parameter b za velikostni razred manjši od parametra a. Velja: b < < a. Ta shema je suboptimalna.

Linearna L_{R − I} shema

Pri tej shemi v primeru napake ne spreminjamo verjetnosti, torej je b=0. Pri tej shemi imamo absorpcijska stanja, zato shema ni ergodična in ni primerna za nestacionarna okolja. Prednost te sheme je hitrejša konvergenca kot pri ostalih. Ta shema je suboptimalna.

Nelinearne sheme

Ne vem, če nas bo s tem matrou.

Absolutna prikladnost

Absolutno prikladne sheme predstavljajo edini razred shem, za katere so potrebni in zadostni pogoji snovanja poznani. Če je shema absolutno prikladna, to pomeni, da je kazen monotono padajoča funkcija v odvisnosti od časa. Te sheme predstavljajo posplošitev L_{R − I} sheme. Veljati mora: ΔM(n) < 0. Funkciji g in h morata zadoščata pogojem simetrije:

- funkcija nagrade

- funkcija kazni

Splošen zapis absolutno prikladne sheme:

L_{R − I} shemo dobimo, če izenačimo funkcijo kazni z 0.

Nestacionarna okolja

Okolje je nestacionarno, če se verjetnosti kazni, ki ustrezajo posameznim akcijam s časom spreminjajo. Če so spremembe hitre, med njimi pa daljši čas ko ni sprememb, govorimo o etapno različnih stacionarnih okoljih - okolje je sestavljeno iz niza različnih stacionarnih okolij, avtomat preklaplja med shemami, ki so prilagojene posameznemu okolju.

Markovska preklopna okolja

Različna etapna okolja so stanja Markovske verige. Če je veriga ergodična, lahko izračunamo verjetnost posameznega okolja v limiti.

Povprečno kazen v takem okolju lahko izračunamo kot

,

kjer je r število akcij, d število okolji, p_i(n) verjetnost i-te akcije v n-tem časovnem koraku, q_j(n) verjetnost j-tega okolja, c_ij pa verjetnost kaznovanja i-te akcije v okolju E_j.

Avtomat je prikladen, če velja:

,

kjer so q ^* stacionarne verjetnosti okolij. Tako se obnaša PCA v takem okolju.

Stanjsko odvisna okolja

Akcije avtomata vplivajo na odziv okolja (primer: telefonska centrala).

Primer: ob akciji α_i se verjetnsot kazni c_i poveča, ostale pa se zmanjšajo - izvedene akcije se slabšajo, neizvedene pa boljšajo.