事前学習なしでARC-AGIを解く

 (iliao2345.github.io)
1 ポイント 投稿者 GN⁺ 2025-03-05 | 1件のコメント | WhatsAppで共有
  • ARC-AGIのように少ない例から規則を見つける必要がある問題で、CompressARC は事前学習・外部データセット・大規模探索なしに、パズルごとの推論時学習だけで解法を見つける
  • 中核となるアイデアは、答えまで含めたパズル表現がより短くなるよう 可逆な情報圧縮 の目的を最適化すると、知的な振る舞いが現れうるという実験である
  • RTX 4070でパズルごとに約20分を使い、訓練セット 34.75%、評価セット 20% を記録しており、対象パズル1つだけを学習データとして使うニューラルネットワーク手法である点が特徴である
  • アーキテクチャは、例の順序、色の置換、回転・反射に対する 等変性 を中心に設計されており、複数ランクのテンソルを束ねた multitensor 表現を使う
  • 色-手続きマッピング、塗りつぶし、切り抜き、点の接続、短距離移動には強いが、数え上げ、長距離パターン拡張、回転・複製・サイズ変更、エージェント計画は依然としてボトルネックとして残っている

圧縮だけでARC-AGIを解けるかという実験

  • 中核の問いは、可逆な情報圧縮 だけで知的な振る舞いを作り出せるかどうかである
  • CompressARCはARC-AGIパズルを対象に、圧縮ベースの目的関数だけで動作する手法である
  • 3つの制約を置く
    • 事前学習なし: モデルはランダム初期化され、推論時に学習される
    • データセットなし: 1つのモデルは対象のARC-AGIパズル1つだけを学習し、答えを1つ出力する
    • 探索なし: 多くの意味で探索を行わず、勾配降下法だけを使う
  • 結果は訓練セット 34.75%、評価セット 20% で、各パズルはRTX 4070でおよそ 20分 かかる
  • 対象パズルだけを学習データとして使うARC-AGI向けニューラルネットワーク手法としては初めてだと説明されている

ARC-AGIの問題設定

  • ARC-AGI は2019年に紹介されたAIベンチマークで、少ない例から 抽象規則 を推論し、一般化する能力をテストする
  • 各パズルは複数の入力-出力例と1つのテスト入力を与え、システムはテスト出力グリッドを当てなければならない
  • 1パズルあたり 2回の試行 が可能で、どちらか1つでも正解なら1点を得る
  • 出力グリッドのサイズを変え、すべてのピクセルの色を選べる
  • パズルは人間なら妥当に解けるが、機械にはより難しいよう設計されている
    • 平均的な人間は訓練セットの 76.2% を解く
    • 人間の専門家は 98.5% を解く
  • 400個の訓練パズルは他より簡単で、次のパターンを学ばせる用途がある
    • 対象性: オブジェクトは理由なく現れたり消えたりしない
    • 目標指向性: 一部のオブジェクトは意図を持つエージェントのように振る舞う
    • 数とカウント: オブジェクト数、整列、比較、加減算のような基本的な数学が使われる
    • 幾何と位相: 図形の反射、回転、移動、変形、結合、反復、距離差などが含まれる
  • ARC Prizeの最近のKaggle大会では最大 100万ドル超 の賞金があり、主要賞は制限環境で12時間の計算により非公開100問で85%を達成する手法に割り当てられている

