בונים BPE Tokenizer: למה המודל שלך לא מצליח לספור R

יש שתי דרכים מובנות מאליהן להזין טקסט לרשת, ושתיהן נכשלות מסיבות שכדאי להבין, כי הכישלון מגדיר את צורת הפתרון.

מילים. מפצלים לפי רווחים, ומקצים לכל מילה מספר. באנגלית יש מאות אלפי צורות מילים, והמודל צריך שורת embedding לכל אחת, כך שה-vocabulary — וגם שכבת הפלט, שחייבת להפיק ציון לכל רשומה — נעשה עצום. גרוע מזה הוא מה שקורה בזמן inference: למילה שהמודל מעולם לא ראה באימון אין מספר. זו בעיית ה-out-of-vocabulary, והתיקון המקובל הוא למפות כל דבר לא מוכר ל-token יחיד <UNK>, מה שזורק את המידע לפח. בנוסף, ״מילה״ אינה מושג מוגדר היטב: סינית ויפנית לא שמות רווחים בין מילים, וגרמנית מצמידה שם עצם לשם עצם בלי סוף.

תווים. אין בעיית out-of-vocabulary, וה-vocabulary כולל מאה ומשהו סימנים. אבל הרצפים נעשים ארוכים מאוד, ופרק 9 יראה שעלות attention גדלה ריבועית עם אורך הרצף. מסמך בן 1,000 מילים הוא בערך 5,000 תווים — רצף ארוך פי ארבעה עד חמישה ממה שהוא צריך להיות, במחיר ריבועי. וכל תו כמעט לא נושא משמעות בפני עצמו, כך שהשכבות הראשונות מתבזבזות על הרכבה מחדש של מילים שה-tokenizer היה יכול למסור שלמות.

התשובה נמצאת ביניהם: subwords. מילים נפוצות נעשות token אחד, מילים נדירות מתפצלות לחלקים, ושום דבר לעולם אינו לא מוכר כי החלקים מגיעים עד bytes בודדים. החלק המעניין הוא שאף אחד לא מתכנן את הפיצול. ה-tokenizer מאומן, על אותו סוג נתונים כמו המודל, והוא לומד אילו רצפי bytes שווים מספר משלהם על ידי ספירה של התדירות שבה הם מופיעים יחד.

האלגוריתם הוא מ-1994, והוא היה אלגוריתם דחיסה. Philip Gage פרסם אותו ב-C Users Journal כדרך לכווץ קבצים על ידי החלפה חוזרת של זוג ה-bytes הסמוכים השכיח ביותר ב-byte שאינו מופיע בנתונים.¹ הוא ישב שם עשרים ושתיים שנה עד ש-Sennrich, Haddow ו-Birch התאימו אותו מחדש לתרגום מכונה ב-2016 כדי לפתור את בעיית ה-out-of-vocabulary.² היום כך בעצם כל מודל שפה גדול קורא.

לולאת האימון היא ארבעה צעדים שחוזרים על עצמם:

הנה כל המאמן:

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 bytes של פרוזה באנגלית והדפיסו את שנים-עשר המיזוגים הראשונים בזמן שהם קורים. זה החלק שכדאי לקרוא לאט, כי אף אחד לא סיפר לאלגוריתם שום דבר על אנגלית:

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״ — עם הרווח שלפניה והרווח שאחריה, כיחידה אחת, שהתגלתה באיטרציה השתים-עשרה של לולאה שסופרת זוגות. אף אחד לא סיפק מילון. היא שם כי חמשת ה-bytes האלה מופיעים יחד יותר מכל חמישה אחרים באנגלית.

מיזוג 3 אינו טקסט בכלל. \xe2\x80 הם שני ה-bytes הראשונים בקידוד UTF-8 של סימני פיסוק טיפוגרפיים — קו מפריד ארוך, מירכאות מסולסלות. לאלגוריתם אין מושג ש-UTF-8 קיים, והוא הרגע גילה מחדש חתיכה מהמבנה שלו, כי קידודים מרובי-bytes הם, לפי ההגדרה, רצפי bytes שתמיד מופיעים יחד.

