سؤال مصاحبه

آموزش فهرست merge در BPE بر اساس بسامد کلمات

Train a BPE merge list from word counts

  • سطح ۲: میانی
  • پروژه‌ی خانگی
  • ۳۰ دقیقه

پیکره متنی (corpus) در قالب یک دیکشنری به شما داده می‌شود؛ کلیدهای آن کلمات هستند (هر کلمه یک تاپل از شناسه‌های بایتی است) و مقادیر آن تعداد تکرار هر کلمه را مشخص می‌کنند. حلقه‌ی آموزشی را بنویسید که یک فهرست مرتب از ادغام‌ها (merges) تولید کند، و سه قاعده‌ای را بیان کنید که عملکرد این حلقه را قطعی (deterministic) می‌کنند. سپس بگویید این حلقه چه کاری را نباید با داده‌های فراخواننده (caller) انجام دهد.

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

پاسخ کوتاه

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

پاسخ کامل

حلقه‌ی آموزش

def train(units, num_merges, first_id=256):
    merges = []
    units = dict(units)
    for i in range(num_merges):
        pairs = count_pairs(units)
        best = best_pair(pairs)
        if best is None or pairs[best] < 2:
            break
        new_id = first_id + i
        units = {apply_merge(word, best, new_id): freq for word, freq in units.items()}
        merges.append((best, new_id))
    return merges, units

شناسه‌های ابتدایی برای بایت‌های خام رزرو شده‌اند؛ بنابراین، اولین merge نخستین شناسه‌ی آزاد بعدی را می‌گیرد و هر ادغام بعدی شناسه‌ی پس از آن را دریافت می‌کند. فهرست merge بر اساس ترتیب آموزش، همان توکنایزر (tokenizer) است. کُدگذاری متن جدید نیازمند اعمال همان ادغام‌ها با همان ترتیب است؛ در نتیجه، هرگونه تغییر در ترتیب ادغام‌ها هنگام استنتاج (inference)، رشته‌ای متفاوت از شناسه‌ها را رمزگشایی (decode) می‌کند.

شمارش‌های وزن‌دار

یک جفت درون کلمه‌ای که پنج بار تکرار شده است، عدد 5 را به شمارش اضافه می‌کند، نه 1. اگر هر تکرار را صرفاً یک‌بار بشمارید، کلمات طولانی و کم‌کاربرد بر کلمات کوتاه و رایج غلبه می‌کنند و ترتیب ادغام‌ها تغییر می‌کند. جفت‌ها از انتهای یک کلمه به ابتدای کلمه‌ی بعدی نمی‌روند؛ همین تفکیک مرز کلمات است که mergeها را درون کلمات نگه می‌دارد و امکان تعمیم‌پذیری آن‌ها را فراهم می‌کند.

موارد تساوی و قاعده‌ی توقف

دو جفت با بسامد یکسان باید در هر بار اجرا دقیقاً به یک شکل تعیین‌تکلیف شوند؛ بنابراین، جفتی که در مقایسه‌ی ترتیبیِ تاپل کوچک‌تر باشد برنده است. بدون یک قاعده‌ی ثابت، ترتیب داخلی دیکشنری تصمیم‌گیرنده خواهد بود و دو بار اجرای آموزش روی یک پیکره متنی یکسان، توکنایزرهای متفاوتی تولید می‌کند. همچنین اگر بیشترین بسامد کمتر از 2 باشد، حلقه پیش از موعد متوقف می‌شود؛ زیرا جفتی که فقط یک‌بار تکرار شده باشد هیچ فشرده‌سازی انجام نمی‌دهد و صرفاً جایگاه‌های (slots) واژگان را هدر می‌دهد.

ورودی را تغییر ندهید

دیکشنری و تاپل‌های ارائه‌شده از سمت فراخواننده دست‌نخورده باقی می‌مانند. پاک کردن و پر کردن مجدد دیکشنری به‌صورت درجا (in-place)، یا بازنویسی تاپل‌ها از طریق یک لیست، داده‌هایی را که شاید فراخواننده همچنان به آن‌ها نیاز داشته باشد دستکاری می‌کند. در هر مرحله باید یک دیکشنری جدید از کلمات ادغام‌شده ساخته شود.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: چرا با پیشرفت آموزش، تعداد نمادها کاهش می‌یابد و این موضوع چه تأثیری بر هزینه‌ی هر گام دارد؟ پاسخ مورد انتظار: هر merge طول کلمات را کوتاه‌تر می‌کند، بنابراین تعداد کل جفت‌ها در پیکره متنی کاهش می‌یابد و گام‌های بعدی سبک‌تر و کم‌هزینه‌تر می‌شوند.
  • سطح 2: قاعده‌ی حل تساوی (tie rule) از چه چیزی محافظت می‌کند؟ پاسخ مورد انتظار: بازتولیدپذیری (reproducibility)؛ پیکره متنی یکسان باید روی هر سیستمی دقیقاً همان فهرست merge را تولید کند.
  • سطح 3: اگر دو کلمه پس از یک گام ادغام، به تاپل یکسانی تبدیل شوند، دیکشنری جدید چه کاری باید انجام دهد؟ پاسخ مورد انتظار: باید بسامدهای آن‌ها را با هم جمع کند، نه اینکه فقط آخرین کلمه را نگه دارد.
  • سطح 3: اندازه‌ی واژگان (vocabulary size) چه ارتباطی با تعداد mergeها دارد؟ پاسخ مورد انتظار: بلوک بایت‌های پایه‌ای، به‌علاوه‌ی یک شناسه به ازای هر merge، به‌علاوه‌ی شناسه‌های رزرو‌شده‌ی ویژه.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «هر جفت را به ازای هر کلمه فقط یک‌بار بشمارید.» وزن‌دهی بر اساس بسامد دقیقاً همان سازوکاری است که باعث می‌شود جفت‌های رایج زودتر برنده شوند.
  • «اولین جفتی را که بیشترین شمارش را دارد انتخاب کنید.» ترتیب دیکشنری در ورودی‌های مختلف پایدار نیست، بنابراین توکنایزر بازتولیدناپذیر خواهد شد.
  • «ادغام را تا زمانی که بودجه مصرف شود ادامه دهید.» جفتی که تنها یک‌بار دیده شده هیچ سودی ندارد و جایگاه‌های واژگان را هدر می‌دهد.

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

درس BPE از صفر حلقه‌ی آموزش و قرارداد جدول ادغام (merge table) را بررسی می‌کند، درس توکنایزرها مراحل ادغام را به‌صورت دستی دنبال می‌کند، و تمرین BPE قاعده‌ی تساوی و قاعده‌ی توقف (stop rule) را ارزیابی می‌کند.