본 논문은 기존 신경기호(Neuro-Symbolic, NeSy) 학습 방식의 레이블 데이터 과의존 문제를 해결하기 위해 새로운 학습 패러다임인 검증 학습(Verification Learning, VL)을 제안합니다. VL은 NeSy의 레이블 기반 추론 과정을 레이블이 없는 검증 과정으로 전환하여, 오직 비표시 데이터와 예측이 규칙을 준수하는지 확인하는 함수만을 사용하여 우수한 학습 결과를 달성합니다. 본 논문은 이 문제를 제약 최적화 문제(Constraint Optimization Problem, COP)로 공식화하고, 검증 시도를 줄여 계산 비용을 효과적으로 낮추는 동적 조합 정렬(Dynamic Combinatorial Sorting, DCS) 알고리즘을 제안합니다. 또한, 단축 경로 문제를 해결하기 위한 사전 정렬 방법을 제시하고, 어떤 NeSy 작업이 레이블 없이 수행될 수 있으며 어떤 경우 규칙이 무한한 레이블을 대체할 수 있는지, 그리고 어떤 경우 규칙이 효과가 없는지에 대한 이론적 분석을 제공합니다. 덧셈, 정렬, 매칭, 체스와 같은 여러 가지 완전 비지도 학습 과제를 통해 제안된 프레임워크의 성능 및 효율성 향상을 검증합니다.
