پیاده‌سازی زمان‌بند تکرار و اجرای هم‌روند آزمایش‌ها

در سیستم‌های خودکار پژوهشی و آزمایش‌های مبتنی بر مدل‌های زبانی، اجرای ترتیبی فرضیه‌ها منابع پردازشی را تلف می‌کند. از آنجا که نتایج یک آزمایش می‌تواند مسیر آزمایش‌های بعدی را کاملاً دگرگون کند، استفاده از یک صف ساده (FIFO) دیگر پاسخ‌گوی نیازهای پیچیده نیست و به یک زمان‌بند هوشمند نیاز است.

در این درس یاد می‌گیرید که چگونه با ترکیب الگوریتم حد بالای اطمینان (UCB1) و کتابخانه‌ی asyncio در پایتون، یک چرخه‌ی پژوهش هم‌روند بسازید. این زمان‌بند هم‌زمان با اجرای آزمایش‌ها در چند اسلات موازی، بازدهی شاخه‌های مختلف فرضیه را محاسبه کرده، گزینه‌های کم‌بازده را هرس می‌کند و شاخه‌های موفق را برای تولید فرضیه‌های تکمیلی یا نگارش مقاله توسعه می‌دهد.

چرخه‌ی پژوهشی بدون اسکژولر (scheduler)، صفی از کارها با توهم کارآمدی است. اسکژولر همان‌جایی است که چرخه تصمیم می‌گیرد دست از کاوش در چه چیزهایی بکشد؛ و تمام بازی در گرو همین تصمیم است.

اهداف یادگیری

• مدل‌سازی یک جریان کاری پژوهشی به‌صورت صف فرضیه‌ها که اسلات‌های موازی آزمایش را تغذیه می‌کند و نتایج آن‌ها دوباره جمع‌آوری می‌شود.
• اجرای هم‌روند چندین آزمایش با asyncio تا اسکژولر بتواند تمام اسلات‌ها را پیوسته پر نگه دارد.
• امتیازدهی به هر branch فرضیه با UCB تا اسکژولر بتواند شاخه‌های کم‌بازده را هرس کند، بدون آنکه دست از کاوش بردارد.
• توزیع موازی نتایج نهایی به مرحله‌ی نگارش مقاله و مرحله‌ی صف‌بندی دوباره، تا یک branch پربازده فرضیه‌های تکمیلی تولید کند.
• ارائه‌ی یک ردگیری محاسبات به‌ازای هر تکرار، شامل امتیازهای branch، وضعیت اشغال اسلات‌ها و تصمیم‌های هرس کردن.

چرا اسکژولر، نه یک لیست کاری ساده

یک لیست کاری ساده و خطی، کارها را به ترتیب ثبت‌شدن اجرا می‌کند. این روش زمانی جواب می‌دهد که هر وظیفه مستقل باشد. کارهای پژوهشی مستقل نیستند: یافته‌ای از آزمایش سوم، اولویت آزمایش‌های چهارم و پنجم را دگرگون می‌کند. اسکژولری که نتایج دریافتی را می‌خواند و صف را دوباره مرتب می‌کند، به‌ازای هر واحد توان پردازشی، کار مفید بسیار بیشتری انجام می‌دهد.

انتخاب جذاب در طراحی، قاعده‌ی امتیازدهی است. یک سیستم امتیازدهی حریصانه (greedy) همیشه گزینه‌ی پیشتاز فعلی را برمی‌دارد و هرگز کاوش (exploration) نمی‌کند. سیستم امتیازدهی یکنواخت هم هیچ‌گاه سراغ بهره‌برداری (exploitation) نمی‌رود. الگوریتم UCB (حد بالای اطمینان / Upper Confidence Bound) راه میانه است: بهره‌برداری از گزینه‌ی برتر، هم‌زمان با حفظ ظرفیت برای شاخه‌هایی که کمتر آزموده شده‌اند.

ساختار کلی سیستم

