gzipは言語モデルになれるか？

gzipは言語モデルになれるか？

以前、ニューラルネットワークを使わない言語モデリングについて書きました。そこでは、重みや学習なしで、ひたすらカウントするだけで、アンバウンドn-gramモデルを使ってシェイクスピアのテキストを生成しました。偶然にも、Language Modeling is Compressionという論文に出会い、そこには圧縮と予測の等価性という言葉がありました。

あらゆる予測モデルは本質的にコンプレッサーであり、あらゆる圧縮アルゴリズムは予測モデルである

これが自然な疑問につながりました。「gzipは言語モデルになれるのか？」[1] ニューラルネットワークも学習済みパラメータも何もなしで、オペレーティングシステムに付属しているコンプレッサーだけで。コーパスでプライムし、通常のテキストプロンプトを与えると、バイトシーケンスの中で最もよく圧縮されるものを探してプロンプトを継続します。tiny Shakespeareでプライムした後の、編集されていない実際の出力がこちらです。

gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:
' --length 200

MENENIUS:
'Though all at once canq

MARCIUS:
Pray now, nocamest thou to a morsel .

LARTIUS:
Hence, and
I' the end admire, where G
again; and after it ag .

結果は、まあ、なんとなく、です。正確に一貫性のあるテキストではありませんが、明らかにテキストについて何かを「知って」います。私がgzipに期待していたよりもはるかに多くのことを。[2] では、コンプレッサーがどのようにしてこれを生成できるのでしょうか？

この記事はHacker Newsに掲載されました。議論へのリンクはこちら。

圧縮は予測である#

コンプレッサーが何をするのか考えてみましょう。コンプレッサーは、自分が「期待する」データには少ないバイトを使い、期待しないデータには多くのバイトを使います。もし私が、文字Aが100万回繰り返されるファイルを渡されたら、あなたはそれを一文で説明できます。一方、100万個のランダムなバイトには、利用できる構造がなく、ほとんど圧縮されません。

これは偶然ではありません。情報理論の核心です。シンボルをエンコードするために必要なビット数は $-\log_2 p$ です。ここで、$p$はそのシンボルにモデルが割り当てる確率です。確率が高いほど、必要なビットは少なくなります。したがって、コンプレッサーには、誰かが書き留めたかどうかにかかわらず、確率モデルが隠されています。

gzipはDEFLATEを使用しており、これは32 KiBのスライディングウィンドウ内で最近のテキストに対する一致を見つけることで次のバイトを圧縮します。もし継続がウィンドウ内の何かをエコーする場合、DEFLATEはそれをリテラルバイトの代わりに安価なバックリファレンスとしてエンコードします。したがって：

gzipが「期待した」継続は、既にウィンドウ内にあるテキストをエコーするため、ほとんど何も圧縮されません。

これでスコアが得られます。コンテキストがあり、候補となる継続がどれだけ良いかを知りたい場合、測定するのは次のとおりです。

$$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$

圧縮された長さが小さいほど、候補はより「予測された」ものとなります。モデルをプライムするために、gzipのウィンドウにコーパスを含めます。コーパスのように見える継続は小さく圧縮され、そうでない継続は大きく圧縮されます。

ビームサーチによる生成#

スコアリングは一つですが、生成は別です。最もよく圧縮される単一の次のバイトを選択するという素朴なアプローチは、微妙な理由でひどく失敗します。gzipは整数バイト長（小数なし）しか提供しません。1バイトを追加しても圧縮長が変わらないことがよくあるため、多くの候補が同点となり、信号は量子化ノイズに埋もれてしまいます。

修正策は、コミットする前に全体のスパンを先読みすることです。gziptはバイトシーケンス上でビームサーチを実行します。各ステップで、現在のコンテキストは次のようになります。

corpus window + recent tail of (prompt + generated bytes)

次にgziptは可能な次のバイトを試します。各候補の継続は、context + candidateを圧縮し、圧縮された結果が何バイト取るかをチェックすることでスコアリングされます。

ループは次のとおりです。

1. プロンプト。 ユーザーのプロンプトを初期テキストとして開始します。開始トークンはありません。プロンプトバイトは、gzipが見るコンテキストの一部にすぎません。
2. コンテキスト。 コーパスウィンドウと、プロンプト/生成されたテキストの最近の末尾をgzipに表示します。
3. 検索。 beam_width個の最も圧縮性の高い部分的な継続を保持します。それぞれをコーパスに出現するすべてのバイトで拡張し、圧縮長でスコアリングし、最も良いbeam_widthに絞り込みます。horizonバイト繰り返します。
4. コミット。 最も圧縮性の高い完全なスパン（またはtemperatureが正の場合はファイナリストの中からサンプリング）を取り、それを追加してループを再開します。

重要な詳細として、生成された出力の最後のtailバイトのみがスコアリングコンテキストに残ります。 DEFLATEは遠い一致よりも近い一致をより安価にコード化するため、gzipがその履歴全体を見ることができれば、最も安価な方法は、それがちょうど出力したテキストを繰り返しコピーすることになりがちです。

上記の С анимация でデコーディングとスコアリングのプロセスを見ることができます。これは、一番上で表示されたのと同じリプレイです。全体は標準ライブラリのPython（zlibのみ）で書かれた単一のファイルです。コードはGitHubにありますので、遊んでみてください。

---

1. 論文でもこの試みは行われましたが、結果は芳しくありませんでした。ビームサーチを追加することで生成品質が大幅に向上しました（彼らが言及したアイデアであり、以下で議論します）。↩︎
2. コードは実際にはgzipプロセスを起動する代わりにzlibを使用していますが、GziPTという名前は良すぎました。どちらも内部的には同じDEFLATEアルゴリズムを使用していると信じています。↩︎