CompressARCの動作方式

  • CompressARCでは、より少ないビット数で圧縮される表現ほど、より正確なパズル解答に結びつく
  • システムは不完全なパズルを完成済みのパズルへ変換する 圧縮表現 を探し、この表現を復号するとパズルと解答が再構成されるようにする
  • ニューラルネットワークは デコーダ の役割を担う
    • 別個のエンコーダニューラルネットワークはない
    • エンコーディングは、推論時にデコーダを勾配降下法で学習することで実装される
    • 最適化された重みと入力分布設定が、パズルと答えを含む圧縮ビット表現の役割を果たす
  • 標準的な機械学習の表現では次の手順になる
    • ARC-AGIパズルを受け取る
    • パズルの例数と観測された色数に合わせてニューラルネットワーク f を構成する
    • z ~ N(μ, Σ) のランダムな正規入力を受け取り、すべてのグリッドについてピクセルごとの色ロジットを出力する
    • 既知グリッドに対する交差エントロピー和を最小化し、答えグリッドは無視する
    • N(μ, Σ) が N(0,1) に近づくよう KLダイバージェンスのペナルティ を置く
    • 学習中に生成された答えグリッドを保存し、最も頻繁に出た答えを最終予測として選ぶ
  • fθ は、入力-出力ペアの順序変更、色の置換、空間回転・反射といった一般的な拡張に対して 等変的 に設計されている

圧縮観点からの導出

  • 可逆圧縮とは、情報をできるだけ少ないビットで表現しつつ、そのビット表現から元データを正確に復元する問題である
  • ARC-AGIでは本来、パズルと答えのペア全体をシンボルとして圧縮すべきだが、実際には答えはエンコーダ入力に存在せず、パズル生成分布も分からない
  • ARC-AGIデータセットに対して、実用的に実装可能なビット効率のよい圧縮システムが存在すると仮定する
  • 分布 p を知らなくても、プログラム f と入力 s の長さ len(f)+len(s) を最小化する普遍圧縮器を考えられる
    • デコーダは f(s) を実行して元データを復元する
    • アルゴリズム情報理論では、元の圧縮器よりも f の長さの分だけしか非効率にならない可能性がある
    • 実際には、プログラム空間を探索するエンコーダは実用的ではない
  • CompressARCはプログラム空間探索の代わりに、ニューラルネットワークのforward pass を固定プログラムとして選ぶ
    • s は重み θ、入力 z、出力補正 ε で構成される
    • θ と z はRelative Entropy Coding（REC）の観点で、ε は arithmetic coding の観点で符号長を計算する
    • 出力補正の符号長は、既知グリッドの総交差エントロピーに等しくなる
    • z の符号長は KL(pz || qz) となり、qz = N(0,I) と置く
  • 全体の符号長はVAE損失と同じ形になる
    • 再構成誤差
    • z に対するKL
    • デコーダ正則化
  • CompressARCの実装は、この導出に対して正則化の一部、等変性、パズル間独立性に関する修正を含む形になっている

アーキテクチャ: multitensorと等変性

  • アーキテクチャの最も重要な特徴は 等変性 である
    • 入力 z が変換されると、出力されるARC-AGIパズルも同じように変換されるべきである
    • 例としては、入力-出力ペアの並べ替え、色のシャッフル、グリッドの反転・回転・反射がある
  • 設計はまず完全に対称な基本アーキテクチャを作り、必要な非等変能力を与える 非対称レイヤ を追加して不要な対称性を1つずつ壊す方式である
  • 内部データは multitensor という形式で流れる
    • 複数のランクとshapeを持つテンソル群の束である
    • 次元は最大で [n_examples, n_colors, n_directions, height, width, n_channels] の部分集合から構成される
    • 常に channel 次元は維持される
    • 規則を適用してmultitensor内の合法テンソル数を18個に減らす
  • パズルは [examples, colors, height, width, channel] テンソルで表現できる
    • channel は入力または出力グリッドを選ぶために使う
    • width と height はピクセル位置を表す
    • color 次元はピクセル色のone-hot表現を含む
  • 全体のアーキテクチャは次の流れを持つ
    • z 分布パラメータから開始
    • Decoding Layer
    • Multitensor Communication、Softmax、Directional Cummax、Directional Shift、Directional Communication、Nonlinear、Normalization を4回繰り返す
    • Linear HeadsでARC-AGIパズル分布を出力する

