기술 요약: 답변 집합 프로그래밍을 위한 신경 결정 - 전파

1. 문제 제기

신경 - 심볼릭 AI 에서 답변 집합 프로그래밍 (ASP) 과 신경망의 통합은 견고한 학습과 심볼릭 추론을 결합할 수 있게 하여 유망한 방향으로 부상했습니다. 그러나 기존 접근법 (예: NeurASP, SLASH) 은 일반적으로 추론 파이프라인 내에서 고전적인 ASP 솔버에 의존합니다. 이러한 의존성은 심볼릭 솔버가 종종 계산 비용이 많이 들고 엔드 - 투 - 엔드 미분 가능 학습 프레임워크에 통합하기 어렵기 때문에 확장성에 심각한 병목 현상을 초래합니다. 또한, 일부 방법은 확률적 피드백을 사용하여 검색 공간을 축소하려 시도하지만, 여전히 근본적으로 이산적이고 미분 불가능한 해결 메커니즘에 의존합니다.

본 논문은 외부 심볼릭 솔버에 의존하지 않고 신경망과 원활하게 통합되며 학습 가능한 결정 휴리스틱을 계산할 수 있는 확장 가능하고 미분 가능한 안정 모델 계산 방법을 필요로 합니다.

2. 방법론

2.1 결정 - 전파 (DProp)

저자들은 먼저 고전적 ASP 에서 안정 모델을 계산하기 위한 새로운 알고리즘인 **결정 - 전파 (DProp)**를 제안합니다. DProp 는 원자 (atoms) 집합 $A$를 작동하며, 이를 True($T$), False($F$), Undecided($U$) 의 세 가지 불교합 집합으로 분할합니다. 알고리즘은 종료될 때까지 두 번의 교번 단계를 반복합니다:

1. 결정 단계: 알고리즘은 미결정된 원자 $a \in U$를 비결정적으로 선택하고 이를 False로 결정하여 $F$로 이동시킵니다.
2. 전파 단계: 집합 $F$를 고정된 상태로 두고, 알고리즘은 현재 $T$에서 시작하여 즉각적 결과 연산자 $C_{P, A \setminus F}$의 최소 고정점을 전방향 체이닝 (forward-chaining) 방식으로 유도합니다. 참으로 유도된 원자들은 $U$에서 $T$로 이동합니다.

이 과정은 $U$가 비어있을 때 종료됩니다. 계산이 $U = \emptyset$으로 종료되고 모순 ($T \cap F = \emptyset$) 이 없을 때 성공한 것으로 간주됩니다. 저자들은 모든 성공적인 DProp 계산이 프로그램의 안정 모델 의미를 포착함을 증명합니다. 구체적으로, 집합 $S$가 안정 모델일 필요충분조건은 성공적인 DProp 실행의 최종 참 집합인 것입니다.

2.2 신경 결정 - 전파 (NDProp)

학습과 신경망 통합을 가능하게 하기 위해 저자들은 DProp 의 미분 가능한 확장인 NDProp를 개발했습니다.

• 표현: 이진 집합 대신 NDProp 은 각 원자에 대해 연속적인 참도 $\tau \in [0, 1]^n$과 거짓도 $\phi \in [0, 1]^n$을 유지합니다. 소속 점수 $p_i = \frac{1}{2}(\tau_i + 1 - \phi_i)$는 소프트 참값을 나타냅니다.
• 미분 가능한 결정: "결정" 단계는 순환 신경망 (RNN) 결정 모듈을 통해 구현됩니다. RNN 은 현재 상태 ($\tau, \phi$, 그리고 미결정 정도 $\mu$) 를 입력받아 결정 로짓을 출력하며, 이를 시그모이드 함수를 통해 점수 $\delta$로 변환합니다. 거짓도는 가산적으로 업데이트됩니다: $\phi^{t+1} = \phi^t + (\mu^t \odot \delta^t)$. 이를 통해 네트워크는 어떤 원자를 거짓으로 만들지 학습할 수 있습니다.
• 미분 가능한 전파: "전파" 단계는 참도 $\tau$를 업데이트하기 위해 퍼지 논리 연산자 (t-norm 과 t-conorm) 를 사용합니다. 이는 소프트 즉각적 결과 연산자 $C_{P, \phi}$를 고정점 수렴 (또는 고정된 단계 수) 할 때까지 반복합니다.
• 크리스프 복구: 저자들은 입력과 출력이 이진 값 (0 또는 1) 으로 제한될 때 NDProp 이 이산 DProp 알고리즘과 정확히 일치함을 증명합니다.
• 안정성 강제: 논문은 손실 함수 (예: 이진 교차 엔트로피) 를 통해 이진 출력을 강제함으로써 전파가 고정점에 도달한다면 시스템이 내재적으로 안정 모델로 수렴하게 됨을 보여줍니다. 이는 답변 집합에 대한 명시적 레이블 없이도 모델이 안정 모델을 찾도록 학습하는 비지도 학습을 가능하게 합니다.

