最小BPEを実装して気づいたこと #13

最初、BPEを調べてみたら、Wikipediaのバイト対符号化だけを見ると、非常にシンプルな処理のように見えたので、実際にPythonを使って、BPEの最小限の機能だけ実現してみようと思った。

やりたいのは何？

バイト対符号化の例からすると、BPEの最小限の機能としては、以下が必要のようだ。

1. 出現頻度の高いペアを調べる。
2. [1]で確認できたペアを、新しいTokenに置換する。
3. [2]でできたToken列を対象として、[1]から繰り返す。

最小限機能から見えてきたBPEの原理

出現頻度の高いペア

ここのキーワードは2つ存在している。

1. 頻度の高い
2. ペア

頻度の高い

当然だが、学習対象となるデータによって「頻度の高い」の結果が変わることが分かった。

そのため、Tokenizerが異なれば、同じ文字列でも1 Tokenになる場合もあれば、2 Tokenや3 Tokenになる場合もある。

ここでもう1つ疑問が出てきた。

もし、出現頻度が同じペアが複数存在した場合は、どれを先に圧縮するのか。

例えば、複数のペアが同じ回数だけ出現している場合、先にどのペアを圧縮するかによって、その後にできるToken列が変わる可能性がある。

つまり、BPEは一度圧縮すると次に数えるペアそのものが変わるため、圧縮する順番にも影響を受ける。

ペア

BPEでは、最初は文字列をUTF-8にEncodeし、となりのByteをペアとして「頻度の高い」ものを探す。

ただし、一度圧縮した後は、新しく作られたTokenも対象になるため、厳密には「となり2つのToken」をペアとして扱う。

また、ペアの出現回数を数えることと、実際に圧縮できる回数は、必ずしも同じではない。

例えば、

AAA

の場合、

AA
AA

と、AAというペアは2回存在しているように見える。

しかし、この2つのペアは中央のAを共有しているため、同時に2回圧縮することはできない。

例えば、

AA -> 256

とすると、

AAA
↓
256 A

のようになる。

つまり、「ペアを数えること」と「実際にペアを圧縮すること」は、少し違う問題になる。

また、BPEは単語の意味を見て分割しているわけではない。

あくまでTokenの出現パターンを見て圧縮するため、Tokenizerには「単語」という概念はない。

最後に、Wikipediaでは「出現頻度が高いペア」を圧縮しているが、なぜ「頻度が高い」必要があるのか？

Tokenizerを作る方法として、本当にこれ以外の考え方はないのか？

確認できたペアを新しいTokenに置換

ここのキーワードも2つ存在している。

1. 新しいToken
2. 置換

新しいToken

Wikipediaの説明では「使われていない文字」に置換しているが、LLMのTokenizerとして考える場合、厳密には使われていない「文字」ではなく、新しいToken IDを割り当てると考えた方が分かりやすい。

そのToken IDと頻度の高いペアの関係を保存することで、新しいTokenが作られる。
その新しいToken、ペアで、Vocabularyになる。

最小実装では、

256 -> (67, 68)

のような形で管理した。

ただし、実際にはToken IDとペアの関係だけではなく、「どのペアをどの順番で圧縮するか」という圧縮ルールも重要になる。

例えば、

65　->　A 
66　->　B
67　->　C

256 -> (65, 66)
257 -> (256, 67)

の場合、

256 = AB
257 = ABC

となる。

257を作るためには、先にABを256へ圧縮する必要がある。

つまり、BPEでは新しいTokenそのものだけではなく、圧縮する順番も保存する必要がある。

実際のTokenizerでは、Vocabularyと圧縮ルールは分けて考えた方が良さそうだ。

置換

プログラム的には「置換」だが、考え方としては、

複数のToken
↓
1つのToken

にまとめ、Token列を短くするだけ。

BPEのキーワードとして「置換」よりも「圧縮」と呼ばれる。

ただし、zipのようなデータ圧縮というより、「よく出現するToken列を1つのTokenとしてまとめる」と考えた方がいいだろう。

繰り返す

ここにも疑問が出てきた。

Wikipediaの例なら問題ないが、膨大な学習データに対して、BPE処理を何回繰り返すのか。

ABCDCDABCDCDE

理論上、何度も繰り返していけば、Token列をどんどん短くすることができる。

極端に考えると、学習データ全体を巨大なTokenとして扱うこともできる。

しかし、そこまでやるとBPEの意味がなくなる。

つまり、

Vocabularyを大きくする
↓
Token列は短くなる

一方で、

Vocabularyを小さくする
↓
Token列は長くなる

という関係がある。

BPEでは、無限に圧縮するのではなく、Vocabulary Sizeや圧縮回数など、どこかで終了条件を決める必要がある。

ここには、

Vocabulary Size
        と
Token Sequence Length

の一得一失が存在しているようだ。