性能結果

  • 学習はAdamで 2000 iterations 実行する
    • 学習率は 0.01
    • β1 = 0.5、β2 = 0.9
  • 訓練セット結果
    • 100 iteration: Pass@2 2.25%
    • 500 iteration: Pass@2 27.5%
    • 1000 iteration: Pass@2 31.75%
    • 2000 iteration: Pass@2 34.75%
    • 2000 iterationでのPass@1000は 52.75%
  • 評価セット結果
    • 100 iteration: Pass@2 1.25%
    • 500 iteration: Pass@2 15%
    • 1000 iteration: Pass@2 19.25%
    • 2000 iteration: Pass@2 20%
    • 2000 iterationでのPass@1000は 33.75%
  • ARC-AGIの採点では2回試行できるため、本文の主要結果は Pass@2 基準である

解けるパズルと難しいパズル

  • CompressARCは持っている能力で可能な限り規則を把握するが、アーキテクチャが持たない能力でボトルネックに突き当たる
  • 可能な作業の例は次の通り
    • 個別の色を個別の手続きに割り当てる
    • 塗りつぶし
    • 切り抜き
    • 45度対角線を含む点の接続
    • 同じ色の検出
    • ピクセル隣接性の識別
    • 例ごとの色割り当て
    • 図形の一部分の識別
    • 短距離移動
  • 難しい作業の例も明確である
    • 2色を相互に対応付ける
    • 同じ演算を何度も連続して繰り返す
    • 移動、回転、反射、サイズ変更、画像複製
    • 連結性のような位相的性質の検出
    • エージェント行動の計画とシミュレーション
    • 長距離パターン拡張
  • 訓練パズル28e73c20では、端から中央へパターンを拡張する必要があるが、CompressARCは短距離拡張はできても中央付近では推測に頼る

事例: Color the Boxes

  • 人間の解法では、入力が箱に分かれており、出力ではその箱が色付けされることを見抜く
    • 角は常に黒
    • 中央は常にマゼンタ
    • 辺側の箱は方向に応じて、上が赤、下が青、右が緑、左が黄に決まる
  • CompressARCの学習進行は段階ごとに異なる
    • 50 step: 入力のシアンの行・列が出力にも対応することを反映する
    • 150 step: 近いピクセル同士が似た色を持つ出力形状を示す
    • 200 step: シアン境界で切られたより大きな色塊と黒い角塊を模倣する
    • 350 step: 中心基準の方向に合った箱の色をおおむね当てる
    • 1500 step: 出力はほぼ洗練されるが、サンプルではまれにミスが残る
  • 学習された z 分布を分析すると、色-方向対応表 と行・列の区切り線位置を符号化していることが分かる
  • 4つのテンソルだけが情報量を維持する
    • (examples, height, channel): 各例のシアン行位置を含む
    • (examples, width, channel): 各例のシアン列位置を含む
    • (direction, color, channel): 方向と色の対応を含む
    • (color, channel): マゼンタとシアンの特別な役割を区別する

追加事例と表現分析

  • Bounding Box パズル 6d75e8bb

    • 人間の解法は、赤い図形を囲む最小のシアン枠を描くというものだ
    • CompressARCは100 stepで共通bounding boxを把握した痕跡を示し、150 stepでは答えを見つけた後、その後の学習で答えを洗練する
    • 生き残った主要テンソルは (examples, height, channel)、(examples, width, channel)、(color, channel) である
    • 行・列テンソルはシアンのピクセルが多い行と列を表すが、境界位置をどう把握しているかは不明である

  • Center Cross パズル 41e4d17e

    • 入力の青いバブル中心からマゼンタの光線を上下左右に描き、バブルの色は光線の上に重ねる必要がある
    • CompressARCは入力をコピーした後にマゼンタの行・列が現れ、徐々に正しい位置へ安定する
    • 人間の解法のように、バブルの上に誤って光線を描いてしまうミスは見られない
    • 生き残ったテンソルは (examples, height, width, channel) と (color, channel) である
    • (examples, height, width, channel) はバブル中心を符号化している

