Byte-Pair Encoding

  • 27 views
  • 4 minute read
Photo by Aivars Vilks on Unsplash
Photo by Aivars Vilks on Unsplash
Byte-Pair Encoding（BPE）是一種以統計頻率為基礎的符號合併演算法，最早被提出作為資料壓縮方法。在自然語言處理（NLP）中，BPE 被重新詮釋為一種 subword tokenization 技術，用來在字元與詞彙之間取得平衡。透過從資料中自動學習高頻片段，BPE 能夠在不依賴語言知識的情況下，有效建立可擴展的 vocabulary。
Total
0
Shares
0
0
0
0
Share
0 people shared the story
0
0
0
0

Byte-Pair Encoding（BPE）是一種以統計頻率為基礎的符號合併演算法，最早被提出作為資料壓縮方法。在自然語言處理（NLP）中，BPE 被重新詮釋為一種 subword tokenization 技術，用來在字元與詞彙之間取得平衡。透過從資料中自動學習高頻片段，BPE 能夠在不依賴語言知識的情況下，有效建立可擴展的 vocabulary。

完整程式碼可以在 下載。

Table of Contents
  1. 概覽
  2. 演算法
  3. 實作
  4. 範例
  5. 結語
  6. 參考

概覽

Byte-Pair Encoding（BPE）最早由 Philip Gage 於 1994 年提出，並發表於 A New Algorithm for Data Compression。在該篇論文中，Gage 將 BPE 定義為一種純粹基於統計頻率的替換式資料壓縮演算法，其設計目的並非語言建模，而是有效降低符號序列的儲存成本。

BPE 的構想相當直接，它反覆尋找資料中出現次數最多的 byte pair，並將該 pair 以一個新的符號取代，藉此逐步縮短整體表示長度。這種設計方式具有以下幾個特性：

  • 完全不需要語言知識
    • 演算法僅依賴符號序列本身及其出現頻率，不涉及任何語意或語法假設。
  • 貪婪式（greedy）策略
    • 每一次替換皆選擇當下能帶來最大壓縮效果的 pair，而不回溯或全域最佳化。
  • 可逆性（reversible）
    • 只要保留完整的替換規則，即可從壓縮後的表示還原出原始資料。

值得注意的是，儘管原始的 BPE 嚴格聚焦於 byte-level 的資料壓縮問題，但其由資料本身學習高頻片段，並將其視為新符號的構想，後來被自然地延伸並移植到文字處理與 NLP 領域，成為 subword 表示方法的重要基礎。

演算法

在 NLP 中，BPE 通常被重新詮釋為一種 subword segmentation 方法，用來在字元層級與詞彙層級之間建立折衷的表示方式。其基本流程如下：

  1. 初始化符號表，將語料（corpus）中的每個字元或 byte 視為一個獨立的 token。
  2. 統計相鄰 token pair 的出現次數。
  3. 合併出現次數最高的 token pair。
  4. 更新 corpus 的表示方式，並重新統計。
  5. 重複上述步驟，直到達到預設的 vocabulary size 或 merge 次數上限。

為了更清楚說明 BPE 在實際 corpus 上的運作方式，以下使用一個簡單的句子作為示例：

the lowest price is lower than the last one

在最初階段，BPE 將句子中的每一個字元視為獨立的 token：

t h e   l o w e s t   p r i c e   i s   l o w e r   t h a n   t h e   l a s t   o n e

此時，vocabulary 僅包含單一字元，模型尚未學到任何較長的片段結構。

在整個 corpus 中，可以觀察到某些相鄰字元對反覆出現，例如 (l, o)、(o, w)、和 (t, h) 等。假設統計結果顯示 (t, h) 是目前出現次數最高的 pair，則進行第一次合併：

th e   l o w e s t   p r i c e   i s   l o w e r   th a n   th e   l a s t   o n e

此時，th 成為 vocabulary 中的一個新 token。

接著重新統計新的 token pair。此時可能觀察到 (th, e)、(l, o)、(o, w)、和 (w, e) 等 pair 具有相同且最高的出現次數。由於 BPE 是貪婪式演算法，通常會依據實作細節（如先出現者或排序規則）選擇其中一個進行合併。此處假設選擇 (l, o) 作為第二次合併對象：

th e   lo w e s t   p r i c e   i s   lo w e r   th a n   th e   l a s t   o n e

再次重新統計後，常見的高頻 pair 可能包含 (th, e)、(lo, w)、和 (w, e)。假設此時選擇 (th, e) 進行合併，則得到：

the   lo w e s t   p r i c e   i s   lo w e r   th a n   the   l a s t   o n e

在這個階段，vocabulary 中已同時包含：

  • 原始的單一字元
  • 合併後的 token，如 th、the、和 lo。

接下來，BPE 會持續反覆進行重新統計和合併的流程，逐步學習更長、在 corpus 中更常出現的 subword，直到達到預設的 vocabulary size 或 merge 次數上限為止。

