기술 요약: EM-NeSy: 신경-기호 학습을 위한 기대-최대화(Expectation Maximization)

문제 정의

신경-기호(Neurosymbolic, NeSy) 모델은 신경망의 지각적 강점과 기호 논리의 추론 능력을 통합하는 것을 목표로 한다. 최첨단 NeSy 모델들은 일반적으로 역전파를 통해 신경 및 기호 구성 요소를 모두 통과하며 엔드 투 엔드(end-to-end) 학습을 수행하지만, 이 접근 방식은 기호 구성 요소가 근사 추론에 의존할 때 상당한 어려움에 직면한다.

정확한 확률 추론(Exact probabilistic inference)은 복잡한 작업에서 #P-hard이며 계산적으로 불가능한 경우가 많다. 결과적으로 많은 시스템이 근사 추inference 방법(예: 샘플링, 신념 전파 또는 선형 계획법 완화)을 사용하게 된다. 그러나 이러한 방법들은 미분 가능성 문제를 야기한다:

1. 비미분성(Non-differentiability): 샘플링과 같은 기술은 본질적으로 미분 불가능하며, 이를 위해 특수한 그래디언트 추정기(예: REINFORCE)나 재매개변수화 트릭(reparameterization tricks)이 필요하다.
2. 계산 오버헤드: 이론적으로는 미분 가능한 반복적 방법(예: 신념 전파)이라 할지라도, 모든 반복 과정을 통과하여 역전파를 수행하기 위해 필요한 거대한 계산 그래프 때문에 실제 적용 시에는 비실용적이다.

현재의 솔루션들은 미분 가능성을 보장하기 위해 추론 특화된 수정 사항을 요구하는 경우가 많으며, 이는 NeSy 시스템의 유연성과 확장성을 제한한다.

방법론: EM-NeSy

저자들은 EM-NeSy를 제안하며, 이는 확률적 NeSy 학습을 기대-최대화(Expectation-Maximization, EM) 알고리즘의 한 사례로 간주한다. 이 정식화는 기호 추론 과정을 그래디언트 계산으로부터 분리하여, 어떤 추론 엔진(정확하거나 근사적인, 혹은 미분 가능하거나 불가능한)도 사용할 수 있게 한다.

프레임워크

NeSy 모델은 다음과 같은 잠재 변수 모델로 취급된다:

• $X$: 하위 심볼릭 입력 (예: 이미지).
• $Z$: 잠재 기호 변수 (신경망에 의해 예측됨).
• $Y$: 타겟 기호 출력 (예: 스도쿠 격자의 유효성).
• $\theta$: 신경망 파라미터.

학습 과정은 다음 두 단계를 교대로 수행한다:

1. E-단계 (Expectation):
   기호 구성 요소는 관측된 레이블 $Y$와 입력 $X$가 주어졌을 때의 잠재 변수 $Z$의 사후 분포를 계산한다:
   $$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$$
   여기서 $p_{Ne}$는 신경 사전 확률(neural prior)이고 $p_{Sy}$는 기호 가능도(symbolic likelihood)이다. 결정적으로, 이 단계는 배경 지식을 바탕으로 $Z$에 대한 소프트 또는 하드 레이블을 추론하는 "확률적 교정기(probabilistic corrector)" 역할을 한다. 이 단계는 미분 가능성 여부와 상관없이 어떠한 기호 추론 엔진(정확한, 근사적인, 샘플링 기반 등)에 의해서도 수행될 수 있다.

2. M-단계 (Maximization):
   신경 파라미터 $\theta$는 E-단계에서 계산된 사후 분포 $\ell(z)$와 신경 사전 확률 $p_{Ne}(z|x, \theta)$ 사이의 크로스 엔트로피를 최소화함으로써 업데이트된다:
   $$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$$
   그래디언트는 사후 분포 $\ell(z)$를 상수로 취급하여 신경 구성 요소만을 통해 역전파된다. 이를 통해 기호 추론 과정을 미분할 필요성을 제거한다.

이론적 동등성

본 논문은 정확한 추론(exact inference) 하에서 EM-NeSy가 계산하는 그래디언트가 표준 엔드 투 엔드 미분 가능 NeSy 학습의 그래디언트와 수학적으로 동일함을 증명한다(정리 3.1). 따라서 EM-NeSy는 정확한 추론이 가능한 경우 표준 설정을 복구하면서도, 그것이 불가능할 때 차별화된 이점을 제공한다.

변형 및 확장

