圧縮とLLMに共通する本質は「データの予測」

「データの圧縮」と「大規模言語モデル(LLM)」は一見すると全く異なる分野ですが、根幹では「データの予測」という同じ課題を解決しようとしています。いずれも「データの冗長性を削減」「より効率的な表現」を目指すものであり、ひいては情報理論におけるエントロピーという数学的枠組みで結びついています。ngrokのデベロッパー・エデュケーターであるアニー・セクストン氏は「圧縮は予測」と題したブログを公開し、圧縮とLLMに共通する本質について語っています。

Compression is prediction | ngrok blog
https://ngrok.com/blog/compression-is-prediction

◆圧縮の基本
圧縮アルゴリズムはデータに含まれる「冗長性」を利用してファイルサイズを削減します。

・ミニフィケーション
コードを短縮化する手法として、人間が読める変数名・コメント・空白などを削除もしくは短縮し、機械が解析するのに最低限必要な部分のみを残す手法です。例えば以下のコードについて考えてみます。

// Sum every number in the list
function sumNumbers(numbers) {
  let total = 0;
  for (const number of numbers) {
    total += number;
  }
  return total;
}

ミニフィケーションの結果、上のコードは以下のようになります。

function sumNumbers(n){let t=0;for(const r of n)t+=r;return t}

ただしミニフィケーションはあくまで構文上の不要要素を削除するものであり、冗長性データを圧縮する「真の圧縮」とは異なるものです。

・ランレングス・エンコーディング
「AAAAAAAAAABBBBBCCDAAADDDDD」といった繰り返しパターンを圧縮する方法の一つです。

どの文字がいくつ連続しているかをデータ化し「A9B4C2D1A3D9」とすることでより短い文字列としてエンコードできます。

8ビットASCIIエンコードの場合、元の文字列は224ビット使用されていましたが、圧縮した文字列は96ビットしか使用していません。

・圧縮アルゴリズムの構造
gzipやBrotliといった圧縮ツールはさらにデータを圧縮するために様々な手法を用いています。最新の圧縮ツールは大まかに3つの構成要素を持っています。

・変換
・モデル
・エントロピーコーダー

上記の用語については便宜上、明確で区別可能なものとして扱いますが、実際にはそれぞれの境界がやや曖昧になることもあり単独で使用されることはまずありません。

「変換」はデータを圧縮しやすくするための前処理であり、例えばランレングス・エンコーディングも手法の一つとなりますが、変換によって必ずしもデータ量が縮小するとは限りません。場合によっては変換によって冗長性を高めることも可能であり、冗長性を持たせることによって後工程でより高い圧縮率を実現できる場合があります。

「モデル」は各シンボル(文字・数字・トークン・バイナリコードなど)の出現頻度に基づいてデータの形状を記述します。実際のモデルはより高度なものですが、簡単な例としてモデルを各記号と出現確率との対応表として考えてみます。

「エントロピーコーダー」はほぼすべての圧縮アルゴリズムにおいて最終段階に位置し、最終的な圧縮結果である「生のビットストリーム」、つまりファイルフォーマットのような構造を一切持たないただのビットストリームを生成します。

より重要な「モデル」と「エントロピーコーダー」の2つに注目すると、私たちのデータモデルはデータを可能な限り効率的にエンコードするためにエントロピーコーダーに一連の確率を渡し、エントロピーコーダーは圧縮されたビットストリームを出力します。では、エントロピーコーダーは渡された確率をどのように活用し、圧縮を行う上でどう役立てているのでしょうか？

・エントロピーコーダーの役割
物事を単純化するためエントロピーコーダーの役割のうち「算術符号化」にのみ焦点を当てます。算術符号化はシンボルの出現確率に基づいてデータをエンコードします。「ABABAAC」というデータを圧縮する場合、まずは各シンボルの確率を求めます。

どのシンボルが出現するかの確率をまとめると0～1の範囲として表すことができます。これで実際の圧縮を行う準備が整いました。

データの先頭のシンボルは「A」なので、範囲は0～0.571となります。

2番目のシンボルは「B」なので範囲は0.571～0.857となりますが、先頭のシンボル「A」の範囲0～0.571の内部に含まれることを考慮すると「AB」の範囲は0.327～0.490となります。

同様にして全てのシンボルを処理すると、最終的に「ABABAAC」の範囲は0.3873～0.3885となります。

すなわち「ABABAAC」を圧縮した値としてはは0.3873～0.3885の範囲に含まれるどんな数値でも正解ですが、圧縮率を考えるとなるべく少ないビット数で表現できる値とするのが理想的であり、ごく簡単な演算を行えば「0.3876953125」というマジックナンバーを算出することができます。元のデータ「ABABAAC」は8ビットASCIIコードで合計56ビットが必要ですが、最終的に得られたマジックナンバー「0.3876953125」は10ビットしか必要ありません。

