gzipでテキスト分類(圧縮距離NCD+kNN)を73記事で追試——93.8%は出るが、文字数だけでも89.2%出た
2023年、「gzipがBERTに勝つ」という論文が機械学習界隈で大きな話題になった。ニューラルネットも学習も一切なし。テキストをgzipで圧縮したときのサイズから正規化圧縮距離(NCD)という距離を計算し、あとはk近傍法(kNN)で多数決するだけ——それでいくつかのベンチマークではBERTを上回った、という主張だった。
ただしこの話には続きがある。公開コードを検証したKen Schutte氏が、k=2のkNNのタイブレーク処理が「上位2件のどちらかが正解なら正解」という実質top-2精度になっていたことを指摘したのだ。正しく評価し直すと、数字はそれなりに下がる。「圧縮だけでBERTに勝つ」という見出しと、「評価にバグがあった」という続報。両方読んだ上でずっと気になっていた。バグを除いた素のgzip分類は、実際どのくらい戦えるのか?
ちょうどこのブログには手頃な実験材料がある。前回のセルフ監査記事で使った、自分のブログ記事コーパスだ。今回は既存の全73記事を使い、NCD+kNNでタグ分類の追試をやってみる。外部データは一切使わない。ついでに、話題になったタイブレークのバグも自分の手で再現して、正しい評価との差を実測する。
実験に使ったコードの全文はGitHubに置いています。
実験設計: zlibの圧縮サイズだけで距離を作る
正規化圧縮距離(NCD)の定義はシンプルだ。C(x)を「テキストxを圧縮したときのバイト数」として、
NCD(x, y) = (C(xy) - min(C(x), C(y))) / max(C(x), C(y))xyはxとyをそのまま連結した文字列。似た2つのテキストを連結すると、圧縮器が共通パターンを使い回せるのでC(xy)はあまり増えない——この直感を距離にしたものだ。理論的にはコルモゴロフ複雑性の近似という背景があるが、実装はPython標準のzlib(gzipと同じDEFLATE圧縮)で数行で書ける。今回は圧縮レベル9(最高圧縮)を使った。
データはこのブログの既存73記事(執筆中の本記事は除く)。frontmatterと画像・コード・リンク構文を取り除いた本文プレーンテキストをUTF-8バイト列にして圧縮する。前処理は前回のUMAP記事と完全に同じにした。ラベルも前回と同じ規則で、タグに「実践記/機械学習」を含む記事を実験系(53記事)、「Claude入門/比較」を含む記事を入門系(12記事)とし、どちらでもない8記事は「その他」として分類対象から外した。
評価は次の2タスク。どちらもleave-one-out(1記事を抜いて残り全部を訓練データにする、を全記事分繰り返す)で測る。
- タスクA: 実験系 vs 入門系の2クラス分類(65記事)
- タスクB:
series(連載)を持つ22記事について、6つある連載のどれに属するかを当てる6クラス分類
対照群として、前回と同じTF-IDF文字n-gram(単語分割なしの2〜4文字n-gram)を使った2つの手法——コサイン距離の1NNと、ロジスティック回帰——を同じ条件で回した。
結果その1: NCD距離行列にはブロック構造がはっきり出る
まず、73記事×73記事の全ペアでNCDを計算した距離行列を見てほしい。行と列は、6つのseries→seriesなしの実験系→入門系→その他、の順に並べ替えてある。
圧縮サイズしか見ていないのに、構造はちゃんと浮かび上がる。一番目立つのは右下、入門系の記事同士が作る濃い青のブロックだ。入門系記事内の平均NCDは0.881で、実験系内の0.906より近く、トラックをまたいだペアの0.943よりはっきり近い。対角線上には「多様体学習の実験」「生成モデルを一から実装する」といったseriesの小さな濃いブロックも見える。実際、全2,628ペア中で最もNCDが小さかったのは「初心者向け生成AIのコツ」と「Claudeの使い方」のペア(0.766)で、上位はほぼすべてClaude入門系の組み合わせだった。gzipは「Claude」「プロンプト」のような繰り返し現れる文字列を素直に拾っているらしい。
結果その2: 93.8%——ベースラインには圧勝、TF-IDFには届かない
タスクA(実験系53 vs 入門系12)の精度を手法別に並べる。
| 手法 | 精度 (LOO) |
|---|---|
| 多数決(全部「実験系」と答える) | 81.5% |
| 本文の文字数だけ(閾値1本) | 89.2% |
| TF-IDF + ロジスティック回帰(class_weight=balanced) | 87.7% |
| gzip NCD + 1NN | 93.8% |
| gzip NCD + kNN(k=5) | 95.4% |
| TF-IDF + 1NN(コサイン距離) | 96.9% |
gzipは「思ったより戦える」。学習ゼロ・特徴量設計ゼロで93.8%、k=5なら95.4%。教師あり学習であるロジスティック回帰(87.7%)より上に来た。1NNが間違えた4記事を見ても、「Claude CodeのSkillとHookの実践記」の最近傍が「Claudeのエージェント/Skill入門」になるといった、人間が読んでも紛らわしい混同ばかりで、負け方に納得感がある。
ただし順位には二重の但し書きが付く。第一に、同じ1NNで距離だけ差し替えたTF-IDFコサイン距離は96.9%で、gzipより上。「gzipが強い」というより「1NNという分類器がこの規模のデータで強く、距離としてはTF-IDFの方が上」というのが正確なところだ。第二に——これは後述するが——灰色のもう1本のベースライン、「本文の文字数だけ」で89.2%出ている。この数字が今回の実験で一番効いた。
タスクB(series当て・6クラス)はもっと差が開いた。NCD+1NNは77.3%(多数決ベースライン27.3%)に対し、TF-IDF+1NNは95.5%(22記事中21正解)。NCDの誤答5件のうち3件は「最適化のライフレッスン」連載を「生成モデルを一から実装する」連載と取り違えたものだった。
タイブレークのバグを再現する: 「実質top-2精度」は何ポイント盛るのか
話題になった論文の公開コードでは、kNNのkが2に設定されていた。k=2で2つの近傍のラベルが割れたとき(2クラスなら必ず1対1のタイになる)、本来なら何らかのルールで1つに決めて、その予測が正解かどうかを数えるべきだ。ところが元実装の評価は、上位2件のどちらかが正解ラベルなら正解とカウントしていた。つまり報告された数字は通常の精度ではなく、top-2精度に相当する。
これを自分のコーパスで意図的に再現した。「正しい評価」(タイはランダムに1つ選ぶ・1,000回平均、タスクBはタイ時最近傍を採用)と「バグ入り評価」(top-2精度)を、同じk=2・同じ距離行列で比較する。
- タスクA: 93.8% → 95.4%(+1.5ポイント)
- タスクB: 77.3% → 81.8%(+4.5ポイント)
クラス数が多く、タイや際どい近傍が増えるタスクBほど水増し幅が大きい。これは元論文への指摘とも整合する——影響はデータセット依存で、多クラスのベンチマークほど「盛れて」いた。1.5〜4.5ポイントというと小さく聞こえるかもしれないが、当時の「BERTに勝った」という主張はまさにこの数ポイントの差の上に成り立っていたので、勝敗をひっくり返すには十分な幅だ。
ついでに言うと、k=2の「正しい評価」はタイブレークの定義次第でほぼk=1に一致する(タイ時に最近傍を採るならk=1と完全に同じ)。元論文がなぜk=2を選んだのかは、いま見返しても謎のままだ。
日本語UTF-8はどう圧縮されているのか
日本語のひらがな・漢字はUTF-8で1文字3バイトを占める。バイト列を見るgzipにとってこれがどう効いているのかも観察した。
- 圧縮前は平均2.62バイト/文字(漢字かな3バイトと半角英数1バイトの混合)
- zlib圧縮後は約1.06バイト/文字まで縮む(圧縮率は平均43%)
3バイトかかっていた日本語1文字が、圧縮を通すと約1バイト——UTF-8の3バイト表現には大量の冗長性があり、DEFLATEはそれをきちんと絞り出せている。「マルチバイトだからgzip分類は日本語に不利」という単純な話にはならなそうだ、というのが今回の範囲で言えることだった。
一方で、圧縮器を距離の道具として使うときの「あら」も2つ見えた。まずNCD(x, x)、つまり自分自身との距離が0にならない。全73記事の平均で0.030あった。理論上のNCDは同一テキストなら0だが、zlibは理想の圧縮器ではないので、連結テキストの後半を「さっきと同じ」と完全には言い切れない。もうひとつはDEFLATEの32KBという参照ウィンドウだ。連結バイト列が32KBを超えるペア(全体の2.4%)では、後半のテキストを圧縮するときに前半の冒頭部分がもう窓の外に出てしまっている。今回のコーパスは平均9KB/記事なのでほぼ無傷だったが、長文で同じことをやるなら効いてくるはずだ。
前回のUMAP記事との照合: 距離を変えても結論は同じか
前回の記事では、TF-IDF空間での結論は「実践記 vs Claude入門というタグ2分類はほとんど分離しない(シルエットスコア0.064)、一方でseries単位ならくっきり固まる」だった。距離の定義をNCDに総取り替えしても、同じ結論になるのか。
なった。まず2トラックのシルエットスコアは、NCD距離で0.044。TF-IDFの0.064と同水準の「ほぼ無分離」だ。93.8%で分類できるのに分離していないというのは矛盾に聞こえるが、そうではない——クラスの「境界」は最近傍の多数決で引ける程度には存在するけれど、クラスタと呼べるほど塊としては離れていない、ということだ。そしてseriesは今回も一貫していた。6つの連載すべてで、連載内の平均NCD(0.854〜0.895)がコーパス全体の平均(0.921)を下回った。
| series | 記事数 | series内平均NCD | 全体平均との差 |
|---|---|---|---|
| 多様体学習の実験 | 4 | 0.854 | -0.067 |
| 生成モデルを一から実装する | 4 | 0.858 | -0.063 |
| 画像処理の周波数分析 | 2 | 0.859 | -0.062 |
| Self-Attentionを実装する | 3 | 0.874 | -0.047 |
| 探索と活用のアルゴリズム | 3 | 0.882 | -0.038 |
| 最適化のライフレッスン | 6 | 0.895 | -0.026 |
| 全記事ペアの平均 | — | 0.921 | — |
ただし濃淡はある。TF-IDFではseries内距離が全体平均より0.1〜0.23も短かったのに対し、NCDでの差は0.03〜0.07と控えめだ。series当てタスクの精度差(NCD 77.3% vs TF-IDF 95.5%)はこの構造の弱さをそのまま反映している。gzipは「Claude」「結び目」のような繰り返し文字列は拾えるが、TF-IDFのように「その連載でしか出ない珍しい断片を重み付けする」仕組みを持たないぶん、連載の指紋の検出力は一段落ちる——という解釈で辻褄が合う。
正直に書いておくべきこと
- コーパスが小さい。タスクAは65記事なので、1記事の正誤で精度が約1.5ポイント動く。93.8%と96.9%の差(2記事分)も、95%信頼区間を考えればかなり心もとない。この記事の数字は「この規模でもこのくらいの傾向は見える」以上のものではない。
- クラスが不均衡(53対12)。精度だけ見ると多数決の81.5%が既に高い。だからこそ文字数ベースラインと少数派クラスの再現率(NCD 1NNで入門系83.3%)を併記した。
- ロジスティック回帰の87.7%は「この設定では」の数字。デフォルト設定では全記事を「実験系」と答える多数決マシンに退化した(精度81.5%、入門系の再現率0%)ので、class_weight=balancedにした値を載せている。特徴量が26万次元で訓練データが64記事しかないのだから、教師あり学習には根本的に分が悪い土俵だ。
- 書き手が全記事同一人物という、一般のテキスト分類ベンチマークにはない特殊条件がある。文体の差がないぶんタスクは難しくなっているかもしれないし、逆に定型的な言い回しの共有で簡単になっているかもしれない。
- 元論文はgzipだが今回は
zlib(同じDEFLATE圧縮でヘッダが違うだけ)。また「正しいタイブレーク」の定義(ランダム/最近傍)にも幅があり、それ自体で数字は微妙に動く。
手を動かして意外だったこと
一番の想定外は、対照群のつもりで足した「本文の文字数だけ」ベースラインの89.2%だった。実験系の記事は平均4,238文字、入門系は平均1,567文字。閾値を1本引くだけで65記事中58記事が正しく分かれてしまう。つまりNCD+1NNの93.8%のうち、多数決から上積みした12.3ポイントの大半は「長さを見れば分かる」領域と重なっている可能性がある。NCDは定義上、圧縮サイズの比を取って長さを正規化しているはずなのに、だ。前回のUMAP記事で「次元削減の軸が実質、記事の長さ軸だった」という交絡に出くわしたばかりだが、距離をNCDに変えても同じ亡霊が出た。自分のコーパスの2トラックは、内容の前にまず長さが違う。ラベルと相関する交絡は、手法を替えたくらいでは消えてくれない。
もうひとつは、バグ再現の副産物。「上位2件のどちらかが正解なら正解」という評価は、コードを読めば明らかにおかしいと分かるのに、出てくる数字は+1.5〜4.5ポイントというもっともらしい範囲にしか動かないことだ。精度が60%から95%に跳ねるようなバグならすぐ気づく。数ポイントだけ静かに盛るバグは、その数ポイントがちょうど「勝敗」を分けるラインだったとしても、結果の見た目からは検出できない。評価コードのバグは、派手なものより地味なものの方が怖い。
まとめ
- Python標準の
zlibで正規化圧縮距離(NCD)を実装し、自分のブログ73記事のタグ分類を追試した。実験系53 vs 入門系12の2クラス分類(leave-one-out)で、NCD+1NNは93.8%。多数決81.5%とロジスティック回帰87.7%を上回ったが、同じ1NNのTF-IDFコサイン距離96.9%には届かなかった - 話題になった「k=2のタイブレークが実質top-2精度」バグを再現すると、精度は2クラスで+1.5ポイント、6クラスのseries当てで+4.5ポイント水増しされた。当時の「BERT超え」を左右するには十分な幅
- 「本文の文字数だけ」の閾値分類で89.2%出た。長さ正規化を含むNCDでも、長さと相関したラベルの交絡からは逃げられていない
- NCD距離行列には入門系ブロック(内部平均0.881 vs トラック間0.943)とseriesの小ブロックがはっきり現れた。最も近いペアはClaude入門系記事同士(NCD 0.766)
- 前回のTF-IDF+UMAP記事との照合では結論が再現した。タグ2分類はNCDでもほぼ無分離(シルエットスコア0.044、TF-IDFでは0.064)、seriesは6連載すべてで内部距離が全体平均より短い。ただし差はTF-IDFより小さく、series当て精度も77.3% vs 95.5%で完敗
- 日本語UTF-8(平均2.62バイト/文字)はzlibで約1.06バイト/文字まで縮む。NCD(x,x)は0にならず平均0.030、DEFLATEの32KB窓を超えるペアも2.4%あり、圧縮器は「理想の距離計」ではない
関連記事
このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。