Y@SiN
09-13-2009, 08:52 PM
در يک تصمصم گيری شما تعدادی عمل (action) داريد که می تونيد از بين اونا يکی رو انتخاب کنيد. انتخاب بهترين عمل مستلزم دونستن نتايج بعدی اون کار هست و نه فقط نتايج آنی اون. درک نتايج دراز مدت معمولاْ می تونه به تصميم گيری بهتر خيلی کمک کنه. نکته اينجاست که تصميم گيرنده بايد بتونه بين فوايد کوتاه مدت و دراز مدت که لزوماْ باعث تقويت همديگه نمی شن انتخاب کنه. اين مدل به مدل پنهان مارکوف معروفه و هر روز در کارهای روزمره مردم از اون استفاده می کنن.
برای مسائلی به اين شکل راه حل های استانداردی وجود داره که اگه بتونيم اجزای مساله رو به خوبی مدل کنيم به راحتی می تونيم از اونا استفاده کنيم.
اجزای اصلی يک مدل مارکوف عبارتند از:
۱- من کجام؟ (مجموعه حالت ها)
وضعيتی که مساله شما در اون قرار داره حالت اون مساله گفته می شه. در واقع اگه ما تمامی حالت هايی که ممکنه مساله به اون بره رو در نظر بگيريم٬ ميشه مجموعه حالات. مثال: در مساله پيدا کردن يک خونه هدف در يک جدول٬ هر خونه جدول يک حالته
۲- چيکار می تونم بکنم؟ (مجموعه عمل ها)
تصميمی که می تونه گرفته بشه يک عمله. تمامی مجموعه تصميمات قابل اتخاذ مجموعه اعمال رو تشکيل می ده. مثال: در مساله قبلی اعمال رفتن به چپ٬ راست٬ بالا و پايين
۳- اين کارا منو به کجا می رسونه؟ (گذر)
يک گذر ازيک حالت مشخص کننده اينه که يک عمل در اون حالت به چه نتيجه ای (حالت و پاداشی) منجر می شه. يکی از توسيع (extention) هايی که در مورد مدل مارکوف هست اينه که گذرها احتمالاتی باشن. همچنين توسيع ديگه اينه که از يک حالت با يک عمل ممکنه به حالتهای مختلف بريم. مثال: تغيير مختصات در جهت هر يک از اعمال فوق
۳- چی گيرم مياد؟ (ارزش افزوده فوری هر عمل)
برای اينکه بتونيم بين اعمالمون ارزشی برای يکی و ترجيحی برای اون قايل بشيم بايد بتونيم ارزش افزوده ای براش تعيين کنيم. (پاداشی که از هر عمل می گيريم. مثال: برای مساله فوق اگه پاداش هر حرکت ۰.۱- و پاداش خروج از جدول ۰.۵- و پاداش رسيدن به هدف ۱+ گرفته بشه با روش Q-Learning جواب ميده.
*آدم بايد سياست داشته باشه (حل مساله مدل مارکوفی)
حل يک مساله مارکوف سياست حل اون ناميده می شه که برای هر حالت بهترين حالت بعدی رو تعيين ميکنه. در هر حال سياست بصورت يک تابع ارزش (value-function) نشون داده می شه که در هر حالتی بهترين حالت بعدی رو ميشه از روش حساب کرد.
* عوضی نيای
بعضی از مسايل هست که يک گذر بسته به چندين حالت قبليه که ديگه اين جزء مارکوف حساب نميشه و بايد برين يه جای ديگه حلش کنين.
کلاْ يک مساله رو زمانی مارکوفی به حساب ميارن که رسيدن به يک حالت فقط بستگی به حالت قبلی و عمل انجام شده در اون حالت داشته باشه.
برای مسائلی به اين شکل راه حل های استانداردی وجود داره که اگه بتونيم اجزای مساله رو به خوبی مدل کنيم به راحتی می تونيم از اونا استفاده کنيم.
اجزای اصلی يک مدل مارکوف عبارتند از:
۱- من کجام؟ (مجموعه حالت ها)
وضعيتی که مساله شما در اون قرار داره حالت اون مساله گفته می شه. در واقع اگه ما تمامی حالت هايی که ممکنه مساله به اون بره رو در نظر بگيريم٬ ميشه مجموعه حالات. مثال: در مساله پيدا کردن يک خونه هدف در يک جدول٬ هر خونه جدول يک حالته
۲- چيکار می تونم بکنم؟ (مجموعه عمل ها)
تصميمی که می تونه گرفته بشه يک عمله. تمامی مجموعه تصميمات قابل اتخاذ مجموعه اعمال رو تشکيل می ده. مثال: در مساله قبلی اعمال رفتن به چپ٬ راست٬ بالا و پايين
۳- اين کارا منو به کجا می رسونه؟ (گذر)
يک گذر ازيک حالت مشخص کننده اينه که يک عمل در اون حالت به چه نتيجه ای (حالت و پاداشی) منجر می شه. يکی از توسيع (extention) هايی که در مورد مدل مارکوف هست اينه که گذرها احتمالاتی باشن. همچنين توسيع ديگه اينه که از يک حالت با يک عمل ممکنه به حالتهای مختلف بريم. مثال: تغيير مختصات در جهت هر يک از اعمال فوق
۳- چی گيرم مياد؟ (ارزش افزوده فوری هر عمل)
برای اينکه بتونيم بين اعمالمون ارزشی برای يکی و ترجيحی برای اون قايل بشيم بايد بتونيم ارزش افزوده ای براش تعيين کنيم. (پاداشی که از هر عمل می گيريم. مثال: برای مساله فوق اگه پاداش هر حرکت ۰.۱- و پاداش خروج از جدول ۰.۵- و پاداش رسيدن به هدف ۱+ گرفته بشه با روش Q-Learning جواب ميده.
*آدم بايد سياست داشته باشه (حل مساله مدل مارکوفی)
حل يک مساله مارکوف سياست حل اون ناميده می شه که برای هر حالت بهترين حالت بعدی رو تعيين ميکنه. در هر حال سياست بصورت يک تابع ارزش (value-function) نشون داده می شه که در هر حالتی بهترين حالت بعدی رو ميشه از روش حساب کرد.
* عوضی نيای
بعضی از مسايل هست که يک گذر بسته به چندين حالت قبليه که ديگه اين جزء مارکوف حساب نميشه و بايد برين يه جای ديگه حلش کنين.
کلاْ يک مساله رو زمانی مارکوفی به حساب ميارن که رسيدن به يک حالت فقط بستگی به حالت قبلی و عمل انجام شده در اون حالت داشته باشه.