Tự xây BPE Tokenizer: Vì sao model của bạn không đếm được chữ R

Có hai cách hiển nhiên để đưa văn bản vào một mạng, và cả hai đều thất bại vì những lý do đáng hiểu, bởi thất bại đó định hình lời giải.

Từ. Tách theo khoảng trắng, gán cho mỗi từ một con số. Tiếng Anh có hàng trăm nghìn dạng từ, và model cần một hàng embedding cho mỗi dạng, nên vocabulary — và output layer, vốn phải tạo điểm số cho mọi mục — trở nên khổng lồ. Tệ hơn là điều xảy ra khi inference: một từ model chưa từng thấy trong training sẽ không có số. Đó là vấn đề out-of-vocabulary, và miếng vá thường dùng là ánh xạ mọi thứ chưa biết vào một token <UNK> duy nhất, tức là vứt bỏ thông tin. Ngoài ra, "từ" không phải là một khái niệm được định nghĩa rõ: tiếng Trung và tiếng Nhật không đặt khoảng trắng giữa các từ, còn tiếng Đức có thể ghép danh từ này vào danh từ khác gần như vô hạn.

Ký tự. Không có vấn đề out-of-vocabulary, và vocabulary chỉ gồm khoảng hơn một trăm ký hiệu. Nhưng chuỗi trở nên rất dài, và Chương 9 sẽ cho thấy chi phí attention tăng theo bình phương độ dài chuỗi. Một tài liệu 1000 từ có khoảng 5000 ký tự — một chuỗi dài gấp bốn đến năm lần mức cần thiết, với cái giá bình phương. Và mỗi ký tự gần như không mang nghĩa riêng, nên vài layer đầu bị tiêu tốn để lắp lại các từ mà tokenizer lẽ ra có thể chuyển giao nguyên vẹn.

Câu trả lời nằm ở giữa: subword. Từ phổ biến trở thành một token, từ hiếm tách thành các mảnh, và không có gì là không biết vì các mảnh cuối cùng quy về từng byte riêng lẻ. Phần thú vị là không ai thiết kế cách tách đó. Tokenizer được training, trên cùng loại dữ liệu như model, và nó học chuỗi byte nào đáng có một con số riêng bằng cách đếm tần suất chúng xuất hiện cùng nhau.

Thuật toán này có từ năm 1994, và ban đầu là một thuật toán nén. Philip Gage công bố nó trên C Users Journal như một cách thu nhỏ tệp bằng cách liên tục thay cặp byte kề nhau xuất hiện thường xuyên nhất bằng một byte không xuất hiện trong dữ liệu.¹ Nó nằm đó suốt hai mươi hai năm cho đến khi Sennrich, Haddow và Birch tái sử dụng nó cho dịch máy vào năm 2016 để giải quyết vấn đề out-of-vocabulary.² Giờ đây về cơ bản đó là cách mọi large language model đọc.

Vòng lặp training gồm bốn bước lặp lại:

Đây là toàn bộ 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

Chạy nó trên 151.191 byte văn xuôi tiếng Anh và in ra mười hai phép gộp đầu tiên ngay khi chúng xảy ra. Đây là phần đáng đọc chậm, vì không ai nói với thuật toán bất cứ điều gì về tiếng Anh:

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)

Có ba điều trong danh sách đó đáng chỉ ra.

Phép gộp 12 là từ "the" — với khoảng trắng trước nó và khoảng trắng sau nó, như một đơn vị duy nhất, được phát hiện ở vòng lặp thứ mười hai của một vòng lặp chỉ đếm cặp. Không ai cung cấp từ điển. Nó ở đó vì năm byte ấy đồng xuất hiện nhiều hơn bất kỳ năm byte nào khác trong tiếng Anh.

Phép gộp 3 hoàn toàn không phải là văn bản. \xe2\x80 là hai byte đầu của mã hóa UTF-8 cho dấu câu kiểu typographic — dấu gạch ngang dài, dấu ngoặc kép cong. Thuật toán không hề biết UTF-8 tồn tại, và nó vừa tái phát hiện một phần cấu trúc của UTF-8, bởi các mã hóa nhiều byte, theo định nghĩa, là những chuỗi byte luôn xuất hiện cùng nhau.

Hầu hết các phép gộp sớm đều liên quan đến khoảng trắng, và khoảng trắng thường nằm ở bên trái. Đó là nguồn gốc của một trong những hành vi gây bối rối nhất trong thực tế, ta sẽ quay lại ngay sau đây.

