ساخت یک BPE Tokenizer: چرا مدل شما تعداد Rها را نمی‌شمارد

دو راه بدیهی برای خوراندن متن به یک شبکه وجود دارد و هر دو به دلایلی شکست می‌خورند که ارزش فهمیدن دارند، چون همین شکست شکل راه‌حل را تعیین می‌کند.

واژه‌ها. متن را بر اساس فاصله‌ها جدا کنید و به هر واژه یک عدد بدهید. انگلیسی صدها هزار شکل واژگانی دارد و مدل برای هرکدام به یک ردیف embedding نیاز دارد، پس واژگان — و لایه خروجی، که باید برای هر مدخل یک امتیاز تولید کند — عظیم می‌شود. بدتر از آن چیزی است که هنگام inference رخ می‌دهد: واژه‌ای که مدل هرگز در آموزش ندیده عددی ندارد. این همان مسئله out-of-vocabulary است، و وصله رایج این است که هر چیز ناشناخته را به یک token واحد <UNK> نگاشت کنیم، که اطلاعات را دور می‌ریزد. همچنین «واژه» مفهوم دقیق و خوش‌تعریفی نیست: چینی و ژاپنی بین واژه‌ها فاصله نمی‌گذارند، و آلمانی می‌تواند اسم‌ها را بی‌انتها به هم بچسباند.

نویسه‌ها. مسئله out-of-vocabulary وجود ندارد، و واژگان فقط حدود صد نماد دارد. اما دنباله‌ها بسیار طولانی می‌شوند، و فصل 9 نشان خواهد داد که هزینه attention با طول دنباله به‌صورت درجه‌دو رشد می‌کند. یک سند 1000 واژه‌ای حدود 5000 نویسه دارد — دنباله‌ای چهار تا پنج برابر طولانی‌تر از چیزی که لازم است، با هزینه‌ای درجه‌دو. و هر نویسه به‌تنهایی تقریباً هیچ معنایی حمل نمی‌کند، پس چند لایه اول صرف بازسازی واژه‌هایی می‌شوند که tokenizer می‌توانست سالم تحویل بدهد.

پاسخ بین این دو است: زیرواژه‌ها. واژه‌های رایج به یک token تبدیل می‌شوند، واژه‌های نادر به تکه‌ها شکسته می‌شوند، و هیچ‌چیز هرگز ناشناخته نیست چون تکه‌ها در نهایت به byteهای منفرد می‌رسند. نکته جالب این است که هیچ‌کس این برش را طراحی نمی‌کند. tokenizer آموزش می‌بیند، روی همان نوع داده‌ای که مدل می‌بیند، و با شمردن اینکه کدام دنباله‌های byte بیشتر کنار هم رخ می‌دهند یاد می‌گیرد کدام‌ها ارزش عدد اختصاصی دارند.

این الگوریتم متعلق به 1994 است، و یک الگوریتم فشرده‌سازی بود. Philip Gage آن را در C Users Journal منتشر کرد، به‌عنوان روشی برای کوچک‌کردن فایل‌ها با جایگزینی مکرر پرتکرارترین جفت byteهای مجاور با byteای که در داده وجود ندارد.¹ بیست‌ودو سال آنجا ماند تا اینکه Sennrich، Haddow و Birch در 2016 آن را برای ترجمه ماشینی بازاستفاده کردند تا مسئله out-of-vocabulary را حل کنند.² اکنون عملاً هر مدل زبانی بزرگ با همین روش می‌خواند.

حلقه آموزش چهار مرحله تکرارشونده دارد:

این کل trainer است:

def get_stats(ids):
    counts = {}
    for a, b in zip(ids, ids[1:]):
        counts[(a, b)] = counts.get((a, b), 0) + 1
    return counts


def merge(ids, pair, idx):
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and ids[i] == pair[0] and ids[i + 1] == pair[1]:
            out.append(idx)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out


class BPE:
    def __init__(self):
        self.merges = {}
        self.vocab = {i: bytes([i]) for i in range(256)}

    def train(self, text, vocab_size):
        ids = list(text.encode("utf-8"))
        for i in range(vocab_size - 256):
            stats = get_stats(ids)
            if not stats:
                break
            pair = max(stats, key=stats.get)      
            idx = 256 + i                         
            ids = merge(ids, pair, idx)           
            self.merges[pair] = idx               
            self.vocab[idx] = self.vocab[pair[0]] + self.vocab[pair[1]]
        return ids

