سؤال مصاحبه

پروژه ارزیابی مهندسی: پیاده‌سازی توکنایزر سطح بایت همراه با تست‌ها

Take-home, a byte-level tokenizer with tests

  • سطح ۳: ارشد
  • پروژه‌ی خانگی
  • ۱۵ دقیقه

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

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

پاسخ کوتاه

شناسه‌های 0 تا 255 را به بایت‌های خام و یک بلوک کوچک بعد از آن‌ها را به نشانگرهای پایان متن (end-of-text) و فاصله‌گذاری (pad) اختصاص دهید. پیکره متنی (corpus) را بر اساس فاصله‌ها و علائم نگارشی بخش‌بندی (split) کنید. در مرحله‌ی آموزش، جفت‌های مجاور را با وزن‌دهی بر اساس بسامد کلمات بشمارید و جفت دارای بالاترین بسامد را با یک مساوی‌شکنی (tie-break) قطعی (deterministic) merge کنید. برای انکود، پایین‌ترین رتبه (rank) merge قابل‌اعمال را آن‌قدر به کار بگیرید تا دیگر هیچ mergeای نخورد. برای رمزگشایی، بایت‌های گسترش‌یافته را به هم متصل کنید و در پایان فقط یک بار کل رشته را با UTF-8 رمزگشایی کنید. تست‌ها بازگشت‌پذیری (round-trip) کاملاً دقیق روی سطح بایت را برای یک جمله‌ی دیده‌نشده، یک ایموجی و رشته‌ی عینی توکن ویژه (در دو حالت فعال و غیرفعال بودن فلگ allow) ارزیابی می‌کنند؛ علاوه‌بر این، ترتیب صحیح merge و وضعیت شناسه‌های رزروشده نیز بررسی می‌شوند. نمودار انتخابی، منحنی فشرده‌سازی است: طول رشته‌ی انکودشده برای یک جمله‌ی نگه‌داشته‌شده (held-out) هم‌گام با افزایش اندازه‌ی واژگان (vocabulary size) هدف از 300 به 600.

پاسخ کامل

طرح سیستم

ids 0..255        raw bytes
next few ids      <|endoftext|>, <|pad|>
then              one id per merge, in training order
  • بایت‌های ورودی را دست‌نخورده نگه دارید تا بازگشت‌پذیری روی سطح بایت دقیق بماند. نرمال‌سازی‌های تطبیقی (compatibility normalization) خط‌پیوندها (ligatures) یا حروف با عرض کامل (fullwidth) را به فرم ساده تبدیل می‌کنند و اتلاف اطلاعات دارند (lossy هستند)؛ بنابراین تنها در صورتی این نرمال‌سازی را اضافه کنید که در گزارش قید شده باشد تضمین بازگشت‌پذیری صرفاً مختص متن نرمال‌شده است.
  • متن را بر اساس کلمات و علائم نگارشی پیش‌بخش‌بندی (pre-split) کنید تا فرآیند merge درون مرزهای یک کلمه باقی بماند؛ استفاده از الگوی عبارات باقاعده (regex) توکنایزرهای بزرگ محیط عملیاتی (production)، یک افزونه‌ی اختیاری به حساب می‌آید.
  • آموزش: جفت‌های مجاور را در کل پیکره متنی بخش‌بندی‌شده و با وزن‌دهی بر اساس بسامد کلمات بشمارید؛ جفت برتر را با تخصیص اولین شناسه‌ی آزاد merge کنید، عملیات merge را ثبت کرده و این کار را تا رسیدن به اندازه‌ی واژگان هدف تکرار کنید. در صورت برابری بسامد، مساوی‌شکنی را بر اساس خودِ جفت بایت انجام دهید تا دو بار اجرای الگوریتم روی داده‌ی یکسان، جدول کاملاً مشابهی تولید کند.
  • انکود: در صورت روشن بودن فلگ allow، ابتدا تطابق دقیق توکن‌های ویژه را بررسی کنید؛ برای متن‌های معمولی، کار را از بایت‌ها شروع کرده و پیاپی پایین‌ترین رتبه‌ی mergeهای قابل‌اعمال را پیاده کنید.
  • رمزگشایی: شناسه‌های ویژه به رشته‌های نشانگر خود و بقیه‌ی شناسه‌ها به بایت‌هایشان نگاشت می‌شوند؛ تمام بایت‌ها را به هم بچسبانید، سپس فقط یک بار فرآیند رمزگشایی را انجام دهید و برای کاراکتر ناقص انتهای رشته از کاراکتر جایگزین (replacement character) استفاده کنید.

تست‌ها

  1. بازگشت‌پذیری روی جمله‌ای که توکنایزر هرگز ندیده است.
  2. بازگشت‌پذیری روی جمله‌ای حاوی ایموجی، که در آن ممکن است 4 بایت تشکیل‌دهنده‌ی کاراکتر در چند توکن پخش (اسپن / span) شوند.
  3. بازگشت‌پذیری روی جمله‌ای شامل متن عینی رشته‌ی پایان متن؛ با خاموش بودن فلگ به بایت‌های عادی تبدیل شود و با روشن بودن فلگ به شناسه‌ی رزروشده نگاشت گردد.
  4. ترتیب merge: یک کلمه‌ی نگه‌داشته‌شده دقیقاً به شناسه‌های ثبت‌شده انکود شود، در حالی که با جدولی که ترتیب آن به هم خورده است چنین نشود.
  5. شناسه‌های رزروشده هرگز به‌عنوان مقصد merge ظاهر نشوند و با شناسه‌ی بایت‌ها تداخل نداشته باشند.
  6. قطعی بودن: دو بار اجرای آموزش روی یک پیکره متنی یکسان، جدولی کاملاً مشابه بدهد.

