技術的サマリー：最小限の過剰パラメータ化下における回路とトランスフォーマーの例からの認証は困難である

問題定義

最先端のニューラルネットワークが推論やアルゴリズムタスクへの展開をますます増やしている中、それらの厳密な正しさを保証することが極めて重要となっている。高い平均ケース精度はしばしば一貫性のない振る舞いを隠蔽し、意図された推論ロジックから逸脱した失敗を検出することを困難にする。本論文は、厳密な認証の問題、すなわち、目標仮説 $f^*$ を仮説クラス $\mathcal{H}$ の中で一意に特定するために必要なラベル付き入力 - 出力例の最小数を決定する問題に取り組み、その結果として $\mathcal{H}$ 内の他のどの仮説も $f^*$ と全定義域で一致しないようにすることを扱う。

中心的な問いは、この認証の複雑さが周囲の仮説クラスのサイズに対していかに敏感であるかである。具体的には、著者らは仮説クラスを最小限に拡大すること（例えば、単一のゲートまたは定数個のパラメータを追加すること）が、以前は認証が容易であったターゲットであっても、認証を指数関数的に困難にさせるかどうかを調査する。

手法

本論文は、教える複雑性と回路複雑性に根ざした理論的枠組みを採用し、二進数加算タスクにおける実証的検証によって補完している。

理論的枠組み

1. 認証サイズ定義: 著者らは、認証サイズ $\text{cert}(f^*, \mathcal{H})$ を、バージョン空間 $V_S^{\mathcal{H}}$（ラベル付きサンプル $S$ と整合する $\mathcal{H}$ 内の仮説の集合）が $f^*$ のみを含まないようなラベル付きサンプル $S$ の最小サイズとして定義する。
2. 非交差不一致原理: 核心的な証明戦略は、「欺く」仮説の集合を構築することにある。ターゲット $f^*$ に対して、著者らは特定の、互いに非交差な「トリガーブロック」$B_\pi$ 上を除いて $f^*$ と一致する仮説の族 $\{g_\pi\}$ を構築する。
   • 仮説クラスが、不一致集合が互いに非交差であるような欺く仮説の族を含んでいる場合、いかなる厳密な認証も、すべての不一致集合から少なくとも 1 つの例を含まなければならない。
   • したがって、認証サイズは、そのような非交差ブロックの数によって下方から抑えられる。
3. 過剰パラメータ化分析: 著者らは、最小限の容量の追加（例えば、回路における 1 つの追加ゲート、トランスフォーマーにおける 1 つの追加アテンションヘッドと定数幅の埋め込み）が、元のより小さなクラス内のすべてのターゲットに対して、これらの指数関数的な欺く仮説族の構築を可能にすることを分析する。

実証的分析

著者らは理論を二進数加算認識に関する 2 つの実験で補完する。

1. 構築された回路: 加算を認識する閾値回路（$TC_0$）に対して、理論的な欺き構築を具体化する。彼らは、入力ブロックのそれぞれでターゲットと異なる $2^n$ 個の誤った回路の集合を生成し、認証候補の均一サンプリングによっていくつが生存するかを測定する。
2. 学習されたトランスフォーマー: 彼らはエンコーダのみのトランスフォーマーを 10 ビット加算で学習させる。厳格な検証チェック（99.9% の精度）をパスしたモデルを選択した後、それらを大きな保持テストセットで評価する。彼らは、均一にサンプリングされた認証候補にさらされた際に、これらの不完全なモデル（欺き）が「生存」するかを分析し、多項式サイズのサンプルで残留誤差を検出できるかどうかをテストする。

主要な貢献と結果

1. 最小限の過剰パラメータ化による指数関数的困難性

主要な理論的貢献は、認証が仮説クラスのサイズに極めて敏感であることを実証することである。

