สร้าง BPE Tokenizer: ทำไมโมเดลของคุณนับตัว R ไม่ถูก

มีวิธีที่ดูชัดเจนสองวิธีในการป้อนข้อความให้เครือข่าย และทั้งสองล้มเหลวด้วยเหตุผลที่ควรเข้าใจ เพราะความล้มเหลวนั้นกำหนดรูปร่างของคำตอบ

คำ. แยกตามช่องว่าง แล้วกำหนดตัวเลขให้แต่ละคำ ภาษาอังกฤษมีรูปคำหลายแสนรูป และโมเดลต้องมีแถว embedding สำหรับแต่ละคำ ดังนั้น vocabulary — และ output layer ซึ่งต้องสร้างคะแนนให้ทุก entry — จึงใหญ่โตมาก ที่แย่กว่านั้นคือสิ่งที่เกิดขึ้นตอน inference: คำที่โมเดลไม่เคยเห็นตอน training จะไม่มีตัวเลข นี่คือปัญหา out-of-vocabulary และแพตช์ทั่วไปคือ map ทุกสิ่งที่ไม่รู้จักไปเป็น token <UNK> เดียว ซึ่งเท่ากับทิ้งข้อมูลไป อีกอย่าง “คำ” ไม่ใช่แนวคิดที่นิยามชัดเจน: ภาษาจีนและญี่ปุ่นไม่เว้นวรรคระหว่างคำ และภาษาเยอรมันประกอบคำนามต่อกันได้ไม่สิ้นสุด

ตัวอักษร. ไม่มีปัญหา out-of-vocabulary และมี vocabulary แค่สัญลักษณ์ร้อยกว่าตัว แต่ลำดับจะยาวมาก และบทที่ 9 จะแสดงว่า cost ของ attention โตแบบกำลังสองตามความยาวลำดับ เอกสาร 1000 คำมีประมาณ 5000 ตัวอักษร — เป็นลำดับที่ยาวเกินจำเป็นสี่ถึงห้าเท่า พร้อมราคาที่เป็นกำลังสอง และตัวอักษรแต่ละตัวแทบไม่มีความหมายในตัวเอง ดังนั้น layer แรก ๆ จึงถูกใช้ไปกับการประกอบคำกลับขึ้นมา ทั้งที่ tokenizer น่าจะส่งต่อคำเหล่านั้นให้ครบชิ้นได้ตั้งแต่แรก

คำตอบอยู่ระหว่างกลาง: subwords คำที่พบบ่อยกลายเป็น token เดียว คำที่หายากแตกเป็นชิ้น ๆ และไม่มีอะไรที่ไม่รู้จักเลย เพราะชิ้นส่วนเล็กสุดคือ byte เดี่ยว ส่วนที่น่าสนใจคือไม่มีใครออกแบบการแยกนี้ tokenizer ถูก train บนข้อมูลชนิดเดียวกับโมเดล และมันเรียนรู้ว่า byte sequence ใดควรได้หมายเลขของตัวเองด้วยการนับว่ามันเกิดร่วมกันบ่อยแค่ไหน

อัลกอริทึมนี้มาจากปี 1994 และเดิมเป็นอัลกอริทึม compression Philip Gage เผยแพร่ใน C Users Journal เพื่อย่อไฟล์ด้วยการแทนที่คู่ byte ที่อยู่ติดกันและพบบ่อยที่สุดซ้ำ ๆ ด้วย byte ที่ไม่เกิดในข้อมูล¹ มันอยู่เฉย ๆ ยี่สิบสองปี จนกระทั่ง Sennrich, Haddow และ Birch นำไปใช้ใหม่กับ machine translation ในปี 2016 เพื่อแก้ปัญหา out-of-vocabulary² ตอนนี้มันคือวิธีที่โมเดลภาษาขนาดใหญ่แทบทุกตัวใช้อ่านข้อความ

training loop คือสี่ขั้นตอนที่ทำซ้ำ:

