「gzip beats BERT」論文の数値はなぜ食い違ったのか？

 (kenschutte.com)
1 ポイント 投稿者 GN⁺ 2023-07-18 | 1件のコメント | WhatsAppで共有
  • Jiang et al. の“Low-Resource” Text Classification論文で注目された gzip ベースの kNN 分類器 の性能は、一般的な kNN の精度ではなく、k=2 における top-2 に近い方法で計算されていた可能性がある
  • 公式リポジトリの experiments.py 内の calc_acc は、同率候補の中に 正解ラベルが1つでもあれば正解 として扱うため、最も近い2つの学習サンプルのうち片方だけ合っていても成功として計算される
  • 最初の4つのデータセットの “Full” 列を再計算すると複数の数値が変わり、KirundiNews では gzip 手法が最高性能から最低性能へと下がる
  • 別実装の結果では、公式コードの出力は top2 と常に同じで、k=2 の同率を近いサンプル優先で解消すると実質的に k=1 と同じ結果になる
  • rand==True オプションは random.choice で同率を解消するが、論文結果には使われていないようで、SogouNews はデータサイズのためまだ実行されていない

論文結果の再現中に明らかになった精度計算の問題

  • 対象は Jiang et al. の “Low-Resource” Text Classification: A Parameter-Free Classification Method with Compressors で、gzip ベースの手法が複数のニューラルネットワークベース手法より高い性能を示した表が Twitter で注目を集めた
  • 公式の ソースコード を再現する過程で、kNN 分類器の 精度計算方式 が一般的な方法とは異なって動作している点が確認された
  • 特に k=2 では通常の kNN(k=2) の精度というより top-2 精度 に近く、論文手法の性能がより高く見積もられる可能性がある

k=2 の kNN で同率が問題になる理由

  • 論文手法は kNN classifier を使用しており、Appendix C によればすべての実験で k=2 を用いている
  • k=2 分類では、各テストサンプルごとに最も近い学習サンプル2件を探すため、ラベルの状態は単純になる
    • 2つのラベルが同じならそのラベルを予測し、結果として k=1 と同じ答えになる
    • 2つのラベルが異なれば 1:1 の同率になるため、近いサンプル優先のような別途の同率解消ルールが必要になる
  • 同率をランダムに解消すると、1:1 の同率の半分ではより遠いサンプルを選ぶことになり、k=1 より良くなるのは難しい

calc_acc が同率を処理する方法

  • 問題の箇所は experiments.py の calc_acc メソッドである
  • コードの流れは、sorted_pred_lab に top-k サンプルのラベルとカウントを集め、ラベルごとにまとめた後、カウント基準でソートする
  • 最も高いカウントと同率のラベル群を順に見ていき、そのうち1つでもテストラベルと一致すれば if_right = 1 に設定されて 正解扱い となる
  • k=2 で異なる2つのラベルがそれぞれ1票を得た場合、2候補のうちどちらかが正解かどうかだけを確認していることになる
  • この結果は ImageNet でいう top-k 精度に似ているが、ここでは選ばれた k 個のラベルではなく k 個の学習サンプル を基準にしている点が異なる
  • このメソッドは任意の k を受け取るが、すべての k で top-k を計算しているわけではなく、k=2 の場合にはすべての候補が最大カウント1で並ぶ特殊な状況が生じる
  • calc_acc には rand フラグがあり、rand==True では random.choice で同率を解消するが、論文結果には使われていないようである

再計算後の精度の変化

  • 最初の4つのデータセットの “Full” 列における論文値と修正後の knn2d の値は以下の通り
区分 KinyarwandaNews KirundiNews DengueFilipino SwahiliNews
論文 0.891 0.905 0.998 0.927
修正 knn2d 0.835 0.858 0.999 0.850
  • 5つ目のデータセットである SogouNews は規模が大きいため、まだ実行されていない
  • この違いにより実験の解釈は大きく変わり、KirundiNews では gzip 手法が最高性能から最低性能へと下がる

別実装で確認した結果

  • 別実装では2つの同率解消戦略を用いている
    • r: ランダム選択
    • d: 同率がなくなるまで k を減らす
  • 再実装の結果は以下の通り