רוב המיזוגים המוקדמים כוללים רווח, והרווח נמצא בדרך כלל משמאל. זה המקור לאחת ההתנהגויות הכי מבלבלות בפועל, ונחזור אליה עוד מעט.

כל מיזוג מקצר את הרצף ומגדיל את ה-vocabulary. כמה רחוק לדחוף את זה היא החלטה אמיתית, ואפשר למדוד אותה — כאן על אותם 151,191 bytes:

תשואה פוחתת, בבירור. הכפלה מ-512 ל-1024 קונה 0.78 bytes לכל token; הכפלה מ-2048 ל-4096 קונה 1.07 — טוב יותר כאן רק מפני שה-corpus הזה קטן מספיק כדי שמיזוגים ארוכים יותר ימשיכו להשתלם. ב-corpus אמיתי העקומה משתטחת חזק.

והעלות של vocabulary גדול יותר אינה רק זיכרון. כל token צריך שורת embedding, ו — יקר יותר — שכבת הפלט של המודל צריכה להפיק ציון עבור כל רשומה ב-vocabulary בכל צעד, כך שכפל המטריצות הסופי גדל עם גודל ה-vocabulary. מודלים אמיתיים נמצאים בין 32,000 ל-200,000: GPT-2 השתמש ב-50,257, cl100k של GPT-4 משתמש ב-100,277, ו-o200k של GPT-4o בערך מכפיל את זה. המגמה היא כלפי מעלה, והסיבה נמצאת בחלק הבא.

הנה אותה פסקה, מתורגמת, ונמדדת בעזרת ה-tokenizers האמיתיים ש-OpenAI מספקת:

אותו תוכן, אותה משמעות, ועם cl100k הגרסה הרוסית צורכת פי שניים וחצי יותר tokens. מכיוון ש-APIs מחייבים לפי token ו-context windows נמדדים ב-tokens, זו לא סקרנות לשונית — זו שורה בתקציב, context window אפקטיבי קצר יותר, ותגובה איטית יותר, שלושתם יחד, לכל מי שלא עובד באנגלית.

המנגנון הוא נתוני האימון. tokenizer שאומן בעיקר על אנגלית מבזבז את תקציב המיזוגים שלו על רצפי bytes באנגלית. ספרדית חולקת את האלפבית הלטיני ולכן עדיין נהנית מחלק מהיתרון; רוסית כמעט לא מקבלת ממנו כלום, כי תווים קיריליים תופסים שני bytes ב-UTF-8 ומעטים מהזוגות האלה היו נפוצים מספיק ב-corpus האימון כדי לזכות במיזוג. יפנית גרועה עוד יותר: שלושה bytes לתו, ו-72 תווים נעשים 79 tokens — יותר tokens מתווים.

עמודת o200k מראה שזו בעיה פתירה, ושפותרים אותה. הכפלת ה-vocabulary ואיזון מחדש של נתוני האימון מקצצים את התקורה בספרדית מ-+39 % ל-+16 %, וברוסית מ-+152 % ל-+39 %. זו הסיבה האמיתית ש-vocabularies ממשיכים לגדול: לא דחיסה לשם דחיסה, אלא העובדה שהדור הקודם חייב בשקט חלק גדול מהעולם בתוספת מחיר.

האימון יצר רשימת מיזוגים מסודרת. קידוד של טקסט חדש משחזר אותה — והוא חייב לשחזר אותה באותו סדר, כי מיזוג 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")

פענוח פשוט בהשוואה: מחפשים את ה-bytes של כל id, משרשרים, ומפענחים כ-UTF-8. שימו לב ל-errors="replace": מודל יכול לפלוט רצף tokens שמסתיים באמצע תו, וזה לא היפותטי — זה מה שקורה כשתגובת streaming נחתכת באמצע emoji, ולכן streaming APIs מחזיקים bytes חלקיים בבאפר במקום לפענח token אחרי token.