آن را روی 151,191 byte نثر انگلیسی اجرا کنید و دوازده ادغام اول را همان‌طور که رخ می‌دهند چاپ کنید. این بخشی است که ارزش دارد آهسته خوانده شود، چون هیچ‌کس چیزی درباره انگلیسی به الگوریتم نگفته بود:

merge   1: b'e' + b' '   -> b'e '     (occurred 4433 times)
merge   2: b' ' + b't'   -> b' t'     (occurred 3302 times)
merge   3: b'\xe2' + b'\x80' -> b'\xe2\x80'  (occurred 3247 times)
merge   4: b' ' + b'a'   -> b' a'     (occurred 2335 times)
merge   5: b' t' + b'h'  -> b' th'    (occurred 2253 times)
merge   6: b'i' + b'n'   -> b'in'     (occurred 2011 times)
merge   7: b't' + b' '   -> b't '     (occurred 1904 times)
merge   8: b'e' + b'r'   -> b'er'     (occurred 1813 times)
merge   9: b'd' + b' '   -> b'd '     (occurred 1703 times)
merge  10: b'o' + b'u'   -> b'ou'     (occurred 1554 times)
merge  11: b' ' + b's'   -> b' s'     (occurred 1467 times)
merge  12: b' th' + b'e '-> b' the '  (occurred 1270 times)

سه چیز در آن فهرست ارزش اشاره دارند.

ادغام 12 واژه «the» است — با فاصله پیش از آن و فاصله پس از آن، به‌صورت یک واحد واحد، که در تکرار دوازدهم حلقه‌ای کشف شده که فقط جفت‌ها را می‌شمارد. هیچ‌کس فرهنگ لغت نداده است. آنجا هست چون این پنج byte بیش از هر پنج byte دیگری در انگلیسی با هم رخ می‌دهند.

ادغام 3 اصلاً متن نیست. \xe2\x80 دو byte اول رمزگذاری UTF-8 برای نشانه‌گذاری تایپوگرافیک است — خط تیره بلند، نقل‌قول‌های خمیده. الگوریتم هیچ تصوری از وجود UTF-8 ندارد، و همین حالا بخشی از ساختار آن را دوباره کشف کرده است، چون رمزگذاری‌های چند byteای بنا به ساختارشان دنباله‌هایی از byteها هستند که همیشه با هم ظاهر می‌شوند.

بیشتر ادغام‌های اولیه شامل یک فاصله‌اند، و فاصله معمولاً در چپ است. این منشأ یکی از گیج‌کننده‌ترین رفتارها در عمل است، که کمی بعد به آن برمی‌گردیم.

هر ادغام دنباله را کوتاه‌تر و واژگان را بزرگ‌تر می‌کند. اینکه تا کجا آن را پیش ببرید یک تصمیم واقعی است، و می‌توان آن را اندازه گرفت — اینجا روی همان 151,191 byte:

بازده نزولی، کاملاً آشکار. دو برابر کردن از 512 به 1024 معادل 0.78 byte به‌ازای هر token می‌خرد؛ دو برابر کردن از 2048 به 4096 معادل 1.07 می‌خرد — اینجا بهتر است فقط چون این پیکره آن‌قدر کوچک است که ادغام‌های بلندتر هنوز صرفه دارند. روی یک پیکره واقعی، منحنی به‌شدت تخت می‌شود.

و هزینه واژگان بزرگ‌تر فقط حافظه نیست. هر token به یک ردیف embedding نیاز دارد، و — پرهزینه‌تر — لایه خروجی مدل باید در هر گام برای هر مدخل واژگان یک امتیاز تولید کند، پس ضرب ماتریسی نهایی با اندازه واژگان مقیاس می‌گیرد. مدل‌های واقعی بین 32,000 و 200,000 قرار دارند: GPT-2 از 50,257 استفاده می‌کرد، cl100k در GPT-4 از 100,277 استفاده می‌کند، و o200k در GPT-4o تقریباً آن را دو برابر می‌کند. روند صعودی است، و دلیلش در بخش بعدی است.

این همان پاراگراف است، ترجمه‌شده، و با tokenizerهای واقعی‌ای که OpenAI عرضه می‌کند اندازه‌گیری شده:

همان محتوا، همان معنا، و با cl100k نسخه روسی دو و نیم برابر token مصرف می‌کند. از آنجا که APIها بر اساس token هزینه می‌گیرند و context windowها با token اندازه‌گیری می‌شوند، این یک کنجکاوی زبانی نیست — هم‌زمان یک ردیف در بودجه، یک context window مؤثر کوتاه‌تر، و پاسخ کندتر است، برای هر کسی که به انگلیسی کار نمی‌کند.