นี่คือ 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 สิบสองรายการแรกขณะที่มันเกิดขึ้น ส่วนนี้ควรอ่านช้า ๆ เพราะไม่มีใครบอกอัลกอริทึมเกี่ยวกับภาษาอังกฤษเลย:

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)

มีสามอย่างในรายการนั้นที่ควรชี้ให้เห็น

Merge 12 คือคำว่า “the” — พร้อมช่องว่างข้างหน้าและช่องว่างข้างหลัง เป็นหน่วยเดียวที่ถูกค้นพบในรอบที่สิบสองของ loop ที่นับคู่ ไม่มีใครป้อนพจนานุกรมให้ มันอยู่ตรงนั้นเพราะ byte ห้าตัวนั้นเกิดร่วมกันมากกว่า byte ห้าตัวอื่นใดในภาษาอังกฤษ

Merge 3 ไม่ใช่ข้อความเลย. \xe2\x80 คือ byte สองตัวแรกของการเข้ารหัส UTF-8 สำหรับเครื่องหมายวรรคตอนแบบ typographic — em dash, curly quotes อัลกอริทึมไม่รู้ว่า UTF-8 มีอยู่จริง และมันเพิ่งค้นพบชิ้นหนึ่งของโครงสร้างนั้นอีกครั้ง เพราะ encoding แบบหลาย byte โดยโครงสร้างแล้วคือ sequence ของ byte ที่ปรากฏร่วมกันเสมอ

merge ช่วงแรกส่วนใหญ่มีช่องว่างเข้ามาเกี่ยวข้อง และช่องว่างมักอยู่ทาง ซ้าย นี่คือที่มาของพฤติกรรมหนึ่งที่ชวนสับสนที่สุดในการใช้งานจริง ซึ่งเราจะกลับมาดูในอีกไม่นาน

ทุก merge ทำให้ sequence สั้นลงและ vocabulary ใหญ่ขึ้น จะผลักไปไกลแค่ไหนเป็นการตัดสินใจจริง และวัดได้ — ที่นี่วัดบน 151,191 byte ชุดเดิม:

ผลตอบแทนลดลงอย่างเห็นได้ชัด การเพิ่มจาก 512 เป็น 1024 ได้เพิ่ม 0.78 byte ต่อ token; การเพิ่มจาก 2048 เป็น 4096 ได้ 1.07 — ที่นี่ดีกว่าเพียงเพราะ corpus นี้เล็กพอที่ merge ยาว ๆ ยังให้ผลคุ้ม บน corpus จริง เส้นโค้งจะแบนลงอย่างแรง

และ cost ของ vocabulary ที่ใหญ่ขึ้นไม่ใช่แค่ memory ทุก token ต้องมีแถว embedding และ — ที่แพงกว่า — output layer ของโมเดลต้องสร้างคะแนนให้ ทุก entry ใน vocabulary ในทุก step ดังนั้น matrix multiply ขั้นสุดท้ายจึง scale ตามขนาด vocabulary โมเดลจริงอยู่ระหว่าง 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 ที่มีผลจริงสั้นลง และการตอบสนองที่ช้าลง ทั้งสามอย่างพร้อมกัน สำหรับทุกคนที่ไม่ได้ทำงานเป็นภาษาอังกฤษ

กลไกคือ training data tokenizer ที่ train ด้วยภาษาอังกฤษเป็นหลักใช้ merge budget ไปกับ byte sequence ภาษาอังกฤษ ภาษาสเปนใช้อักษรละตินเหมือนกันจึงยังได้ประโยชน์บ้าง ภาษารัสเซียแทบไม่ได้เลย เพราะอักขระ Cyrillic ใช้สอง byte ใน UTF-8 และมีคู่เหล่านั้นน้อยมากที่พบบ่อยพอใน training corpus จนได้ merge ภาษาญี่ปุ่นแย่กว่าอีก: สาม byte ต่ออักขระ และ 72 อักขระกลายเป็น 79 token — token มากกว่าอักขระ

