기술 요약: 규칙 유도를 위한 대칭 인식 파운데이션 모델

문제 정의

논리적 규칙 유도(Logical rule induction)는 다양한 명제 스키마 전반에 걸쳐 일반화할 수 있는 해석 가능한 가설(구체적으로는 논리합 표준형, 즉 DNF 규칙)을 학습하는 것을 목표로 한다. ILP(Inductive Logic Programming)나 LFIT(Learning from Interpretation Transition)와 같은 기존 방식은 노이즈가 있거나, 부분적으로 관찰되었거나, 보이지 않는 데이터에 대응하는 데 어려움을 겪는 경우가 많다. 신경-기호(neuro-symbolic) 방법론은 노이즈 내성을 제공하지만, 대개 태스크별 학습을 요구하며, 새로운 스키마에 제로샷(zero-shot)으로 전이할 수 있는 진정한 파운데이션 모델로서 기능하지 못한다.

이러한 모델의 확장을 가로막는 결정적인 장벽은 구조적 대칭성의 위반이다. 견고한 규칙 유도 모델은 논리 문제에 내재된 네 가지 핵심 대칭성을 준수해야 한다:

1. 예시 순서 ($S_M$): 훈련 예시의 순서를 치환하더라도 학습된 규칙은 변하지 않아야 한다.
2. 원자 이름 변경 ($S_N$): 원자(변수)의 이름을 변경하면 그에 대응하여 규칙의 이름도 변경되어야 한다.
3. 극성 반전 ($Z_2^N$): 원자의 극성을 반전시키면(예: $x_j \to \neg x_j$) 규칙 내의 해당 리터럴도 반전되어야 한다.
4. 레이블 스왑 ($Z_2^y$): 출력 레이블(0/1)을 바꾸면 학습된 규칙의 불리언 보수(Boolean complement)가 되어야 한다.

NRI(Neural Rule Inducer)와 같은 기존의 파운데이션 모델들은 예시 순서는 준수하지만, 원자 이름 변경, 극성 반환, 또는 레이블 스왑에 대한 등변성(equivariance)을 유지하는 데 실패한다. 결과적으로, 이들은 훈련 시 본 것보다 큰 스키마에 적용될 때 성능이 크게 저하되며, 내보낸(exported) 규칙들이 대칭 연산에 따라 올바르게 변환되지 않는다.

방법론

본 논문은 NRI의 대칭성이 복원된 버전인 G-NRI를 제안한다. 핵심 기여는 새로운 학습 알고리즘이 아니라, 추가적인 학습 가능 파라미터나 재학습 없이도 정확한 등변성을 보장하기 위해 설계된 **정준 내보내기 메커니즘(canonical export mechanism)**과 특정 아키텍처 수정 사항이다.

1. 대칭 그룹 정의

문제는 대칭 그룹 $G = S_M \times B_N \times Z_2^y$ 하에서 프레임화된다. 여기서 $B_N = S_N \ltimes Z_2^N$은 부호가 있는 원자 치환(signed atom permutations)을 나타낸다. 맵(map)이 $G$-등변적이라는 것은 모든 $G$의 변환과 교환 법칙이 성립함을 의미한다.

2. 아키텍처 수정 ( $B_N$ 복원)

원자의 치환 및 극성 반전에 대해 NRI의 내부 점수 생성이 등변성을 유지하도록 하기 위해, 인코더와 디코더에 세 가지 구체적인 수정 사항을 적용한다:

• 제로 리터럴 부호 특징 (Zero Literal Sign Feature): 양의 리터럴과 음의 리터럴을 구분하는 상수 특징을 0으로 설정하여, 모델이 고정된 부호 표현에 의존하는 것을 방지한다.
• 예시 어텐션 콘텐츠 키 비활성화 (Disable Example-Attention Content Keys): 예시에 대한 학습된 키를 비활성화하여, 집합(aggregation)이 특정 원자 순서에 의존하지 않도록 한다.
• 타이-완전 선택 (Tie-Complete Selection): 리터럴 쌍 사이의 동점(tie)을 원자 인덱스로 해결하는 대신(이는 치환 불변성을 깨뜨림), $k$번째 최적값과 점수가 동일한 모든 쌍을 유지하는 "타이-완전" 선택 방식을 사용한다.
• 극성 평균화 임베딩 (Polarity-Averaged Embeddings): $Z_2^N$ 등변성을 위해, 선택된 쌍의 임베딩을 극성 반전에 대해 평균화한다.

3. 정준 규칙 내보내기 ( $Z_2^y$ 및 전체 $G$ 복원)

연속적인 리터럴 점수($p^+, p^-$)로부터 이산적인 규칙을 디코딩하는 **정준 내보내기(canonical export)**를 도입하며, 이는 수학적으로 등변성이 보장된다:

• 존재 점수 ($s_j$): $\max(p^+_j, p^-_j)$로 정의되며, 극성 스왑에 대해 불변이다.
• 부호 대비 ($d_j$): $p^+_j - p^-_j$로 정의되며, 극성 스왑 시 부호가 바뀐다.
• 결정 로직: $s_j \ge 0.5$이고 $d_j \neq 0$인 경우 원자를 포함한다. 극성은 $d_j$의 부호에 의해 결정된다. 만약 $d_j = 0$(정확한 동점)인 경우, 임의로 극성을 할당하는 대신 원자를 제외(기권, abstention)한다.
• 듀얼 레일 선택 (Dual-Rail Selection): 레이블 스왑을 처리하기 위해, 두 개의 "레일"(양의 클래스와 음의 클래스)로부터의 예측을 평균 내고, 레이블 스왑 불변 비교기를 사용하여 최종 규칙 또는 그 드 모르간(De Morgan) 보수를 선택한다.
• 기권 (Abstention): 선택 과정에서 발생하는 정확한 동점에 대해 임의로 동점을 깨는 대신, 기권(빈 규칙 반환)한다.