Mỗi phép gộp làm chuỗi ngắn hơn và vocabulary lớn hơn. Đẩy đến đâu là một quyết định thật sự, và có thể đo được — ở đây trên cùng 151.191 byte:

Lợi ích giảm dần, thấy rõ. Tăng gấp đôi từ 512 lên 1024 mua thêm 0,78 byte trên mỗi token; tăng gấp đôi từ 2048 lên 4096 mua thêm 1,07 — ở đây tốt hơn chỉ vì corpus này đủ nhỏ để các phép gộp dài hơn vẫn còn sinh lợi. Trên một corpus thực, đường cong phẳng đi rất mạnh.

Và chi phí của vocabulary lớn hơn không chỉ là bộ nhớ. Mỗi token cần một hàng embedding, và — tốn kém hơn — output layer của model phải tạo điểm số cho mọi mục trong vocabulary ở mọi bước, nên phép nhân ma trận cuối cùng tăng theo kích thước vocabulary. Các model thực nằm trong khoảng 32.000 đến 200.000: GPT-2 dùng 50.257, cl100k của GPT-4 dùng 100.277, o200k của GPT-4o gần như gấp đôi con số đó. Xu hướng là đi lên, và lý do nằm ở phần tiếp theo.

Đây là cùng một đoạn văn, được dịch, đo bằng các tokenizer thật mà OpenAI cung cấp:

Cùng nội dung, cùng ý nghĩa, và với cl100k, bản tiếng Nga tiêu thụ token nhiều gấp hai lần rưỡi. Vì API tính phí theo token và context window được đo bằng token, đó không phải là một chuyện lạ về ngôn ngữ — mà là một dòng trong ngân sách, một context window hiệu dụng ngắn hơn, và một phản hồi chậm hơn, cả ba cùng lúc, với mọi người không làm việc bằng tiếng Anh.

Cơ chế nằm ở dữ liệu training. Một tokenizer được training chủ yếu trên tiếng Anh sẽ tiêu ngân sách gộp của nó cho các chuỗi byte tiếng Anh. Tiếng Tây Ban Nha dùng chung bảng chữ cái Latin nên vẫn được hưởng một phần lợi ích; tiếng Nga gần như không, vì ký tự Cyrillic chiếm hai byte trong UTF-8 và rất ít cặp trong số đó đủ phổ biến trong corpus training để giành được một phép gộp. Tiếng Nhật còn tệ hơn: ba byte trên mỗi ký tự, và 72 ký tự trở thành 79 token — nhiều token hơn ký tự.

Cột o200k cho thấy đây là một vấn đề có thể giải quyết, và đang được giải quyết. Tăng gấp đôi vocabulary và cân bằng lại dữ liệu training cắt chi phí vượt của tiếng Tây Ban Nha từ +39 % xuống +16 %, và tiếng Nga từ +152 % xuống +39 %. Đó là lý do thật sự khiến vocabulary tiếp tục lớn lên: không phải nén vì bản thân việc nén, mà vì thế hệ trước đã âm thầm tính thêm phí cho một phần lớn thế giới.

Training tạo ra một danh sách phép gộp có thứ tự. Encoding văn bản mới sẽ phát lại danh sách đó — và phải phát lại theo cùng thứ tự, vì phép gộp 12 kết hợp kết quả của phép gộp 5 và 1. Áp dụng theo thứ tự khác, bạn sẽ có một tokenization khác, sai, và không khớp với bất cứ thứ gì model đã thấy trong 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")

Decoding thì đơn giản hơn nhiều: tra cứu byte của từng id, nối lại, giải mã dưới dạng UTF-8. Hãy chú ý errors="replace": một model có thể phát ra một chuỗi token kết thúc giữa chừng một ký tự, và đó không phải giả thuyết — đó là điều xảy ra khi một phản hồi streaming bị cắt giữa một emoji, vì vậy các API streaming đệm các byte chưa hoàn chỉnh thay vì giải mã từng token một.

Round-trip hoạt động với mọi thứ, đúng như lời hứa của BPE cấp 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

Khi cơ chế đã rõ, một loạt phàn nàn tưởng như không liên quan hóa ra là cùng một phàn nàn.

Số học. Các số không được tách theo bất kỳ cách nhất quán nào:

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']

Để cộng 1234 và 12345, model trước tiên phải tự suy ra rằng ['123','4'] và ['123','45'] là các số có các chữ số căn hàng theo một cách cụ thể — và cách căn hàng khác nhau với mọi cặp số. Chữ số của một số không nằm ở cùng vị trí từ số này sang số khác. Một số tokenizer mới hơn buộc chữ số tách thành các nhóm nhất quán gồm ba chữ số chính xác là để loại bỏ trở ngại này, và các model được training với chúng giỏi số học hơn một cách đo được.