3. 주요 기여

1. DProp 알고리즘: 교번하는 거짓 결정과 참 전파에 기반한 안정 모델 계산의 새로운 방법 도입 및 성공적인 실행이 안정 모델 의미를 포착한다는 공식적 증명.
2. NDProp 프레임워크: 의사결정에 신경망을, 전파에 퍼지 논리를 사용하는 완전한 미분 가능한 확장 (NDProp) 개발. 크리스프 경우에 DProp 와 일치함이 입증됨.
3. 학습 역학: 외부 솔버에 의존하지 않고 무작위 ASP 문제를 해결하기 위한 결정 휴리스틱을 NDProp 이 학습할 수 있음을 입증.
4. 신경 - 심볼릭 통합: NDProp 을 신경 - 심볼릭 파이프라인에 성공적으로 통합하여, 솔버 기반 베이스라인에 비해 인식과 추론의 엔드 - 투 - 엔드 학습이 더 우수한 정확도와 확장성을 제공함을 보여줌.

4. 실험 결과

저자들은 세 가지 유형의 실험을 수행했습니다:

• 무작위 ASP 해결: 무작위 음수 2-리터 (N2L) 및 3-LP 프로그램을 사용하여 NDProp 이 결정 역학을 학습하도록 훈련시켰습니다. 결과는 NDProp 이 1-샷 설정에서도 무작위 결정 베이스라인 (RDProp) 을 크게 능가했으며, 더 큰 문제 크기로도 잘 일반화되었음을 보였습니다.
• 신경 - 심볼릭 벤치마크: MNIST 기반 산술 작업 (덧셈, Add2x2, Apply2x2, 소속도) 에서 평가했습니다. NDProp 은 NeurASP 및 SLASH 와 비교되었습니다.
  • 정확도: NDProp 은 모든 작업에서 더 높은 인식 및 추론 정확도를 달성했습니다.
  • 속도: GPU 병렬화와 심볼릭 솔버 호출 제거로 인해 NDProp 은 훨씬 빠른 추론 속도를 보였습니다 (NeurASP 대비 평균 46 배, SLASH 대비 7.5 배 빠름).
• 불완전 데이터로 추론: 불완전한 숫자 분류기 예측이 포함된 시각적 스도쿠 작업에서 NDProp 은 순수 신경 베이스라인과 표준 ASP 솔버 모두를 능가했습니다. 예측에 노이즈가 있을 때 (1% 데이터) ASP 솔버는 크게 실패한 반면, NDProp 은 호환 가능한 솔루션을 찾기 위한 검색을 안내하는 휴리스틱으로 노이즈가 있는 예측을 사용하여 견고성을 유지했습니다.

5. 중요성 및 주장

본 논문은 NDProp 이 새로운 고정점 의미론에 기반한 완전한 미분 가능한 답변 집합 솔버를 제공한다고 주장합니다. 그 주요 중요성은 다음과 같습니다:

• 확장성: 고전적 심볼릭 솔버에 대한 의존성을 제거함으로써 NDProp 은 훨씬 더 높은 추론 속도를 달성하고 더 큰 문제로 확장됩니다.
• 엔드 - 투 - 엔드 학습: 인식 (신경망) 과 추론 (논리) 의 공동 최적화를 가능하게 하여 신경 - 심볼릭 시스템에서 더 일관되고 통합된 출력을 도출합니다.
• 이론적 건전성: 이 방법은 고전적 안정 모델 의미론과의 명확한 연결을 유지하여 이진 출력이 유효한 안정 모델에 해당함을 보장합니다.

저자들은 t-norm 선택과 퍼지 변형 또는 복잡한 구성 요소 (제약 조건, 집계) 로의 확장은 향후 과제로 남아있지만, NDProp 이 신경 아키텍처 내에서 ASP 추론을 확장 가능하고 학습 가능하게 만드는 중요한 진전이라고 결론지었습니다.