ではマジックナンバーから元のデータを得る方法を見ていきます。解凍器はマジックナンバーに加えて圧縮に使用したのと同じ確率および元のデータの長さを受け取ります。マジックナンバーが確率のどの範囲に位置するかを確認することにより、先頭のシンボルが「A」であることがわかります。

「A」の範囲0～0.571をさらに確率の範囲で細分することにより、2番目のシンボルが「B」であることがわかります。

同様に範囲を細分することにより、元のデータが「ABABAAC」であることがわかるというわけです。

・確率が圧縮に及ぼす影響
確率がどのように圧縮効果に影響を及ぼすのかを見るために、新たに「A」が極端に多く含まれるデータを使用します。

初めに使用した比較的均等にシンボルが含まれるデータの場合は「平均ビット/シンボル」の値が1.38ですが、「A」が極端に多く含まれるデータの場合は0.82となります。つまり特定のシンボルの出現確率が高い(データの偏りが大きい)ほど圧縮率は向上します。この「平均ビット/シンボル」は「情報エントロピー」と呼ばれ、可逆圧縮における圧縮の限界を示す指標となります。

◆コンテキストの重要性
ここまではシンボルの出現頻度のみを考慮する非常に単純なモデルを取り上げていました。しかし実際のシンボルの確率は「コンテキスト(文脈)」に大きく影響されます。英語の場合を例とすると、「U」が現れる確率は約0.028です。ただし「Q」の直後に「U」が現れる確率は約0.999に跳ね上がります。

単一のコンテキストを用いてシンボルの出現確率を決定することを「オーダー1モデル」と呼びます。オーダー1モデルでは直前のシンボル1つだけをコンテキストとして考慮しますが、オーダー2・オーダー3・オーダー4……と拡張することも可能であり、直前のN個のシンボルをコンテキストとして考慮することになるので「オーダーNモデル」と呼びます。

「オーダーNモデル」をエントロピーコーダーに組み込むには、直前のコンテキストに応じて別個の確率表を使用すればよさそうです。ケースを簡略化するため、オーダー1モデルを用いて「TO BE OR NOT TO BE」という文字列に算術符号化を適用してみましょう。

文字列の先頭に「T」が出現する確率の範囲が以下の図の通りだったとします。

「T」の次に「O」が出現する確率の範囲は別のものが適用されます。

「O」の次に空白が出現する確率の範囲。

空白の次に「B」が出現する場合の……といった具合に次々と別の確率の範囲が適用されていきます。

最終的に、「TO BE OR NOT TO BE」の範囲は0.05870～0.05871となります。

コンテキストを使用しない場合とオーダー1モデルを使用した場合とを比較すると以下の表の通りとなります。コンテキストを使用した方がより強力な確率を得られるのが明確となっています。

◆LLMと圧縮
LLMは高度な予測能力を有していることにより、圧縮アルゴリズムと非常に密接な関係があります。2023年にGoogle DeepMindが発表した論文によると、言語モデリングと圧縮は「同じものの二つの見方」であるとされています。

・LLMの圧縮メカニズム
LLMは与えられたコンテキストに基づいて次に来る単語(トークン)の確率分布を予測します。この予測能力は圧縮における「モデル」の性能に直結します。LLMは訓練を通じて「ビット/シンボル」数を最小化するように最適化されますが、これは圧縮におけるエントロピーを低くすることに相当します。

・LLMによる圧縮の実験
LLMを圧縮に利用する場合、モデルの予測がどれだけ実際のシンボルに近かったかが重要になります。予測が正確であれば少ないビット数で表現でき高い圧縮率が得られます。

ただ、既に旧式とされるLLMであっても優れた圧縮率を示すことができます。チャールズ・ディケンズの文章を算術符号化で圧縮する実験を行ったところ、オーダー1モデルを使用した場合にオリジナルに対して24％で圧縮していたところ、GPT-2を使用するとオリジナルに対して10％まで圧縮率が向上しました。

・現実面からみたLLM圧縮の課題
高い圧縮率を達成できるにもかかわらず圧縮が必要なシーンでLLMがあまり使用されていない理由は、圧縮ツールの目的が単にデータをできるだけ小さくすることだけではないからであり、特にHTTPレスポンスのような単純なタスクでの実用化は難しいとされています。モデル自体のサイズや圧縮・解凍の際に必要となる計算リソースの大きさが、圧縮によって節約されるデータ量よりも大きくなってしまうためです。

◆まとめ
圧縮アルゴリズムとLLMはどちらも「予測」という共通の基盤を持っています。圧縮はデータの冗長性を予測してより効率的な表現を見つけるプロセスであり、LLMは文脈に基づいて次のシンボルを予測することに特化しています。この両者は情報エントロピーという数学的枠組みで結びついており、根本的には同じ数学的原理に基づく2つの表現にすぎないといえます。