[1808.06226] SentencePiece: A simple and language independent subword tokenizer and detokenizer for Neural Text Processing [paper-reading]

[yoheikikuta]

論文リンク

https://arxiv.org/abs/1808.06226

公開日（yyyy/mm/dd）

2018/08/19

概要

大規模言語モデル自体によく使われる subword を多言語で高速に tokenize することのできる SenentencePiece のデモペーパー。 tokenize → de-tokenize で恣意性がなく情報が失われないようにする lossless tokenization や高速化やユーザーが使いやすいようなライブラリ設計と実装を提供しており、非常によく使われている。 日本語や中国語のように単語間の区切りがない言語を含めてデータドリブンで学習できる tokenizer であり、特に学習後の tokenization 時のスピードで威力を発揮する。

[yoheikikuta]

言語によらないサブワードの tokenizer/de-tokenizer として広く使われている SentencePiece の原論文。 過去に読んだことがあるが paper-reading に残していなかったので改めて残しておくことにする。

実装がメインでこの論文はエッセンスを伝えるデモペーパーなので、実装も一部見に行きつつ読み進めていくことにする。

[yoheikikuta]

問題意識は、ニューラル機械翻訳において言語依存の前処理や後処理が存在し、多言語対応モデルを扱うコストが高いということ。

サブワードが使われるようになっているので、テキストの取り扱いは人間の文法に必ずしも剃っていなくても機械学習モデルの性能がよければメリットのほうが大きいとなってきているが、そもそもサブワードを作るために言語依存の処理が残っている。

英語のようにスペースで区切られている言語はまだ扱いやすくて単語を集めてサブワードを作っていけばいいが、日本語のような言語であればまず単語を取得するために形態素解析・分かち書きをする必要がある。

シンプルで言語非依存なサブワードの tokenizer/de-tokenizer を提供した、というのが SentencePiece の貢献である。

[yoheikikuta]

SentencePiece のシステム overview として、メインとなるコンポーネントは以下の4つ

• Normalizer
  • 意味的に等価なUnicode文字を正規化するもの。正規化と言っているのは例えば全角文字を半角文字にするなど。
  • code は https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/normalizer.cc
• Trainer
  • 正規化されたコーパスからサブワード分割モデルを学習するもの。
  • code はモデル毎に train のためのファイルが作られていて、例えば BPE の場合は https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/bpe_model_trainer.cc
• Encoder
  • normalizer を実行して入力テキストを正規化し、学習したサブワードモデルを使ってテキストをサブワード列にトークン化するもの。
  • code はモデル毎に作られていて、例えば BPE の場合は https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/bpe_model.cc
• Decoder
  • サブワード列を正規化されたテキストに変換するもの。
  • code は decode はモデルとは独立にできるので https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/sentencepiece_processor.cc#L761-L910

Encoder と Decoder の役割はそれぞれ tokenize と de-tokenize だが、SentencePieceは語彙とIDのマッピングを保持するのでテキストからモデルに食わせるID列への変換やその逆を直接的に取り扱うことができる。モデルの入出力の ID を直接的に扱えるという意味で Encoder/Decoder と呼んでいる。

論文に載っている例は以下。

[yoheikikuta]

ここからはライブラリのデザインの話。

論文で強調しているのは SentencePiece が lossless tokenization という、encode して decode すれば元に戻る（つまり encode によって情報が失われない）という成立。

$$ \text{Decode} (\text{Encode} ( \text{Normalize} (text))) = \text{Normalize} (text) $$

これはパッと見でそのようになることを期待したい性質に思えるが、従来の手法ではこれが担保されていない。 例えば英語において以下のように tokenize するのは人間の感覚的には自然に思える。

• Raw text: Hello world.
• Tokenized: [Hello] [world] [.]

しかしこの tokenize ではスペースの情報が失われている。Hello と world の間にスペースがあるがその情報が失われている。もしくは tokenize 後に機械的にスペースを入れようとすると、今度は world と . の間にはスペースがないという情報が失われている。

これに対してどのように対処していたかというと、言語依存のルールを定義してうまく de-tokenize できるようにしていた。 いまの例だと period とか comma の場合はその前にはスペースを入れない、とかをルール化すれば、基本的には de-tokenize するときはスペースを入れて、ルールに該当する場合はスペースを入れないとかで対応できる。 もちろんこれ以外にも色々ルールを考えないといけないが、英語だけを対象にするならルールを網羅するのは頑張ればできる気がする。

一方で、これが日本語とか中国語とかも扱おうとすると、単語間にスペースを入れないケースが多いので上のようなルールでは困ることになる。そうするとまずは言語判定をして言語毎にルールを作り込んで... となってめちゃくちゃ大変になってしまう。

lossless tokenization の基本的なアイデアは入力テキストを（スペースとかも含めて） Unicode 文字列として扱うというものだ。 人間の自然な認識に合わせてスペースを削除するとかをすると de-tokenize するときの情報が失われてしまうので、それをしないようにする。 明確化のためにスペースを Unicode のブロック要素 https://en.wikipedia.org/wiki/Block_Elements の記号 _ (U+2581) に置き換えて扱う。アンダースコア (U+0332) とは異なるので注意、アンダースコアだと普通にテキストにちょこちょこ登場するのでほぼほぼ登場しない文字で置き換えている。