4. 훈련 및 추론

• 대칭화된 훈련 (Symmetrised Training): 손실 함수는 레이블 스왑에 대한 예측의 평균을 취함으로써 대칭화되지만, 논문에서는 추론 시에만 적용되는 변형(구성 요소 1~4)도 거의 동일한 정확도를 달성한다고 언급한다.
• 제로샷 스케일링 (Zero-Shot Scaling): 모델은 작은 합성 스키마($N=6$에서 $12$)에서 훈련되며, 재학습 없이 최대$N=1024$의 스키마에 대해 평가된다.

주요 기여

1. 규칙 유도에서의 대칭성 공식화: 본 논문은 이진 규칙 유도를 그룹 $G = S_M \times B_N \times Z_2^y$ 하에서 정식화하고, 유도된 규칙이 입력 데이터의 변환과 정확히 일치하게 변환되어야 한다는 등변성을 정의한다.
2. 정확한 보증을 갖춘 정준 내보내기: 핵심 기여는 연속적인 점수로부터 이산적인 규칙을 끌어올리는 디코딩 메커니즘이다. 정리 2는 입력 점수가 $G$-등변적이라면, 정준 내보내기가 재학습 없이도 (논리적 동등성까지 고려했을 때) 정확히 $G$-등변적인 규칙을 생성함을 증명한다.
3. 스케일링의 실증적 검증: 훈련된 구조에 의해 대칭성을 강제함으로써, 작은 스키마에서 훈련된 모델이 더 큰 스키마($N=1024$)로 안정적으로 확장될 수 있음을 입증한다. 반면 베이스라인 모델은 성능이 크게 저하된다.

결과

평가는 합성 스트레스 테스트와 19개의 실제 데이터셋(UCI 벤치마크, MONK 문제, MUTAG, CLEVR-Hans3 포함)을 사용하여 수행되었다.

• 정확한 등변성 (RQ1): 합성 데이터에서 전체 G-NRI는 13가지 서로 다른 대칭 변환에 대해 100% 규칙 동등성을 달성했다. 실제 데이터에서 모델은 스키마 유효 변환(변환이 인코딩의 유효성을 보존하는 경우)에 대해 **정확한 등변성(1.000)**을 유지한다. 그러나 인코딩 유효성을 깨뜨리는 원시 변환(특히 Mushroom 및 MUTAG 데이터셋)의 경우 규칙 동등성이 0.785로 떨어지며, 이는 이 보증이 인코딩을 보존하는 부분군에 국한됨을 확인시켜 준다.
• 스케일링 신뢰성 (RQ2): $N=1024$까지의 스키마에서 평가했을 때, G-NRI는 안정적인 서포트 셋 정확도와 규칙 충실도를 유지한다. 반면 베이스라인 NRI는 $N$이 커짐에 따라 급격히 저하되어 무작위 확률에 가까워진다. 아키텍처 수정 사항만으로도 이러한 이득의 대부분을 설명할 수 있다.
• 실제 세계 전이 (RQ3): 19개의 실제 데이터셋에서 G-NRI는 베이스라인보다 높은 제로샷 정확도를 보였으며, 스키마 크기가 커질수록 개선 폭이 커졌다(예: $N > 100$인 스키마에서 +5.67 퍼센트 포인트).
• 규칙 품질: 내보내진 규칙은 압축적이다. 평균적으로 G-NRI는 약 2개의 절(clause)와 약 6개의 리터럴을 가진 DNF를 유도하며, 이는 의사결정 나무(Decision Tree)나 RIPPER 베이스라인보다 훨씬 희소하다. 다만 제로샷 전이를 고려할 때 태스크별로 훈련된 모델보다는 약간 낮은 정확도를 보인다.

의의 및 주장

본 논문은 구조적으로 대칭성을 강제하는 것이 작은 데이터로 사전 훈련된 모델을 변수 스키마로 전이 가능한 재사용 가능하고 해석 가능한 파운데이션 모델로 변모시킨다고 주장한다.

• 수학적 속성: 저자는 정출된 규칙의 정확한 등변성이 NRI 아키텍처의 특수한 기능이 아니라, 정준 내보내기 메커니즘의 수학적 속성임을 강조한다. $G$-등변적인 리터럴 점수를 제공하는 어떤 유도 모델이라도 이 내보내기를 사용할 수 있다.
• 재학습 불필로: 이 방법은 재학습이나 데이터셋별 적합(fitting) 없이 이러한 보증을 달성하며, 추론 시간에 아주 작은 상수 배의 시간(1.2~1.8배)만을 추가한다.
• 제한적 범위: 저자는 자신의 모델의 일반적인 경쟁력에 대해 겸손한 태도를 보인다. 즉, 모든 지표(예: "car"와 같은 다중 클래스 문제의 정확도)에서 태스크별 훈련된 학습자를 능가하지는 못한다. 그러나 대칭성 제약이 변수 스키마 기반의 파운데이션 모델에서 신뢰할 수 있는 스케일링을 위해 필수적임을 성공적으로 입증하였다.

이 연구는 도메인 대칭성(원자 명명, 극성, 레이블 스왑)을 존중하는 것이 단순한 학습 목표가 아니라, 훈련 분포 너머로 논리적 유도를 확장하기 위한 구조적 필수 요소임을 검증한다.