GZIPで10行未満のコードからMNISTで78%の精度を達成
(jakobs.dev)- MNISTの手書き数字分類をGZIP圧縮とk近傍法(k-NN)だけで約78%の精度まで引き上げた実験で、圧縮をモデル不要の分類ツールとして使えることを示している
- 2つの画像サンプルを一緒に圧縮したときに長さがどれだけ変わるかをもとに正規化圧縮距離(NCD) を計算し、これを画像間の類似度指標として用いる
- 各テストサンプルは訓練サンプル100件と比較され、距離が最も近いk=5の近傍の多数ラベルが予測値になる
- 計算コストのため、精度はテストセット全体ではなくテスト画像の一部で測定しており、全体セットを使えば評価はより正確になる可能性がある
- 公開サンプルには圧縮長のキャッシュを作成しているのに実際のNCD計算では使っていないリファクタリング時のミスが残っており、キャッシュの削除または
compute_ncdへの反映が必要
GZIP + k-NNでMNISTを分類する
- 実験ではMNIST手書き数字データセットをGZIP + k-NNの組み合わせで分類する
- 短いコード例では
gzip.compress(z.tobytes())の結果の長さを圧縮長として使い、NCDを計算したうえで、近傍5件のラベルの最頻値を選ぶ - 実行可能な例はJupyter Notebookにある
- 目的は最高精度ではなく、圧縮をモデル不要の分類ツールとして活用するアイデアを手軽に検証することにある
- 10行未満のコードは実験の核心というより、遊びとしてのコードゴルフ要素に近い
類似度計算と分類手順
- NCDは、2つのデータポイントをまとめて圧縮したときのコストが、それぞれ別々に圧縮した場合と比べてどの程度異なるかを正規化し、類似度を測定する
- 圧縮長は次の形で計算する
Cx1 = len(gzip.compress(x1.tobytes()))Cx2 = len(gzip.compress(x2.tobytes()))Cx1x2 = len(gzip.compress((x1 + x2).tobytes()))
- NCDの式は
(Cx1x2 - min(Cx1, Cx2)) / max(Cx1, Cx2)の形 - 分類では各テスト画像と訓練画像の距離を計算し、近い順に並べたうえで、最も近い5件のラベルの多数決を使う
- 実験では訓練サンプル100件を基準に比較し、計算コストのためテストセットも一部のみを使用した
参考にしたアイデアとコード上の注意点
- このアプローチはtext generation from data compressionの記事とparameter free text classification論文に着想を得ている
- 記事執筆後、Andreas Kirschが2019年に似た手法で書いたMNIST by ZIPの記事も見つかった
- サンプルコードは訓練サンプルの圧縮長キャッシュを作成しているが、実際のループではそのキャッシュ値を使っていない
- 通常版と難読化版の両方で
compressed_lengthsまたはclsを作成しているが、NCD計算ではキャッシュされた長さを使っていない - キャッシュを削除して
training_setをそのまま使うか、compute_ncdがキャッシュ値を活用するように変更すれば、コードの意図と実装が一致する
- 通常版と難読化版の両方で
1件のコメント
Hacker News のコメント
コードの距離関数をより単純な尺度に置き換えてみたところ、MNIST分類では GZIP距離は精度も低く、計算量もはるかに大きい
Gzip距離：約3分、精度78% / ユークリッド距離：約0.5秒、93% / ジャカード距離：約0.7秒、94% / Dice非類似度：約0.8秒、94%
ジャカードとDiceは画像を二値化してから測定している
GZIPアルゴリズムに詳しいわけではないが、結果がここまで低いのは興味深く、画像中心の圧縮アルゴリズムならもっと良くなるのかも気になる
記事自体は創造的で、コードと説明も良かったが、上のベースラインがgzipのスコアに文脈を加えてくれると思う
NMI skimage：約30秒、精度95% / NMI numba：約0.6秒、精度95%
ChatGPTが出してくれた
numbaコードで、2x2の結合カウント、エントロピー、正規化相互情報量を計算した個人的にはCIFAR10の高速学習に関心があるので、こうしたアプローチは他の領域でもかなり有用そうに見える
https://github.com/benjamin-recht/mnist_1_pt_2/tree/main
zstandardも入れてみると、Zstd(level=3)は約3.5秒で精度88%と、gzipよりはるかに速かった
Cx1x2を計算するときにx1+x2の代わりに(x1-x2)*2を使うと、zstdは精度93%まで上がる2つの配列を足さずに上下に積むと性能が完全に崩れて20%未満になるが、文字列分類ではそのやり方がうまく効くようで興味深い
他の手法と比べると、Linear SVCは92%、RBFカーネルSVCは96.4%、多項式カーネルSVCは94.5%、ロジスティック回帰は89%、ナイーブベイズは81%程度
出典: https://dmkothari.github.io/Machine-Learning-Projects/SVM_wi...
オンラインの記事を見ると、K-NNだけでもはるかに良い結果が可能に見えるので、著者はgzipを使って問題をわざわざ難しくしたようにも思える
単純なモデルから始めて、後で複雑さを足すのが好きだが、実際にはうまく機能する問題でも「ロジスティック回帰では駄目だ」とよく言われた
MNISTでベースライン性能がどれくらいだと思うか尋ねると、20〜30%と推測する人が多い
機械学習をしている人たちでも、モデルの複雑さを大きく増やしたときに 収穫逓減がどれほど早く来るかを過小評価しがち
単純なモデルで性能が良くない場合、より複雑なモデルでも優れた性能を得るのは難しかったことが多い
MNISTデータセットを紹介した元論文も約98%の精度を出しており、最近のニューラルネットは99.87%の精度まで行っている
https://paperswithcode.com/sota/image-classification-on-mnis...
圧縮はもともと問題をより難しくするためのもので、実際にも依然としてそう機能している
他のモデルはどこかでノイズを加える傾向があるので、gzipの前に特徴量エンジニアリングを入れたらどうかと思う
たとえば最初にガウシアンブラーと畳み込みを適用し、その後に特徴選択でディープラーニングを使う、といったことも可能そう
コードは優雅で短いかもしれないが、MNISTで 精度78% は非常に悪い部類
TensorFlowで作ったダミーモデルでも簡単に精度90%に到達し、最高モデルは99.87%
ベンチマーク: https://paperswithcode.com/sota/image-classification-on-mnis...
興味深いのは、モデルを学習しなくても 圧縮を分類に使えるという点
だから、もっと安価で損失のある別の情報理論的尺度も使えるのか、という問いにつながる
To Compress or Not to Compress- Self-Supervised Learning and Information Theory: A Review
[https://arxiv.org/abs/2304.09355\)" class="ud link">https://arxiv.org/abs/2304.09355\](https://arxiv.org/abs/2304.09355\)*
GZipが最新の最高性能に到達するかどうかが興味深いのではなく、それなりに分類できるという事実が興味深い
熊がMozartを完璧に再現するかではなく、ピアノを弾けること自体が驚き、というのに似ている
それでもベースラインより8倍良く、圧縮が 表現を学習できることを示している
compute_ncdをユークリッド距離に置き換えると、テスト精度が 15ポイント上がり、計算量も大幅に減るdistances = [(np.sqrt(np.sum(np.square(x1-x))), label) for x, _, label in compressed_lengths]のように変えればよい情報理論、圧縮、学習アルゴリズムの深いつながりを扱った本としては MacKay が一番よかった
きちんと教育を受けた人には常識かもしれないが、独学で実務寄りの機械学習をやってきた立場としては、このテーマが素粒子物理や宇宙論のような分野にまでつながっているのを見て、強烈な「なるほど！」の瞬間を味わった
1人でも同じ気づきを得られればと思って残しておく
gzip の基盤の一つである元の Lempel-Ziv 圧縮が、単にサイズを小さくしようとする試みというより、「有限列の複雑度」の研究から生まれたものだと知ったときは、かなり印象的だった
https://ieeexplore.ieee.org/document/1055501
公平に言えば、MNIST は UMAP に通すだけでもほぼ完璧に分離される
今どき MNIST で性能を悪くするには、かなり頑張る必要があると思う
https://github.com/lmcinnes/umap_paper_notebooks/blob/master...
もうこのデータセットは引退させたほうがよく、QuickDraw のようなデータセットのほうがずっと筋が通っていると思う
それ自体を大きな成果と見るのは難しいが、それでも動くのを見るのは興味深い
家に帰ったら、MNIST を解くことが比較的簡単だという点を記事に追記する
それでも、単純で妥当なアルゴリズムの大半が 97% の精度に達するので、教育用ツールや Hello world データセットとしては今でも価値がある
最初からツールを自作しても宿題規模に収まり、「郵便物の数字認識」のように誰でも理解できる有用な課題でもある
圧縮を理解していれば、このアプローチも非常に単純なアイデアなので、MNIST が公開された初日にも書けただろうし、それでも 78% の精度が出たはずだ
その点がかなり驚きに感じられる
リポジトリも UMAP を定義していないが、ChatGPT を信じるなら、UMAP は Uniform Manifold Approximation and Projection の略で、機械学習とデータ分析で使われる 次元削減および可視化手法だ
この分野は趣味レベルだが、強く圧縮されたデータは暗号化されたデータのように エントロピーが高いのではないかと思う
圧縮済みデータからパターンを見つけて元の数字を判別できるなら、そのパターンをよりよい圧縮に活用できるべきではないだろうか
「7 7」は「7 3」よりもうまく圧縮されるはずで、ラスター画像の「7 7」も「7 3」よりうまく圧縮されるだろう、という考え方だ
圧縮不可能性は効率的な暗号演算の特徴だ
Kolmogorov 複雑性の記事の圧縮セクションを参照: https://en.wikipedia.org/wiki/Kolmogorov_complexity#Compress...
圧縮で好きな概念の一つは 鳩の巣原理で、すべての圧縮アルゴリズムには、入力よりも大きくなる出力が必ず存在するというものだ
よく設計された暗号化ペイロードでも圧縮を試みることはできるが、平均的には出力が入力より大きくなり、圧縮が役に立たなくなるため「圧縮不可能」と呼ぶ
https://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_...
数年前、MNIST 画像の サイズを「メタ特徴」として使った事例があったような気がするが、すぐには見つけられない
画像を見もせずに、その特徴一つだけでもおおよそ 90% 前後の精度が出ていたと記憶している
gzip で圧縮したサイズなのか？ 単に MNIST 画像がどれだけ暗いか、つまり暗いピクセルの割合だけを見るなら約 20% の精度で、ランダム推測の2倍ではあるが 90% には遠く及ばない
その論文の著者たちがミスをして、結果がベンチマーク上位に跳ね上がってしまったのではないかと思う
その件以来、理論に一貫性がないと見ていたが、それでも GZIP だけで 78% の精度は印象的だ
この問題が圧縮トリックのよい適用対象かどうかは別として、実験する人たちは
gzipを使うのをやめてzlibを使ったほうがよい1行目を
gzip.compressからzlib.compressに変えれば、同じ分類性能で速度は3倍速くなるはずだ