صف فرضیه‌ها را نگه می‌دارد. اسکژولر با خالی شدن هر اسلات، فرضیه‌ای را برمی‌دارد که بیشترین امتیاز UCB را دارد. هر اسلات آزمایشی را به‌صورت ناهمگام اجرا می‌کند. آزمایش‌های پایان‌یافته نتایج خود را روی گذرگاه داده (bus) می‌فرستند. این گذرگاه آمارهای UCB مربوط به branch مبدأ را به‌روزرسانی می‌کند و هرگاه بازدهی یک شاخه از یک آستانه گذشت، فرآیند را به‌صورت موازی به‌سمت مرحله‌ی نگارش مقاله می‌فرستد.

ساختار Hypothesis

فیلد branch کلید اصلی آمارهای UCB است. چندین فرضیه ممکن است در یک branch مشترک باشند (شاخه همان جهت‌گیری پژوهشی است؛ فرضیه یک آزمون در دل آن است). فیلد runs تعداد آزمایش‌های کامل‌شده برای آن branch و reward_sum پاداش تجمعی است. UCB هر دو را می‌خواند.

امتیازدهی با UCB

فرمول UCB استفاده‌شده در این درس، همان فرمول کلاسیک UCB1 است.

$$\text{ucb}(\text{branch}) = \text{mean\_reward}(\text{branch}) + c \sqrt{ \frac{\ln(\text{total\_runs})}{\text{runs}(\text{branch})} }$$

فیلد total_runs تعداد کل آزمایش‌های کامل‌شده در تمامی branchها است. c وزن کاوش است که در این درس به‌طور پیش‌فرض sqrt(2) در نظر گرفته شده است. شاخه‌ای با صفر بار اجرا امتیاز +inf می‌گیرد تا شاخه‌های آزموده‌نشده همیشه اولویت نخست زمان‌بندی باشند. شاخه‌ای با میانگین پاداش بالا، امتیاز بالای خود را حفظ می‌کند تا زمانی که سایر شاخه‌ها به آن برسند؛ در مقابل، شاخه‌ای که بارها اجرا شود اما پاداش چندانی نیاورد، زیر سایه‌ی گزینه‌های کمتر اجراشده قرار می‌گیرد.

درگاه هرس کردن کاملاً جدا از بخش انتخاب فرضیه کار می‌کند. هرس کردن شاخه‌ای را از زمان‌بندی‌های بعدی کنار می‌گذارد که میانگین پاداش آن پس از دست‌کم prune_after_runs بار آزمون (پیش‌فرض 3)، به زیر یک کف مطلق (پیش‌فرض 0.2) سقوط کند. این کار صف را محدود نگه می‌دارد.

اسلات‌های موازی با asyncio

اسکژولر آزمایش‌ها را با asyncio.create_task اجرا می‌کند. هر وظیفه، اجراکننده‌ی آزمایش (یک کالبلِ async def) را اجرا می‌کند که خروجی آن یک Result است. حلقه‌ی اصلی روی مجموعه‌ی وظایف در جریان با asyncio.wait(..., return_when=asyncio.FIRST_COMPLETED) منتظر می‌ماند و با اتمام هر وظیفه، به‌روزرسانی امتیازها را فراخوانی می‌کند.

سه اسلات به‌طور هم‌روند اجرا می‌شوند. حلقه‌ی اصلی هیچ‌گاه پشت یک آزمایش معطل نمی‌ماند. اسکژولر به‌محض آزاد شدن یک اسلات، وظیفه‌ی جدیدی را آغاز می‌کند تا زمانی که هم صف خالی شود و هم هیچ وظیفه‌ای در حال اجرا نمانده باشد.

توزیع موازی: محرک‌های نگارش مقاله

هرگاه میانگین پاداش یک branch از paper_threshold (پیش‌فرض 0.7) فراتر برود و آن شاخه هنوز مقاله‌ای تولید نکرده باشد، اسکژولر رویداد paper.trigger را در یک لیست خروجی ثبت می‌کند. در ادامه‌ی مسیر، ابزار نگارش مقاله از درس پنجاه‌وچهارم این رویداد را دریافت خواهد کرد. در این درس، این محرک در قالب یک لیست ذخیره می‌شود تا آزمون‌ها بتوانند صحت آن را بررسی کنند.

توزیع موازی: فرضیه‌های تکمیلی

