آیا gzip می تواند یک مدل زبان باشد؟

مدتی قبل درباره مدل‌سازی زبان بدون شبکه‌های عصبی نوشتم، جایی که شکسپیر را با یک مدل n-gram نامحدود ایجاد کردم: بدون وزن، بدون آموزش، فقط شمارش. تصادفا با مقاله Language Modeling is Compression مواجه شدم که معادل فشرده سازی-پیش بینی را ذکر کرده است:

هر مدل پیش‌بینی ذاتا یک کمپرسور است و همه الگوریتم‌های فشرده‌سازی مدل‌های پیش‌بینی هستند.

این منجر به این سوال طبیعی شد: آیا gzip می تواند مدل سازی زبان را انجام دهد؟ 1 بدون شبکه عصبی، بدون پارامترهای آموخته شده، هیچ چیز. فقط کمپرسوری که با سیستم عامل شما عرضه می شود. شما آن را با یک پیکره اولیه می‌نویسید، به آن یک پیام متنی معمولی می‌دهید، و با جستجوی دنباله‌های بایتی که به بهترین شکل فشرده می‌شوند، آن دستور را ادامه می‌دهد. در اینجا برخی از خروجی های واقعی و ویرایش نشده پس از آماده سازی آن در شکسپیر کوچک آورده شده است:

معلوم است، نوعی؟ این متن دقیقا منسجم نیست، اما به وضوح چیزی در مورد متن می داند. خیلی بیشتر از چیزی که انتظار داشتم gzip بداند. 2 پس چگونه یک کمپرسور می تواند این را ایجاد کند؟

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

این تصادفی نیست؛ این هسته نظریه اطلاعات است. تعداد بیت های مورد نیاز برای رمزگذاری یک نماد $-\log_2 p$ است که $p$ احتمالی است که مدل به آن اختصاص می دهد. احتمال زیاد یعنی چند بیت. بنابراین هر کمپرسوری دارای یک مدل احتمالی است که در داخل آن پنهان شده است، چه کسی آن را نوشته باشد یا نه.

gzip از DEFLATE استفاده می کند که با پیدا کردن مطابقت با متن اخیر در یک پنجره کشویی 32 کیلوبایتی، بایت های بعدی را فشرده می کند. اگر ادامه مطلبی را در پنجره بازتاب دهد، DEFLATE آن را به‌جای بایت‌های تحت اللفظی، به‌عنوان یک مرجع برگشتی ارزان رمزگذاری می‌کند. بنابراین:

ادامه‌ای که gzip «انتظار» آن را داشت، زیرا متنی را که قبلا در پنجره‌اش بازتاب می‌دهد، تقریبا به هیچ‌وجه فشرده نمی‌شود.

این به ما نمره می دهد. اگر زمینه ای داشته باشم و بخواهم بدانم که ادامه نامزد چقدر خوب است، فقط اندازه گیری می کنم:

هرچه طول فشرده‌شده کمتر باشد، کاندید «پیش‌بینی»‌تر است. برای آماده‌سازی مدل، یک پیکره را در پنجره gzip قرار می‌دهم. هر ادامه‌ای که به نظر می‌رسد جسم کوچک را فشرده می‌کند، و هر ادامه‌ای که بزرگ را فشرده نمی‌کند.

گلزنی یک چیز است. تولید چیز دیگری است. رویکرد ساده لوحانه انتخاب تک بایت بعدی که به بهترین وجه فشرده می‌شود، به شدت شکست می‌خورد، و به یک دلیل ظریف: gzip فقط طول بایت عدد صحیح (بدون کسری) می‌دهد. افزودن یک بایت اغلب طول فشرده شده را تغییر نمی دهد، بنابراین بسیاری از کاندیدها به هم متصل می شوند و سیگنال در نویز کوانتیزاسیون مدفون می شود.

راه حل این است که قبل از انجام تعهد، یک دوره کامل را به جلو نگاه کنید. gzipt یک جستجوی پرتویی را روی توالی بایت انجام می دهد. در هر مرحله، زمینه فعلی به شرح زیر است:

سپس gzipt بایت های بعدی ممکن را امتحان می کند. هر ادامه نامزد با فشرده سازی متن + نامزد و بررسی چند بایت نتیجه فشرده امتیازدهی می شود.

یکی از جزئیات مهم این است که تنها آخرین بایت های دنباله خروجی تولید شده در زمینه امتیازدهی باقی می مانند. کدهای DEFLATE نزدیک‌تر با کدهای دور مطابقت دارند، بنابراین اگر gzip بتواند کل تاریخچه خود را ببیند، ارزان‌ترین کار اغلب این است که در حلقه‌های کلمه به کلمه قرار بگیریم، و مکررا متنی را که منتشر کرده‌ایم کپی کنیم.

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

مقاله این را امتحان کرد، اما در نهایت عملکرد ضعیفی داشت. افزودن جستجوی پرتو به طور قابل توجهی کیفیت تولید را بهبود بخشید (ایده ای که آنها ذکر کردند)، که در زیر مورد بحث قرار می گیرد. ↩︎

کد در واقع از zlib به جای ایجاد فرآیند gzip استفاده می کند، اما نام GziPT خیلی خوب بود. من معتقدم که هر دو از یک الگوریتم DEFLATE در زیر کاپوت استفاده می کنند. ↩︎