🤖 machine learning

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

本論文は、科学的発見のための構成的関数木の学習におけるサンプル複雑性が、記号的構造の組合せ爆発ではなく、木の深さと演算子のリプシッツ定数によって支配されることを確立し、PAC学習可能性の境界および、汎化ギャップが $\mathcal{O}(L^d/\sqrt{n})$ にスケールするという経験的な検証を提供している。

原著者： Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

公開日 2026-06-30

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、コンピュータに単なるデータの集まりから「物理法則」（$F=ma$ や重力の仕組みなど）を発見させる方法を教えようとしていると想像してください。通常、科学者は**記号回帰（Symbolic Regression）**と呼ばれる手法を用います。ブラックボックス型のニューラルネットワークを与える代わりに、足し算（ $+$ ）、掛け算（ $\times$ ）、サイン（ $\sin$ ）、指数関数（ $e^x$ ）といった、特定の「レゴブロック」を使って数式を組み立てるようコンピュータに求めるのです。

最大の問題は、**「レゴの積み上げ方が多すぎる！」**ということでした。

もし10個のブロックを深く積み重ねると、可能な構造の数は数十億通りへと爆発的に膨れ上がります。長い間、人々はこれによって、コンピュータが正しい数式を見つけ出すためには、天文学的な量のデータが必要になると考えてきました。つまり、数式の深さに比例して、「統計的コスト（必要なデータ量）」が指数関数的に増大すると信じられていたのです。

しかし、この論文はこう言っています。「必ずしもそうではありません。」

以下に、著者たちの発見を日常的な例えを用いて分かりやすく解説します。

1. 「レゴの塔」 vs 「ぐらつく積み重ね」

数式を組み立てることを、レゴブロックを積み上げて塔を作ることに例えてみましょう。

かつての恐怖： 人々は、作ることができる「塔の形」があまりにも多いため、コンピュータが混乱してしまい、正しいものを見つけるために何百万ものデータポイントが必要になると考えていました。
新しい洞察： 著者らは、難しさは「形」の数にあるのではないと主張しています。問題は、その塔がどれほど**「安定しているか」**なのです。

もし、すべてのブロックがぐらついて滑りやすい（数学的に言えば、演算が「不安定」であったり、高いリプシッツ定数を持っていたりする）場合、塔全体が崩れたり、入力のわずかな変化で激しく揺らいだりしてしまいます。

論文の主張： もしレゴブロックが頑丈で安定していれば（数学的に「リプシッツ連続」であれば）、たとえ非常に高い塔（深い数式）であっても、必ずしも膨大なデータが必要になるわけではありません。統計的コストは、作れる「塔の総数」ではなく、その「塔がどれくらい揺れるか」によって決まるのです。

2. 「波及効果」（深さと複雑さ）

著者らは、数式の「複雑さ」が特定の方法で増大することを証明しました。

深さ ( $d$ ): 数学的な演算が何層積み重なっているか。
安定性 ( $L$ ): 各数学演算が、小さな誤差をどれだけ増幅させてしまうか。

彼らは、学習の難易度が、おおよそ $L^d / \sqrt{n}$ のようにスケールすることを発見しました。

$L^d$ : ブロックが少しでもぐらついている（ $L > 1$ ）場合、それらを深く（ $d$ ）積み重ねると、揺らぎが倍増していきます。これが「悪いニュース」です。
$\sqrt{n}$ : しかし、より多くのデータ（ $n$ ）を与えれば、学習は容易になります。データが多いほど、揺らぎを抑え込むことができます。

例え： 本を10冊積み重ねる場面を想像してください。

本が滑りやすい（高い $L$ ）場合、積み上げたものが倒れないようにするには、非常に安定した手（大量のデータ）が必要です。
本にゴムのグリップがついている（低い $L$ 、安定している）場合、もっと高く積み上げても、それほど苦労せずに済みます。
この論文は、単に「積み重ねが高いから」といって魔法のような量のデータが必要なわけではなく、使用している特定の「本の滑りやすさ」を打ち消すのに十分なデータさえあればよいのだ、ということを示しています。

3. 「物理実験室」の検証

これが単なる机上の空論ではないことを証明するために、著者らは「科学者のように振る舞うコンピュータプログラム」を作成しました。

彼らは、既知の数式（深さ1、2、4層）を持つ「偽の物理学」データ（例：丘を転がるボール）を作成しました。
そして、彼らの「レゴ組み立て機」を、少量のデータ（50から5,000の例）で訓練しました。
結果： 彼らは、見ていない新しいデータに対するコンピュータの予測精度（汎化ギャップ）を測定しました。

