سؤال مصاحبه

دو بستر آزمایشی و دو فرمول برای محاسبه‌ی pass@k

Two harnesses, two pass at k formulas

  • سطح ۳: ارشد
  • کدخوانی
  • ۱۰ دقیقه

دو بستر آزمایشی (harness) در این مخزن، معیار pass@k را محاسبه می‌کنند. اولی نرخ قبولی تجربی p را می‌گیرد و عبارت 1 - (1 - p) ** k را برمی‌گرداند. دومی تعداد نمونه‌ها n، تعداد قبولی‌ها c و k را می‌گیرد و عبارت 1 - C(n - c, k) / C(n, k) را محاسبه می‌کند. هر دو را بخوانید. چه زمانی نتیجه‌ی یکسانی دارند، چه زمانی تفاوت پیدا می‌کنند و کدام‌یک باید در گزارش بیاید؟

اول خودتان جواب بدهید، بعد پاسخ را باز کنید.

پاسخ کوتاه

فرمول اول با هر نمونه‌گیری مثل یک آزمایش مستقل با احتمال موفقیت p برخورد می‌کند و یک برآورد جایگذاری (plug-in estimate) است. فرمول دوم احتمال دقیق اینکه k نمونه‌ی تصادفی از بین n نمونه‌ی اجراشده حداقل یک قبولی داشته باشند را می‌شمارد و همان برآوردگر نااریب (unbiased estimator) است که بنچمارک‌های تولید کد به کار می‌برند. این دو فرمول فقط وقتی n بسیار بزرگ شود همگرا می‌شوند؛ برای نمونه‌هایی که واقعاً اجرا کرده‌اید، برآورد جایگذاری مقداری کمتر و پرنوفه‌تر به دست می‌دهد و اگر k از n بیشتر شود، دست به برون‌یابی می‌زند. برآوردگر نااریب را همراه با تعداد خام نمونه‌ها در کنارش گزارش کنید.

پاسخ کامل

بررسی تابع اول

def pass_at_k(empirical_pass_rate, k):
    if k <= 0:
        return 0
    p = max(0, min(1, empirical_pass_rate))
    return 1 - (1 - p) ** k

این تابع مقدار p را مهار (clamp) می‌کند و نمونه‌گیری‌ها را مستقل فرض می‌گیرد. تابع هر مقداری را برای k می‌پذیرد، حتی مقداری بزرگ‌تر از تعداد نمونه‌هایی که بستر آزمایشی اجرا کرده است؛ بنابراین می‌تواند با داشتن 5 نمونه، pass@10 را چاپ کند.

بررسی تابع دوم

def pass_at_k(n, c, k):
    if k > n:
        return float(c > 0)
    if n - c < k:
        return 1
    log_prob = 0
    for i in range(k):
        log_prob += math.log(n - c - i) - math.log(n - i)
    return 1 - math.exp(log_prob)

این تابع از برون‌یابی خودداری می‌کند: اگر k بیشتر از n باشد، برمی‌گرداند که آیا هیچ نمونه‌ای قبول شده یا نه، که این یک کمیت متفاوت است و باید با همین عنوان مشخص شود. وقتی تعداد نمونه‌های ناموفق کمتر از k باشد، هر زیرمجموعه‌ی kتایی قطعاً یک قبولی دارد، بنابراین مقدار 1 را برمی‌گرداند. در غیر این صورت، احتمال اینکه تک‌تک k انتخابِ بدون جایگذاری ناموفق باشند را در هم ضرب می‌کند؛ این کار در فضای لگاریتمی انجام می‌شود تا ضرایب دوجمله‌ای بزرگ سرریز نکنند. لایه‌ی برآوردگر میانگین این مقدار را در تمام وظایف (tasks) محاسبه می‌کند.

تفاوت‌ها کجاست؟

فرض کنید k برابر با n باشد. تابع دوم هر وقت حتی یک نمونه قبول شده باشد، 1 را برمی‌گرداند. اما تابع اول مقداری کمتر از 1 به دست می‌دهد، چون نمونه‌گیری را با جایگذاری در نظر می‌گیرد. به‌طور کلی، نمونه‌گیری بدون جایگذاری احتمال ناموفق بودن هم‌زمان تمام k نمونه را کمتر می‌کند؛ بنابراین برای n و c یکسان، مقدار دقیق همیشه برابر با برآورد جایگذاری یا بیشتر از آن است. علاوه‌بر این، برآورد جایگذاری در nهای کوچک، برآوردی اریب با واریانس بالاست.

چه چیزی را گزارش کنیم؟

به ازای هر وظیفه n نمونه اجرا کنید، طوری که n حداقل برابر با k باشد؛ درست مثل مثال پروژه‌ی پایانی با 10 نمونه و pass@5. معیار pass@1 را به‌صورت c تقسیم بر n، معیار pass@k را از تابع نااریب، و تعداد خام نمونه‌ها را گزارش کنید. هرگز مقدار pass@k را برای مقداری از k که برای آن نمونه‌گیری نکرده‌اید، چاپ نکنید.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 3: در تابع دوم، چرا وقتی n منهای c کوچک‌تر از k است، مقدار 1 برگردانده می‌شود؟ پاسخ مورد انتظار: نمی‌توان k نمونه‌ی ناموفق را از میان کمتر از k شکست انتخاب کرد؛ بنابراین هر زیرمجموعه‌ی kتایی قطعاً شامل یک قبولی است.
  • سطح 3: چرا حاصل‌ضرب در فضای لگاریتمی محاسبه می‌شود؟ پاسخ مورد انتظار: ضرایب دوجمله‌ای برای nهای متوسط سرریز می‌کنند؛ لگاریتم این نسبت، یک جمع کوتاه از لگاریتم‌هاست.
  • سطح 4: تیمی به ازای هر وظیفه 5 نمونه اجرا کرده و pass@10 را گزارش داده است. اشکال کار کجاست؟ پاسخ مورد انتظار: k از n بیشتر است، بنابراین چیزی اندازه گرفته نشده؛ تابع دوم به این بسنده می‌کند که آیا هیچ نمونه‌ای قبول شده یا نه، و تابع اول هم دست به برون‌یابی می‌زند.
  • سطح 4: آیا دو تابع در pass@1 هم‌نظرند؟ پاسخ مورد انتظار: بله؛ هر دو وقتی k برابر با 1 باشد، به کسر c تقسیم بر n تبدیل می‌شوند.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «هر دو یک فرمول هستند.» این دو فقط با بزرگ شدن n همگرا می‌شوند؛ برای نمونه‌هایی که اجرا کرده‌اید، فرمول جایگذاری مقداری کمتر و پرنوفه‌تر می‌دهد.
  • «معیار pass@k یعنی احتمال اینکه ایجنت درست عمل کند.» این احتمال وجود حداقل یک قبولی در مجموعه‌ای متشکل از k نمونه است؛ بدون یک سازوکار انتخاب‌گر، کاربر در نهایت یک نمونه دریافت می‌کند.
  • «نمونه‌های بیشتر در هر وظیفه، مقدار pass@1 را بالا می‌برند.» این کار دقت برآورد را بالا می‌برد؛ خود مقدار همان نرخ قبولی به ازای هر تک‌نمونه است.

کجای دوره آموزش داده می‌شود

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