Round-tripping עובד על כל דבר, וזוהי ההבטחה של 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'] הם מספרים שהספרות שלהם מיושרות בדרך מסוימת — והיישור שונה לכל זוג מספרים. הספרות של מספר אינן נמצאות באותם מקומות ממספר אחד לבא. כמה tokenizers חדשים יותר מאלצים ספרות להתפצל לקבוצות עקביות של שלוש בדיוק כדי להסיר את המכשול הזה, ומודלים שאומנו איתם טובים יותר במדידה בחשבון.

הזחה ב-Python.

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

ארבעה רווחים ושמונה רווחים הם tokens יחידים שונים, ו-tab מותך עם התו שאחריו. הזחה, שב-Python היא תחביר, מיוצגת באופן לא עקבי — וזה חלק גדול מהסיבה שמודלים נהגו לייצר Python עם הזחה שגויה בעדינות, ומהסיבה ש-tokenizers ממוקדי קוד מוסיפים tokens מפורשים לריצות הזחה נפוצות.

איות והיפוך. אותה סיבה כמו בספירת אותיות ה-r: לבקש ממודל להפוך את strawberry פירושו לבקש ממנו לסדר מחדש אותיות בתוך שלושה ids אטומים. מודלים עושים זאת כי הם שיננו איותים בזמן האימון ולא כי הם מסתכלים, ולכן הם עושים זאת היטב במילים נפוצות ורע במילים נדירות.

Glitch tokens. המקרה הבולט ביותר הוא SolidGoldMagikarp וקבוצה של מחרוזות דומות שגרמו ל-GPT-2 ול-GPT-3 להתנהג באופן מוזר — לסרב לחזור עליהן, להפיק פלט לא קשור, ולפעמים להעליב את המשתמש. ההסבר יומיומי ונובע ישירות מהעובדה שה-tokenizer מאומן בנפרד מהמודל: המחרוזות האלה היו שכיחות ב-corpus האימון של ה-tokenizer (אלה היו שמות משתמש ב-Reddit), ולכן הן קיבלו token משלהן, אבל היו נדירות או לא קיימות ב-corpus האימון של המודל. התוצאה היא שורת embedding שאותחלה אקראית וכמעט אף פעם לא עודכנה. למודל יש סמל שהוא למעשה כמעט לא ראה מעולם, וההתנהגות שלו שם היא מה שהאתחול האקראי יצא במקרה.

tokenizer הוא ממשק מאבד מידע בין טקסט למספרים, וכל התנהגות מוזרה בפרק הזה היא הממשק שמציץ החוצה. חשוב לומר בבירור שהפשרה מכוונת: BPE ברמת byte פירושו שאין קלט שאי אפשר לייצג, רצפים קצרים פי ארבעה עד חמישה משהיו תווים, ומילים נפוצות מגיעות שלמות.

המחיר הוא שהאטומים של המודל אינם האטומים שלנו. הוא מסיק על טקסט שהוא לא יכול לאיית, ביחידות שנבחרו על ידי ספירת שכיחויות על corpus שהוא לא ראה, עם עלות לפי שפה שאף אחד לא ניהל עליה משא ומתן.

כעת יש לכם רצף של מספרים שלמים. זה פורמט הקלט לכל מה שבשאר חלק II.

מה שאין לכם הוא סיבה כלשהי לכך שמספר שלם אחד יבוא אחרי אחר. הפרק הבא מציג את היעד שכל מודל שפה מאומן עליו, והוא פשוט להדהים: בהינתן ה-tokens עד כה, חזו את הבא. היעד היחיד הזה — בלי labels, בלי annotation, רק טקסט עם העתיד של עצמו כמטרה — הוא מה שהופך את כל האינטרנט לנתוני אימון, ומשם מגיעים הייצוגים האמיתיים הראשונים של המודל.

הוא גם דורש שכלל השרשרת של הסתברות מפרק 2 יהיה מדויק לחלוטין, כי הטענה שחיזוי token אחד בכל פעם שקול למידול מסמכים שלמים היא פירוק לגורמים, לא מטפורה.

פרק 8 הוא היעד האוטורגרסיבי, 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 וטיפול ב-special-token. פרק 6 של Hugging Face LLM Course מכסה את שלושת האלגוריתמים זה לצד זה עם דוגמאות פתורות.