1. برای کسب اطلاعات بیشتر در ساعات 9 الی 13 و 16 الی 18 با شماره 08138270182 یا 09353637799 تماس حاصل فرمایید.
    آدرس ایمیل: info@wsnlab.ir
    آدرس کانال تلگرام http://telegram.me/gloriot
  2. بدین وسیله به اطلاع پژوهشگران محترم می رسانیم که آزمایشگاه اینترنت اشیاء ایران راه اندازی شد. از این پس می توانید با شماره تلفن همراه 09353637799 با لابراتوار در تماس باشید.

آتوماتای یادگیر تصادفی چیست؟

شروع موضوع توسط Homaei 10/4/14 در انجمن هوش مصنوعی، الگوریتم های هوشمند

تلفن سفارش: 08138311237 تلفن سفارش: 08138311237
  1. Homaei مدیر کل سایت

    تاریخ عضویت:
    25/2/12
    تعداد ارسال ها:
    2,038
    تشکر شده:
    11,617
    امتیاز دستاورد:
    12,265
    وب سایت:
    2.اتوماتاي يادگير

    يك اتوماتاي يادگير از دو قسمت اصلي تشكيل شده است.
    i. يك اتوماتاي تصادفي با تعداد محدودي اقدام و يك محيط تصادفي كه اتوماتا با آن در ارتباط است.
    ii. الگوريتم يادگيري كه اتوماتا با استفاده از آن اقدام بهينه را ياد مي‌گيرد.

    2.1.اتوماتاي تصادفي

    يك اتوماتاي تصادفي بصورت پنج‌تايي [IMG] تعريف مي‌شود كه [IMG] تعداد اقدامهاي اتوماتا، [IMG] تعداد اقدامهاي اتوماتا، [IMG] مجموعه اقدامهاي اتوماتا، [IMG] مجموعه وروديهاي اتوماتا، [IMG] تابع توليد وضعيت جديد، [IMG] تابع خروجي كه وضعيت فعلي را به خروجي بعدي نگاشت مي‌كند و [IMG] مجموعه وضعيتهاي داخلي اتوماتا در لحظه n، مي‌باشند.
    مجموعه [IMG] شامل خروجيهاي (اقدامهاي) اتوماتا است كه اتوماتا در هر گام يك اقدام از r اقدام اين مجموعه را براي اِعمال بر محيط انتخاب مي‌نمايد. مجموعه ورودي‌ها ([IMG]) وروديهاي اتوماتا را مشخص مي‌كند. توابع F و G وضعيت فعلي ورودي را به خروجي بعدي (اقدام بعدي) اتوماتا نگاشت مي‌كنند. اگر نگاشتهاي F و G قطعي باشند، اتوماتا يك اتوماتاي قطعي[1] ناميده مي‌شود. در حالتيكه نگاشتهاي F و Gتصادفي باشند، اتوماتا يك اتوماتاي تصادفي ناميده مي‌شود.
    اتوماتاي يادگير به دو گروه اتوماتاي با ساختار ثابت[2] و اتوماتاي با ساختار متغير[3] تقسيم بندي مي‌گردند. در اتوماتاي تصادفي با ساختار ثابت احتمال اقدامهاي اتوماتا ثابت هستند. درحاليكه در اتوماتاي تصادفي با ساختار متغير احتمالات اقدامهاي اتوماتا در هر تكرار بِروز مي‌شوند. در اتوماتاي يادگير با ساختار متغير، تغيير احتمالهاي اقدامها بر اساس الگوريتم يادگيري انجام مي‌شود. همچنين در اتوماتاي يادگير با ساختار متغير، وضعيت داخلي اتوماتا [IMG] توسط احتمالات اقدامهاي اتوماتا بازنمايي مي‌شوند. در واقع اتوماتا بصورت يك state-output automata در نظر گرفته مي‌شود كه خروجي آن معادل با وضعيت داخلي آن مي‌باشد. وضعيت داخلي اتوماتا [IMG] در لحظه n را با بردار احتمال اقدامهاي اتوماتا P(n) كه در زير آمده است، نشان داده مي‌شود.

    [IMG]
    بطوريكه
    (.1)
    [IMG]
    در آغاز فعاليت اتوماتا، احتمال اقدامهاي آن با هم برابر و مساوي [IMG] مي‌باشند. (كه r تعداد اقدامهاي اتوماتا مي‌باشد.)
    2.2.محيط

    محيط را مي توان توسط سه تايي [IMG] نشان داد كه در آن [IMG] مجموعه وروديهاي محيط، [IMG] مجموعه خروجيهاي محيط و[IMG] مجموعه احتمالهاي جريمه مي‌باشند.
    ورودي محيط يكي از r اقدام انتخاب شده اتوماتا است. خروجي(پاسخ) محيط به هر اقدام i توسط [IMG] مشخص مي شود. اگر [IMG] يك پاسخ دودويي باشد، محيط مدلP[4] ناميده مي‌شود. در چنين محيطي [IMG] بعنوان پاسخ نامطلوب[5] يا شكست[6] و [IMG] بعنوان پاسخ مطلوب[7] يا موفقيت در نظر گرفته مي‌شوند. در محيط مدلQ[8] ،[IMG] شامل تعداد محدودي از مقادير قرار گرفته در بازه [1، 0] مي‌باشد. درحاليكه در محيط مدلS[9] مقادير[IMG] يك متغير تصادفي در بازه [1، 0] مي‌باشد ([IMG]). مجموعه c احتمالات جريمه (شكست) پاسخهاي محيط را مشخص مي‌كند و بصورت زير تعريف مي‌شود.

    [IMG]
    كه احتمال اينكه اقدام [IMG] پاسخ نامطلوبي از محيط دريافت كند را نشان مي‌دهد. مقادير [IMG]ها نامشخص هستند و فرض مي‌شود كه [IMG]ها يك مينيمم يكتا دارند. بهمين صورت مي‌توان محيط را توسط مجموعه احتمالات پاداش(موفقيت) [IMG] نشان داد كه در اين حالت[IMG] نشان‌دهنده احتمال دريافت پاسخ مطلوب به اقدام [IMG] مي‌باشد. در محيطهاي ايستا[10] مقادير احتمال جريمه ([IMG]ها) ثابت هستند. درحاليكه در محيطهاي غير ايستا[11] احتمالات جريمه در طول زمان تغيير مي‌كند.

    [IMG]
    شكل .1 اتوماتاي يادگير تصادفي
    ارتباط اتوماتاي تصادفي با محيط در شكل .‑1 نشان داده شده است. از اين مجموعه بهمراه الگوريتم يادگيري تحت عنوان اتوماتاي يادگير تصادفي[12] نام برده مي‌شود. بهمين ترتيب اتوماتاي يادگير تصادفي را مي‌توان با چهارتايي [IMG] نشان داد كه [IMG] تعداد اقدامهاي اتوماتا، [IMG] تعداد اقدامهاي اتوماتا، [IMG] مجموعه اقدامهاي اتوماتا، [IMG] مجموعه وروديهاي اتوماتا، [IMG] بردار احتمال اقدامهاي اتوماتا و [IMG] الگوريتم يادگيري مي‌باشد.
    2.3.معيار‌هاي رفتار اتوماتاي يادگير

    براي اندازه‌گيري كارايي اتوماتاي يادگير تصادفي، شاخصهاي معيني تعريف شده‌اند كه امكان مقايسه روشهاي مختلف يادگيري را فراهم مي‌آورند. يك اتوماتاي شانسي محض بصورت اتوماتايي تعريف مي‌شود كه اقدامهاي آن هميشه احتمال يكساني براي انتخاب شدن داشته باشند. بنابراين يك اتوماتاي يادگير بايد از يك اتوماتاي شانسي محض بهتر عمل كند.
    همانطور كه ذكر شد، محيط توسط احتمالات جريمه [IMG] نشان داده مي‌شود كه [IMG]احتمال جريمه متناظر با اقدام [IMG] است. مقدار [IMG] بصورت ميانگين جريمه‌هاي دريافت شده توسط اتوماتا (براي يك بردار اقدام مفروض) تعريف و بر اساس رابطه .‑2 محاسبه مي‌شود.
    (.2 )
    [IMG]
    براي يك اتوماتاي شانسي محض ميانگين جريمه‌‌ها M(n) يك عدد ثابت [IMG] است كه طبق رابطه .‑3 بدست مي‌آيد:
    [IMG]
    (.3 )
    بنابراين اتوماتايي كه بخواهد بهتر از اتوماتاي شانسي محض عمل كند، بايد ميانگين جريمه‌هاي كمتري از [IMG] داشته باشد. از آنجاييكه [IMG] يك متغير تصادفي است، اميد رياضي [IMG] ([IMG]) با [IMG] مقايسه مي‌شود. بنابراين تعاريف زير را خواهيم داشت.
    تعريف .1 يك اتوماتاي يادگير expedient گفته مي‌شود، اگر :
    [IMG]
    (.4 )
    تعريف .2يك اتوماتاي يادگير بهينه[13] گفته مي‌شود، اگر :
    [IMG]
    (.5 )
    كه [IMG]. در حاليكه بهينه بودن اتوماتا يك ويژگي مطلوب در محيطي ايستا بشمار مي‌رود، در عمل ممكن است يك كارايي نيمه‌ بهينه[14] مورد نياز باشد. يك محيط واقعي معمولا متغير است و در نتيجه اقدام بهينه در زمان تغيير مي‌كند. در چنين حالتي و از آنجاييكه الگوريتم بر روي هيچ حالت خاصي متوقف نمي‌ماند، يك اتوماتاي نيمه بهينه مناسب‌تر مي‌باشد. بنابراين تعريف زير را نيز خواهيم داشت:
    تعريف .3يك اتوماتاي يادگير [IMG] گفته مي‌شود، اگر :
    [IMG]
    (.6)
    تعريف .4يك اتوماتاي يادگير Absolutely Expedient گفته مي‌شود، اگر :
    [IMG]
    (.7)
    Expediency بندرت نشان مي‌دهد كه اتوماتاي يادگير بهتر از اتوماتاي شانسي محض عمل مي‌كند. بنابراين بهينه بودن[15] شاخص مناسب‌تري براي مقايسه روشهاي مختلف يادگيري مي‌باشد. بهينه‌بودن اطمينان مي‌دهد كه اقدامي كه توسط اتوماتا انتخاب مي‌شود، اقدامي بهينه باشد. در محيطهاي واقعي بعلت متغير بودن محيط رفتار زير ‌بهينه ارجحيت دارد .

    2.4.الگوريتمهاي يادگير

    2.4.1.الگوريتمهاي يادگير استاندارد

    همانطور كه در بخش ‏2 نشان داده شد، الگوريتم يادگيري T بصورت [IMG] نشان داده مي‌شود. اگر T يك عملگر خطي باشد، الگوريتم يادگيري تقويتي، خطي ناميده مي‌شود. در غير اينصورت الگوريتم يادگيري غيرخطي ناميده مي‌شود. ايده اصلي تمام الگوريتمهاي يادگيري بصورت زير است.
    اگر اتوماتاي يادگير در تكرار nاُم، يك اقدام خود مانند [IMG] را انتخاب كند و يك پاسخ مطلوب[16] از محيط دريافت نمايد، [IMG] (احتمال اقدام [IMG]) افزايش و احتمال ساير اقدامها كاهش مي‌يابد. بالعكس در صورت نامطلوب بودن پاسخ دريافتي از محيط، احتمال اقدام [IMG] كاهش و احتمال ساير اقدامهاي اتوماتا افزايش مي‌يابد. در هر حال، تغييرات به گونه اي صورت مي گيرد تا حاصل جمع [IMG]ها همواره ثابت و مساوي يك باقي بماند. تغيير احتمال اقدامها بصورت زير مي‌باشد.
    الف- پاسخ مطلوب از محيط
    [IMG]
    (.8)
    ب- پاسخ نامطلوب از محيط
    [IMG]
    (.9)

    توابع [IMG] و [IMG] دو تابع غير منفي هستند كه بترتيب توابع پاداش و جريمه ناميده مي‌شوند. همانطور كه در روابط فوق مشاهده مي‌شود، اين روابط صحت رابطه (.‑1) را حفظ مي‌كنند. از آنجاييكه الگوريتمهاي يادگيري خطي از لحاظ رياضي ساده‌تر مي‌باشند، بررسي‌هاي زيادي بر روي آنها انجام شده است. در يك الگوريتم يادگيري تقويتي خطي (در اتوماتايي با چند اقدام) توابع [IMG] و [IMG] بصورت زير تعريف شده‌اند.
    [IMG]
    (.10)
    [IMG]
    (.11)
    كه r تعداد اقدامهاي اتوماتا، a پارامتر پاداش و b پارامتر جريمه مي‌باشند. با استفاده از رابطه (.‑10) و (.‑11) شكل عمومي الگوريتم يادگيري بصورت زير است.‌ اگر در گام nاُم اقدام [IMG] انتخاب شده باشد، سپس در گام 1+nاُم خواهيم داشت :
    الف- پاسخ مطلوب از محيط
    [IMG]
    (.12)
    ب- پاسخ نامطلوب از محيط
    [IMG]
    (.13)
    با توجه به مقادير a و b در روابط فوق، سه حالت را مي توان در نظر گرفت. اگر مقادير a و b برابرباشند، اتوماتاي يادگير [IMG] ناميده مي‌شود. زمانيكه b مساوي با صفر باشد اتوماتاي يادگير [IMG][17] ناميده مي‌شود. اگر b<<a باشد، اتوماتاي يادگير [IMG][18] ناميده مي‌شود. اتوماتاي [IMG] رفتاري expedient از خود نشان مي‌دهد. در حاليكه دو اتوماتاي [IMG] و [IMG] رفتاري زير بهينه دارند. روشهاي بروز رساني غير خطي نيز معرفي شده‌اند كه بهبود محسوسي نسبت به روشهاي خطي فوق نشان نمي‌دهند.
    يك عامل تعيين كننده كه استفاده از اتوماتاي يادگير تصادفي را در حل مسائل محدود مي‌كند، نرخ همگرايي كُند اتوماتاي يادگير است. اين عامل با افزايش تعداد اقدامهاي اتوماتا تشديد مي‌شود. هرچند استفاده از برخي از روشهاي يادگيري غيرخطي باعث افزايش سرعت همگرايي اتوماتا مي‌گردد.

    2.4.2.الگوريتمهاي يادگيري مدل-S


    در محيطهاي S پاسخ محيط به اقدامهاي اتوماتاي يادگير، يك متغير تصادفي در بازه [1، 0] مي‌باشد. بنابراين خروجي محيط (ورودي اتوماتا) بصورت زير تغيير مي‌كند.
    [IMG]

    از آنجاييكه پاسخ محيط از نوع S يك متغير تصادفي در بازه [1، 0] است، استفاده از مدل S براي سيستمهاي يادگير نياز به اطلاعات اوليه‌اي از كران بالا و پايين شاخصهاي كارايي سيستم دارد تا بتواند پاسخهاي محيط را در مقياس [1، 0] تنظيم نمايد

    2.4.2.1. الگوريتم [IMG]

    در محيط مدلP محيط توسط احتمال جريمه‌ها تعريف مي‌شود. براي هر اقدام مانند [IMG]، محيط پاسخي با يك مقدار تصادفي [IMG] به اتوماتا مي‌دهد كه ورودي اتوماتا را تشكيل مي‌دهد. در مدل P، پاسخ [IMG] با احتمال [IMG] برابر 1 (پاسخ نامطلوب) و با احتمال [IMG]-1 صفر(پاسخ مطلوب) در نظر گرفته مي‌شود. اما در محيط مدل S، محيط بصورت زير تعريف مي‌شود.
    [IMG]

    [IMG]
    كه
    [IMG] مقدار ميانگين پاسخ [IMG] براي اقدام [IMG] مي‌باشد و در واقع [IMG]ها بعنوان شدت جريمه‌ها محسوب مي‌شوند. فرض كنيد در گام nاُم اقدام [IMG] انتخاب شده باشد و پاسخ محيط به آن [IMG] بوده باشد. در چنين حالتي احتمال اقدامهاي اتوماتاي [IMG] بصورت زير بروز مي‌شوند.
    [IMG]
    (.14)
    كه a پارامتر يادگيري و 1<a<0 مي‌باشد.

    2.4.2.2. الگوريتم [IMG]


    الگوريتم يادگيري تقويتي اتوماتاي يادگير در مدل [IMG] بصورت زير بردار احتمالات اقدامهاي اتوماتا را بروز مي‌كند. در اتوماتايي با r اقدام، اگر در تكرار nاُم اقدام [IMG] انتخاب شده باشد و پاسخ محيط به آن [IMG] باشد، بردار احتمالهاي اتوماتا طبق رابطه (.‑15) بروز مي‌شود.
    [IMG]
    (.15)
    2.4.2.3. الگوريتم [IMG]


    اتوماتاي يادگيري [IMG] با r اقدام و پارامتر پاداش a و پارامتر جريمه b ، بصورت زير بردار اقدامهاي خود را بروز مي‌كند. اگر در تكرار nاُم اقدام [IMG] انتخاب شده باشد و پاسخ محيط به آن [IMG] باشد، بردار احتمالهاي اتوماتا طبق رابطه (.‑16) بروز مي‌شود.
    [IMG]
    (.16)
    2.5.اتوماتاي يادگير با اقدامهاي متغير

    اتوماتاي يادگير داراي تعداد اقدام ثابتي مي‌باشند اما در بعضي از كاربردها نياز به اتوماتايي با تعداد اقدام متغير مي‌باشد. اين اتوماتا در لحظه n اقدام خود را فقط از يك زير مجموعه غير تهي ([IMG]) ازاقدامها كه اقدامهاي فعال ناميده مي‌شوند انتخاب مي‌كند. انتخاب مجموعه [IMG] توسط يك عامل خارجي و بصورت تصادفي انجام مي‌شود. نحوه فعاليت اين اتوماتا بصورت زير است. براي انتخاب يك اقدام در زمان[IMG]، ابتدا مجموع احتمال اقدامهاي فعال خود ([IMG]) را محاسبه مي‌كند و سپس بردار[IMG] را مطابق رابطه (.‑17) محاسبه مي‌كند. آنگاه اتوماتا يك اقدام از مجموعه اقدام‌هاي فعال خود را بصورت تصادفي و مطابق بردار احتمال[IMG] انتخاب كرده و بر محيط اعمال مي‌كند. اگر اقدام انتخاب شده[IMG] باشد، پس از دريافت پاسخ محيط، اتوماتا بردار احتمال[IMG] اقدامهاي خود در صورت دريافت پاداش بر اساس رابطه (.‑18) و در صورت دريافت جريمه طبق رابطه (.‑19) بِروز مي‌كند(در محيط مدلP).

    [IMG]

    (.17)
    الف- پاسخ مطلوب از محيط
    [IMG]
    (.18)
    ب- پاسخ نامطلوب از محيط
    [IMG]
    (.19)

    سپس اتوماتا بردار احتمال اقدامها[IMG] را با استفاده از بردار[IMG] و بصورت زير بِروز مي‌كند.[1]
    [IMG]
    ( .20)


    2.6.اتوماتاي يادگير توزيع شده[19]

    اتوماتاي يادگير توزيع شده (DLA) ، شبكه‌اي از اتوماتاهاي يادگير است كه براي حل يک مساله با يكديگر همكاري مي نمايند. تعداد اقدامهاي يك اتوماتا در DLA برابر تعداد اتوماتاهاي يادگ ير متصل به اين اتوماتاي يادگير مي باشد. انتخاب يك اقدام توسط يك اتوماتا ي يادگ ير در شبكه، اتوماتاي يادگ ير متناظر با اين اقدام را فعال مي سازد. بعنوان مثال در شكل 2 هر اتوماتا يادگ ير داراي دو اقدام مي باشد. انتخاب اقدام [IMG] توسط [IMG]، اتوماتا يادگير [IMG] را فعال خواهد كرد. اتوماتاي يادگير فعال شده [IMG] سپس يكي از اقدامهاي خود را انتخاب مي كند كه در نتيجه آن يكي از اتوماتاهاي يادگ ير متصل به آن اتوماتا ي يادگ ير كه متناظر با اقدام انتخاب شده مي باشد فعال مي شود. در هر زمان فقط يك اتوماتاي يادگير در شبكه فعال ميباشد. بطور رسميDLA را ميتوان توسط گراف [IMG] كه [IMG] مجموعه اتوماتاهاي يادگير و n تعداد اتوماتاهاي يادگير در DLA و [IMG] مجموعه لبه‌هاي گراف مي باشد، تعريف كرد. لبه [IMG] اقدام j اتوماتا ي يادگير [IMG] را نشان مي دهد. [IMG] زماني فعال خواهد شد كه اقدام j اتاماتای یادگیر [IMG] انتخاب شود. تعداد اقدامهاي اتوماتاي يادگير [IMG] ([IMG] ) برابر درجه‌ي خروجي گره متناظر با اتوماتاي يادگير [IMG] مي باشد[2].

    [IMG]
    شكل 2-2: اتوماتاي يادگير توزيع شده (DLA) با 3 اتوماتا ي يادگير


    [1] Deterministic Automata
    [2] Fixed Structure Automata
    [3] Variable Structure Automata
    [4] P-model
    [5] Unfavorable
    [6] Failure
    [7] Favorable
    [8] Q-model
    [9] S-model
    [10] Stationary
    [11] Non-Stationary
    [12] Stochastic Learning Automata
    [13] Optimal
    [14] Sub-Optimal
    [15] Optimality
    [16] Favorable
    [17] Linear Reward Inaction
    [18] Linear Reward Epsilon Penalty
    [19] Distributed Learning Automata
    Ghobadi and niko like this.
    لطفاً انجمن را به دوستان خود معرفی نمایید تا محیطی پویا تر داشته باشیم.
  2. مشاوره، آموزش و پیاده سازی پروژه های شبکه های موردی، شبکه حسگر بی سیم و انواع شبکه های کامپیوتری . برای کسب اطلاعات بیشتر با شماره 08138270182 تماس بگیرید. .

به اشتراک بگذارید