نمودار

مدل را تا چندین اندازه‌ی واژگان هدف آموزش دهید، همان جمله‌ی نگه‌داشته‌شده را هر بار انکود کنید و تعداد توکن‌ها را در برابر اندازه‌ی واژگان رسم کنید. با طولانی‌تر شدن بخش‌های تحت پوششِ هر merge، تعداد توکن‌ها افت می‌کند. خط دومی که نشان‌دهنده‌ی نسبت فشرده‌سازی (compression ratio) است (تعداد توکن‌ها تقسیم بر تعداد بایت‌های ورودی، که 0.50 یعنی تعداد توکن‌ها نصف بایت‌هاست)، همین روند را با واحدی نشان می‌دهد که در پیکره‌های مختلف نیز قابل مقایسه و انتقال است.

معیارهای ارزیابی مصحح

صحت بازگشت‌پذیری، قطعی بودن فرآیند، تفکیک تمیز مسیر توکن‌های ویژه از مسیر merge، کیفیت تست‌ها و گزارشی که باگی را که داوطلب در پیاده‌سازی با آن مواجه شده به صراحت نام ببرد. سرعت در این مرحله ارزیابی نمی‌شود: اجرای Python در این مقیاس بسیار کمتر از یک ثانیه زمان می‌برد و کتابخانه‌های محیط عملیاتی که با زبان‌های کامپایلری نوشته شده‌اند، همین الگوریتم را 10 تا 100 برابر سریع‌تر اجرا می‌کنند.

سؤال‌های تکمیلی مصاحبه‌گر
  • سطح 2: چرا بایت‌های خام پیش از هر چیز شناسه‌های 0 تا 255 را به خود اختصاص می‌دهند؟ پاسخ مورد انتظار: به این ترتیب هر ورودی پیش از تعریف هرگونه merge، با واژگان موجود قابل بیان است و هیچ کاراکتری ناشناخته باقی نمی‌ماند.
  • سطح 3: ورودی، نشانگر پایان متن را به شکل متن ساده می‌آورد. فلگ allow چه تغییری ایجاد می‌کند؟ پاسخ مورد انتظار: در حالت خاموش، این رشته بایت‌ها و تکه‌های عادی در نظر گرفته می‌شود؛ در حالت روشن، به شناسه‌ی رزروشده نگاشت شده و حلقه‌ی merge از روی آن عبور می‌کند.
  • سطح 3: چرا مساوی‌شکنی در بسامد جفت‌ها باید قطعی باشد؟ پاسخ مورد انتظار: دو بار اجرای کد روی یک پیکره متنی یکسان باید جدول کاملاً یکسانی تولید کند، وگرنه متنی یکسان روی سیستم‌های مختلف شناسه‌های متفاوتی می‌گیرد.
  • سطح 4: بخش‌بندی ساده را با الگوی regex محیط عملیاتی جایگزین کنید. چه مواردی را با هم مقایسه می‌کنید؟ پاسخ مورد انتظار: واژگان و طول رشته‌های انکودشده روی یک پیکره متنی یکسان، با بررسی چگونگی مدیریت فرم‌های مخفف (contractions)، ارقام و فاصله‌های ابتدای کلمات.
جواب‌های اشتباهی که مصاحبه‌گرها زیاد می‌شنوند
  • «استفاده از نقاط کد یونیکد (Unicode code points) به‌عنوان نمادهای پایه.» تعداد نقاط کد به صدها هزار مورد می‌رسد و برای کاراکترهای دیده‌نشده جای خالی باقی می‌گذارند؛ در حالی که بایت‌ها 256 عدد هستند و پوشش کاملی دارند.
  • «رمزگشایی هر توکن به رشته و سپس اتصال رشته‌ها به یکدیگر.» یک توکن ممکن است فقط بخشی از یک کاراکتر چندبایتی را در بر بگیرد؛ ابتدا باید بایت‌ها را به هم پیوند داد و در پایان فقط یک بار رمزگشایی کرد.
  • «حذف مرحله‌ی پیش‌بخش‌بندی برای دستیابی به فشرده‌سازی بهتر.» در این حالت، مرزهای کلمات با merge شکسته می‌شوند و واژگان با عباراتی پر می‌شود که به متون دیگر تعمیم‌پذیر نیستند.

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

پروژه‌ی پایانی BPE به طراحی ساختار، توکن‌های ویژه و تست‌ها می‌پردازد؛ درس ساخت توکنایزر نرمال‌سازی و کار با regex را اضافه می‌کند و درس توکنایزرها به تعریف نسبت فشرده‌سازی اختصاص دارد.