سازوکارش داده آموزشی است. tokenizerی که عمدتاً روی انگلیسی آموزش دیده بودجه ادغام خود را روی دنباله‌های byte انگلیسی خرج می‌کند. اسپانیایی الفبای لاتین را به اشتراک می‌گذارد، پس هنوز کمی بهره می‌برد؛ روسی تقریباً هیچ بهره‌ای نمی‌برد، چون نویسه‌های سیریلیک در UTF-8 دو byte می‌گیرند و تعداد کمی از آن جفت‌ها در پیکره آموزشی آن‌قدر رایج بوده‌اند که ادغام دریافت کنند. ژاپنی از این هم بدتر است: سه byte برای هر نویسه، و 72 نویسه به 79 token تبدیل می‌شود — tokenهای بیشتر از نویسه‌ها.

ستون o200k نشان می‌دهد این مسئله قابل حل است و در حال حل شدن است. دو برابر کردن واژگان و متوازن‌سازی دوباره داده آموزشی، سربار اسپانیایی را از +39 % به +16 % و روسی را از +152 % به +39 % کاهش می‌دهد. دلیل واقعی رشد پیوسته واژگان همین است: نه فشرده‌سازی برای خود فشرده‌سازی، بلکه این واقعیت که نسل قبلی بی‌سروصدا بخش بزرگی از جهان را بیشتر شارژ می‌کرد.

آموزش یک فهرست مرتب از ادغام‌ها تولید کرد. encode کردن متن تازه آن را بازپخش می‌کند — و باید آن را به همان ترتیب بازپخش کند، چون ادغام 12 نتایج ادغام‌های 5 و 1 را ترکیب می‌کند. اگر آن‌ها را به ترتیب دیگری اعمال کنید، tokenization متفاوت و غلطی به دست می‌آورید که با هیچ‌چیزی که مدل در آموزش دیده سازگار نیست.

    def encode(self, text):
        ids = list(text.encode("utf-8"))
        while len(ids) >= 2:
            stats = get_stats(ids)
            # the pair whose merge came FIRST during training wins   
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))   
            if pair not in self.merges:
                break
            ids = merge(ids, pair, self.merges[pair])
        return ids

    def decode(self, ids):
        return b"".join(self.vocab[i] for i in ids).decode("utf-8", errors="replace")

Decoding در مقایسه با آن ساده است: byteهای هر id را نگاه کنید، به هم بچسبانید، و به‌صورت UTF-8 decode کنید. به errors="replace" توجه کنید: مدل می‌تواند دنباله‌ای از tokenها بیرون بدهد که وسط یک نویسه تمام می‌شود، و این فرضی نیست — وقتی پاسخ streaming وسط یک ایموجی قطع می‌شود دقیقاً همین رخ می‌دهد، و به همین دلیل APIهای streaming به‌جای decode کردن token به token، byteهای جزئی را buffer می‌کنند.

رفت‌وبرگشت روی هر چیزی کار می‌کند، و این وعده BPE در سطح byte است:

'strawberry'                            -> 6 tokens, decode == original: True
'Alice was beginning to get very tired' -> 14 tokens, decode == original: True
'café — naïve — 日本語'                   -> 23 tokens, decode == original: True

وقتی سازوکار روشن شود، مجموعه‌ای از شکایت‌های ظاهراً نامرتبط معلوم می‌شود همان شکایت واحدند.

حساب. عددها به هیچ روش سازگاری شکسته نمی‌شوند:

1234     -> 2 tokens  ['123', '4']
12345    -> 2 tokens  ['123', '45']
1000000  -> 3 tokens  ['100', '000', '0']
3.14159  -> 4 tokens  ['3', '.', '141', '59']
2024     -> 2 tokens  ['202', '4']

برای جمع کردن 1234 و 12345 مدل باید اول بفهمد ['123','4'] و ['123','45'] عددهایی هستند که رقم‌هایشان به شیوه‌ای خاص هم‌تراز می‌شوند — و این هم‌ترازی برای هر جفت عدد فرق می‌کند. رقم‌های یک عدد از عددی به عدد دیگر در جای یکسانی نیستند. برخی tokenizerهای جدیدتر دقیقاً برای برداشتن همین مانع، رقم‌ها را مجبور می‌کنند به گروه‌های سه‌تایی سازگار شکسته شوند، و مدل‌هایی که با آن‌ها آموزش دیده‌اند در حساب به‌طور قابل اندازه‌گیری بهترند.

تورفتگی Python.

'    x = 1'      -> 5 tokens  ['   ', ' x', ' =', ' ', '1']
'        x = 1'  -> 5 tokens  ['       ', ' x', ' =', ' ', '1']
'\tx = 1'        -> 4 tokens  ['\tx', ' =', ' ', '1']

