سؤال مصاحبه

چرا انکودر فهرست mergeها را به ترتیب بازپخش می‌کند؟

Why the encoder replays the merge list in order

  • سطح ۲: میانی
  • مفهومی
  • ۸ دقیقه

هنگام کدگذاری (encode)، توکن‌ساز BPE کل جدول ادغام (merge table) را در اختیار دارد. چرا باید mergeها را دقیقاً به همان ترتیبی که یاد گرفته است بازپخش (Replay) کند، و اگر دو merge بتوانند در یک نقطه اعمال شوند چه مشکلی پیش می‌آید؟

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

پاسخ کوتاه

فرایند انکود کردن باید دقیقاً همان رفتاری را روی متن بازتولید کند که در زمان آموزش انجام شده است؛ و فرایند آموزش، mergeها را یکی‌یکی و دقیقاً با همان ترتیب دیده است. اگر merge اول ترکیب «th» را ساخته باشد و merge پنجم با ترکیب «th» و «e» عبارت «the» را بسازد، «the» فقط زمانی می‌تواند شکل بگیرد که «th» از قبل وجود داشته باشد. وقتی دو merge بتوانند در یک موقعیت اعمال شوند، آن موردی برنده می‌شود که رتبه‌ی (Rank) پایین‌تری دارد و زودتر یاد گرفته شده است. اگر این قاعده را تغییر دهید، همان متن شناسه‌های متفاوتی تولید می‌کند؛ در نتیجه مدل با توزیعی از شناسه‌ها روبه‌رو می‌شود که هرگز روی آن‌ها آموزش ندیده است.

پاسخ کامل

انکودر ساده‌لوحانه (Naive)

def encode_bpe(word, merges):
    symbols = list(word) + ["</w>"]
    for a, b in merges:
        i = 0
        while i < len(symbols) - 1:
            if symbols[i] == a and symbols[i + 1] == b:
                symbols = symbols[:i] + [a + b] + symbols[i + 2:]
            else:
                i += 1
    return symbols

این انکودر کل جدول را به ازای تک‌تک کلمات پیمایش می‌کند؛ بنابراین هزینه‌ی محاسباتی آن برابر با طول کلمه ضرب در تعداد mergeهاست. این روش برای جدول ادغامی که روی کاراکترها آموزش دیده درست کار می‌کند، اما کند است.

انکودر مبتنی بر رتبه

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

چرا این قاعده اصلِ قرارداد است؟

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

نقش توکن‌های ویژه در اینجا

رشته‌های رزروشده، مثل نشانگر پایان متن (end-of-text)، پیش از اجرای حلقه‌ی ادغام به‌طور دقیق تطبیق داده می‌شوند و به شناسه‌های ثابتی نگاشت می‌شوند. این رشته‌ها هرگز در هیچ ادغامی شرکت نمی‌کنند؛ بنابراین هیچ ترتیبی در جدول نمی‌تواند آن‌ها را تفکیک کند یا پیوند دهد.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: چرا حلقه‌ی ساده‌لوحانه کند است؟ پاسخ مورد انتظار: کل جدول ادغام را برای هر کلمه پیمایش می‌کند؛ بنابراین هزینه‌ی آن متناسب با اندازه‌ی جدول ضرب در طول کلمه افزایش می‌یابد.
  • سطح 3: انکودرهای محیط عملیاتی چطور به زمان اجرای نزدیک به خطی می‌رسند؟ پاسخ مورد انتظار: با جست‌وجوی رتبه برای هر جفت مجاور و استفاده از یک صف اولویت‌دار که همیشه ادغام قابل‌اعمال با کمترین رتبه را در دسترس قرار می‌دهد.
  • سطح 3: دو توکن‌ساز روی مجموعه‌داده‌های متفاوتی با اندازه‌ی واژگان (Vocabulary size) یکسان آموزش دیده‌اند. آیا شناسه‌های یکسانی تولید می‌کنند؟ پاسخ مورد انتظار: خیر؛ مجموعه‌داده‌های متفاوت، جداول ادغام و رتبه‌های متفاوتی تولید می‌کنند.
  • سطح 3: چه تستی ترتیب ادغام را تثبیت می‌کند؟ پاسخ مورد انتظار: انکود کردن یک کلمه‌ی نگه‌داشته‌شده (Held-out) و مقایسه‌ی آن با شناسه‌های ذخیره‌شده؛ تست‌های پروژه‌ی پایانی رفت‌وبرگشت کامل (round trip) و رزرو توکن‌های ویژه را هم تثبیت می‌کنند.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «به‌صورت حریصانه طولانی‌ترین توکن منطبق موجود در واژگان را انتخاب کنید.» این یک الگوریتم متفاوت است و تقطیعی متفاوت با اجرای زمان آموزش ایجاد می‌کند.
  • «ترتیب اهمیتی ندارد چون ادغام‌ها جابه‌جایی‌پذیر هستند.» یک ادغامِ دیرتر به نمادهایی وابسته است که ادغام‌های قبلی ساخته‌اند؛ بنابراین خاصیت جابه‌جایی‌پذیری ندارند.
  • «ادغام‌ها را بر اساس طول توکن مرتب کنید.» طول توکن همان رتبه نیست؛ یک قطعه‌ی طولانی ممکن است خیلی زود یاد گرفته شده باشد و یک قطعه‌ی کوتاه در مراحل پایانی.

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

درس توکن‌سازها جدول مرتب‌شده را توضیح می‌دهد، پروژه‌ی پایانی BPE انکودر مبتنی بر رتبه را پیاده‌سازی می‌کند، و درس زیرکلمه (Subword) حلقه‌ی ساده‌لوحانه و هزینه‌ی آن را شرح می‌دهد.