本文へ
ハクソク

世界を動かす技術を、日本語で。

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

元記事: 原文(nathan.rs)

概要

gzip のような圧縮ツールが 言語モデル として使えるかを検証。 圧縮と予測 の理論的な等価性について解説。 DEFLATE アルゴリズムの仕組みとスコアリング手法を説明。 ビームサーチ による生成プロセスの工夫とその効果を紹介。 実験コードは GitHub で公開。

圧縮アルゴリズムによる言語モデリング

  • ニューラルネットワーク を使わず、n-gramやgzipなどの 圧縮アルゴリズム で言語モデル構築を試みた事例
  • 圧縮と予測の等価性 ：あらゆる予測モデルは圧縮器であり、全ての圧縮アルゴリズムは予測モデルであるという理論
  • gzip （DEFLATEアルゴリズム）は、直近32KiBのスライディングウィンドウ内で過去の一致を探し、繰り返し部分を効率的に圧縮
  • 圧縮率が高い＝モデルが「予測」した（＝コーパスに似ている）というスコアリング
  • 実際に tiny Shakespeare で試すと、完全な意味は通らないが、明らかにテキストの特徴を捉えている出力を生成

圧縮によるスコアリングと生成手法

  • 圧縮器は「予測しやすい」データは少ないバイト数で表現し、「予測しにくい」データは多くのバイト数を必要とする
  • 符号化に必要なビット数は $-\log_2 p$（pはモデルが割り当てた確率）で決まる
  • gzip(context + candidate) の圧縮後サイズをスコアとし、サイズが小さいほど「より予測された」継続とみなす
  • コーパスをウィンドウに読み込み、プロンプトに続く候補を圧縮してスコアリング

ビームサーチによる生成の工夫

  • 1バイトごとに最良を選ぶ単純な方法では、gzipの圧縮長が整数単位でしか変化しないため、候補の差が埋もれやすい
  • ビームサーチ を導入し、複数の候補を並行して評価しながら、最も圧縮率の高い継続を選択
    • プロンプトを初期テキストとし、コーパスウィンドウ＋直近の生成テキストをコンテキストとして利用
    • コーパス中に現れる全てのバイトを次候補とし、圧縮後サイズでスコアリング
    • 最良のビーム幅分だけ候補を残し、所定の長さまで繰り返す
    • 最終的に最も圧縮率の高い継続を生成結果として採用
  • DEFLATEは直近の一致に強く反応するため、スコアリング時は直近のテキストのみをコンテキストに残すことで、単純な繰り返しを防止

実験結果と考察

  • 論文でも類似の試みがなされていたが、単純な生成では品質が低い
  • ビームサーチ の導入により、生成品質が大きく向上
  • 実装は 標準ライブラリのzlib で完結し、GitHubで公開
  • gzip（またはDEFLATE）が持つ「予測モデルとしての本質」を体験的に理解できる実験

まとめ

  • 圧縮アルゴリズムは、実質的に確率モデルとして機能
  • 言語モデルの「予測力」と圧縮率は密接に関連
  • ニューラルネットワークなしでも、圧縮器を工夫すれば「それらしい」テキスト生成が可能
  • ただし、意味的な一貫性や流暢さはニューラルモデルに及ばない
  • 圧縮と生成の理論的背景や実装の工夫を学べる好例

提供: ハクソク · 要約更新:

AIによる日本語要約です。内容は原文とあわせてご確認ください。

Hacker Newsの議論を読む

Hackerたちの意見

WinRARがOpenAIよりも利益が出てるってのは、偶然なのかな…？そんなわけないよね！

└

WinRARって利益出てるの？マジで？でも、損失は出してないのは確かだね。

普通のテキストプロンプトを与えると、最適に圧縮できるバイト列を探し続けるんだよね。でも、どうやってその検索がどれだけうまくいったかを知るの？意味のある検索空間を探す方法なんてないし。だから、結果はgzipがテキストの続きの「妥当性テスト」としてどれだけ機能するかの下限しか示してないんだ。可能な列の空間は、検索したものよりも何桁も大きいから、もっと圧縮できる列があるかもしれないよ。テキストにはビームサーチについて触れてるけど、gzipの圧縮性に関してビームサーチがどれだけグローバルオプティマを見つけるのかについての議論は見当たらないね。

└