Thụt lề Python.

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

Bốn khoảng trắng và tám khoảng trắng là các token đơn khác nhau, và tab được hợp nhất với ký tự sau nó. Thụt lề, vốn là cú pháp trong Python, được biểu diễn không nhất quán — đây là một phần lớn lý do vì sao các model trước đây hay tạo Python với thụt lề sai một cách tinh vi, và vì sao tokenizer tập trung vào code thêm các token rõ ràng cho những chuỗi thụt lề phổ biến.

Đánh vần và đảo ngược. Cùng nguyên nhân như việc đếm chữ r: yêu cầu model đảo ngược strawberry là yêu cầu nó sắp xếp lại các chữ cái bên trong ba id mờ đục. Model làm được bằng cách đã ghi nhớ cách đánh vần trong training thay vì bằng cách nhìn, đó là lý do chúng làm tốt với từ phổ biến và tệ với từ hiếm.

Glitch token. Trường hợp nổi bật nhất là SolidGoldMagikarp và một nhóm chuỗi tương tự từng khiến GPT-2 và GPT-3 hành xử kỳ quặc — từ chối lặp lại chúng, tạo đầu ra không liên quan, đôi khi xúc phạm người dùng. Lời giải thích rất đời thường và đi thẳng từ thực tế tokenizer được training riêng với model: các chuỗi đó xuất hiện thường xuyên trong corpus training của tokenizer (chúng là username Reddit), nên chúng giành được token riêng, nhưng lại hiếm hoặc vắng mặt trong corpus training của model. Kết quả là một hàng embedding được khởi tạo ngẫu nhiên và gần như không bao giờ được cập nhật. Model có một ký hiệu mà về cơ bản nó chưa từng thấy, và hành vi của nó ở đó là bất cứ thứ gì mà khởi tạo ngẫu nhiên tình cờ tạo ra.

Tokenizer là một giao diện có mất mát giữa văn bản và con số, và mọi hành vi kỳ lạ trong chương này là giao diện ấy lộ ra. Cần nói rõ rằng sự đánh đổi này là cố ý: BPE cấp byte nghĩa là không đầu vào nào là không thể biểu diễn, chuỗi ngắn hơn bốn đến năm lần so với dùng ký tự, và các từ phổ biến đi vào nguyên vẹn.

Cái giá là các nguyên tử của model không phải nguyên tử của chúng ta. Nó suy luận về văn bản mà nó không thể đánh vần, trong những đơn vị được chọn bởi một phép đếm tần suất trên một corpus mà nó không thấy, với chi phí theo ngôn ngữ mà không ai từng thương lượng.

Bây giờ bạn có một chuỗi số nguyên. Đó là định dạng đầu vào cho mọi thứ trong phần còn lại của Phần II.

Điều bạn chưa có là bất kỳ lý do nào để một số nguyên đi sau một số nguyên khác. Chương tiếp theo giới thiệu objective mà mọi language model được training trên đó, và nó đơn giản đến đáng ngạc nhiên: cho các token cho đến hiện tại, dự đoán token tiếp theo. Chỉ riêng objective đó — không nhãn, không chú thích, chỉ văn bản với chính tương lai của nó làm target — là thứ biến toàn bộ internet thành dữ liệu training, và là nơi các biểu diễn thật sự đầu tiên của model xuất hiện.

Nó cũng đòi hỏi quy tắc dây chuyền của xác suất từ Chương 2 phải chính xác tuyệt đối, vì tuyên bố rằng dự đoán từng token một cũng giống như mô hình hóa toàn bộ tài liệu là một phép phân rã, không phải ẩn dụ.

Chương 8 là autoregressive objective, embeddings, và nơi đầu tiên một model học được điều mà không ai đặt vào đó.

Kudo, T. Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates (arXiv:1804.10959) giới thiệu model Unigram; Kudo và Richardson, SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing (arXiv:1808.06226) là implementation mà hầu hết model đa ngôn ngữ sử dụng; Schuster và Nakajima, Japanese and Korean Voice Search (ICASSP 2012) là nguồn gốc của WordPiece. Let's build the GPT Tokenizer của Andrej Karpathy và repository karpathy/minbpe đi kèm là tổ tiên trực tiếp của code trong chương này và đi xa hơn đáng kể, bao gồm regex GPT-4 và xử lý special-token. Chương 6 của Hugging Face LLM Course trình bày ba thuật toán cạnh nhau với các ví dụ đã giải.