方式 kinnews kirnews filipino swahili 説明
table5 0.891 0.905 0.998 0.927 論文表の数値
code 0.891 0.906 1.000 0.927 npc_gzip リポジトリ使用
top2 0.891 0.906 1.000 0.927 top-2
knn1r 0.835 0.858 0.999 0.850 kNN, k=1, 同率ランダム
knn1d 0.835 0.858 0.999 0.850 kNN, k=1, 同率時に k を減少
knn2r 0.828 0.807 0.851 0.842 kNN, k=2, 同率ランダム
knn3r 0.838 0.791 0.851 0.881 kNN, k=3, 同率ランダム
knn2d 0.835 0.858 0.999 0.850 kNN, k=2, 同率時に k を減少
knn3d 0.843 0.794 0.904 0.883 kNN, k=3, 同率時に k を減少
  • 検算結果は、公式コードが何を計算していたかを示している
    • table5 は code と 0.001 または 0.002 以内で近く、論文の数値を再現できる
    • code は常に top2 と同じで、公式コードの結果が別実装の top-2 結果と一致している
    • knn1r == knn1d であり、k=1 では同率は発生しない
    • knn2d == knn1d であり、k=2 の同率を最初のサンプルで解消すると k=1 と同じになる
    • knn2r < knn2d であり、k=2 の 1:1 同率でランダム選択をすると半分のケースでより遠いサンプルを選ぶことになる

残っている確認事項

  • より多くの k の値を含む新しい再実装は gzip-knn にある
  • DengueFilipino が一部のケースで 1.0 のように非常に高い理由は、続編の Part 2 で扱われる
  • table5 と code が2つのケースでわずかに異なる理由は、まだ確認課題として残っている

関連記事

