Contoh kehidupan nyata dari Proses Keputusan Markov

20

Saya telah menonton banyak video tutorial dan terlihat sama. Yang ini misalnya: https://www.youtube.com/watch?v=ip4iSMRW5X4

Mereka menjelaskan keadaan, tindakan dan probabilitas yang baik-baik saja. Orang itu menjelaskannya baik-baik saja tetapi sepertinya saya tidak bisa memahami apa yang akan digunakan dalam kehidupan nyata. Saya belum menemukan daftar apa pun. Yang paling umum yang saya lihat adalah catur.

Bisakah itu digunakan untuk memprediksi sesuatu? Kalau begitu apa jenis barangnya? Bisakah ia menemukan pola di antara jumlah data yang tak terbatas? Apa yang bisa dilakukan algoritma ini untuk saya.

Bonus: Ini juga terasa seperti MDP adalah tentang berpindah dari satu negara ke negara lain, apakah ini benar?

Karl Morrison
sumber

Jawaban:

28

Sebuah Proses Keputusan Markov memang harus dilakukan dengan pergi dari satu negara ke negara lain dan terutama digunakan untuk perencanaan dan pengambilan keputusan .

Teori

Mengulang teori dengan cepat, MDP adalah:

MDP=S,SEBUAH,T,R,γ

di mana adalah status, tindakan, probabilitas transisi (yaitu probabilitas untuk berpindah dari satu kondisi ke kondisi lain yang diberikan tindakan), imbalannya (diberikan kondisi tertentu, dan mungkin action), dan adalah faktor diskon yang digunakan untuk mengurangi pentingnya imbalan di masa mendatang.SSEBUAHTPr(s|s,Sebuah)Rγ

Jadi untuk menggunakannya, Anda harus memiliki standar:

  1. Negara : ini dapat merujuk pada misalnya peta kotak dalam robotika, atau misalnya pintu terbuka dan pintu tertutup .
  2. Tindakan : serangkaian tindakan tetap, seperti misalnya pergi ke utara, selatan, timur, dll untuk robot, atau membuka dan menutup pintu.
  3. Probabilitas transisi : probabilitas untuk berpindah dari satu kondisi ke kondisi lain yang diberikan tindakan. Misalnya, berapa probabilitas pintu terbuka jika aksinya terbuka . Di dunia yang sempurna nanti bisa jadi 1.0, tetapi jika itu adalah robot, itu bisa gagal dalam menangani kenop pintu dengan benar. Contoh lain dalam kasus robot yang bergerak adalah aksi utara , yang dalam banyak kasus akan membawanya di sel grid utara, tetapi dalam beberapa kasus bisa bergerak terlalu banyak dan mencapai sel berikutnya misalnya.
  4. Hadiah : ini digunakan untuk memandu perencanaan. Dalam contoh grid, kita mungkin ingin pergi ke sel tertentu, dan hadiahnya akan lebih tinggi jika kita semakin dekat. Dalam kasus contoh pintu, pintu terbuka mungkin memberi hadiah tinggi.

Setelah MDP didefinisikan, kebijakan dapat dipelajari dengan melakukan Iterasi Nilai atau Iterasi Kebijakan yang menghitung imbalan yang diharapkan untuk masing-masing negara. The kebijakan kemudian memberikan per negara terbaik (diberikan model MDP) tindakan untuk melakukan.

Singkatnya, MDP berguna ketika Anda ingin merencanakan urutan tindakan yang efisien di mana tindakan Anda tidak selalu 100% efektif.

Pertanyaan Anda

Bisakah itu digunakan untuk memprediksi sesuatu?

Saya akan menyebutnya perencanaan, bukan memprediksi seperti regresi misalnya.

Kalau begitu apa jenis barangnya?

Lihat contoh .

Bisakah ia menemukan pola di antara jumlah data yang tak terbatas?

MDP digunakan untuk melakukan Penguatan Pembelajaran , untuk menemukan pola yang Anda butuhkan Pembelajaran Tanpa Pengawasan . Dan tidak, Anda tidak dapat menangani jumlah data yang tak terbatas. Sebenarnya, kompleksitas menemukan kebijakan tumbuh secara eksponensial dengan jumlah negara.|S|

Apa yang bisa dilakukan algoritma ini untuk saya.

Lihat contoh .

Contoh Aplikasi MDP

Dan ada beberapa model lagi. Model yang bahkan lebih menarik adalah Proses Keputusan Markovian yang Dapat Diobservasi Sebagian di mana negara bagian tidak sepenuhnya terlihat, dan sebaliknya, pengamatan digunakan untuk mendapatkan gambaran tentang keadaan saat ini, tetapi ini di luar ruang lingkup pertanyaan ini.

informasi tambahan

Proses stokastik adalah Markovian (atau memiliki properti Markov) jika distribusi probabilitas bersyarat dari keadaan masa depan hanya bergantung pada keadaan saat ini, dan bukan pada yang sebelumnya (yaitu tidak pada daftar keadaan sebelumnya).

agold
sumber
2
Ini mungkin jawaban yang paling jelas yang pernah saya lihat di Cross Validated.
Hidden Markov Model
Apakah ada peluang Anda dapat memperbaiki tautan? Beberapa dari mereka tampak rusak atau ketinggalan jaman.
ComputerScientist
Jadi setiap proses yang memiliki states, actions, transition probabilitiesdan rewardsdidefinisikan akan disebut sebagai Markov?
Suhail Gupta