それはいい質問だね。例えば、全ての長さnのシーケンスxに対して、len(gzip(context + prompt + x))を最小化するバイトシーケンスxを見つける方法があるとしよう。ここで「+」は文字列の連結を示してる。これがどれほど役立つかは不明だね。あまり役立たない理由は、Deflateの要素の一つに、繰り返し出現する部分文字列を平文の入力ストリーム内の以前の出現にバックリファレンスで置き換えるパスがあるからだ。例えば、n=200のバイトシーケンスxを見つけたいとする。もしprompt+yがcontextの部分文字列であるような200バイトのシーケンスyが存在すれば、Deflateはprompt+yをその以前のシーケンスへのバックリファレンスとしてエンコードできる。マッチ長と距離長をHuffmanツリーを使ってエンコードする必要があるんだ。この候補解yは、我々の目標関数のグローバルミニマムではないかもしれないけど、そうでなくても、かなり良い近似解になる可能性が高い。少し引いて考えると、入力コンテキストの巨大な部分を繰り返すことは、圧縮された出力サイズを最小化するのには良いけど、生成モデルとしてはあまり役に立たないように思える。編集: そうだ、実験をしてみたんだ。コンテキスト内でプロンプトを探して、その後のテキストを解としてコピーすると、圧縮出力の長さを最小化する点で、ビームサーチよりもずっと良い解が得られた。でも、生成ツールとしてはあまり役に立たなかった。同じ例をブログ記事から取ると: コンテキスト: tinyshakespeare.txtの最初の30,000バイト プロンプト: 'MENENIUS:\n' 解をxとすると、xは長さ200の文字列だ。L(x)をlen(gzip(context+prompt+x))としよう。我々の目標関数だ。プロンプトを入力内で探す提案された検索方法をrfind（Pythonのstr.rfindの後）と呼ぼう。そうすると、検索方法 解 解の長さ 実現可能？ 目標値 検索時間（壁時計、s） ------------- ---- ----------- --------- --------------- --------------------------- 空文字列 "" 0 いいえ 13,023 0.04s gzipt ビームサーチ ブログ記事参照 200 はい 13,051 11.93s rfind 以下参照 200 はい 13,026 0.04s だから'rfind'は目標関数を最小化するのにより良い解を見つけているんだ。実現不可能な空文字列の解よりも3バイト多くエンコードするだけで、ブログ記事に実装されたgziptのビームサーチで見つかった解よりも25バイト少ない。これがrfindによって「生成」された解で、入力コンテキストからコピー＆ペーストしたもので、"MENENIUS:"の最も右の出現から始まる。MENENIUS: O, true-bred! First Senator: Your company to the Capitol; where, I know, Our greatest friends attend us. TITUS: COMINIUS: Noble Marcius! First Senator: MARCIUS: Nay, let them follow: The Volsces これが'rfind'のコードだ - 我々の完全な「生成アルゴリズム」: def find_candidate_solution_from_context(context, prompt, length): n = len(context) i = context.rfind(prompt, 0, n-length) これをgzipt.pyに組み込むには、outが定義された後、ビームサーチが始まる前にこの行を追加すればいい。 out += find_candidate_solution_from_context(corpus_window, prompt, length)

└

最後まで読んでみて：実際には最も圧縮率の高い出力を探してるわけじゃないんだ。すぐに「aaaaaaaaaaa」みたいになっちゃうからね。最近のテキストの小さな部分にスライディングウィンドウをかけて、それを使ってるんだ。要するに、その選択のせいで全体の前提が崩れちゃってると思う。gzipがどんどん大きくなる繰り返しの部分じゃなくて、ランダムな文字の塊を拾い始めるようにアルゴリズムを調整して、面白そうな結果を強引に出した感じ。

逆に、LLMがgzipと比べて圧縮器としてどれだけ機能するかの方が興味あるな（その異常に遅い速度は無視して）。

└

ハッタープライズのトップコンテスタントは、圧縮にニューラルネットワークを使ってるよ。だから、LLMはgzipと比べてかなり良いパフォーマンスを発揮するって言えるね。

└

ロスレスとロスィー、これが問題だね。

└

幻覚はロスのある圧縮アーティファクトだよ。

これは面白いけど、歴史的に見ると、こういうモデルやn-gram言語モデルが大規模なニューラルネットワークモデルに近いって言うのはちょっと行き過ぎな気がする。でも、確かに関連性はあるね。

└

うん、でも両方の方法が同じ数学的問題を解こうとしているというのは有益な洞察だね。LLMを魔法のように考えるよりはいい。あなたが「クロスエントロピー損失」と言うと、統計のバックグラウンドがない人はウィキペディアを見て、ちらっと見て、自分のメンタルモデルを「不可解な魔法」に調整するんだ。CPU、メモリ、ストレージの許容されるトレードオフとしての主な違いを考えるのは間違ってはいないよ。間違っているのは、gzipを同じ複雑さや一般化に達する可能性のある方法だと考えることだ。そしてもっと重要なのは、（指示された、思考の連鎖）LLMのためにトレーニングデータがどのようにキュレーションまたは生成されるかを無視することだ。でもそれでも、LLMの目標がテキスト圧縮であるというメンタルモデルは間違っていない。次に尋ねるべき質問は、どんな種類のテキストを圧縮することを期待しているのかということだ。

3blue1brownがこのトピックについてシリーズをやってるよ：https://www.youtube.com/watch?v=l6DKRf-fAAM https://www.youtube.com/watch?v=GlYgs6v2YfU（もう一つはまだ公開されてないと思う）

Hacker Newsで議論の続きを見る

同じ出典の記事