改善アイデア

  • パズルごとに別々に圧縮する代わりに、ARC-AGIデータセット全体をまとめて圧縮すれば、パズル間で計算を共有してより良い帰納バイアスを得られる可能性がある
    • すべてのパズルで同じネットワーク重みを使い、パズルごとに制限付きのperturbationを与える方法を検討している
    • パズルごとの高次元埋め込みを学習し、その埋め込みからネットワーク重みへの線形写像を学習する hypernetwork 方式も提案している
    • この方向は研究の反復速度を遅くしうるため試していない
  • 図形複製タスクにはconvolution系レイヤが有用かもしれない
    • あるグリッドが図形を保存し、別のグリッドが複製位置を示せば、convolutionで複製結果を作れる
    • 一般的なconvolutionはノイズを信号より大きく増幅する問題があった
    • tropical convolutionはおもちゃパズルではよく動いたが、ARC-AGI訓練パズルには十分ではなかった
  • posterior collapse 緩和のためにKL floorを置く方法も検討されている
    • 重要なテンソルのKLが0に落ちると再び回復できない現象が観察された
    • KLをしばらく0より大きく保てば、ネットワークがその情報を使うよう学習できる
    • 実装はしたが、テンソルが回復する事例は見られず、KL floorスケジュールを別の形に設計する必要がある
  • 正則化は実装では使っていない
    • 問題定式化では f の複雑さを測る要素であり、CompressARCの導出にも含まれる
    • 実装から外したのはやや大胆だったと評価している

関連研究と研究上の位置づけ

  • 圧縮と知能の等価性というアイデアは Hutter Prize に着想を得ている
    • Hutter PrizeはWikipediaのテキストファイルを最もうまく圧縮するシステムに賞を与え、情報圧縮能力を知能と結びつける
  • 理論的背景にはSolomonoff Induction、Kolmogorov Complexity、Minimum Description Lengthが含まれる
  • 情報理論の観点では Relative Entropy Coding が中核である
    • KLダイバージェンスを制限できれば圧縮アルゴリズムを構成できるとし、実際の2進コード実装問題を抽象化している
  • VAEの観点では、デコーダが復号アルゴリズムの役割を果たす
    • より一般的な能力を持つ neural Turing machine も考えられるが、勾配降下法最適化に適さないためVAE寄りの方法を使っている
    • beta-VAE式の再構成損失の再重み付けはこの場合うまく機能する
  • 既存のARC-AGI手法は主にLLM、データ拡張、代替データセット、テスト時学習、ドメイン特化言語ベースのプログラム探索を使っている
  • CompressARCは、外部事前学習と大規模探索なしにディープラーニングを使う手法である点を強調している
  • プロジェクトコードは GitHub で公開されている

関連記事

