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

しばらく前に、ニューラルネットワークを使わない言語モデリングについて書きました。そこでは、重みも学習もなしに、ただカウントするだけで、無限長のn-gramモデルでシェイクスピアを生成しました。 偶然にも、「Language Modeling is Compression」という論文に出会いました。そこでは、圧縮と予測の等価性について言及されていました。あらゆる予測モデルは本質的にコンプレッサーであり、あらゆる圧縮アルゴリズムは予測モデルである、というものです。 これが自然な疑問につながりました。gzipは言語モデルになれるのか？ニューラルネットワークなし、学習済みパラメータなし、何もなし。オペレーティングシステムに付属しているコンプレッサーだけです。 あなたはそれをコーパスでプライムし、通常のテキストプロンプトを与え、そしてそれはバイトシーケンスを検索することでそのプロンプトを継続します。最もよく圧縮されるバイトシーケンスです。 以下は、tiny Shakespeareでプライムした後の、実際の編集されていない出力です。 gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS: ' --length 200MENENIUS: '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が知っていると期待していたよりもはるかに多くのことを。 では、コンプレッサーはどうやってこれを生成できるのでしょうか？ 圧縮は予測です コンプレッサーが何をするかを考えてみてください。それは「期待する」データには少ないバイトを使い、「期待しない」データには多くのバイトを使います。 もし私があなたに、文字Aが100万回繰り返されるファイルを手渡したら、あなたはそれを1文で説明できるでしょう。一方、100万個のランダムなバイトには構造がなく、ほとんど圧縮されません。 これは偶然ではありません。情報理論の核心です。 シンボルをエンコードするために必要なビット数は $-\log_2 p$ です。ここで、$p$ はモデルがそれに割り当てる確率です。高い確率ということは、少ないビットを意味します。 したがって、コンプレッサーには、誰かがそれを書き留めたかどうかにかかわらず、確率モデルが隠されています。 gzipはDEFLATEを使用しており、これは最近のテキスト（32KiBのスライディングウィンドウ内）に対する一致を見つけることで次のバイトを圧縮します。 継続がウィンドウ内にあるものをエコーする場合、DEFLATEはそれをリテラルバイトの代わりに安価なバックリファレンスとしてエンコードします。 したがって： gzipが「期待した」継続（既にウィンドウ内にあるテキストをエコーしているため）は、ほとんど何も圧縮されません。 これにより、スコアが得られます。 あるコンテキストがあり、候補となる継続がどれだけ良いかを知りたい場合、私は次のように測定します。 $$\text{score}(\text{candidate}) = \texttt{len(gzip(context + candidate))}$$ 圧縮された長さが小さいほど、候補はより「予測された」ものとなります。 モデルをプライムするために、ウィンドウにコーパスを含めます。 コーパスのように見える継続は小さく圧縮され、そうでない継続は大きく圧縮されます。 ビームサーチによる生成 スコアリングは一つのことですが、生成は別のことです。 最もよく圧縮される次の1バイトを選択するという単純なアプローチは、微妙な理由でひどく失敗します。gzipは整数バイト長（小数なし）しか提供しません。 1バイトを追加しても、圧縮された長さがまったく変わらないことがよくあります。そのため、多くの候補が同点になり、信号は量子化ノイズに埋もれてしまいます。 修正策は、コミットする前に全体の範囲を先読みすることです。 gzipt はバイトシーケンス上でビームサーチを実行します。 各ステップで、現在のコンテキストは次のようになります。 コーパスウィンドウ + (プロンプト + 生成されたバイト) の最近のテール 次に、gzipt は可能な次のバイトを試します。 各候補となる継続は、コンテキスト + 候補を圧縮し、圧縮された結果が何バイト取るかをチェックすることでスコアリングされます。 ループは次のようになります。 プロンプト。ユーザーのプロンプトを初期テキストとして開始します。開始トークンはありません。プロンプトバイトは、gzipが見るコンテキストの一部にすぎません。 コンテキスト。gzipにコーパスウィンドウとプロンプト/生成されたテキストの最近のテールを表示します。 検索。最も圧縮性の高い部分的な継続の中から、beam_width 個を保持します。 コーパスに出現する各バイトでそれぞれを拡張し、圧縮された長さで全てをスコアリングし、最適な beam_width まで絞り込みます。 horizon バイトごとに繰り返します。 コミット。最も圧縮性の高い完全なスパンを選択します（または温度が正の場合はファイナリストの中からサンプリングします）。それを追加し、ループを再開します。 重要な詳細の1つは、生成された出力の最後のテールバイトのみがスコアリングコンテキストに残ることです。 DEFLATE は、遠い一致よりも近い一致をより安価にコード化します。そのため、gzip がその履歴全体を見ることができれば、最も安価な方法は、しばしばそのままのテキストをループでコピーすることです。 上のアニメーションでデコーディングとスコアリングのプロセスを見ることができます。これは、一番上で示されているのと同じリプレイです。 全体は、標準ライブラリの純粋なPython（zlibのみ）の1つのファイルです。 コードはGitHubにありますので、試したい方はどうぞ。 論文ではこの試みが行われましたが、結果は低調でした。 ビームサーチを追加することで生成品質が大幅に向上しました（彼らが言及したアイデア）。これは以下で議論されています。 ↩︎ コードは実際にはgzipプロセスを起動するのではなくzlibを使用していますが、GziPTという名前は良すぎました。 どちらも内部で同じDEFLATEアルゴリズムを使用していると信じています。 ↩︎