這個過程也清楚顯示，BPE 並非依賴任何語言學規則，而是單純根據資料中反覆出現的結構，逐步建立出一組對語料最有效率的符號表示。

實作

以下為 BPE 的一個簡化實作範例，用以對應前一節所描述的演算法流程。在此實作中，token_to_id 即代表最終學得的 vocabulary，其 key 為實際的 byte 序列，value 則為對應的 token ID。

整體實作可分為三個主要部分：初始化、訓練（training）、以及編碼（encoding）。

實作一開始即採用 byte-level 作為最小單位，將所有 0–255 的 byte 預先放入 vocabulary 中。這個設計確保：

  1. vocabulary 在任何情況下都是完整可用的。
  2. 任意輸入字串皆可被編碼，不會出現 OOV（out-of-vocabulary）問題。

在此階段，每個 token 僅對應到單一 byte，尚未引入任何 subword 結構。

在進行 BPE 訓練之前，實作先透過一個簡單的 pretokenization 規則，將原始文字切分為較粗粒度的片段（如英文單字、數字、標點與空白）。這個步驟並非 BPE 原始演算法的一部分，而是現代 NLP tokenizer 中常見的前處理設計，用來避免 BPE merge 跨越明顯不合理的邊界。

在完成 pretokenization 後，每個 token 會被轉換為 UTF-8 byte 序列，並以其在 corpus 中的出現次數作為後續 pair frequency 計算的權重。

訓練階段對應到前一節描述的 BPE 核心演算法：

  1. 對每個 token 的 byte sequence，統計相鄰 byte pair 的出現次數。
  2. 將出現次數最高的 pair 視為下一個合併目標。
  3. 建立新的 token，並將該 pair 在所有 token 中進行替換。
  4. 將合併規則依序記錄下來。

此流程會反覆進行，直到 vocabulary size 達到預設上限，或是最高頻率的 pair 低於最小門檻為止。需要注意的是，這裡的合併策略是貪婪式（greedy）的，即每一步只根據當前的統計結果做出局部最優選擇，而不回溯先前的決策。

在實際編碼（encoding）新輸入文字時，流程與訓練階段的邏輯相互對應：

  1. 輸入文字先經過相同的 pretokenization。
  2. 每個 token 被轉為 byte sequence。
  3. 依照訓練時記錄的 merge 順序，逐一套用合併規則。
  4. 最終輸出對應的 token ID 序列。

由於 merge 規則是以固定順序套用，這個過程是確定性的，也確保了訓練與推論階段的一致性。

import re
from collections import Counter
from typing import Iterable

PRETOKENIZE_PATTERN = re.compile(r"'s|'t|'re|'ve|'m|'ll|'d|\s?[A-Za-z]+|\s?\d+|\s?[^A-Za-z\d\s]+|\s+")


class BPE:
    def __init__(self):
        self.token_to_id: dict[bytes, int] = {bytes([i]): i for i in range(256)}
        self.id_to_token: dict[int, bytes] = {token_id: token for token, token_id in self.token_to_id.items()}
        self.merges: list[tuple[int, int]] = []

    def train(self, corpus: Iterable[str], vocab_size: int, min_frequency: int = 2):
        word_counts = Counter()
        for line in corpus:
            for token in self.pretokenize(line):
                b = token.encode("utf-8")
                if b:
                    word_counts[b] += 1

        word_symbols: dict[bytes, list[int]] = {word: list(word) for word in word_counts}

        while len(self.token_to_id) < vocab_size:
            pair_frequencies = Counter()

            for word, symbols in word_symbols.items():
                word_count = word_counts[word]
                for i in range(len(symbols) - 1):
                    pair_frequencies[symbols[i], symbols[i + 1]] += word_count

            if not pair_frequencies:
                break

            (symbol_left, symbol_right), pair_frequency = pair_frequencies.most_common(1)[0]
            if pair_frequency < min_frequency:
                break

            new_id = len(self.token_to_id)
            new_token = self.id_to_token[symbol_left] + self.id_to_token[symbol_right]

            self.token_to_id[new_token] = new_id
            self.id_to_token[new_id] = new_token
            self.merges.append((symbol_left, symbol_right))

            self._merge(word_symbols, symbol_left, symbol_right, new_id)

    @classmethod
    def pretokenize(cls, text: str) -> list[str]:
        return [m.group(0) for m in PRETOKENIZE_PATTERN.finditer(text)]

    @classmethod
    def _merge(cls, word_symbols: dict[bytes, list[int]], left: bytes, right: bytes, new_id: int) -> None:
        for word, symbols in word_symbols.items():
            new_symbols = []
            i = 0
            while i < len(symbols):
                if i < len(symbols) - 1 and symbols[i] == left and symbols[i + 1] == right:
                    new_symbols.append(new_id)
                    i += 2
                else:
                    new_symbols.append(symbols[i])
                    i += 1
            word_symbols[word] = new_symbols

    def encode(self, text: str) -> list[int]:
        ids = []
        for token in self.pretokenize(text):
            symbols = list(token.encode("utf-8"))
            symbols = self._apply_bpe(symbols)
            ids.extend(symbols)
        return ids

    def _apply_bpe(self, symbols: list[int]) -> list[int]:
        for left, right in self.merges:
            new_token = self.id_to_token[left] + self.id_to_token[right]
            new_id = self.token_to_id[new_token]
            i = 0
            output = []
            while i < len(symbols):
                if i < len(symbols) - 1 and symbols[i] == left and symbols[i + 1] == right:
                    output.append(new_id)
                    i += 2
                else:
                    output.append(symbols[i])
                    i += 1
            symbols = output
        return symbols