• Raw text: Hello_world.
• Tokenized: [Hello] [_wor] [ld] [.]

tokenize した後でもこのブロック要素の文字は保持するので、detokenize するときはたとえば Python なら以下のようにスペース情報を復元すること実現できるので、言語毎にルールなどは考える必要はない。

detok = ’’.join(tokens).replace(’_’, ’ ’)

ちなみに code 上でスペースを置き換える部分はこれ: https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/normalizer.cc#L107-L128

ちなみに subword-nmt https://github.com/rsennrich/subword-nmt という手法だと以下のように @@ を subword の境界マーカーとして使うようにしている。ただしこれも日本語とか多言語対応を考えた時には不定性がある（@@ がある場合はスペースなし、ない場合はスペースありで以下の例はいけるけど結局日本語とか中国語とかとの言語的な差異の問題は変わらない）。

• Tokenized: [Hello] [wor] [@@ld] [@@.]

シンプルで分かりやすいが、スペースも文字として扱うので SentencePiece の語彙にはスペースが含まれたものになる。例えば you と _you とか。もちろん前者は単語をサブワードに分割する時にも使えるトークンであるしこれらを別々に扱うのは思想的にもそうなんだけど、明確に別々の語彙になっている。

[yoheikikuta]

subword をどうやって学習するかというアルゴリズムに関して、SentencePiece では BPE, unigram, char, word モデルを提供している。

よく使われる BPE だが、オリジナルの論文 https://github.com/yoheikikuta/paper-reading/issues/20 では、入力文字列の長さ $N$ に対してナイーブな実装をしているので $\mathcal{O}(N^2)$ になる。 これは文字のペアをマージするかどうかをカウントして決めるアルゴリズムで、ナイーブには文字のペアを全探索してカウントするので $\mathcal{O}(N^2)$ になる。 英語を対象にしているのでスペースで分割することで入力文字列としては単語になるので、$\mathcal{O}(N^2)$ でもそこまで困らないという事情があった。

---

ナイーブな BPE では入力文字列 $N$ に対して tokenize を実施するとき、まず最頻出ペアを取り出し $\mathcal{O}(1)$、そのペアをマージして $\mathcal{O}(N)$、入力文字列をアップデートする。そしてこれをこれ以上マージできないまでループを回すので、最大で $N-1$ 回マージするので、全体として $\mathcal{O}(N^2)$ の計算量になる。

入力文字列が単語単位で区切られていれば単語毎に subuword tokenization の処理を走らせられるので処理としては重くはない。

---

一方で、日本語とか中国語の場合は単語分割をしない tokenizer を作りたいというモチベーションだったので、入力文字列としては文単位（これであればナイーブには句点区切りで機械的に処理できるので入力データを作るのはそこまで大変ではない）とかで扱いたい。 この場合、$\mathcal{O}(N^2)$ のアルゴリズムは問題になるので、SentencePiece では $\mathcal{O}(N \log (N) )$ のアルゴリズムを提供している。

具体的なコードは https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/bpe_model.cc にある。

tokenize するメインの処理の一部を取り出すと以下のようになっている。 agenda というのが優先度付きキューになっていて、ここから最頻出ペアを取り出したり追加（ここには貼ってないけど MaybeAddNewSymbolPair で優先度付きキューに追加の処理が入っている）したりする処理は $\mathcal{O}(\log (N))$ であり、それを最大で agenda に入っているシンボル全て、つまり $\mathcal{O}(N)$、繰り返すので、全体として $\mathcal{O}(N \log (N))$ である。アルゴリズムそのものは何も変えてないけど、効果的なデータ構造を実装して効率化している。 こういうのをちゃんとやって実用的なライブラリを提供しているというのは偉いねぇ。

while (!agenda.empty()) {
    SymbolPair *top = agenda.top();
    agenda.pop();

    // `top` is no longer available.
    if (symbols[top->left].piece.empty() || symbols[top->right].piece.empty() ||
        symbols[top->left].piece.size() + symbols[top->right].piece.size() !=
            top->size) {
      continue;
    }

    // Note that orignal BPE-dropout paper assumes that all merged symbols are
    // pre computed, but here we randomly skip merge opration inside this loop.
    // This implemenation is theoretically equivalent to the original one.
    if (skip_merge()) continue;

    // Replaces symbols with `top` rule.
    symbols[top->left].piece = absl::string_view(
        symbols[top->left].piece.data(),
        symbols[top->left].piece.size() + symbols[top->right].piece.size());

    // Updates prev/next pointers.
    symbols[top->left].next = symbols[top->right].next;
    if (symbols[top->right].next >= 0) {
      symbols[symbols[top->right].next].prev = top->left;
    }
    symbols[top->right].piece = absl::string_view("");

    // Adds new symbol pairs which are newly added after symbol replacement.
    MaybeAddNewSymbolPair(symbols[top->left].prev, top->left);
    MaybeAddNewSymbolPair(top->left, symbols[top->left].next);
  }