その結果、コンピュータのミスは彼らの予測と完璧に一致しました。

数式が深かったり、「滑りやすい」数学（ $e^x$ など）を使用していたりすると、ミスは大きくなりました。
データを追加すると、ミスは減少しました。これは彼らの数式が予測した通りでした。

4. これが「科学的発見」にとって何を意味するか

この論文は、数式が安定していれば、記号回帰は非常に深い数式であっても統計的に「学習可能」であると結論付けています。

良いニュース： 私たちは、科学法則を発見するために無限のデータを必要とするわけではありません。探している法則が、安定した滑らかな数学で作られているならば、コンピュータは合理的な量のデータでそれを見つけ出すことができます。
注意点： この論文は、数式を「見つける」ことが簡単だと言っているわけではありません。あくまで、正しい構造さえあれば「学習する」ことが可能だと言っているのです。「数十億通りのレゴの形の中から探し出す」という困難な部分は、依然としてデータの問題ではなく、コンピュータの計算速度の問題として残っています。

要約すると：
この論文は、科学的な数式を発見するための「統計的な難易度」は、可能な数式の総数によって決まるのではなく、その数学がいかに「ぐらつきやすいか」によって決まることを教えてくれます。数学が安定していれば、比較的少ないデータセットであっても、深く複雑な法則を発見できるのです。コンピュータに必要なのは、ただ、その揺らぐ塔が倒れないように支えるための、十分なデータなのです。

技術的要約：科学的発見におけるサンプル複雑性

問題提起
記号回帰（Symbolic Regression, SR）による科学的発見は、しばしば統計的および計算的に手に負えないものとして特徴づけられる。支配的な見解では、記号式の仮説空間は深さに伴って組合せ爆発的に増大するため、最適な式の探索はNP困難であり、そのようなモデルの統計的な汎化は信頼できないとされる。本論文は、計算の困難さと統計的な学習可能性の混同に異議を唱えるものである。著者は、最適な記号構造を見つけることは計算的に困難であるが、構成的な関数木の統計的な汎化は、基礎となる演算子が安定性の特性を備えているならば、良好な挙動を示す可能性があると主張している。ここで扱われる核心的な問いは、構成的な演算子木のサンプル複雑性が、木の深さに対して指数関数的に爆発するのか、それとも演算子の安定性（リプシッツ性）と木の深さによって制御されるのか、という点である。

手法
著者らは、おそらく近似的に正しい（Probably Approximately Correct, PAC）学習理論の観点から、ラデマッハー複雑度（Rademacher complexity）を用いて汎化誤差を抑え込むことで問題にアプローチしている。

仮説空間の定義: 本研究では、深さ $d$ の根を持つ演算子木からなる構成的仮説空間 $H^d_{comp}$ を定義する。内部ノードは、 $\{+, \times, \sin, \cos, \exp\}$ やアフィン写像などの有限の語彙（ $H_{base}$ ）から抽出される。葉ノードは、入力座標または有界なアフィン関数である。
理論的枠組み:
- リプシッツ仮定: 解析では、基礎となる演算子が関連するデータ範囲において局所的にリプシッツ連続であり、その定数が $L_h$ であると仮定する。境界を定めるために、最大のリプシッツ定数 $L = \max L_h$ が使用される。
- ラデマッハー複雑度: 著者らは、経験的ラデマッハー複雑度 $R_n(H^d_{comp})$ の上界を導出する。その際、古典的な縮小引数（Ledoux & Talagrand, 1991）およびベクトル縮小不等式（Maurer, 2016）を、木構造の合成へと拡張している。
- 再帰的境界: 有限の演算子語彙（ $b$ 個の子を持つ場合、アリティは $b$ ）に対する和集合境界を適用し、ベクトル縮小を用いて、深さ $d$ と深さ $d-1$ の間の複雑性の再帰的な関係を確立する。
実験的検証:
- 合成データ: 著者らは、制御された深さ（ $d \in \{1, 2, 3, 4\}$ ）と既知の正解構造を持つ、合成的な「物理学的性質を持つ」ターゲットを生成するためのモジュール化されたPyTorchコードベースを構築した。
- 微分可能な木: 遺伝的プログラミングや離散探索の代わりに、勾配降下法（Adam）を用いて、演算子の係数を適合させるための微分可能な演算子木を訓練した（これはMLPではない）。
- 指標: 著者らは汎化ギャップ（テストMSEと訓練MSEの差）を測定し、理論的な複雑性項 $(bL^d)/\sqrt{n}$ （ここで $\hat{L}$ は勾配ノルムから導出されたリプシッツ定数の経験的推定値）と比較した。