چهار فاصله و هشت فاصله tokenهای منفرد متفاوتی هستند، و tab با نویسه پس از خود ادغام شده است. تورفتگی، که در Python نحو محسوب می‌شود، به‌صورت ناسازگار نمایش داده می‌شود — و این بخش بزرگی از دلیل آن بود که مدل‌ها قبلاً Python را با تورفتگی‌های ظریفاً غلط تولید می‌کردند، و اینکه چرا tokenizerهای متمرکز بر کد tokenهای صریحی برای دنباله‌های رایج تورفتگی اضافه می‌کنند.

املا و وارونه‌سازی. همان علت شمارش rها: درخواست از مدل برای وارونه کردن strawberry یعنی درخواست برای بازآرایی حروف داخل سه id مات. مدل‌ها این کار را با حفظ کردن املاها در طول آموزش انجام می‌دهند، نه با نگاه کردن، و به همین دلیل برای واژه‌های رایج خوب و برای واژه‌های نادر بد انجامش می‌دهند.

Glitch tokenها. چشمگیرترین نمونه SolidGoldMagikarp و مجموعه‌ای از رشته‌های مشابه است که باعث می‌شدند GPT-2 و GPT-3 رفتارهای عجیبی نشان دهند — از تکرارشان سر باز بزنند، خروجی نامرتبط تولید کنند، و گاهی به کاربر توهین کنند. توضیح پیش‌پاافتاده است و مستقیم از این واقعیت می‌آید که tokenizer جدا از مدل آموزش می‌بیند: آن رشته‌ها در پیکره آموزشی tokenizer پرتکرار بودند (نام‌های کاربری Reddit بودند)، پس token اختصاصی خود را گرفتند، اما در پیکره آموزشی مدل نادر یا غایب بودند. نتیجه یک ردیف embedding است که تصادفی مقداردهی اولیه شده و تقریباً هرگز به‌روزرسانی نشده. مدل نمادی دارد که عملاً هرگز آن را ندیده، و رفتارش آنجا هر چیزی است که مقداردهی اولیه تصادفی از آب درآمده باشد.

tokenizer یک رابط زیان‌دار میان متن و عددهاست، و هر رفتار عجیبی در این فصل، خودِ رابط است که از پشت پرده بیرون زده. ارزش دارد روشن بگوییم این معامله عمدی است: BPE در سطح byte یعنی هیچ ورودی‌ای هرگز غیرقابل نمایش نیست، دنباله‌ها چهار تا پنج برابر کوتاه‌تر از حالت نویسه‌ای‌اند، و واژه‌های رایج سالم وارد می‌شوند.

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

اکنون شما یک دنباله از اعداد صحیح دارید. این قالب ورودی برای همه چیز در باقی بخش II است.

چیزی که ندارید، هیچ دلیلی است برای اینکه یک عدد پس از عدد دیگر بیاید. فصل بعد هدفی را معرفی می‌کند که هر مدل زبانی بر اساس آن آموزش می‌بیند، و به‌طرز شگفت‌آوری ساده است: با داشتن tokenهای تا اینجا، token بعدی را پیش‌بینی کن. همین هدف واحد — بدون برچسب، بدون annotation، فقط متن با آینده خودش به‌عنوان target — چیزی است که کل اینترنت را به داده آموزشی تبدیل می‌کند، و جایی است که نخستین بازنمایی‌های واقعاً معنادار مدل از آن می‌آیند.

این همچنین نیاز دارد قاعده زنجیره‌ای احتمال از فصل 2 دقیقاً درست باشد، چون ادعای اینکه پیش‌بینی یک token در هر زمان همان مدل‌سازی کل اسناد است، یک تجزیه است، نه استعاره.

فصل 8 هدف autoregressive، embeddings، و نخستین جایی است که مدل چیزی را یاد می‌گیرد که هیچ‌کس آنجا نگذاشته است.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) مدل Unigram را معرفی می‌کند؛ Kudo and Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) پیاده‌سازی‌ای است که بیشتر مدل‌های چندزبانه استفاده می‌کنند؛ Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012) خاستگاه WordPiece است. Let's build the GPT Tokenizer از Andrej Karpathy و مخزن همراه karpathy/minbpe نیاکان مستقیم کد این فصل‌اند و بسیار فراتر می‌روند، از جمله regex مربوط به GPT-4 و handling مربوط به special-tokenها. فصل 6 از Hugging Face LLM Course سه الگوریتم را کنار هم با مثال‌های کارشده پوشش می‌دهد.