• 閾値回路（$TC_0$）: 深度 $d \ge 2$ の回路において、単一の追加閾値ゲートを追加すること（ゲート予算を $s$ から $s+1$ に増やす）は、元のクラス $TC_{d,s}$ 内のすべてのターゲットの認証サイズを、入力次元 $n$ に対して指数関数的にさせる。具体的には、$\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ となる。
• トランスフォーマー: 平均化ハードアテンション（AHAT）を備えた対数精度トランスフォーマーにおいて、最終層に1 つのアテンションヘッドを追加し、6 つの補助的埋め込み/残差座標を追加することで、認証が指数関数的に困難になるように拡大されたクラスが作成される。ターゲット $f^*$ がより小さなアーキテクチャにおいて多項式サイズの認証を持つ場合でも、わずかに大きなアーキテクチャに対して認証するには指数関数的な数の例が必要となる。
• 空虚性の欠如: 著者らは、これらの下限が空虚ではないことを証明する。彼らは、より小さなクラス（$TC_{d,s}$ および標準的なトランスフォーマー）には多項式サイズの認証を持つターゲット（具体的には $O(\log |\mathcal{H}|)$）が含まれていることを示しつつ、これらの同じターゲットがクラスが最小限に拡大されると指数関数的に認証が困難になることを示す。

2. 近似認証の困難性

本論文は、これらの結果を近似認証に拡張する。

• 絶対誤差許容: 認証が多項式個の誤り（$R = \text{poly}(n)$）のみを許容する場合、認証サイズは指数関数的（$2^{\Omega(n)}$）のままとなる。
• 相対誤差許容: 認証が定数の相対誤差（$\epsilon$）を許容する場合、認証サイズは小さく（$1/\epsilon$ に関する多項式）なり得る。しかし、これは指数関数的に多い絶対誤差を許容する代償を伴う。著者らは、定数の相対誤差保証は指数関数的に多くの誤りを隠蔽し得るのに対し、多項式の絶対誤差保証は依然として指数関数的な認証を必要とすることを示す。

3. 実証的検証

• 回路実験: 構築された $TC_0$ 欺きは理論的障壁を確認した。多項式サイズの認証候補であっても、構築された欺きのほとんどはサンプリングされたラベルと整合したままとなり、それらを排除するには指数関数的なサンプリングが必要であった。
• トランスフォーマー実験: 広範な検証をパスした 150 個の学習済みモデルのうち、63 個が保持テストセット上で残留誤差を持っていた。分析は、誤りが多い例のターゲット部分集合を用いた場合でも、多項式サイズの均一にサンプリングされた認証候補が、すべての厳密でない仮説を排除することに失敗したことを示した。不完全なモデルは、大規模な均一サンプリング候補によって検出を回避し得た。

意義と主張

本論文は、厳密な学習に対する認証困難性の定量的な形態を提供すると主張する。その意義は、以下の主張にある。

1. モデル容量への感受性: 認証は単にターゲット関数の性質ではなく、「環境」仮説クラスに決定的に依存する。モデル容量の最小限の増加（定数オーバーヘッド）は、モデルの正しさを検証する難易度を根本的に変え得る。
2. 受動的認証の限界: 受動的な設定（モデルに問い合わせることなく例をサンプリングする）において、仮説クラスがわずかに過剰パラメータ化されている場合、多項式サイズのデータセットはモデルが意図された計算を学習したことを認証するには不十分である。
3. 学習可能性との区別: 結果は、学習可能性と認証の間のギャップを浮き彫りにする。関数が学習可能である（または制限されたクラスにおいて小さな認証を持つ）場合でも、わずかに大きなクラスに対してそれを認証することは非現実的となり得る。
4. 推論モデルへの示唆: 加算などのアルゴリズムタスクに展開されるモデルにとって、高い検証精度は厳密さを保証しない。本論文は、より強力なプロトコル（能動学習や特定の問い合わせなど）がなければ、大規模な均一サンプリングデータセットは、推論モデルにおける微妙で構造化された不一致を検出することに失敗する可能性があると示唆する。

著者らは結論として、厳密な認証は基礎的な課題であるが、その障壁は単なる最悪ケースの異常ではなく、現代の推論タスクに関連するクラスにおける最小限の過剰パラメータ化の構造的帰結であると述べる。彼らは、将来の研究はこれらの受動的障壁を克服する可能性を秘めた能動的認証プロトコルの探求を行うべきであると提案する。