範例

為了驗證前述 BPE 實作的實際行為，以下使用 WikiText-2 作為訓練 corpus。WikiText-2 是一個常見的語言模型基準資料集，包含約三萬多行經過最少清理的 Wikipedia 文字，能保留自然語言中常見的標點、空白與結構，適合作為 tokenizer 訓練的測試 corpus。

在此實驗中，我們將訓練集中的所有文字行作為輸入，並將 vocabulary size 設定為 2000。由於實作採用 byte-level 初始化，這個設定意味著在原始 256 個 byte token 之外，最多可額外學得約 1700 個 subword token。

from datasets import load_dataset

from bpe import BPE


def main():
    print("Loading WikiText-2...")
    dataset = load_dataset("wikitext", "wikitext-2-raw-v1")
    train_text = dataset["train"]["text"]
    print(f"Number of training lines: {len(train_text)}")

    print("Training BPE...")
    bpe = BPE()
    bpe.train(corpus=train_text, vocab_size=2000)

    print("Training finished")
    print("Vocab size:", len(bpe.token_to_id))
    print("Number of merges:", len(bpe.merges))

    print("\nFirst 20 merges (as bytes):")
    for i, (a, b) in enumerate(bpe.merges[:20]):
        ta = bpe.id_to_token[a]
        tb = bpe.id_to_token[b]
        print(f"{i:02d}: {ta!r} + {tb!r}")

    example = "Natural language processing is interesting"
    encoded = bpe.encode(example)

    print()
    print(f"Example text: {example}")
    print(f"Encoded token ids: {encoded}")
    print(f"Decoded tokens: {[bpe.id_to_token[i] for i in encoded]}")


if __name__ == "__main__":
    main()

訓練完成後，可觀察到以下幾個關鍵結果：

  • 最終 vocabulary size 為 2000。
  • 實際執行的 merge 次數為 1744。
  • merge 次數略小於上限，表示在後期已無足夠高頻的 pair 可供合併。

透過純粹的頻率統計與貪婪式合併，模型得以從原始 byte 序列中，自動學得一組能有效表示 corpus 結構的 subword vocabulary。

Loading WikiText-2...
Number of training lines: 36718
Training BPE...
Training finished
Vocab size: 2000
Number of merges: 1744

First 20 merges (as bytes):
00: b' ' + b't'
01: b'h' + b'e'
02: b' ' + b'a'
03: b'i' + b'n'
04: b' t' + b'he'
05: b'e' + b'r'
06: b'o' + b'n'
07: b' ' + b','
08: b'r' + b'e'
09: b' ' + b's'
10: b'e' + b'd'
11: b' ' + b'o'
12: b' ' + b'w'
13: b'n' + b'd'
14: b'a' + b't'
15: b' ' + b'.'
16: b'o' + b'r'
17: b'i' + b't'
18: b' ' + b'c'
19: b'e' + b'n'

Example text: Natural language processing is interesting
Encoded token ids: [78, 270, 1221, 312, 630, 117, 553, 1971, 444, 285, 363, 824, 390, 285]
Decoded tokens: [b'N', b'at', b'ural', b' l', b'ang', b'u', b'age', b' proc', b'ess', b'ing', b' is', b' inter', b'est', b'ing']

結語

從實驗結果可以看出，BPE 在效能與實作複雜度之間提供了一個相當實用的折衷方案。相較於 word-level tokenization，BPE 能有效降低 vocabulary 規模並避免 OOV 問題。由於其演算法簡單、可控性高，且能直接從 corpus 中學習結構，BPE 至今仍被廣泛使用於多種 tokenizer 設計中，例如 GPT-2 所採用的 byte-level BPE，以及後續模型所沿用的相關變體。即使在更新的 tokenizer 方法不斷出現的情況下，BPE 仍是理解現代語言模型 tokenization 設計的一個基準方法。

參考

  • Philip Gage. 1994. A new algorithm for data compression. C Users Journal, Volume 12, Issue 2, pages 23–38.

Total
0
Shares
Share 0
Tweet 0
Share 0
Share 0
Related Tags

我是 Wayne，從事全端軟體開發有 20 年以上的經驗。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You May Also Like