Vanhoja postauksia: Markov decision process

Täysin irrelevantista asiasta tulee joskus mieleen kysymys, joka jää vaivaamaan päätä ja joka helpottaa vasta kun on onnistunut selvittämään vastauksen. Itse tuhasin yhden yön opetellessani mistä on kyse Markov decision prosessissa (MDP) – ja mihin sitä voi käyttää hyödyksi. Tunne oli kieltämättä loistava siinä vaiheessa, kun palaset loksahtivat paikoilleen ja viimein tajusin mistä on kyse.

Perusperiaate on nerokas. MDP on työkalu, jolla voidaan ratkoa esimerkiksi optimaalisia toimintatapoja systeemistä jossa tiedämme eri tilat, siirtymät, niiden todennäköisyydet ja eri tilojen arvostuksen/palkinnot. MDP:ssä lasketaan eri tila+siirtymä+todennäköisyys-yhdistelmille arvot, joiden perusteella on mahdollista valita jokaisessa tilassa paras mahdollinen valinta.

Laskennassa lähdetään liikkeelle ajatuksesta että simuloiden systeemissä liikkuvan agentin elämää laskemme arvoja jokaiselle tilalle – kasvattaen jokaisessa vaiheessa agentin elinikää yhdellä vaiheella, diskontaten tulevat palkinnot (arvon lisäys) – ja laskien nämä yhteen agentin ko. tila/siirtymä-parille keräämään arvoon.

MDP:n nerokkuus on juuri tässä laskennassa, sillä algoritmissa otetaan huomioon ettemme liikkeelle lähtiessä tiedä mikä jokaisen tilan ja valinnan oikea arvo on. Toisinsanoen algoritmissa agentin eliniän kasvaessa opitaan koko ajan lisää systeemistä – ja systeemin simulaatio on valmis, kun agentin keräämä tieto ei enää muuta systeemin tietoja oleellisesti. Simulaation tultua valmiiksi, meidän on helppo valita jokaiselle tilalle se toiminto, jolla on halujemme mukaan esimerkiksi suurin tai pienin arvo.

Allaolevista linkeistä erityisesti tuo Python ohjelma ja tutorial auttoivat ymmärtämään mistä oikeasti asiassa on kysymys, ja varmistumaan siitä että algoritmi myös oikeasti toimii.

http://aima.cs.berkeley.edu/python/mdp.html

http://www.autonlab.org/tutorials/mdp.html

http://www.cs.ualberta.ca/~sutton/book/ebook/the-book.html

http://www.autonlab.org/tutorials/

Nerokasta.

This entry was posted in Uncategorized. Bookmark the permalink.

Vastaa

Täytä tietosi alle tai klikkaa kuvaketta kirjautuaksesi sisään:

WordPress.com-logo

Olet kommentoimassa WordPress.com -tilin nimissä. Log Out / Muuta )

Twitter-kuva

Olet kommentoimassa Twitter -tilin nimissä. Log Out / Muuta )

Facebook-kuva

Olet kommentoimassa Facebook -tilin nimissä. Log Out / Muuta )

Google+ photo

Olet kommentoimassa Google+ -tilin nimissä. Log Out / Muuta )

Muodostetaan yhteyttä palveluun %s