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

기술 요약: 과학적 발견의 샘플 복잡도

문제 정의
기호 회귀(Symbolic Regression, SR)를 통한 과학적 발견은 흔히 통계적 및 계산적으로 난해한 것으로 특징지어진다. 지배적인 견해는 기호적 표현의 가설 공간이 깊이에 따라 조합론적으로 증가하며, 이로 인해 최적의 표현을 찾는 과정은 NP-hard가 되고, 이러한 모델의 통계적 일반화는 신뢰할 수 없다고 제안한다. 본 논문은 계산적 어려움과 통계적 학습 가능성을 혼동하는 것에 이의를 제기한다. 본 논문은 최적의 기호 구조를 찾는 것은 계산적으로 어려울 수 있으나, 구성적 연산자(compositional operators)들이 안정성 속성을 갖는다면 구성적 함수 트리(compositional function trees)의 통계적 일반화는 잘 작동할 수 있다고 상정한다. 핵심 질문은 기호적 연산자 트리의 샘플 복잡도가 깊이에 따라 지수적으로 폭발하는가, 아니면 연산자의 안정성(Lipschitzness)과 트리의 깊이에 의해 제어되는가 하는 것이다.

연구 방법론
저자들은 문제를 아마도 근사적으로 올바른(Probably Approximately Correct, PAC) 학습 이론의 관점에서 접근하며, 특히 라데마허 복잡도(Rademacher complexity)를 사용하여 일반화 오차를 경계 짓는다.

1. 가설 공간 정의: 연구는 깊이 $d$를 가진 루트 연산자 트리로 구성된 구성적 가설 공간 $H^d_{comp}$를 정의한다. 내부 노드는 $\{+, \times, \sin, \cos, \exp\}$ 및 아핀 맵(affine maps)과 같은 유한한 어휘 집합($H_{base}$)에서 추출된다. 리프 노드는 입력 좌표이거나 유계된 아핀 함수이다.
2. 이론적 프레임워크:
   • 리프시츠(Lipschitz) 가정: 분석은 기초 연산자들이 관련 데이터 범위 내에서 국소적 리프시츠 연속성 상수 $L_h$를 가진다고 가정한다. 바운딩을 위해 전역 리프시츠 상수 $L = \max L_h$가 사용된다.
   • 라데마허 복잡도: 저자들은 경험적 라데마허 복잡도 $R_n(H^d_{comp})$에 대한 상한을 도출한다. 이들은 고전적인 수축 정리(contraction arguments, Ledoux & Talagrand, 1991)와 벡터 수축 부등식(vector contraction inequalities, Maurer, 2016)을 트리 구조의 합성(composition)으로 확장한다.
   • 재귀적 경계: 유한한 연산자 어휘 집합($K = |H_{base}|$)에 대한 유니언 바운드(union bound)를 적용하고, $b$개의 자식(arity)에 대한 벡터 수축을 활용함으로써, 저자들은 깊이 $d$와 $d-1$ 사이의 복잡도에 대한 재귀적 관계를 확립한다.
3. 실험적 검증:
   • 합성 데이터: 저자들은 제어된 깊이($d \in \{1, 2, 3, 4\}$)와 알려진 정답 구조를 가진 합성 "물리 유사" 타겟을 생성하기 위해 모듈형 PyTorch 코드베이스를 구축하였다.
   • 미분 가능한 트리: 유전 프로그래밍이나 이산 탐색 대신, 저자들은 그래디언트 하강법(Adam)을 사용하여 연산자의 계수를 맞추는 미분 가능한 연산자 트리를 학습시켰다(MLP가 아님).
   • 지표: 저자들은 일반화 갭(테스트 MSE - 훈련 MSE)을 측정하고, 이를 이론적 복잡도 항 $(bL^d)/\sqrt{n}$ (여기서 $\hat{L}$은 그래디언트 노름으로부터 도출된 경험적 리프시츠 상수 추정치)과 비교하였다.

주요 기여

