بخشی از مقاله
چکیده
تجرید حالت روشی قدرتمند برای مدیریت زمان و حافظه در یادگیری تقویتی هست. در رویکردهای قدیمی این روش برای افزایش سرعت یادگیری وظیفه فعلی مورد استفاده قرار می گیرد. در بیشتر این موارد، هزینه یافتن تجرید
مناسب و سپس بهره گیری از آن در برابر سود حاصله مقرون به صرفه نیست. با این وجود، وقتی قرار است چندین محیط مشابه از یک حوزه یاد گرفته شوند، از این روش برای بهبود یادگیری در وظایفِ دیگرِ حوزه و در نتیجه افزایش سود در برابر هزینه می توان بهره برد. در این مقاله یک فرمول بندی برای شناسایی متغیرهای حالت که در بیشتر وظایف حوزه تأثیری در یادگیری ندارند ارائه می شود تا با حذف آن ها در وظایف بعدی، سرعت یادگیری با پذیرش خطایی کنترل شده افزایش یابد.
مقدمه
یادگیری انتقال دانش به معنای بهره گیری از دانش یاد گرفته شده در وظایف مبدأ جهت بهبود یادگیری در وظایف هدف مرتبط، اما متفاوت است. در برخی از تحقیقات تلاش شده است تا با انتقال تجرید حالت به سایر وظایف بر مشکلات تجرید حالت سنتی غلبه شود و بدین ترتیب هزینه کشف وظیفه مبدأ با سود حاصله بیشتر جبران گردد.
والش و همکاران ]۴[ تلاش کرده اند تا از دانش حاصل از تعداد زیادی از وظایف از قبل یاد گرفته شده از حوزه وظایف بهره برده و با استفاده از این دانش اولیه فرایند تجرید در وظایف بعدی را سرعت ببخشند. نویسندگان یک مدل بسیار مفید و انعطاف پذیر به نام الگوریتم عمومی انتقال تجرید GATA ارائه داده اند و آن را با مقداری بحث های تئوری پشتیبانی کرده اند. با این وجود، مبانی تئوری و آزمایش های تجربی ارائه شده ناکافی و بسیار ابتدایی است. در این مقاله مدل GATA توسعه داده می شود و مبانی تئوری لازم نیز ارائه می گردد.
یک حوزه چندوظیفه ای را در نظر بگیرید بهگونه ای که تمام وظایف متعلق به یک توزیع D بوده و تمام آن ها فرایندهای مارکوف فاکتور شده با مجموعه متغیرهای حالت و مجموعه اعمال کاملا یکسان اما توابع پاداش و گذر دلخواه باشند. اگر به تعداد m فرایند مارکوف نمونه از Dقبلا حل شده باشند و سیاست های بهینه یا مقادیر ارزش بهینه آن ها به دست آمده باشند، می توان از این دانش حاصل از مجموعه نمونه از وظایف برای انجام نوعی تجرید در وظیفه هدف بهره گرفت و بدین ترتیب سرعت یادگیری آن را افزایش داد.
یکی از ساده ترین شکل های تجرید این است که فضای حالت را به یک زیرفضا با ب عد کمتر تصویر کنیم. این کار معادل با این است که از برخی متغیرهای حالت صرف نظر کنیم. این دقیقا همان کاری است که راویندران ]٣[ به عنوان همومورفیسم تصویر ساده برای یافتن فرایند مارکوف مجرد از یک فرایند مارکوف فاکتور شده با مدل کاملا معلوم ارائه داده است. هرچند در الگوریتم ارائه شده توسط راویندران، دو مرحله تجرید حالت و مرحله انتخاب متغیرهای مرتبط با هم ترکیب شده اند و بطور هم زمان انجام می شوند، اما روش مذکور تنها برای فرایندهای مارکوف با مدل بیزی کاملا معلوم قابل استفاده است.
در این مقاله، این دو مرحله از یکدیگر مجزا شده اند و تلاش شده است تا الگوریتمی ارائه گردد که برای مواردی که مدل فرایند مارکوف هدف شناخته شده نیست هم قابل استفاده باشد. در روش پیشنهادی، زیرمجموعه ای از متغیرهای مرتبط از مجموعه نمونه از وظایف استخراج می شوند و به عنوان دانش اولیه در اختیار وظیفه هدف قرار می گیرند؛ سپس با استفاده از این دانش، فضای حالت در وظیفه هدف به زیرفضا با بعد کمتر تصویر می شود و بدین ترتیب تجرید بدون هیچ هزینه برخطی صورت می گیرد.
برای وظایف مبدأ نمونه با مدل معلوم، ابتدا تجرید حالت بر مبنای یک معیار مثل مقادیر ارزش Q بهینه یا سیاست های بهینه یا معیارهای دیگر صورت می گیرد؛ سپس از هریک از این تجریدها، زیرمجموعه ای از متغیرهای حالت به عنوان متغیرهای مرتبط استخراج می شوند؛ و در نهایت یک زیرمجموعه نهایی از متغیرها، به عنوان مثال اجتماع تمام متغیرهای استخراج شده از وظایف مبدأ نمونه، به عنوان دانش اولیه در اختیار وظیفه هدف قرار می گیرند.
٢ فرمول بندی مسئله و نتایج اصلی
یک فرایند مارکوف فاکتور شده، یک فرایند مارکوف است که در آن فضای حالت بصورت حاصلضرب کارتزین حوزه های یک مجموعه متناهی از متغیرهای تصادفی Z = fS1; :::; Sng تعریف شده است.
تعریف ٢ . ١. یک مجموعه فا کتور شده S در یک فضای Nب عدی را با مجموعه متغیرهای Z در نظر بگیرید. ا گر Sj حوزه مربوط به متغیر Zj باشد، Zj -تصویر١ S یک نگاشت_Zj : S ! Sj است که بصورت _Zj - z⃗ - = zj تعریف شده و .z⃗ = z1; _ _ _ ; zN
برای یک زیرمجموعه از متغیرها X _ Z ، می توان تعریف بالا را توسعه داد. -Xتصویرِ S، تصویر S بروی زیرفضای حاصل از متغیرهای X است. این را می توان با نگاشت _X : S ! _ - Zj 2X - Sj که بصورت _X = _ - Zj 2X - _Zj تعریف شده، نشان داد.
تعریف ٢ . ٢. هر تابع ϕ با دامنه S یک رابطه هم ارزی روی S تعریف می کند بطوری که s1 _ϕ s2 اگر و تنها اگر .ϕ - s1 - = ϕ - s2 - می گوییم s1 و s2، -ϕهم ارز هستند اگر .s1 _ϕ s2 افراز حاصل از این رابطه هم ارزی روی S را با Pϕ نمایش می دهیم
تعریف ٢. ٣. دو افراز P و P ′ روی مجموعه S را در نظر بگیرید. به یاد آورید که یک افراز S عبارتست از تقسیم S به ” کلاس ها“یا ”بلوک ها“ی ناتهی که با هم همپوشانی نداشته باشند. می گوییم افراز یک تظریف افراز P ′ است و آن را با P ′نمایش می دهیم اگر و تنها اگر هر بلوک از P زیرمجموعه ای از بلوکی از P ′ باشد. در این حالت می گوییم P ظریف تر از P ′ است
شکل ١: یک مثال از متغیر نامرتبط؛ Z1 نسبت به افراز P 1 نامرتبط نیست اما نسبت به افراز P 2 نامرتبط است.
تعریف ٢ . ۴. یک افراز P روی مجموعه فاکتور شده S در نظر بگیرید. فرض کنید Z مجموعه تمام متغیرهای S و Y زیرمجموعه ای از متغیرها و X = Z Y باشند. می گوییم Y نسبت به افراز P نامرتبط است - -Pنامرتبط٣ - اگر P_X، افراز معرفی شده بوسیله -Xتصویر S، ظریف تر از P باشد. در این حالت می گوییم X، -Pسازگار۴ است.
یک مجموعه -Pسازگار ماکسیمال است اگر افزودن هر متغیر دلخواهی به آن منجر به یک مجموعه غیرِ -Pنامرتبط شود. یک مجموعه -Pسازگار مینیمال است اگر حذف هر یک از متغیرهای آن منجر به یک مجموعه غیرِ -Pسازگار شود.
این بدان معناست که افراز حاصل از صرف نظر کردن از متغیرهای مجموعه Y در افراز P می نشیند و در نتیجه محدودیت های شدیدتری - اطلاعات جزئی تری - نسبت به P دارد، اما از محدودیت های - بلوک های - P تجاوز نمی کند. برای روشن شدن بیشتر مطلب، یک مجموعه دو بعدی S با متغیرهای Z1 و Z2 را در نظر بگیرید. فرض کنید Z1 2 f0; 1g و .Z2 2 f0; 1; 2g دو افراز P 1 = ff - 0; 0 - ; - 0; 1 - g; f - 0; 2 - g; f - 1; 0 - ; - 1; 1 - g; f - 1; 2 - gg و P 2 = ff - 0; 0 - ; - 0; 1 - ; - 1; 0 - ; - 1; 1 - g; f - 0; 2 - ; - 1; 2 - gg روی S را در نظر بگیرید.
اکنون اگر از محدودیت های ایجاد شده توسط متغیر Z1 صرف نظر شود، افراز حاصله روی مجموعه S، افراز P_Z2 = ff - 0; 0 - ; - 1; 0 - g; f - 0; 1 - - 1; 1 - g; f - 0; 2 - ; - 1; 2 - gg خواهد بود. این افراز برخی از محدودیت های افراز P 1 را نقض می کند؛ بنابراین Z1 نسبت به P 1 نامرتبط نیست. اما مشاهده می شود که با صرف نظر کردن از Z1 تعدادی از محدودیت های اضافی که در P 2 موجود نبودند، از بین می روند و هر چند افراز حاصله هم چنان محدودیت های اضافه تر و جزئی تری نسبت به P 2 دارد اما از P 2 تجاوز نمی کند و محدودیت های آن را نقض نمی کند؛ بنابراین Z1 نسبت به P 2 نامرتبط است - شکل ١ را ببینید. -
هم چنان که از تعداد بیشتر و بیشتری از متغیرها صرف نظر شود، افراز حاصله درشت تر و درشت تر می شود. علت این است که ب عد فضای تصویر کاهش می یابد. این فرایند را باید تا جایی ادامه داد که افراز حاصله از افراز P تجاوز نکند. با این کار محدودیت های - اطلاعات - اضافی نسبت به محدودیت های P که متغیرها ایجاد می کنند از بین می روند و کنار گذاشته می شوند. برای یافتن مجموعه متغیرهای نامرتبط، والش و همکاران ]۴[ یک الگوریتم ابتکاری افزایشی ارائه می دهند که در اینجا با استفاده از تعریف های دقیق صورت گرفته دوباره ساختاردهی و ارائه شده است
به وضوح، ممکن است بیشتر از یک مجموعه از متغیرهای نامرتبط نسبت به یک افراز وجود داشته باشد که برخی از آن ها ماکسیمال هستند. این الگوریتم یک ترتیب روی مجموعه متغیرها در نظر می گیرد