• Hard EM: 소프트 사후 분포 대신 최대 사후 확률(MAP) 할당을 사용한다.
• Multi-M EM: 하나의 E-단계에 대해 여러 번의 M-단계(그래디언트 업데이트)를 수행하여, 비용이 많이 드는 사후 분포 재계산 없이 수렴을 가속화한다.
• 근사 추론: 이 프레임워크는 수정 없이 샘플링 기반 방법(예: Rejection Sampling, ABC Sampling) 및 반복 알고리즘(예: Belief Propagation)을 자연스럽게 지원한다.

주요 기여

1. NeSy 학습의 재정식화: 저자들은 NeSy 학습을 EM 프레임워크 내로 재구성하여, 향상된 유연성을 위해 고급 EM 변형(Generalized EM, Stochastic EM, Hard EM)을 사용할 수 있게 했다.
2. 미분 불필요한 통합: 기호 추론 과정이 미분 가능할 필요 없이, 어떤 확률적 추론 엔진도 NeSy 모델에 통합할 수 있는 일반적인 프레임워크를 제안했다.
3. 확장성 및 효율성: 이 접근 방식은 정확한 추론이 난해하거나 반복 솔루션을 미분하는 것이 계산적으로 과도한 비용이 드는 작업에서도 NeSy 학습이 확장 가능함을 입증했다.

실험 결과

저자들은 세 가지 벤치마크인 MNISTAdd(손으로 쓴 숫자의 덧셈), Visual Sudoku, Warcraft path-planning에서 EM-NeSy를 평가했다.

• 정확한 추론 (MNISTAdd): EM-NeSy는 표준 엔드 투 엔드 미분 가능 NeSy(BP-std) 및 DeepStochLog와 유사한 정확도를 달성했다. 그러나 확장성과 효율성 측면에서는 이들을 크게 앞질렀다. DeepStochLog는 지식 컴파일 한계로 인해 15자리 숫자로 확장하는 데 실패한 반면, EM-NeSy는 100자리 숫자까지 확장 가능했다. 또한 피크 메모리 사용량을 약 90 GB에서 35 GB로 줄였고 훈련 시간도 단축했다.
• 근사/비미분 추론:
  • Visual Sudoku: 표준 미분 가능 방법들(Scallop, SL)은 9x9 격자에서 시간 초과가 발생했다. ABC 샘pling을 사용한 EM-NeSy는 최소한의 훈련 시간(8.24분)으로 경쟁력 있는 정확도(53.3%)를 달달성했으며, 다른 방법들은 적용조차 불가능했다.
  • Warcraft Path-Planning: ABC 샘플링을 사용한 EM-NeSy는 I-MLE 및 EXAL에 비해 훨씬 빠른 훈련 시간과 함께 최첨단 정확도(12x12에서 98.80%, 30x30에서 69.60%)를 달성했다.
• 관찰된 한계점: EM-NeSy의 성능은 근사 사후 분포의 품질에 의존한다. Hard EM(MAP)은 MNISTAdd에서 편향(bias)을 보였고, Loopy Belief Propagation은 팩터 그래프 구조로 인해 9x9 Sudoku에서 실패했다. ABC 샘플링은 더 큰 인스턴스에서 높은 분산을 보였으나 작은 설정에서는 여전히 효과적이었다.

의의 및 주장

본 논문은 EM-NeSy가 추론 특화된 미분 가능성 수정을 제거함으로써 모델 설계를 실질적으로 단순화하는 통합 학습 프레임워크를 제공한다고 주장한다. EM 문제로 NeSy 학습을 다룸으로써 다음과 같은 이점을 얻는다:

• 특화되거나 최적화되었거나 비미분적인 솔버를 포함한 모든 기호 추론 엔진을 사용할 수 있다.
• 정확한 추론 하에서는 표준 엔드 투 엔드 학습을 복구하면서도 우수한 계산 효율성과 메모리 확장성을 제공한다.
• 정확한 추론이 불가능하거나 미분 가능한 근사를 구축하기 어려운 복잡한 조합 제약(경로 계획이나 Sudoku와 같은)이 포함된 작업을 수행할 수 있도록 NeSy 시스템을 가능하게 한다.

저자들은 EM-NeSy가 효과적인 근사치를 선택하는 문제(여전히 작업 의존적임)를 해결하는 것은 아니지만, 미분 가능성이라는 장벽을 제거함으로써 더 확장 가능하고 유연한 신경-기호 시스템을 가능하게 한다고 결론짓는다.