คอลัมน์ o200k แสดงว่านี่เป็นปัญหาที่แก้ได้ และกำลังถูกแก้ การเพิ่ม vocabulary เป็นสองเท่าและปรับสมดุล training data ลด overhead ของภาษาสเปนจาก +39 % เหลือ +16 % และภาษารัสเซียจาก +152 % เหลือ +39 % นี่คือเหตุผลจริงที่ vocabulary โตขึ้นเรื่อย ๆ: ไม่ใช่ compression เพื่อ compression เอง แต่เป็นเพราะรุ่นก่อนหน้ากำลังคิดเงินเพิ่มจากประชากรโลกจำนวนมากอย่างเงียบ ๆ

การ train สร้างรายการ merge ที่มีลำดับ การ encode ข้อความใหม่คือการ replay รายการนั้น — และต้อง replay ในลำดับเดียวกัน เพราะ merge 12 รวมผลของ merge 5 และ 1 ถ้าใช้ลำดับอื่น คุณจะได้ tokenization ที่ต่างและผิด ซึ่งจะไม่ตรงกับสิ่งใดที่โมเดลเห็นตอน training

    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")

การ decode เทียบกันแล้วง่ายมาก: lookup byte ของแต่ละ id, concatenate, decode เป็น UTF-8 สังเกต errors="replace": โมเดลสามารถ emit token sequence ที่จบกลางอักขระได้ และนี่ไม่ใช่สมมติฐาน — มันคือสิ่งที่เกิดขึ้นเมื่อ streaming response ถูกตัดกลาง emoji ซึ่งเป็นเหตุผลที่ streaming API buffer partial byte แทนที่จะ decode ทีละ token

Round-tripping ใช้ได้กับทุกอย่าง นี่คือคำสัญญาของ byte-level BPE:

'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'] เป็นตัวเลขที่ digit เรียงตำแหน่งกันในวิธีเฉพาะ — และการจัดตำแหน่งนั้นต่างกันสำหรับเลขทุกคู่ digit ของตัวเลขหนึ่งไม่ได้อยู่ในตำแหน่งเดียวกันจากเลขหนึ่งไปอีกเลขหนึ่ง tokenizer รุ่นใหม่บางตัวบังคับให้ digit แยกเป็นกลุ่มสม่ำเสมอสามตัวพอดีเพื่อขจัดอุปสรรคนี้ และโมเดลที่ train ด้วย tokenizer เหล่านั้นทำเลขคณิตได้ดีขึ้นอย่างวัดได้

การเยื้องบรรทัดใน Python.

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

ช่องว่างสี่ตัวและช่องว่างแปดตัวเป็น token เดี่ยวคนละตัว และ tab ถูกหลอมรวมกับอักขระถัดไป การเยื้องบรรทัด ซึ่งใน Python เป็น syntax ถูกแทนอย่างไม่สม่ำเสมอ — นี่เป็นส่วนใหญ่ของเหตุผลที่โมเดลในอดีตมักผลิต Python ที่เยื้องบรรทัดผิดแบบละเอียดอ่อน และทำไม tokenizer ที่เน้นโค้ดจึงเพิ่ม token เฉพาะสำหรับชุดการเยื้องบรรทัดที่พบบ่อย

การสะกดและการกลับคำ. สาเหตุเดียวกับการนับตัว r: การขอให้โมเดลกลับคำ strawberry คือการขอให้มันจัดเรียงตัวอักษรใหม่ภายใน id ทึบแสงสามตัว โมเดลทำได้ด้วยการจำการสะกดจาก training แทนที่จะมองเห็น ซึ่งเป็นเหตุผลที่มันทำได้ดีสำหรับคำที่พบบ่อยและแย่สำหรับคำที่หายาก