1件のコメント

 
GN⁺ 2025-03-05
Hacker Newsのコメント

  • 大規模な事前学習は、一般性という趣旨に反しているように感じる
    3つの例だけを見て4つ目を予測するプログラムを合成できる汎用機械を作ったなら、実質的にはオラクル合成を解いたことになる
    逆に、パズル作成まで含めた人類の知識全体でネットワークを学習させ、データセットの99%で微調整したあと、最後の1%に対して何度も試行させたなら、それは試験作成者の心理を圧縮する高価な圧縮器を作ったのに近い

    • これは知識と理解について、かなり素朴な見方を示している
      AGIが接続しさえすればよいプラトン的な論理と理性の領域があると前提しているが、文脈なしに意味も推論も論理もありえない
      図形パターンを見分けるには図形という概念が必要で、それは空間関係の概念を前提とし、さらに2次元または3次元空間の概念を前提とする
      こうしたものが当然で暗黙的に見えるのは、人間の精神が何億年にもわたって解釈するよう進化してきた環境、そして何十年にもわたって消費し処理してきた環境に深く染み込んでいるからだ
      AGIの本当の試験は、異なる情報を一貫した世界観へと同化する能力であり、事前学習は実質的にその仕事をしている
      そのような能力を持つ知能であっても、自分が置かれる世界についての構造的な仮定が「事前に積み込まれて」いる必要がある可能性は高い。空間関係、言語、感覚解釈に長けた脳領域に近い
    • 機械が初めて見るタイプの問題に出会ったとき、自分でどう学習するか、つまり重み調整の方法を決められるなら、汎用知能の趣旨に反しないと思う
      人間も、何かをもっと上手くやりたいとき、その課題をどう練習するかを見つけ出し、実際に上達する形で学習する
    • その通り。現在のパラダイムの多くの問題もそこにあり、真の汎化を許していない
      だから当面AGIは現れないと考える人たちもいる: https://www.lycee.ai/blog/why-no-agi-openai
    • 人間の学習の大半は、何年にもわたる感覚入力から来ると考えている
      背景知識なしに機械がうまく汎化できると期待すべき理由があるだろうか
    • ARCは4枚の画像タプルに対する分布と等価で、事前分布がなければ最初の3枚が与えられても最後の画像は一様分布になる

  • Marcus Hutterが出演したLex Fridmanのポッドキャストを思い出す
    Joshua Bachも知能を現実を正確にモデル化する能力と定義していたが、可逆圧縮そのものが知能なのか、それとも最適適合モデルなのかが気になる。両者に違いはあるのだろうか?
    https://www.youtube.com/watch?v=E1AxVXt2Gv4

    • ちなみに、ARC-AGIを作ったFrançois Cholletは2020年のLex Fridmanポッドキャストで、知能は圧縮ではないと主張している: https://youtu.be/-V-vOXLyKGw
    • 知能とは、複雑な現実を高い精度と低い遅延で予測する単純なモデルを見つける能力だ
      したがって、単純性、精度、遅延、現実の複雑さという4つの軸を見る必要があり、人工知能はこの空間内のどこかの領域になるはずだ
      実は知能を見分ける簡単なテストがある。C関数のコードを読んで、入力の変化が出力にどう影響するかを説明できるかどうかだ
      複雑なアルゴリズムでは内部モデルを作る必要がある。そうでなければ、100万件の項目に対してqsortがどう動くかをどう頭の中で実行するのか
      学生が理解したふりをしているのか、本当に理解しているのかも同じ方法で区別できる
      より難しいテストは逆に、いくつかの入出力例だけを見てアルゴリズムを作り出すことだ
    • ポッドキャスト全体を見ずに手短につなげると、Hutterの立場はHutter Prize[1]という形で表れており、ある意味ではARC-AGIと目標がかなり似ているが、圧縮そのものを知能へ向かう基準点と見なしている
      [1] http://prize.hutter1.net/

  • このアプローチの本質を取り出そうとしているのだが、特定の圧縮方式の選択や事前分布のような本質的でない細部の背後に隠れているように見える。
    中核となる革新は、勾配降下法で最適化できる「モデル」を構成し、その最適点が入力-出力関係を記憶する最も「単純な」モデルになるようにした点にあるようだ。
    ここでの「単純さ」は具体的には「効率的に圧縮可能であること」だが、より一般的には モデル複雑性 が可能な限り低いという意味に近い。
    これは標準的な機械学習と明確に対照的だ。通常はまずモデル構造と複数の複雑性パラメータを選んで複雑性予算を定め、その後でデータを使って入出力関係をうまく記憶する解を見つける。
    この新しい方法は機械学習を逆転させる。入出力ペアは記憶し続けつつ、モデル複雑性をできるだけ小さくするよう最適化する。
    学習例が2個しかないのに汎化できるという点は本当に驚くべきで、汎化を扱う正しい方向を強く示唆していると思う。
    著者らがこの構造に到達した経路は情報理論だったが、それが本質なのかはよく分からない。
    核心は、固定された複雑性予算の中で最良のモデルを探すのではなく、可能な 最小複雑性モデル を見つけられるという気づきに近いように見える。

    • 複雑性最小化のアイデアは、見た目ほど新しいものではない。
      最適化の損失目的関数には正則化項がしばしば追加され、こうした正則化はしばしば複雑性へのペナルティとして解釈できる。
      双対性のおかげで、同じ目的関数をいくつもの形で見ることができる。データ誤差と複雑性の加重和を最小化する、データ誤差を閾値以下に保ちながら複雑性を最小化する、あるいは複雑性を閾値以下に保ちながらデータ誤差を最小化するといった形だ。
      こうした古典的な 正則化 は最近では流行から外れているように見える。
      大半のTransformerアーキテクチャで大きな役割を果たしているとは思わないが、何らかの形で戻ってくるなら興味深い。
      それ以外にも、このアプローチには新しい要素が多すぎて、何が実際に性能を生んでいるのか見分けにくい。
      例えばニューラルネットワークの構造自体も、ARC-AGI型の課題性能を最大化するようかなり念入りに調整されているように見え、その先にどう一般化するのかはあまり見えてこない。
    • 核心となる材料についてはその通りだと思うが、この結果はかなり ARC-AGI特化 だと感じる。
      各パズルは形式が似ており、パズル内で変化するデータは規則を推論するのに必要な情報とほぼ正確に一致している。
      規則を説明するために必要な情報量を減らすと、情報損失を最小にするためにコーデックはほとんど規則そのものがしていることへと縮退せざるを得ない。
      各パズルにノイズや任意のデータがもっと多ければ、この手法は機能しなかったように思う。
      もちろん、ある地点を超えるとパズルが「パズルがどこにあるかを見つける」ものになってはいけないが、ここでは各例がパズル自体に関する純粋な情報なので機能している。

  • 興味深い。機械学習の今後は、私たちが慣れ親しんできた意味での「機械学習」がむしろ少なくなる方向なのではないかと、ますます思うようになっている。
    事前学習、データ、探索は減り、直接表現、記号処理、制約充足、メタ学習のようなものが増える方向だ。
    あまり必要でなくなるもの、つまり事前学習やデータなどは、雑然としていて無差別で偶発的だ。
    そうしたものに依存すると常にデータ品質に左右されるし、データマイニングが目的ならそれで構わないが、データの根本原因をモデリングしようという目的には合わない。
    私の理解では、彼らは解答/問題空間の 最小表現 を露わにしようとしているのに近い。
    等変性を通じて問題の実際の構造を追跡し、多数の解法例の中で偶然捉えられることを期待する代わりに、パズルの実際の基底表現と解法により近いものを導き出している。

  • 素晴らしいドキュメント化と説明だ。自分の内省とも一致していてうれしい。
    「知能とは、情報を 既約な表現 に圧縮すること」だと考えている。

  • ARC-AGIが最小限の例から抽象規則を推論し、汎化する能力をテストするベンチマークなのだとすれば、結局のところ知能を情報を規則集合へ圧縮する能力として定義していることになる。
    だとすれば、圧縮がその役割を果たすというのはもっともだ。

    • これは主張のように循環的でも自明でもない。
      ARC-AGIの問題を実際に解いたことがあるのか気になる。
      問題はかなり微妙で、幅広い 抽象概念 をテストしている。
      参考までに、o1-previewは公開評価で21%を記録し、元記事のアプローチは34%だった。

  • ある程度関連するSchmidhuberの論文: https://arxiv.org/abs/0812.4360

  • 「各パズルをRTX 4070で約20分処理」という表現なら、100問チャレンジには 33.3時間 かかることになるようだ。
    これはチャレンジ目標の12時間を超えるが、アプローチ自体はかなりクールだ。

  • これは、構造をかなり手間をかけて設計している点を除けば、ほぼ標準的な ベイズ深層学習 アプローチに見える。