وقتی نتیجه‌ای با بازدهی بالا به‌دست می‌آید، اسکژولر می‌تواند تابع expander ارائه‌شده از سوی کاربر را فراخوانی کند تا یک یا چند فرضیه‌ی تکمیلی روی همان branch بسازد. این تابع گسترش‌دهنده یک تابع خالص از Result به list[Hypothesis] است. در این درس یک تابع گسترش‌دهنده‌ی قطعی گنجانده شده که به‌ازای هر نتیجه‌ای با پاداش بیشتر از آستانه‌ی مقاله، دو فرضیه‌ی تکمیلی تولید می‌کند.

بودجه‌ها

دو نوع بودجه از اسکژولر در برابر حلقه‌های بی‌پایان محافظت می‌کنند.

max_experiments    : total count of experiments run across all branches
max_seconds        : wall-clock cap (asyncio time)

به‌محض فعال شدن هر یک از این دو شرط، اسکژولر زمان‌بندی وظایف جدید را متوقف می‌کند، منتظر تکمیل وظایف در جریان می‌ماند و ردگیری محاسبات نهایی را بازمی‌گرداند. این ردگیری محاسبات شامل فیلد stop_reason است.

ردگیری محاسبات و گزارش نهایی

هر تصمیم زمان‌بندی (انتخاب، اعزام، نتیجه، هرس کردن، توزیع موازی) یک رویداد ثبت می‌کند. گزارش نهایی خلاصه‌ای از آمارهای هر branch، تعداد کل اجراها، کل زمان واقعی و محرک‌های مقاله‌ی صادرشده را در بر دارد. درس بعدی که به دمو و اجرای سرتاسری اختصاص دارد، این گزارش را می‌خواند تا ابزار نگارش مقاله را هدایت کند.

راهنمای خواندن کد

فایل code/main.py ساختارهای Hypothesis، Result، BranchStats و IterationScheduler را به همراه کارخانه‌ی make_deterministic_runner تعریف می‌کند؛ کارخانه‌ای که یک اجراکننده‌ی آزمایش مبتنی بر asyncio با پاداش‌های پیش‌بینی‌پذیر برمی‌گرداند. این اجراکننده برای مدت‌زمان ثابت delay_ms (پیش‌فرض 5ms) متوقف می‌شود تا هم‌روندی به‌طور ملموس دیده شود.

فایل code/tests/test_scheduler.py این موارد را پوشش می‌دهد: اولویت دادن UCB به شاخه‌های آزموده‌نشده، اشغال اسلات‌های موازی، ارسال محرک مقاله هنگام عبور از آستانه، هرس کردن شاخه‌ها پس از آزمون‌های کم‌بازده، توزیع موازی فرضیه‌های تکمیلی، و پایان کار بر اساس بودجه (هم از نظر تعداد آزمایش و هم زمان واقعی).

گام‌های بعدی

یک پیاده‌سازی واقعی به سه قابلیت تکمیلی نیاز خواهد داشت. نخست، ماندگاری آمارهای UCB در میان نشست‌ها: آمارهای کنونی در حافظه نگهداری می‌شوند؛ درحالی‌که یک اسکژولر واقعی باید از آن‌ها چک‌پوینت بگیرد تا با راه‌اندازی مجدد، بودجه‌ی کاوشِ صرف‌شده از دست نرود. دوم، امتیازدهی چندهدفه: به‌جای یک پاداش اسکالر، هر نتیجه یک بردار برمی‌گرداند و UCB به یک انتخاب‌گر مبتنی بر بهینگی پارتو (Pareto) تبدیل می‌شود. سوم، راهزنان زمینه‌ای (contextual bandits): سازوکار انتخاب بر ویژگی‌های فرضیه (مانند طول و پیچیدگی) مشروط می‌شود تا فرضیه‌های مشابه در کاوش با یکدیگر سهیم شوند.

اسکژولر همان جایی است که پژوهش را از یک لیست کاری ساده فراتر می‌برد. به‌محض اینکه UCB متصل شود و اسلات‌ها به‌صورت موازی به کار بیفتند، همه‌ی بهبودهای دیگر را می‌توان روی همین پایه سوار کرد.