Glitch tokens. กรณีที่โดดเด่นที่สุดคือ SolidGoldMagikarp และชุดสตริงคล้ายกันที่ทำให้ GPT-2 และ GPT-3 มีพฤติกรรมประหลาด — ปฏิเสธที่จะทวนซ้ำ สร้าง output ที่ไม่เกี่ยวข้อง บางครั้งด่าผู้ใช้ คำอธิบายนั้นธรรมดาและตามตรงมาจากข้อเท็จจริงที่ว่า tokenizer ถูก train แยกจากโมเดล: สตริงเหล่านั้นพบบ่อยใน training corpus ของ tokenizer (เป็น username บน Reddit) จึงได้ token ของตัวเอง แต่หายากหรือไม่มีเลยใน training corpus ของโมเดล ผลคือแถว embedding ที่ถูก initialise แบบสุ่มและแทบไม่เคยถูก update โมเดลมีสัญลักษณ์ที่โดยพื้นฐานแล้วมันแทบไม่เคยเห็น และพฤติกรรมตรงนั้นก็เป็นอะไรก็ตามที่ random initialisation บังเอิญให้มา

tokenizer คือ interface แบบ lossy ระหว่างข้อความกับตัวเลข และพฤติกรรมประหลาดทุกอย่างในบทนี้คือ interface ที่โผล่ให้เห็น ควรพูดให้ชัดว่าการแลกเปลี่ยนนี้ตั้งใจทำ: byte-level BPE หมายความว่าไม่มี input ใดที่แทนค่าไม่ได้ sequence สั้นกว่าการใช้ตัวอักษรสี่ถึงห้าเท่า และคำที่พบบ่อยส่งมาถึงแบบครบชิ้น

ราคาคืออะตอมของโมเดลไม่ใช่อะตอมของเรา มันให้เหตุผลเกี่ยวกับข้อความที่มันสะกดไม่ได้ ในหน่วยที่เลือกโดยการนับความถี่บน corpus ที่มันไม่ได้เห็น พร้อม cost รายภาษาที่ไม่มีใครได้ต่อรอง

ตอนนี้คุณมี sequence ของจำนวนเต็มแล้ว นั่นคือรูปแบบ input สำหรับทุกอย่างในส่วนที่เหลือของ Part II

สิ่งที่คุณยังไม่มีคือเหตุผลใด ๆ ว่าทำไมจำนวนเต็มหนึ่งควรตามหลังอีกจำนวนเต็มหนึ่ง บทถัดไปจะแนะนำ objective ที่โมเดลภาษาทุกตัวถูก train ด้วย และมันเรียบง่ายจนน่าตกใจ: เมื่อมี tokens ก่อนหน้าแล้ว ให้ทำนาย token ถัดไป objective เดียวนี้ — ไม่มี label ไม่มี annotation มีเพียงข้อความที่ใช้อนาคตของตัวเองเป็น target — คือสิ่งที่เปลี่ยนอินเทอร์เน็ตทั้งใบให้เป็น training data และเป็นที่ที่ representation แท้จริงชุดแรกของโมเดลเกิดขึ้น

มันยังต้องใช้ chain rule ของความน่าจะเป็นจากบทที่ 2 อย่างถูกต้องพอดี เพราะข้ออ้างว่าการทำนายทีละ token เหมือนกับการ model เอกสารทั้งฉบับนั้นเป็น factorisation ไม่ใช่อุปมา

บทที่ 8 คือ autoregressive objective, 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) คือ implementation ที่โมเดล multilingual ส่วนใหญ่ใช้; Schuster and Nakajima, Japanese and Korean Voice Search (ICASSP 2012) คือจุดกำเนิดของ WordPiece งาน Let's build the GPT Tokenizer ของ Andrej Karpathy และ repository karpathy/minbpe ที่มาพร้อมกันคือบรรพบุรุษโดยตรงของโค้ดในบทนี้ และไปไกลกว่ามาก รวมถึง regex ของ GPT-4 และการจัดการ special-token บทที่ 6 ของ Hugging Face LLM Course อธิบายอัลกอริทึมทั้งสามแบบเคียงข้างกันพร้อมตัวอย่างที่ทำให้ดู