主な貢献

SRの統計的学習可能性: 本論文は、構成的な木の汎化能力が、必ずしも個別の記号構造の数に対して指数関数的に増大するわけではないことを証明している。むしろ、それは木の深さ $d$ と演算子のリプシッツ定数によって支配される。
明示的な複雑性境界: 著者らは、経験的ラデマッハー複雑度に関する具体的な上界を導出した：
$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$
その結果、語彙サイズ $K$ とアリティ $b$ を定数として扱う場合、超過リスクは $O(L^d / \sqrt{n})$ となる。これは、離散的な構文空間の濃度に依存する境界とは対照的である。
探索と推定の分離: 本研究は、離散的な最適化問題（木の構造の探索）と、連続的な回帰問題（係数の適合）を形式的に分離している。導出された境界は後者に適用され、ある構造が提案された後に期待される統計的なスケーリングを明確にしている。
経験的相関: 実験により、観察された汎化ギャップと予測された複雑性項 $(bL^d)/\sqrt{n}$ との間の正の相関が示された。データは、ギャップが深さ（リプシッツ定数の累積による）に伴って増加し、サンプルサイズ（ $1/\sqrt{n}$ ）に伴って減少することを示しており、このスケーリングは理論的予測と一致している。

結果

理論的: 定理 4.9 は、有界な出力とリプシッツ連続な演算子に対して、超過リスクが $1/\sqrt{n}$ で減衰することを確立しており、その定数因子はリプシッツ定数の積を介して深さに指数関数的に依存する。系 4.11 はこれを PAC サンプル複雑度の境界へと変換し、サンプル複雑性が樹木の組合せ的な数ではなく、 $L^{2d}$ に比例してスケールすることを示している。
経験的: 深さ（ $d$ $d$ ）とサンプルサイズ（ $n$ $n$ ）を変化させた400回の実験ランを通じて、汎化ギャップが理論的項を追跡していることが判明した。
- 浅い深さ（ $d=1, 2$ ）では、リプシッツ近似 $\hat{L}$ は安定しており、ギャップは主に $1/\sqrt{n}$ でスケールした。
- $\exp$ のような非線形性を伴う深い合成（ $d=3, 4$ ）では、 $\hat{L}$ が増大し、結果としてギャップも大きくなった。これは、安定性定数の乗法的蓄積と一致している。
- 対数・対数スケールでのべき乗則フィットは 0.48 の相関を示した。これは、構成的複雑性項が汎化ギャップの分散の有意な部分を捉えていることを示唆しているが、最適化誤差やノイズといった他の要因も役割を果たしている。

意義と主張
本論文は、記号回帰を用いた科学的発見に対する「学習可能性の証明書（learnability certificate）」を提供することを主張している。その主要な意義は、記号構造の組合せ爆発から、演算子の**構成的安定性（compositional stability）**へと視点を転換した点にある。

小規模データによる発見の実現可能性: 著者らは、安定した演算子語彙と適度な深さが確保されていれば、小規模なデータセットからの科学的発見は統計的に実現可能であると主張している。統計的な汎化はボトルネックではなく、むしろ構造の計算的探索と誘導バイアスの設計が課題である。
スケーリングの明確化: 本研究は、非線形係数の推定における統計的スケーリングが、樹形の全列挙ではなく、計算グラフに沿ったリプシッツ定数の蓄積によって決定されることを明らかにしている。
限界: 著者らは、自らの保証は一様境界（uniform bounds）であり、PAC-Bayes 的な手法ほど構造的事前分布（オッカムの剃刀など）を効果的に活用していないことを謙虚に述べている。さらに、経験的検証は、制御されたイン・ディストリビューションの合成データ（1次元入力）に依存しており、分布シフトや誤指定下での挙動については、これらの境界による保証はない。推定値 $\hat{L}$ は、最悪のケースのグローバルな定数を証明するものではなく、適合された写像上の安定性を測定するものである。

結論として、本論文は、記号回帰モデルが、安定したプリミティブを持つ構成的関数木として捉えられる場合、深さと演算子の安定性が管理されている限り、限られたデータからでも汎化が可能となる好ましい統計的特性を備えていると断じている。

1. 「レゴの塔」 vs 「ぐらつく積み重ね」

2. 「波及効果」（深さと複雑さ）

3. 「物理実験室」の検証

4. これが「科学的発見」にとって何を意味するか

技術的要約：科学的発見におけるサンプル複雑性

関連論文