1件のコメント

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

  • 著者たちにとっては残念だろうが、これは見事な反証だと思う
    機械学習ではこうしたミスは本当に起こしやすく、さらに厄介なのは、微妙な方法論上の誤りが他の工学・科学分野のようにたいてい致命的な失敗として表れるのではなく、わずかな性能変化として現れることだ
    悪いデータが学習セットに混ざったり、目標値の情報が漏れたりしても、システムはそれなりに動いてしまい、結果が少し汚染されるだけだ
    既存の圧縮アルゴリズムを機械学習に適用するのは、期待していたよりも都合のよすぎる話に感じられる。圧縮アルゴリズムに特別な魔法があるなら、トランスフォーマーを圧縮器として使うより、圧縮アルゴリズムをエンコーダとして使っていたはずだ

    • この点はぜひ覚えておくべきだ。ミスは起こしやすいからこそよくあり、科学はノイズの多いプロセスだが、その中にはシグナルもあり、いま見えているのがまさに査読の本質だ
      だから私は、学会やジャーナルより公開出版のほうがより良い査読の形だとよく主張している。査読とは仲間が私の仕事を検討することであって、学会やジャーナルが掲げる恣意的でノイズの多い基準が本質ではない
      歴史の大部分では実際にそう機能しており、現代的な意味での査読は1970年代半ばのかなり新しい概念だ。昔のジャーナルは、今日のarxivのように研究を配布する任務に近かった
      https://mitcommlab.mit.edu/broad/commkit/peer-review-a-histo...
      学会やジャーナルをなくすべきだと主張するもう一つの理由は、そうすることで再現論文や失敗論文のような重要な仕事を積極的に奨励できるからだ。「新規性」という基準に縛られる必要はなく、実際ほとんどすべての研究は漸進的だ
      「出版」とは、自分の仕事を仲間に伝え、彼らが結果を検証または反証できるようにすることだ
      ただし、学会が人を集めて協業を促進する点は良い。ここで言っているのは、学会やジャーナルを研究の妥当性を判断する手段として使うことへの批判だ
      学会システムが単に研究とコミュニティを招く場であるなら、まったく問題ない。ジャーナルも理論上は著者とレビュアーの対話があるという点で良いが、これもarxiv + githubやOpenReviewで容易に実現できると思う
    • そのような手法はすでに使われている。最小記述長原理やエントロピーに基づく分類器を調べればよい
      性能は高くないが確かに存在し、配布も非常に簡単だ。似たテキストほどよく圧縮される傾向があるので、gzipが剽窃検出に使われているのを見たことがある
      圧縮率をスプリングモデルの重みとして使って可視化することもできるし、ネットワーク通信のメタデータにも適用できる
    • 多くの実験ではその通りだ。望む結果を得たいという欲求が、実際に得られたものを検証しなければならないという必要性を簡単に上回ってしまう
      とりわけ、その結果が既存の考えを裏づけてくれるときはなおさらだ
    • 最近機械学習をかなり勉強しているが、こういう傾向をよく目にする。ソフトウェアエンジニアとしてやってきたことのほとんどと正反対に感じられる、もう一つの点だ
      セミコロンを一つ落とせば即座にエラーになる
      ところが3層のうち1層の勾配計算を間違えても、ときには動いてしまう。ただし結果はおかしくなる
    • 学術研究のコードはたいてい、アマチュアができるだけ急いで書いたひどいコードで、テストもほとんどなく、そうしたコードの主な産出物は論文引用を積み上げることだ
      科学論文が半分に減り、そのぶん注意深さが2倍になる世界のほうがはるかに大きな価値を生むだろうが、システム全体が絶望的なまでにゲーム化されている

  • このブログ記事を書いた本人です。ここに書いた内容にはかなり自信があるが、見落としがあるなら著者たち自身が説明してくれる必要があるかもしれない
    たった今GitHubにissueを立てた: https://github.com/bazingagin/npc_gzip/issues/3

    • 記事の冒頭に注記を追加することを検討してもよいかもしれない。多くの人がタイトルだけをざっと見て「gzip論文はいい加減で、gzipアプローチも大したことはない」と受け取っているようだが、実際には「gzipアプローチは深層ニューラルネットワークモデルより優れてはいないものの、概ね十分競争力があり、実行コストはずっと安い」に近いように見える
      論文自体は依然としてしっかりしている
    • 論文の第1著者で、ブログ記事を読んだ。k=2を選んだ理由は、n^{1/2} を使うことが推奨されており、5-shot設定に合うkを選びたかったからだ
      ただ、この選択がやや奇妙だという指摘はその通りだ。論文とTwitterで述べた通り、kの値が変われば結果も変わり、報告したのは得られる最大の結果だったので、予測が常に当たる理想的な状況を意味している
      W2VとSentBERTにも同じ戦略を使った。ただし、これはtop-2精度という意味ではない。私の理解では、top-2精度とは予測された上位2クラスのうち1つが正しければ得点になるものだ
      しかし指摘の通り、kNNでk=2のとき最も近い2つの近傍が同じクラスを指す場合があり、このときtop-2精度を報告するなら別のクラス候補1つを取り逃すことになる
      時間ができてarxivに新しい版を上げるときには、別の戦略や別のk値についての結果も追加したい。ブログで述べられていたdecrement戦略は本当に良く、望むならリポジトリに追加したい
      短く遅い返答で申し訳ない。まだリポジトリを確認できていない。明日、論文審査の準備をしているので、それが終わったらissueに返信して対応するつもりだ
    • 再現してくれてありがとう。重要な作業だ
      別の結果表であるTable 3も再現してみたのか気になる
      私の理解が正しければ、クラスが2つしかないときtop-2精度は1になるが、クラス数が増えるほど平均的には「通常の」精度との差は次第に小さくなる。したがってデータセットにクラスが多ければ、Table 3の結果はそこまで大きくは変わらないはずだ
      いずれにせよ、20-newsgroupsデータセットでtop-2精度0.685というのは、文字すら文字として見ていない手法にしてはかなり印象的だ[1]。トークン、n-gram、埋め込みといった自然言語処理研究者が何年も注ぎ込んできた優れたツール群は言うまでもない
      [1] 私の理解では、gzipはビット列しか扱わず、これは単語、つまりバイト境界と必ずしも整列していない
    • 公開する前に、まず著者たちに連絡してみたのか気になる

  • Shopifyで検索関連性の実験をするときにもミスをたくさんしたので、著者たちに共感する。自分にも公の場で恥をかいた失敗がかなりある
    Shopifyでの終盤に、良い科学には良いソフトウェアエンジニアリングが必要だと学んだ。スタックのあまりに多くの箇所でミスしやすいからだ
    そのため、数値を信頼でき、お互いの実験を再現できるように、厳密でテストが多く品質の高い実験用ソフトウェアを作ることに多くの時間を費やした
    一回限りの評価方法は避けるようにし、新しい方法を作ったら評価ツール群に追加したうえで、その指標が何を意味するのか理解するためにテストした
    当たり前に見えるが、こうした実験をしてきた自分の経験では、残念ながら望むほど一般的ではない。会社はスピードを求めるし、統計的に深く考えたり内部ツールを作ったりすることは、たいてい上層部の利害とあまり合わない

    • 「良い科学には良いソフトウェアエンジニアリングが必要だ」というのは、産業研究の前向きな面でもある
      第一に、より多くのソフトウェアエンジニアリングの専門性を使えるし、第二に、主張を誇張しにくくなるインセンティブがある。動くと言ったら、実際の運用環境に入れろという期待を受けるからだ

  • このブログ記事が公開されてうれしい
    自分もこういう小さなプロジェクトを本当にたくさんやるが、論文の問題を示すこうした作業ですら日の目を見ないことが多い。たいていは少し声を上げるだけで、ハードディスクに埋もれたまま終わる
    だから、こうして出してくれてありがとう

    • 最近はTwitterを低コストなブログのように使い始めた
      こういう作業に一日使ったあとだと、実際にブログ記事を書く気力が残っていないことが多く、もったいなく感じる。それでも短いTwitterスレッドを書くくらいなら、たいていはできる

  • この結果を見られて本当にうれしい。kNN + 分類タスク + 純粋なテキスト類似度ベースの分類は、結果が有利に積み上がりやすい組み合わせだ
    この論文を見て痛快がる反応は、自然言語の要素が埋め込みにおいて中核的に重要だという点を誤解している。単語を共有するフレーズは分類もうまくいくしGZIPでもうまくいくので、GZIPを代替分類器として使うことはできる
    BERTや埋め込みの奇跡は、単語を共有していなくてもよいことにある。たとえば what is my safe passcode? は my lockbox pin is 1234 と強く対応するが、my jewelry is stored safely in the safe とはそうならない
    LLMでもこの点は重要だ。多くの人がテキスト類似度用の埋め込みを使っているが、実際には質問とその答えを含む文書が相関するように学習されたSBERTモデルを使うべきだ
    全体の深掘りは https://www.sbert.net/ で見られる
    以前の記事: Should you use OpenAI's embeddings? Probably not, and here's why. https://iamnotarobot.substack.com/p/should-you-use-openais-e...
    HNでの議論: https://news.ycombinator.com/item?id=35377935

    • 公平に言えば、元の課題は kNN+圧縮 のような方式がうまくいく可能性のある場所、つまりドメイン外 + 低リソース環境として意図的に選ばれていた
      こうした条件では、学習入力があまりに疎で、パラメータ数の多いモデルが良い埋め込みを学習するのは難しいかもしれない
      従来のドメイン内大規模データ分類設定では、圧縮のようなノンパラメトリック手法が学習済み表現に勝てる可能性はない

  • 著者たちがなぜ分類器としてkNNを選んだのかは明確ではなかった。距離行列を作ったなら、多次元尺度法で行列を要因に変換したうえで、xgboostのような木ベースのアルゴリズムを使えただろうし、そうすればkNNより多くの情報を活用して、はるかに良い結果を出せた可能性が高い
    LZ系圧縮器よりはるかに優れたPAQ圧縮アルゴリズムも使えたはずだ。こうした選択が結果を大きく改善し、元の結論に到達できた可能性もある
    この論文で良かった点は、圧縮アルゴリズムを抽象化したことだ。そのおかげで、p(x) ~ K^(-|x|) の関係から、圧縮でほかに何ができるかを考えさせられる。ここでKはアルファベットサイズ、|x|は文字列xの長さであり、最適符号化を仮定する
    たとえば各応答の要因を別個の文書としてまとめ、論文と同じやり方で次のサンプルを最もうまく圧縮する文書を見つけてクラスを決める、という伝統的な分類も可能だろうと思った。いわば圧縮アルゴリズムを使った教師あり分類だ
    圧縮器がそのデータセットの最適符号に近いほど、よりうまく機能するはずだ
    順序列予測の方式も、実装は同じく簡単だ
    気持ちのよい驚きだった

  • 圧縮アルゴリズムがどうして LLM に勝てるのか説明してもらえる？ まるで言葉のほうがグラフィティより優れていると言っているように聞こえる
    どこかに答えがあるのだろうけど、AI に詳しくないのでまったく理解できない

    • 一般に 圧縮 = モデル + エントロピー符号化 である
      モデルの役割は次に来るものを予測することで、エントロピー符号化器の役割は予測と実際の次の値の差を符号化しつつ、可能性の高い結果ができるだけ少ないビット数になるようにすることだ
      モデルが正確であるほど現実と予測の差は小さくなり、エントロピー符号化器が必要とするビット数も減るので、圧縮性能は良くなる
      単純な圧縮アルゴリズムは、「同じバイトを 10 回見たなら 11 回目も同じ可能性が高い」といった単純なモデルを持つ。だが、LLM もモデルとして使える。もっともらしい単語でテキストを補完するのが LLM の仕事だからだ
      ここでは逆のことをした。圧縮にモデルを使う代わりに、いくつかの工夫で圧縮アルゴリズムをモデルのように使ったのだ。圧縮アルゴリズムが結果をより少ないビットで符号化するとき、それを最も可能性の高い結果とみなす方法である
      元の論文の著者たちは、一部のタスクでは gzip から取り出せる単純なモデルが、はるかに複雑な LLM に勝つことを示した
    • 言語モデルは単語列の確率 P(w_1, ..., w_n)、あるいは同等に P(word | context) を推定する
      圧縮では確率の高い単語列により短いコードを割り当てる必要があるため、直接的な関係がある。確率に基づいてこのようなコードを作るよく知られた方法が ハフマン符号化 である
      単語頻度を使う統計的言語モデルでも、確率推定に LLM を使う場合でも成り立つ。言語モデルが優れているほど、つまりパープレキシティが低いほど、圧縮結果は短くなる
      逆に、圧縮アルゴリズムはコード長を通じて暗黙のうちに言語モデルを定義しているとも言える。たとえば、重複する文字列はランダムノイズよりも起こりやすいと仮定しているわけだ
    • gzip のやり方の直感はこうだ
      ABC を圧縮すると X バイトになる。続いて ABCABC を圧縮しても 2X バイトにはならない。連結した 2 つの文字列が似ているほど、必要なバイト数は減る
      ABCABD は ABCABC よりは大きいが、ABCXYZ よりは小さいはずだ
      BERT は今日の基準では非常に小さな LLM であり、今よく目にする数十億パラメータ規模のモデルより性能が劣ることも分かっている
    • 圧縮は知能と等価である
      https://mattmahoney.net/dc/rationale.html
    • 非常に限定的なタスクである。1 つの文書を受け取り、たとえば 10 個ほどのカテゴリのうち 1 つに分類するというものだ
      特定の単語を検出するような方法でも、場合によってはかなりうまくいく。よく圧縮される対象には共通の部分文字列が頻繁に現れる

  • これが本当なら、その論文について大げさなことを言っていた人たちが、今どうやって静かに痕跡を消していくのか見てみたい
    とくに LinkedIn と Twitter のインフルエンサーたちを見ている
    本当でなければ自分が間抜けに見えるだろうが、記事をざっと流し読みしただけだ

  • 分類器としての Gzip は驚くほど優秀で、ニューラルネットワークのベースラインとして使うべきだ

  • ちなみにブログは 2022 年で止まっているようだ
    記事の日付が 2022 年 7 月 17 日になっている

    • ありがとう。すぐに修正されるはず。日付を手で書くとこういうことになる...