テキスト分類において、Gzip と KNN が Transformers を上回る

 (twitter.com/LukeGessler)
2 ポイント 投稿者 GN⁺ 2023-07-15 | 1件のコメント | WhatsAppで共有
  • gzip のような単純な圧縮器と k-最近傍(kNN) 分類器を組み合わせた、ノンパラメトリック(non-parametric)なテキスト分類手法を提案
  • 学習パラメータがまったく不要でありながら、軽量・汎用的で、DNN と比べて計算コストの負担が低い
  • 事前学習なしのディープラーニング手法と比較して、6つの in-distribution データセットで競争力のある結果を達成
  • 4つの 低リソース言語を含む 5つの OOD(out-of-distribution) データセットすべてで BERT を上回る
  • ラベル付きデータが不足して DNN の学習が難しい few-shot 環境でも優れた性能を発揮

背景と問題提起

  • DNN は高い精度でテキスト分類に広く利用されている
  • しかし 数百万のパラメータと大量のラベル付きデータを必要とするため、計算コストが大きい
  • このため、利用・最適化・そして OOD(out-of-distribution) 状況への転移は、実務においてコストの高い作業となる

提案手法

  • DNN の代替として、簡単で軽量、かつ汎用的なノンパラメトリック手法を提示
  • gzip のような単純な圧縮器と k-最近傍分類器を組み合わせた構成
  • 学習パラメータがまったく不要である点が中核的な特徴

実験結果

  • 6つの in-distribution データセットで、事前学習なしのディープラーニング手法と競合可能な水準の性能
  • 4つの低リソース言語を含む 5つの OOD データセットすべてで BERT を上回る
  • ラベル付きデータが少なすぎて DNN を効果的に学習させにくい few-shot 環境でも強みを示す

関連記事