ちなみにアルゴリズム的な話はこの資料がよく書けている: https://guillaume-be.github.io/2021-09-16/byte_pair_encoding

[yoheikikuta]

vocabulary size を指定することができたり、特別なメタシンボル unknown symbol ( <unk> ), BOS ( <s> ), EOS ( </s> ) and padding ( <pad> ) に対して ID が予約されていたり、メタシンボルを自分で作ることができることも述べられている。

こういうのは実際に使う場合には結構ポイントになる。 例えば <cls> とか <mask> とかはよく使うので、そういうのを見越して柔軟に扱えるようになっているのは大事なところ。

[yoheikikuta]

次に正規化の話。

これは NFC や NFKC といったUnicode標準の正規化方式があり、SentencePiece では NFKC を使うようになっている。 正規化方式に関しては参考: https://www.unicode.org/glossary/#normalization_form_c coe 上にもコメントがある: https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/builder.h#L57-L92

正規化方式は以下の 4 つがあって、ここはだいぶ奥が深いのであまり立ち入らないというか自分が詳しくないが、例えば wikipedia では https://ja.wikipedia.org/wiki/Unicode%E6%AD%A3%E8%A6%8F%E5%8C%96 compatibility の方が同一とみなす時により緩い基準で、decomposition は composition の後に再合成するのでコンピュータがバイト列として扱う場合により短くなる。この辺りの性質を踏まえて NLP では NFKC を使う場合が多い気がする。

• NFD (Normalization Form Canonical Decomposition)
• NFC (Normalization Form Canonical Composition)
• NFKD (Normalization Form Compatibility Decomposition)
• NFKC (Normalization Form Compatibility Composition)

あと SentencePiece では TSV ファイルでルールを記述してカスタム正規化を実施することもできるらしい。 これは流石になかなか使うことはなさそう。

[yoheikikuta]

SentencePieceモデルは、完全に self-contained になるように設計されていて、モデルファイルには語彙や分割パラメータだけでなく、文字の正規化のために事前にコンパイルされた有限状態トランスデューサーも含まれている。

---

有限状態トランスデューサーというのは知らなかったが、自然言語処理の正規化タスクなどでよく使われているものらしい。 Wikipedia を眺めてみると、有限オートマトンに出力つけて拡張したという感じかな。 Wikipedia: https://en.wikipedia.org/wiki/Finite-state_transducer

---

SentencePiece の動作はモデルファイルによってのみ決定され、外部依存はないように作られている。 これによって再現性が保証されるとともに、SentencePieceモデルファイルをNMTモデルの一部として配布することもできる。

実際にこの性質はよく使われていて、学習済みの SentencePiece モデルを配布するということはよくやられている（自分も過去に日本語 BERT を作った時にやった）。

SentencePiece モデルは Protocol buffer で保存されている。

[yoheikikuta]

SentencePiece はオフラインの前処理のコマンドだけでなく、on-the-fly の処理もできるように C++ や Python などの API も提供している。これは例えば data augmentation やノイズを入れて学習するなどの処理を入れる際にも拡張・統合しやすくなっている。

以下は Python API を使って Unigram 言語モデルに基づいて subword sequence をサンプルする subword regularization のためのコードを示している。

[yoheikikuta]

あとは実験。

機械翻訳タスク Kyoto Free Translation Task (KFTT) での結果が以下。 SentencePiece でも pre-tokenization (つまり形態素解析して分かち書きしたものに対して SentencePiece を適用) した場合と、ソース言語とターゲット言語それぞれで異なる tokenization を使う場合も実験している。

重要な点は以下:

• baseline の word モデルよりもよい（これは先行研究の結果と一致）
• pre-tokenization は常に必要というわけではなく、特に日本語を扱う場合には pre-tokenization がない方が性能が良い（pre-tokenization が強い制約になるのでモデルが性能を引き出す分割になってない可能性がある）

次は segmentation のパフォーマンスの比較。

英語でも速くなってるところがあって実装力！という感じがするが、特に pre-tokenization なしでの japanese の segmentation が早いということが重要。学習の時は高速化が特に効かせられないので入力文字列長の影響が大きいが、学習ができて語彙の辞書ができている状態なら優先度付きキューの威力が発揮されているということになる。

segmentation のところで pre-tokenization ありよりもなしの方が速いのはよくわからないけど、これはアルゴリズムの計算量以外のところの影響の方が大きいということだろう。

[yoheikikuta]

論文の内容は以上で終了。 デモペーパーということでコンセプトの紹介の趣が強いが、実装も眺めたりしたので勉強になった。 コンセプトがシンプルで妥当性もあり、それをしっかりと実現したという内容。

いや〜しかし大規模言語モデル時代にぴったりな tokenizer を作りきってメンテし続けているのはすごいね。