Sentencepiece : ニューラル言語処理向けトークナイザ

少し時間が経ってしまいましたが、[Sentencepice](https://github.com/google/sentencepiece)というニューラル言語処理向けのトークナイザ・脱トークナイザを公開しました。[MeCab](http://taku910.github.io/mecab/)や[KyTea](http://www.phontron.com/kytea/index-ja.html)といった単語分割ソフトウエアとは趣旨や目的が異なるソフトウェアですので、少し丁寧にSentencepieceの背景、応用、実験結果等をお話したいと思います。

## サブワード
ニューラル言語処理の中心となる要素技術に[LSTM (RNN)](https://en.wikipedia.org/wiki/Long_short-term_memory)があります。テキスト(トークン列)を低次元のベクトルに符号化したり、ベクトルからテキストを復号化したり、その応用範囲は多岐にわたります。[ニューラル機械翻訳 (NMT)](https://arxiv.org/abs/1609.08144) は、LSTMによる符号化・復号化を組み合わせて翻訳を行います。

↓↓↓↓↓↓↓ あなたの記事の内容
NMTのアーキテクチャは従来法と大きく異なりますが、入出力はこれまでと同様、なにかしらのトークン列です。どのような列でもよいのですが、慣習的に単語列が使われてきました。多くの人が何も考えずに、MeCab(+neologd)で分割した結果をLSTMに食わせているのではないでしょうか。しかし単語をそのまま扱うのは実用上の問題点があります。RNNによるテキスト生成では、語彙サイズに依存した計算量が必要となるめ、大規模な語彙を扱えません。高頻度語彙のみに限定することで計算量の問題は回避できますが、低頻度語が捨てられてしまいます。
───────
NMTのアーキテクチャは従来法と大きく異なりますが、入出力はこれまでと同様、なにかしらのトークン列です。どのような列でもよいのですが、慣習的に単語列が使われてきました。多くの人が何も考えずに、MeCab(+neologd)で分割した結果をLSTMに食わせているのではないでしょうか。しかし単語をそのまま扱うのは実用上の問題点があります。RNNによるテキスト生成では、語彙数に依存した計算量が必要となるため、大規模な語彙を扱えません。高頻度語彙のみに限定することで計算量の問題は回避できますが、低頻度語が捨てられてしまいます。
↑↑↑↑↑↑↑ 編集リクエストの内容

この問題を解決する手法の一つがSentencepieceの土台ともなった**サブワード**です。[^1]

サブワードのアイデアは非常に簡単です。要は、低頻度語は文字や部分文字列にフォールバックしましょうというだけです。具体的には、事前にテキストを単語分割し、各単語の頻度を求めておきます。このときに、高頻度の単語は1単語として扱い、低頻度語はより短い単位に分割します。最終的なトークン数が事前に与えられたサイズ(通常数千から数万以下)になるように分割を進めていきます。

[Byte Pair Encoding (BPE)](https://arxiv.org/abs/1508.07909) は、テキストの圧縮率を目的関数にして、貪欲的に分割を決定していくサブワード分割アルゴリズムです。BPEはもともと[データ圧縮の分野で提案された手法](https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%88%E5%AF%BE%E7%AC%A6%E5%8F%B7%E5%8C%96)ですが、NMTのトークン化に適用されその効果が[報告](https://arxiv.org/abs/1609.08144)されています。

サブワードにより実質未知語がなくなります。どんな低頻度語でも最終的には文字のならびにフォールバックされます。また、数千から数万程度の語彙サイズになるよう分割が行われるため処理速度が向上します。さらに、テキストの圧縮率をベースに最適化を行うため、テキスト生成時のステップ数もそれほど増加しません。仮に「文字」で分割してしまうと、語彙サイズは減りますがステップ数の増加が問題になります。サブワードは語彙サイズとステップ数のバランスをうまくとる効果があります。

## サブワードからSentencepieceへ
サブワードはシンプルなアイデアにもかかわらずその効果は想像以上です。しかし、単語列からスタートしているのが気になります。英語等のヨーロッパ言語の場合、単語の同定は容易ですが、日本語・中国語にサブワードを適用しようとすると、事前にMeCabやKyTea等で分割しないといけません。この事前の分割処理をなんとか駆逐できないかと思って作ったのが Sentencepieceです。

Sentencepieceは、単語列からスタートするのではなく、生文から直接分割を学習します。アイデアはそれだけですが、以下のような拡張を加えています。

1. **BPEの高速化**: [Sennrich](https://arxiv.org/abs/1508.07909)らが単語リストからBPEを学習した理由に計算量があります。ナイーブに実装すると計算量は$O(n^2)$(nはテキスト長)になるため、単語分割による探索空間の削減は必須でした。Sentencepieceでは $O(n log n)$のアルゴリズムを採用しており、大規模な生文から直接学習・分割が可能です。
2. **言語モデルベースの分割**:  BPEとは別に、言語モデルベースの分割手法も実装しています。大雑把な比較として、BPEはトークン数を目的関数にする、[辞書に基づく圧縮](https://en.wikipedia.org/wiki/Dictionary_coder)、言語モデルは尤度を最大化する[エントロピー圧縮](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%B3%E3%83%88%E3%83%AD%E3%83%94%E3%83%BC%E7%AC%A6%E5%8F%B7)とみなせます。どちらもテキストを圧縮するという意味では同じです。最終的な分割結果を見ると、BPEの貪欲法によるエラーが散見され、言語モデルのほうが正しい分割をしているようです。[^2]
3. **End to End 処理に向けたテキストの可逆分割**: これは後述します。

以下に分割例を示します。SentencePieceでは、低頻度の固有名詞は文字単位に分割されますが、高頻度の機能語列(〜により、〜された)は1トークンになっていることがわかります。結果、分割数をそれほど変えることなく、語彙サイズを1/10 (8k) にまで圧縮しています。

|分割手法|分割|分割数|
|---|---|---|
|SentencePiece (8k)|本 山 は 、 足利義 満 により 建立 された 京都 の 相 国 寺 。|15|
|KyTea|本山 は 、 足利 義満 に よ り 建立 さ れ た 京都 の 相国 寺 。|17|
|MeCab|本山 は 、 足利 義満 により 建立 さ れ た 京都 の 相国寺 。|14|
|MeCab-neologd|本山 は 、 足利義満 により 建立 さ れ た 京都 の 相国寺 。|12|
## テキストの可逆分割
「脱トークン化」とは、トークン列からもとの文を復元する処理のことを指します。形式的には、トークン化(単語分割)の逆変換に相当し、ユーザに提示する文字列を生成する重要な処理です。この脱トークン化、単純そうに見えてトークン化と同様、言語依存処理の塊です。

例えば ”Hello World.” という文は [Hello] [World] [.] の3つのトークンに分割できます。脱トークン化はこの逆変換、すなわち3トークンからもとの文を生成する処理ですが、[Hello] と [World] の間にはスペースを入れ、[World] と [.] は結合するといったように処理を分けなければなりません。言語が変わるとどうでしょう？ 日本語の [こんにちは] [世界] [。] の場合、スペースは不要です。

スペースを入れるか入れないかという判断は何を拠り所にすればよいのでしょう？ これぐらいなら、ちょっとしたルールで何とかなる... いやいやそんなに甘くはありません。

* [I] [said] ["] [Hello] ["]  →  I said "Hello"    
  いわゆるダムクォート。開き・閉じでスペースの位置が変わる。
* [20] ["] [display] → 20" display 
  " が単位として使われると左に結合する。
* [ABC] [-] [DEF]  →  ABC - DEF or  ABC-DEF?  
  記号列はもはやもとの表記にスペースがあったかわからない。   
* [나] [는] [학생] [입니다] → 나는 학생입니다  
  韓国語は原則分かち書きをするが、[品詞によって振る舞いが変わる。](https://ja.wikipedia.org/wiki/%E3%82%8F%E3%81%8B%E3%81%A1%E6%9B%B8%E3%81%8D#.E6.9C.9D.E9.AE.AE.E8.AA.9E.E3.81.AE.E3.82.8F.E3.81.8B.E3.81.A1.E6.9B.B8.E3.81.8D)


これまで、脱トークン化は、言語と文字種を手がかりに、[目を覆いたくなるような複雑なルール](https://github.com/moses-smt/mosesdecoder/blob/master/scripts/tokenizer/detokenizer.perl)で実装されてきました。最先端なNLPをやってるのに、こういうところは前世紀のテクノロジーに未だに依存している現実にバランス感覚のなさを感じます。個人的には真っ先に駆逐したい対象でもあります。

脱トークン化が複雑にならざるを得ない理由は、トークン化の際に、スペースの有無情報を一切落としていることにあります。

Sentencepieceは、スペースも通常のトークンとして扱います。具体的には、NFKC等の言語非依存の単純なテキスト正規化処理を行ったあと、便宜的にスペースをメタ文字("▁" (U+2581)) に置き換えます。

```Hello▁World. ```

このあと、BPEや言語モデルに基づく教師なし分割を行います。例えば以下のように分割されたとします。

```[Hello] [▁Wor] [ld] [.]```


トークン列に元のスペースの情報が残っているため、脱トークン化は以下の操作で曖昧性なく行えます。

```detokenized = ''.join(pieces).replace('_', ' ')```


トークン化と脱トークン化が対称性を持ち、可逆変換になることで様々な利点が生まれます。まず、言語依存の処理がなく、データから教師なしで分割を学習するため、解析・生成を含めて完全な End-to-End 処理が可能になります。また、システムが出力したトークン列を情報を落とすことなくそっくりそのまま別の処理の入力として再利用できます。多言語処理も複数言語のコーパスを混ぜて単一のSentencepieceモデルを学習すれば、言語ごとに処理を切り替える必要がありません。

## 実験
従来の単語分割手法([MeCab](http://taku910.github.io/mecab/),[MeCab+nelogd](https://github.com/neologd/mecab-ipadic-neologd),[KyTea](http://www.phontron.com/kytea/index-ja.html))とSentencepieceを機械翻訳を応用に比較してみました。

結果は[こちら](https://github.com/google/sentencepiece/blob/master/doc/experiments.md#results-bleu-scores)をご覧ください

Sentencepieceはたった8000の語彙サイズ(しかも英語と日本語で共有)にもかかわらず、従来の単語分割手法を凌ぐBLEUスコアが達成できています。さらに興味深いことに、一文あたりのトークン数はSentencepieceを使ってもそれほど大きく変わっていません。Sentencepieceはテキストを少ないパラメータで表現し、結果として翻訳精度の向上に貢献したのではないかと考えます。

[MeCab+neologd](https://github.com/neologd/mecab-ipadic-neologd) は、他の分割手法に比べてBLUEスコアが著しく低いことがわかります。neologdは、恣意性の高い基準で語彙が決定されているため、統計的圧縮を基礎とするSentencepieceとは対極にある単語分割手法です。少なくともNMTでは、統計的に一貫性のある分割手法を使ったほうがよさそうです。

## おわりに
Sentencepieceに限ったことではありませんが、応用に即した単語分割を使うべきだとこれまで主張してきました。意味処理ならJUMAN,  音声がからむと unidic,  情報抽出だと neologd といった塩梅です。

ニューラル言語処理にもそれに適した分割手法を選ぶ必要があります。厄介なことに、これまで良いと考えられてきた基準「文法的に正しい分割」「語彙のサイズ」は役に立たないどころか時として逆効果のようです。単語分割に限らず、ニューラル言語処理はこれまでの常識が通用しなかったり、覆されるような結果が出ることが日常茶飯事です。

ニューラルネットワークは、これまで人手でチューンされてきた特徴抽出・前処理の自動化に大きく貢献してきました。トークン化も一種の特徴抽出とみなせば、下手に外部知識を使うよりは、データから直接学ばせたほうが End-to-End としての性能向上が期待できます。Sentencepieceを使ってみたくなったでしょうか？

[^1]: 他にもSoftmaxをサンプリング等の手法を組み合わせて高速化する手法もあります。
[^2]: 文法的に正しいことが翻訳に常に有効とは限りません。