과학적 발견의 샘플 복잡도: 구성 함수 트리(Compositional Function Trees)의 PAC 학습 가능성

심볼릭 회귀(symbolic regression)를 통한 과학적 발견은 가설 공간이 깊이에 따라 조합적으로 증가하기 때문에 통계적, 계산적으로 다루기 어렵다고 여겨지는 경우가 많습니다. 본 논문은 이러한 관점을 PAC 학습(PAC learning)의 렌즈를 통해 재검토하며, 유한한 범위의 부드러운 연산자(smooth operators) (예: ${+, imes, ext{sin}, ext{exp}}$ 및 아핀 변환(affine maps))로 구축된 구성 함수 트리(compositional function trees)에 초점을 맞춥니다. 우리는 관련 일반화 양(generalization quantity)인 라데마허 복잡도(Rademacher complexity), 그리고 따라서 과잉 위험(excess risk)이 반드시 고유한 심볼릭 구조의 수에 따라 지수적으로 폭발하지 않으며, 대신 (i) 깊이 $d$와 (ii) 구성된 계산 그래프를 따라 기본 연산자들의 리프시츠 상수(Lipschitz constants)에 의해 제어됨을 증명합니다. 구체적으로, 연산자에 대한 온건한 리프시츠 조건과 유계 아핀 리프(bounded affine leaves) 하에서, 크기가 $K=|\mathcal{H}_{ ext{base}}|$인 어휘집에 대한 유한 합집합 경계(finite-union bound)와 Maurer 유형 벡터 수축을 결합하면, 다음 관계를 얻습니다: $\mathfrak{R}n(\mathcal{H}{ ext{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}n(\mathcal{H}{ ext{comp}}^{1})$ (여기서 $b$는 아리티(arity) 상한입니다). 이에 대응하는 고확률 위험 경계는 $K, b=O(1)$이고 $\mathfrak{R}n(\mathcal{H}{ ext{comp}}^{1})=O(n^{-1/2})$일 때 $\mathcal{O}(L^{d}/\sqrt{n})$으로 스케일합니다. 우리는 이론을 모듈식 코드베이스로 보완하여, 제어된 깊이의 합성 '물리 기반' 목표값에 대해 미분 가능한 연산자 트리(MLPs가 아닌)를 훈련시키고, 경험적 일반화 간격(empirical generalization gap)이 예측된 복잡도 항 $(\widehat{L}^{d})/\sqrt{n}$과 양의 상관관계를 가짐을 보여줍니다.