1. SR의 통계적 학습 가능성: 본 논문은 구성적 트리의 일반화 능력이 별개의 기호 구조의 개수에 따라 반드시 지수적으로 폭발하지 않음을 증명한다. 대신, 이는 연산자의 리프시츠 상수와 깊이 $d$에 의해 결정된다.
2. 명시적 복잡도 경계: 저자들은 다음과 같은 구체적인 라데마허 복잡도 상한을 도출한다:
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   결과적으로, 어휘 크기 $K$와 아리티(arity) $b$를 상수로 취급할 때 초과 위험(excess risk)은 $O(L^d / \sqrt{n})$으로 스케일링된다. 이는 이산적 구문 공간의 카디널리티에 의존하는 경계와 대조된다.
3. 탐색과 추정의 분리: 본 연구는 트리 구조를 찾는 이산 최적화 문제와 계수를 맞추는 연속 회귀 문제를 공식적으로 분리한다. 도출된 경계는 후자에 적용되며, 구조가 제안되었을 때 기대할 수 있는 통계적 스케일링을 명확히 한다.
4. 경험적 상관관계: 실험은 관찰된 일반화 갭과 예측된 복잡도 항 $(bL^d)/\sqrt{n}$ 사이의 양의 상관관계를 보여준다. 데이터는 깊이가 깊어질수록(리프시츠 상수의 누적으로 인해) 그리고 샘플 크기가 커질수록($1/\sqrt{n}$) 갭이 변화함을 보여주며, 이러한 스케일링이 이론적 예측과 일치함을 입증한다.

결과

• 이론적 결과: 정리 4.9는 유계 출력과 리프시츠 연산자에 대해 초과 위험이 $1/\sqrt{n}$으로 감소함을 확립하며, 상수 인자는 리프시츠 상수의 곱을 통해 깊이에 따라 지수적으로 의존한다. 추론 4.11은 이를 PAC 샘플 복잡도 경계로 변환하여, 샘플 복잡도가 트리 형태의 조합적 개수가 아닌 $L^{2d}$에 따라 스케일링됨을 보여준다.
• 경험적 결과: 깊이($d$)와 샘플 크기($n$)를 변화시킨 400회의 실험 실행 전반에 걸쳐, 일반화 갭은 이론적 항을 추적하는 것으로 나타났다.
  • 얕은 깊이($d=1, 2$)의 경우, 리프시츠 대리 지표 $\hat{L}$이 안정적이었으며, 갭은 주로 $1/\sqrt{n}$에 따라 스케일링되었다.
  • $\exp$와 같은 비선형성을 포함하는 더 깊은 합성($d=3, 4$)의 경우, $\hat{L}$이 증가하여 갭이 커졌으며, 이는 안정성 상수의 곱셈적 누적과 일치한다.
  • 로그-로그 스케일에서의 멱법칙 피팅(power-law fit)은 0.48의 상관관계를 나타냈으며, 이는 구성적 복잡도 항이 일반화 갭의 분산 중 의미 있는 부분을 포착하고 있음을 나타낸다. 다만 최적화 오차, 노이즈 등 다른 요인들도 역할을 한다.

의의 및 주장
본 논문은 기호 회귀를 이용한 과학적 발견에 대한 "학습 가능성 인증서(learnability certificate)"를 제공한다고 주장한다. 본 연구의 주요 의의는 관점을 기호 구조의 조합론적 폭발에서 **연산자의 구성적 안정성(compositional stability)**으로 전환하는 데 있다.

• 소규모 데이터 기반 발견의 타당성: 저자들은 안정적인 연산자 어휘와 적절한 깊이가 있다면, 소규모 데이터셋으로부터의 과학적 발견이 통계적으로 가능하다고 주장한다. 통계적 일반화가 병목이 아니라, 오히려 구조에 대한 계산적 탐색과 귀납적 편향(inductive bias)의 설계가 남은 과제이다.
• 스케일링의 명확화: 본 연구는 비선형 계수 추정의 통계적 스케일링이 가능한 트리 형태의 열거가 아니라, 계산 그래프를 따른 리프시츠 상수의 누적에 의해 결정됨을 명확히 한다.
• 한계점: 저자들은 자신들의 보장이 균등 경계(uniform bounds)이며, PAC-Bayes 방식만큼 구조적 사전 확률(structural priors, 예: 오캄의 면도날)을 효과적으로 활용하지 못한다는 점을 겸허히 언급한다. 또한, 실험적 검증은 제어된 분포 내(in-distribution) 합성 데이터와 1차원 입력에 의존하므로, 분포 변화(distribution shift)나 오지정(misspecification) 상황에서의 동작은 이 경계에 의해 보장되지 않는다. 추정치 $\hat{L}$은 최악의 경우의 전역 상수를 인증하기보다는 적합된 맵(fitted map) 상의 안정성을 측정한다.

결론적으로, 본 논문은 기호 회귀 모델이 안정적인 프리미티브를 가진 구성적 함수 트리로 간주될 때, 깊이와 연산자의 안정성이 관리된다면 제한된 데이터로도 일반화가 가능한 유리한 통계적 특성을 보유하고 있다고 단언한다.