1件のコメント

 
GN⁺ 2023-07-15
Hacker Newsのコメント

  • 論文への直接リンク: https://aclanthology.org/2023.findings-acl.426.pdf
    直感的には、要点は文書 x1、x2 と新しい文書 x があるとき、x の統計的規則性が x2 より x1 に近ければ、len(compress(cat(x1,x))) - len(compress(x)) < len(compress(cat(x2,x))) - len(compress(x)) になる、ということ。ここで cat は連結、compress は gzip のような圧縮器を指す。
    文字どおり len(compress(cat(x1,x))) - len(compress(x)) は、x の統計的規則性が与えられたときに、x1 の統計的規則性を圧縮するために追加で必要になるバイト数である。x1 と x が似ているほど、x だけを圧縮する場合に比べて cat(x1,x) を圧縮するのに必要な追加バイトは少なくなる。
    著者らはこのアイデアに基づく 正規化圧縮距離（NCD）という距離関数を使い、圧縮された文書に k 近傍法（kNN）を適用している。NCD と情報、Shannon エントロピー、Kolmogorov 複雑性との関係も扱っている。
    驚くことに、この単純で直感的な手法が、複数の ゼロショット分類 タスクで BERT を上回っている。ただし、より大きく新しい Transformer まで必ず上回るという意味ではない。

    • この手法がよりうまくいくのは、分布外データで、かつトークンが重なる場合に限られる。意味理解能力はなく、結果は正しいがタイトルは誤解を招く。
    • 単に文書を連結する代わりに、zstd の圧縮辞書サポートを使うと少し良い結果になるのか気になる。
      文書を圧縮辞書として使った場合と使わなかった場合の圧縮サイズを比較する、という形である。zstd は少なくとも 20+ レベルでは gzip よりはるかに高い圧縮率を出すので、gzip でうまくいく理由が Kolmogorov 複雑性の近似にあるなら、よりうまく機能する可能性もある。
    • 解こうとしている問題が結局「x は x1 と x2 のどちらにより似ているか」なら、これは LLM が解く問題とは違って見えるので、よりうまくできても驚きではない。
      x1 が英語で、x が同じ文書のヘブライ語訳なら、LLM のほうがうまくやるのではないかと思う。
    • 厳密に言えばゼロショットではなく フューショット である。依然として基準となる学習用プロトタイプ集合が必要だ。
    • 画像にも同じ方法が可能なのか気になる。
      最近画像を扱いながら JPEG を出力してみたが、同じ基本ピクセルからでも非常に多様な画像ができる。画像がノイズの多いランダムに近いものほど JPG ファイルサイズは大きくなり、逆に写真らしく見えるほど JPG サイズは小さくなるのが興味深い。

  • AI と圧縮の等価性に興味があるなら Hutter Prize を見るとよい :) http://prize.hutter1.net/
    Large Text Compression Benchmark も見る価値がある http://mattmahoney.net/dc/text.html - 現在世界最高の圧縮器は、ffmpeg と QEMU を作った有名な Fabrice Bellard のニューラルネットワークである。
    こうしたページの適切な テキスト専用スタイル も本当に気に入っている。

    • 特に、次に来る内容を予測して 区間の重み を調整する算術符号化ベースの圧縮アルゴリズムは非常によく似ている。
      予測するバイト/ビットの文脈に応じて算術符号化（https://en.wikipedia.org/wiki/Arithmetic_coding）を調整するため、続く内容をより正確に予測できるほど、エンコードはより効率的になる。タスク自体が GPT のような Transformer と非常によく似ている。
      完璧な予測では算術区間が小さくならないため、追加の保存コストはほとんどなく、したがってビットも保存されない。ただし公正なベンチマークを行うには、展開器のサイズも計算しなければならない。
    • 数学を深く掘り下げると、多くのものは根本的に同じになる。超解像はもっともらしく包装した デコンボリューション であり、単層パーセプトロンは線形カーネル SVM でありロジスティック回帰でもあり、FFT は単なる因数分解である。
    • 著者らが 正規化圧縮距離（NCD）を使っている点が重要だ。NCD は Kolmogorov 複雑性を近似する方法である。
      かなり古いアイデアで、[1,2] を見ればよい。古いが、パーセプトロンのように今でも非常に有用だ。
      [1] Li and Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
      [2] Clustering by compression. https://arxiv.org/pdf/cs/0312044
    • Fabrice Bellard は本当に生ける伝説だ。そのリストには QuickJS、jslinux、tcc、TinyGL も追加すべきだ。
    • この種の「圧縮」は、本質的には物理学の理論のような 理論を通じた理解 に近い。
      理論は、同じ「登場人物」だけで多くのことを説明する物語に似ている。ここでの登場人物は概念に近く、例えば原子がこれに当てはまる。

  • この手法がより強いのは ニュース に限られる、という点を指摘したい。
    Yahoo Questions では最高性能ではない。ニュースは似たような書き方をされ、ときには一部がコピーされることもあるため、共通する単語が多いと見ても無理はない。
    Yahoo Questions はフォーラムなので単語のばらつきは大きいだろうが、単語同士には意味的類似性がある。
    つまり gzip は単語の重なりが多いときに強く（gzip 圧縮時のサイズ増加が小さい）、意味的類似性が重要な場合は DNN が常に勝つ。
    結果は興味深いが、聞こえるほど興味深くはないと思う。

    • 意味的類似性が異なるなら、それはどう機能するのだろうか。学習中に意味的に似た 表現 をまとめる問題にすぎないのではないかと思う。

  • この結果が分布外データから出たものだという点を、とても重要に見るべき。たとえば「Kinyarwanda、Kirundi、Pinyin」のような言語のニュースである
    より一般的な設定では、BERTが今でも圧倒的に勝つ
    こういう単純な方法が非常に効果的になり得るのは素晴らしいが、過度に誇張して売り込むべきではない

    • この点は本当にもっと強調されるべき。タイトルだけ読んだときは、これまで知られておらず、まだ説明されていない物理法則、この場合は言語学の法則の証拠を偶然発見したかのように驚いた
      しかし引用されている条件を見ると、むしろかなり直感的だ。まったく知らない言語のテキストを分類するとは何なのか。Kirundiのテキストを分類しろと言われたら、意味はまったく分からず、できる最善のことは単語または文字シーケンスの頻度を見つけ、似た頻度のフィンガープリントを持つテキスト同士をまとめることだ
      実際の意味は依然として分からないが、ランダムよりは良くなり得るし、実際そうなる。良い知らせは、これがまさにgzip+kNNのやっていることであり、彼らの本業であり存在理由だという点だ
      このテキストを読んで理解しようとしたり、次の文字を予測しようとしたりしても、あまり得るものはない。普通の人なら、その言語を知らないのでそもそも試みもしないだろう。残念ながらBERTはまさにそれをやる。BERTにできる唯一のことだからだ。それでも普通の人間、おそらく普通でない人間よりも活用できているのは称賛に値する

  • 実際、とても賢く、直感的にも理解できる
    似たテキスト片を2つつなげれば、異なるテキスト片を2つつなげたときよりもうまく圧縮できるはずだ

    • 知られてはいるが、ややあまり知られていない手法だ。ここでの主な貢献は定式化と測定である

  • これはこの手法の勝利というより、ディープラーニングベースの類似度に対するネガティブなシグナルに近いように見える
    LLMブームの中で、LLMがすごいのは確かだが、多くの人が純粋なテキスト類似度用の埋め込み層でも同じような進歩があったと仮定しているようだ
    そのため、あらゆる埋め込みデータベースのブームが起きたが、私にはそれを裏付ける証拠はほとんどないように見える

    • https://twitter.com/eugeneyan/status/1678060204943097863

      When Deepmind needs semantic retrieval, they just use the largest index on the planet.
      面白い事実: クエリ-文書の類似度はベクトルではなく、単純なTF-IDFで処理していた。検索文書数が45件を超えるとベクトル検索より良く、実際には50件を使っていた
      https://blog.vespa.ai/improving-zero-shot-ranking-with-vespa...
      This case illustrates that in-domain effectiveness does not necessarily transfer to an out-of-domain zero-shot application of the model. Generally, as observed on the BEIR dense leaderboard, dense embeddings models trained on NQ labels underperform the BM25 baseline across almost all BEIR datasets.

    • ひとつだけ質問に答えてもらえるだろうか。LLMで類似度測定に使うテキスト埋め込みを作るとき、どの層を使うのか。入力層か。入力層+位置エンコーディングか。隠れ層か。出力層か。

  • リンクは論文PDFである https://aclanthology.org/2023.findings-acl.426.pdf を指すべきだ

  • 圧縮アルゴリズムは空間、つまりビットとバイトの節約/圧縮である。機械学習モデル、特に生成モデルは、人間の表現と思考を節約/圧縮するものだ
    テキスト分類は、人間の表現の上にある圧縮の一種だ。機械学習タスクでどちらがよりうまくいくかを説明してくれる、人間の言語とデータの根本的な性質が何かあるのだろうか。
    いつかそのような理論が形を成せば、圧縮されたビット/バイトのエンコーディングと圧縮された人間の表現が、何らかの空間で密接に関係しており、両者が何らかの形でつながっているという点は驚きではなくなるかもしれない。実際にそのような理論、たとえばエントロピーベースまたは物理ベースの理論は、特定の種類の人間表現の圧縮で圧縮アルゴリズムを使うべきか、機械学習モデルを使うべきかを選ぶ助けになる可能性がある
    データ中心で見ると、こうしたアルゴリズムを悪くする難しい負例とは何だろうか。現時点では、さまざまな人間のテキストデータの種類という観点からだけ、その理論を近似できるのかもしれない。たとえば統計的トピックモデルで混合を予測するのは、学術テキストではうまくいくが、インターネットのテキストでは苦戦する
    Wolfram Physics以外に、こうした理論を研究している人はいるのだろうか。

  • 完全に納得できる。圧縮は「理解」に関するもの、つまり入力を認識しラベル付けできる形で表現することだ
    認識されたビットがラベルより大きくなれば、ほら、圧縮になる。gzipがこのタスクでDNNより優れている可能性があるのは驚きではない

    • だとすると、他の圧縮アルゴリズムならさらにうまくいくこともあるのか気になる
    • 圧縮は理解の部分集合だと思う。子どもが文法的に正しく話し始めるとき、触れてきたすべての言語パターンを文法規則へ圧縮したということだ
      部分集合と言うのは、理解の方がより一般的だからだ。特定の圧縮アルゴリズムは浮動小数点数ではうまく機能するかもしれない。逆に脳と人工ニューラルネットワークは、性能は劣るとしても、どんな入力パターンでも圧縮できるのかもしれない

  • gzipが文全体の意味を反転させる「not」のような単語をどう処理できるのか分からない
    分かる人はいる？

    • Twitterの一部コメントにもあるように、これはトピックモデリング用だ。否定語は感情分析のようなタスクに比べると、ここではそれほど重要ではないかもしれない